一時的な優先度と退避を用いた効率的なマルチエージェント配送

• Item type: Trans(1)
• 公開日: 2022-12-15
• タイトル: 一時的な優先度と退避を用いた効率的なマルチエージェント配送
• タイトル / 言語: en
• タイトル: Efficient Multi-agent Pickup and Delivery with Temporary Priority and Avoidance
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [オリジナル論文] マルチエージェント配送問題，マルチエージェント経路探索，分散制御
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 早稲田大学基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学基幹理工学研究科情報理工・情報通信専攻
• 著者所属(英): en
• 著者所属(英): School of Fundamental Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): School of Fundamental Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): School of Fundamental Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): School of Fundamental Science and Engineering, Waseda University
• 著者名: 藤谷, 雪北; 山内, 智貴; 宮下, 裕貴; 菅原, 俊治
• 著者名(英): Yukita, Fujitani; Tomoki, Yamauchi; Yuki, Miyashita; Toshiharu, Sugawara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では，マルチエージェント配送問題の制御手法であるPriority Inheritance with BackTracking（PIBT）に一時的な優先度を導入し，PIBTの基本的な性質は保持したまま適用環境の制約を緩め，その適用範囲を広げる拡張型のPIBTを提案する．PIBT手法はステップことに優先度を計算し，その優先度の高いエージェントから順番に，次のステップでの移動先を確定させるアルゴリズムである．このアルゴリズムでは，行き止まりや木構造のような形状を含むマップでは行き詰まり（デッドロック）が発生するため，環境にその発生を防ぐ制約を設けている．そこで本研究では，エージェントに通常の優先度に加えて一時的な優先度を持たせ，さらに不要な部分への移動を禁止する拡張を施し，先行研究で求められる条件を緩め，2重連結領域である主領域に，木構造や小規模の2重連結領域を加えた領域でも継続的な搬送ができることを述べる．条件を緩めた環境において既存手法との比較実験を通し，その効率が高いこと，特に実際の配送問題で想定されるような運搬箇所に集中や偏りがある場合にその効率がきわめて優位であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose an extension of priority inheritance with backtracking (PIBT) by introducing a temporary priority for multi-agent pickup and delivery (MAPD) problem. PIBT is an algorithm that calculates agents' priorities every timestep and determines the location of each agent at next step in turn in order of their priorities. Although, the PIBT algorithm is effective for a MAPD problem, it has a restriction that excludes with tree-structured and cul-de-sac to avoid deadlocks. Our proposed method uses temporary priorities as well as normal priorities, and prohibits movements to unnecessary parts in the environment. Then, it enables agents to conduct MAPD tasks continuously in environments where the original PIBT is not applicable. Through comparative experiments, we show that our method is efficient especially in the environments with a few and unbalanced pickup and delivery locations.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 15, 号 4, p. 11-22, 発行日 2022-12-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会