A Cooperative Search Scheme for Dynamic Problems
Yasuhiko Kitamura, Zheng Bao Chauang, Shoji Tatsumi, and Takaaki Okumoto
Faculty of Engineering, Osaka City University
3-3-138 Sugimoto, Sumiyoshi-ku, Osaka, 558, JAPANS. Misbah Deen
DAKE Centre, University of Keele
Keele, Sta ordshire, ST5 5BG, ENGLAND
schems to nd a path from a start node to a goal nodeby cooperations of multiple agents.
Di using search algorithm is such a distributed pathnding algorithm. [10].
The search begins at an agent with the start nodeand it di uses among agents until some agent nds thegoal node. The problem dealt with in the scheme is astatic problem where the cost of its links is xed. On
the other hand, we deal with dynamic problems where
the cost is dynamically changeable in the cource of
search. A typical example of this problem is a routing
problem in communication networks. Assuming communication nodes and links are managed by agents ina distributed manner, we can view this problem as a
distributed path nding problem to nd an appropriate communication links from a node with a message
to a node of its destination. When we view the communication delay of a link as its cost, as it is changeable according to the amount of incoming messages
into the link, we can view this problem as a dynamic
problem.
To deal with dynamic problems, we propose a cooperative scheme where agents exchange cost information and use it as estimates when required to nd a
I. INTRODUCTION
path.
Distributed problem solving (DPS) mainly studies
In this scheme, the more agents exchange the inforhow multiple agents cooperativelly solve a problem mation, the better estimations which lead to nd bet[3, 9, 7, 4]．Several experimental DPS systems and ter paths are obtained. It, however, raises more comschemes so far have been proposed. Most of them, munication overhead among agents and decreases the
however, are implemented on speci c architectures total performance. In other words, the performance(e.g. blackboard system) and discussed on speci c ap- improvement by cooperations is a trade-o against theplications (e.g. sensor network), and it was dicult communication overhead. Our question, therefore, is
to make general discussions on their relations or com- to know how much information the agents should exparisons among them. Hence, the importance of re- change to make the total performance best and thissearches concerning formulations of DPS or generic is one of important general research issues of DPS[6]．
problem solving schemes is being widely acknowledged We here introduce a device to adjust the amount of[5].
information by a parameter . Namely, when  is low,
As we can see problem solving has been formulated more information is exchanged, but the estimations
conventionally based on search [1], and various search are more accurate. When it is high, the communicaalgorithms are proposed based on heuristics [11], DPS tion is supressed at the cost of the estimations. We
can be formulated based on distributed search [10]． made simulation experiments of a routing problem in a
Assuming each agent searches a given graph partially, communication network to clarify how much  is most
distributed path nding is one of distriubted search appropriate depending on problems.

Abstract The importance of building a generalframework for distributed problem solving is coming
to be acknowledged. Distributed search is one of suchframeworks and de ned as to nd a required path in agiven graph by cooperation of multiple agents, each ofwhich is able to search the graph partially. In this paper, we propose a new cooperative search scheme fordynamic 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 signi cant 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 de ned as its communication delay. We measured its performance according to theamount of the cost information exchanged.

II.

Distributed
problem

path

nding

We here give a formulation of distributed path nding
problem[10].

A. Graph

We give some basic terminology about graph theory
for mathematical preparation.
A graph is denoted as a pair < N; L > where N (6= ;) isa set of nodes and L( N 2 N ) is a set of directed links.
In this paper, we assume only nite graphs where thenumber of N is nite and (n; n) 62 L. A partial graphof < N; L > is < N ; L > which satis es N  N; L 
L; L  N 2 N .
For a given graph < N; L >, if (n ; n ) 2 L, then n
is said to be a child of n and n is said to be a parentof n . A sequence of nodes (n0 ; n1 ; . . . ; n )(m  1) isa path from n0 to n if it satis es 8k(0  k  m 0 1) :` +1 (= (n ; n +1 )) 2 L, and m is the length of the path.
When a cost, c : L ! R where R is the set of positive
real numbers, is assign to eachthe cost of path
P link,1(n0 ; n1 ; . . . ; n ) is de ned as
c
(
`
+1 ).
=0
0

0

0

0

0

0

j

j

i

i

j

m

m

k

b

Connective knowledge represents relations among
the domain knowledge and is denoted as a set of pairsof a node and an agent. If a node is included in domain knowledge of mutiple agents, it is called connective
node. We say the node connects the agents. We havethe following assumption concerning the connective
knowledge.
 8a 2 C; 8n 2 Na ; 8b 2 C 0 fag : n 2 Na \ Nb , (n; b) 2

In words, the connective knowledge of eachagent includes all the pair of connective nodes andthe connected agents.
CKa :

k

m0

m

k;k

k

B. Problem and its solution

A problem is denoted as 3-tuple < G; n ; n > whereis a graph and n ; n 2 N are said tobe start node and goal node respectively. For a given
problem < G; n ; n >, any path from n to n is asolution and the cost of the solution is given as thatof the path. When a solution sol exists, if there is noother solution of which cost is smaller than that ofsol, then sol is called optimal. In the course of problem
solving, if the cost of links is xed, the problem is said
to be static, and otherwise, it is said to be dynamic.
s

G =< N; L >

s

s

g

g

g

s

g

C. Capability of agent

Distributed path nding problem is solved cooperatively by multiple agents. We call the set of agents community denoted by C . We assume an agent is a computational process and is capable of executing search algorithms and exchanging messages with other agents.
We assume also that domain knowledge DK =<N ; L > and connection knowledge CK =< N ; C > areavailable to each agent (a is the agent identi er). Fora graph G =< N; L > and an agent, the domain knowledge represents the partial graph which the agent cansearch and satis es the followings.
 8a 2 C : N  N; L  N 2 N ; L  L. In words,
each agent can search a partial graph of the problem graph. A single agent, hence, may not be able
to nd a whole solution path.
 N =[
N ;L = [L ．Any nodes and links consiting of the problem graph are included in the
a

a

a

0

i

k;k

domain knowledge of some agent in the community. Hence, agents in the community can nd awhole solution path by their cooperation.
 8a; b 2 C : a 6= b ) L \ L = ;. There is no duplicated links in the domain knowledge of agents.
The community is a non-redundant system.

a

a

a2C

a

a

a

a2 C

a

a

a

a

a

D. Path nding algorithms
Non-distributed path nding problem is a classicalproblem and easily solvable by using traditional centralized search algorithms [8]. To solve the distributed
version, which is our main concern, by those algorithms, it is needed to collect cost information managed by distributed agnets into a central agent. These
centralized algorthms have drawbacks such as reliability that the breakdown of the central agent is fatal to
the whole network and eciency that the load and thecommunication are concentrated to the central agent.
On the other hand, the di using searchalgorithm[10] is a distributed version of the traditional
search algorithm. In the algorithm, the search begins
at an agent with the start node. The agent continues
to search in the range of its domain knowledge, andif it reaches to a connective node, the agent requests
the further search to the connected agent(s) by using its connetive knowledge. Once an agent nds agoal node, the search is terminated. In other words,
the search di uses from an agent with the start node
among other agents. When the problem is static, it
is possible to nd an optimal solution by using thisalgorithm with the superiority to the centralized algorithm in its reliability and eciency. In the case of
dynamic problems, however, the di using search algorithm which nds a solution path by cooperationof multiple agents has the following shortcommings.
Since the cost of links are variable dynamically in thecourse of search, the obtained optimal solution may
have been obsolete. The di using search algorithm,
therefore, is not appropriate for dynamic problems.
In IV.., we propose a cooperative search scheme
which adaptable to dynamic problems by exchanging
cost information among agents.

C 12

2

1
C 21

C 41

C 14

C 23

C 32

C 43

4

3
C 34

Figure 1: A Communication Network.
III.

Routing Problem in Communication Networks

The routing problem in communication networks is
one of dynamic ditributed path nding problem. A
communication network can be viewed as a graph consisting of communication nodes and links. The cost of
a communication link is given as its communication
delay or its congestion. The problem is to nd a pathfrom a communication node with a message to a node1
of its destination with cost which is as less as possible .
Although an agent can manage multiple communication nodes and links, we assume that a signle agent
manage only one node and links which is coming outof the node without loss of generality. Thus, in the following discussion, we often identi es a node with anagent which manages the node. By `manage' we here
mean to switch local message routing and to monitor
the communication delay of local links. Multiple agnets thus need to cooperate to nd a path of which
the length is more than 2.
For example, Figure 1 shows a communication network consiting of 4 nodes and 8 links. Node 1 manages
links C12 and C14, node 2 manages links C21 andC23, node 3 manages links C32 and C34, and node
4 manages links C41 and C43. When node 1 has amessage destinated for node 3, there are two routes:
one through node 2 and another through node4, it
is required to know the correct communication delayof 4 links (C12,C23,C14,C43) to nd the appropriate
route. Since node 1 already knows the delays of links
C12 and C14, it needs to cooperate with nodes 2 and4 which knows the delays of links C23 and C43 respectively.
1 Since this problem is a dynamic problem where the cost of linkis changeable according to the amount of messages, it is dicult tode ne a optimal path.

Routing algorithms for communcation networks canbe calssi ed into nonadaptive ones and adaptive ones [12].
Nonadaptive algorithms are not adative to changes of
the topology or the communcation delay of communication networks, and are suitable for static problems.
On the other hand, adaptive algorithms are suitablefor dynamic problems and they are further classi ed
into global, local, and distirbuted algorithms. Global algorithm gather the information distributed among nodes
into a single node called RCC (Routing Control Center) which generates a routing table and distributes its
copys among nodes. In this algorithm, since the prerequisite information is gathered into RCC, the routing is relatively correct and each node needs not tocompute for its routing. On the other hand, RCC has
to do a large amount of computation for the routing
for the whole network and the breakdown of RCC isfatal.
Local algorithm is a way to route messages locally
based on the information locally gatherd by each node.
It is superior to global algorithm in reiability and loadbalancing, but has a drawback that the whole routing
is inaccurate because of the locality of information.
Distributed algorithm is the combination of global
algorithm and local algorithm and its routing is done
locally by each node, but the nodes exchange the required information for the routing. In the next chapter, the proposed scheme is one of distributed algorithms. In the onventinal algorithms, nodes exhange
the information synchronously with a xed time interval. Our propsed algorithm exchanges the information
asynchronously depending on the amount of communication delay of each link by using a threshold value
and is more sensitive to the state of the network.
IV.

Distributed
path nding scheme for dynamic problems

In this chapter, we propose a distiributed path nding
scheme for dynamic problems, using a routing problem in a communication network as an example.

A. Route selection

In our proposed scheme, the node with a message does
not nd a whole path to the node of its destination,
but just nds a path to one of its adjacent nodes andsend the message and commits to nd the rest of thepath to the adjacent node. This scheme thus is adaptive to changes of delay of links in the course of taking
over the message.
Formally, we denote a node with a message as n0 ,a node of its destination as n , adjacent nodes ofn0 as n1 ; . . . ; n where the message is transfered ton through one of those. When we de ne the delaygpg

through an adjacent node n asjc(nj ) = c(n0 ; nj ) + c(nj ; ng );(1)

the selected node n should satisfy c(n ) =.
In this scheme, to nd a better path is equivalent
to nd an more appropriate adjacent node. Under
our assumptions, however, although a node knows theexact delay to its adajacent node, it has to use someestimation for the delay from the adjacent node to thedestined node. In other words, in eq.(1), the rst termis exact but we have to use an estimation c~(n ; n ) for
the second term. We therefore use a scheme where
nodes exchange delay information needed to calculate
estimations.
kkmin1jp c(nj )jgB. Update of delay information

Nodes exchange delay information required to estimate communication delay. Formally, when node n0
monitors a change of link delay c(n0 ; n ) (1  j  p),
it updates its delay information table and noti es thechange to all the other nodes. The receivers also update their tables based on the received information.
When delay of links changes dynamically and frequently, nodes also need to exchange the information
frequently to keep the estimations more accurate. On
the other hand, this raises to increase the amount ofcommunicatation and thus degrades the total performance. It can be viewed that the estimation quality
is trade-o against the communication overhead andit becomes interesting to know how much communication makes the total performance optimal.
We here introduce a device to control communication to exchange the delay information. When anode noti es the delay, it records the value. We assume the initial value is 0. Only when the di erence of change is more than , the node can notify
the delay and update the record. In other words,
only when c(n0 ; n ) 0 c (n0 ; n ) > , the node noti es
and sets c (n0 ; n ) = c(n0 ; n ). To change the value ,hence, enable to control the amount of communication. Namely, when  is set to be lower, more messages
are sent and the quality of estimation is improved.
When it is higher, on the other hand, the quality isdegraded but the amount of communication decreases.
j

k

0

V.

k

0

k

k

Simulation experiments

We executed simulations on a communication networkmodel in Figure 1. We assume each communication
link is a queue. Messages coming in the link arequeued and one message can get out of it and is transfered to the other node in a unit time. We de ne
the delay of a link is the length of the corresponding
queue.
We assume messages are generated at node 1, 2, and
4 and the destination of all is node 3. When node 3 re-ceives a message, it sends back an ACK message. Messages generated at node 2 or 4 are regularly transferedthrough link C23 or C43 respectively, while messages
at node 1 have two choices: through C12 and C23
or through C14 and C43. Node 1 selects the former
when d(C 12) + d(C 23) < d(C 14) + d(C 43) and the latter
when d(C 12) + d(C 23) > d(C 14) + d(C 43). Ties are broken rondomly. (d(C ) denotes the delay of link C or its
estimate.) When node 3 sends back ACK messages,
it follows the same routing process.
We assume messages generated at mode 1,2, and4 follows a Poisson process [2] and 2we denote theiraverages as g1 ; g2 , and g4 respectively . We change thearrival rates of nodes 2 and 4 by using eq.(2) where t
is the current time.
P1 + P2 sin(!t + ):(2)

Control messages with delay information are sentfrom nodes 2 and 4 to nodes 1 and 3 according to theparameter . Namely, node 2 and 4 sends the delay
information of links C23 and C43 respectively to node
1 and that of links C21 and C41 respectively to node3.
We executed a simulation to know how the performance changes according to the parameter . The
arrival rates are g1 = 0:5, g2 = 0:5 + 0:45 sin(2t=1000),
and g4 = 0:5 + 0:45 sin(2t=1000 + ). In words, the communication between nodes 2 and 3 and between nodes
4 and 3 are congested in the interval of 1000 units
time and their phases are opposite each other. Nodes
1 and 3, hence, have to change links according to themessage arrivals at nodes 2 and 4.
To see how the performance changes according to without communication overhead to send delay information, we executed a simulation of an ideal casewhere nodes 2 and 4 can can send delay information
without delay. The performance measure is the turnaround time, the communication time from when node
1 sends a message to when it receives a corresponding ACK message. We used the average of 100,000
messages. When the routing is good, this measure islow. We show the results in Figure 2(exclusive). As 
grows, it shows the performance is degraded.
When there is delay to send the delay information,in other words, normal messages and control messages
are sent through the same link, we show the resultsin Figure 2(inclusive). When  is low, the communication overhead dominates, while the deteriorationof routing dominates, caused by the degraded qualityof estimation, when  is high. As  grows, since theamount of control messages decreases, and the performance approaches that of the ideal case. In thissimulation, the performance is optimal when  = 5.
2 Time interval of messages follows an exponential distribution
with the average 1=g unit time.

Delay
6.2

6.0

5.8

5.6

5.4
inclusive
exclusive
5.2

δ

5.0
0

10

20

Figure 2: Simulation results.

30

VI.

Summary

We proposed a cooprative path nding scheme for dynamic problems, using an example of routing in communication networks. To be adaptive to the dynamicchange of link cost, a node with a message selects arouting only to one of adjacent nodes and commits
the rest to the adjacent node. To select the adjacentnode properly, nodes notify changes of link cost eachother and use them as their estimations. Hence, tokeep the estimations accurate, nodes need frequent exchange and that raise communication overhead which
degrades the total performance. To cope with thisproblme, we introduced a device to control communication by using a parameter  and showed throughsimulation experiments that there exists a amount ofcommunication which optimizes the total performnce.
The followings are future studies.
 General evaluation: we showed through simulation experiments that there exists an optimal
amount of communication for a speci c case. The
optimal amount may depend on the topology of
network, the arrival rate of messages, the cycle ofcongestion, etc. We need a method to evaluate
general cases.
 Automatic control of parameter  : In general, thearrival ratio and the cycle of congestion change
dynamically. We thus need, for each node, a device to control  autonomously to optimize thetotal performance.
 Application to a large network: In this paper, we
simulated a very small network, while if we apply our scheme to a large network, we need amore sophisticated device to cope with a large
amount of communication. For example, whena path between two nodes is long, frequent exchange of detailed delay information between thetwo is inappropriate since most of the information
is obsolete when it reaches to the opposite. We
therefore can propose a scheme to change  foreach pair of nodes according to the length of thepath between them.
References[1] Ranan B. Banerji. Art cial intelligence: a theoretical
approach. Elsevier North Holland, Inc., 1980.
[2] Dimitri Bertsekas and Robert Gallager. Data Networks, Second Edition. Prentice-Hall International,
Inc., 1992.
[3] Alan H. Bond and Les Gasser, editors. Readings inDistributed Arti cial Intelligence. Morgan Kaufman
Publishers, Inc., San Mateo, California, 1988.
[4] Special section on distributed art cial intelligence. IEEE Transactions on System, Man, and Cybernetics, 21(6), November/December 1991.

[5] Edmund H. Durfee. The distributed arti cial intelligence melting pot. IEEE Transactions
on Systems, Man, and Cybernetics, 21(6):1301{1306,
November/December 1991.
[6] Edmund H. Durfee, Victor R. Lesser, andDaniel D. Corkill. Coherent cooperation amongcommunicating problem solvers. IEEE Transactions on Computers, C-36(11):1275{1291, November 1987.
[7] Les Gasser and Michael N. Huhns, editors. Distributed Arti cial Intelligence, Volume II. Morgan
Kaufman Publishers, Inc., San Mateo, California,
1989.
[8] E. Horowitz and S. Sahni. Fundamentals of Computer
Algorithms. Computer Science Press, 1987.
[9] Michael N. Huhns, editor. Distributed Arti cial Intelligence. Morgan Kaufman Publishers, Inc., Los
Altos, California, 1987.
[10] Yasuhiko Kitamura and Takaaki Okumoto. Diffusing inference: An inference method for distributed problem solving. In S. M. Deen, editor,
Cooperating Knowledge Based Systems 1990, pages 79{
94. Springer-Verlag, 1991.
[11] Judea Pearl. Heuristics. Addison-Wesley, Reading,
Massachusetts, 1984.
[12] Andrew S. Tanenbaum. Computer Networks.
Prentice-Hall, 1988.