Ohstacle Avoidence Path Planning Based On Cellular Genetic Algorithms

Path planning technology aims at searching an optimum safety path from start point to destination under environments with obstacles according to certain criterion.Path planning technology has been used widely in many industrial applications, such as robots, very large scale integrated circuits, geographic information system, and navigation system and so on. Many literatures have emerged in the field of mobile robot path planning so far, which include gradient decent method, the dynamic programming algorithm, A*algorithm, graphical method, artificial potential field,annealing simulation, taboo search, artificial neutral network and several swarm intelligent optimization methods such as genetic algorithm, ant colony algorithm and particle optimization.As an important branch of swarm intelligent algorithms, genetic algorithm is based on Darwin’s theory of natural selection, where offspring population are generated through genetic operator and population are progressed according to the rule of survival of the fittest, which has vigorous globally search performance. The application of genetic algorithm in path planning field has been paid extensive attraction and some theoretical achievement has arisen recently. But, when traditional genetic algorithm is utilized to plan path for mobile robot under complicated discrete environments, the feasibility of trajectory is difficult to be guaranteed during the insert phase for discontinuous path and algorithm is prone to converge prematurely because of the influence of selection pressure. So, a feasible path generation algorithm is presented in this paper which is based on statistical model of Moore neighbor and Cellular Genetic Algorithms is brought forward to plan path of robots under grid environments in order to present better performance. In the Cellular Genetic Algorithms, both cellular spatial structure and cellular state transition rule are incorporated into traditional genetic algorithm. Each individual is mapped from genetic space into cellular space of same scalability and viewed as a cell, and the genetic evolution is carried on the cellular space where individual is interacted with its neighbor randomly and the state of each cell is changed using life game rule. Since Cellular Genetic Algorithms can provide diversity of population when local optimization, the premature convergence can be restrained on some extent. The simulation platform of robot path planning is developed with Visual C++6.0and Matlab7.0, under which many different obstacle situations have been tested by both the new algorithm and other several algorithms to analyze performance of algorithms. Experimental results show new method can provide better solution than others, as indicate the validity and feasibility of the Cellular Genetic Algorithms.