The Reachability Objective in Multi-Agent Path Finding

Multi-Agent Path Finding (MAPF) is the problem of path planning for multiple agents while avoiding collisions. In MAPF, each agent must reach a designated target location and stay there. We consider a different objective: each agent must reach its target, but it may move away afterwards. We call this MAPF with Reachability Objective (MAPF-RO). Despite compelling real-world use cases, few prior works have explicitly studied MAPF-RO. We propose several efficient and complete algorithms for MAPF-RO, based on stateof-the-art MAPF algorithms. Experimental results show that using MAPF-RO algorithms instead of classic MAPF algorithms yields huge benefits in terms of runtime and solvability, solving in some cases problems with 1, 000 more agents than baseline approaches. Then, we show a reduction that allows using our MAPF-RO to solve MAPF with Unassigned Agents, a recent practical variant of MAPF in which only a subset of the agents are assigned targets.

Authors

• Noy Gabay Ben-Gurion University of the Negev
• Jonathan Morag Ben-Gurion University of the Negev
• Ariel Felner Computer and Information Sciences, Ben-Gurion University of the Negev
• Roni Stern Ben-Gurion University of the Negev

Keywords

• Multi-agentpathfinding
• Reachabilityobjective
• Unassignedagents