摘要
针对在较大栅格地图上进行路径规划时,传统A^*算法搜索路径效率低,路径存在许多冗余节点和转折点的问题,提出了一种改进A^*算法。首先,针对传统A^*算法的启发函数,引入当前节点的父节点启发函数;然后,再引入切比雪夫距离作为当前节点的父节点启发函数之和的系数,得到基本的搜索路径;再次,通过转折点选取策略剔除冗余共线节点;最后,通过关键点选取方法,剔除冗余转折点,得到只包含起点、转折点、终点的路径。仿真实验结果表明,与传统A^*算法和指数衰减系数加权的改进A^*算法相比,搜索路径耗费时间分别减少了59.79%和30.93%,路径长度分别缩短了2.57%和0.07%,而路径包含节点分别减少了99.21%和0.00%。实验结果表明,在较大栅格地图中,所提算法能够有效提高路径搜索效率,同时缩短路径长度,减少路径包含的路径节点数,获得更优质的路径。
Since the path obtained by the traditional A^* algorithm usually have many turning node cost much time in a big grid map,an improved A^* algorithm was proposed.Firstly,for the heuristic function of the traditional A^* algorithm,the parent node of the current node was introduced into it.Secondly,the Chebyshev distance was also introduced into the heuristic function.Thirdly,the redundant collinear nodes on the path were eliminated by a turning point selection strategy.Finally,by the key point selection method,the redundant turning points were eliminated again,the final path only included the staring node,the turning nodes and the ending node.In the comparison with the traditional A^* algorithm and the improved A^* algorithm,the time for finding path decreased by 59.79%and 30.93%,the path length decreased by 2.57%and 0.07%and the paths’nodes decreased by 99.21%and 0.00%.The results show that the proposed algorithm searches path more effective,shorten the path length,reduces the number of path nodes,and obtain a better path in large grid maps.
作者
刘生伟
马钺
孟树峰
孙树琪
LIU Shengwei;MA Yue;MENG Shufeng;SUN Shuqi(Shenyang Institute of Automation,Chinese Academy of Sciences,Shenyang Liaoning 110016,China;University of Chinese Academy of Sciences,Beijing 100049,China;Henan Shuanghui Investment and Development Company Limited,Luohe Henan 462003,China)
出处
《计算机应用》
CSCD
北大核心
2019年第S02期41-44,共4页
journal of Computer Applications
