Cloud driven implementation for multi-agent path finding

• Main Author: Datta, Anusha
• Other Authors: Tang Xueyan
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2022
• Subjects: Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
• Online Access: https://hdl.handle.net/10356/156705
• Institution: Nanyang Technological University

Multi-Agent Path Finding (MAPF) is the computational problem of constructing collision-free paths for a set of agents from their respective start to goal positions within a given maze. In recent years, MAPF has gained increasing importance as it is central to many large-scale robotic applications, from logistic distribution systems to simultaneous localization and mapping. Over time, numerous approaches to MAPF have emerged, one of which is the dual level Conflict Based Search (CBS) Algorithm. At the high level, CBS performs search on a binary constraint tree. While at the lower level, it performs a search for a single agent at a time. In most cases, this reformulation enables CBS to examine fewer states than a global A* based approached, while still maintaining optimality. Hence, this project explores Conflict Based Search for optimal Multi-Agent Path Finding. These findings are augmented with additional experimentation on search performances of different lower level search heuristics. Furthermore, this project also includes the design, development and deployment of a cloud driven MAPF application. This application aims to provide an intuitive user experience to interact with the MAPF algorithm, visualise the traversal of the path finding solution and record statistical navigation parameters such as execution cost and execution time of the same. Finally, a navigation statistics pipeline is also established to produce strong predictive insights and navigation trends which subsequently facilitate intelligent business decisions.