# Symmetry Breaking for k-Robust Multi-Agent Path Finding

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 12 references that are in the map.
- First posted on arXiv 17 Feb 2021.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Multi-Agent Path Finding with Delay Probabilities](https://mlsanity.com/paper/1612.05309/) (2016)

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

- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution](https://mlsanity.com/paper/2403.18145/) (2024)
- [Robust Multi-Agent Pickup and Delivery with Delays](https://mlsanity.com/paper/2303.17422/) (2023)
- [Search-Aided Joint Agent-Environment Reinforcement Learning for Robust Lifelong Multi-Agent Path Finding with Rotations](https://mlsanity.com/paper/2608.05588/) (2026)

## Abstract (arXiv)

During Multi-Agent Path Finding (MAPF) problems, agents can be delayed by unexpected events. To address such situations recent work describes k-Robust Conflict-BasedSearch (k-CBS): an algorithm that produces coordinated and collision-free plan that is robust for up to k delays. In this work we introducing a variety of pairwise symmetry breaking constraints, specific to k-robust planning, that can efficiently find compatible and optimal paths for pairs of conflicting agents. We give a thorough description of the new constraints and report large improvements to success rate ina range of domains including: (i) classic MAPF benchmarks;(ii) automated warehouse domains and; (iii) on maps from the 2019 Flatland Challenge, a recently introduced railway domain where k-robust planning can be fruitfully applied to schedule trains.