An Improvement of D* Algorithm for Mobile Robot Path Planning in Partial Unknown Environment

摘要

An important problem in autonomous mobile robot (Mobot) navigation is that the mobot can effectively plan a path in the unknown or partial unknown environment. It's unpractical to know the environment completely. These factors, such as bias of environmental expression and change of obstacles state, will cause incomplete information of environment. In this case, the motion planning must be implemented in real-time. It is obvious that path planning in dynamic or partially known environment is a difficult problem to solve in practice. D* algorithm combines local planning and global planning, makes sufficient use of global environment and information from sensors, that had tested in the practice application. In this paper we analysis at the situation of partially known environment, and use D* algorithm to process the path planning. The improvement of D* algorithm is presented to plan better path. First, the model of 2D workspace with some obstacles is expressed in regularity grids. Optimal path is planned by using the improved D* algorithm by searching in the neighbor grid cells on 16 directions. It makes the robot that the smallest turning angle drops to pi /8. The mobot moving angle discrete precision is raised and the unnecessary cost of path planning is reduced. So the mobot motion path is smoother. Then the improved D* algorithm is tested in WiRobotX80 mobile robot. Experiment results show that the improved D* algorithm is effective and it can result in higher quality path than the conventional D* algorithm in the same map environment.