A-star algorithm for expanding the number of search directions in path planning

Zailong Zhang, Shanyu Wang, Jianwei Zhou

20212021 2nd International Seminar on Artificial Intelligence, Networking and Information Technology (AINIT)29 citationsDOI

Abstract

In order to solve the problem that the traditional A-star algorithm (square A-star algorithm has 8 search directions, regular hexagon A-star algorithm has 6 search directions) has many inflection points and long path, an improved A-star algorithm is proposed to expand the number of search directions. Firstly, the grid method is used to model the spatial environment that needs path planning. The improved A-star algorithm improves the search direction to 12 search directions. Because the improved A-star algorithm has more search directions and more choices than the traditional A-star algorithm, the total length of the planned path is significantly smaller than the traditional A-star algorithm, compared with the traditional square A-star algorithm and the traditional hexagon A-star algorithm, the total length of the path is reduced by 8.87% and 3.65% respectively. And because the search direction of the improved A-star algorithm is more, the planned path is smoother and the inflection points in the path are reduced.

Topics & Concepts

A* search algorithmStar (game theory)AlgorithmPath (computing)Search algorithmInflection pointBest-first searchPath lengthComputer scienceGuide starMathematicsYen's algorithmShortest path problemBeam searchTheoretical computer scienceDijkstra's algorithmStarsComputer visionGeometryComputer networkProgramming languageGraphMathematical analysisRobotic Path Planning AlgorithmsData Management and AlgorithmsRobotics and Sensor-Based Localization