Multiagent Real-Time-A* with Selection:
Introducing Competition in Cooperative Search
Makoto Yokoo, Yasuhiko Kitamura
Conference on Multiagent Systems (ICMAS-96),
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.,
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