動的問題のための協調探索手法
北村泰彦，鄭保創，辰巳昭治，奥本隆昭，S.Misbah Deen (University of Keele, DAKE Centre)
マルチエージェントと協調計算II，近代科学社，137-147, 1993.
Abstract
The importance of building a general framework for distributed problem
solving is coming to be acknowledged. Distributed search is one of such
frameworks and defined as to find a required path in a given graph by
cooperation of multiple agents, each of which is able to search the
graph partially. In this paper, we propose a new cooperative search
scheme for dynamic problems where costs of links are changeable during
search. To cope with the dynamic character, agents cooperate with each
other by exchanging cost information that they keep. When the amount of
exchanged information is large, the quality of solution is improved, but
on the other hand it raises communication overhead. Therefore, it
is significant to know how much information optimizes the performance.
We developed a testbed that simulates a communication network and
applied our scheme to the routing problem which can be viewed as a
dynamic problem where the cost of a link is defined as its communication
delay. We measured its performance according to the amount of the cost
information exchanged.
(130K bytes)
Last Updated: 96/4/1
kitamura@info.eng.osaka-cu.ac.jp