Organizational Strategies for Multiagent Real-Time Search

Yasuhiko Kitamura, Ken-ichi Teranishi and Shoji Tatsumi, Osaka City University, Japan

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.