Maximizing Throughput in Lifelong Multi-Agent Path Finding with Unassigned Agents

Abstract

The Multi-agent Path Finding with Unassigned Agents (MAPFUA) is a recently introduced practical variant of MAPF. In MAPFUA there are two types of agents: assigned agents that have targets to go to and unassigned agents}that do not have targets but are allowed to move to clear the way for the assigned agents. In this paper we deal with the lifelong variant LMAPFUA where new tasks arrive over time and the aim is to maximize the throughput. We first provide a new variant of Lacam for MAPFUA and a general framework for LMAPFUA. We then focus on the best balance between the total number of agents available and how many of them should be assigned for achieving high throughput. Our experiments show that usually a higher throughput is achieved if some assigned agents are transferred to be unassigned agents that may be better positioned to perform future tasks.