# Multi-Goal Multi-Agent Pickup and Delivery

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 17 references that are in the map.
- First posted on arXiv 2 Aug 2022.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [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)
- [Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2110.14891/) (2021)
- [Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering](https://mlsanity.com/paper/2009.05161/) (2020)

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

- [Scalable Multi-Agent Reinforcement Learning for Warehouse Logistics with Robotic and Human Co-Workers](https://mlsanity.com/paper/2212.11498/) (2022)
- [AI4OPT: AI Institute for Advances in Optimization](https://mlsanity.com/paper/2307.02671/) (2023)
- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [Decomposition-based Hierarchical Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications](https://mlsanity.com/paper/2308.10393/) (2023)
- [MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem](https://mlsanity.com/paper/2404.19518/) (2024)
- [Graph Attention Multi-Agent Fleet Autonomy for Advanced Air Mobility](https://mlsanity.com/paper/2302.07337/) (2023)
- [DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding](https://mlsanity.com/paper/2312.06314/) (2023)
- [Optimal Integrated Task and Path Planning and Its Application to Multi-Robot Pickup and Delivery](https://mlsanity.com/paper/2403.01277/) (2024)
- [Neural ATTF: A Scalable Solution to Lifelong Multi-Agent Path Planning](https://mlsanity.com/paper/2504.15130/) (2025)
- [An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms](https://mlsanity.com/paper/2511.18604/) (2025)
- [GRAND: Guidance, Rebalancing, and Assignment for Networked Dispatch in Multi-Agent Path Finding](https://mlsanity.com/paper/2512.03194/) (2025)
- [Wireless communication empowers online scheduling of partially-observable transportation multi-robot systems in a smart factory](https://mlsanity.com/paper/2603.23967/) (2026)

## Abstract (arXiv)

In this work, we consider the Multi-Agent Pickup-and-Delivery (MAPD) problem, where agents constantly engage with new tasks and need to plan collision-free paths to execute them. To execute a task, an agent needs to visit a pair of goal locations, consisting of a pickup location and a delivery location. We propose two variants of an algorithm that assigns a sequence of tasks to each agent using the anytime algorithm Large Neighborhood Search (LNS) and plans paths using the Multi-Agent Path Finding (MAPF) algorithm Priority-Based Search (PBS). LNS-PBS is complete for well-formed MAPD instances, a realistic subclass of MAPD instances, and empirically more effective than the existing complete MAPD algorithm CENTRAL. LNS-wPBS provides no completeness guarantee but is empirically more efficient and stable than LNS-PBS. It scales to thousands of agents and thousands of tasks in a large warehouse and is empirically more effective than the existing scalable MAPD algorithm HBH+MLA*. LNS-PBS and LNS-wPBS also apply to a more general variant of MAPD, namely the Multi-Goal MAPD (MG-MAPD) problem, where tasks can have different numbers of goal locations.