Coordinated Target Assignment and UAV Path Planning with Timing Constraints

The engagement of a group of autonomous air vehicles against several targets is a major challenge in mission planning. This paper addresses the problem of cooperative flight path planning where the air vehicles should arrive at the destinations simultaneously or sequentially with specified time delays, while minimizing the total mission time. This involves finding an optimal assignment of air vehicles to targets and generating trajectories in compliance with the kinematic constraints of the vehicles. The trajectories have to avoid nofly-areas, threats and other obstacles, and must prevent the air vehicles from colliding with each other. The presented algorithm for simultaneous arrival first calculates shortest flight paths between all pairs of air vehicles and targets using a network-based routing model. An optimal assignment and a critical path is found by solving a linear bottleneck assignment problem with costs corresponding to the lengths of the shortest paths. The other flight paths are prolongated to the length of the critical path by automatic insertion of waypoints. This is achieved by concatenating subpaths stored in different shortest-path-trees. Due to the special structure of the network, all concatenated flight paths are flyable and feasible. Sequential arrival at a target is realized by sorting the flight paths according to their lengths and prolongating them whenever necessary to accomplish the desired time delays. The capability of the approach is demonstrated by simulation results.