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
Hypergraph-based Multi-robot Motion Planning with Topological Guidance, Courtney McBeth, James Motes, Marco Morales, Nancy M. Amato, ArXiv Preprint, Nov 2023. @misc{mcbeth2023hypergraphbased, We present a multi-robot motion planning algorithm that efficiently finds paths for robot teams up to ten times larger than existing methods in congested settings with narrow passages in the environment. Narrow passages represent a source of difficulty for sampling-based motion planning algorithms. This problem is exacerbated for multi-robot systems where the planner must also avoid inter-robot collisions within these congested spaces, requiring coordination. Topological guidance, which leverages information about the robot's environment, has been shown to improve performance for mobile robot motion planning in single robot scenarios with narrow passages. Additionally, our prior work has explored using topological guidance in multi-robot settings where a high degree of coordination is required of the full robot group. This high level of coordination, however, is not always necessary and results in excessive computational overhead for large groups. Here, we propose a novel multi-robot motion planning method that leverages topological guidance to inform the planner when coordination between robots is necessary, leading to a significant improvement in scalability.
Keywords: Motion Planning, Multi-Agent, Workspace Topology
Links : [ArXiv] BibTex
title={Hypergraph-based Multi-robot Motion Planning with Topological Guidance},
author={Courtney McBeth and James Motes and Marco Morales and Nancy M. Amato},
year={2023},
eprint={2311.10176},
archivePrefix={arXiv},
primaryClass={cs.RO}
}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