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