Multi-agent path finding

• Main Author: Wang, Xiaoyu
• Other Authors: Tang Xueyan
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence; Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling
• Online Access: https://hdl.handle.net/10356/148107
• Institution: Nanyang Technological University

The Multi-Agent Path Finding (MAPF) problem aims to find a set of paths for a set of agents to move from their respective initial positions to goal positions without collision. This problem has a number of real-life applications, especially in the area of robotics and planning. A novel approach called Conflict-Based Search (CBS) was invented to solve an MAPF problem optimally. CBS takes in the problem specifications and returns a plan which consists of a set of paths for all agents. However, during the execution of this plan, unexpected delays in the movements of agents may occur. This could render the plan useless at runtime. To cater to this possibility, a variation of CBS, called k-Robust CBS (kR-CBS) was invented. kR-CBS takes into account the delays when it computes a plan, such that during the actual execution, agents following that plan will not collide with each other even if there are delays in their movements. In this project, both CBS and kR-CBS are reviewed, and an implementation of kR-CBS is presented. In addition to implementing the algorithm, a web-based graphical user interface is developed to visualise the movements of agents during runtime. Moreover, further explorations on kR-CBS are conducted and additional features are added to the implementation of kR-CBS. These include the consideration of different types of conflicts and different cost functions. Improvements to the efficiency of the algorithm are also thought through, and three enhancements are added, namely computation of heuristics functions, bypassing conflicts and prioritising conflicts. Experiments are conducted on both the basic version of kR-CBS implementation and the improved versions. In these experiments, we aim to find out the impact of different factors (e.g. number of agents, number of obstacles, maximum delay an agent can have, cost functions, enhancements to the solvers etc.) on the performance of kR-CBS solvers.