Language Evolution and Computation Bibliography

We analyze a general model of multi-agent communication in which all agents learn to communicate simultaneously to a message board. We show that the communicating multi-agent system is equivalent to a Mealy finite state machine whose states are determined by the agents' usage of the learned language. Increasing the language size increases the number of possible states in the Mealy machine, and can improve the performance of the multi-agent system. We introduce the term \em semantic density to describe the average number of meanings assigned to each word of a language. Using semantic density, a simple rule is presented that provides a pessimistic estimate of the minimum language size that should be used for any multi-agent problem in which the agents communicate simultaneously. Simulations on a version of the predator-prey pursuit problem, a simplified version of problems seen in warfare scenarios, validate these predictions. The communicating predators evolved using a genetic algorithm perform significantly better than all previous work on similar preys.

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 the predator-prey pursuit problem. We show that the resulting behavior of the communicating multi-agent system is equivalent to that of a Mealy finite state machine whose states are determined by the agents' usage of the evolved language. Simulations show that the evolution of a communication language improves the performance of the predators. Increasing the language size (and thus increasing the number of possible states in the Mealy machine) improves the performance even further. Furthermore, the evolved communicating predators perform significantly better than all previous work on similar prey. We introduce a method for incrementally increasing the language size, which results in an effective coarse-to-fine search that significantly reduces the evolution time required to find a solution. We present some observations on the effects of language size, experimental setup, and prey difficulty on the evolved Mealy machines. In particular, we observe that the start state is often revisited, and incrementally increasing the language size results in smaller Mealy machines. Finally, a simple rule is derived that provides a pessimistic estimate on the minimum language size that should be used for any multi-agent problem.