Cooperative Mission Planning with Multiple UAVs in Realistic Environments

In this paper, a mission planning system is developed for managing multiple unmanned aerial vehicles (UAVs) of various capabilities to execute a series of missions over multiple targets. A target may need up to three tasks (i.e., classification, attack, and verification) to be carried out in sequence. The problem is addressed in two decision-making stages. First, the shortest feasible flying path for a UAV to fly between any pair of task locations is obtained using a customized A* algorithm. During the search, constraints such as collision avoidance from terrain, circumvention of flight prohibition zones, and the flying capabilities of UAVs are considered. In the second stage, with the obtained UAV flying paths between task locations, mission planning is modeled as a vehicle routing problem (VRP) with time window and precedence requirements. A genetic algorithm with a built-in mixed integer programming (MIP) solver is developed to solve the problem. The outputs of this proposed planning system include (1) task assignment among the UAVs, (2) mission execution schedule for each UAV, and (3) flying paths of the UAVs.