beetle

In the genetic algorithms described earlier the software had to 'play God' by selecting the fittest individuals for reproduction. This program based on the column of AK Dewdney in Scientific American of november 1985 ⁽¹⁾ is a bit more cruel to it's creatures. They either adapt, or die.

The concept is very simple. A group of beetles lives in an atrificial world. In order to live the beetles must eat, however the distribution of the food requires a certain behaviour in order to actually find it. Those who do not display that behaviour don't find the food, and die. Those who are successful in finding food get to reproduce. Since there is no mate all parent genes are completely copied to the child, however one random mutation is made. That's all there is to it, AI software doesn't come simpler than this!

beetle gene

The genes of each beetle are stored in the format shown above. The number is the current number of that beetle in a specific run, the serial number is the unique beetle number. The age is the number of runs the beetle has survived. The x and y position indicate the location of the beetle on the screen. Each time the beetle moves a bit of energy is lost, but when food is found energy is gained again. If the energy level get's down to zero the beetle dies (and is removed). If the energy is high enough the beetle is allowed to reproduce. The array of direction/chance fields is the part that determines the beetles behaviour. Whenever a choice has to be made regarding the direction of the beetle 'dice' are thrown. The direction with the highest chance has the highest chance to be selected. During reproduction these chance fields are modified by a random mutation.

Since we are mainly interested in breeding some sort of robotic behaviour the beetles program has it's food in squares, surrounded by a thick black line. All beetles when born are placed inside one of the squares, right in the middle of the food. If they turn around when they 'hit' the black line they stay within the food region. If they do not turn around and thus cross the black line they will die before reaching the next square. So successful beetles will learn to avoid the black line, and if we copy that behaviour into a Lego robot we end up with a robot that will stay within a black square. This is what the screen looks like:

beetle.bas

The tiny blue specs are the beetles, those who have wandered outside the food squares will die. The screen wrap's around, so if a beetle walks off the screen it reappears on the other side. At the bottom are some statistics. The number of splits indicates how many reproductions have taken place. Ofcourse you can distribute the food any way you want, and thus breed completely different behaviours. Click here to download the source in Quick Basic.

Apart from that the program contains some basic variables that help control the genetic process:

'base data
MaxAantalTor = 400        'Maximum number of beetles allowed
AantalTor = 10            'Number of active (alive) Beetles
SplitsingsRecht = 40      'Required energy to split
WaardeBacterie = 2        'Energy per food particle
EindeCyclus = 1000000000  'Maximum number of cycles (runs)
MinimaalTor = 1           'Minimum number of Beetles to continue program
Mutatie = 5               'Mutation size

Beware that this is not exactly a fast process. I like it very much because it's so simple and yet yields such interesting results, but it does take a bit of time. The run below took several hours on a Pentium 166. As you can see after about 800 runs a promising beetle has emerged, and the maximum age in the population is increasing, but after 1400 runs something goes wrong and our 'star performer' dies. It takes about 400 more runs for the next successful beetle to emerge but then we're on a roll and by the time I want to go to bed (after 4000 runs) the most successful beetle has survived 1762 runs, and the average of the population is 433. Ofcourse not all runs look like this, you'll have total failures as well...

screenshot dat_anal.bas

If the population drops below the minimum size new beetles are randomly added, so it is not unusual to have a very low minimum age within the group. On the horizontal axis in the graph is the number of runs (unit is 100!) on the vertical axis is the age (in runs). Click here to download the source in Quick Basic of the program that shows the graphs based on the datafile of the beetle.bas program. If you'd like to see the best performer of the run above in rcx-code click here.

I hadn't done any real projects with the Mindstorm yet, and since everybody said the Lego rcx-code wasn't powerfull enough to do any AI work with it, I thought I'd give it a try. So once beetle.bas finishes it generates a source code for the best beetle of the last run in Mindstorm in rcx-code, like this:

#source RIS1.5
#target RCX

main [
  sensor s2 on 2
  var counter = 0
  output motorA on 1
  output motorB on 2
  output motorC on 3
  forward [motorA motorB motorC]
  power [motorA motorB motorC] 7
  s2 is light as percent
  start progTask
  wait 10
  forever []
]

task progTask [
  forward [motorA motorC]
  forever [
    on [motorA motorC]
    while s2 is 44..100 [
    ]
    clear counter
    repeat (random 59+1) [
      counter += 1
    ]
    if counter is 1..10 [
    ][
      if counter is 11..20 [
        forward motorA
        backward motorC
        on [motorA motorC] for 80
        forward [motorA motorC]
      ][
        if counter is 21..30 [
          forward motorA
          backward motorC
          on [motorA motorC] for 160
          forward [motorA motorC]
        ][
          if counter is 31..40 [
            forward motorA
            backward motorC
            on [motorA motorC] for 240
            forward [motorA motorC]
          ][
            if counter is 41..50 [
              forward motorA
              backward motorC
              on [motorA motorC] for 320
              forward [motorA motorC]
            ][
              forward motorA
              backward motorC
              on [motorA motorC] for 400
              forward [motorA motorC]
            ]
          ]
        ]
      ]
    ]
  ]
]

which is ofcourse just an example (it's the starting condition for a beetle, with all chances equal to 10). If you load it into your Mindstorm CD rcx workbench you'll see that it looks like this:

source loaded in the CD

and you can download it to the Mindstorm as you would with any other program. Kinda neat, isn't it? Now all you need to do is built a robot to download the code into, such as the one on top of this screen, and place it on one of the maps you got with your Mindstorm. If you're eager to start click here to download the most successful beetle of one of my runs:

beetle in action

Here's some small building details of the gearing and the light sensor:

For those of you interested in the gene of the most successful beetle a small tabel:

direction    chance
                original        best performer

forward         10              0
right           10              0
sharp right     10              11
reverse         10              0
sharp left      10              0
left            10              9

Quite interesting, isn't it. Mind you, this robot is still able to leave the track when after a turn the lightsensor happens to be outside the track (while the robot itself is still on the inside). This can be overcome by mounting the lightsensor closer to the robot turning point (or the main axle if you like) or by making the black lines surrounding the track wider.

(1) If you're Dutch I'd recommend Kees Vuik's book 'Vuiks verhandelingen over computers, wetenschap en denken' (ISBN 902743123x, 1992) which describes this subject and many others.