文献

J-GLOBAL ID：202202251471657621   整理番号：22A1981932

暫時的な優先度を導入したPIBT手法の拡張

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

抄録/ポイント： 本研究では,MAPD問題の制御手法であるPriority Inheritance with BackTracking(PIBT)に暫時的な優先度を導入した拡張PIBTを提案し,PIBTの基本的な性質を変えることなく適用環境の制約を緩めることで適用範囲を拡大すると共に,実験的にその効果を示す.PIBT手法はステップことに優先度を計算し,その優先度の高いエージェントから順番に,次のステップでの移動先を確定させるアルゴリズムである.このアルゴリズムでは,行き止まりや袋小路のような形状を含むマップでは行き詰まり(デッドロック)が発生するため,環境にその発生を防ぐ制約を設けている.そこで本研究では,エージェントに通常の優先度に加えて暫時的な優先度を持たせ,更に不要な部分への移動を禁止する拡張を施し,先行研究で求められる条件を緩めても継続的な搬送ができることを述べる.よく知られた既存手法であるToken Passingとの比較実験を通し,その効率が優位であること,特に一般的な応用で想定されるような運搬箇所に集中や偏りがある場合にその効果が極めて高いことを示す.(著者抄録)

シソーラス用語： *マルチエージェントモデル ,  *配送 ,  *優先度 ,  探索理論 ,  効率 ,  ツリー構造 ,  アルゴリズム ,  実験 ,  最適化 ,  評価実験 ,  制約付最適化 ,  深さ優先探索 ,  理論 ,  改変
準シソーラス用語： バックトラック法 ,  効率性

分類 (1件)： オペレーションズリサーチ一般  (KA03010Q)

引用文献 (10件)：

• Dresner, K. and Stone, P.: A Multiagent Approach to Autonomous Intersection Management, J.Artif.Intell.Res, Vol. 31, pp. 591-656 (2008).
• Wurman, P., D’Andrea, R. and Mountz, M.: Coordinating hundreds of cooperative, Autonomous vehicles in warehouses, AI magazine, p. 29 (2008).
• Ma, H., Li, J., Kumar, T. and Koenig, S.: Lifelong multiagent path finding for online pickup and delivery tasks, AAMAS, pp. 837-845 (2017).
• Sharon, G., Stern, R., Felner, A. and Sturtevant, N. R.: Conflict-based search for optimal multi-agent pathfinding, Artif.Intel, Vol. 219, pp. 40-66 (2015).
• Okumura, K., Machida, M., Defago, X. and Tamura, Y.: Priority inheritance with backtracking for iterative multi-agent path finding, IJCAI (2019).

タイトルに関連する用語 (3件)： 優先度 ,  手法 ,  拡張