Programming a Robot using Genetic Programing

Target: programming a robot to walk along a room walls using Genetic Programming.

By: Aviv Ron (ronav@cs.bgu.ac.il) (www.cs.bgu.ac.il/~ronav)

The Room:

a 27.6 x 27.6 Feet room with two 4.6 x 6.9 Feet “blimps” as seen in diagram 1.

The Robot:

A simple Robot consisting of the next elements:

1. 12 sensors {S0, S1,…, S11} that evaluate the distance between the robot and the wall in their direction. The sensors are 30 degrees away from each other as shown in diagram 2.
2. The ability to move forward or backward a given distance.
3. The ability to turn left or right 30 degrees each time.

The Program:

the Program is a Scheme expression (AKA Sexpr).

Function set:

1. (MF) – tells the robot to move forward (its facing direction) 1 foot and returns minimum[S2,S4].
   The move will be executed only if the 5 sensors facing the forward movement {S1, S2,…,S5} are bigger than 1.1 feet.
2. (MB) – tells the robot to move backward 1 foot and returns minimum[S2,S4].
   the move will be executed only if the 5 sensors facing the backward movement {S7, S8,…,S11} are bigger than 1.1 feet.
3. (TR) – tells the robot to turn right 30 degrees and returns minimum[S2,S4].
4. (TL) – tells the robot to turn left 30 degrees and returns minimum[S2,S4].
5. (IFLTE A B C D) – expects four arguments. If A<=B returns the evaluation of C else the evaluation of D.
6. (PROGN2 A B) – evaluates A and returns the evaluation of B.
7. (PROGN3 A B C) – evaluates A and B and returns the evaluation of C.

Terminal set:

1. S0 to S11 – evaluate to the value of the sensors of the robot at the given time step.
2. SS – is minimum[S0, S1, …, S11]
3. EDG – evaluates to 2.3 (the legal distance from the walls that is accepted)
4. MSD – evaluates to 2 (minimum safe distance from wall)

Mutation:

Choose a random node in the Sexpr tree and replace the sub tree of which it is its root with a new random Sexpr.

Cross over:

Choose a random node in each of the Sexpr’s Tree’s and swap them.

Fitness:

The fitness assigned to a Program is the number of 2.3 x 2.3 bricks along the walls (as shown in diagram 1) that the root has stepped on during its walk. The walk is limited to 400 time steps were each execution of {MF,MB,TR,TL} counts as one time step.
We want to reach a fitness of 56.

Other Parameters:

• Population size – 1000.
• Crossover P – 0.7.
• Mutation P – 0.2.
• Tournament selection with tournament size 5.
• 60 generations
• The robot starts each walk from the middle of the room facing NORTH (0 degrees)
• The first generation of Programs are random, full Sexprs of depth 4.

The Application:

Written in Java. The robot and the room are simulated in Java. I built a Package of Objects simulating Scheme Expressions in Java so I won’t need to program the robot in Scheme. Each Sexpr from the Function set and Terminal set has an object representing it and evaluating to its value.
Here are links to:

§ Source code.

§ Executable jar.

§ Javadoc.

The Results:

A Program scoring 56 was found on generation 26! Here is the table of results and graph:

A simulation of the best programs from generations 0, 4, 5, 22 and 26 can be seen in this applet

Lets have a look at some of the best Programs:

Generation 0 best Program scored a fitness of 24:

(IFLTE (PROGN2 (IFLTE S4 (MB) (TL) (TR)) (PROGN2 (MF) S3)) (PROGN3 (IFLTE (TR) (MF) (MB) (MF)) (PROGN3 S10 SS (MF)) (PROGN3 (MF) S9 S0)) (PROGN3 (PROGN2 S1 S7) (PROGN2 MSD (MF)) (PROGN3 S11 (MB) (TL))) (PROGN2 (IFLTE SS (TR) S10 MSD) (IFLTE (TL) S6 S7 (MF))))

Generation 4 best Program scored a fitness of 37:

(IFLTE (PROGN3 (IFLTE (MB) (MB) (MB) (TR)) (PROGN2 S1 S6) (PROGN2 (TL) S7)) (IFLTE (PROGN3 (IFLTE S3 S11 EDG (MB)) (PROGN2 (MF) S3) (IFLTE S0 S3 S10 S5)) (PROGN2 MSD (TR)) (PROGN2 S5 (TR)) (PROGN3 S8 S11 S0)) S11 (IFLTE (MB) S0 S3 (MF)))

Generation 5 best Program scored a fitness of 49:

(PROGN2 (PROGN2 (MF) S3) (IFLTE (PROGN3 S6 (TR) MSD) (IFLTE (MF) (MF) S3 S3) S10 (PROGN3 (MB) (TL) (TL))))

Generation 22 best Program scored a fitness of 55:

(PROGN2 (PROGN2 (MF) (MF)) (IFLTE (PROGN3 S6 (TR) MSD) (IFLTE (MF) S3 S3 S3) (PROGN2 S0 (IFLTE (PROGN3 S6 (TR) MSD) (IFLTE (MF) (PROGN2 S6 MSD) S3 S3) S8 (PROGN3 (MB) (TL) (TL)))) (PROGN3 (MB) (TL) (TL))))

This program was missing just one square to hit the maximum fitness.

And the best Program was found on generation 26 scoring the maximum fitness 56:

(PROGN2 (PROGN2 (MF) S0) (IFLTE (PROGN3 (IFLTE (PROGN3 S6 (IFLTE (PROGN3 S6 (TR) MSD) (IFLTE (MF) EDG S3 S3) S3 (PROGN3 (MB) (TL) (TL))) MSD) (IFLTE S6 (MF) S3 S3) (PROGN2 S0 S3) (PROGN3 (MB) (TL) (TL))) (TR) MSD) (IFLTE (MF) (MF) S3 S3) (PROGN2 MSD (IFLTE (PROGN3 S6 (TR) MSD) (IFLTE (MF) (PROGN2 S6 MSD) S3 S3) S8 (PROGN3 (MB) (TL) (TL)))) (PROGN3 (MB) (TL) (TL))))

In the Hierarchical diagrams shown next we can see that the best program has evolved from the best program of generation 5 with fitness of 49 into the best program of generation 22 with fitness 55 to the best program scoring maximum fitness on generation 26.

Generation: 0

Fitness: 24

depth: 4

No similarity between Generation 0 to Generation 4 best programs

Generation: 4

Fitness: 37

depth: 5

No similarity between Generation 4 to Generation 5 best programs

Generation: 5

Fitness: 49

depth: 4

The next program from generation 22 evolved from the last one. The different nodes are highlighted in orange.

Generation: 22

Fitness: 55

depth: 6

The next program from generation 26 evolved from the last one. The different nodes are highlighted in orange.

Generation: 26

Fitness: 56

depth: 7

We can see here GP working at its best. A good base program was found on generation 5 and the GP managed to evolve it into a perfect program after 21 generations.

Diagram 1: The room’s diameters:

Diagram 2: the robots sensors: