Talking helps: Evolving communicating agents for the predator-prey pursuitproblem

We analyze a general model of multi-agent communication in which all agents communicate simultaneously to a message board. A genetic algorithm is used to evolve multi-agent languages for the predator agents in a version of th e predator-prey pursuit problem. We show that the resulting behavior of the communicating multi-agent system is equivalent to that of a Mealy finite s tate machine whose states are determined by the agents' usage of the evolve d language. Simulations show that the evolution of a communication language improves the performance of the predators. Increasing the language size (a nd thus increasing the number of possible states in the Mealy machine) impr oves the performance even further. Furthermore, the evolved communicating p redators perform significantly better than all previous work on similar pre y. We introduce a method for incrementally increasing the language size, wh ich results in an effective coarse-to-fine search that significantly reduce s the evolution time required to find a solution. We present some observati ons on the effects of language size, experimental setup, and prey difficult y on the evolved Mealy machines. In particular, we observe that the start s tate is often revisited, and incrementally increasing the language size res ults in smaller Mealy machines. Finally, a simple rule is derived that prov ides a pessimistic estimate on the minimum language size that should be use d for any multi-agent problem.