Hierarchy Coverage Path Planning With Proactive Extremum Prevention in Unknown Environments

The local extremum is a crucial factor that affects the efficiency of online coverage path planning (CPP). Most online CPP methods generate coverage motions point by point in unknown environments. However, these solutions ignore efficient global coverage and probably result in local extremum. This letter presents a hierarchy coverage path planning approach (HCPP) with proactive extremum prevention. HCPP incrementally generates coverage tasks and produces coverage motions in a global-to-local planning manner. Global planning generates a sequence of traversals of all coverage tasks, and local planning provides a route from one task to the next. By maintaining the connectivity of the uncovered area from both a global and local perspective, HCPP avoids the local extremums caused by separate areas. The effectiveness of HCPP was confirmed by multiple simulations and physical experiments in a laboratory setting on an Akerman robot. Experimental results indicate that HCPP reduces coverage times by preventing the local extremum while achieving complete coverage.

I. Introduction

Coverage path planning (CPP) is the task of planning a route that covers all points in a region with minimal time while avoiding obstacles [1]. This task is crucial for many robotic applications, such as area exploration, environmental monitoring, and search and rescue [2], [3], [4]. In all of these applications, the regions are completely or partially unknown. Hence, it is necessary to develop a sensor-based method for online exploration and coverage planning in unknown environments [5], [6].