Multi-agent path finding

• Main Author: Feng, Qingyu
• Other Authors: Tang Xueyan
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/165898
• Institution: Nanyang Technological University

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.