Multi-agent path finding (part A)

• Main Author: Ong, Wei Hua
• Other Authors: Tang Xueyan
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: https://hdl.handle.net/10356/138430
• Institution: Nanyang Technological University

Multi-Agent Path Finding algorithm has become a topic that has been actively researched in the field of Artificial Intelligence. As the technology advances each year, many of our process has been automated and are being carried out by robot agents to complete the tasks. Single-agent path finding algorithms such as A* focus on a single agent environment where it is unable to be used in a multiple agent environment to provide a solution to solve the multi-agent path finding problem. In this FYP, we use an algorithm, Conflict-Based Search algorithm (CBS), a multi-agent path finding algorithm that uses A* search for low-level searching and heuristic constraints in the high-level searching to solve multi-agent path finding problems. The aim is to find an optimal path for multi-agent path finding problem in grid maps of different dimensions. We employed CBS algorithm to search for multi-agent path finding solution. This algorithm is used to get the time taken for the generation of the optimal path in different scenarios of the grid maps. Our experiments show that the algorithm performs better with fewer agents given an adequate number of obstacles in the map. With a bigger dimension of the map, the algorithm can have a bigger pool of possibility in planning an optimal path for the agents in the map.