  In modern fulfillment warehouses, agents traverse the map to complete endless
tasks that arrive on the fly, which is formulated as a lifelong Multi-Agent
Path Finding (lifelong MAPF) problem. The goal of tackling this challenging
problem is to find the path for each agent in a finite runtime while maximizing
the throughput. However, existing methods encounter exponential growth of
runtime and undesirable phenomena of deadlocks and rerouting as the map size or
agent density grows. To address these challenges in lifelong MAPF, we explore
the idea of highways mainly studied for one-shot MAPF (i.e., finding paths at
once beforehand), which reduces the complexity of the problem by encouraging
agents to move in the same direction. We utilize two methods to incorporate the
highway idea into the lifelong MAPF framework and discuss the properties that
minimize the existing problems of deadlocks and rerouting. The experimental
results demonstrate that the runtime is considerably reduced and the decay of
throughput is gradually insignificant as the map size enlarges under the
settings of the highway. Furthermore, when the density of agents increases, the
phenomena of deadlocks and rerouting are significantly reduced by leveraging
the highway.
