Organizational Strategies for Multiagent Real-Time Search
Yasuhiko Kitamura, Ken-ichi Teranishi, and Shoji Tatsumi
Proc. International Conference on Multi-Agent Systems (ICMAS-96), 150-156, 1996.
Abstract
MultiAgent Real-Time A* (MARTA*) is a multi-agent version of Real-Time A* (RTA*) algorithm where multiple agents concurrently and autonomously search and move to find a solution. In this paper, we introduce two organizational strategies based on repulsion and attraction to MARTA*. Each agent observes the distances from others and moves as it becomes parted from or approaches others, in contrast it simply moves randomly in the original MARTA*. Through simulation experiments, we demonstrate repulsion and attraction are effective in both search time and solution quality for Maze and 15-puzzle respectively. However, the opposite combinations of strategy and problem degrade the performance. We finally discuss why the effectiveness of organizational strategy depends on the problem from a viewpoint of heuristic depression. Observed results suggest that there is a fertile research field which crosses over the traditional heuristic search and the organizational approach in multi-agent environment.
(248K bytes)
Last Updated: 97/2/7
kitamura@info.eng.osaka-cu.ac.jp