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 算法提供确定性和概率性的保证，在实验中，算法表现出了较好的有效性和健壮性，尤其是减少了重规划的次数。

具有延迟的强大多智能体取送货

Robust Multi-Agent Pickup and Delivery with Delays

The multi-agent pickup and delivery (MAPD) problem, in which multiple agents
iteratively carry materials without collisions, has received significant
attention. However, many conventional MAPD algorithms assume a specifically
designed grid-like environment, such as an automated warehouse. Therefore, they
have many pickup and delivery locations where agents can stay for a lengthy
period, as well as plentiful detours to avoid collisions owing to the freedom
of movement in a grid. By contrast, because a maze-like environment such as a
search-and-rescue or construction site has fewer pickup/delivery locations and
their numbers may be unbalanced, many agents concentrate on such locations
resulting in inefficient operations, often becoming stuck or deadlocked. Thus,
to improve the transportation efficiency even in a maze-like restricted
environment, we propose a deadlock avoidance method, called standby-based
deadlock avoidance (SBDA). SBDA uses standby nodes determined in real-time
using the articulation-point-finding algorithm, and the agent is guaranteed to
stay there for a finite amount of time. We demonstrated that our proposed
method outperforms a conventional approach. We also analyzed how the parameters
used for selecting standby nodes affect the performance.

该研究提出了一种叫做 “基于等待的死锁避免”(SBDA) 的死锁避免方法，可以提高迷宫般的环境中多代理人搬运物资的运输效率。该方法通过实时使用割点算法来确定待机节点，并保证智能体在那里停留一定的时间，从而有效减少阻塞或死锁的情况。实验证明，与传统方法相比，该方法的性能更好。也分析了用于选择待机节点的参数如何影响性能。

多智能体接送任务的基于备用的死锁避免方法

Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks

The Multi-Agent Pickup and Delivery (MAPD) problem models applications where
a large number of agents attend to a stream of incoming pickup-and-delivery
tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and
effective. We make TP even more efficient and effective by using a novel
combinatorial search algorithm, called Safe Interval Path Planning with
Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an
advanced data structure that allows for fast updates and lookups of the current
paths of all agents in an online setting. The resulting MAPD algorithm
TP-SIPPwRT takes kinematic constraints of real robots into account directly
during planning, computes continuous agent movements with given velocities that
work on non-holonomic robots rather than discrete agent movements with uniform
velocity, and is complete for well-formed MAPD instances. We demonstrate its
benefits for automated warehouses using both an agent simulator and a standard
robot simulator. For example, we demonstrate that it can compute paths for
hundreds of agents and thousands of tasks in seconds and is more efficient and
effective than existing MAPD algorithms that use a post-processing step to
adapt their paths to continuous agent movements with given velocities.

本研究介绍了一个处理多智能体运输问题的新算法，使用组合搜索算法 SIPPwRT 进行单智能体路径规划，并考虑了实际机器人的动力学约束，相比于现有算法更为高效和有效。