融合插点和跳跃点改进A*算法的路径规划  

Path Planning of Improved A* Algorithm by Integrating Interpolation and Jump Points

作　　者：陆辉山[1] 张燕飞 王福杰[1] 于婷 崔纪权 LU Hui-shan;ZHANG Yan-fei;WANG Fu-jie;YU Ting;CUI Ji-quan(School of Mechanical Engineering,North University of China,Taiyuan 030051,China)

机构地区：[1]中北大学机械工程学院,太原030051

出　　处：《科学技术与工程》2023年第24期10387-10393,共7页Science Technology and Engineering

基　　金：国家重点研发计划(2016YFD0700202);山西省自然科学基金(20210302123054)。

摘　　要：为了解决传统A*算法在路径规划中存在的一些问题,提出了一种融合插值点跳跃搜索路径算法来改进A*算法。在对栅格环境图中具有特殊意义的多组数据进行预处理后,通过起始点和目标点确定目标函数,并搜索出一条最优路径。利用MATLAB软件平台对8组规格不同的环境地图进行了路径规划仿真。实验结果表明:改进后的算法可以减少计算时间、搜索节点数量、内存占用和搜索路径长度。可见改进后的算法在搜寻最佳路径方面的效率更高。In order to solve some problems of the traditional A* algorithm in path planning,a fusion interpolation point jump search path algorithm was proposed to improve the A* algorithm.After pre-processing multiple sets of data with unique meaning in the raster environment map,the goal function was defined by the start and destination locations,and an optimum route was found.Path planning models were run on the MATLAB software framework for eight distinct groups of area maps.The experimental results show that the improved method can decrease computation time,the number of search nodes,memory occupation,and search route length.It can be seen that the improved algorithm is more effective in looking for the optimal route.

关 键 词：路径规划 插点 跳跃点搜索(JPS)算法 跳跃点 A*算法 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]