Solving Scalability and Reality Gaps in Multi-Agent Pathfinding

PhD Thesis Proposal Defence


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

by

Mr. Mingkai TANG


Abstract:

The classical Multi-Agent Pathfinding (MAPF) problem, which focuses on 
computing collision-free paths for multiple agents on a graph, serves as a 
foundational model for coordinated multi-robot motion. Driven by its critical 
role in applications such as automated warehousing and logistics, MAPF has 
attracted sustained research interest across artificial intelligence, 
multi-agent systems, and robotics. However, its direct applicability is 
limited by two prominent challenges: the reality gap stemming from its 
oversimplified formulation, and the scalability issue in coordinating large 
numbers of agents in complex, long-term scenarios.

This proposal aims to bridge the reality gap and enhance the scalability of 
classical MAPF by addressing three key limitations arising from its 
simplifying assumptions: (1) optimizing visiting order among multiple goals, 
(2) enabling cyclic operations in structured environments, and (3) 
incorporating agent energy constraints. First, to allow agents to visit 
multiple goals optimally, we introduce the Multi-Goal Conflict-Based Search 
(MGCBS) algorithm. This approach achieves improved efficiency using a 
Time-Interval-Space Forest (TIS Forest) structure. Second, to extend one-shot 
planning to cyclic operation, we formalize Streaming MAPF (S-MAPF) and 
develop the Agent Stream Conflict-Based Search (ASCBS) algorithm to handle 
cyclic agent actions with unlimited working hours. Third, to incorporate 
energy constraint, we define the Energy-Limited Lifelong Multi-Agent Pickup 
and Delivery (EL-MAPD) problem. We provide theoretical guarantees for 
solvability and a practical online planner called Fallback Priority Planning 
(FPP), which ensures the acquisition of a feasible action in every planning 
episode.

In summary, these contributions provide an algorithmic and theoretical 
foundation that significantly enhances the scalability and practicality of 
multi-robot systems.


Date:                   Thursday, 5 February 2026

Time:                   3:00pm - 5:00pm

Venue:                  Room 3494
                        Lifts 25/26

Committee Members:      Dr. Ling Pan (Supervisor)
                        Prof. Fangzhen Lin (Chairperson)
                        Dr. Qifeng Chen