# Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 37 references that are in the map.
- First posted on arXiv 16 Jan 2022.

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

- [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)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1901.11454/) (2019)
- [Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/1812.06355/) (2018)
- [MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees](https://mlsanity.com/paper/1401.3905/) (2014)
- [Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios](https://mlsanity.com/paper/1702.05515/) (2017)
- [MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding](https://mlsanity.com/paper/2103.09979/) (2021)
- [Time-Independent Planning for Multiple Moving Agents](https://mlsanity.com/paper/2005.13187/) (2020)
- [winPIBT: Extended Prioritized Algorithm for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1905.10149/) (2019)
- [Multi-objective Conflict-based Search Using Safe-interval Path Planning](https://mlsanity.com/paper/2108.00745/) (2021)

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

- [Constrained Environment Optimization for Prioritized Multi-Agent Navigation](https://mlsanity.com/paper/2305.11260/) (2023)
- [Co-Optimizing Reconfigurable Environments and Policies for Decentralized Multi-Agent Navigation](https://mlsanity.com/paper/2403.14583/) (2024)
- [Deadlock-Free Method for Multi-Agent Pickup and Delivery Problem Using Priority Inheritance with Temporary Priority](https://mlsanity.com/paper/2205.12504/) (2022)
- [Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF](https://mlsanity.com/paper/2608.06702/) (2026)

## Abstract (arXiv)

The multi-agent pickup and delivery (MAPD) problem, in which multiple agents iteratively carry materials without collisions, has received significant attention. However, many conventional MAPD algorithms assume a specifically designed grid-like environment, such as an automated warehouse. Therefore, they have many pickup and delivery locations where agents can stay for a lengthy period, as well as plentiful detours to avoid collisions owing to the freedom of movement in a grid. By contrast, because a maze-like environment such as a search-and-rescue or construction site has fewer pickup/delivery locations and their numbers may be unbalanced, many agents concentrate on such locations resulting in inefficient operations, often becoming stuck or deadlocked. Thus, to improve the transportation efficiency even in a maze-like restricted environment, we propose a deadlock avoidance method, called standby-based deadlock avoidance (SBDA). SBDA uses standby nodes determined in real-time using the articulation-point-finding algorithm, and the agent is guaranteed to stay there for a finite amount of time. We demonstrated that our proposed method outperforms a conventional approach. We also analyzed how the parameters used for selecting standby nodes affect the performance.