Decentralized deadlock-free path-finding algorithm and ROS 2 implementation for a multi-robot system

This thesis addresses the Multi-Agent Path-Finding (MAPF) problem, which involves computing collision-free paths for multiple agents in shared environments. Traditional centralized approaches struggle with scalability, making decentralized solutions more effective. The study begins by exploring the theoretical foundations of MAPF, including its variants and existing algorithms. Building on this, the thesis introduces the Walk Stop Count and Swap (WSCaS) algorithm, a decentralized and deadlock-free method for coordinating agents in grid-based settings. WSCaS ensures distributed decision-making, leveraging a structured swapping mechanism to resolve conflicts and maintain efficiency. The algorithm, along with a preliminary task assignment process, is first implemented in Python, where numerical simulations and custom scenario generators test its performance across various environments and agent densities. It is then integrated into the Robot Operating System 2 (ROS 2), using the ChoiRbot architecture to implement the algorithm, enabling realistic virtual experiments in the Webots simulator to assess its performance in different scenarios. Results confirm WSCaS’s scalability and effectiveness in dense environments, enabling multi-agent coordination without requiring global control. While not always optimal in terms of path length, its decentralized nature makes it a practical solution for real-world applications such as automated warehouses and cooperative robotics.