/genetic-algorithm-path-planning

Primary LanguagePythonMIT LicenseMIT

Python implementation of Genetic Algorithm in Path Planning

GA_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.