Multi-robot motion planning (MRMP) requires coordinating teams of robots to find collision-free paths without the prohibitive cost of searching the full joint configuration space, which grows exponentially with the number of robots. CIPHER (Coordinated Incremental Planning with Hierarchical Expansion and Refinement) addresses this by introducing resolution guidance — a novel coordination strategy that reasons over workspace representations at different resolutions to keep each robot’s planning space small while still avoiding inter-robot conflicts.

CIPHER Framework

CIPHER operates as a five-phase pipeline that alternates between high-level workspace reasoning and low-level trajectory planning:

  1. Decomposition & MAPF — partition the workspace into a uniform grid and compute conflict-free region paths for all robots using Conflict-Based Search (CBS)
  2. Guided Planning — each robot independently plans a dynamically feasible trajectory guided by its region path
  3. Conflict Detection — discretize trajectories and check for geometric inter-robot conflicts
  4. Conflict Resolution — apply escalating resolution strategies to eliminate detected conflicts
  5. Fallback Planning — if resolution fails, fall back to composite planning in the full joint configuration space

Unlike skeleton-based guidance methods, CIPHER’s uniform grid naturally covers the entire workspace, providing effective guidance in open environments without requiring narrow passages.

Workspace Decomposition

The workspace is partitioned into a uniform grid of rectangular cells. High-level coordination is computed using 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.

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:

  1. 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
  2. Spatial Expansion — expand the refinement region to include adjacent cells, broadening the search for alternative routes
  3. 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 state is \([x, y, \theta]\) and control inputs are linear and angular velocity \([v, \omega]\).

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 from 2 to 32 robots, against a broad set of geometric and kinodynamic baseline planners including Coupled RRT, Decoupled RRT, sRRT, ARC, WG-DaSH, and their kinodynamic analogs.

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 region size parameter controls the granularity of workspace guidance. The analysis below shows that a region size approximately 5 times the robot radius achieves the best balance between over-constraining the planner and providing insufficient coordination.

Code

CIPHER is publicly available:

https://github.com/parasollab/cipher

Publications

Updated: