マルチエージェント実時間探索における組織化手法
An Organizational Approach to Multiagent Real-Time Search
北村泰彦，寺西憲一，辰巳昭治，奥本隆昭
Yasuhiko Kitamura, Teranishi Ken-ichi, Shoji Tatsumi, and Takaaki Okumoto
マルチエージェント協調計算IV，近代科学社，85-91，1995
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