波及型探索に関する研究

波及型探索は分散協調問題解決のための基本的な問題解決手法である．問題は状態空間グラフで表現され，その部分グラフがエージェントにそれぞれ割り当てられていると仮定する．また，解は初期状態から目標状態までの経路として定式化される．このような前提の上で，波及型探索は初期状態をもつエージェントから探索が開始され，そのエージェントが保持する部分グラフの範囲内で探索を行う．隣接するエージェントまでの接続状態に到達するとそれから先の探索を隣接エージェントに依頼する．このように探索は目標状態が発見されるまで徐々にエージェントに波及してゆく．本研究では波及型探索アルゴリズムの完全性，計算量，通信オーバヘッド，階層化について議論している．

関連論文

北村泰彦，辰巳昭治，奥本隆昭．分散問題解決のための波及型探索法とその評価．情報処理学会論文誌，35(12):2651-2663,1994.

Yasuhiko Kitamura, Ken-ichi Teranishi, Shoji Tatsumi, and Takaaki Okumoto. Communication Resource Sharing in Diffusing Inference. International Symposium on Fifth Generation Computer Systems 1994, Workshop on Heterogeneous Cooperative Knowledge-Bases, 167-179, 1994.

北村泰彦，寺西憲一，辰巳昭治，奥本隆昭．波及型探索における通信制御法とその評価．マルチエージェントと協調計算III，近代科学社，185-192, 1994.

Yasuhiko Kitamura, Shoji Tatsumi, Takaaki Okumoto, and S. Misbah Deen. A Problem Decomposition Scheme for Distributed Problem Solving. '94 Japan/Korea Joint Conference on Expert Systems, 71-76, 1994.

Yasuhiko Kitamura and Takaaki Okumoto. Diffusing Inference: An Inference Method for Distributed Problem Solving. CKBS'90: Proceedings of International Working Conference on Cooperating Knowledge Based Systems (ed. S. Misbah Deen), Springer-Verlag, 79-94, 1991.