2024/09/04 by Megnath Ramesh, Ramesh, Megnath, Frank Imeson +5 · 1 citation
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.2409.03120
openalex publication_date 2024/09/04 · openalex created_date 2024/10/19 · openalex updated_date 2026/07/28
In this paper, we investigate the problem of decomposing 2D environments for robot coverage planning. Coverage path planning (CPP) involves computing a cost-minimizing path for a robot equipped with a coverage or sensing tool so that the tool visits all points in the environment. CPP is an NP-Hard problem, so existing approaches simplify the problem by decomposing the environment into the minimum number of sectors. Sectors are sub-regions of the environment that can each be covered using a lawnmower path (i.e., along parallel straight-line paths) oriented at an angle. However, traditional methods either limit the coverage orientations to be axis-parallel (horizontal/vertical) or provide no guarantees on the number of sectors in the decomposition. We introduce an approach to decompose the environment into possibly overlapping rectangular sectors. We provide an approximation guarantee on the number of sectors computed using our approach for a given environment. We do this by leveraging the submodular property of the sector coverage function, which enables us to formulate the decomposition problem as a submodular set cover (SSC) problem with well-known approximation guarantees for the greedy algorithm. Our approach improves upon existing coverage planning methods, as demonstrated through an evaluation using maps of complex real-world environments.