Toward Universal and Scalable Road Graph Partitioning for Efficient Multi-Robot Path Planning

Abstract

To date, multi-robot path planning has primarily been addressed by centralized solvers, typically aiming to maintain optimality. However, given its NP-hard nature, directly applying existing solvers in large and complex scenarios proves inefficient. A promising alternative lies in adopting a divide- and-conquer strategy to break down the problem into manageable sub-problems. In this work, we propose a systematic, universal, and scalable graph partitioning method, aiming to automatically divide any real-world environment into multiple regions. Building upon this, we convert the path planning on the entire graph into distributed sub-region path planning and devise corresponding inter-regional strategies. Our work can be easily implementable in practical systems and effectively enhances the scalability of existing solvers. Experimentally, our approach contributes to a tenfold improvement in computational efficiency while only sacrificing about 10% of optimality.