Adaptive Robot Coordination: A Subproblem-Based Approach for Hybrid Multi-Robot Motion Planning

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 innovative, cost-effective hybrid exploration of the multi-robot planning space by dynamically coupling and decoupling necessary subsets of robots only when required and in specific physical locations. 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 cost-efficient 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.