Branch and bound tree search for assigning cooperating UAVs to multiple tasks
Steven J. Rasmussen, Tal Y. Shima · 2006
This paper describes a branch and bound optimization 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' dynamic constraint, of minimum turning radius, is taken into account. 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. It is shown that the algorithm's convergence rate is dependent on the optimized cost function of the cooperative mission