Problem description

The problem is controlling an autonomous mobile robot to perform the task of following the walls of an irregular room. The robot is capable of executing the following five primitive motor functions: moving forward by a constant distance, moving backward by a constant distance, turning right by 30 degrees, turning left by 30 degrees, and stopping. The robot has 12 sonar sensors that report the distance to the nearest wall. Each sonar sensor covers a 30-degree sector around the robot.

We need to use Genetic Programming to find a program that will control the robot and make it move along the walls.

Problem definition data:

· The edging distance (EDG) representing the preferred distance between the robot and the wall is 2.3

· The minimum safe distance (MSD) between the robot and the wall is 2 feet.

· The room is a 30x30 square with two protrusions of 7 feet by 4.

· Population size is 500, and number of generations (G) is 51. We may change these values if they don't work.

Process of work

We started by reading the article of Koza. Then we tried to just write the code for the genetic programming using scheme.

We defined the following according to koza's article:

The set of terminals:

· 12 distance sensors – S1...S12

· EDG – 2.3.

· MSD – 2

· SS – Shortest sensor, defines the minimum distance sensor.

The set of functions:

· TR - Turn the robot 30° right

· TL - Turn the robot 30° left

· MF - Move the robot forward by 1

· MB - Move the robot backward by 1.3

· PROGN2 – This function receives two arguments, evaluates both of its arguments, in order, and returns the result of the second evaluation.

· IFLTE - If-less-then-or-equal. This function receives four arguments, if the first argument is less than or equal the value of the second argument, the third argument is evaluated and returned. Otherwise, the fourth argument is evaluated and returned.

Going on from there was not as easy as we expected. We have made several attempts to create a genetic process that creates programs built of these elements. This was not easy especially because we had no experience at all in genetic programming, and we were a bit lost. After going through the class material a little bit, we decided to make our first attempt on genetic programming with something simpler and more familiar from class- evaluating a simple 1 parameter function, starting with X+1.

The terminal set: X

The function set: +, -, *, new-dev, IFLTE

*New-dev = divides one number with another, if the divisor is zero return 1.

We started the genetic programming with writing a function to create a random program from the terminals and functions. The function created a Full tree genome with a given depth.

Now we wanted to determine the fitness of such genomes. Our fitness function compared the results of a given program with the program (+ X 1). The input values for x were in the range (-1, 1) with constant intervals, and the fitness given is the sum of differences in the results. Hence the lower fitness is better and the best fitness is zero.

After having genomes and fitness function we could finally build the select, mutate & cross over functions:

Mutate – receives a genome (tree), and returns a copy of it after replacing a random node and its sub tree with a new random sub tree. The random sub tree is created by the tree creator function.

Cross over – receives 2 genomes (trees), selects a random node (sub tree) on each tree, and returns a copy of them after replacing the two nodes with each other.

Select – selects a genome from the population, using fitness proportionate selection.

This was not enough, to create the new generation we had to make another function that implements the following flowchart:

This process went well and our program easily got to the correct solution.

Reference to the X+1 code.

Now we were ready to go on with the robot problem.

We understood that we have to build the whole background infrastructure of the room and the robot's movement and sensors. We started defining a room wall using two points – start and end. Later we found it easier to rely on the assumption that all walls are vertical or horizontal, splitting them to these 2 groups.

The robot movement was easy to implement – just changing it's (x, y) position. For the turns we just changed its direction.

As for the sensors, we had to determine the distance from the closest wall on some specific direction. We used geometry functions to do that.

For the Fitness Points list we selected points on a line distant EDG/2 from the wall. The interval between the points is EDG. A robot is close to a fit Point if both the x values difference and the y values difference are smaller then EDG/2. Thus a robot close to a fit point is close to a wall and not close to an adjacent fit point.

To give fitness to a robot program we had to calculate its travel route. We decided that the program will run in loops until the robot made 400 movement functions (TL, TR, MF, MB), as defined in Koza's article.

Great, Now we used the selection, cross over and mutation functions we already written for the X+1 problem. It did not work because the movement functions (TL, TR, MF, MB) do not receive any parameters thus do not create a sub tree. Also they do not return any value. To fix the first problem we moved these functions to the terminals list with evaluation parenthesis. To fix the second problem we changed the functions to return the S0 sensor current value (for MB function we returned current S6 sensor). Another fix we made was to restrict movement of the robot if the distance from the wall on that direction is less then MSD (i.e. not safe to move).

Now the selection, cross over and mutation functions worked, but for some reason we did not reach good results- on the best cases the robot just went into a wall. We decided to give fitness also to robot programs which did not reach a fit Point.

We changed the fitness function as follows:

· If the travel routed close to fit points it gets double the number of fit points it routed close to.(fit>=2)

· If the travel did not route close to fit points it gets its distance from the start divided by the route's length. (fit<=1.3)

This got the programs to evolve to reach the wall, but still for some reason we did not get much better results then robots just banging into the wall. We thought we have some mistake in the route evaluation so we decided to try and write a good robot program manually and see if it gets good fitness. We did not make it! After a lot of attempts we found the problem- the evaluation function was applicative evaluation (not lazy). This gave the function IFLTE a whole new meaning as it evaluated all the arguments it received and hence all the movement functions were executed anyway. Apparently this new IFLTE is not good enough to create a good program for the robot to follow the room's walls.

This applicative evaluation problem was not found on the X+1 problem because we did not use set! action. The arguments of IFLTE were all evaluated but it did not make any side effects.

We solved that problem by using define-syntax to make the IFLTE function lazy.

Somewhere along the way we also added 2 grow tree creators. The first one randomly selects a function/terminal for each sub-tree. The second one first selects the node type (Terminal/Function) and afterwards selects an appropriate sub-tree/node.

The tree creation function for new population and for mutate is a random selection from the three tree creators we now have.

After we saw the algorithm works well we added savings of all generation results to files, and used an external program (which we wrote!) to view each generation best travel.

Reference to genetic robot scheme code

Reference to the graphics program we wrote in c++

The experiments:

We started with 50 generations of a population sized 500. After one generation the best genome had a 72 fitness (36 fit points), and the second generation gave us 102 fitness where the maximum fitness is 120 (60 fit points). We understood that this big population finds good genomes very fast and the evolutionary process will not be seen in the analyzing graphs.

We decided to simultaneously use a smaller population (size 100) with 70 generations hoping it work faster and also show better the evolutionary process. We are giving here the results of both experiments.

Results:

The first experiment:

Population: 500

Number of generations: 51

Probabilities:

Mutate – 2/17

Cross over – 10/17

Selection – 5/17

Tree creation maximum depth: 3

Plot of best and average fitness versus time:

Max Fit	Max Avg
120	104

Generation	Best fitness	Best genome
0	22	(iflte (iflte (mf) edg s01 s12) (iflte s01 edg s06 edg) (progn2 (tl) s02) (iflte msd ss s01 s05))
2	102	(iflte (iflte s03 s09 s02 s12) (iflte (mf) edg s05 (tr)) (progn2 (tl) msd) (iflte s01 s03 (mf) edg))
5	114	(iflte (iflte edg s07 (mb) (tr)) (progn2 edg (mb)) (iflte s06 (mf) s01 s09) (iflte (iflte ss edg s07 s10) (iflte s02 s06 edg edg) (progn2 s07 s08) (iflte (progn2 s12 s02) (iflte (tl) s04 s06 s03) (progn2 s06 s09) (progn2 s01 s01))))
8	118	(iflte (iflte edg s07 (mb) (tr)) (progn2 edg (mb)) s12 (iflte s07 (iflte s02 s06 edg edg) (progn2 s07 s08) (iflte (progn2 s12 s02) (iflte (tl) s04 s06 s03) s12 (progn2 s01 s01))))
42	120	(iflte (iflte edg s07 (mb) (tr)) edg (iflte s06 (mf) (progn2 (iflte ss (iflte s01 s07 (iflte (iflte (tl) s04 s06 (progn2 (iflte s09 ss (mb) s03) s10)) s12 (progn2 (iflte (mb) s08 s03 (iflte (mb) s12 s05 s12)) msd) s01) (mb)) s03 (progn2 (iflte s01 (tr) s03 (progn2 (progn2 (mf) (mf)) (iflte ss (tr) s08 (mf)))) (iflte s12 s10 s04 (tl)))) msd) s09) (iflte s07 (iflte s03 s06 edg edg) (progn2 s07 msd) (iflte (progn2 (iflte (progn2 s03 ss) edg (iflte s01 s04 s07 s02) (iflte (tr) s10 s04 edg)) s02) (iflte (tl) (iflte (progn2 s01 s04) (iflte s11 s08 edg s11) (progn2 s03 (progn2 (progn2 s11 msd) (progn2 s04 s09))) (progn2 s04 ss)) s02 s09) s12 (progn2 s12 s01))))

The robot route pictures:

(note: you can view all of the generation's info on the software)

Press next/prev or change the edit box number to see the routes.

The Second experiment:

Population: 100

Number of generations: 70

Probabilities:

Mutate – 2/17

Cross over – 10/17

Selection – 5/17

Tree creation maximum depth: 3

Plot of best and average fitness versus time:

Max Fit	Max Avg
120	106.1

Generation	Best fitness	Best genome
0	46	(iflte (iflte s09 (tr) s06 ss) (progn2 (mb) edg) (iflte s04 s09 ss msd) (iflte s01 (tl) s12 (mb)))
3	84	(iflte (progn2 s08 (tl)) (iflte (mf) (mf) s12 (tr)) (iflte (mf) (mf) s12 (tr)) (mf))
18	108	(iflte (progn2 s05 (tl)) (iflte (mf) (mf) ss (tr)) (iflte (mf) (iflte (iflte (mf) s06 s11 s03) (progn2 (tr) s07) (iflte (tl) (iflte (mf) (iflte edg edg (mf) s05) s12 (tr)) s03 s04) (iflte (iflte (iflte s11 s09 ss s03) (progn2 (tr) (progn2 (iflte s03 edg s12 msd) (mf))) (iflte s11 (iflte (mf) (mf) s12 (tr)) s08 s05) (progn2 (tr) (tr))) (tr) s05 s01)) s12 (tr)) (iflte s03 edg (iflte s03 (iflte (progn2 s08 (tl)) (iflte (mf) (mf) ss (tr)) (iflte (mf) (iflte (iflte s04 s06 s11 s03) (progn2 (tr) s07) (iflte (tl) (mb) (tl) s04) (iflte s12 (iflte (progn2 edg msd) edg (progn2 s12 s06) (iflte s12 s05 s06 s05)) s05 s01)) s12 (tr)) (iflte s03 edg (iflte s03 edg s12 (progn2 (iflte (mf) (iflte edg edg s05 (mf)) s04 (mf)) (tl))) edg)) s05 s05) edg))
41	116	(iflte (progn2 s05 (tl)) (iflte (mf) (mf) ss (tr)) (iflte (mf) (iflte (iflte (mf) s06 s11 s03) (progn2 (tr) s07) (iflte (mf) (iflte (iflte s11 s06 edg (iflte (mf) (iflte edg (iflte (iflte ss s02 s05 s08) (iflte s04 s09 s03 (mf)) (progn2 s03 s04) (iflte ss (mb) s04 s01)) (mf) s05) edg (tr))) (progn2 (tr) s07) (iflte (tl) (iflte (mf) (iflte edg edg (mf) s05) s12 (tr)) s03 s04) (iflte (iflte (iflte s11 s09 ss s03) (progn2 (tr) (progn2 (iflte s03 edg s12 s03) (mf))) (iflte s11 (iflte (mf) (mf) s12 (tr)) s08 s05) (progn2 (iflte edg edg s05 (mf)) (tr))) (tr) s05 s01)) s12 (tr)) (iflte (iflte (iflte s11 s09 ss s03) (progn2 (tr) s04) (tl) s03) (tr) s05 s01)) s12 (tr)) (iflte s03 edg (iflte s03 (iflte (progn2 s08 (tl)) (iflte (progn2 (progn2 msd s07) (iflte s07 (mf) (mb) (tl))) (mf) ss (tr)) (iflte (mf) (iflte (iflte s04 s06 s11 s03) (progn2 (tr) s07) (iflte edg (mb) (tl) s04) (iflte s12 (iflte (progn2 s08 msd) edg (progn2 s12 s06) (iflte s12 s05 s06 s05)) s05 s01)) s12 s03) (iflte s05 edg (iflte s03 s05 s12 (progn2 (iflte (mf) (iflte edg edg s05 (mf)) s04 (mf)) (tl))) edg)) (iflte (progn2 s04 s02) (progn2 (mf) s07) (iflte s04 ss edg (iflte s08 (mf) s04 s12)) (iflte (tl) s08 s07 ss)) s05) edg))
57	120	(iflte (progn2 s05 (tl)) (iflte (mf) (mf) ss (tr)) (iflte (mf) (iflte (iflte (mf) s06 s11 s03) (progn2 (tr) s07) (iflte (mf) (iflte (iflte (mf) s06 edg (iflte (mf) (iflte edg (iflte (iflte ss s02 s05 s08) (iflte s04 s09 s03 (mf)) (progn2 s03 s04) (iflte ss (mb) s04 s01)) (mf) s05) edg (tr))) (progn2 (tr) s07) (iflte (tl) (iflte (mf) (iflte edg edg (mf) s05) s12 (tr)) s03 s12) (iflte (iflte (iflte s11 s09 ss s03) (progn2 s10 (iflte ss s02 s05 s08)) (iflte s11 (iflte (mf) (mf) s12 (tr)) s08 s05) (progn2 (tr) (tr))) (tr) s05 s01)) s12 (tr)) (iflte (iflte (iflte s11 s09 ss s03) (progn2 (tr) s04) (tl) s03) (tr) s05 s01)) s12 (tr)) (iflte s03 edg (iflte edg (iflte (progn2 s08 (tl)) (iflte (progn2 (progn2 msd s07) (iflte s07 (mf) (mf) (tl))) (mf) ss (tr)) (iflte (mf) (iflte (iflte s04 s06 s11 s03) (progn2 (tr) s07) (iflte edg (mb) (tl) s04) (iflte s12 (iflte (progn2 s08 msd) edg (progn2 s12 msd) (iflte s12 s05 (tr) s05)) s11 edg)) s12 (iflte s08 s10 msd edg)) (iflte s05 ss (mf) edg)) s05 s05) edg))

The robot route pictures:

(note: you can view all of the generation's info on the software)

Reference to all results data sheets

Conclusions:

1. Genetic programming is great! We love GP!

2. Genetic programming is exhausting.

3. The Autonomous Mobile Robot problem can be solved using GP.

4. Shaked is terrible in graphics

5. Meltzer is just terrible

6. Scheme is a good language for developing genetic programming - A program is
also an object. Applicative evaluation is problematic, especially when we use functions with side effect like set! , because then all function calls in the expression are evaluated either way. This problem can be solved though.

7. A big limitation in genetic programming is keeping a unified domain for terminals, functions arguments and functions return values. This is what caused us use the set! Function in the first place.

8. We did not use the suggested scan conversion line algorithm as recommended. Instead we used basic geometry evaluations. We think that this solution is not only much more accurate but it was also easier to implement.

Bonus

We allowed vary numbers of sensors. The number of sensors is also the number of directions the robot can move. Following are the results for 4 sensors and 24 sensors. We used population of size 100 over 50 generations.

Reference to results

4 sensors:

Max Fit	Max Avg
120	108.96

Best genome, at generation 49:

Click here to download the software for all generations.

24 sensors:

Max Fit	Max Avg
102	65.34

Best genome, at generation 49:

Click here to download the software for all generations.

We can see that when the number of sensors decrease the genetic programming is better. We think this is because it simplifies the robot program – less terminals and directions. Apparently when Simple functions are enough to solve the problem it is better not to overhead with more complexity.

Reference to all results data sheets

Glossary:

Grow tree genome - An individual created with this method may be a tree of any depth up to a specified maximum, m.

1. Starting from the root of the tree every node is randomly chosen as either a function or terminal.

2. If the node is a terminal, a random terminal is chosen.

3. If the node is a function, a random function is chosen, and that node is given a number of children equal to the arity (number of arguments) of the function. For every one of the function’s children the algorithm starts again, unless the child is at depth m, in which case the child is made a randomly selected terminal.

This method does not guarantee individuals of a certain depth (although

they will be no deeper than m). Instead it provides a range of structures

throughout the population.

This method does not guarantee individuals of a certain depth (although they will be no deeper than m). Instead it provides a range of structures throughout the population.

The method may produce individuals containing only one (terminal) node. Such individuals are quickly bred out if the problem is non-trivial, and so are not really much value.

Full Tree Genome - The full method is very similar to the grow method except the terminals are guaranteed to be a certain depth. This guarantee does not specify the number of nodes in an individual. This method requires a final depth, d.

1. Every node, starting from the root, with a depth less than d, is made a randomly selected function. If the node has a depth equal to d, the node is made a randomly selected terminal.

2. All functions have a number (equal to the arity of the function) of child nodes appended, and the algorithm starts again. Thus, only if d is specified as one, could this method produce a one-node tree.