Abstract：The traditional A* algorithm has the disadvantages of long planning time and large search range in unmanned vehicle path planning. After comprehensively analyzing the calculation process of the A* algorithm, the A* algorithm was improved from four aspects. Firstly, targeted expansion, that is, different quadrants were selected with target for node expansion according to the relative position of the node to be expanded and the target node. Secondly, target visibility judgment, that is, whether there were obstacles between the node to be expanded and the target point was determined, if there were no obstacles, A* algorithm jumped out of the exploration process to reduce redundant searches. Thirdly, the heuristic function of the A* algorithm was changed, that is, the cost estimation of the n-th generation parent node of the node to be expanded to the target point was increased, thereby reducing the local optimal situation of the cost estimation to the target point. Fourthly, the selection strategy of the expanded nodes was changed, that is, the traditional method of minimizing the heuristic function to select the expanded nodes was changed, and the simulated annealing method was introduced to optimize the selection method of the expanded nodes, so that the search process was performed as close to the target point as possible. Finally, the Matlab simulation experimental results show that, under the simulated map environment, the improved A* algorithm has the running time reduced by 67.06%, the number of experienced grids decreased by 73.53%, and the fluctuation range of the optimized path length is ±0.6%.
[1] TSITSIASHVILI G S,LOSEV A S. Application of the Floyd algorithm to the asymptotic analysis of networks with unreliable ribs[J]. Automation and Remote Control,2008,69(7):1262-1265. [2] 李泽文, 唐平, 曾祥君, 等. 基于Dijkstra算法的电网故障行波定位方法[J]. 电力系统自动化,2018,42(18):162-168.(LI Z W, TANG P,ZENG X J,et al. Method of traveling wave fault location based on Dijkstra algorithm in power grid[J]. Automation of Electric Power Systems,2018,42(18):162-168.) [3] CHEN R M,HSIEH F R,WU D S. Heuristics based ant colony optimization for vehicle routing problem[C]//Proceedings of the 7th IEEE Conference on Industrial Electronics and Applications. Piscataway:IEEE,2012:1039-1043. [4] 于立婷, 谭小波, 吴艳梅. SDN网络中基于改进粒子群的最优路径规划算法[J]. 沈阳理工大学学报,2019,38(2):20-25. (YU L T,TAN X B,WU Y M. Optimal path planning algorithm based on improved particle swarm optimization under the SDN architecture[J]. Journal of Shenyang Ligong University,2019,38(2):20-25.) [5] 李俊, 舒志兵. 基于改进D* Lite遗传算法路径规划研究[J]. 机床与液压,2019,47(11):39-42. (LI J,SHU Z B. Research on path planning based on improved D* Lite genetic algorithm[J]. Machine Tool and Hydraulics,2019,47(11):39-42.) [6] 禹建丽, 李晓燕, 王跃明, 等. 一种基于神经网络的机器人路径规划算法[J]. 洛阳工学院学报,2001,22(1):31-34.(YU J L, LI X Y,WANG Y M,et al. An algorithm of path planning for carlike robots based on neural network[J]. Journal of Luoyang Institute of Technology,2001,22(1):31-34.) [7] 巩敦卫, 曾现峰, 张勇. 基于改进模拟退火算法的机器人全局路径规划[J]. 系统仿真学报,2013,25(3):480-483,488. (GONG D W,ZENG X F,ZHANG Y. Global path planning method of robot based on modified simulated annealing algorithm[J]. Journal of System Simulation,2013,25(3):480-483,488.) [8] 贾庆轩, 陈钢, 孙汉旭, 等. 基于A*算法的空间机械臂避障路径规划[J]. 机械工程学报,2010,46(13):109-115. (JIA Q X, CHEN G,SUN H X. Path planning for space manipulator to avoid obstacle based on A* algorithm[J]. Journal of Mechanical Engineering,2010,46(13):109-115.) [9] 王殿君. 基于改进A*算法的室内移动机器人路径规划[J]. 清华大学学报(自然科学版),2012,52(8):1085-1089. (WANG D J. Indoor mobile-robot path planning based on an improved A* algorithm[J]. Journal of Tsinghua University(Science and Technology),2012,52(8):1085-1089.) [10] 王维, 裴东, 冯璋. 改进A*算法的移动机器人最短路径规划[J]. 计算机应用,2018,38(5):1523-1526. (WANG W,PEI D,FENG Z. The shortest path planning for mobile robots using improved A* algorithm[J]. Journal of Computer Applications, 2018,38(5):1523-1526.) [11] 吴天羿, 许继恒, 刘建永, 等. 基于改进A*算法的越野路径规划研究[J]. 计算机应用研究,2013,30(6):1724-1726.(WU T Y,XU J H,LIU J Y,et al. Research of cross-country path planning based on improved A* algorithm[J]. Application Research of Computers,2013,30(6):1724-1726.) [12] 高民东, 张雅妮, 朱凌云. 应用于机器人路径规划的双向时效A*算法[J]. 计算机应用研究,2019,36(3):792-795,800. (GAO M D,ZHANG Y N,ZHU L Y. Bidirectional time-efficient A* algorithm for robot path planning[J]. Application Research of Computers,2019,36(3):792-795,800.) [13] 熊壬浩, 刘羽. A*算法的改进及并行化[J]. 计算机应用, 2015,35(7):1843-1848. (XIONG R H,LIU Y. Improvement and parallelization of A* algorithm[J]. Journal of Computer Applications,2015,35(7):1843-1848.) [14] PATRICK. A* pathfinding for beginners[EB/OL].[2019-03-15] https://www.jianshu.com/p/e52d856e7d48. [15] 冯玉蓉. 模拟退火算法的研究及其应用[D]. 昆明:昆明理工大学,2005. (FENG Y R. Study and application of simulated annealing algorithm[D]. Kunming:Kunming University of Science and Technology,2005.)
2020, Vol. 40 
