MILP Formulation for Aircraft Path Planning in Persistent Surveillance

Persistent surveillance systems using manned or unmanned aerial vehicles play a crucial role in modern intelligence, surveillance, and reconnaissance missions. One of the crucial aspects that determine the quality of these systems is path planning. Path planning often attempts to optimize one or two objective metrics, such as coverage area, cost, or time, while meeting several constraints that would challenge these missions, such as weather, downtime, and amount of information gathered. A number of approaches have been proposed in the literature to address the path planning problem. However, the majority of these approaches are often based on a single objective measure, such as minimizing cost, maximizing travel distance, or maximizing coverage time. In cases where combined measures are considered, the formulations are often nondeterministic polynomial-time hard, leading to solutions that are computationally intractable. In this article, a mixed integer linear programming model with two conflicting objective functions-namely, maximizing coverage area and coverage time, has been developed. We propose a two-stage method to handle missions that involve multiple periods, multiple vehicles, and multiple dispersed areas while meeting a number of operational constraints, such as refueling and downtimes. Evaluations based on a number of simulated, yet realistic, scenarios show that our formulation leads to very promising outputs and performance.