# Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 70 references that are in the map.
- First posted on arXiv 12 Mar 2021.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Intractability of Optimal Multi-Robot Path Planning on Planar Graphs](https://mlsanity.com/paper/1504.02072/) (2015)
- [Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics](https://mlsanity.com/paper/1507.03290/) (2015)
- [A Commentary on "Breaking Row and Column Symmetries in Matrix Models"](https://mlsanity.com/paper/1910.01423/) (2019)
- [On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs](https://mlsanity.com/paper/1911.04871/) (2019)
- [Symmetry Breaking for k-Robust Multi-Agent Path Finding](https://mlsanity.com/paper/2102.08689/) (2021)
- [Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent](https://mlsanity.com/paper/2003.12924/) (2020)

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

- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2308.11234/) (2023)
- [Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large Scale Imitation Learning for MAPF](https://mlsanity.com/paper/2409.14491/) (2024)
- [Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance](https://mlsanity.com/paper/2105.10993/) (2021)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Learning Team-Based Navigation: A Review of Deep Reinforcement Learning Techniques for Multi-Agent Pathfinding](https://mlsanity.com/paper/2308.05893/) (2023)
- [rm E(3)-Equivariant Actor-Critic Methods for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2308.11842/) (2023)
- [Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution](https://mlsanity.com/paper/2401.00315/) (2023)
- [Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses](https://mlsanity.com/paper/2304.14309/) (2023)
- [Intelligent logistics management robot path planning algorithm integrating transformer and GCN network](https://mlsanity.com/paper/2501.02749/) (2025)
- [Effective Integration of Weighted Cost-to-go and Conflict Heuristic within Suboptimal CBS](https://mlsanity.com/paper/2205.11624/) (2022)
- [Tracking Progress in Multi-Agent Path Finding](https://mlsanity.com/paper/2305.08446/) (2023)
- [Engineering LaCAM^ast: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2308.04292/) (2023)
- [Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search](https://mlsanity.com/paper/2312.16106/) (2023)
- [Windowed MAPF with Completeness Guarantees](https://mlsanity.com/paper/2410.01798/) (2024)
- [Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding](https://mlsanity.com/paper/2406.10827/) (2024)
- [Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds](https://mlsanity.com/paper/2503.03779/) (2025)
- [Analyzing Planner Design Trade-offs for MAPF under ADG-based Realistic Execution](https://mlsanity.com/paper/2512.09736/) (2025)
- [GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments](https://mlsanity.com/paper/2603.10858/) (2026)
- [CREST: Constraint-Release Execution for Multi-Robot Warehouse Shelf Rearrangement](https://mlsanity.com/paper/2603.28803/) (2026)

## Abstract (arXiv)

Multi-Agent Path Finding (MAPF) is a challenging combinatorial problem that asks us to plan collision-free paths for a team of cooperative agents. In this work, we show that one of the reasons why MAPF is so hard to solve is due to a phenomenon called pairwise symmetry, which occurs when two agents have many different paths to their target locations, all of which appear promising, but every combination of them results in a collision. We identify several classes of pairwise symmetries and show that each one arises commonly in practice and can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes for current state-of-the-art (bounded-sub)optimal MAPF algorithms. We propose a variety of reasoning techniques that detect the symmetries efficiently as they arise and resolve them by using specialized constraints to eliminate all permutations of pairwise colliding paths in a single branching step. We implement these ideas in the context of the leading optimal MAPF algorithm CBS and show that the addition of the symmetry reasoning techniques can have a dramatic positive effect on its performance - we report a reduction in the number of node expansions by up to four orders of magnitude and an increase in scalability by up to thirty times. These gains allow us to solve to optimality a variety of challenging MAPF instances previously considered out of reach for CBS.