(149K bytes)Makoto Yokoo (NTT Communication Science Laboratories) and Yasuhiko Kitamura
Proc. International Conference on Multi-Agent Systems (ICMAS-96), 409-4161996.
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.
Last Updated: 97/9/8
kitamura@info.eng.osaka-cu.ac.jp