マルチエージェント実時間探索における組織化とその評価
An Organizational Approach to Multiagent Real-Time Search and Its Evaluation
北村 泰彦，寺西憲一，辰巳昭治
Yasuhiko Kitamura, Ken-ichi Teranishi, and Shoji Tatsumi
人工知能学会誌，11(3):470-477, 1996.
Journal of Japanese Society for Artificial Intelligence, 11(3):470-477,
1996.
Abstract
Real-Time A* (RTA*) is an on-line search scheme in which look-ahead
searches and moves are interleaved. It does not guarantee to find an
optimal solution but it finds a semi-optimal solution with less search
effort. To improve the quality of solution, Knight has proposed
Multi-Agent Real Time A* (MARTA*), in which multiple agents concurrently
and autonomously execute RTA* for a given problem. In this scheme,
agents do not coordinate their moves, but each agent just randomly
choose its move when the candidates look equally good. In this paper,
we have interest in how agents should coordinate their moves to find a
better solution faster. We propose two organizational approaches based
on scattering and gathering. Each agent measures the distances from
other agents and chooses its move in the direction of departing or
approaching. These two approaches strengthen the discovery effect to
find more undiscovered solutions and the learning effect to find more
good solutions of MARTA* respectively. We evaluate them through
simulation experiments on maze and 15-puzzle problems and analyze why
they work well or not from a point of heuristic depression, which is a
local hollow of heuristic state evaluation values on paths to goal
states. Once an agent falls into a depression, it cannot escape without
filling in the depression, namely updating the state evaluation values.
In a maze problem, in which deep depressions are scattered in its state
space, scattered agents show better performance than gathered agents
because less agents fall into depressions. On the other hand, in a
15-puzzle problem, in which shallow depressions are ubiquitous, gathered
agents shows better performance because they are better at cooperating
to fill in the depressions. As a result, it is shown that we can get
better search performance in MARTA* by using an appropriate organization
of agents depending on the characteristic of heuristic depressions of
the given problem.
(In Japanese, 270K bytes)
Last Updated: 96/9/12
kitamura@info.eng.osaka-cu.ac.jp