##
ƒ}ƒ‹ƒ`ƒG[ƒWƒFƒ“ƒgŽÀŽžŠÔ’Tõ‚É‚¨‚¯‚é‘gD‰»Žè–@

An Organizational Approach to Multiagent Real-Time Search

–k‘º‘×•FCŽ›¼Œ›ˆêC’C–¤ºŽ¡C‰œ–{—²º

Yasuhiko Kitamura, Teranishi Ken-ichi, Shoji Tatsumi, and Takaaki Okumoto
ƒ}ƒ‹ƒ`ƒG[ƒWƒFƒ“ƒg‹¦’²ŒvŽZIVC‹ß‘ã‰ÈŠwŽÐC85-91C1995

Multi Agent and Cooperative Computation '94, Kindaikagakusha, ISBN4-7649-0251-6,
85-91, 1995.

*Abstract*

Conventional off-line search schemes, for example A*, find a complete
optimal solution path before starting to move, and the amount of
computation grows exponentially as the size of problem (the number of
nodes) grows. Real-time A* (RTA*), which interleaves lookahead search
and move, can reduce the amount of computation at the cost of no
guarantee of solution optimality. A way to improve the solution quality
of RTA* is to increase the depth of lookahead horizon, but the amount of
computation grows exponentially as the depth increases. An alternative
way is to increase the number of agents which involve in the search. In
the multiagent RTA*, each agent autonomously executes RTA* and makes a
random move when multiple paths to go look equally good. The solution
quality is improved as the number of agents is increased because the
agents can find more undiscovered paths, and the amount of computation
grows only linearly as the the number of agents increases. In this
paper, we propose an organizational approach to coordinate agents in the
multiagent RTA*. Our approach tries to make agents scatter by making
them repelling each other. Its performance is evaluated by using maze
and 15-puzzle problems. It is shown that effect of repelling
among agents depends on the depth and the distribution of heuristic
depressions in the state space graph.
(In Japanese, 88K bytes)

**Last Updated: ***96/4/1*

kitamura@info.eng.osaka-cu.ac.jp