# Fault-Tolerant Offline Multi-Agent Path Planning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 25 Nov 2022.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots](https://mlsanity.com/paper/1409.2399/) (2014)
- [Iterative Refinement for Real-Time Multi-Robot Path Planning](https://mlsanity.com/paper/2102.12331/) (2021)
- [Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems](https://mlsanity.com/paper/2109.12343/) (2021)
- [Resilient Active Target Tracking with Multiple Robots](https://mlsanity.com/paper/1809.04032/) (2018)
- [Robust Multiple-Path Orienteering Problem: Securing Against Adversarial Attacks](https://mlsanity.com/paper/2003.13896/) (2020)
- [Offline Time-Independent Multi-Agent Path Planning](https://mlsanity.com/paper/2105.07132/) (2021)
- [Robust Multi-Agent Task Assignment in Failure-Prone and Adversarial Environments](https://mlsanity.com/paper/2007.00100/) (2020)
- [Active Modular Environment for Robot Navigation](https://mlsanity.com/paper/2102.12748/) (2021)

## Abstract (arXiv)

We study a novel graph path planning problem for multiple agents that may crash at runtime, and block part of the workspace. In our setting, agents can detect neighboring crashed agents, and change followed paths at runtime. The objective is then to prepare a set of paths and switching rules for each agent, ensuring that all correct agents reach their destinations without collisions or deadlocks, despite unforeseen crashes of other agents. Such planning is attractive to build reliable multi-robot systems. We present problem formalization, theoretical analysis such as computational complexities, and how to solve this offline planning problem.