Research On Indoor Path Planning And Obstacle Avoidance Based On Improved D~* Algorithm Using CA Model

With the rapid development of science and technology, the technology of intelligent mobile robot becomes a research hotspot in modern times. Home service robot is one of the representatives of the mobile robots. The path planning and autonomous walking also become key research objects. In this dissertation, the existing path planning algorithm is improved, and the researches on mobile robot path planning in indoor environment are as follows:Firstly, this dissertation introduces and analyzes the cellular automata model and D~* path planning algorithm. We know that the D~* algorithm searches 4 or 8 directions from current position every time, and it is a kind of length priority algorithm, so the generated path has many unnecessary bent corners. In order to solve this problem, this dissertation uses the extended Moore neighborhood structure of cellular automata to search 16 directions from current position. The minimum incremental change of angle is reduced to π/8 and the unnecessary rotation of the robot is reduced by this method.Secondly, when it encounters obstacles, it searches other adjacent to the shortest possible path again, so the generated path and obstacles are too close. In order to solve this problem, this dissertation adds collision coefficient to the cost estimation function of D~* algorithm. That is to say, the closer to the obstacles the cellular automata is, the higher collision coefficient will be. We can keep a safe distance between path an obstacles by this way.Finally, when the robot is in the actual moving process, it may encounter unknown obstacles and lead to collision. In this regard, through this article the robot has the ability to perceive environmental information by installing sensors on it, if the robot has detected that the dynamic obstacles are in linear motion, then it uses the relative velocity method to predict whether collision will occur; if motion trajectory of the obstacles is uncertain, then it uses regression method to predict the arrival location of the obstacles in the future, and estimates whether the two object will collide. If the collision happened, then adopt different collision avoidance methods to guide the robot moving according to different collision situations.In this dissertation, The experiment proved that the improved D~* algorithm which is based on the CA model can plan out a relatively smooth and safe path. Meanwhile, the prediction algorithm of obstacle’s location and the method of collision avoidance can avoid collisions between the robot and unknown dynamic obstacles effectively.