分散問題解決のための波及型探索法とその評価
Diffusing Search Scheme for Distributed Problem Solving and Its Evaluation
北村泰彦，辰巳昭治，奥本隆昭
Yasuhiko Kitamura, Shoji Tatsumi, and Takaaki Okumoto
情報処理学会論文誌 ，35(12):2651-2663,1994
Transactions of Information Processing Society of Japan，35(12):2651-2663,1994
概要
計算機システムの利用形態は集中から分散へと移行しつつあるが，さらに大規模
な問題解決を行うために，エージェントと呼ばれる自律的な解決器の協調による
分散問題解決が注目されている．従来の研究は特定のアプリケーションやアーキ
テクチャに基づく実験的なアプローチがほとんどであったが，本研究では汎用的
な推論手法である波及型探索方式を提案している．本研究ではまず状態空間表
現による分散問題解決の定式化を行い，分散問題解決を，探索空間が複数のエー
ジェントに分割されているという前提のもとで，初期状態から目標状態までの経
路探索と定義している．したがって解を求めるためには複数のエージェントの
協力による分散探索が不可欠になる．波及型探索は従来の探索手法を分散システ
ムのために拡張したもので，本稿では単一解と最適解を求めるアルゴリズムを提
案し，その完全性，適格性，また解析的にアルゴリズムの計算複雑度，メッセー
ジ複雑度，近似並列度を明らかにしている．さらに，より実際的な評価を行うた
めに分散迷路探索問題を例題とし，波及型探索アルゴリズムの性能と迷路の複雑
度，エージェント間の通信コストとの関係を明らかにしている．その結果，探索
空間が広くなる問題に対しては波及型探索による並列性の向上が示されたが，通
信コストの大きさが性能低下に大きな影響を与えることも明らかになった．
Abstract
Computer systems have been evolving from centralized ones to distributed
ones, and furthermore, cooperating systems, which consists of
intelligent and autonomous agents cooperating with each other, are
drawing attention to cope with large scale and complex problems. Most
of the conventional approaches have been experimental ones based on
specific application or architecture, but, in this paper, we propose a
generic distributed inference scheme wich is called diffusing search.
At first, we formalize distributed problem solving as a search process
to find a path from the initial state to a goal state on a state space
graph which is divided and assigned to each agent a priori, and propose
two diffusing search algorithms to find a single path and an optimal
path respectively. Then, we prove their completeness and admissibility
and analyze their computational and message complexities and approximate
speed-up. To evaluate their actual performance, we make simulation
experiments on distributed maze problems and show its performance
concerning the complexity of maze and the communication cost. As
results, we show that the diffusing search is effective for problems
whose search space becomes large, on the other hand, ineffective when
the communication cost is high.
(In Japanese, 245K bytes)
Last Updated: 96/4/1
kitamura@info.eng.osaka-cu.ac.jp