Matlab implementation of Genetic Algorithm in Path Planning

Problem Statement

Mobile robots move in environments, which can be static or dynamic.

In the static environment shown in the Fig., the MR is required to move from the start point to the endpoint (Goal) on permissible paths while avoiding collisions with the obstacles and minimizing the total distance travelled, time taken or energy consumed.

Methodology

Genetic Algorithms: A stochastic evolutionary technique based on human genetics.

Theory

Stochastic Methods

Stochastic Methods are based on laws of probability for sampling of random events and have the advantage that they can handle large problems.

Genetic Algorithms (GA)

The GA method is applicable to both static and dynamic environments. In static environment all coordinates (MR, obstacles, goal) are input into the onboard computer system of MR while in dynamic environment sensors need to be used.

A brief comparison between genetic algorithms and human genetics is given below:

GA Program

A chromosome consists of path points from Start to End

Each path has an associated length Or “distance”

Objective is to find the “optimal” path i.e. the shortest path

Flow Chart of Genetic Algorithm

Algorithm Development

Create Environment

The Environment is “created” by defining the workspace i.e. the 2D min and max of the coordinates (x,y); there are 7 obstacles and path points labeled 0-15 i.e. 16 path points; Starting Position is 0 and End-Point is 15 (see figure).

Note that link points in table are 1 through 16 and in adjoining image they are from 0 to 15.

Fitness of each chromosome

The “fitness” of a path is the inverse of the length of the path from starting point to end-point

Fitness(iPath) = 1.0/DistanceInPath(iPath)

Chromosome Length

No. of chromosomes: NC=20

For each iteration select 40% of these i.e. 8 chromosomes

No. of Bits NBITS = log NPTS /log 2 = log 16 / log 2 = 4

If there are 1024 points, then NBITS = log 1024/log 2 = 10

CHR_LEN=(NOBS+2)*NBITS = (7+2)*4 = 36 for 7 obstacles and 4 bits

CHR_LEN = (7+2)*10=900 for 7 obstacles and 10 bits

Selection of Path Points (Generating Population)

A Path is generated by selected points from a specified start-point to a specified end-point.

Starting Point

Consider each link point

Find distance from each link point to end-point

Calculate the Probability of moving to each link point (PDF and CDF)

Generate a random number in (0,1)

Select the next point in path (based on the random number generated)

Continue till end point is reached

Summary

An optimal solution is obtained by generating an initial population of chromosomes (paths consisting of path points), computing their “fitness” to select “best” parents for producing the “next generation” of chromosomes by carrying out evolutionary procedures of cross-over and mutation. The procedure is continued until no further improvement is possible; this is called “convergence” which corresponds to an “optimal” solution.