論文

査読有り 国際誌
2022年9月

Deadlock-Free Method for Multi-Agent Pickup and Delivery Problem Using Priority Inheritance with Temporary Priority

Procedia Computer Science (Proceedings of 26th International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, KES 2022)
  • Yukita Fujitani
  • ,
  • Tomoki Yamauchi
  • ,
  • Yuki Miyashita
  • ,
  • Toshiharu Sugawara

207
開始ページ
1552
終了ページ
1561
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1016/j.procs.2022.09.212

This paper proposes a control method for the multi-agent pickup and delivery problem (MAPD problem) by extending the priority inheritance with backtracking (PIBT) method to make it applicable to more general environments. PIBT is an effective algorithm that introduces a priority to each agent, and at each timestep, the agents, in descending order of priority, decide their next neighboring locations in the next timestep through communications only with the local agents. Unfortunately, PIBT is only applicable to environments that are modeled as a bi-connected area, and if it contains dead-ends, such as tree-shaped paths, PIBT may cause deadlocks. However, in the real-world environment, there are many dead-end paths to locations such as the shelves where materials are stored as well as loading/unloading locations to transportation trucks. Our proposed method enables MAPD tasks to be performed in environments with some tree-shaped paths without deadlock while preserving the PIBT feature; it does this by allowing the agents to have temporary priorities and restricting agents' movements in the trees. First, we demonstrate that agents can always reach their delivery without deadlock. Our experiments indicate that the proposed method is very efficient, even in environments where PIBT is not applicable, by comparing them with those obtained using the well-known token passing method as a baseline.

リンク情報
DOI
https://doi.org/10.1016/j.procs.2022.09.212
DBLP
https://dblp.uni-trier.de/rec/conf/kes/FujitaniYMS22
URL
https://www.sciencedirect.com/science/article/pii/S187705092201095X
URL
https://arxiv.org/abs/2205.12504
ID情報
  • DOI : 10.1016/j.procs.2022.09.212
  • DBLP ID : conf/kes/FujitaniYMS22

エクスポート
BibTeX RIS