Multi-robot hybrid techniques behave decoupled to obtain individual paths to guide robots but behave coupled to provide coordination when conflicts arise. Hybrid techniques offer a solution to many real-world problems, such as payload transportation and manufacturing, often involve deploying a considerable number of robots, demanding precise coordination. Achieving coordination and scalability is a common challenge in Multi-Robot Motion Planning (MRMP) scenarios, illustrated by the inherent trade-off between coupled and decoupled MRMP solvers. Consequently, we investigate hybrid approaches that integrate decoupled and coupled behaviors to provide improved scalability and coordination.
All methods are available in the Open-Source Parasol Planning Library.
CBS-MP: Conflict-based Search for Motion Planning
CBS-MP is an extension of Conflict-Based Search (CBS) which addresses efficiently the complexity of multi-robot motion planning problems. CBS is a recognized hybrid algorithm for Multi-Agent Pathfinding (MAPF), to resolve conflicts efficiently. By constructing individual roadmaps for each robot in the team, CBS-MP utilizes an adapted CBS framework for effective queries. This approach, while probabilistically complete, excels at finding optimal solutions with respect to the robots' state space representations.
Algorithm Overview
Initialization- Sample individual roadmaps until each one contains a valid path for each robot.
- Uniformly discretize the robots' paths with respect to traversal time.
- Utilize discretized paths to detect real-time conflicts between robots.
- Generate roadmap constraints derived from conflicts to create CT child nodes.
- Plan conflict-free by avoiding the roadmap constraints.
- Expand the CT until the first solution is found.
Evaluation
CBS-MP was compared with other decoupled, hybrid and coupled multi-robot planners to evaluate its efficacy.
The algorithms were tested on different environments considering different types of multi-robot systems, including mobile, manipulator, and heterogeneous.
- CBS-MP shows significantly better run time and is the only method able to plan for 32 robots.
- CBS-MP finds lower-cost solutions while using sparser roadmaps.
ARC: Adaptive Robot Coordination
Adaptive Robot Coordination (ARC) framework is a hybrid approach for multi-robot motion planning (MRMP), employing local subproblems to resolve inter-robot conflicts. ARC dynamically adjusts the coordination level by exploring both coupled and decoupled planning spaces, demonstrating probabilistic completeness, adaptability for any robot, and efficient, cost-effective solutions within reduced planning times.
Algorithm Overview
MRMP framework- Compute initial paths through sampling and querying individual roadmaps
- Detect conflicts among two or more robots
- Define subproblems around conflicts to obtain feasible paths
- Upon conflict detection, subproblems are defined around conflicts.
- Solutions to subproblems are utilized to repair robot paths and resolve conflicts.
- When subproblems are unsolvable, we adapt them to consider additional robots or space.
Evaluation
ARC was compared against decoupled, coupled, and hybrid baselines in scenarios requiring low, high, and varying levels of coordination.
- ARC stands out as the sole method capable of addressing the varying coordination scenario, encompassing conflicts with diverse levels of complexity and involving varying numbers of robots.
- ARC competes effectively with decoupled approaches, which demonstrate scalability in scenarios with low coordination, and coupled approaches, which excel in scenarios demanding higher levels of coordination.
Related Publications
Adaptive Robot Coordination: A Subproblem-based Approach for Hybrid Multi-Robot Motion Planning, Irving Solis, James Motes, Mike Qin, Marco Morales, Nancy M. Amato, ArXiv Preprint, Dec 2023. DOI: https://arxiv.org/abs/2312.08554 @misc{solis2023adaptive, 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: Motion Planning, Multi-Agent Systems, Sampling-Based Motion Planning
Links : [ArXiv] BibTex
title={Adaptive Robot Coordination: A Subproblem-based Approach for Hybrid Multi-Robot Motion Planning},
author={Irving Solis and James Motes and Mike Qin and Marco Morales and Nancy M. Amato},
year={2023},
eprint={2312.08554},
archivePrefix={arXiv},
primaryClass={cs.RO}
}Abstract
Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search, Irving Solis, James Motes, Read Sandström, Nancy M. Amato, IEEE Robotics and Automation Letters, Mar 2021. DOI: https://doi.org/10.1109/LRA.2021.3068910 @article{solis2019representation, Multi-Agent Motion Planning (MAMP) is the problem of computing feasible paths for a set of agents each with individual start and goal states within a continuous state space. Existing approaches can be split into coupled methods which provide optimal solutions but struggle with scalability or decoupled methods which provide scalable solutions but offer no optimality guarantees. Recent work has explored hybrid approaches that leverage the advantages of both coupled and decoupled approaches in an easier discrete subproblem, Multi-Agent Pathfinding (MAPF). In this work, we adapt recent developments in hybrid MAPF to the continuous domain of MAMP. We demonstrate the scalability of our method to manage groups of up to 32 agents, demonstrate the ability to handle up to 8 high-DOF manipulators, and plan for heterogeneous teams. In all scenarios, our approach plans significantly faster while providing higher quality solutions.
Keywords: Industrial Applications, Motion Planning, Multi-Agent
Links : [Published] [Manuscript] BibTex
title={Representation-optimal multi-robot motion planning using conflict-based search},
author={Solis, Irving and Sandstr{\"o}m, Read and Motes, James and Amato, Nancy M},
journal={arXiv preprint arXiv:1909.13352},
year={2019}
}Abstract