Industrial Applications of Genetic Algorithms:Development of Mobile Robot Wall-following Algorithms Using Genetic Programming

Previous | Table of Contents | Next

## Chapter 14
Development of Mobile Robot Wall-following Algorithms Using Genetic Programming

Robert A. Dain

Sierra On-Line
bob.dain@sierra.com.

ABSTRACT

This chapter demonstrates the use of genetic programming (GP) for the development of mobile robot wall-following navigation algorithms. Algorithms are developed for a simulated mobile robot that uses an array of range finders for navigation. Navigation algorithms are tested in a variety of different shaped environments to encourage the development of robust solutions, and reduce the possibility of solutions based on memorization of a fixed set of movements or solutions that capitalize on insignificant coincidental properties of the simulation environment. Results are presented and GP is shown to be capable of producing robust wall-following navigation algorithms that perform well in each of the test environments used.

INTRODUCTION

This work focuses on using genetic programming (GP) to develop mobile robot navigation strategies that will perform well in the real world. A simulated robot is used for learning, but the simulation is designed to closely approximate a real robot. The algorithms developed with GP can then be tested in the real world, on a real robot. Wall-following was selected for the initial problem domain because it is a fairly simple problem to set up and evaluate, and because it lays the groundwork for more complex problem domains, such as maze traversal, mapping, and full coverage navigation (i.e., vacuuming and lawn mowing). The development process for these behaviors is described, and the results of the experiments are presented.1

> 1All experiments are conducted using a genetic programming application developed by the author.

Genetic programming is attractive for this work for several reasons. First, it is a machine learning technology, so control strategies are emergent rather than predetermined. The GP environment is set up for a particular problem domain and it is left to “the unyielding weight of evolution,” as Dr. John Koza puts it [1], to drive out solutions. Also, GP is a black-box system in that a-priori knowledge of the system under analysis is not required. Some method of analyzing the results obtained from a set of input conditions is all that is necessary. Finally, the results of a GP learning session can be arbitrarily complex. Complexity is bounded by imposing limits on the maximum size of the computer programs that GP can create. GP will explore solutions that range up to the largest allowable size, regardless of the magnitude of that limit.

GENETIC PROGRAMMING OVERVIEW

Genetic programming is a methodology for automatically generating computer programs. Rather than writing programs explicitly, GP applies natural selection and genetic recombination to evolve programs that solve a given problem. GP is founded on the premise that computer programs can be represented as tree structures, as shown in Figure 14.1a. The functions (f) operate on terminals (T) to produce a result. Functions are operations that take one or more arguments. They can be sequential (i.e., +, AND), conditional (i.e., If, When), or iterative (i.e., DoUntil, WhileDo). Terminals are operations that take no arguments but return a value (i.e., variables and constants). Figure 14.1b shows a simple arithmetic function. If terminals T1, T2, and T3, evaluate to 5, 7 and 2, respectively, then the program will return the value 6 when it is executed. (5 is added to 7 for an intermediate value of 12, which is then divided by 2 for a final result of 6.)

Figure 14.1a Tree-like representation of a computer program

Figure 14.1b (T1 + T2) / T3

The genetic programmer defines a set of functions and terminals appropriate for the problem at hand. These may include highly generic functions, such as those mentioned above, or they may be specific to the problem domain. The set of functions and terminals defined must satisfy two constraints: sufficiency and closure. Sufficiency requires that a solution to the given problem must exist within the space of all possible computer programs that can be created using the specified set of functions and terminals. Obviously, if a solution does not exist GP will not be able to find it. Closure requires that every function and terminal return a value of compatible type, and that every function accepts arguments of this same type. This constraint guarantees that any combination of functions and terminals that comprise a complete tree structure (i.e., a terminal is placed at every leaf node) will be a syntactically valid computer program that can be evaluated.

The genetic programmer also defines a fitness test that quantifies the performance of a computer program. The performance of a computer program in GP can be a function of the final result that it produces, or it can be based on an analysis of some side effect that the computer program has produced. In the work presented herein, the function and terminal sets contain operators that affect the contents of a 2-dimensional memory array. The final state of this array is evaluated to determine the computer program’s fitness.

Previous | Table of Contents | Next

Copyright © CRC Press LLC