Multi-agent path finding

Abstract

In the multi-agent path finding (MAPF) problem, we are given a set of agents, each with a start and goal position. The task is to find paths for all agents while avoiding any collision. In the k-Robust multi-agent path finding (kR-MAPF) problem, possible delays of agents are also taken into consideration. Conflict-Based Search (CBS) is one of the state-of-the-art optimal MAPF algorithms. It has two levels. The high level divides a MAPF problem into multiple single-agent path finding (SAPF) problems. The low level solves those SAPF problems. k-Robust Conflict-Based Search (kR-CBS) is a variant of CBS specific to kR-MAPF problems. It has an improved version called Improved k-Robust Conflict-Based Search (IkR-CBS). The focus of this Final Year Project is on the study, implementation as well as improvement of CBS and IkR-CBS. In Chapter 1, an introduction to all the problems and algorithms concerned in this project is provided and the project scope is defined. In Chapter 2, my implementation of CBS and IkR-CBS is presented and explained. In Chapter 3, two innovative methods, MA-IkR-CBS & Floating Range Constraints, are introduced to improve the algorithm performance. Experiments are conducted to show that these two methods improve the performance by up to 20% & 7% respectively.