Multiperiod Coverage Path Planning and Scheduling for Airborne Surveillance

In this paper, optimal surveillance mission plans are developed to cover disjoint areas of interest (AOIs) over an extended time horizon using multiple aerial vehicles. AOIs to be covered are divided into a number of cells. To promptly update information collected from AOIs and to ensure persistent surveillance, each cell is to be revisited within a time slot. Joint path planning and temporal scheduling is formulated as a combinatorial optimization with the proposal of novel objective functions: 1) maximizing the minimum number of nonrepeatedly covered cells in a sliding-window fashion and 2) maximizing the total number of covered cells in the mission plan. A multiobjective evolutionary algorithm (MOEA) with a specific chromosome representation and custom genetic operators, in which the constraint that each cell be revisited within a time slot is transformed into the third objective to handle infeasibility, is developed. The initial single-period paths are generated by solving a series of orienteering problems. The initial population is obtained by connecting these single-period paths and selecting the take-off time for each flight. Three mutation moves are proposed to enable revisiting in a single-period path and rescheduling of take-off time. The solutions converge in the MOEA and are selected by a weighted-sum model according to user preferences in decision making. Simulation results on different mission scenarios and different criteria show the superiority of the proposed algorithm. The algorithm is done offline ahead of the missions and requires modest computational resources.