Conflict-Free Node-to-Robot Scheduling for Lifelong Operation in a Warehouse with Narrow-Corridor Environment
Sharad Kumar Singh, M Hemantharaj, Sayantani Bhattacharya, Manish Jha · 2023
This paper presents a solution to lifelong Multi-Agent Path Finding (MAPF) problems for long and narrow-corridor environments. In this setting, robots need to navigate conflict-free paths while adapting to new goals. We propose an algorithm called Conflict-Free Node-To-Robot Scheduling (CFNRS), which effectively coordinates the paths of robots on a given graph in a constrained environment. The algorithm assigns nodes of the graph, ensuring no conflicts with other robots. In particular, we introduce a Deadlock-Detection and Resolution mechanism to find and resolve conflicts and ensure conflict-free paths. We have introduced a problem-reduction technique for improved efficiency. The proposed algorithms are evaluated through simulations in narrow-corridor environments and compared to existing state-of-the-art MAPF solvers, demonstrating their validity and effectiveness in ensuring that robots can navigate conflict-free paths.