Constrained coverage path planning: evolutionary and classical approaches

The constrained coverage path planning addressed in this paper refers to finding an optimal path traversed by a unmanned aerial vehicle (UAV) to maximize its coverage on a designated area, considering the time limit and the feasibility of the path. The UAV starts from its current position to assess the condition of a new entry to the area. Nevertheless, the UAV needs to comply with the coverage task, simultaneously and therefore, it is likely that the optimal policy would not be the shortest path in such a condition, since a wider area can be covered through a longer path. From the other side, along with a longer path, the UAV may not reach to the target in due time. In addition, the speed of UAV is assumed to be constant and as a result, a feasible path needs to be smooth enough to support this assumption. The problem is modeled as an Epsilon-constraint optimization in which a coverage function has to be maximized, considering the constraints on the length and the smoothness of the path. For this purpose, a new genetic path planning algorithm with adaptive operator selection is proposed to solve such a complicated constrained optimization problem. The proposed approach has been compared to some classical approaches like, a modified version of the Artificial Potential Field and a modified version of Dijkstra's algorithm (a graph-based approach). All the methods are implemented and tested in different scenarios and their performances are evaluated via the simulation results.