Obstacles Avoidance Path Planning for Mobile Robot Based on Cellular Automata

In order to quickly plan the shortest path for mobile robot in two-dimensional space, a two-stage obstacles avoidance path planning algorithm based on cellular automata was presented in this paper. For the first stage, the distance between each free cell to the ending cell was gradually generated by the evolution of cellular automata, and the algorithm’s cellular space, cellular states, Moore type neighbors and evolutionary rules were described, respectively. For the second stage, by using the idea of the negative gradient, a method of generating the shortest path based on the cells’ state values was proposed. Accordingly, the corresponding flow chart and Matlab programme of the algorithm were designed. The effectiveness of the algorithm was verified by the simulation and the physical experiment. The results showed that the shortest path in complex environment can be efficiently planned by using our cellular automata algorithm.