Where to Wait: Postponing the Decision About Waiting Locations in Multi-Agent Path Finding

Abstract

Multi-Agent Path Finding (MAPF) is a problem of finding collision-free paths for a group of agents in a shared discrete environment. The agents often need to wait in place for one or more discrete time steps to avoid each other, and they frequently have multiple locations where they can wait. While the locations may be equally good from the waiting agent’s perspective, they impact the rest of the fleet because no other agent can pass through the location in the meantime. Where exactly an agent waits is decided while planning its path and only takes into consideration the agent’s own preferences. Giving the other agents the option to influence the waiting location can improve the quality of solutions found by MAPF solvers, and in case of solvers which do not re-plan, even improve their success rate. We present the Partially Safe Interval (PSI) which allows to postpone the decision about exact waiting locations while preserving safety. PSI can be obtained by a simple post-processing procedure, and by following an exact set of rules, the waiting locations can be decided whenever an exact path is necessary or when there is only one remaining option. We demonstrate the benefits of PSI using an extension of the Prioritized Safe Interval Path Planning algorithm, which improves the average Sum of Delays by up to 4.12% and the success rate by up to 5% on benchmark maps. We also provide context for the improvement by comparing the results with the state-of-the-art suboptimal methods PIBT and LaCAM.