Tree search algorithm for assigning cooperating UAVs to multiple tasks

Abstract This paper describes a tree search algorithm for assigning cooperating homogeneous uninhabited aerial vehicles to multiple tasks. The combinatorial optimization problem is posed in the form of a decision tree, the structure of which enforces the required group coordination and precedence for cooperatively performing the multiple tasks. For path planning, a Dubin's car model is used so that the vehicles' constraint, of minimum turning radius, is taken into account. Due to the prohibitive computational complexity of the problem, exhaustive enumeration of all the assignments encoded in the tree is not feasible. The proposed optimization algorithm is initialized by a best‐first search and candidate optimal solutions serve as a monotonically decreasing upper bound for the assignment cost. Euclidean distances are used for estimating the path length encoded in branches of the tree that have not yet been evaluated by the computationally intensive Dubin's optimization subroutine. This provides a lower bound for the cost of unevaluated assignments. We apply these upper and lower bounding procedures iteratively on active subsets within the feasible set, enabling efficient pruning of the solution tree. Using Monte Carlo simulations, the performance of the search algorithm is analyzed for two different cost functions and different limits on the vehicles' minimum turn radius. It is shown that the selection of the cost function and the limit have a considerable effect on the level of cooperation between the vehicles. The proposed deterministic search method can be applied on line to different sized problems. For small‐sized problems, it provides the optimal solution. For large‐sized problems, it provides an immediate feasible solution that improves over the algorithm's run time. When the proposed method is applied off line, it can be used to obtain the optimal solution, which can be used to evaluate the performance of other sub‐optimal search methods. Copyright © 2007 John Wiley & Sons, Ltd.