Complete Coverage Path Planning Algorithm Based on Greedy Extension
Changlei Xu, Lixing Wang · 2025
With the advancement of marine resource development and protection activities, tasks such as full geomorphology mapping and underwater area sweeping in turbid water pose serious challenges to underwater mobile robots. The complete coverage path planning algorithm based on the traditional algorithm cannot perceive global environmental information, and mobile robots can only sense the information of a limited range of areas, resulting in a gradual increase in the cumulative errors and an excessively high path repetition rate. This study introduces an enclosing perception strategy to solve the limitations of traditional complete coverage path planning algorithms in perceiving global information. In addition, a greedy approach is incorporated to extend inward gradually based on global information, adding uncovered grid points to the path until the path includes all grid points to be covered, thereby achieving a complete coverage path that allows the mobile robot to complete the complete coverage task and return exactly to its initial position. Based on this, the greedy extension algorithm in an unknown environment is proposed to address the full coverage task in an unknown environment. This algorithm can acquire complete environmental information while achieving full coverage. The simulation results demonstrate the effectiveness of the proposed algorithm, and the planned complete coverage path has a lower path repetition rate.