论文标题
基于备用的僵局回避方法用于多代理接送和交付任务
Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks
论文作者
论文摘要
多代理拾取和交付（MAPD）问题，其中多种迭代的材料在没有碰撞的情况下携带材料，引起了极大的关注。但是，许多常规的MAPD算法都假设一个专门设计的网格式环境，例如自动仓库。因此，他们有许多接送地点，代理商可以在其中长时间停留，并有很多绕道而行，以避免由于网格中的行动自由而碰撞。相比之下，由于诸如搜索和建筑工地之类的迷宫般环境的接送/送货地点较少，而且它们的数字可能是不平衡的，因此许多代理商专注于此类位置，导致效率低下的操作，通常会陷入困境或陷入僵局。因此，为了提高运输效率，即使在迷宫般的限制环境中，我们提出了一种避免僵局的方法，称为基于备用的僵局回避（SBDA）。 SBDA使用使用关节找到的算法实时确定的待机节点，并且保证该代理可以在此停留有限的时间。我们证明我们提出的方法的表现优于常规方法。我们还分析了用于选择备用节点的参数如何影响性能。
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.
