# Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution

arXiv: https://arxiv.org/abs/2401.00315 · HTML: https://mlsanity.com/paper/2401.00315/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 30 Dec 2023.

## Builds on (most cited first, 8 of 8)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [Multi-Agent Path Finding with Delay Probabilities](https://mlsanity.com/paper/1612.05309/) (2016)
- [A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph](https://mlsanity.com/paper/2010.05254/) (2020)
- [Offline Time-Independent Multi-Agent Path Planning](https://mlsanity.com/paper/2105.07132/) (2021)

## Built on by (most cited first, 6 of 6)

- [A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution](https://mlsanity.com/paper/2403.18145/) (2024)
- [Precomputing Multi-Agent Path Replanning Using Temporal Flexibility](https://mlsanity.com/paper/2601.04884/) (2026)
- [Lifelong Scalable Multi-Agent Realistic Testbed and A Comprehensive Study on Design Choices in Lifelong AGV Fleet Management Systems](https://mlsanity.com/paper/2602.15721/) (2026)
- [From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding](https://mlsanity.com/paper/2511.21886/) (2025)
- [Analyzing Planner Design Trade-offs for MAPF under ADG-based Realistic Execution](https://mlsanity.com/paper/2512.09736/) (2025)
- [CREST: Constraint-Release Execution for Multi-Robot Warehouse Shelf Rearrangement](https://mlsanity.com/paper/2603.28803/) (2026)

## Abstract (arXiv)

The Multi-Agent Path Finding (MAPF) problem involves planning collision-free paths for multiple agents in a shared environment. The majority of MAPF solvers rely on the assumption that an agent can arrive at a specific location at a specific timestep. However, real-world execution uncertainties can cause agents to deviate from this assumption, leading to collisions and deadlocks. Prior research solves this problem by having agents follow a Temporal Plan Graph (TPG), enforcing a consistent passing order at every location as defined in the MAPF plan. However, we show that TPGs are overly strict because, in some circumstances, satisfying the passing order requires agents to wait unnecessarily, leading to longer execution time. To overcome this issue, we introduce a new graphical representation called a Bidirectional Temporal Plan Graph (BTPG), which allows switching passing orders during execution to avoid unnecessary waiting time. We design two anytime algorithms for constructing a BTPG: BTPG-na"ive and BTPG-optimized. Experimental results show that following BTPGs consistently outperforms following TPGs, reducing unnecessary waits by 8-20%.