Multi-agent path finding

Abstract

The Multi-Agent Path Finding (MAPF) problem is about finding the paths for multiple agents from a source vertex to a target vertex. The key is to design and implement a collision-free algorithm with consideration of different types of constraints. It has many real-life applications, especially in the robotics and path planning fields. A state-of-art optimal algorithm Conflict-Based Search (CBS) is studied and implemented. It has two levels, the high-level search makes use of a constraint tree to detect conflicts between agents and generates constraints for agents while the low-level search will find optimal paths for each agent. A more general form and an enhancement of CBS, Meta-Agent Conflict-Based Search (MA-CBS), is able to perform a merge action of agents based on merge policy. It is considered as a framework constructed over any complete and optimal MAPF low-level solver. However, the (MA-) CBS does not perform very well on large maps, to improve the search speed, Safe Interval Path Planning, a path planning algorithm that uses a concept of safe interval to ensure collision avoidance while optimizing the path for agents, is studied. This Final Year Project focuses on the study and implementation of CBS, MA-CBS, and SIPP algorithms. An innovative combination of the CBS and SIPP algorithm is also explored. Experiments are carried out for CBS, MA-CBS, and SIPP algorithms. The results show that the (MA-) CBS algorithm with A* as a low-level solver can produce an optimal solution. The combination of the CBS and SIPP algorithm can largely improve the success rate and reduce the calculation time by 100 times.