Python implementation of Genetic Algorithm in Path Planning

Running instruction:

• Run the main.py file from directory.
• User can defined path points, links b/w path points, population size, mutation rate in the Config.py file

Requirements

• python
• numpy

Features

• user can define fixed links b/w nodes
• user can initialize population of chromosomes which are initialized randomly but program insures that two consective nodes should be linked to each other.
• user can calculate chromosome fitness based on total distance of chromosomes and connectivity of nodes.
• user can find best fitness indices
• user can rank the initial population of chromosomes using roulets wheels selection method
• user can do crossover on the population
• user can do mutation on the population

Fixed issues:

• bug fixed in create population function
• bug related to chromosome population fitness best indices removed
• Bug in generate mating pool function of ranking file fixed
• Bug removed in function check fitness based on connection in fitness file

Example for usage:

You can initialize population in main function like:

• chr_population = population()

You can calculate fitness & find best fitness indices in main function like:

• chr_pop_fitness, chr_best_fitness_index = fitness(chr_pop=chr_population)

You can obtain ranked population in main function like:

• chr_ranked_population = ranking(chr_pop_fitness=chr_pop_fitness, pop=chr_population)

You can do crossover & mutation in main function like:

• chr_crossover_mutated_population = dna(chr_pop_fitness=chr_pop_fitness, ranked_population=chr_ranked_population, chr_best_fitness_index=chr_best_fitness_index, last_pop=chr_population)

Objective

• Use Genetic Algorithm for finding a best path for mobile robot in a 2D environment.
• To move from starting point to the endpoint while avoiding collisions with obstacles and minimizing total distance travelled.

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.