Evolutionary Computational Intelligence for Multi-Agent Simulations
Authors
Abstract
The growing interest in multi-agent simulations, influenced by the advances in fields like complex adaptive systems and artificial life is related to a modern direction in computational intelligence research. Instead of building isolated artificial intelligence systems from the top-down, this new approach attempts to design systems where a population of agents and the environment interact and adaptation processes take place. As proposed by Holland, intelligence can be seen as the inter- nal model of agents. In adaptive systems, this internal model can develop as the agent adapts to the environment. In nature, adaption encompasses varied processes, from neo Darwinian evolution to learning in the brain or in the immune system. We will focus on adaptation based on evolution, which may be considered the fundamental driving force of complexification in Nature.We present the gridbrain, a novel model that attempts to address several important limitations of current artificial brains used in evolutionary multi-agent systems. Two main classes of models are in use nowadays: symbolic approaches like production rule systems or decision trees and ar- tificial neural networks. Evolutionary systems based on IF/THEN rules tend to lead to simple, reactive agents. They can be very effective in developing models to abstract and test ideas about biological, social or other systems, but they are limiting when it comes to evolving more complex computational intelligence. Artificial neural networks are inspired in biological nervous systems. A multitude of algorithms exist for both learning and evolution of ANNs, with many successful implementations. Recurrent neural networks can be shown to be Turing-complete and are theo- retically capable of complex computations. It is important to note, however, that biological neural networks are analogic and highly parallel systems, while modern computers are digital and sequen- tial devices. The implementation of artificial neural networks on digital computers demands for a significant simplification of the biological models. In neural networks, neurons are the building blocks. We believe that for the purpose of evolving artificial brains in multi-agent simulations, it is interesting to experiment with computational building blocks that are a more natural fit to von Neumann?s modern digital computer model. We deconstruct the von Neumann machine into a set of computational building blocks that fall into the categories of input/output, boolean logic, math operations, memory and clocks. This way we expect to facilitate the evolution of systems that take advantage of the processing capabilities of the computer, and more easily develop behaviors that require memory and synchronization.
Another limitation of agent models in current evolutionary multi-agent simulation is the sensory system. Many such simulations use simple 2D grid models where an agent is only capable of perceiving one other world entity per simulation cycle. As we move towards continuous simulations and more sophisticated sensors like vision or audition, we become confronted with the problem of dealing with multiple-object perceptions per simulation cycle. A common approach to this problem is to pre-design a layer of translation for the agent?s brain. Predefinition of sensory translations limit the range of behaviors that the agent may evolve. In the architecture we present, this problem is addressed by dividing the brain in sensory layers (alpha grids) and a decision layer (beta grid). In a way loosely inspired by the human brain, a layer exists for each sensory channel (ex: vision, audition, self state).
It is our goal to create systems where the perception layers can evolve with a great degree of freedom. We present a world definition model where object properties are defined as symbols. These symbols, like variables in programming languages, have types. Agents have internal symbol tables for each symbol type used. For each symbol type, a method to determine the distance between two symbols is provided. Perception components in alpha grids are associated with internal
5
6
symbols, and calculate the distance between this internal symbol and a symbol of the same type perceived in an external object. During evolution, alpha grids may increase their ability to establish distinctions in the environment by increasing the amount of internal symbols against which distance comparisons can be made.
The gridbrain is constituted by a set of rectangular grids of components and a set of feed- forward weighted connections between these components. Inter-grid connections are allowed, from any alpha grid to the beta grid. Some components have an internal state that is preserved across computation cycles, for example clocks. Others, like memory cells, also contain persistent infor- mation.
We describe a set of mutation and recombination genetic operators that can be used to evolve gridbrains from initial empty configurations, allowing each grid to grow independently according to the demands of the environment. We describe mechanisms by which symbol tables and memory adapt their size as gridbrains evolve. Mechanisms to prevent bloat are also discussed.
A simulation embedded genetic algorithm is proposed. This algorithm was designed to impose as few restrictions as possible on the simulation, and it includes extensions for the promotion of cooperative behavior, exploring kin proximity and group selection strategies.
Experimentation is done with LabLOVE, a multi-agent simulation environment that we devel- oped for our research and that is available to the community as open source. We present results from several experimental scenarios, emerging behaviors that adapt to the environment and that include cases of synchronization, cooperation and competition.
We expect out work to have application in the development of more sophisticated scientific multi-agent simulations as well as the engineering os systems like robot swarms, and agents for video games and virtual reality environments.