K-ARC: Adaptive Robot Coordination for Multi-Robot Kinodynamic Planning
Mike Qin, Juan Irving Solis Vidana, James Motes, Marco Morales, Nancy Amato
AI summary
Problem
Existing multi-robot kinodynamic planners struggle to balance scalability and coordination, as coupled methods face exponential state-space growth and decoupled methods fail in highly constrained environments.
Approach
The algorithm divides initial paths into segments and iteratively computes dynamically feasible trajectories, deploying a prioritized hierarchy of optimization and sampling solvers only when inter-robot conflicts arise.
Key results
- Plans trajectories for up to 32 planar mobile robots
- Achieves up to two orders of magnitude speed-up over baselines
- Scales robustly across increasing robot counts and dynamic complexities
- Dynamically balances planning speed and solution robustness
Why it matters
Provides a scalable planning framework essential for real-world multi-robot applications like warehouse automation and delivery systems that require both dynamic feasibility and high coordination.
Abstract
This work presents Kinodynamic Adaptive Robot Coordination (K-ARC), a novel algorithm for multi-robot kino- dynamic planning. Our experimental results show the capability of K-ARC to plan for up to 32 planar mobile robots, while achieving up to an order of magnitude of speed-up compared to previous methods in simulated scenarios. K-ARC is able to achieve this due to its two main properties. First, K-ARC constructs its solution iteratively by planning in segments, where initial kinodynamic paths are found through optimization-based approaches and the inter-robot conflicts are resolved through both optimization and sampling-based approaches. The inter- leaving use of both approaches allows K-ARC to leverage the strengths of each in different sections of the planning process where one is more suited than the other, while previous methods tend to emphasize one over the other. Second, K-ARC builds on a previously proposed multi-robot motion planning framework, Adaptive Robot Coordination (ARC), and inherits its strength of focusing on coordination between robots only when needed, saving computational effort. We show how the combination of these two properties allows K-ARC to achieve better overall performance in our simulated experiments with increasing num- bers of robots, increasing degrees of problem difficulties, and increasing complexities of robot dynamics.