R-DFS: A Coverage Path Planning Approach Based on Region Optimal Decomposition

Remote Sensing

Hao Zhou¹  Congqiang Tang¹  Gang Tang¹  Christophe Claramunt²  Shaoyang Men³ 

[1] Logistics Engineering College, Shanghai Maritime University, Shanghai 201306, China;Naval Academy Research Institute, F-29240 Lanvéoc, France;School of Medical Information Engineering, Guangzhou University of Chinese Medicine, Guangzhou 510006, China;

关键词: coverage path planning;    region optimal decomposition;    depth-first-search algorithm;    remote sensing;   

DOI  :  10.3390/rs13081525

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown