Large-Scale Multi-Robot Coverage Path Planning via Local Search (Extended Abstract)

We study graph-based Multi-Robot Coverage Path Planning (MCPP) that aims to compute paths for multiple robots to cover all vertices of a given 2D grid terrain graph G. Existing graph-based MCPP algorithms rely on computing a tree cover on G and then employ the Spanning Tree Coverage (STC) paradigm to generate coverage paths on the decomposed graph D of G. In this paper, we take a different approach by exploring how to systematically search for good coverage paths directly on D. We introduce a new algorithmic framework, called LS-MCPP, which leverages a local search to operate directly on D. We propose ESTC, that extends STC to achieve complete coverage for MCPP on any decomposed graphs, even those resulting from incomplete terrain graphs. Furthermore, we demonstrate how to integrate ESTC with three novel types of neighborhood operators into our framework to effectively guide its search process. Remarkably, LS-MCPP scales efficiently to handle MCPP instances with 32 robots on terrain graphs with 11,892 vertices with just minutes of runtime, thereby showcasing its significant benefits for large-scale real-world coverage tasks.