分散協調問題解決における通信制御法に関する研究

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

複数のエージェントが協調して一つの問題を解決する分散協調問題解決の汎用的手法である波及型探索アルゴリズムにおいて,探索が広がるにつれ,エージェント間の通信が指数的に増加し,性能が急速に低下するという通信オーバヘッドの問題があった.そこで本研究では波及型探索で生じる通信を適切に制御して,探索の並列性と通信オーバヘッドのバランスをとりながら,全体的な性能を向上させるための以下に示す三つの手法を開発し,分散迷路探索によるシミュレーション実験によりその評価を行った.(1)局所静的通信制御手法まず,エージェント毎に並行依頼の上限数を抑える手法を開発した.各エージェントは並行依頼の上限数を示すカウンタを設け,そのカウンタの上限値を定数で抑える.(2)局所動的通信制御手法(1)の方法では通信路の混雑の変化に柔軟に対応することができない.そこで通信路の混雑状況に応じて並行依頼の上限数を自動的に調整する手法を開発した.すなわち,通信路が混雑している場合は並行依頼の上限数を抑え,空いているときは上げるようにする.(3)大局的通信制御手法(2)の局所的な制御手法ではエージェント数が増加すると,エージェントが個別に通信量を調整してもシステム全体の通信量が増加する.そこで送通信量を規制するために,システム全体の並行探索上限数を固定し,この値を各エージェントに配分する手法を開発した.集中制御ではなく,分散的に実現するために並行探索総数を示すト-クンを導入し,これをエージェントに配分するようにした.この手法により,探索初期には初期状態付近のエージェントが活発に探索を行い,終盤には目標状態付近のエージェントが活発になるような分散的で柔軟な探索制御を行うことが可能になった.