Path Generation for Mobile Robot using Genetic Algorithm

Abstract

The shortest/optimal path generation is essential for the efficient operation of mobile robot. This paper will present an algorithm for global path planning to a goal with a mobile robot in an known environment. The algorithm makes use of the modified quadtree data structure to model the environment and uses a genetic algorithm to generate a optimal path for the robot to move. Actually the genetic algorithm consists of two stages, the first stage (named a minor league) checks if a chromosome is reachable to goal position or not, and makes the individuals evolve. And, the only reachable chromosome and the best individuals of them are transferred to the second stage (called a major league) and then are evolved. Finally, the best chromosome of individuals in second stage is survived, so that the optimal/shortest path is generated. It is shown that our proposed method can find out a optimal path very quickly through simulation results.