2110742 Evolutionary Computation 

second semeter 2005

Important date

Final exam submission is on  Wednesday 15 March 2006,  1pm  at  the class room on 19th floor, Eng Build 4.  We will discuss the final exam then, class duration 1 hour.

syllabus
GP system to evolve robot programs

Explanation of the robot arm experiment
update source code  (work in Windows XP)  24 Feb 2006

update source code   work for all examples    1 Mar 2006
update source code    with C-space viewer     3 Mar 2006
update  C-space viewer  (LOGO) bit.lgo        7 Mar 2006

Problems

I have found some problems that are distinguished from others.  Many problems are easy: env0, env1, env2, env3, env8 use this parameters:

pop 200
cross 100
muadd 50
muext 50
nbest 20
time 200
gen 10

env9 and env10 are more difficult and require larger pop size.

pop 400
cross 200
muadd 100
muext 100
nbest 20
time 400
gen 10

env11 is most difficult

pop 800
cross 400
muadd 200
muext 200
nbest 20
time 400
gen 10

I have created two problems, env15, env16 that look similar but GP cannot solve env16.  env15 uses the set of parameter pop 400, however, GP fails to solve env16 even I expand parameter to very large (such as pop 1600).

Try them yourselves.

// pop 200, nbest 20, cross 100, mu 50+50, time 200, gen 10
void env0(void){
  clearimage(BACKGR);
  fillbox(180,60,30,20,OBSTAC);
  maketarget(140,20,10);
}

void env1(void){
  clearimage(BACKGR);
  fillbox(115,53,60,20,OBSTAC);
  maketarget(116,33,10);
}

void env2(void){
  clearimage(BACKGR);
  fillbox(37,57,45,22,OBSTAC);
  fillbox(137,52,60,20,OBSTAC);
  maketarget(75,35,10);
}

void env3(void){
  clearimage(BACKGR);
  fillbox(35,60,50,20,OBSTAC);
  fillbox(140,60,60,20,OBSTAC);
  maketarget(75,30,10);
}

void env8(void){
  fillbox(35,60,50,20,OBSTAC);
  fillbox(140,60,60,20,OBSTAC);
  maketarget(130,20,10);
}

// pop 400, nbest 20, cross 200, mu 100+100, time 400, gen 10
void env9(void){
  fillbox(20,50,50,20,OBSTAC);
  fillbox(115,50,15,15,OBSTAC);
  fillbox(170,50,60,20,OBSTAC);
  maketarget(120,30,10);
}

// pop 400, nbest 20, cross 200, mu 100+100, time 400, gen 10
void env10(void){
  fillbox(55,60,50,20,OBSTAC);
  fillbox(160,60,20,50,OBSTAC);
  maketarget(130,40,10);
}

// pop 800, nbest 20, cross 400, mu 200+200, time 400, gen 10
void env11(void){
  fillbox(75,60,50,20,OBSTAC);
  fillbox(160,60,20,50,OBSTAC);
  maketarget(130,40,10);
}

// pop 400, nbest 10, cross 200, mu 100+100, time 400, gen 10
// it is similar to env16 except that box1 is longer to prevent local min
void env15(void){
  fillbox(95,60,60,20,OBSTAC);
  fillbox(40,60,20,50,OBSTAC);
  maketarget(90,35,10);
}
// fail !  pop 800, nbest 20, cross 400, mu 200+200, time 400, gen 10
void env16(void){
  fillbox(95,60,30,20,OBSTAC);
  fillbox(40,60,20,50,OBSTAC);
  maketarget(90,35,10);
}

Explanation of the robot arm experiment

I simplified the robot arm simulator and increased the resolution of joint angles (2 degrees per step).  Each joint has a range 180 degrees.  GP found solutions to all environments (env0..env9, except env4 which has not been tried).

How to set parameters

for env0..8  (except env4)

pop 200
cross 100
muadd 50
muex 50
elite (nbest)  20
max generation 10
timelimit 200

for env9

pop 400
cross 200
muadd 100
muex  100
elite (nbest) 20
max generation 10
timelimit 400

If you increase population size beyond 400, you may have to increase MAXCELL (in gp.h).  Each node consumes 5 cells.  See pgm.c for memory management methods.

I generate a lookup table for ishit().  It is stored in hitq[][][].  The subsequent generation evolution is much faster.

To run the experiment:

c:> vreach
gen 1 best fit -497 av fit -1562 av len 60
gen 2 best fit -235 av fit -528 av len 59
gen 3 best fit -235 av fit -398 av len 62
gen 4 best fit -160 av fit -217 av len 63
gen 5 best fit -152 av fit -176 av len 69
gen 6 best fit -149 av fit -154 av len 76
gen 7 best fit -32 av fit -139 av len 72
gen 8 best fit -30 av fit -53 av len 76
gen 9 best fit -25 av fit -28 av len 82
pgm 0 len 75 fit -24 time 93 success 1 dist 2442
: nmnhnhlnigimlbcnmfhgkcklchghilabcmendbdmkekgjicnnckglnfneclfhkhibckecakjjdh
pgm 1 len 95 fit -25 time 82 success 1 dist 2311
:

lnmnhnhlgmlmjgcaanmfhgkcklchghnlgjmdkcaakglabcmlddbendbdmkekgjicnnckglnfneclf

hkhibckecakjjdhihf
pgm 2 len 76 fit -25 time 86 success 1 dist 2303
...

At the final generation (gen 10), the nbest programs are displayed with their statistics:

len is the size of the program as the number of nodes
fit is the fitness value (near to zero is better)
time is the number of loop in executing a program
sucess is 1 when the robot reached the target
dist is the accumulated distance (smaller is better)

You can redirect the output to a file

c:> vreach > out.txt

then you choose one program and store it in a file (say prog1.txt)

nmnhnhlnigimlbcnmfhgkcklchghilabcmendbdmkekgjicnnckglnfneclfhkhibckecakjjdh

To see the movie of this program, generate a trace of coordinate by executing:

c:> vreach -t < prog1.txt > tr1.txt

tr1.txt look like this:

107 128 173 117 197 117
106 130 173 121 196 121
106 130 172 119 196 119
106 130 172 119 195 119
106 130 172 116 196 116
...
0
pgm 0 finishF 1 seeF 1 fit -24 clock 93 len 75 dist 2442

and see the movie of this trace using plot.lgo. It is a Logo program that read the trace file and display the movie.

in Logo, file > load > (your directory) plot.lgo.  Edit using "Edall" and edit the function "to rdpoint"  to use the correct environment "envX".

to rdpoint
  openread "tr1.txt
  setread "tr1.txt
  cs
  ht
  box 0 0 250 200
  env8               <=====
...

do "save and exit" with the editor, file > save and exit.  Then execute the program using the command line window (at the bottom), type

rdpoint

and you will see the movie.

To install Logo    download this file and execute it

Msw Logo version 6.5a    

C-space viewer

I have written a c-space viewer, "bit.lgo".  The c-space map is generated from "vreach" by:

c:> vreach -m > env1.bit

the "env1.bit" is the c-space map.  It is viewed in Logo by executing "rdbit".  To change the map name, edit the function "to rdbit" in Logo.

logo > rdbit

The "rdbit" required two files: the c-space map file, "envX.bit", and the trace file, "tr1.txt".

The trace of joint angle is seen as a movie in c-space map.  I have modified the trace file to output joint angles as the last three elements in each line of the trace.  To generate a trace:

c:> vreach -t < prog1.txt > tr1.txt

C-space map

To map 3D joint space into 2D, I "compress" the wrist angle into 3 regions and use 3 colours to display it.  The wrist angle ranges -90..0..90 degrees.  It is divided into -90..-30, -30..30, 30..90 or left-side, middle, and right-side.

It is shown in four colours:

blue  for collision free region
red   for collision on left-side
yellow for collision on middle
green  for collision on right-side

blue means there is no collision for all wrist angles

When you watch the trace in c-space, remember that the trajectory may intersect the non-blue region because the wrist is in the different angle than the angle that causes collision.  For example, in env1.bit, a trace cuts the green-region, this means that the wrist angle is not in the right-side.

The "bit.lgo" also contains everything in "plot.lgo" so you can view trajectory in Cartesian space as before by executing "rdpoint".

logo > rdpoint

You can change the speed of movie by editing the "wait 2" in the "rdbit" and "rdpoint".  The unit is 1/60 sec.  Delete it will achieve the fastest speed.

P. Chongstitvatana

last update 7 March 2006