マルチエージェント実時間探索における組織化とその評価
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