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

• Item type: SIG Technical Reports(1)
• 公開日: 2022-02-14
• タイトル: マルチエージェント搬送問題のためのグラフ理論を活用したデッドロック回避手法の提案
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学基幹理工学研究科情報理工・情報通信専攻
• 著者名: 山内, 智貴; 宮下, 裕貴; 菅原, 俊治
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では迷路状の制限された環境でも輸送効率を向上するため，multi-agent pickup and delivery（MAPD）問題に対してグラフ理論を活用したデッドロック回避手法 standby-based deadlock avoidance（SBDA）を提案する．複数エージェントが衝突せずに資材を繰り返し回収・運搬する MAPD 問題が注目されているが，従来の MAPD アルゴリズムの多くは自動倉庫のような特別に設計されたグリッド状の環境を想定する．それらの環境にはエージェントが長時間滞在できる集配場所が多く，グリッド内の移動の自由さから，衝突回避のための迂回路も豊富である．一方，災害現場や建設現場のような迷路状の環境には集配場所が少なく，それらの数が偏るため，多くのエージェントが集配場所に集中する結果，輸送効率の悪化や立ち往生，デッドロックに陥りやすい．SBDA はグラフ理論の articulation-point-finding アルゴリズムを用いてリアルタイムに決定される待機ノードを使用し，エージェントが有限時間そこに滞在することを保証する．我々は実験により，提案手法が従来手法の輸送効率を上回ることを示した．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11135936
• 書誌情報: 研究報告知能システム（ICS）; 巻 2022-ICS-205, 号 4, p. 1-7, 発行日 2022-02-14
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-885X
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会