Passage-Focused Soft Coordination for Hierarchical Multi-Robot Navigation in Bottleneck Environments

Haoze Dong, Stepan Dergachev, Meng Guo, Konstantin Yakovlev, Zhongkui LiarXiv 2026 · arXiv

TL;DR

This paper introduces a hierarchical navigation framework that solves the "bottleneck problem" in multi-robot systems by combining long-horizon "soft" global coordination with flexible local execution. By using a passage-focused graph of convex sets and an adaptive MPPI controller, the system achieves near-perfect success rates in cluttered environments, outperforming traditional rigid scheduling methods in both efficiency and robustness.

What Problem Does This Paper Address?

Multi-robot navigation in crowded environments—specifically narrow passages or "bottlenecks"—is a balancing act.

On one hand, global planners (like MAPF) are great at coordinating who goes through a door and when, but they usually produce rigid schedules. If one robot gets delayed by a stray obstacle, the whole plan can fall apart. On the other hand, local reactive methods (like ORCA) are excellent at dodging immediate collisions but are "short-sighted." Without a high-level plan, robots often end up in deadlocks at narrow openings, like two people trying to walk through a narrow doorway at the same time and getting stuck.

The authors address this gap: how do we coordinate bottleneck traversal over long horizons without stripping robots of the flexibility they need to handle local, real-time interactions?

Methods

The authors propose a two-layer hierarchical framework:

  1. Global Layer (Soft Coordination): Instead of hard "reservations," the global planner uses a Passage-Induced Graph of Convex Sets (ST-GCS).
  2. Spatial Route Selection: Robots choose routes based on "passage-usage records," penalizing routes that are already congested.
  3. Temporal Optimization: Within the chosen route, the planner optimizes traversal timing using soft space-time conflict penalties. It doesn't forbid robots from being in the same place at the same time; it just makes it "expensive" in the optimization cost, encouraging them to spread out.
  4. Local Layer (Adaptive MPPI): The robots follow the global reference using a Model Predictive Path Integral (MPPI) controller.
  5. Adaptive Tracking: This is a key innovation. If a robot is on schedule, it uses temporal tracking (staying synced with the clock). If it gets significantly delayed, it automatically switches to spatial tracking (following the path regardless of time) to maintain progress without trying to "teleport" to a missed timestamp.
  6. Selective Replanning: The system monitors progress. If a robot falls too far behind or off-track, it triggers a targeted global replan for only that robot, rather than halting the entire fleet.

Datasets

The framework was evaluated across 1,200 simulation instances using four distinct map types:

  • Rooms: Adapted from the MovingAI benchmark, featuring interconnected rooms.
  • Warehouse: A scaled version of the Bench-MR environment.
  • Random: A workspace with randomly placed square obstacles.
  • Passages: A custom map with nine square obstacles forming four intersecting narrow corridors.

The authors also conducted hardware experiments using a fleet of 8 differential-drive robots in a lab setting equipped with OptiTrack for localization.

Key Insights and Ideas

  • Soft vs. Hard Constraints: The "aha moment" here is that global plans should be treated as guidance rather than law. By using soft penalties for space-time conflicts, the global planner organizes the flow of traffic without creating a brittle system that breaks upon the first minor delay.
  • Passage-Awareness: By explicitly identifying narrow passages and treating them as special nodes in a graph, the system can proactively manage the most likely points of failure (deadlocks) before the robots even reach them.
  • Dual-Mode Tracking: The switch between temporal and spatial tracking solves a common failure mode in hierarchical systems where a delayed robot tries to "catch up" by speeding dangerously or taking shortcuts that violate the intended coordination.

Key Results

  • Success Rate: The proposed method achieved a near-perfect success rate (98.7% to 100%) across all tested environments with up to 30 robots.
  • Efficiency: It consistently outperformed baselines like EECBS and HAGP in makespan (time for the last robot to arrive) and flowtime (total time for all robots). In the "rooms" environment with 30 robots, the best competing method had a makespan 1.3x higher than this framework.
  • Scalability: Global planning time scaled gracefully, taking only ~4.3 seconds for 32 robots in complex scenarios.
  • Hardware Validation: In 17 real-world trials with 8 robots, the system completed all tasks with zero collisions, even when faced with the coordination challenges of constrained doorways.

Limitations and Future Work

  • Fixed Priorities: The current global planner uses a fixed priority order for robots. In extremely dense scenarios, this might lead to suboptimal routes for lower-priority agents.
  • Two-Stage Planning: The separation of spatial route selection and temporal optimization is computationally efficient but might miss complex "detour" solutions that a simultaneous optimization could find.
  • Schedule Deviations: While adaptive tracking prevents crashes, it allows for substantial deviations from the original schedule. The authors note that investigating how to better bound these deviations while maintaining flexibility is a promising future direction.

Summary updated

Abstract

In multi-robot navigation, rigid global schedules are sensitive to execution deviations, while local methods lack long-horizon coordination. We propose a passage-focused framework combining soft global coordination with flexible local execution. A passage-induced graph of convex sets supports priority-ordered planning with two levels of soft coordination. Passage-aware route selection accounts for passage usage and traversal directions, while route-restricted continuous space-time planning penalizes temporal conflicts. The resulting references guide a model predictive path integral controller that avoids collisions online. Adaptive temporal and geometric tracking accommodates execution deviations, while selective replanning maintains coordination without rigid trajectory reservations. Across 1,200 instances in 4 different environments with 5-30 robots, the framework achieves a near-perfect success rate and outperforms evaluated baselines in makespan and flowtime. Hardware experiments with 8 robots demonstrate successful completion of all trials without collisions. These results highlight the effectiveness of passage-focused coordination in balancing long-horizon cooperation with flexible execution.
BibTeX
@misc{dong2026passage,
  author = {Haoze Dong and Stepan Dergachev and Meng Guo and Konstantin Yakovlev and Zhongkui Li},
  title = {{Passage-Focused Soft Coordination for Hierarchical Multi-Robot Navigation in Bottleneck Environments}},
  year = {2026},
  eprint = {2611.18877},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.18877},
}
Figure