Ass 3

Evolving Wall-Following Behavior for an Autonomous Mobile Robot

Submitted:

Lior Becker – 052690849, liorbecker@gmail.com , http://liorbecker.googlepages.com , http://liorbecker.googlepages.com/

Arie Ohana ID: 33771635 ohanaar

Problem description:

The definition of the problem is given in Koza's paper.

In brief, we use genetic programming to solve the problem of evolving a robot to follow a wall, in a given room.

Process of work:

The problem is solved using a GP.

Gene:

A Scheme program that is represented by a Tree (Like a compiler AST).

(a) Terminals: {SS0…SS11, EDG, SS, MSD}

· EDG == 2.3, SS ==minimum of all sensors, MSD == 2.0.

· SS0..SS11 are the sensors in a 30 degree interval, and each returns the distance to the first intersected wall.

(b) Functions: {PLUS, IFLTE, PROGN2, TL, TR, MB, MF}

· All the functions are taken from the article, except PLUS that takes 2 arguments and return their sum.

· TL, TR, MB, MF – moves the robot and returns the minimum of SS2 and SS3.

· IFLTE - equals to "if less then equal then else".

· PROGN2 takes 2 arguments evaluates both of them and returns the second.

· All the functions that make the robot move take one time step.

Fitness function:

The fitness function is the number of tiles (out of 56) that the robot move through them.

Each robot has 400 time steps to simulate, and if there is no change from the last evaluation we will stop the evaluation loop.

Selection method:

Fitness proportion function, using roulette wheel sampling.

Population size = 500.

Num of generations = 51.

Crossover:

Pc = 0.9.

The cross over is done between sub trees, the sub tree is picked randomly.

Mutation:

Pm = 0.01.

In our case the mutation objective is to reduce tree size.

It will pick a sub tree and replace it with a new sub tree of depth 1.

Steps / Process:

1. Initial population calculated randomly, all the trees are complete in depth of 2.

2. Fitness calculation.

3. Selection.

4. Crossover and mutation.

5. Moving to next generation.

· in the process we save the following data:

Plots of best fitness versus time.

Five LISP programs that we evolved using GP (along with their fitness values):

A program from Generation 0, 10, 20, 30, 51(the best program found).

Along with each of the five programs we submit an image of the robot's trajectory.

This will show how the robot evolves in time to solve the problem.

Results:

Generation 1

Best individual Fitness: 21

(IFLTE(PROGN2 TL S09 )(IFLTE MF S05 S09 TR )(PLUS TR MSD )(IFLTE S10 S01 S05 S00 ))

Generation 10

Best individual Fitness: 47

(IFLTE(PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 )(IFLTE MF (PLUS S11 S04 ) S09 TR )(PLUS TR MSD )(PROGN2 S05 S03 ))

Generation 30

Best individual Fitness: 54

(IFLTE(PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 )(IFLTE MF (PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 )(IFLTE(PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 ) EDG (IFLTE S11 EDG TL MSD ) S11 ) TR )(IFLTE MF (PLUS S11 S04 ) S09 (PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 )) TR )

Generation 40

Best individual Fitness: 56

(IFLTE(IFLTE(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S05 EDG TR )(IFLTE MF (IFLTE(PROGN2(PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 )(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 )) S09 )(IFLTE(IFLTE MF S05 S09 TR )(PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 ) S09 TR )(IFLTE MF S05 S09 TR ) TR ) S09 TR )(PROGN2(PLUS(PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 ) EDG )(PROGN2(IFLTE(PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 ) EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 ))(IFLTE(PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD )(IFLTE MF S05 S09 TR ))(IFLTE MF (PROGN2(IFLTE EDG EDG (IFLTE S11 EDG TL MSD ) S11 ) S09 ) S09 TR )) EDG (IFLTE S11 EDG TL MSD ) S11 ))

Generation 51

Best individual Fitness: 56

Generation	Fitness
1	21
10	47
30	54
40	56
51	56

We can see the progress of the GP Fitness during the generations

Generation 1 visualization of the path

Fitness 21

Generation 10 visualization of the path

Fitness 47

Generation 30 visualization of the path

Fitness 54

Generation 40 visualization of the path

Fitness 56

Generation 51 visualization of the path

Fitness 56

Conclusions:

1. One of the problems in GP is that the Tree – Code have the tendency to grow throughout the generations.

We tried to moderate the problem using a mutation function (with probability of Pm=0.01), we replaced a random sub tree with a new tree of size 1.

This should cause the tree – code to reduce its size.

2. The Fitness function doesn't take into account the length of the path, and number of time steps needed to complete "collecting" all the tiles.

So we tried to replace the Fitness function with a new Function.

F1 = (Tiles stepped on) + factor /(Time steps) + factor /(Wall collisions).

Where:

· Tiles stepped on - the number of Tiles that the robot "picked" during the run.

· Time steps – the number of time steps that took the robot to complete the mission (max 400)

· Wall collisions – the number of walls that the robot collided during the run.

The new fitness function had no effect on the evolution progression, so we decided to drop the idea.

· You can also see the despite the fact that the robot didn't take the above data it found a very short way to solve the problem.

3. You can see clearly the increasing value of the average and best fitness during the generations.

It confirms the correctness of using GP to solve this problem.

4. In the simulated plot of generation 30, 40, 51 you can see an interesting behavior at the beginning of the robot path, it does some unexplained loops.

We witnessed the same behavior in Koza's article.

We can't explain the behavior.

5. We wanted to know if the robot is capable of walking near walls in some other rooms.

We tested the function on 3 more rooms and the results where disappointing, the robot failed to achieve the goal.

Code

Code folder

LIVE SIMULATION

IMPORTANT !!!!!

You can view a live simulation of the our robot:

Download the robo_plot.m and path.txt place them both in the same directory (work directory of Matlab).

Activate Matlab and press "robo_plot".