BTPG-max: Achieving Local Maximal Bidirectional Pairs for Bidirectional Temporal Plan Graphs
Yifan Su, Rishi Veerapaneni, Jiaoyang Li · 2025
Read BTPG-max: Achieving Local Maximal Bidirectional Pairs for Bidirectional Temporal Plan Graphs by Yifan Su, Rishi Veerapaneni, Jiaoyang Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-04849.txt.
Description
Yifan Su, Rishi Veerapaneni, and Jiaoyang Li loosened the execution constraints on warehouse robot fleets in a 2025 paper. Multi-agent path finding plans hit-free routes for many robots, but real robots run late, and a plan tied to exact timesteps breaks under delay. Time-based plan graphs fix this by replacing clock times with ordering dependencies between agents. Bidirectional versions relax some dependencies into pairs that can be traversed in either order, letting delayed robots recover gracefully.
The authors' method, BTPG-max, finds more of those flexible pairs than prior methods and is provably locally maximal: no further pair can be added to its output. In practice the extra bidirectional edges improve anytime actions and robustness to delays, making fleets less brittle when reality intrudes on the plan.
Catalog record
| CREATOR | Yifan Su, Rishi Veerapaneni, Jiaoyang Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-04849