繰り返し貪欲組合せオークションを用いた利己的マルチエージェント経路計画

• 町田 真直

  日本電気株式会社

書誌事項

タイトル別名

• Iterative Greedy Combinatorial Auction for Self Interested Multi-Agent Path nding

抄録

本稿では、繰り返し貪欲組合せオークションを用いた、利己的なマルチエージェント間における経路探索メカニズムを提案する。マルチエージェント経路探索（MAPF）は、各エージェントがそれぞれのスタートからゴールまで、衝突することなく移動し、全体のコスト（例えば、全エージェントの移動時間）を最小化する経路を探索する問題である。組合せオークション（CA）は、複数の商品を、利己的なエージェントの効用の総和が最大であるように割り当てる問題である。近年の２つの研究で、利己的なエージェント間でのMAPFの手法が提案されている。１つは、ITFと呼ばれる、同時競り上げオークションに似た枠組みを用いている。また、もう一方では、CAを用いて、全体のコストを最小化する手法を提案している。しかし、ITFを用いた手法には近似保証がなく、CAを用いた手法は計算困難（NP困難）であるという欠点がある。本稿では、計算効率の良い繰り返し貪欲組合せオークションを用いた、２種類の手法を提案する。また、１つ目の手法は、エージェント数の２乗の近似保証を持ち、２つ目の手法は、数値実験においてITFより全体のコストが低くなることを示す。

収録刊行物

• 人工知能学会全国大会論文集

  人工知能学会全国大会論文集 JSAI2018 (0), 3J103-3J103, 2018

  一般社団法人 人工知能学会

詳細情報

• CRID: 1390564238001631360
• NII論文ID: 130007425599
• DOI: 10.11517/pjsai.jsai2018.0_3j103
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可