Solving Scalability and Reality Gaps in Multi-Agent Pathfinding

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Solving Scalability and Reality Gaps in Multi-Agent
Pathfinding"

By

Mr. Mingkai TANG


Abstract:

The classical Multi-Agent Pathfinding (MAPF) problem, which involves computing 
collision-free paths for multiple agents on a graph, serves as a fundamental 
framework for coordinated multi-robot motion. Due to its essential role in 
applications such as automated warehousing and logistics, MAPF has 
consistently drawn research interest from the fields of artificial 
intelligence, multi-agent systems, and robotics. However, its practical 
deployment is hindered by two major challenges: the reality gap caused by its 
oversimplified problem formulation, and the scalability issue in coordinating 
large numbers of agents in complex, long-horizon scenarios.

To bridge the reality gap and enhance the scalability of classical MAPF, this 
thesis investigates three key limitations that originate from its simplifying 
assumptions: (1) optimizing the order in which agents visit multiple goals, 
(2) enabling cyclic operations over an infinite horizon, and (3) accounting 
for energy constraints that affect agent viability over time.

First, to enable optimal multi-goal visitation, we introduce the Multi-Goal 
Conflict-Based Search (MGCBS) algorithm, whose efficiency is enhanced by a 
Time-Interval-Space Forest (TIS Forest) data structure. Second, to accommodate 
cyclic, infinite-horizon operations, we formalize the Streaming MAPF (S-MAPF) 
problem and propose the Agent Stream Conflict-Based Search (ASCBS) algorithm, 
which employs a disjoint-splitting technique to improve efficiency in small 
maps. Recognizing that S-MAPF assumes agents disappear upon reaching their 
destinations and operate with fixed initial start times, we further extend 
this formulation to the Multi-Agent-Stream Scheduling and Pathfinding 
(S2-MAPF) problem, which supports persistent agent presence and adaptive 
initial start times. For this enhanced model, we introduce two solution 
approaches: the Matching Planning (MP) algorithm, which decouples task 
scheduling from pathfinding to achieve computational efficiency, and the 
Coupled Planning (CP) algorithm, which integrates both subproblems to 
guarantee optimality.

Finally, to incorporate energy constraint, we define the Energy-Limited 
Lifelong Multi-Agent Pickup and Delivery (EL-MAPD) problem, establish 
theoretical solvability conditions, and introduce a practical online planner 
called Fallback Priority Planning (FPP), which guarantees a feasible action in 
every planning episode.

Together, these contributions establish algorithmic and theoretical 
foundations that meaningfully enhance the scalability and real-world 
applicability of multi-robot systems.


Date:                   Monday, 31 August 2026

Time:                   10:00am - 12:00noon

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               Dr. Yantao YU (CIVL)

Committee Members:      Dr. Ling PAN (Supervisor)
                        Dr. Long CHEN
                        Dr. Qifeng CHEN
                        Prof. Wei ZHANG (ECE)
                        Prof. Dongning LIU (Guangdong University of
                        Technology)