Innovative collaborative task allocation for uavs

Decades of advances in electronics and communication technologies have enabled large-scale, flexible, reconfigurable multiple-UAV systems with a variety of applications ranging from large-scale military surveillance and reconnaissance to environmental monitoring and disaster response. Most of these applications require multiple tasks and service requests to be handled by a large group of UAVs in an efficient manner. Motivated by these problems, this chapter is devoted to a large-scale distributed task/target assignment problem for a fleet of autonomous UAVs. Central to this chapter is an algorithm that uses the delayed column generation approach on a non-convex supply-demand formulation for the problem. The algorithm exploits a computationally tractable distributed coordination structure, i.e., a market for tasks and targets created by the UAV fleet. The resulting structure is solved via a fleet-optimal dual simplex ascent in which each UAV updates its respective flight plan costs with a linear update of waypoint task values as evaluated by the market. Synchronized and asynchronous distributed implementations of this approximation algorithm is demonstrated in a thorough experimental study involving dynamically changing scenarios with random pop-up targets. Results from the tests performed on an in-house built network mission simulator are also provided for the numerical verification of the algorithm on (a) bounded polynomial-time computational complexity and (b) hard real-time performance for problem sizes on the order of 100 waypoints per UAV.