分散制約充足問題のためのMulti-agent Tabu Search手法の効果

摘要

近年，ネットワーク接続された分散自律ロボットの登場などにより，分散制約充足問題の位置付けが重要性を増している．分散制約充足問題は，制約充足問題（CSP）の制約と変数それぞれがエージェントに分散した問題である．本論文では，分散制約充足問題を解くためのメタヒューリスティックスとしてMulti-agent Tabu Search 手法を提案する．Multi-agent Tabu Search 手法はエージェント間の局所的ルールによりエージェントが組織化されることで，局所最適解からの脱出が行われる．このMulti-agent Tabu Search 手法を応用した二つのアルゴリズムを試作評価した結果，従来のアルゴリズムより効率的であることが確認された.