Designing a Robot

Designing a Robot

Introduction

One of the main concerns in robotics is to plan a path for a robot system moving purposely and safely in an environment filled with known or unknown obstacles. There are two distinct categories which all existing approaches on robot motion planning fall into (Lumelsky 93). The first category is often called the piano movers' model. Full information about the geometry of the robot and obstacles in the environment is given beforehand, so path planning becomes a one-time off-line operation. In the second category of approaches, often called sensor motion planning, information about obstacles is assumed to be unknown, or at least partial, and local on-line information comes from sensory feedback. No detailed model of the environment is assumed and planning is done continuously based on whatever partial information is available at the moment. Sensor motion planning's advantages include: 1) it can deal with the uncertainty typical of unstructured environments; and 2) it requires much less memory or computation because relatively little information has to be processed in each step. On the negative side, generality is an elusive goal and optimality is usually ruled out.

As an artificial model of natural selection in biological systems, a genetic algorithm is a stochastic parallel search method based on the mechanics of natural selection and natural genetics (Holland 75). It consists of three basic genetic operators: selection, crossover, and mutation. While randomized, GA search is a structured and guided information exchange process rather than a simple random walk. It seeks near-optimal performance through the juxtaposition of encoded partial solutions or building blocks. The beauty of GAs lies in their robustness, efficiency, and flexibility and they are especially suitable for searching large, complex, and poorly-understand spaces often encountered in design tasks.

During the last decade, many papers have been written to explore the evolution of robot control strategies. Evolving combinational circuits was reported by Louis and Rawlins in 1991 (Louis 91). Louis, McGraw, and Wyckoff applied Case-Based Reasoning (CBR) to GAs as an analysis tool for the parity combinational circuit design problem (Loius 92). A series of technical reports has been published by Cliff, Husbands, and Harvey about using genetic algorithms to design neural-network control architectures for a simulated visually guided robot (Cliff 92). Murray and Louis applied GAs to design control circuits for four basic behaviors and another switch circuit to combine these low level behaviors together for a simulated robot (Murray 95).

Genetic Algorithms

Genetic algorithms (GAs) are randomized parallel search methods based on natural selection and evolution (Holland 75). They have been widely used in a variety of problems especially in machine learning and function optimization (Goldberg 89). To apply a GA to a problem, the problem's parameters are encoded into a binary string and all the binary strings concatenated into a chromosome or genotype. An initial population is created from a number of randomly generated genotypes and each genotype is assigned a fitness value computed by a problem-specific evaluation function.

A genetic algorithm is an iterative search process: ...