Research On Path Planning Based On Improved A* Algorithm

This thesis summarized the research progress of path planning and explores the improvement and application of path smoothing and the obstacle avoidance of global path planning based on A-star algorithm,and the obstacle avoidance of local path planning based on dynamic window approach(DWA).The main research are as follows.1)The method of removing redundant nodes and connecting key nodes is proposed to resolve the problem that the traditional A-star algorithm has many inflection points which bring abrupt speed changes to the robot’s movement.When environment with low obstacle density of 6 %,the modified method can save the number of inflection point by about 50 %,save the path length by about 3 %.When environment with medium obstacle density of 12%,the modified method can save the number of inflection point by about 28 %,save the path length by about 3 %.When environment with high obstacle density of 24%,the modified method can save the number of inflection point by about 25 %,save the path length by about 1 %.This method provides a new idea for reducing the number of inflection points and effectively reducing the computational workload.2)An improved A-star algorithm containing the parameter of obstacle numbers around the path is proposed to avoid the problem that the path may pass through dense obstacle areas related to the traditional A-star algorithm considering only the distance factor in the global path planning.Experiments were carried out on maps with different obstacle densities to explore the influence of the obstacle parameter ωon the number of obstacles around the path,the length of the path,the number of search nodes and search time.Simulation results shows that the selection of ωdepends on the obstacle density.In the map with 12 % low obstacle density,ω at the range of [0.2,0.4],the number of obstacles around the path can be greatly reduced with a small increase in search time.In particular,when ω is 0.2,the number of obstacles around the path is reduced by about 58 %.In the map with 24 % high obstacle density,ω at the range of [0.8,1.0],the number of obstacles around the path can be greatly reduced with a small increase in search time.In particular,when ω is0.8 the number of obstacles around the path is reduced by about 18 %.3)Dynamic path planning is explored by fusing DWA algorithm and A-star algorithm,wherein the improved A-star algorithm is used for global path planning and the DWA algorithm is used for local path planning and obstacle avoidance.Meanwhile,a method of segmenting the global path and improving the orientation evaluation function is proposed to neutralize the problem that the traditional DWA algorithm may deviate from the global path.Dynamic path planning simulation results show that the fusion algorithm can effectively avoid deviation from the global pathThis study proposes the methods to effectively reduce the path inflection points involved in the traditional A-star algorithm,reduce the number of obstacles around the path,and improve the path offset problem in local path planning involved in DWA,which provide a reference strategy for the design of dynamic path planning.31 pictures,81 references...