Adaptive Robot Coordination: A Subproblem-based Approach for Hybrid Multi-Robot Motion Planning
Authors:
- Irving SolisISIrving Solis
- James MotesJMJames Motes
- Mike QinMQMike Qin
- Marco MoralesMMMarco Morales
- Nancy M. AmatoNANancy M. Amato
Preprint
Abstract
This work presents Adaptive Robot Coordination (ARC), a novel hybrid framework for multi-robot motion planning (MRMP) that employs local subproblems to resolve inter-robot conflicts. ARC creates subproblems centered around conflicts, and the solutions represent the robot motions required to resolve these conflicts. The use of subproblems enables an inexpensive hybrid exploration of the multi-robot planning space. ARC leverages the hybrid exploration by dynamically adjusting the coupling and decoupling of the multi-robot planning space. This allows ARC to adapt the levels of coordination efficiently by planning in decoupled spaces, where robots can operate independently, and in coupled spaces where coordination is essential. ARC is probabilistically complete, can be used for any robot, and produces efficient cost solutions in reduced planning times. Through extensive evaluation across representative scenarios with different robots requiring various levels of coordination, ARC demonstrates its ability to provide simultaneous scalability and precise coordination. ARC is the only method capable of solving all the scenarios and is competitive with coupled, decoupled, and hybrid baselines.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Representation-Optimal Multi-Robot Motion Planning Using Conflict-Based SearchIEEE Robotics and Automation Letters, 2021
- Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planningThe International Journal of Robotics Research, 2016
- Conflict-based search for optimal multi-agent pathfindingArtificial Intelligence, 2015
- Subdimensional expansion for multirobot path planningArtificial Intelligence, 2015
- Coordinated path planning for multiple robotsRobotics and Autonomous Systems, 1998
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979