CIPHER: Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement
TL;DR
CIPHER (Coordinated Incremental Planning with Hierarchical Expansion and Refinement) is a scalable multi-robot motion planner built on resolution guidance: a coordination strategy that reasons over workspace representations at different resolutions to keep each robot's planning space small while still avoiding inter-robot conflicts. It achieves a 100% success rate across all geometric and kinodynamic test scenarios and plans up to an order of magnitude faster than decoupled RRT baselines.
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.
The CIPHER Framework
CIPHER operates as a five-phase pipeline that alternates between high-level workspace reasoning and low-level trajectory planning:
- Decomposition & MAPF — partition the workspace into a uniform grid and compute conflict-free region paths for all robots using Conflict-Based Search (CBS)
- Guided Planning — each robot independently plans a dynamically feasible trajectory guided by its region path
- Conflict Detection — discretize trajectories and check for geometric inter-robot conflicts
- Conflict Resolution — apply escalating resolution strategies to eliminate detected conflicts
- Fallback Planning — if resolution fails, fall back to composite planning in the full joint configuration space
The workspace is partitioned into a uniform grid of rectangular cells, and high-level coordination is computed with Conflict-Based Search (CBS), a Multi-Agent Path Finding (MAPF) algorithm that produces conflict-free region paths — sequences of grid cells — for each robot. Because CBS operates independently of robot dynamics, this step scales efficiently with the number of robots and robot types. Each robot then uses its region path to bias low-level sampling during trajectory planning, keeping planning largely decoupled across robots.
Unlike skeleton-based guidance methods, CIPHER's uniform grid naturally covers the entire workspace, providing effective guidance in open environments without requiring narrow passages.
CIPHER is probabilistically complete: if the hierarchical resolution strategies fail to find a solution, the method falls back to a composite RRT planner in the joint configuration space, which is itself probabilistically complete.
Conflict Resolution Strategies
When inter-robot conflicts are detected in the planned trajectories, CIPHER applies a three-tier hierarchy of resolution strategies rather than immediately resorting to expensive composite planning:
- Decomposition Refinement — locally refine grid cells in the conflict region to a finer resolution, giving MAPF more routing alternatives to find a conflict-free assignment
- Spatial Expansion — expand the refinement region to include adjacent cells, broadening the search for alternative routes
- Fallback — prioritized decoupled RRT, then composite RRT in the full joint configuration space, preserving probabilistic completeness
This hierarchy resolves most conflicts at low cost, reserving expensive joint-space planning only when necessary.
Kinodynamic Planning
For robots with differential constraints, CIPHER uses a Region-Guided Discontinuity Bounded RRT (DB-RRT) that incorporates trajectory optimization. This extends resolution guidance beyond simple geometric robots to handle real-world dynamic constraints such as first-order unicycle kinematics, where the state is [x, y, θ] and the control inputs are the linear and angular velocities [v, ω].
The kinodynamic variant applies the same five-phase framework, with the low-level planner replaced by the region-guided DB-RRT.
Experimental Evaluation
CIPHER was evaluated across five environment types — empty, rooms, low clutter, medium clutter, and high clutter — scaling in multiples of 2 from 2 up to 32 robots, with ten random seeds per scenario and a 600-second planning budget. Baselines include a broad set of geometric and kinodynamic planners: Coupled RRT, Decoupled RRT, sRRT, ARC, WG-DaSH, their kinodynamic analogs (including K-ARC and K-WG-DaSH), and a naive prioritized region-guided baseline (PP-RG-RRT). Key results:
- 100% success rate across all geometric and kinodynamic test scenarios
- Planning times up to an order of magnitude faster than Decoupled RRT
- Consistently outperforms WG-DaSH in open environments where skeleton-based guidance struggles
- The naive PP-RG-RRT baseline achieves fast planning times but suffers low success rates as the number of robots grows — CIPHER's explicit conflict detection and resolution is what maintains reliability at scale
Environments
The five experimental environments, shown below with the starts and goals for a 16-robot problem. Starts and goals are drawn as outlines of the robots, with goals as dashed lines.
Empty
Rooms
Low Clutter
Medium Clutter
High Clutter
Geometric Planners
Average planning time (left) and success rate (right) over 10 seeds for the geometric planners. Standard deviation in the planning times is shown where more than one seed succeeded; results are omitted where all seeds failed.
Empty
Rooms
Low Clutter
Medium Clutter
High Clutter
Kinodynamic Planners
Average planning time (left) and success rate (right) over 10 seeds for the kinodynamic planners. Standard deviation in the planning times is shown where more than one seed succeeded; results are omitted where all seeds failed.
Empty
Rooms
Low Clutter
Medium Clutter
High Clutter
Region Size Ablation
The region size parameter controls the granularity of workspace guidance. The analysis above shows that a region size approximately 5 times the robot radius achieves the best balance between over-constraining the planner and providing insufficient coordination — regions close to the robot's size over-constrain the problem, while overly large regions provide too little coordination.
Future Work
Future directions include exploring different forms of workspace representations, such as adaptive decompositions, and providing better representations of narrow passages, where a uniform grid may require significant refinement before it captures the connectivity of the free space.
BibTeX
@inproceedings{ngui2026cipher,
title={Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement},
author={Ngui, Isaac and McBeth, Courtney and Motes, James D. and Morales, Marco and Amato, Nancy M.},
booktitle={World Symposium on the Algorithmic Foundations of Robotics (WAFR)},
year={2026},
note={To appear. arXiv:2605.20395}
}