Multiagent Real-Time A* with Selection: Introducing Competition in Cooperative Search

Makoto Yokoo, NTT and Yasuhiko Kitamura, Osaka City University, Japan

A new cooperative search algorithm that introduces a GA-like selection mechanism is developed. In this algorithm, a state-space search problem is solved concurrently by multiple agents, each of which executes the Real-Time-A* algorithm. These agents compete for existence, i. e., each agent periodically reproduces offspring stochastically based on its fitness defined by the heuristic estimation value of its current state, so that an agent in a good state tends to reproduce many offspring while an agent in a bad state tends to be exterminated. Experimental evaluations show that this algorithm is very effective for problems that can be divided into serializable subgoals (e. g., n-puzzles), although the agents do not have any knowledge about these subgoals. In particular, this algorithm can solve the 48-puzzle, which can not be solved by existing heuristic search algorithms consistently within a reasonable amount of time unless the knowledge about the subgoals is explicitly given.

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.