为解决传统A∗寻路算法在搜索过程中会产生大量冗余节点,导致算法整体搜索效率低,运算内存消耗大等问题,从A∗算法的两个重要决策点出发,改进算法的代价评估函数与邻节点搜索策略,提出一种改进融合算法.首先,采用向量叉积与尺度平衡因子相结合的方法优化传统A∗算法的启发函数,减少A∗算法寻路过程中在最优路径周围产生的具有相同代价值的冗余节点,减少了对称路径的搜索;其次,融合跳点搜索(Jump point search,JPS)策略,通过逻辑判断实现路径的变步长跳跃搜索,避免了A∗算法逐层搜索效率低的弊端.在不同尺寸的栅格地图中进行仿真分析,发现改进融合算法相比于传统A∗算法,在路径长度基本相等的情况下,节点搜索数量约减少95%,且与传统JPS寻路算法相比,有效过滤了路径周围复杂形状障碍物产生的大量冗余跳点.最后,将改进融合算法应用于ROS移动机器人并进行对比实验以验证算法的可行性.实验结果表明:改进融合算法在获得高效安全的路径基础上,搜索效率相比于A∗算法可提高约94%.
Research on Improved A? Algorithm Integrating Vector Cross-product and Jump Point Search Strategy
The traditional A∗routing algorithm has many problems in the search process,such as many redundant nodes,low overall search efficiency and large computational memory consumption.To solve these problems,in this paper,starting from the two important decision points of the A∗ algorithm,an improved fusion algorithm was proposed by improving the cost evaluation function and adjacent node search strategy of the algorithm.Firstly,the combination of vector cross-product and scale balance factor was selected to optimize the heuristic function of traditional A∗algorithm,which reduced the redundant nodes with the same generation value around the optimal path in the routing process of A∗ algorithm and reduced the search of symmetric path.Secondly,the algorithm integrated the jump point search strategy and realized the variable step size jump search of the path through logical judgment,which avoided the disadvantages of low search efficiency of A∗ algorithm layer by layer.Through simulation analysis in grid maps of different sizes,it was found that,compared with the traditional A∗ algorithm,the improved fusion algorithm reduced the number of node searches by approximately 95%at the same path length,and effectively filtered many redundant hops generated by complex shape obstacles around the path compared with the traditional JPS routing algorithm.Finally,the improved fusion algorithm was applied to ROS mobile robot,and comparative experiments were carried out to verify the feasibility of the algorithm.The experimental results showed that the search efficiency of the improved fusion algorithm was approximately 94%higher than that of A∗algorithm on the basis of obtaining efficient and safe paths.
path planningcross-productjump point searchA∗algorithmmobile robot
国家科技期刊平台
NSTL
万方数据
