ƒ}ƒ‹ƒ`ƒ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