Prioritised Planning for Continuous-time Lifelong Multi-agent Pathfinding

Alvin Combrink, Sabino Franceso Roselli, and Martin Fabian.

This is the official respository for Prioritised Planning for Continuous-time Lifelong Multi-agent Pathfinding, which describes a fast, sub-optimal planning algorithm CPLP for collision-free movements of volumetric agents for the continuous-time lifelong multi-agent pathfinding problem. The pre-print version is available at , presented at CoDIT25.

Abstract

Multi-agent Path Finding (MAPF) is the problem of planning collision-free movements of agents such that they get from where they are to where they need to be. Commonly, agents are located on a graph and can traverse edges. This problem has many variations and has been studied for decades. Two such variations are the continuous-time and the lifelong MAPF problems. In the continuous-time MAPF problem, edges can have non-unit lengths and agents can traverse them at any real-valued time. Additionally, agent volumes are often considered. In the lifelong MAPF problem, agents must attend to a continuous stream of incoming tasks. Much work has been devoted to designing solution methods within these two areas. However, to our knowledge, the combined problem of continuous-time lifelong MAPF has yet to be addressed.

This work addresses continuous-time lifelong MAPF with agent volumes by presenting the fast and sub-optimal Continuous-time Prioritized Lifelong Planner (CPLP). CPLP continuously re-prioritizes tasks, assigns agents to them, and computes agent plans using a combination of two path planners; one based on CCBS and the other on SIPP. Experimental results with up to 700 agents on graphs with over 10 000 vertices demonstrate average computation times below 80 ms per call, well below a planning horizon of 1 second. In online settings where available time to compute plans is limited, CPLP ensures collision-free movement even when failing to meet these time limits. Therefore, the robustness of CPLP highlights its potential for real-world applications.

Repository Structure

├── src/                           # Source code for the project
│   ├── Benchmark_Sets/            # Benchmark sets, containing sets of problem instances
│   ├── Benchmark_Results/         # Benchmark results, follows the same file structure as Benchmark_Sets
│   ├── ...
├── animations/                    # Contains animation files
├── InfeasibleGraphExample/        # Contains instances found to be infeasible.
├── README.md                      # Project documentation (this file)
├── requirements.txt               # Required Python libraries and dependencies
└── LICENSE                        # License information

Getting Started

Prerequisites

1. Python (version 3.13 or higher)
2. Install required dependencies using:

pip install -r requirements.txt

3. See main.py for examples on how to run the code.

License

This project is licensed under the MIT License. See LICENSE for details.