Multi-Task Allocation and Path Planning for Cooperating UAVs

John Bellingham, Michael Tillerson, Arthur Richards, Jonathan How
Conference on Coordination, Control and Optimization, Nov. 2001.

This paper presents results on the guidance and control of fleets of cooperating Unmanned Aerial Vehicles (UAVs). A key challenge for these systems is to develop an overall control system architecture that can perform optimal coordination of the fleet, evaluate the overall fleet performance in real-time, and quickly reconfigure to account for changes in the environment or the fleet. The optimal fleet coordination problem includes team composition and goal assignment, resource allocation, and trajectory optimization. These are complicated optimization problems for scenarios with many vehicles, obstacles, and targets. Furthermore, these problems are strongly coupled, and optimal coordination plans cannot be achieved if this coupling is ignored. This paper presents an approach to the combined resource allocation and trajectory optimization aspects of the fleet coordination problem which calculates and communicates the key information that couples the two. Also, this approach permits some steps to be distributed between parallel processing platforms for faster solution. This algorithm estimates the cost of various trajectory options using the distributed platforms and then solves a centralized assignment problem to minimize the mission completion time. The detailed trajectory planning for this assignment can then be distributed back to the platforms. During execution, the coordination and control system reacts to changes in the fleet or the environment. The overall approach is demonstrated on several example scenarios to show multi-task allocation and cooperative path planning prior to the mission and to show dynamic re-planning to account for changes in the environment during execution.

Download: Paper

Professor Jonathan P. How

November 24, 2002