# Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 19 May 2025.

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

- [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)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning](https://mlsanity.com/paper/2310.01207/) (2023)
- [Improving Learnt Local MAPF Policies with Heuristic Search](https://mlsanity.com/paper/2403.20300/) (2024)
- [Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search](https://mlsanity.com/paper/2312.16767/) (2023)
- [Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2412.11678/) (2024)

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

- [Graph Attention-Guided Search for Dense Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.17382/) (2025)
- [Local Guidance for Configuration-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.19072/) (2025)
- [GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments](https://mlsanity.com/paper/2603.10858/) (2026)
- [Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF](https://mlsanity.com/paper/2608.06702/) (2026)

## Abstract (arXiv)

PIBT is a computationally lightweight algorithm that can be applied to a variety of multi-agent pathfinding (MAPF) problems, generating the next collision-free locations of agents given another. Because of its simplicity and scalability, it is becoming a popular underlying scheme for recent large-scale MAPF methods involving several hundreds or thousands of agents. Vanilla PIBT makes agents behave greedily towards their assigned goals, while agents typically have multiple best actions, since the graph shortest path is not always unique. Consequently, tiebreaking about how to choose between these actions significantly affects resulting solutions. This paper studies two simple yet effective techniques for tiebreaking in PIBT, without compromising its computational advantage. The first technique allows an agent to intelligently dodge another, taking into account whether each action will hinder the progress of the next timestep. The second technique is to learn, through multiple PIBT runs, how an action causes regret in others and to use this information to minimise regret collectively. Our empirical results demonstrate that these techniques can reduce the solution cost of one-shot MAPF and improve the throughput of lifelong MAPF. For instance, in densely populated one-shot cases, the combined use of these tiebreaks achieves improvements of around 10-20% in sum-of-costs, without significantly compromising the speed of a PIBT-based planner.