Large-Scale Multi-Robot Coverage Path Planning on Grids with Path Deconfliction

Abstract--We study Multi-Robot Coverage Path Planning (MCPP) on a 4-neighbor 2D grid G, which aims to compute paths for multiple robots to cover all cells of G. Traditional approaches are limited as they first compute coverage trees on a quadrant coarsened grid H and then employ the Spanning Tree Coverage (STC) paradigm to generate paths on G, making them inapplicable to grids with partially obstructed 2 2 blocks. To address this limitation, we reformulate the problem directly on G, revolutionizing grid-based MCPP solving and establishing new NP-hardness results. We introduce Extended-STC (ESTC), a novel paradigm that extends STC to ensure complete coverage with bounded suboptimality, even when H includes partially obstructed blocks. These methods then apply the Spanning Tree Coverage (STC) [17] paradigm to generate coverage I. Coverage Path Planning (CPP) addresses the problem of determining However, operating exclusively on the coarsened grid H has a path that fully covers a designated workspace [1]. First, it fails in cases where H is This problem is essential for a broad spectrum of robotic incomplete--that is, when any 2 2 blocks contain obstructed applications, from indoor tasks like vacuum cleaning [2] and grid cells absent from G. Second, even optimal coverage trees inspection [3] to outdoor activities such as automated harvesting on H do not necessarily result in an optimal MCPP solution (as [4], planetary exploration [5], and environmental monitoring illustrated in Figure 1-(b) and (c)), as evidenced by an asymptotic [6]. Multi-Robot Coverage Path Planning (MCPP) is an suboptimality ratio of four for makespan minimization [14], extension of CPP tailored for multi-robot systems, aiming to since the paths derived from circumnavigating coverage trees coordinate the paths of multiple robots to collectively cover the of H constitute only a subset of all possible sets of coverage given workspace, thereby enhancing both task efficiency [7] The authors are with the School of Computing Science, Simon to discuss the structure and topology of G more precisely, especially in the Fraser University, Burnaby, BC V5A1S6, Canada. The robots require a cost of 1 to traverse between adjacent vertices of G. (a) Single-robot coverage path LS-MCPP but also those generated by existing MCPP methods, to effectively resolve conflicts between robots We revolutionize solving MCPP on grid graphs, overcoming and accounts for turning costs, further enhancing the the above limitations through a two-phase approach that first practicability of the solutions. Our algorithmic contribution are detailed in real-world robotics applications.