Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Bidirectional Temporal Plan Graphs (BTPG) that let agents switch passing orders at conflict locations during MAPF plan execution, with two anytime construction algorithms (BTPG-naïve and BTPG-optimized) that reduce unnecessary waiting by 8-20%.
Problem
MAPF plans assume agents reach locations at exact timesteps; under execution delays, TPG-based execution enforces fixed passing orders that cause unnecessary waiting and longer execution times.
Approach
Extends TPG with bidirectional pairs of type-2 edges so that, at execution, the first agent to arrive at a conflict location determines the passing order ("first-come-first-served"), and provides cycle-based validity conditions and DFS-based algorithms to add such pairs to a TPG built from a standard MAPF plan.
Key results
- BTPG-optimized achieves median improvement over TPG of 8.1-17.8% across six maps (mean 8.9-17.9%) in simulations with 3,900 instances.
- BTPG-optimized finds roughly 2x more bidirectional pairs than BTPG-naïve (e.g., 1,008 vs 663 on den520d).
- No negative improvements were observed across 3,900 simulations, with 31.2% of instances showing over 20% improvement.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow switching passing orders with BTPG execution instead of following a fixed TPG order | MAPF plan execution · MAPF simulations across six benchmark maps | unnecessary-wait reduction: 8-20% | Helped |
| Use BTPG-optimized instead of BTPG-naïve | BTPG construction · All six benchmark maps | execution-time improvement over TPG | Helped |
Surprising findings
- A hand-crafted adversarial example shows BTPG can produce longer execution time than TPG under specific delays, though none occurred in 3,900 simulations.
- Only about 10% of bidirectional pairs are actually used during execution, yet they drive the reported execution time reductions.
Limitations
- Adversarial cases exist where BTPG execution is slower than TPG.
- Only a small fraction (~10%) of bidirectional pairs are used, and singleton type-2 edges limit the candidate set.
- Evaluated only in simulation with a specific delay model (10% agents, 30% chance, 5 timesteps).
Experimental setup
Datasets: MAPF benchmark maps (den520d, warehouse, Paris, random, empty, Berlin)
Benchmarks: MAPF benchmark maps den520d, warehouse, Paris, random, empty, Berlin
Metrics: mean execution timesteps improvement over TPG relative to Ideal number of bidirectional pairs found BTPG runtime
Baselines: TPG execution policy BTPG-naïve
Builds on: Temporal Plan Graph MAPF with Delay Probability CBSH2-RTC
Closest papers by meaning
- Speedup Techniques for Switchable Temporal Plan Graph Optimization (AAAI 2025 · similarity 0.92)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.91)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.89)
- Windowed MAPF with Completeness Guarantees (AAAI 2025 · similarity 0.89)
- Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities (AAAI 2025 · similarity 0.88)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.