Delay-tolerant Multi-Agent Path Finding: Delay-tolerant methods for solving multi-agent path finding problems in autonomous systems

Abstract

Multi-agent path finding algorithms find collision-free paths that agents should follow according to a schedule. The schedules found by multi-agent path finding algorithms are strict, meaning that when a robot in an autonomous system is delayed and fall behind schedule, the schedule is invalidated and the movement of all agents are paused until a new schedule is found. Computing these schedules is inherently slow due to the hardness of multi-agent path finding problems. There are methods, such as MAPF-POST, which find the delay tolerance of a given schedule and, in some cases, allow agents to be delayed without doing expensive replanning. We propose a modification to the multi-agent path finding algorithm Conflict-based search, which makes the schedule found by the algorithm tolerant to delays. The delay tolerance that the schedule should have can be selected by the user. Our results show that the delay tolerant conflict-based search can successfully reduce the number of recalculations in a system with delays, at the cost of a higher run-time. We also propose a method called refined component stalling, which avoids recalculations by purposefully delaying a subset of the agents in order to retain a valid schedule. Our experiments show that this method successfully reduces the number of agents affected by delays and the need for recalculations, at the cost of giving the agents longer paths. Our contributions reduces the time spent on recalculations significantly, which means that the time it takes for the agents to follow a schedule may be faster compared to existing multi-agent path finding algorithms, which sometimes spends a lot of time on recalculations. This is especially clear when agents move fast, since the longer path length of our contributions are less noticeable.