Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement

Isaac Ngui*, Courtney McBeth*, James D. Motes, Marco Morales, Nancy M. Amato · 2026

Read Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement by Isaac Ngui*, Courtney McBeth*, James D. Motes, Marco Morales, Nancy M. Amato (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-20395.txt.

Introduction

Ngui and four co-workers speed multi-robot motion planning by up to an order of magnitude. Planning all robots jointly avoids collisions but costs dearly in search over the joint configuration space. Their method searches a discrete workspace decomposition to coordinate robots, then refines it so planners search smaller decoupled spaces. The refinement step goes beyond prior topology-based methods that only decide when robots must be planned jointly.

Catalog record

CREATORIsaac Ngui*, Courtney McBeth*, James D. Motes, Marco Morales, Nancy M. Amato
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39194
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.20395

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement Isaac Ngui*, Courtney McBeth*, James D. Motes, Marco Morales, Nancy M. Amato Abstract A fundamental challenge in multi-robot motion planning is achieving sufficient coordination to avoid inter-robot conflicts without incurring the large computational expense of searching the joint configuration space of the robot group. In this work, we present a method for multiple mobile robot motion planning that achieves an improvement in planning time up to an order of magnitude by leveraging the insight that we can use discrete search over a workspace decomposition to provide coordination between robots during planning. While prior work uses workspace topology to inform when coordination between robots is needed and then composes robots into their joint configuration space, we take a step further by iteratively refining our workspace representation to allow our planner to search smaller, decoupled configuration spaces. † † *Equal Contribution 1 Introduction Multi-robot systems have applications ranging from autonomous warehouse management to search and rescue. These applications require careful multi-robot motion planning (MRMP) to avoid collisions with the environment and between robots. There exists a tradeoff between the amount of coordination provided during planning and planning speed, especially considering large robot groups with kinodynamic constraints. Searching the joint configuration space of the robot team, the composite space , ensures collision avoidance but comes at a significant computational cost due to the size of the space. Alternatively, decomposing the problem requires additional reasoning to prevent unresolved inter-robot conflicts. Existing approaches have explored using guidance , often provided by a workspace representation, to expedite MRMP. Prior works [ 8 , 7 ] use sampling guidance to bias sampling toward high-quality areas of the composite space. Several existing planners [ 7 , 20 , 16 ] leverage coordination guidance where the planner reasons over when robots should be composed into the same configuration space. Often, this is indicated by a topological skeleton of the workspace, which is an embedded graph where edges represent free areas of the workspace. While skeletons provide useful guidance to motion planners in environments with narrow passages, they struggle to represent open environments well, leading us to consider a region decomposition [ 11 ] to make our approach robust to environments with open spaces. These forms of guidance reduce the computational burden of providing coordination during planning, but still require planning in the composite space of multiple robots either for the entirety of planning or when inter-robot conflicts cannot otherwise be prevented. In this work, we take a step toward avoiding the computational bottleneck of planning in the composite space by introducing resolution guidance which provides coordination by reasoning over the workspace representation at different resolutions. Our proposed MRMP approach, Coordinated Incremental Planning with Hierarchical Expansion and Refinement (CIPHER) , adaptively refines the resolution of the workspace representation. By directing the movement of the robots over the workspace representation we provide coordination at a high level and reduce the need to plan in the composite space. We additionally recognize that we can refine our region decomposition during planning, leveraging resolution guidance. CIPHER features a hierarchical search, planning high-level paths for each robot over the workspace representation and then translating those into paths through configuration space. When multiple robots traverse a region, we attempt to further decompose that region to separate robots onto distinct paths over the workspace representation (Fig. 1 ). By doing this, we provide coordination between robots at a high level and reduce the need to compose robots into larger, computationally expensive configuration spaces. Our method shows an improvement in planning time up to an order of magnitude compared to other state-of-the-art geometric and kinodynamic MRMP approaches. Our contributions include: • CIPHER, a hybrid multi-robot motion planning algorithm that searches over a region decomposition to coordinate robots at a high level, reducing the need to plan in the composite space. • Resolution guidance, a process by which our method iteratively refines the workspace representation to direct the movement of robots at a finer level. • An extensive experimental validation that evaluates the strengths and weaknesses of our approach compared to other methods. (a) Decomposition (b) Skeleton Figure 1: (a) An example of iterative decomposition of the workspace representation. Robots’ paths over the region decomposition (colored lines) attempt to avoid coming into proximity with other robots. (b) A skeleton representation for the same environment. Despite the open space, robots are forced into proximity with each other by skeleton sampling guidance, increasing risk of conflicts. 2 Related Work In this section, we discuss related work in the fields of multi-robot motion planning and guided motion planning. We highlight strengths and weaknesses of existing approaches relative to our work. 2.1 Multi-robot Motion Planning Multi-robot motion planning methods can be categorized as coupled , decoupled , or hybrid . Coupled methods [ 13 ] plan paths by searching the composite space. While they provide high coordination, they lack scalability due to the large size of the composite space. Decoupled methods [ 13 , 1 ] plan for each robot separately, often using a priority ordering. These methods achieve high scalability but do not have the level of coordination required to solve complex problems. Hybrid methods seek to leverage the advantages of both coupled and decoupled planning. These methods leverage different forms of coordination guidance to decide when to search the composite space of multiple robots. We focus our discussion of multi-robot motion planning on offline hybrid planners and kinodynamic planners. Decoupled Kinodynamic RRT Coupled Kinodynamic RRT K-ARC K-WG-DaSH CIPHER Composition decoupled coupled hybrid hybrid hybrid Guidance Type kinematic skeleton cellular decomp Conflict Resolution prioritized planning subproblem subproblem guidance + subproblem Table 1: Multi-robot Kinodynamic Planner Characteristics Hybrid Planners Hybrid planners combine coupled and decoupled planning. Several methods do this by searching the individual robots’ configuration spaces first and then expanding the search space to provide more coordination as needed. Subdimensional expansion RRT (sRRT) [ 20 ] plans RRTs in the individual configuration spaces of each robot and follows those until inter-robot conflicts occur. Then, it expands the planning space to plan for the affected robots in their joint configuration space until they reach their goals. Adaptive Robot Coordination (ARC) [ 16 ] similarly plans decoupled paths, but uses local subproblems to resolve inter-robot conflicts when they occur. It attempts to use less expensive planners before resorting to replanning the relevant portion of the paths in the composite space. Discrete RRT (MRdRRT) [ 17 ] builds PRMs for each robot and searches the implicit composite space of the robots by building a tensor product roadmap. The scalability of these approaches shows the benefits of planning in smaller configuration spaces when possible, however, they do not support kinodynamic constraints and reactively account for collisions rather than proactively. Kinodynamic Planners Kinodynamic planners are required to find plans for robots that adhere to a set of kinodynamic constraints. Many single-robot planners have extended classical sampling-based algorithms to solve problems with kinodynamic constraints, like Kinodynamic RRT [ 4 , 5 , 10 ] , with many preserving the properties of sampling-based algorithms such as probabilistic completeness and asymptotic optimality. Additionally, many of these algorithms have also been extended to the multi-robot motion planning problem by

Read the complete text