Complete and Locally Optimal Algorithms for Multi-Agent Path Finding on Graphs

In this thesis, we study and propose new algorithms for Multi-Agent Path Finding (MAPF) on undirected and directed graphs. On an assigned graph, the problem of Multi-Agent Pathfinding (MAPF) consists in finding paths for multiple agents, avoiding collisions. Finding the minimum-length solution is known to be NP-hard, and computation times grow exponentially with the number of agents. We present multiple approaches to address this problem. The first approach consists in decomposing the graph via spectral clustering, moving agents to their goal clusters first, which enables the efficient, parallel execution of rule-based algorithms within highly connected subgraphs. The second part of the thesis focuses on MAPF problems on strongly connected directed graphs, introducing a procedure that checks feasibility in linear time and an algorithm (diSC) that reaches suboptimal solutions in polynomial time. Finally, we propose a local search procedure that iteratively improves an initial feasible solution, combining dynamic programming with constrained neighborhoods to limit time complexity. The strategies introduced in this thesis focus on MAPF efficiency, feasibility, and solution quality, addressing practical needs for scalable and effective suboptimal solutions in industrial and densely populated scenarios.