Multi-Agent Pickup and Delivery (MAPD) is the problem of computing
collision-free paths for a group of agents such that they can safely reach
delivery locations from pickup ones. These locations are provided at runtime,
making MAPD a combination between classical Multi-Agent Path Finding (MAPF) and
online task assignment. Current algorithms for MAPD do not consider many of the
practical issues encountered in real applications: real agents often do not
follow the planned paths perfectly, and may be subject to delays and failures.
In this paper, we study the problem of MAPD with delays, and we present two
solution approaches that provide robustness guarantees by planning paths that
limit the effects of imperfect execution. In particular, we introduce two
algorithms, k-TP and p-TP, both based on a decentralized algorithm typically
used to solve MAPD, Token Passing (TP), which offer deterministic and
probabilistic guarantees, respectively. Experimentally, we compare our
algorithms against a version of TP enriched with online replanning. k-TP and
p-TP provide robust solutions, significantly reducing the number of replans
caused by delays, with little or no increase in solution cost and running time.

本文研究带延迟的 Multi-Agent Pickup and Delivery 问题，提出了两种算法，基于 Token Passing 算法提供确定性和概率性的保证，在实验中，算法表现出了较好的有效性和健壮性，尤其是减少了重规划的次数。