Evolving Collective Behaviour in an Artificial Ecology

Background Information

On-Line Results

References

Abstract
Collective behaviour refers to coordinated group motion, common to many animals. The dynamics of a group can be seen as a distributed model, each animal applying the same rule set. This study investigates the use of an evolved controller to produce schooling behaviour. A set of artificial creatures 'live' in an artificial world with hazards and food. Each creature has an artificial neural network brain that controls movement in different situations. A chromosome encodes the network structure, which may be combined using artificial evolution with another chromosome, if a creature should choose to mate. Prey and predators coevolve to produce sophisticated, non-deterministic, behaviour. Particularly the work highlights the consideration for understanding the physiology of the species to understanding behaviour. For example, we found that prey require low-resolution visual systems to provide a global outlook whereas predators prefer dominant frontal vision. These and many other interesting conclusions are discussed.This webpage describes the current state of the project.

 

Background Information

Evolution is marked by developments of behavioural and physical characteristics. Yet some behaviours appear innate; collective behaviours such as conformity, obedience and leadership have been studied for years in social psychology. Yet we can see primitive characteristics of these behaviours in animals, such as fish schools, insect swarms and bird flocks. Even across such a diverse set of creatures, the dynamics are very similar. Partridge [19] states that collective behaviour occurs when animals "move in unison, more as a single organism than a collection of individuals". Movement is dependent on the characteristics of the animal; for example insects can fly in 3 dimensions, unlike sheep which are restricted to 2 dimensions. The circumstances that stimulate movement differ too, for example the presence of prey or cold climates. This paper considers whether sensor configuration is also important to collective behaviour.
From an evolutionary standpoint it is understandable why collective behaviours are prevalent in such a range of creatures. Biologists propose several hypotheses for flocking behaviour. It serves to reduce the risk of being eaten by a predator, provides mating efficiency, enables finding food easier and is a good environment for learning and reducing overall aggression [24]. It may also save energy through reducing drag [18].
Zoologists and other scientists have studied collective behaviour in nature for a long time, but these phenomena have proven to be very difficult to study objectively without threatening ecological validity. Partridge [19] for example used a circular tank 10 meters in diameter with a central gantry; experimenters projected a light over the fish, which were conditioned to be attracted to it. Fish were marked with a number and, as the gantry moved, the fish were tracked by measuring various distances to investigate the adjustment of position within the school.
In recent years, computer modelling and simulation has provided a concrete way to test and derive new theories. Reynolds [21] presented the seminal Artificial Life (ALIFE) work in collective behaviour. His program BOIDS, which implemented artificial birds, did not make any pretence that it represented the behaviour of birds. Instead, its objective was to produce convincing flocking behaviour. Each BOID executed three simple rules or tendencies in the presence of neighbours. Using these three simple rules, complex global behaviour emerged from simple local interactions. The results have been reproduced many times. Some variation on the initial rule set and the method of obtaining neighbours has been explored. In general, changing depth of vision and parameters such as tendency to change velocity and heading in response to neighbours, can drastically alter the structure of the flock.
Since Reynolds [21] little research has been carried out to devise a rule set that can produce more realistic behaviour without compromising the sheer simplicity of the original work. Mataric [14] successfully developed robots to produce flocking behaviour. Mataric states that collective behaviour is the weighted combination of a number of basic interactions: collision avoidance, following, dispersion, aggregation and homing. By programming each of these behaviours into several robots and then setting a weight that determined which was more likely to execute, Mataric was able to produce some fairly sophisticated collective behaviour.
These 'behavioural' models are suitable for defining what characteristics to look for when identifying collective behaviour. But they were 'hand written'. Rather than consider the environment and physiology of the species, they are based on some concept about what principles might be considered important [22]. By focusing on behaviour alone, these models create a deterministic, 1 dimensional controller. Knowledge is generally represented in productions (i.e. 'if … then …' rules) and these models frequently neglect sensory modalities.

TOP

 

On-Line Results

The system is a combination of VRML and C++. The main program, written in C++, controls the population dynamics such as evolution, movement, and the ecology for each generation. The output depicting the movements can be viewed using a separate system. The population dynamics are displayed via VRML source code generated by the main program, which is parsed by an external VRML browser. This gives complete control over the viewing angle, speed, blurring, zooming and colouring and enables dynamic navigation in the environment, all at the touch of a button. VRML is a platform independent language, and one of the unique features of this system is that YOU can judge the results for yourself.

Listed below are a selection of behavioural dynamics observed, by following the link you may view the motion..

 

  • Flock 1: with predators in the system
  • Flock 2: without predators in the system
  • Flock 3: higly coordinated group motion
Note that, objects may be distinguished by:
Green = Food
Red    = Predators
Blue    = Prey

 

VRML PLUG-IN
The easiest way of displaying VRML scripts is to download a plug-in for your browser.  I would recommend Cortona VRML client by ParallelGraphics  (1.8mb), it works under Windows NT/98/95.

VRML performance is dependent on the speed of your PC and the amount of RAM it has. It will also benefit from an accelerated graphics card (provided the card supports windows acceleration).  More VRML browsers and resources can be found at www.vrml.org.

 

Disclaimer - I have made every effort to ensure that these files are safe but I will not be held responsible for any damage these files do to your computer.

 

References
     
    Online Resources
    1. Craig Reynolds BOIDS - This is the seminal work in the area. 
    2. PolyWorld - The homepage of the PolyWorld project.

     

    Offline Resources
    1. Braitenberg V. (1984) Vehicles: Experiments in Synthetic Psychology. Cambridge, MA: MIT Press.
    2. Bremermann, H.J. (1958) The Evolution of Intelligence. The Nervous System as a Model of its Environment. Technical Report No. 1, Contract No. 477(17), Dept. of Mathematics, Univ. of Washington, Seattle.
    3. DeJong K.A. (1975) Analysis of behaviour of a class of genetic adaptive systems PhD Thesis, University of Michigan, Dept. Computer and Communication Sciences.
    4. Evans H.D. (1993) The Physiology of Fishes. CRC Marine Science Series.
    5. Fogel, D.B., Anderson, R. W. (2000a) Revisiting Bremermann's Genetic Algorithm: I. Simultaneous Mutation of All Parameters. In proceedings of Congress on Evolutionary Computation 2000 (CEC 2000), La Jolla Marriot Hotel, La Jolla, California, USA, 16-19 July 2000, pp 1204-1209
    6. Fogel, D.B., Fraser, A. S. (2000b) Running Races with Fraser's Recombination. In proceedings of Congress on Evolutionary Computation 2000 (CEC 2000), La Jolla Marriot Hotel, La Jolla, California, USA, 16-19 July 2000, pp 1217-1222
    7. Fraser, A.S. (1957) Simulation of genetic systems by automatic digital computers. II. Effects of linkage on rates under selection. Australian J. of Biol Sci, vol 10, pp 492-499
    8. Fraser, A.S. (1960) Simulation of genetic systems by automatic digital computers. IV. Epistatis. Australian J. of Biol Sci, vol 13, pp 329-346
    9. Gardner M. (1971) On Cellular Automata, Self Reproduction, The Garden of Eden and the Game of Life. Scientific American, 224, 112-117.
    10. Goldberg, D.E. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley
    11. Holland, J.H. (1992) Adaptation in Natural and Artificial Systems. University of Michigan Press (Second Edition: MIT Press, 1992).
    12. Husbands P., Harvey I., Cliff D. & Miller G. (1997) Artificial Evolution: a New Path for Artificial Intelligence? Brain & Cognition, 34, 130-159.
    13. Langton R. (1989) Artificial Life. Wokingham: Addison Wesley.
    14. Mataric M.J. (1992) Designing Emergent Behaviours: From Local Interations to Collective Intelligence. In From Animals to Animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behaviour, Cambridge, MA: MIT Press, pp.432-441.
    15. Michalewicz Z. (1996) Genetic algorithms + Data Structures = Evolution Programs. 3rd Ed. Springer-Verlag.
    16. Michalewicz, Z and Fogel, D.B. (2000) How To Solve It. Springer-Verlag. ISBN 3-540-66061-5
    17. Niwa H. (1994) Self-organizing Dynamic Model of Fish Schooling, Journal of Theoretical Biology, 171, 123-136.
    18. Partridge B.L. & Pitcher T.J. (1979) Evidence against a Hydrodynamic Function of fish schools. Nature, 279, 418-419.
    19. Partridge B.L. (1982) The structure and function of fish schools. Scientific American, 246, 90-99.
    20. Reynolds C.W. (1987) Flocks, Herds and Schools: A Distributed Behavioural Model. ACM Computer Graphics, 21, (SIGGRAPH 1987 Conference Proceedings), 25-34.
    21. Reynolds C.W. (1992) An Evolved, Vision-Based Behavioural Model of Coordinated Group Motion. In From Animals to Animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behaviour, Cambridge, MA: MIT Press, pp.384-392.
    22. Werner G.M. & Dyer M.G. (1992) Evolution of Herding Behaviour in Artificial Animals. In From Animals to Animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behaviour, Cambridge, MA: MIT Press, pp.393-399
    23. Zaera N., Cliff C. & Bruten J. (1996) (Not) Evolving Collective Behaviours in Synthetic Fish. In From Animals to Animats 4: Proceedings of the Fourth International Conference on Simulation of Adaptive Behaviour, Cambridge, MA: MIT Press, pp.635-6.