Research on global path planning algorithm for mobile robots based on improved A*

Abstract

In order to shorten searching time and reduce the quantity of redundant nodes in path planning, an improved A* algorithm was proposed. In the novel algorithm, compared with the A* algorithm, the octet neighborhood was replaced a rectangular boundary without obstacles. The map was explored in two directions from the starting point and the target point respectively. The exploration generated fewer nodes. Due to the enlargement of the search neighborhood and the rectilinear passage without obstacles in the rectangular region, the new algorithm used Euclidean distance as distance estimate. And a new operator was designed to seek the best search node to reduce the time complexity, so as to improve the efficiency of the algorithm. For improving the safety of mobile robot, the novel algorithm adopted adaptive cost function to improve the ability of road safety discrimination. A Slide-Rail corner adjustment method was designed to reduce unnecessary corners and improve the smoothness of the path. The simulation results showed that, compared with the traditional A* algorithm and various improved A* algorithms, the proposed algorithm can shorten the path length and searching time, reduce the number of turns, the total turning angles and search nodes. Compared to A*, the searching time was reduced by 64.76%, the total turning angles were reduced by 56.34%, and the search nodes were reduced by 82.76% averagely in test maps of this paper. Moreover, the average interval width in improved A* was 3.07 and was more than 1.5 times the average interval width in Rectangle Expansion A*.