Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks
Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks
复制标题
DOI：
10.5555/3535850.3536009
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Tomoki Yamauchi;Yuki Miyashita;T. Sugawara
中科院分区：
文献类型：
--
作者：
Tomoki Yamauchi;Yuki Miyashita;T. Sugawara
多代理拾取和交付（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.