# Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery

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

## Key facts

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

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

- [Scalable Multi-Agent Reinforcement Learning for Warehouse Logistics with Robotic and Human Co-Workers](https://mlsanity.com/paper/2212.11498/) (2022)
- [Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning](https://mlsanity.com/paper/2310.01207/) (2023)
- [POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding](https://mlsanity.com/paper/2407.14931/) (2024)
- [Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems](https://mlsanity.com/paper/2109.12343/) (2021)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning](https://mlsanity.com/paper/2506.23793/) (2025)
- [A Conflict-Based Search Framework for Multi-Objective Multi-Agent Path Finding](https://mlsanity.com/paper/2101.03805/) (2021)
- [Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks](https://mlsanity.com/paper/2201.06014/) (2022)
- [Safe Interval Path Planning With Kinodynamic Constraints](https://mlsanity.com/paper/2302.00776/) (2023)
- [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)
- [A Competitive Analysis of Online Multi-Agent Path Finding](https://mlsanity.com/paper/2106.11454/) (2021)
- [Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints](https://mlsanity.com/paper/2108.05145/) (2021)
- [Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding](https://mlsanity.com/paper/2404.16379/) (2024)
- [Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses](https://mlsanity.com/paper/2408.14527/) (2024)
- [An Extension of BIM Using AI: a Multi Working-Machines Pathfinding Solution](https://mlsanity.com/paper/2105.06635/) (2021)
- [Multi-objective Conflict-based Search Using Safe-interval Path Planning](https://mlsanity.com/paper/2108.00745/) (2021)
- [Deadlock-Free Method for Multi-Agent Pickup and Delivery Problem Using Priority Inheritance with Temporary Priority](https://mlsanity.com/paper/2205.12504/) (2022)
- [Robust Multi-Agent Pickup and Delivery with Delays](https://mlsanity.com/paper/2303.17422/) (2023)
- [Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2605.07637/) (2026)
- [Terraforming -- Environment Manipulation during Disruptions for Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2305.11510/) (2023)
- [Neural ATTF: A Scalable Solution to Lifelong Multi-Agent Path Planning](https://mlsanity.com/paper/2504.15130/) (2025)
- [Interleaving Scheduling and Motion Planning with Incremental Learning of Symbolic Space-Time Motion Abstractions](https://mlsanity.com/paper/2603.10651/) (2026)
- [Lifelong Multi-Subsystem Pickup and Delivery with Buffer-Limited Handover Stations](https://mlsanity.com/paper/2607.17724/) (2026)
- [Model-Based Reinforcement Learning for Heterogeneous Multi-Robot Task Assignment Under Distribution Shifts](https://mlsanity.com/paper/2608.21554/) (2026)
- [Dynamic Conflict Clustering with Lightweight Learning and Strategic Repair for Distributed Constraint Satisfaction](https://mlsanity.com/paper/2610.15658/) (2026)

## Abstract (arXiv)

The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for well-formed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities.