Organizational Strategies for Multiagent Real-time Search
Yasuhiko Kitamura, Ken-ichi Teranishi, Shoji Tatsumi · 1996
MultiAgent Real-Time A* (MARTA*) is a multiagent 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 MArtTA*. 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 MAR.TA*. 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 degr’d~le 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.