文献

J-GLOBAL ID：202202220345880222   整理番号：22A0934539

マルチエージェント搬送問題のためのグラフ理論を活用したデッドロック回避手法の提案

著者 (3件)： 山内智貴 (早稲田大) ,  宮下裕貴 (早稲田大) ,  菅原俊治 (早稲田大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2022  号： ICS-205  ページ： Vol.2022-ICS-205,No.4,1-7 (WEB ONLY)  発行年： 2022年02月14日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本研究では迷路状の制限された環境でも輸送効率を向上するため,multi-agent pickup and delivery(MAPD)問題に対してグラフ理論を活用したデッドロック回避手法standby-based deadlock avoidance(SBDA)を提案する.複数エージェントが衝突せずに資材を繰り返し回収・運搬するMAPD問題が注目されているが,従来のMAPDアルゴリズムの多くは自動倉庫のような特別に設計されたグリッド状の環境を想定する.それらの環境にはエージェントが長時間滞在できる集配場所が多く,グリッド内の移動の自由さから,衝突回避のための迂回路も豊富である.一方,災害現場や建設現場のような迷路状の環境には集配場所が少なく,それらの数が偏るため,多くのエージェントが集配場所に集中する結果,輸送効率の悪化や立ち往生,デッドロックに陥りやすい.SBDAはグラフ理論のarticulation-point-findingアルゴリズムを用いてリアルタイムに決定される待機ノードを使用し,エージェントが有限時間そこに滞在することを保証する.我々は実験により,提案手法が従来手法の輸送効率を上回ることを示した.(著者抄録)

シソーラス用語： *マルチエージェントシステム ,  グラフ理論 ,  *デッドロック ,  産業用ロボット ,  衝突回避
準シソーラス用語： *デッドロック回避 ,  搬送ロボット

分類 (1件)： ロボットの運動・制御  (IC04012J)

引用文献 (13件)：

• Čáp, M., Vokřínek, J. and Kleiner, A.: Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures, Twenty-Fifth International Conference on Automated Planning and Scheduling, pp. 324-332 (2015).
• Krakowczyk, D., Wolff, J., Ciobanu, A., Meyer, D. J. and Hrabia, C.-E.: Developing a Distributed Drone Delivery System with a Hybrid Behavior Planning System, Joint German/Austrian Conference on Artificial Intelligence (Künstliche Intelligenz), Springer, pp. 107-114 (2018).
• Li, J., Tinka, A., Kiesel, S., Durham, J. W., Kumar, T. S. and Koenig, S.: Lifelong Multi-Agent Path Finding in Large-Scale Warehouses, Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1898-1900 (2020).
• Liu, M., Ma, H., Li, J. and Koenig, S.: Task and Path Planning for Multi-Agent Pickup and Delivery, Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, pp. 1152-1160 (2019).
• Ma, H., Li, J., Kumar, T. and Koenig, S.: Lifelong multiagent path finding for online pickup and delivery tasks, Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, pp. 837-845 (2017).

タイトルに関連する用語 (7件)： マルチエージェント ,  問題 ,  グラフ理論 ,  活用 ,  デッドロック回避 ,  手法 ,  提案