分散問題解決のための協調探索手法とその応用に関する研究

点击翻译按钮获取中文摘要

分散問題解決における協調探索とは、問題がグラフにおける初期状態から目標状態への経路探索として定式化され、各エージェントがその部分グラフのみの探索が可能である場合に、エージェントの協力により大局的な経路を発見する探索手法である。本研究ではリンクのコストが動的に変化するような場合に対処するエージェント間の協調方式について研究を進めた。得られた成果は以下のとおりである。1.動的経路探索アルゴリズムの開発:まずグラフのリンクのコストが動的に変化する場合の探索アルゴリズムを開発した。本アルゴリズムでは、エージェントは探索可能な部分グラフ内で部分解候補となる経路の中から一つを選択し、残りの探索を他のエージェントに依頼する。この部分解候補の選択のために、エージェントはコスト情報を交換しあい、その値を候補経路から構成される解経路の推測値として利用する、依頼されたエージェントも目標状態に到達するまで同様の探索を行う。2.協調量の調整:よい部分解候補を選択するためにはエージェント間で十分な情報交換を行わなければならないが、このことは逆に通信オーバヘッドを増加させ、性能の低下をもたらすというトレードオフの関係が成り立つことが明らかになった。そこでエージェント間の協調(情報交換)量を調整する機構を導入し、その最適な協調量を求めた。また、問題グラフのサイズが大きくなると協調のための通信オーバヘッドの影響がさらに大きくなり、そのために情報の発生と拡散を2段階に調整する手法を導入し、その有効性を確認した。また、今後の研究課題としては、状況の変化に応じてエージェントが自律的に協調量を変化させる手法があげられる。