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

Problem Statement

Multi-robot motion planning (MRMP) faces a fundamental tradeoff between coordination and computational efficiency. Achieving sufficient coordination to avoid inter-robot conflicts typically requires searching the joint configuration space (composite space) of the robot group, which incurs a significant computational cost that scales exponentially with the number of robots. Conversely, decoupled approaches that plan for robots separately offer high scalability but often lack the coordination necessary to resolve complex conflicts, particularly in dense environments or those with kinodynamic constraints. Existing hybrid methods attempt to balance this by using workspace topology (e.g., skeletons) to guide planning, but these representations often struggle in open environments or force robots into unnecessary proximity, leading to increased conflict resolution costs.

Methodology: CIPHER

The authors propose CIPHER (Coordinated Incremental Planning with Hierarchical Expansion and Refinement), a hybrid MRMP algorithm that leverages resolution guidance to coordinate robots at a high level, thereby reducing the need to plan in the computationally expensive composite space.

Core Framework

CIPHER operates on a plan-check-resolve paradigm, structured into five phases:

1. Decomposition & MAPF (High-Level): The workspace is partitioned into a uniform grid of rectangular cells. A Multi-Agent Path Finding (MAPF) algorithm (specifically Conflict-Based Search) computes conflict-free sequences of region transitions for each robot. This provides a high-level topological guide independent of specific robot dynamics.
2. Guided Planning (Low-Level): Each robot independently computes a dynamically feasible trajectory using a sampling-based planner (RRT Connect for geometric systems; Region-Guided DB-RRT for kinodynamic systems). The high-level region path serves as a heuristic to bias sampling toward specific regions without strictly constraining the path, preserving probabilistic completeness.
3. Conflict Detection: The resulting trajectories are discretized into fixed-duration segments. The system checks all robot pairs for geometric conflicts at each timestep.
4. Hierarchical Conflict Resolution: If conflicts are detected, CIPHER employs an escalating hierarchy of strategies to resolve them without immediately resorting to composite space planning:
   • Decomposition Refinement: The specific grid cell where the conflict occurs is subdivided into a finer resolution. The MAPF problem is re-solved within this refined cell to find alternative sub-regions for the conflicting robots.
   • Spatial Expansion: If refinement fails, the resolution area is expanded to include adjacent cells (including diagonals). The MAPF problem is re-solved over this larger area to discover alternative routes.
5. Fallback Planning: If conflicts persist after exhausting the hierarchical resolution strategies, the planner falls back to a standard composite planner (Composite RRT) to solve the problem in the joint configuration space.

Key Distinctions

Unlike prior works that use skeleton-based guidance (which can restrict movement in open spaces) or reactive conflict resolution, CIPHER uses iterative region decomposition refinement. This allows the planner to proactively separate robots into distinct paths by increasing the resolution of the workspace representation only where necessary.

Key Contributions

The paper identifies three primary contributions:

1. CIPHER Algorithm: A hybrid planning algorithm that searches over a region decomposition to coordinate robots at a high level, significantly reducing the frequency of composite space planning.
2. Resolution Guidance: A novel process where the workspace representation is iteratively refined during planning. This allows the system to direct robot movement at a finer level of detail to resolve conflicts, rather than relying solely on static guidance.
3. Experimental Validation: An extensive evaluation comparing CIPHER against state-of-the-art geometric and kinodynamic MRMP approaches (including Coupled RRT, Decoupled RRT, sRRT, ARC, and WG-DaSH) across various environments.

Experimental Results

The authors evaluated CIPHER on both geometric and kinodynamic systems in environments ranging from empty spaces to highly cluttered rooms, with robot counts scaling up to 32.

• Success Rate: CIPHER achieved a 100% success rate across all tested environments and robot counts for both geometric and kinodynamic variants. In contrast, methods like WG-DaSH struggled in open environments due to skeleton constraints, and decoupled planners (like PP-RG-RRT) failed in high-density scenarios due to unresolved conflicts.
• Planning Time: CIPHER demonstrated planning time improvements of up to an order of magnitude compared to other state-of-the-art methods.
  • Compared to Coupled RRT, CIPHER avoided the exponential cost of joint space search.
  • Compared to Decoupled RRT and PP-RG-RRT, CIPHER maintained high success rates where others failed, while still being significantly faster than reactive hybrid methods (like sRRT and ARC) that only expand to composite space after conflicts occur.
• Kinodynamic Performance: For kinodynamic planners, CIPHER outperformed K-ARC and Kinodynamic WG-DaSH. While a naive guided planner (PP-RG-RRT) was faster, it suffered from low success rates in dense scenarios, highlighting the trade-off between speed and robustness that CIPHER successfully navigates.

Significance and Claims

The paper claims that CIPHER addresses the scalability bottleneck in multi-robot planning by shifting the coordination burden from the high-dimensional joint configuration space to a hierarchical workspace representation. By using resolution guidance, the method proactively avoids conflicts through adaptive refinement rather than reactively resolving them.

The authors assert that this approach allows for:

• Robustness: Effective performance in both open environments (where skeleton guidance fails) and narrow passages.
• Efficiency: A reduction in the computational expense associated with composite space planning, achieving speedups of up to 10x.
• Completeness: Theoretical probabilistic completeness is guaranteed because the algorithm falls back to a probabilistically complete composite planner if all hierarchical strategies fail.

The work suggests that refining the workspace representation itself can serve as a powerful mechanism for conflict resolution, offering a scalable alternative to traditional coupled or purely decoupled planning strategies.