摘要
针对传统A*算法在栅格环境中进行路径规划无约束条件导致的安全隐患以及计算时间较长的问题,提出一种基于正六边形网格建模及改进A*算法的路径规划方法。首先,提取电子海图数据中的海洋环境信息,采用正六边形网格划分建立路径搜索空间的海洋环境模型,使用立方体坐标系对正六边形网格统一编号简化坐标运算;其次,通过引入"引导量"对A*算法启发函数进行改进,减少具有相同估价值的网格数量优化算法搜索效率;最后,分析不同扩展邻域对算法效率以及规划路径的影响。将A*算法分别在基于栅格法划分和基于正六边形网格划分建立的环境模型下进行仿真实验对比,然后将改进A*算法和传统A*算法在正六边形网格划分建立的环境模型下进行仿真实验对比,结果表明,基于正六边形网格建模和对A*算法的改进可以增加算法搜索效率,减少转弯次数,增加路径安全性。
Aiming at the security risks caused by unconstrained path planning in raster environment by the traditional A*algorithm and the problem of long calculation time,a path planning method based on regular hexagon mesh modeling and improved A*algorithm is proposed.Firstly,we extract marine environment information from electronic chart data,use regular hexagon mesh division to establish marine environment model of path search space and use cube coordinate system to simplify coordinate operation by uniform numbering of regular hexagon mesh.Secondly,introduce“bootstrap quantity”to improve the heuristic function of A*algorithm and reduce the number of grids with the same estimated value to optimize algorithm search efficiency.Finally,analyze the influence of different extension domains on algorithm efficiency and path planning.We compare the simulation experiments of the A*algorithm in the environment model based on raster-based partition and the environment model based on the regular hexagon grid partition,and then compare the simulation experiments of the improved A*algorithm and the traditional A*algorithm in the same environment model based on the regular hexagon grid partition.The results show that the modeling based on regular hexagon mesh and the improvement of A*algorithm can increase the algorithm search efficiency,reduce the number of turning and increase the path security.
作者
程杰
陈姚节
CHENG Jie;CHEN Yao-jie(School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China;Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System,Wuhan 430065,China;Metallurgical Industry Process National Virtual Simulation Experimental Teaching Center,Wuhan 430065,China)
出处
《计算机技术与发展》
2020年第11期37-41,共5页
Computer Technology and Development
基金
国家自然科学基金(U1803262)。
关键词
无人水面艇
A*算法
路径规划
电子海图
正六边形网格划分
unmanned surface vehicle
A*algorithm
path planning
electronic chart
regular hexagon mesh division
