# winPIBT: Extended Prioritized Algorithm for Iterative Multi-agent Path Finding

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2019.

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

- [Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks](https://mlsanity.com/paper/2201.06014/) (2022)
- [Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.19219/) (2025)
- [Planning over MAPF Agent Dependencies via Multi-Dependency PIBT](https://mlsanity.com/paper/2603.23405/) (2026)
- [A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning](https://mlsanity.com/paper/2608.17928/) (2026)

## Abstract (arXiv)

The problem of Multi-agent Path Finding (MAPF) consists in providing agents with efficient paths while preventing collisions. Numerous solvers have been developed so far since MAPF is critical for practical applications such as automated warehouses. The recently-proposed Priority Inheritance with Backtracking (PIBT) is a promising decoupled method that solves MAPF iteratively with flexible priorities. The method is aimed to be decentralized and has a very low computational cost, but it is shortsighted in the sense that it plans only one step ahead, thus occasionally resulting in inefficient plannings. This work proposes a generalization of PIBT, called windowed PIBT (winPIBT), that introduces a configurable time window. winPIBT allows agents to plan paths anticipating multiple steps ahead. We prove that, similarly to PIBT, all agents reach their own destinations in finite time as long as the environment is a graph with adequate properties, e.g., biconnected. Experimental results over various scenarios confirm that winPIBT mitigates livelock situations occurring in PIBT, and usually plans more efficient paths given adequate window size.