Emergent Behaviour and Artificial Life

After several days of wracking my brains over what I should talk about at the September UKBUG meeting I decided upon "Something to do with A-life". A-Life has always been a topic that's interested me and it's great fun to play with. It's not very serious though, or, for that matter, very practical. But A-life systems do demonstrate an important characteristic: Emergent Behaviour.

Due to time considerations I haven't had chance to write a very serious article to accompany the talk, but I have put together this article, which is more of a journal, documenting the design and implementation of the demo programs Animal Kingdom and Animal Deliveries. The contents of this article are, more or less, a transcription of the posts I made on the Logical Genetics Forums during the two weeks leading up to the talk.

Animal Kingdom and Animal Deliveries are based on a program that I wrote for a second year project at university with a guy called Nick Johnson. That program was called Donkey World and consisted of a flat square world of small square tiles. The tiles all had a certain amount of grass on them, which grew as time went by. Donkeys were allowed to roam the world randomly, eating the grass as they went. Donkeys had no idea about the shape of the world, or in fact of anything other than the tile they were standing on and the eight tiles around them. They were able to reproduce if they found a suitable mate and able to eat grass to survive. Despite the fact that the donkeys only had a very simple rule based "intelligence" they still formed groups and created a sustained population.

The aim of Animal Kingdom is to develop a more complex system where different types of animal interact in a similar world.

Animal Kingdom

The first task is to develop a class heirarchy for animals and another for the map. The first screen shot, shown in figure 1, shows the map view. The map view is based on a TDrawGrid. The OnDrawCell event has been overridden to allow various bitmap files to be drawn.

Figure 1: The map

Note that I've added water squares round the edge of the map. This means that land animals can't walk off the edge of the world.

Figure 2 shows a similar map (with a view of another part of the coastline). I have now populated the map with a set of creatures. The pink ones are girls and the blue ones are boys (obviously). The creatures are of class TRabbit, but I haven't got round to drawing a rabbit bitmap yet!

Figure 2: The "rabbit" population

I have also implemented a details dialog, so you can see the creature details.

Figure 3: The details dialog is displayed when a tile is double clicked

The next step is to get the rabbits to move around, eat and bonk. That just means adding a few routines to allow animals to detect food and other animals in their 8-neighbourhood (i.e. the eight squares around them), decide whether they are fit for a bonk and then initiate the bonk itself. Once a bonk has been successful (which is based on a probability) the females are pregnant for a number of turns before giving birth. Only creatures of 16 turns old or older will be allowed to bonk. This is not just for the sake of decency, it's to stop male babies immediately impegnating their mothers after they are born!

Figure 4 shows the population after a birth explosion.

Figure 4: Population explosion leads to a lack of food and death for the rabbits

With the original Donkey World we managed to get the population to reach an equilibrium - albeit a sinusoidal one. The important thing is to get the eating and grass growing rates to even out so that the population doesn't crash to nothing aftwer the rabbits eat all the grass.

Figure 5 shows another screen shot with a graph to show the population size of male and female rabbits over time.

Figure 5: The new population graph, showing populations of male and female rabbits

At this point in development I noticed a bug which caused all the rabbits to move to the top corner of the map. This was because of the way the "RandomTile" method was implemented. "RandomTile" is supposed to return a reference to the first tile in the animal's 8-neighbourhood on which the animal is able to survive. The method itterated through the neighbouring tiles clockwise from north. This meant that habitable tiles in a general north-eastery direction were favoured. In order to compensate for this it was necessary to itterate through the directions at random. A friend of mine suggested the following technique (listing 1) which seemed to work well.

function TAnimal.RandomTile: TTile;
var
  i, j, Temp : Integer;
  Dirs : array [0..7] of Integer;
  DirAllowed : array [0..7] of Boolean;
begin
  for i := 0 to 7 do
    DirAllowed[i] := True;

  for i := 0 to 7 do
  begin
    j := Random(8);

    while DirAllowed[j] = false do
      j := (j + 1) mod 8;

    Dirs[i] := j;
    DirAllowed[j] := False;
  end;

  for i := 0 to 7 do
  begin
    if Assigned(Tile.Neighbours[Dirs[i]]) and
       CanSurviveOn(Tile.Neighbours[Dirs[i]]) and
       (Population.AnimalAt(Tile.Neighbours[Dirs[i]].Row,
                        Tile.Neighbours[Dirs[i]].Col) = nil) then
    begin
      Result := Tile.Neighbours[Dirs[i]];
      Exit;
    end;
  end;

  Result := nil;
end;

I managed to get the population to stabilise as soon as the random movement method was fixed. Figure 6 shows the graph that was produced after I left the simulation running for the time it takes to buy and eat a flapjack from the food van.

Figure 6: A stable population of rabbits

Figure 7 is another screen shot. It shows the results of altering the rabbits class so that they behave in the following way (listing 2)

if Hungry and FoodOnThisTile then
  Eat
else if Hungry then
  MoveToTileWithMostFood
else
  MoveRandomly

This is an alteration from the previous code (listing 3)

if Hungry and FoodOnThisTile then
  Eat
else
  MoveRandomly

The goal seeking element of the new algorithm, which causes hungry bunnies to move to the tile with the most food, allows bunnies to live longer. The goal seeking, combined with the random exploration which occurs when rabbits which aren't hungry move to a random tile, causes the population to spread much more evenly across the map. A much larger population can be sustained, with little or no fluctuations after the initial "baby boom". The rabbits eat almost all the food on the map though, quickly finding and devouring any pockets of grass they find.

Figure 7: The rabbit population with the new behaviour

So now I have a working version of Donkey world. The next step is to develop some predator animals to see if I can reproduce some interesting interactions between two species. Figure 8 shows a fox.

Figure 8: After the addition of foxes to the simulation

In first experiments, 20% of the initial population were foxes. Foxes bonk and reproduce in much the same way as rabbits (exactly the same way in fact) but, obviously enough, don't eat grass. Instead they eat rabbits.

Initially the fox population crashed almost immediately, as they moved randomly and didn't actively seek either food or sex. Figure 9 shows the rise and fall of the fox population. Note also the addition of the population "Mini Map" which shows the distribution of the animals around the world.

Figure 9: The rise and fall of the fox population. Foxes in yellow/green

In order to try to extend the life of the fox population I implemented some goal seeking (for food and sex) for the foxes. Getting the two populations to stabilise was a very hard problem indeed. In fact I didn't manage to get a stable fox and rabbit simulation running at all. The problem is that foxes are dependant on rabbits, but rabbits are not dependant on foxes, so the foxes are inherently the weaker species. Figures 10 and 11 show the foxes slightly extended lifespan with the new heuristic (goal seeking) behaviour. Unfortunately in these cases they wipe out the rabbit population and their dependancy on the rabbits for food causes them all to die.

Figure 10: The fox population crashes due to a lack of food

Figure 11: Another crashing fox population

Figure 12 shows an animation of the Mini Map over time. White dots are rabbits and blue dots are a new species of animal: Hares. Hares are very similar to rabbits, but are more intelligent and faster, i.e. they goal seek bonking opportunities and move two squares per cycle.

Figure 12: Animation of a population of rabbits and hares over time

At this point I also added new graphics for rabbits and hares. Hares are the ones with longer legs. Blue creatures are male and pink creatures are female.

Figure 13: Hares and rabbits

I descovered early on that the hares "intelligence" allowed them to quickly dominate, wiping out the rabbits by eating all the food and outliving the foxes. Watch the animation in figure 14 to see the hares take over the world. As far as I can tell, the reasons they do this are:

1. They goal seek bonking, so they are able to cope with being widely dispersed accross a relatively empty map - unlike the rabbits
2. They move faster than the rabbits, thus beating them to the food
3. They do not rely on a high population of other creatures for survival, like the foxes do

Figure 14: Hare dominating in a population of all three species

Suprisingly, even after lowering the probability of a lady hare getting pregnant to just 10% they still seemed to dominate.

Animal Deliveries

The Animal Kingdom simulation is interesting enough. It illustrates many emergent behaviours among populations of simple interacting artificial organisms. It isn't a very "real world" simulation though, and fails to demonstrate how we can design things using emergent behaviours. This section details the other demo program I developed: Animal Deliveries. This program illustrates how a complex task can be solved by a set of cooperating agents. The problem is best described using the rough sketch from my lab book shown in figure 15.

Figure 15: The Animal Deliveries problem

Basically the animals are replaced by two types of robot, water robots (boats) and land robots (trucks). The job of the robots is to deliver parcels from the left hand side of the world to the right. Cooperation is required as there is a big river in the middle of the map. Boats can not sail on land and trucks can not drive through water, but both can meet on a thin strip of beach on each side of the river, where parcels must be exchanged.

The task in hand is to develop some very simple rules for both types of robot to get them to deliver packages successfully. Figure 16 is a screen shot of the robots and the new tarmac world.

Figure 16: The Animal Deliveries world

Listing 4 shows the behaviour for the Boat and Truck agents. Both types of agent have the same behaviour at the moment. If they are hungry (i.e. their batteries are running low) they head towards a charging point. Otherwise they head left. When they reach the far left edge of the map they randomly "search" for a parcel. When they reach a parcel they pick it up and head right. When they can not travel any further to the right they drop the parcel and head back towards the left to find another. The "Searching" boolean is an internal state variable which is used to control this behaviour.

procedure TBoat.ProcessTurn;
var
  Charger : IThing;
  Parcel : IThing;
begin
  inherited ProcessTurn;

  //References to anything interesting we might be stood on
  Charger := Tile.ThingByType('TChargingStation');
  Parcel := Tile.ThingByType('TParcel');

  if Assigned(Charger) and not Carrying then
    Eat(Charger);

  if IsHungry then
  begin
   if Carrying then
     PutDown(Thing, Tile)
   else
    Move(TileTowardsChargingPoint(25));
  end
  else if Carrying then
  begin
    if not CanSurviveOn(Tile.EastTile) then
      PutDown(Thing, Tile)
    else
      Move(TileInGeneralDirection(2));
  end
  else if Seeking and Assigned(Parcel) then
  begin
    Pickup(Parcel, Tile);
  end
  else if not Seeking then
  begin
    if not CanSurviveOn(Tile.WestTile) then
      Seeking := True
    else
      Move(TileInGeneralDirection(6));
  end
  else
  begin
    Move(RandomTile);
  end;
end;

Figure 17 shows the Animal Deliveries simulation running. Note that even though there is no global control for the simulation and the robots are incapable of communicating and have no understanding of the size and topology of the environment in which they live, they are still able to cooperate to deliver the parcels to the right hand side of the map. Green blobs are parcels, red blobs are trucks, light blue blobs are boats and the white blobs correspond to charging stations - though these are not used properly yet.

Figure 17: The Animal Deliveries simulation running. Trucks are red, boats are blue and parcels are green

As you can see, the parcels appear in the left hand 6th of the world and are quickly dispatched to the right hand side. In order to do this I had to implement two new types of tile: Depot tiles, where parcels can be dropped off and Beach tiles, which can be occupied by both boats and trucks (in order to allow for parcel changeover). Figure 18 shows a picture of trucks and boats exchanging parcels on the left hand beach:

Figure 18: Trucks and boats exchanging parcels on the left hand beach

Figure 19 is a picture of trucks dropping off parcels on the right hand side of the map:

Figure 19: Trucks dropping off parcels on the right hand side of the map

Downloads

Feel free to download, play with, alter and extend the demo programs as you see fit. If you manage to generate any interesting behaviours or would like to discuss the software then feel free to get in touch via email or the Logical Genetics Forums. I'd be very interested to hear from anyone who has created more animal classes or demonstrated any interesting new emergent behaviours.

---

"Emergent Behaviour and Artificial Life" (all text and figures) © 2003 Dan Taylor, Logical Genetics