[3H4-J-7] Agents: intelligence in/among robots

[3H4-J-7-02] Strategyproof Mechanism with Agents Grouping for Multi-Agent Pathfinding

〇Manao Machida¹ (1. NEC)

Keywords:Mechanism Design, Multi-Agent Pathfinding

マルチエージェント経路計画問題（MAPF）は、グラフ上に存在するエージェントが、互いに衝突することなく、各々のスタート地点からゴール地点まで移動する問題である。メカニズムデザインは、エージェントの利己的な行動が社会的に望ましい結果を生むメカニズムをデザインすることを目的とする。特に、最適性と耐戦略性を満たすVCGメカニズムが有名である。しかしながら、VCGをMAPFに適用する場合、NP困難な問題を解く必要がある。
本稿では、利己的かつ移動時間に対して異なる線形なコストを持つエージェント間の経路計画問題を解く、計算効率の良い正直申告メカニズムを提案する。また、数値実験により、提案メカニズムがパラメータの設定により、計算時間を調整できることを示す。