Passage-Focused Soft Coordination for Hierarchical Multi-Robot Navigation in Bottleneck Environments
Organizations: School of Advanced Manufacturing and Robotics, Peking University, Beijing, China. · National Research University Higher School of Economics, Moscow, Russia. · Saint-Petersburg University, Saint Petersburg, Russia.
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.
Figures & tables
| rooms | warehouse | random | passages | |
|---|---|---|---|---|
| ORCA-DD | 20% | 10.3% | 25.7% | 11% |
| EECBS ( ) | 100% | 82.3% | 100% | 100% |
| EECBS ( ) | 100% | 49.3% | 96.7% | 100% |
| db-LaCAM | 65.3% | 78.3% | 84.7% | 60.3% |
| HAGP (w/ repl.) | 97.3% | 99.3% | 100% | 99.3% |
| HAGP (w/o repl.) | 97.7% | 100% | 100% | 100% |
| Variant | GP (s) | MS (s) | FT (s) | ||
| NoCo | 12.9 (5.1) | 44.4 (19.8) | 878.9 (258.2) | 534.4 (117.5) | 748.5 (335.4) |
| RegOnly | 4.6 (0.8) | 41.8 (28.0) | 801.2 (372.3) | 442.3 (381.2) | 631.7 (469.6) |
| STOnly | 9.1 (1.9) | 37.5 (11.6) | 829.3 (176.7) | 301.2 (126.5) | 616.0 (219.4) |
| FullG | 51.8 (5.7) | 39.9 (18.0) | 763.3 (262.7) | 408.1 (218.3) | 506.6 (597.0) |
| Ours | 4.3 (0.6) | 35.4 (17.3) | 732.2 (243.3) | 362.8 (154.4) | 480.8 (499.5) |
| Robots | GP (s) | Exact Calls | MS (s) | FT/Robot (s) |
|---|---|---|---|---|
| 8 | 0.9 (0.1) | 170.0 (21.0) | 17.7 (3.6) | 13.8 (1.9) |
| 16 | 2.0 (0.2) | 384.0 (49.2) | 21.9 (7.5) | 15.4 (3.5) |
| 24 | 3.2 (0.4) | 612.0 (73.2) | 26.8 (5.6) | 18.6 (2.8) |
| 32 | 4.3 (0.6) | 827.0 (113.8) | 35.4 (17.3) | 22.9 (7.6) |
| Method | MS (s) | FT (s) | (ms) | |
|---|---|---|---|---|
| Fixed | 35.4 (17.3) | 732.2 (243.3) | 480.8 (499.5) | – |
| Periodic | 37.9 (14.0) | 756.0 (189.7) | 506.2 (299.0) | 2217.3 (485.5) |
| Selective | 36.2 (9.5) | 741.0 (144.8) | 451.4 (215.7) | 156.8 (28.1) |
| Scenario | Succ. | MS (s) | Len (m) | R | GP (s) | (ms) | (ms) |
|---|---|---|---|---|---|---|---|
| Random | 5/5 | 16.83 | 26.63 | 13.4 | 0.49 | 90.23 | 68.09 |
| Rand-Swap | 2/2 | 21.01 | 52.04 | 7.5 | 0.97 | 258.53 | 69.89 |
| Room | 10/10 | 23.86 | 28.56 | 27.3 | 0.40 | 79.05 | 65.11 |
| Overall | 17/17 | 21.46 | 30.75 | 20.9 | 0.49 | 88.75 | 66.45 |
Multi-Robot Motion Planning
Multi-Robot Motion Planning coordinates collision-free paths and trajectories for robot teams sharing space, tasks, and changing environments.
See all 157 papers