Research On The Application Of Indoor Path Planning Based On Improved Hierarchical D~* Algorithm

Recently, with the technical progress and the rapid development of robot related subjects, mobile robotics becomes study hotspot gradually. As the indoor service robot is one of the hot research fields of mobile robot, related path planning problem becomes research object of many scholars.Based on the existing mobile robot path planning algorithm, the main works on the mobile robot path planning in the indoor environment in this dissertation are as follows:Firstly, we analyzed the basic principle of D* algorithm which is heuristic path planning algorithm. In order to overcome the defect of D* algorithm’s large search space, we introduced the idea of hierarchical path planning, structured the robot working environment into several hierarchical levels, and set key nodes in each level. The algorithm generated priori safe paths off-line using Voronoi graph theory to improve the efficiency of path planning among key nodes.Secondly, as the D* algorithm gives priority to the length of the path, in optimal paths searched by using D* algorithm, there is the problem of repeatedly turning within small range, which reduces the smoothness of the optimal paths. The cost of the optimal path is directly dependent on the performance of the cost function, so we improved the heuristic value of the cost function by using the diagonal function, and added the direction cost to the accumulated path cost function. Simulation results show that the smoothness of the optimal paths generated by improved D* algorithm is increased significant.Finally, analyzing the robot path planning algorithms in dynamic environment, we found the efficiency of these path planning algorithms, which used secondary path planning method to avoid collision with moving obstacles, is very low. Therefore, this dissertation proposed a local path planning algorithm in the dynamic environment, and the algorithm predicted the trajectory of the dynamic obstacles in current rolling window and determined whether the robot would collide with dynamic obstacles by using rolling window principle for reference. For uncertain trajectory dynamic obstacles, we predicted the trajectory exactly by using Kalman filtering algorithm and took different collision avoidance measures to guide the robot forward according to different collision situations. Simulation results show that the local path planning algorithm can adapt to the mobile robot path planning better under dynamic environment, and effectively avoid collision between mobile robot and dynamic obstacles.