Organizational Strategies for Multiagent Real-time Search
Yasuhiko Kitamura, Ken-ichi Teranishi, and Shoji Tatsumi
Faculty of Engineering, Osaka City University
3-3-138 Sugimoto, Sumiyoshi-ku, Osaka 558, JAPANkitamura@info.eng.osaka-cu.ac.jp

Abstract
MultiAgent Real-Time A* (MARTA*) is a multiagent version of Real-Time A* (RTA*) algorithm where multiple agents concurrently and autonomously search and move to nd a solution.
In this paper, we introduce two organizational
strategies based on repulsion and attraction to
MARTA*. Each agent observes the distancesfrom others and moves as it becomes parted fromor approaches others, in contrast it simply moves
randomly in the original MARTA*. Throughsimulation experiments, we demonstrate repulsion and attraction are e ective in both searchtime and solution quality for Maze and 15-puzzle
respectively. However, the opposite combinations of strategy and problem degrade the performance. We nally discuss why the e ectiveness of organizational strategy depends on the
problem from a viewpoint of heuristic depression.
Observed results suggest that there is a fertile
research eld which crosses over the traditional
heuristic search and the organizational approachin multi-agent environment.

Introduction

Heuristic search is a fundamental method to deal with
non-deterministic problem-solving which requires trialand-error exploration of alternatives, and a number ofsearch techniques, such as A* (Nilsson 1971) and Iterative Deepening A* (IDA*) (Korf 1985) algorithms
to name a few, have been investigated (Pearl 1984).
We can regard A* or IDA* as an o -line search algorithm which computes an entire solution path before
executing the rst step in the path. Korf (Korf 1990)
proposed Real-Time A* (RTA*) as an on-line searchalgorithm which interleaves planning for a plausible
next move and executing the move, motivated by thetwo-player game assumptions of limited search horizonand commitment to moves in constant time. RTA* do
not nd optimal solutions, but it can nd semi-optimal
solutions much quicker than traditional o -line searchalgorithms.
To improve solution quality of RTA*, Korf suggests
increasing look-ahead horizon in the planning phase,

but it makes the search time grow exponentially as thedepth of look-ahead horizon increases. As an alternative way, Knight (Knight 1993) proposed MultiAgent Real-Time A* (MARTA*) algorithm to improve
solution quality by increasing the number of agents
engaged in the search. Multiple agents execute RTA*
autonomously and concurrently to attack a single problem. When an agent chooses a next move at the planning phase and there are several candidates that lookequally good, the agent chooses one randomly. By increasing the number of agents, we have more chances
to nd a better solution because more distinct paths
toward goal states are explored. Since the computational complexity of MARTA* grows only linearly as
the number of agents increases, Knight shows many
reactive agents which look ahead shallowly are more
e ective for problems such as 15-puzzle than a few deliberative agents which look ahead deeply.
In the original MARTA* algorithm, however, eachagent chooses its moves just independently and does
not coordinate its moves with others. Multiple agents,
therefore, may search the same path redundantly. In
this paper, we have interest in how agents should becoordinated to nd a better solution more rapidly inthe context of MARTA* and propose two organizational strategies based on repulsion and attraction to
make agents move in coordinated manners. Each agent
observes the distances from others and moves as it
becomes parted from or approaches others. Throughsimulation experiments, we demonstrate repulsion andattraction show better performance in both searchtime and solution quality for Maze and 15-puzzle respectively. However, interestingly the opposite combinations of strategy and problem degrade the performance. Therefore, we discuss why the e ectiveness oforganizational strategy depends on the problem froma viewpoint of heuristic depression (Ishida 1995). Observed results suggest that there is a fertile research
eld which crosses over the traditional heuristic searchand the organizational approach in multi-agent environment.

BackgroundIn this section, we give basic terms on graph andheuristic search for our following discussions.

Basic terms on graphs

A graph is represented as a pair < N; L > where
N (6= ;) is a set of nodes and L( N 2 N ) is a setof directed links. We here assume (n; n) 62 L. In agraph < N; L >, if (n ; n ) 2 L, then n is a childof n and n is a parent of n . A sequence of nodes(n0 ; n1 ; . . . ; n )(m  1) is called a path from n0 to n
if 8k(0  k  m 0 1) : (n ; n +1 ) 2 L, and m is called
the length of the path. When a cost c : L ! R+ , where
R+ is the set of all positive real numbers, is attachedto eachthe cost of path (n0 ; n1 ; . . . ; n ) is given
P 0link,1
as =0c(n ; n +1 ).
i

i

j

j

i

j

m

m

k

m
k

k

m

k

k

A tree is a graph in which every node except the root
(node) has only one parent. A node with no child ina tree is called a leaf. The length from the root to anode n is called the depth to n.

Problem formulation

We can formulate non-deterministic problem solving
with which AI has been dealing by using the state space
representation as follows (Banerji 1980).
A problem is de ned as < S; O; sI ; G > where S
is a non-empty set of states, O( S 2 S ) is a set ofoperators, each of which maps a state to another, sI (2S ) is the initial state, and G( S ) is a set of goal states.
< S; O > constitutes a state space graph.
A solution is de ned as any path (s0 ; s1 ; . . . ; sn ) fromthe initial state sI to a goal state sG 2 G where s0 = sI
and sn = sG . When a cost (> 0) is attached to each
operator, the cost of solution is given as that of solution
path. If there exists a solution with cost cmin andno other solution with cost less than cmin , then thesolution is optimal.

Heuristic search

The most basic operation of state space search is generating a child state by applying an operator to a state.
Especially, if we generate all the child states of a state,then we say the parent state is expanded. We begin
a graph search by expanding the initial state and repeatedly expand generated states until a goal state is
generated.
Although there are various search techniques such as
depth- rst or breadth- rst characterized by the orderof generated states, these brute force algorithms are
not tractable in fact for problems whose state space islarge because of its combinatorial explosion of computation. Hence, to improve the search eciency, we introduce a state evaluation function to prioritize states
to be expanded. In general, the following evaluation
function f (s) is widely used as in A* (Nilsson 1971).
f^(s) = g^(s) + h^ (s);where g^(s) is the actual cost of reaching state s fromthe initial state, and h^ (s) is the estimated cost of reaching the goal state from state s. A* algorithm has aproperty that it always nds an optimal solution iff^(s) never overestimates the actual solution cost. A
major drawback of A* algorithm is that it requires exponential time and space.

Real-time search

We can regard A* as an o -line search algorithm which
computes an entire solution path before executing the
rst step in the path. Korf (Korf 1990) proposed RealTime A* (RTA*) algorithm as an on-line search algorithm which interleaves planning for a plausible next
move and executing the move as follows.
Step1 [Initializing] Set sx = sI .
Step2 [Expansion] Expand sx and let C (sx ) tobe the set of child states.
Step3 [Termination?] If there exists a goal state
in C (sx ), then move to the goal state and quit.
Step4 [Look-ahead search] For all sy 2 C (sx ),calculate f^(sx ; sy ) = c(sx ; sy ) + f^(sy ) which isthe estimated cost from sx to the goal statethrough sy . f^(sy ) is calculated from a lookahead search of depth d from sy as follows.
f^(sy ) = s 2min[^c(sy ; sw ) + h^ (sw )];w W (sy ;d)where W (sy ; d) is the set of leaves of the lookahead search tree and c^(sy ; sw ) is the actual costfrom sy to sw known at the stage.
Step5 [Choice] Choose the best child state s0y
with f^(sx ; s0y )(= minsy 2C (sx ) f^(sx ; sy )). Ties
are broken randomly.
Step6 [Estimation update] Update ^h(sx) to bef^(sx ; s00y )(= minsy 2C (sx )0fsy g f^(sx ; sy )) which isthe estimated cost of the second-best child. If
there is no second-best estimation, let h^ (sx ) =1.
Step7 [Move] Set sx = s0y .
Step8 Go to Step2.
Since RTA* does not use g^(1) which is the actual
cost from the initial state but only h^ (1) which is theestimated cost to the goal state, it may fall into anin nite loop in which the same state may be visitedin nite times because the evaluation function f^(1) does
not re ect the search history. In fact, RTA* guarantees
not to fall into an in nite loop as h^ (1) is updated as
to be increased monotonically in Step 6, and to nd asolution if there exists one at least. In RTA* in whicha single agent is engaged in search, updating h^ (1) withthe second-best estimated cost hinders itself from visiting the same state again. On the other hand, theestimated cost is likely to overestimate the actual one.
0

RTA* do not nd optimal solutions, but it can ndsolutions much quicker than traditional o -line searchalgorithms. Korf suggests a remedy to improve solution quality in RTA*. It is by increasing look-ahead
horizon d, but there is a drawback that the searchtime grows exponentially as d increases. Korf proposed a learning version of RTA* also. In the Learning
RTA* (LRTA*) algorithm, h^ (sx ) is updated with thebest estimation f^(sx ; s0y ) for not overestimating the actual cost. Henceforth, LRTA* guarantees that h^ (1) will
eventually converges to the optimal value, but it takes
more time than RTA* because it needs to revisit thesame state more times than RTA*.

Multiagent real-time search

As an alternative to improve solution quality in RTA*,
Knight (Knight 1993) proposed MultiAgent Real-Time
A* (MARTA*) algorithm in which multiple agents autonomously and concurrently execute RTA* where thelook-ahead horizon is set to be 1.
MARTA* has two advantageous properties.
Discovering e ect The more agents are engaged ina search, the more distinct paths toward goal states
are discovered, and this leads to improving solution
quality. Even if some agents get stuck, others arestill able to continue to search.
Learning e ect The more agents are engaged in asearch, the more actively agents update estimatedcosts, and this also leads to improving solution quality.
While the search time of RTA* grows exponentiallyas the look-ahead horizon increases, that of MARTA*
grows only linearly as the number of agents increases.
Moreover, it is also advantageous that MARTA* canbe implemented on parallel processors naturally.
However, there are two aws in MARTA* concerning updating estimated costs and coordinating agents'
move. When an agent updates ^h(1) in MARTA*, ituses RTA* method in which h^ (1) is updated with thesecond-best estimation which may be overestimating
the state. Since multiple agents share h^ (1) in MARTA*,
overestimated h^ (1) hinders other agents from visiting
the state. On the other hand, LRTA* method in whichh^ (1) is updated with the best estimation does not overestimate, but increases the search time because agentstend to visit the same state again.
In this paper, we devise a hybrid updating methodby combining RTA* and LRTA* methods. Namely,
we use two sorts of estimated costs; common h^ G (1)shared by all the agents and local ^hL (1) for each agent.
h^ G (1) is updated by using the LRTA* method not tooverestimate, and h^ L (1) is locally updated by using the
RTA* method for the agent to refrain from visiting thesame state again. Our new algorithm is obtained frommodifying Step 4 and Step 6 in RTA* as follows.

Step4 [Look-ahead search] For all s 2 C (s ),yxcalculate f^(sx ; sy ) = c(sx ; sy ) + h^ (sy ) which isthe estimation of optimal cost from sx to a goalstate through sy . h^ (sy ) is calculated as follows.
^
not been visited,h^ (sy ) = hh^ G((ssy)) ifif ssy has
Lyy has been visited.
Step6 [Estimation update] Update h^ G(sx ) to bef^(sx ; s0y )
which
is
the
best estimation and h^ L (sx ) to be f^(sx ; s00y )(=minsy 2C (sx )0fsy g f^(sx ; sy )) which is the secondbest estimation. If there is no second-best estimation, let h^ L (sx ) = 1.
This hybrid updating method shows improvement insolution quality comparing with the original MARTA*
in our preliminary experiment.
The second aw is concerning coordination of agents'
moves. In the original MARTA*, when an agent meets
multiple child states that look equally good, it selects
one randomly, but this tends to redundant search andhence degrades the performance. In the next section,
we propose two organizational strategies based on repulsion and attraction to make agents move in a coordinated manner.

0Organizational strategies for MARTA*In the original MARTA*, agents do not move in a coordinated way but just randomly. We expect coordinated moving agents according to the problem would
show better performance than random moving agents.
We, in this paper, propose two organizational strategies based on repulsion and attraction, to coordinate
agents' move. Repulsion is expected to strengthen the
discovering e ect by scattering agents in a wider search
space. In contrast, attraction is expected to strengthen
the learning e ect by making agents update estimatedcosts in a smaller search space more actively.

Repulsion

Each agent observes the location of others, and moves
in a direction such that it repels others when it has
candidates to move that look equally good.
We here de ne the term adjacency of an agent which
represents a locational relation of the agent with otheragents. Adjacency (i; si ) of agent i at state si is calculated as follows.
(i; si ) = j2mind^(si ; sj );A0fig
where A is the set of agents engaged in MARTA*, sj
is the state where agent j is located, d^(si ; sj ) is theestimated distance from si to sj . Namely, adjacency
represents the distance to the nearest agent.
We next de ne repulsive range R as the factor todecide whether the agent repulses others or not. Repulsive range R(si ) for agent i at state si is calculated

as follows.

^ (si )
2hR(s ) = ^
;
h(s )
i

I

where sI is the initial state. The repulsive range islargest when the agent is located at the initial state,then reduces as it is approaching the goal state. Hence,
agents strongly repulse each other at the initial stage ofsearch, but they are converging on the goal state since
the repulsive range becomes smaller as they approach
the goal state. By changing , we can change the sizeof repulsive range.
Using adjacency  and repulsive range R, we now
modify Step 5 of MARTA* as follows.
Step5 [Choice] Agent i chooses s0y
from the candidate set Mi = fsy jf^(si ; sy ) =minsz 2C (si ) [c(si ; sz ) + h^ (sz )]g as follows.
Choose s0y as it satis es(i; s0y ) = maxsy 2M (i; sy )if 8sy 2 M : (i; sy ) < R(si ).
Choose s0y as it satis es  (i; s0y )  R(si )otherwise.
Ties are broken randomly.
In words, if all candidates are within the repulsive
range, choose one with a maximum adjacency. Otherwise, choose one from outside of the repulsive range
randomly.

8>
><
>>:

Attraction

Each agent observes the location of others, and moves
in a direction such as it approaches others when it has
multiple candidates to move that look equally good.
We here de ne a term isolation 1 of an agent. Isolation 1(i; si ) of agent i at state si is calculated asfollows.
1(i; si ) = max d^(si ; sj ):j 2A0fig
We here use attraction range G for an agent to decide
whether it approaches other agents or not. When G
is large, agents are scattered, and when small, agents
move crowdedly.
Step 5 of MARTA* is modi ed as follows.
Step5 [Choice] Agent i selects s0y
from the candidate set Mi = fsy jf^(si ; sy ) =minsz 2C (si ) [c(si ; sz ) + h^ (sz )]g as follows.
Choose s0y as it satis es1(i; s0y ) = minsy 2M 1(i; sy )if 8sy 2 M : 1(i; sy ) > G.
Choose s0y as it satis es 1(i; s0y )  Gotherwise.

8>
><
>>:

Ties are broken randomly.

In words, if all the candidates are located outside of
the attraction range, the agent selects one with a minimum isolation. Otherwise, select one in the attraction
range randomly.
It is easy to combine two strategies. When using the
hybrid strategy, agents are located in a doughnut-areade ned by R and G.

OverheadIn the original MARTA*, as each agent moves independently, there is no overhead for coordination. In ourorganizational approach, we need to spend additional
computational cost to coordinate agents' moves. For
each agent, when it decides the next state to move,it refers to the distances to all the other agents forcalculating adjacency and isolation, so the total computational cost for each turn becomes O(A2 ), where A
is the number of agents engaged in MARTA*.

Experimental evaluation

Evaluation problems

To evaluate proposed organizational strategies, wesolved Maze and 15-puzzle problems by using
MARTA* algorithm.

Maze problem: This is a problem to nd a pathfrom the entrance to the exit in a rectangular grid problem space with randomly positioned obstacles (Ishida& Korf 1991). Each agent can move in the horizontal
or vertical direction, but not in the diagonal direction.
We assume an agent takes a single cost for a single
move. We use the 120 2 120 grid and positioned obstacles at a ratio of 40%. The entrance and the exit arelocated at (1; 1) and (120; 120) respectively. We use
the Euclidean distance to the goal state for the initial
estimated cost of each state and adjacency and isolation of each agent. We execute 100 trials of MARTA*
for 100 randomly generated problems with solutions.

15-puzzle problem: The 15-puzzle consists of a4 2 4 square frame containing 15 numbered square tiles
and a single blank. The legal operators slide any tile
horizontally or vertically adjacent to the blank into theblank position. The task is to rearrange the tiles fromsome random initial con guration into a particular desired goal con guration. We assume an agent takes asingle cost for a single move of tile. We use the Manhattan distance for the initial estimated cost of eachstate and adjacency and isolation of each agent. It is
computed by counting, for each tile not in its goal position, the number of moves along the grid it is awayfrom its goal position, and summing these values over
all tiles. We execute 100 trials of MARTA* for 9 problems selected from 100 problems presented in (Korf
1985). 1
1

We selected 3 dicult , 3 middle, and 3 easy problems.

Results

We solve Maze and 15-puzzle problems by using
MARTA* simulating agents as if they run concurrently
on parallel processors with a shared memory. We assume the accessing cost to the shared memory is negligibly small. We also do not count computational costs
taken for look-ahead search and organizational strategies and normalize the time taken for a single move asa unit time. Then, we measure search time and solution length. The search time is the time taken by the
rst agent which reaches a goal state and the solution
length is obtained by deleting cycles from the foundsolution path.
For evaluation of repulsion, we set the attraction
range to be in nity (G = 1), then we varied the parameter . When = 0, it is equivalent to the original
MARTA*. The averaged results of Maze and 15-puzzle
are shown in Figure 1 and Figure 2 respectively. X-axis
represents the number of agents. The results of the experiments show repulsion is e ective for Maze, but notfor 15-puzzle.
For attraction, we set the repulsion range to be 0
( = 0) and varied the attraction range G. When
G = 1, it is equivalent to the original MARTA*. Weshow the averaged results of Maze and 15-puzzle in
Figure 3 and Figure 4 respectively. The results of theexperiments show that attraction is e ective for 15puzzle, but not for Maze. This result makes a sharp
contrast to that of repulsion.

Discussion

We now explain why the two organizational strategies showed contrasting results by using the conceptof heuristic depression (Ishida 1995). Heuristic depression is a set of connected states whose estimated costare less than or equal to those of the set of immediate
and completely surrounding states. Each agent which
performs MARTA* simply selects a state to move withthe least estimated cost from candidates, so it easily moves to the bottom state of a heuristic depression. Once an agent falls into a heuristic depression,
it cannot escape from it without lling the depression,
namely updating the estimated cost h^ (1) of every statesin the depression until they are equal to those of thesurrounding states.
Here we estimate how widely and deeply heuristic
depressions are distributed in Maze and 15-puzzle bycalculating the di erence between the initial estimatedcost and the actual cost of states through which agents
move on the way to the goal state as follows.
1. Execute a single agent RTA* and record the states
which the agent visited and their initial estimatedcost.
2. Perform the breadth- rst search from the goal stateand calculate the actual costs of the recorded states.
3. Calculate the di erence between the actual cost andthe initial estimated cost of the recorded states.

As the size of search space of 15-puzzle is huge, weused 8-puzzle, which seems to have similar heuristic
depressions, instead of 15-puzzle.
The measurement results of Maze and 8-puzzle areshown in Figure 5(a) and (b) respectively. The Xaxis represents the di erence between the actual cost
and the initial estimated cost (h(s) 0 h^ (s)) and the
Y-axis represents the percentage of states. In Maze,
the di erence distributes widely from 0 to 500. The
ratio of states with the same value is less than 1%. In
contrast, in 8-puzzle, the di erence distributes denselyfrom 0 to 20. Comparing these results, we can supposethat deep heuristic depressions are scattered in Maze
more than in 8-puzzle.
In Maze, as heuristic depressions are spread between
the initial state and walls consisting of obstacles, there
are deep depressions spotted in the state space. On theother hand, in 8-puzzle or 15-puzzle, shallow depressions are distributed ubiquitously. Therefore, attracting agents as a whole easily fall into deep depressionsin Maze. In contrast, as repulsing agents move keeping
some distance with each other, even if some fall into
a depression, the rest can continue to search toward
the goal state. Hence, for Maze, repulsing agents aree ective.
In 15-puzzle, there are many shallow depressions.
In such a state space, it is better for agents to movedensely rather than separately to ll depressions collaboratively, namely to update estimated costs incollaboration with others. For 15-puzzle, attracting
agents are e ective.

Conclusion

We proposed and evaluated two organizational strategies based on repulsion and attraction for MARTA*
algorithm. Each agent engaged in the search observes
the location of others and makes a move as it separates from or approach others. MARTA* has two advantages: discovering e ect and learning e ect, andthey are strengthened by repulsion and attraction respectively. For their evaluations, we used Maze and15-puzzle which are contrasting from a viewpoint ofheuristic depression. For Maze in which deep depressions are spotted, repulsion showed a good performance, and for 15-puzzle in which shallow depressions
are distributed ubiquitously, attraction showed a good
performance. In conclusion, if we use an appropriateorganizational strategy according to the characteristicof problem, we can get better performance than using
random moving agents.
In this paper, we just showed a relation between
appropriate organizations and heuristic depressions inMaze and 15-puzzle problems, so application of ourorganizational approach to other problems and performance evaluation in detail including the overhead of
coordination remain as our future study. However, observed results suggest that there seems to be a fertile
research eld which crosses over the traditional heuris-

370

3500

365

Solution Length

4000

Search Time

3000

2500

2000

1500

360
355
350
345
340

335

1000
2

4

6

8

10

12

14

16

2

4

6

8

10

12

Number of Agents

Number of Agents(a) Search Timeb) Solution Quality

14

16

Figure 1: The e ect of repulsion on Maze.
1700

900

1600
1500

800

Solution Length

1400

Search Time

1300
1200
1100
1000
900

700

600
500

800
700

400

600
500

300
2

4

6

8

10

12

2

4

6

8

10

Number of Agents

Number of Agents(a) Search Timeb) Solution Quality

12

Figure 2: The e ect of repulsion on 15-puzzle.
4500
4000

G = 40360

Solution Length

3000
2500
2000
1500

G=
G = 80G = 60365

G = 60G = 40G = 203500

Search Time370

G=
G = 80G = 20

355
350
345
340

1000

335
2

4

6

8

10

12

14

16

2

4

6

8

10

12

Number of Agents

Number of Agents(a) Search Timeb) Solution Quality

Figure 3: The e ect of attraction on Maze.

14

16

1600

850

G=

G=

G = 15750

G = 15

G = 10G= 5700Solution Length

1200

Search Time800

G = 20

1400

1000

800

G = 20
G = 10
G= 5

650
600
550

500
450
400

600

350
300

400

250
2

4

6

8

10

12

2

4

Number of Agents

6

8

10

12

Number of Agents(a) Search Timeb) Solution Quality

Figure 4: The e ect of attraction on 15-puzzle.
25

Percentage of States (%)

Percentage of States (%)

0.75

0.50

0.25

20

15

10

5

0.00

0
0

100

200

300

400

h(s) - h(s)(a) Maze

500

0

2

4

6

8

10

12

14

16

18

20

h(s) - h(s)(b) 8-puzzle

Figure 5: Distribution of heuristic depressions.
tic search and the organizational approach in multiagent environment.

References

Banerji, R. B. 1980. Arti cial Intelligence: A Theoretical Approach. New York: Elsevier North Holland.
Ishida, T. and Korf, R. E. 1991. Moving Target
Search. In Proceedings of the Twelfth International
Joint Conference on Arti cial Intelligence, 204{210.
International Joint Conferences on Arti cial Intelligence, Inc.
Ishida, T. 1995. Two is not Always Better than One:
Experience in Real-Time Bidirectional Search. In
Proceedings of the First International Conference on
Multi-Agent Systems, 185{192. American Association
for Arti cial Intelligence.

Knight, K. 1993. Are Many Reactive Agents Better
Than a Few Deliberative Ones? In Proceedings of
the Thirteenth International Joint Conference on Arti cial Intelligence, 432{437. International Joint Conferences on Arti cial Intelligence, Inc.
Korf, R. E. 1985. Depth-First Iterative-Deepening:
An Optimal Admissible Tree Search. Arti cial Intelligence 27:97{109.
Korf, R. E. 1990. Real-Time Heuristic Search. Articial Intelligence 42:189{211.
Nilsson, N. J. 1971. Problem Solving Methods in Arti cial Intelligence. New York: McGraw-Hill.
Pearl, J. 1984. Heuristics. Reading, Mass.: AddisonWesley.