A Survey of Pathfinding in MAPF and NetworkAnalysis

The Hong Kong University of Science and Technology (Guangzhou)

Data Science and Analytics Thrust

PhD Qualifying Examination

By Mr. WU Ruizhong

Abstract

Pathfinding is a fundamental problem in computer science and graph theory, with wide ranging applications in robotics, navigation, transportation, and network analysis. In recent years, the rapid development of multi-agent systems and the growing interest in understanding complex networks have brought attention to pathfinding techniques. This survey provides a comprehensive overview of shortest path computation and pathfinding techniques in Multi-Agent Path Finding (MAPF) and network analysis. We first introduce classical search-based and index-based shortest path algorithms, and then present the solutions to MAPF. Additionally, we explore the role of pathfinding in network analysis, particularly in centrality measures such as betweenness centrality. Finally, we discuss future research directions.

PQE Committee

Chair of Committee: Prof. LUO Qiong

Prime Supervisor: Prof. LI Lei

Co-Supervisor: Prof. LU Shangqi

Examiner: Prof. WEN Zeyi