# Searching with Consistent Prioritization for Multi-Agent Path Finding

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

## Key facts

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

## Built on by (most cited first, 30 of 81)

- [Learning Safe Multi-Agent Control with Decentralized Neural Barrier Certificates](https://mlsanity.com/paper/2101.05436/) (2021)
- [Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning](https://mlsanity.com/paper/2310.01207/) (2023)
- [Multi-Agent Path Finding with Prioritized Communication Learning](https://mlsanity.com/paper/2202.03634/) (2022)
- [Multi-Robot Coordination and Layout Design for Automated Warehousing](https://mlsanity.com/paper/2305.06436/) (2023)
- [MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale](https://mlsanity.com/paper/2409.00134/) (2024)
- [Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2308.11234/) (2023)
- [Multi-Agent Coordination via Multi-Level Communication](https://mlsanity.com/paper/2209.12713/) (2022)
- [Guidance Graph Optimization for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2402.01446/) (2024)
- [Multi-Goal Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2208.01223/) (2022)
- [Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding](https://mlsanity.com/paper/2312.15908/) (2023)
- [Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities](https://mlsanity.com/paper/2404.16162/) (2024)
- [Subdimensional Expansion for Multi-objective Multi-agent Path Finding](https://mlsanity.com/paper/2102.01353/) (2021)
- [Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance](https://mlsanity.com/paper/2105.10993/) (2021)
- [Learning Control Admissibility Models with Graph Neural Networks for Multi-Agent Navigation](https://mlsanity.com/paper/2210.09378/) (2022)
- [Multi-Agent Motion Planning For Differential Drive Robots Through Stationary State Search](https://mlsanity.com/paper/2412.13359/) (2024)
- [Cooperative Task and Motion Planning for Multi-Arm Assembly Systems](https://mlsanity.com/paper/2203.02475/) (2022)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments](https://mlsanity.com/paper/2209.02865/) (2022)
- [Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding](https://mlsanity.com/paper/2403.07559/) (2024)
- [SOCIALMAPF: Optimal and Efficient Multi-Agent Path Finding with Strategic Agents for Social Navigation](https://mlsanity.com/paper/2210.08390/) (2022)
- [SACHA: Soft Actor-Critic with Heuristic-Based Attention for Partially Observable Multi-Agent Path Finding](https://mlsanity.com/paper/2307.02691/) (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)
- [RAILGUN: A Unified Convolutional Policy for Multi-Agent Path Finding Across Different Environments and Tasks](https://mlsanity.com/paper/2503.02992/) (2025)
- [Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2103.04516/) (2021)
- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [Advancing MAPF Toward the Real World: A Scalable Multi-Agent Realistic Testbed (SMART)](https://mlsanity.com/paper/2503.04798/) (2025)
- [Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning](https://mlsanity.com/paper/2506.23793/) (2025)
- [DeepFleet: Multi-Agent Foundation Models for Mobile Robots](https://mlsanity.com/paper/2508.08574/) (2025)
- [Leveraging Experience in Lifelong Multi-Agent Pathfinding](https://mlsanity.com/paper/2202.04382/) (2022)
- [The Multi-Agent Pickup and Delivery Problem: MAPF, MARL and Its Warehouse Applications](https://mlsanity.com/paper/2203.07092/) (2022)

## Abstract (arXiv)

We study prioritized planning for Multi-Agent Path Finding (MAPF). Existing prioritized MAPF algorithms depend on rule-of-thumb heuristics and random assignment to determine a fixed total priority ordering of all agents a priori. We instead explore the space of all possible partial priority orderings as part of a novel systematic and conflict-driven combinatorial search framework. In a variety of empirical comparisons, we demonstrate state-of-the-art solution qualities and success rates, often with similar runtimes to existing algorithms. We also develop new theoretical results that explore the limitations of prioritized planning, in terms of completeness and optimality, for the first time.