Файл: Embedded Robotics (Thomas Braunl, 2 ed, 2006).pdf

21 Genetic Programming

+

Figure 21.1: Tree structure and evaluation of S-expression

We deal only with integer data values. Our Lisp subset contains pre-defined constants zero, low, and high, and allows the generation of other integer constants by using the function (INC v). Information from the robot’s vision sensor can be obtained by calling obj_size or obj_pos. An evaluation of any of these two atoms will implicitly grab a new image from the camera and then call the color object detection procedure.

There are four atoms psd_aaa for measuring the distance between the robot and the nearest obstacle to the left, right, front, and back. Evaluating any of these atoms activates a measurement of the corresponding PSD (position sensitive device) sensor. These sensors are very useful for obstacle avoidance, wall-following, detecting other robots, etc.

There are four movement atoms remaining. Two for driving (forward and backward), and two for turning (left and right). When one of these is evaluated, the robot will drive (or turn, respectively) by a small fixed amount.

Finally, there are three program constructs for selection, iteration, and sequence. An “if-then-else” S-expression allows branching. Since we do not provide explicit relations, for example like (< 3 7), the comparison operator “less” is a fixed part of the if-statement. The S-expression contains two integer values for the comparison, and two statements for the “then” and “else” branch. Similarly, the while-loop has a fixed “less” comparison operator as loop condition. The iteration continues while the first integer value is less than the second. The two integer arguments are followed by the iteration statement itself.

These are all constructs, atoms, and S-expression lists allowed in our Lisp subset. Although more constructs might facilitate programming, it might make evolution more complex and would therefore require much more time to evolve useful solutions.

Although Lisp is an untyped language, we are only interested in valid S- expressions. Our S-expressions have placeholders for either integer values or statements. So during genetic processing, only integers may be put into integer slots and only statements may be put into statement slots. For example, the first two entries following the keyword in a WHILE_LESS-list must be integer values, but the third entry must be a statement. An integer value can be either

310

21 Genetic Programming

We implemented the Lisp interpreter as a recursive C program (Lisp purists would have implemented it in Lisp) that is executed by the EyeSim simulator. Program 21.1 shows an extract of the main Lisp decoding routine.

Program 21.1: Lisp interpreter in C

1int compute(Node n)

2{ int ret, return_val1, return_val2;

3...

4CAMGetColFrame (&img, 0);

5if (DEBUG) LCDPutColorGraphic(&img);

6ret = -1; /* no return value */

7

8switch(n->symbol) {

9case PROGN2:

10compute(n->children[0]);

11compute(n->children[1]);

12break;

13

14case IF_LESS:

15return_val1 = compute(n->children[0]);

16return_val2 = compute(n->children[1]);

17if (return_val1 <= return_val2) compute(n->children[2]);

21case WHILE_LESS:

22do {

23return_val1 = compute(n->children[0]);

24return_val2 = compute(n->children[1]);

25if (return_val1 <= return_val2) compute(n->children[2]);

26} while (return_val1 <= return_val2);

27break;

28

29case turn_left: turn_left(&vwhandle);

30break;

31case turn_right: turn_right(&vwhandle);

32break;

33...

34case obj_size: ColSearch2 (img, RED_HUE, 10, &pos, &ret);

35break;

36case obj_pos: ColSearch2 (img, RED_HUE, 10, &ret, &val);

37break;

38case low: ret = LOW;

39break;

40case high: ret = HIGH;

41break;

42default: printf("ERROR in compute\n");

43exit(1);

44}

45return ret;

46}

312