רון שטרן

Multi-Agent Path Finding (MAPF) deals with finding conflict-free paths for a set of agents from an initial config uration to a given target configuration. The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target. The common approach for solving LMAPF is to treat it as a sequence of MAPF problems, periodically re planning from the agents’ current configurations to their cur rent targets. A significant drawback of this approach is that in MAPF the agents must reach a configuration in which all agents are at their targets simultaneously. Coordinating the agents’ paths such that they occupy their targets at the same time is needlessly restrictive for LMAPF. Techniques have been proposed to indirectly mitigate this drawback. In this po sition paper, we describe cases where these mitigation tech niques fail. As an alternative, we propose to solve LMAPF problems by solving a sequence of modified MAPF prob lems, in which the objective is for each agent to eventually visit its target, but not necessarily for all agents to do so si multaneously. We refer to this MAPF variant as MAPF for Lifelong (MAPF4L) and propose how to solve it by modify ing several existing MAPF algorithms. A limited experimen tal evaluation identifies some cases where using a MAPF4L algorithm can improve the system throughput significantly.