The aim of this chapter is to investigate the hardware (H/W) implementation of Genetic Algorithm (GA) based motion path planning of robot. The potential benefit of using H/W implementation of genetic algorithm is that it allows the use of huge parallelism which is suited to random number generation, crossover, mutation and fitness evaluation. The operation of selection and reproduction are basically problem independent and involve basic string manipulation tasks. The fitness evaluation task, which is problem dependent, however proves a major difficulty in H/W implementation. Another difficulty comes from that designs can only be used for the individual problem their fitness function represents. Therefore, in this work the genetic operators are implemented in H/W, while the fitness evaluation module is implemented in software (S/W). This allows a mixed hardware/software approach to address both generality and acceleration. Moreover, a simple H/W implementation for fitness evaluation of robot motion path planning problem is discussed.
TopIntroduction
The H/W implementation of genetic algorithm allows the use of parallelism for speedup decision in problems such as motion path planning. In this chapter, the genetic operators are implemented in H/W, while the fitness evaluation module is implemented in S/W. This allows a mixed hardware/software approach to address both generality and acceleration.
The Genetic H/W Engine itself is composed of three modules (Hortensius et al., 1989) as shown in Figure 1. FPGA is used for implementing these modules. In this work, design and simulation results of these modules implementation are presented. A random number generation module (RNG) based on Cellular Automata CA is designed and implemented to provide the other three modules with H/W generated random numbers. The RNG supplies pseudo-random bit strings to the selection module for scaling down the sum of fitness and for the crossover and mutation modules to choose crossover and mutation points.
Figure 1. Genetic algorithm modules
TopRandom Number Generator
The 1st module to be considered is the Random Number Generator (RNG). Hybrid Cellular Automata (CA) Figure (Hortensius et al., 1989), is used due to its maximal length binary sequence production from each site. CA based generators compare favorably with the other types such as Linear Feedback Shift Registers (LFSR) and mixed congenital RNG in terms of quality of randomness, and silicon area used. They use less silicon area in their implementation (Hortensius et al., 1989; Bland & Megson, 1996). Four sites, eight sites and 16 sites are implemented. Good results are obtained by forcing the neighbor to the last site to one. The boundary condition is not cyclic. 1st cell seeding, which can be all zeros, are applied only once. The output of the cell is passed out to provide the seed for next cell. In the next part we review the cellular automata kinds.
Cellular Automata
Cellular automata are groups of cells where each cell’s life (state) depends on its neighboring cells. The state of the cell in the next cycle is determined by following simple rules that checking the state of the cell itself and the state of its neighbors. In the one-dimensional CA RNG, each cell has two neighbors–sometimes called Left and Right respectively. For each cycle, the state or value of any cell is given by rule 30, which states that for any cell S at time t, S = Sl xor Sr.
Hybrid Cellular Automata
For better performance results, several CAs are combined for the implementation. The CA used in the RNG consists of N alternating cells which change their states according to rules 90 and 150 described in (Shackleford et al., 2002). The RNG uses XOR logic to calculate the next state of an indicated cell in the array which is implemented later in VHDL via two cellular automata rules. These rules are:
Rule 90:
Si+:=
Si-1 Xor S i+1
Rule 150:
Si+:=
Si-1 Xor Si Xor S i+1Here, Si is the current state of the cell i in the linear array, Si+ is the next state for Si. Thus, rule 90 updates itself based on only inputs from its neighbors while rule 150 considers its own state along with its neighbor states during updating. The structure of the RNG described here resembles that of a LFSR but has the advantage of having only local interconnects between flip flops, making the CA version operate at higher clock frequency. Also each number in this range is visited only once every 2N-1 calls.