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

Xingyao Han, Bo Cao, Zhe Liu, Shunbo Zhou, Heng Zhang, Hesheng WangIROS 2024 · OpenReview

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.
BibTeX
@inproceedings{han2024toward,
  author = {Xingyao Han and Bo Cao and Zhe Liu and Shunbo Zhou and Heng Zhang and Hesheng Wang},
  title = {{Toward Universal and Scalable Road Graph Partitioning for Efficient Multi-Robot Path Planning}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=0aLwx0Nv3v},
}

Loading related content...

Figure