In Lifelong Multi-Agent Path Finding (L-MAPF) a team of agents performs a
stream of tasks consisting of multiple locations to be visited by the agents on
a shared graph while avoiding collisions with one another. L-MAPF is typically
tackled by partitioning it into multiple consecutive, and hence similar,
"one-shot" MAPF queries, as in the Rolling-Horizon Collision Resolution (RHCR)
algorithm. Therefore, a solution to one query informs the next query, which
leads to similarity with respect to the agents' start and goal positions, and
how collisions need to be resolved from one query to the next. Thus, experience
from solving one MAPF query can potentially be used to speedup solving the next
one. Despite this intuition, current L-MAPF planners solve consecutive MAPF
queries from scratch. In this paper, we introduce a new RHCR-inspired approach
called exRHCR, which exploits experience in its constituent MAPF queries. In
particular, exRHCR employs an extension of Priority-Based Search (PBS), a
state-of-the-art MAPF solver. The extension, which we call exPBS, allows to
warm-start the search with the priorities between agents used by PBS in the
previous MAPF instances. We demonstrate empirically that exRHCR solves L-MAPF
instances up to 39% faster than RHCR, and has the potential to increase system
throughput for given task streams by increasing the number of agents a planner
can cope with for a given time budget.

本文介绍了一种多机器人路径规划算法的新方法 exRHCR，该算法利用先前任务的解决方案来加速新的任务的解决，实验表明，exRHCR 相对于 RHCR 的解决速度提高了 39％，可以在给定时间预算内处理更多的机器人，从而提高了系统的吞吐量。