Scalable Multi-Robot Motion Planning Using Workspace Guidance-Informed Hypergraphs
Open Access
- 19 February 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 11 (4) , 4929-4936
Abstract
In this work, we propose a method for multiple mobile robot motion planning that efficiently plans for robot teams up to 128 robots (an order of magnitude larger than existing state-of-the-art methods) in congested settings with narrow passages in the environment. We achieve this improvement in scalability by extending the state-of-the-art Decomposable State Space Hypergraph (DaSH) multi-robot planning framework to support mobile robot motion planning in congested environments. This is a problem that DaSH cannot be directly applied to because it lacks a highly structured, easily discretizable task space and features kinodynamic constraints. We accomplish this by exploiting knowledge about the workspace topology to limit exploration of the planning space and through modifying DaSH's conflict resolution scheme. This guidance captures when coordination between robots is necessary, allowing us to decompose the intractably large multi-robot search space while limiting risk of inter-robot conflicts by composing relevant robot groups together while planning.Keywords
All Related Versions
Funding Information
- IBM-Illinois Discovery Accelerator Institute and the Center for Networked Intelligent Components and Environments
- University of Illinois at Urbana-Champaign
This publication has 25 references indexed in Scilit:
- db-CBS: Discontinuity-Bounded Conflict-Based Search for Multi-Robot Kinodynamic Motion Planning2024
- Conflict-Based Search for Multi-Robot Motion Planning with Kinodynamic Constraints2022
- Topology-Guided Roadmap Construction With Dynamic Region SamplingIEEE Robotics and Automation Letters, 2020
- Dynamic Region-biased Rapidly-exploring Random Trees2020
- dRRT*: Scalable and informed asymptotically-optimal multi-robot motion planningAutonomous Robots, 2019
- Conflict-based search for optimal multi-agent pathfindingArtificial Intelligence, 2015
- Probabilistic path planning for multiple robots with subdimensional expansion2012
- M*: A complete multirobot path planning algorithm with performance bounds2011
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifoldsAdvances in Applied Mathematics, 1983