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

CREATORYifan Su, Rishi Veerapaneni, Jiaoyang Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-04849

Browse the full library · About the Tower of Babel