摘要
在路径规划问题中,提出以A^(*)算法为基础的改进算法,引入跳点概念进行跳点搜索;提出有效障碍率概念,将有效障碍率与Octile距离相结合,并设置为启发函数;引入最小堆数据结构,改良Openlist的最小值运算,大幅缩短取最小值时间。在python编程环境下,进行低有效障碍率以及高有效障碍率20*20、30*30、50*50的地图环境下的仿真。仿真结果表明:该算法在有效障碍率较低时,运算时间短,寻优结果较好;在有效障碍率较高时,与对照组相比,运算时间更短,访问节点数较少,并且节约了内存空间。
An improved algorithm based on A^(*) algorithm is proposed in the field of path planning,and the algorithm uses the concept of jumping point for jumping-points-search.The concept of effective obstacle rate is proposed and combines the effective obstacle rate with Octile distance for heuristic function.At the same time,the minimum heap data structure is introduced to improve the minimum operation of openlist and greatly shortens the time of taking the minimum value.In the python programming environment,the simulation is carried out in the map environment with low effective obstacle rate and high effective obstacle rate of 20*20,30*30 and 50*50.The simulation results show that the algorithm has short calculation time and better optimization results when the effective obstacle rate is low.When the effective obstacle rate is high,compared with the control group,the operation time is shorter,the number of access nodes is less,and the memory space is saved.
作者
谢春丽
高胜寒
孙学志
XIE Chunli;GAO Shenghan;SUN Xuezhi(School of Transportation,Northeast Forestry University,Harbin 150006,China)
出处
《重庆理工大学学报（自然科学）》
CAS
北大核心
2022年第7期177-187,共11页
Journal of Chongqing University of Technology：Natural Science
基金
黑龙江省自然科学基金项目(LH2021F002)
中央高校基本科研项目业务费专项资金项目(2572018BG02)。
