Research on the A* Algorithm Based on Adaptive Weights and Heuristic Reward Values

Aiming at the problems of the A* algorithm’s long running time, large number of search nodes, tortuous paths, and the planned paths being prone to colliding with the corner points of obstacles, adaptive weighting and reward value theory are proposed to improve it. Firstly, the diagonal-free five-way search based on the number of coordinate changes is used to make the algorithm purposeful. Meanwhile, in order to improve the path security, the diagonal search is filtered out when there are obstacles in the search neighborhood. Secondly, a radial basis function is used to act as the adaptive weighting coefficient of the heuristic function and adjust the proportion of heuristic functions in the algorithm accordingly to the search distance. Again, optimize the cost function using the reward value provided by the target point so that the current point is away from the local optimum. Finally, a secondary optimization of the path is performed to increase the distance between the path and the barriers, and the optimized path is smoothed using Bessel curves. Typical working conditions are selected, and the algorithm is verified through simulation tests. Simulation tests show that the algorithm not only shortens the planning time and improves the path security but also reduces the number of search nodes by about 76.4% on average and the turn angle by about 71.7% on average.