# Multi-Agent Path Finding with Delay Probabilities

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2016.

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

- [Answer Set Planning: A Survey](https://mlsanity.com/paper/2202.05793/) (2022)
- [Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World](https://mlsanity.com/paper/2103.16511/) (2021)
- [Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities](https://mlsanity.com/paper/2404.16162/) (2024)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution](https://mlsanity.com/paper/2401.00315/) (2023)
- [Symmetry Breaking for k-Robust Multi-Agent Path Finding](https://mlsanity.com/paper/2102.08689/) (2021)
- [Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2103.04516/) (2021)
- [Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses](https://mlsanity.com/paper/2304.14309/) (2023)
- [A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution](https://mlsanity.com/paper/2403.18145/) (2024)
- [Multi-Agent Path Finding via Tree LSTM](https://mlsanity.com/paper/2210.12933/) (2022)
- [Robust Multi-Agent Pickup and Delivery with Delays](https://mlsanity.com/paper/2303.17422/) (2023)
- [Formal Modelling for Multi-Robot Systems Under Uncertainty](https://mlsanity.com/paper/2305.17018/) (2023)
- [Multi-Robot Reliable Navigation in Uncertain Topological Environments with Graph Attention Networks](https://mlsanity.com/paper/2411.16134/) (2024)
- [When Agents Break Down in Multiagent Path Finding](https://mlsanity.com/paper/2508.03777/) (2025)
- [CREST: Constraint-Release Execution for Multi-Robot Warehouse Shelf Rearrangement](https://mlsanity.com/paper/2603.28803/) (2026)
- [Towards Autonomous Railway Operations: A Semi-Hierarchical Deep Reinforcement Learning Approach to the Vehicle Rescheduling Problem](https://mlsanity.com/paper/2605.10257/) (2026)
- [Generative Multi-Robot Motion Planning via Diffusion Modeling with Multi-Agent Reinforcement Learning Guidance](https://mlsanity.com/paper/2606.00933/) (2026)
- [Divide and Collapse: MAPF-Collapse via Exact Decomposition into Independent Sub-Instances](https://mlsanity.com/paper/2609.39559/) (2026)

## Abstract (arXiv)

Several recently developed Multi-Agent Path Finding (MAPF) solvers scale to large MAPF instances by searching for MAPF plans on 2 levels: The high-level search resolves collisions between agents, and the low-level search plans paths for single agents under the constraints imposed by the high-level search. We make the following contributions to solve the MAPF problem with imperfect plan execution with small average makespans: First, we formalize the MAPF Problem with Delay Probabilities (MAPF-DP), define valid MAPF-DP plans and propose the use of robust plan-execution policies for valid MAPF-DP plans to control how each agent proceeds along its path. Second, we discuss 2 classes of decentralized robust plan-execution policies (called Fully Synchronized Policies and Minimal Communication Policies) that prevent collisions during plan execution for valid MAPF-DP plans. Third, we present a 2-level MAPF-DP solver (called Approximate Minimization in Expectation) that generates valid MAPF-DP plans.