Many real-world environments like automated warehouses feature large groups of robots navigating through narrow passages in the workspace. In these scenarios, a high degree of coordination during planning is required to avoid inter-robot collisions. Previous work on Dynamic Regions planning strategies has shown that using a topological skeleton of the workspace to guide motion planning can significantly improve the efficiency of planning. We explore extending topological guidance to the multi-robot domain to efficiently search the planning space. All methods are available in the Open-Source Parasol Planning Library.
CDR-RRT: Composite Dynamic Region RRT
We extend Dynamic Regions-biased RRT, a single-robot motion planning method that leverages a topological skeleton to the multi-robot domain to propose Composite Dynamic Regions-biased RRT (CDR-RRT) (available in PPL).
Algorithm Overview
Composite Workspace SkeletonWe develop a composite space analog of the topological skeleton and use this structure to guide planning. A composite skeleton is the Cartesian product graph of the individual topological skeletons for each of the robots in the system. In the example pictured below, one composite skeleton edge is made up of one individual skeleton edge (highlighted in blue) for each robot. The whole composite skeleton is made up of all possible vertex/edge combinations.
Skeleton Guided RRT Construction
The size of the composite skeleton is exponential in the number of robots, so we leverage local, on-demand construction of the skeleton as we heuristically search through it, minimizing the portion of the composite skeleton that we actually see. We grow an RRT by sampling robot group configurations from dynamic sampling regions that move along composite skeleton edges.
Evaluation
In the video below, we demonstrate a comparison of our method against a set of other state-of-the-art coupled, decoupled, and hybrid methods, which provide varying levels of coordination during planning. We demonstrate that our method is able to:- scale to larger teams of robots in congested environments than other methods we compared against
- find higher-quality solutions as a result of topological skeleton guidance
Workspace-DaSH: Workspace Decomposable State Space Hypergraph
Building off of CDR-RRT and the existing DaSH hybrid planning framework, we leverage the skeleton for multiple purposes. As in CDR-RRT the skeleton guides planning though narrow passages in the workspace, limiting the size of the planning space being explored. Additionally, we use the skeleton's natural ability to inform when groups of robots will be in proximity to each other, requiring coordination, and should be locally considered jointly (available in PPL).
Algorithm Overview
Hypergraph SkeletonA hypergraph is a generalization of a graph where hyperarcs represent transitions between sets of vertices. We construct a hypergraph representing the high-level path of each robot over the topological skeleton called the hypergraph skeleton. The example pictured below (left) shows a small portion of the high-level path each robot takes over the skeleton graph (shown in pink). The arrows indicate the current direction of motion of the robots. The dashed line for the yellow robot shows its motion at the next, rather than the current, high-level timestep. The image on the right shows the portion of the hypergraph skeleton that results from these high-level paths. When robots approach the same vertex or edge, they are coupled together, and when the robots move away from each other as indicated by the skeleton, they are decoupled.
Translation to Paths Through CSpace
After the construction of the hypergraph skeleton, we use it to guide the construction of paths through the CSpace for each robot, searching the composite sub-spaces of the groups of robots considered in each of the hyperarcs of the hypergraph skeleton and using dynamic regions sampling. This allows the planner to stay in low-dimensional planning spaces as long as possible, only moving into higher dimensional spaces when the skeleton informs that coordination is necessary.
Evaluation
Workspace-DaSH was compared against CDR-RRT as well as several other state-of-the-art multi-robot motion planning methods which provide various levels of coordination during planning. The results below show the Mining scenario (available in the motion planning benchmarks), modeled after a real-life application of navigation through mine shafts. Only Workspace-DaSH and CDR-RRT where able to solve the scenario even with two robots due to the geometric complexity of the environment.
We show that by using the topological skeleton to decompose the planning space while still providing the necessary level of coordination, we can greatly improve planning efficiency.
Related Publications
Scalable Multi-Robot Motion Planning Using Guidance-Informed Hypergraphs, Courtney McBeth, James Motes, Isaac Ngui, Marco Morales, Nancy M. Amato, ArXiv Preprint, Jun 2024. @misc{mcbeth2024scalablemultirobotmotionplanning, In this work, we present a multi-robot planning framework that leverages guidance about the problem to efficiently search the planning space. 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. Our framework additionally supports planning with kinodynamic constraints through our conflict resolution structure. This structure also improves the scalability of our approach by eliminating unnecessary work during the construction of motion solutions. We also provide an application of this framework to multiple mobile robot motion planning in congested environments using topological guidance. Our previous work has explored using topological guidance, which utilizes information about the robots' environment, in these multi-robot settings where a high degree of coordination is required of the full robot group. In real-world scenarios, this high level of coordination is not always necessary and results in excessive computational overhead. Here, we leverage our novel framework to achieve a significant improvement in scalability and show that our method efficiently finds paths for robot teams up to an order of magnitude larger than existing state-of-the-art methods in congested settings with narrow passages in the environment.
Keywords: Motion Planning, Multi-Agent, Workspace Topology
Links : [ArXiv] BibTex
title={Scalable Multi-Robot Motion Planning Using Guidance-Informed Hypergraphs},
author={Courtney McBeth and James Motes and Isaac Ngui and Marco Morales and Nancy M. Amato},
year={2024},
eprint={2311.10176},
archivePrefix={arXiv},
primaryClass={cs.RO},
url={https://arxiv.org/abs/2311.10176},
}Abstract
Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance, Courtney McBeth, James Motes, Diane Uwacu, Marco Morales, Nancy M. Amato, In IEEE Robotics and Automation Letters, Aug 2023. DOI: 10.1109/LRA.2023.3312980 @ARTICLE{10243143, Multi-robot motion planning (MRMP) is the problem of finding collision-free paths for a set of robots in a continuous state space. The difficulty of MRMP increases with the number of robots and is exacerbated in environments with narrow passages that robots must pass through, like warehouse aisles where coordination between robots is required. In single-robot settings, topology-guided motion planning methods have shown improved performance in these constricted environments. In this work, we extend an existing topology-guided single-robot motion planning method to the multi-robot domain to leverage the improved efficiency provided by topological guidance. We demonstrate our method's ability to efficiently plan paths in complex environments with many narrow passages, scaling to robot teams of size up to 25 times larger than existing methods in this class of problems. By leveraging knowledge of the topology of the environment, we also find higher-quality solutions than other methods.
Keywords: Motion Planning, Multi-Agent, Workspace Topology
Links : [Published] [ArXiv] [Video] BibTex
author={McBeth, Courtney and Motes, James and Uwacu, Diane and Morales, Marco and Amato, Nancy M.},
journal={IEEE Robotics and Automation Letters},
title={Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance},
year={2023},
volume={},
number={},
pages={1-8},
doi={10.1109/LRA.2023.3312980}}Abstract