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

21 Genetic Programming

DARWIN, C. On the Origin of Species by Means of Natural Selection, or Preservation of Favoured Races in the Struggle for Life, John Murray, London, 1859

FERNANDEZ, J. The GP Tutorial – The Genetic Programming Notebook, http://www.geneticprogramming.com/Tutorial/, 2006

GRAHAM, P. ANSI Common Lisp, Prentice Hall, Englewood Cliffs NJ, 1995

HANCOCK, P. An empirical comparison of selection methods in evolutionary algorithms, in T. Fogarty (Ed.), Evolutionary Computing, AISB Workshop, Lecture Notes in Computer Science, no. 865, Springer-Verlag, Berlin Heidelberg, 1994, pp. 80-94 (15)

HWANG, Y. Object Tracking for Robotic Agent with Genetic Programming, B.E. Honours Thesis, The Univ. of Western Australia, Electrical and Computer Eng., supervised by T. Bräunl, 2002

IBA, H., NOZOE, T., UEDA, K. Evolving communicating agents based on genetic programming, IEEE International Conference on Evolutionary Computation (ICEC97), 1997, pp. 297-302 (6)

KOZA, J. Genetic Programming – On the Programming of Computers by Means of Natural Selection, The MIT Press, Cambridge MA, 1992

KURASHIGE, K., FUKUDA, T., HOSHINO, H. Motion planning based on hierarchical knowledge for six legged locomotion robot, Proceedings of IEEE International Conference on Systems, Man and Cybernetics SMC’99, vol. 6, 1999, pp. 924-929 (6)

LANGDON, W., POLI, R. Foundations of Genetic Programming, Springer-Ver- lag, Heidelberg, 2002

LEE, W., HALLAM, J., LUND, H. Applying genetic programming to evolve behavior primitives and arbitrators for mobile robots, IEEE International Conference on Evolutionary Computation (ICEC97), 1997, pp. 501506 (6)

MAHADEVAN, S., CONNELL, J. Automatic programming of behaviour-based robots using reinforcement learning, Proceedings of the Ninth National Conference on Artificial Intelligence, vol. 2, AAAI Press/MIT Press, Cambridge MA, 1991

MCCARTHY, J., ABRAHAMS, P., EDWARDS, D., HART, T., LEVIN, M. The Lisp

Programmers' Manual, MIT Press, Cambridge MA, 1962

WALKER, M., MESSOM, C. A comparison of genetic programming and genetic algorithms for auto-tuning mobile robot motion control, Proceedings of IEEE International Workshop on Electronic Design, Test and Applications, 2002, pp. 507-509 (3)

324

Traditional attempts at formulating complex control programs have been based on “Artificial Intelligence” (AI) theory. The dominant paradigm of this approach has been the sense–plan–act (SPA) organization: a

mapping from perception, through construction of an internal world model, planning a course of action based upon this model, and finally execution of the plan in the real-world environment. Aspects of this method of robot control have been criticized, notably the emphasis placed on construction of a world model and planning actions based on this model [Agre, Chapman 1990], [Brooks 1986]. The computation time required to construct a symbolic model has a significant impact on the performance of the robot. Furthermore, disparity between the planning model and the actual environment may result in actions of the robot not producing the intended effect.

An alternative to this approach is described by behavior-based robotics. Reactive systems that do not use symbolic representation are demonstrably capable of producing reasonably complex behavior [Braitenberg 1984], see Section 1.1. Behavior-based robotic schemes extend the concept of simple reactive systems to combining simple concurrent behaviors working together.

22.1 Software Architecture

Often the importance of the software structure for mobile robots is stressed. Unfortunately, many published software structures are either too specialized for a particular problem or too general, so no advantage can be gained for the particular application at hand. Still, at least two standard models have emerged which we will discuss briefly.

The classical model (Figure 22.1, left) is known by many names: hierarchical model, functional model, engineering model, or three-layered model. It is a predictable software structure with top-down implementation. Names for the

325325

22 Behavior-Based Systems

three levels in some systems are Pilot (lowest level), Navigator (intermediate level), and Planner (highest level), creating three levels of abstraction. Sensor data from the vehicle is pre-processed in two levels until the highest “intelligent” level takes the driving decisions. Execution of the actual driving (for example navigation and lower-level driving functions) is left to the layers below. The lowest layer is again the interface to the vehicle, transmitting driving commands to the robot’s actuators.

Figure 22.1: Software architecture models

The behavior-based model (Figure 22.1, right, [Brooks 1986]) is a bottomup design that is not easily predictable. Instead of designing large blocks of code, each robot functionality has been encapsulated in a small self-contained module, here called a “behavior”. All behaviors are executed in parallel, while

explicit synchronization is not required. One of the goals of this design is to

Subsumption simplify extendability, for example for adding a new sensor or a new behavio- architecture ral feature to the robot program. While all behaviors can access all vehicle sen-

sors, a problem occurs at the reduction of the behaviors to produce a single output for the vehicle’s actuators. The original “subsumption architecture” uses fixed priorities among behaviors, while modern implementations use more flexible selection schemes (see Chapter 22).

22.2 Behavior-Based Robotics

The term “behavior-based robotics” is broadly applicable to a range of control approaches. Concepts taken from the original subsumption design [Brooks 1986] have been adapted and modified by commercial and academic research groups, to the point that the nomenclature has become generic. Some of the most frequently identified traits of behavior-based architectures are [Arkin 1998]:

326

Behavior-Based Robotics

327

22 Behavior-Based Systems

ful task completion are easier to define than a complete system specification, this would significantly reduce the work required of the system designer.

A more advanced and more flexible method for behavior selection is to use a neural network controller (see Chapter 19, Figure 22.2), as we did for some of the following applications. The neural network will receive input from all sensors (including pre-computed high-level sensor data), a clock, plus status lines from each behavior and will generate output to select the currently active behavior, and thereby cause a robot action. The structure of the network is itself developed with a genetic algorithm designed to optimize a fitness function describing the task criteria (see Chapter 20).

Figure 22.2: Behaviors and selection mechanism in robot environment

Emergent The terms emergent functionality, emergent intelligence or swarm intelli- functionality gence (if multiple robots are involved) are used to describe the manifestation of an overall behavior from a combination of smaller behaviors that may not have been designed for the original task [Moravec 1988], [Steels, Brooks 1995]. The appearance of this behavior can be attributed to the complexity of interactions between simple tasks instead of the tasks themselves. Behavior is generally classified as emergent if the response produced was outside the anal-

ysis of system design but proves to be beneficial to system operation.

Arkin argues that the coordination between simpler sub-units does not explain emergence completely [Arkin 1998]. As coordination of a robot is achieved by a deterministic algorithm, a sufficiently sophisticated analysis

328

Behavior-Based Applications

should be able to perfectly predict the behavior of a robot. Rather, the emergent phenomenon is attributed to the non-deterministic nature of real-world environments. These can never be modeled completely accurately, and so there is always a margin of uncertainty in system design that could cause unexpected behavior to be exhibited.

22.3 Behavior-Based Applications

329