Decentralized Algorithms for Multi-Agent Pathfinding

Multi-Agent Pathfinding (MAPF) is the problem of planning the trajectory of many agents, from their start location to their respective destination, while sharing the same environment and avoiding collisions. It is part of the AI field of Planning and unifies concepts of Applied Mathematics, Computer Science, and Robotics. MAPF started being studied during the last decades of the 20th century, but only after 2000 some practical solutions were presented. Over the last few years, it acquired more interest, especially from the application point of view, thanks to the development of advanced Robotics Systems. Well-known accomplishments include warehouse automation in Industry 4.0. Specific planning algorithms are fundamental for fast, ordered, and functional agents' operability. Since planning on previously unknown domains requires some ways to build a navigation map of the environment, algorithms are divided into graph-based and grid-based models. Researchers and companies mainly focus on the latter case, grid-based planning, which means the environment is abstracted as a grid whose nodes may contain at most one agent. In this setting, the two main pathfinding techniques are centralized and decentralized. Centralized algorithms aim at finding a solution from the point of view of a higher entity that tries to reduce a global system objective function by treating all agents as a whole composite object in the ensemble environment. Oppositely, decentralized methods plan agents' paths independently and then apply specific techniques to solve possible occurring conflicts. Each agent tries to optimize its user objective function. In this work, we focus on decentralized grid-based solvers. Many ideas can be exploited to develop decentralized methods, such as priorities, abstractions, and hierarchies. Moreover, specific techniques exist that avoid conflicts between agents. The first objective of this project is to make a thorough literature review, focusing on similarities and differences between the literature algorithms. Secondly, inspired by a specific real-world problem, we develop a simple method and five optimized variants, taking inspiration from the approaches available in the literature or exploiting new ideas. In the first simple algorithm, there is no cooperation, so agents act selfishly, and we apply a basic random-style collision avoidance technique to let them escape imminent conflicts. Optimized variants exploit ideas of computational optimization, intelligent movements, and congestion awareness to obtain better performances. The specific real-world problem requires that all these developed algorithms work in an online setting, dealing with agents coming at any time into the system. Useful techniques are then put together in a final optimized version that we compare with some of the best-working literature's decentralized algorithms. Our final goal is to establish connections to well-known Applied Mathematics concepts: Games Theory and Network Traffic Flow. We apply Games Theory to understand the best choice an agent should make when close to possible conflicts and to be pushed in less congested areas while still looking for its shortest path. Network Traffic Flow helps us to quantify the performance of decentralized algorithms with respect to the centralized counterpart. Indeed, solutions coming from decentralized algorithms for MAPF can be interpreted as user optimum traffic assignments, while centralized versions reflect the system point of view.