BTPG-max: Achieving Local Maximal Bidirectional Pairs for Bidirectional Temporal Plan Graphs

(Oral)

Yifan Su, Rishi Veerapaneni, Jiaoyang Li.

AAAI Conference on Artificial Intelligence (AAAI), pages 29687-29695, 2026.

Publisher arXiv Talk

Multi-Agent Path Finding (MAPF) requires computing collision-free paths for multiple agents in a shared environment. Most MAPF planners assume that each agent reaches a specific location at a specific timestep, but this is infeasible to directly follow on real systems where delays often occur. To address collisions caused by agents deviating due to delays, the Temporal Plan Graph (TPG) was proposed, which converts a MAPF time-dependent solution into a timeindependent solution with a set of inter-agent dependencies. Recently, a Bidirectional TPG (BTPG) was proposed which relaxed some dependencies into “bidirectional pairs” and improved efficiency of agents executing their MAPF solution with delays. Our work improves upon this prior work by designing an algorithm, BPTG-max, that finds more bidirectional pairs. Our main theoretical contribution is in designing the BTPG-max algorithm that is locally maximal, i.e., it constructs a BTPG where no additional bidirectional pairs can be added. We also show how, in practice, BTPG-max leads to BTPGs with significantly more bidirectional edges, superior anytime behavior, and improved robustness to delays.

@inproceedings{ SuAAAI26,
  author    = "Yifan Su and Rishi Veerapaneni and Jiaoyang Li",
  title     = "BTPG-max: Achieving Local Maximal Bidirectional Pairs for Bidirectional Temporal Plan Graphs",
  booktitle = "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)",
  pages     = "29687-29695",
  year      = "2026",
  doi       = "10.1609/aaai.v40i35.40213",
}

Abstract:

Multi-Agent Path Finding (MAPF) requires computing collision-free paths for multiple agents in a shared environment. Most MAPF planners assume that each agent reaches a specific location at a specific timestep, but this is infeasible to directly follow on real systems where delays often occur. To address collisions caused by agents deviating due to delays, the Temporal Plan Graph (TPG) was proposed, which converts a MAPF time-dependent solution into a timeindependent solution with a set of inter-agent dependencies. Recently, a Bidirectional TPG (BTPG) was proposed which relaxed some dependencies into “bidirectional pairs” and improved efficiency of agents executing their MAPF solution with delays. Our work improves upon this prior work by designing an algorithm, BPTG-max, that finds more bidirectional pairs. Our main theoretical contribution is in designing the BTPG-max algorithm that is locally maximal, i.e., it constructs a BTPG where no additional bidirectional pairs can be added. We also show how, in practice, BTPG-max leads to BTPGs with significantly more bidirectional edges, superior anytime behavior, and improved robustness to delays.