“®“I–â‘è‚Ì‚½‚ß‚Ì‹¦’²’TõŽè–@

–k‘º‘וFC“A•Û‘nC’C–¤ºŽ¡C‰œ–{—²ºCS.Misbah Deen (University of Keele, DAKE Centre)

ƒ}ƒ‹ƒ`ƒG[ƒWƒFƒ“ƒg‚Æ‹¦’²ŒvŽZIIC‹ß‘ã‰ÈŠwŽÐC137-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