R-DFS: A Coverage Path Planning Approach Based on Region Optimal Decomposition
Gang Tang, Congqiang Tang, Hao Zhou, Christophe Claramunt, Shaoyang Men
Abstract
Most Coverage Path Planning (CPP) strategies based on the minimum width of a concave polygonal area are very likely to generate non-optimal paths with many turns. This paper introduces a CPP method based on a Region Optimal Decomposition (ROD) that overcomes this limitation when applied to the path planning of an Unmanned Aerial Vehicle (UAV) in a port environment. The principle of the approach is to first apply a ROD to a Google Earth image of a port and combining the resulting sub-regions by an improved Depth-First-Search (DFS) algorithm. Finally, a genetic algorithm determines the traversal order of all sub-regions. The simulation experiments show that the combination of ROD and improved DFS algorithm can reduce the number of turns by 4.34%, increase the coverage rate by more than 10%, and shorten the non-working distance by about 29.91%. Overall, the whole approach provides a sound solution for the CPP and operations of UAVs in port environments.