[1]程 杰,陈姚节.基于正六边形建模的无人水面艇路径规划[J].计算机技术与发展,2020,30(11):37-41.[doi:10. 3969 / j. issn. 1673-629X. 2020. 11. 007]
　CHENG Jie,CHEN Yao-jie.Path Planning of Unmanned Surface Vehicle Based on Regular Hexagon Modeling[J].,2020,30(11):37-41.[doi:10. 3969 / j. issn. 1673-629X. 2020. 11. 007]
点击复制

基于正六边形建模的无人水面艇路径规划()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
30
期数:
2020年11期
页码:
37-41
栏目:
智能、算法、系统工程
出版日期:
2020-11-10

文章信息/Info

Title:
Path Planning of Unmanned Surface Vehicle Based on Regular Hexagon Modeling
文章编号:
1673-629X(2020)11-0037-05
作者:
程 杰1; 2; 陈姚节1; 2; 3
1. 武汉科技大学 计算机科学与技术学院,湖北 武汉 430065; 2. 智能信息处理与实时工业系统湖北省重点实验室,湖北 武汉 430065; 3. 冶金工业过程国家级虚拟仿真实验教学中心,湖北 武汉 430065
Author(s):
CHENG Jie1; 2; CHEN Yao-jie1; 2; 3
1. School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China; 2. Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System,Wuhan 430065,China; 3. Metallurgical Industry Process National Virtual Simulation Experimental Teaching Center,Wuhan 430065,China
关键词:
无人水面艇; A*算法; 路径规划; 电子海图; 正六边形网格划分
Keywords:
unmanned surface vehicle; A* algorithm; path planning; electronic chart; regular hexagon mesh division
分类号:
TP391. 9
DOI:
10. 3969 / j. issn. 1673-629X. 2020. 11. 007
摘要:
针对传统 A*算法在栅格环境中进行路径规划无约束条件导致的安全隐患以及计算时间较长的问题,提出一种基于正六边形网格建模及改进 A*算法的路径规划方法。首先,提取电子海图数据 中的海洋环境信息,采用正六边形网格划分建立路径搜索空间的海洋环境模型,使用立方体坐标系对正六边形网格统一编号简化坐标运算;其次,通过引入“引导量”对 A*算法启发函数进行改进,减少具有相同估价值的网格数量优化算法搜索效率;最后,分析不同扩展邻域对算法效率以及规划路径的影响。将 A*算法分别在基于栅格法划分和基于正六边形网格划分建立的环境模型下进行仿真实验对比,然后将改进 A*算法和传统 A*算法在正六边形网格划分建立的环境模型下进行仿真实验对比,结果表明,基于正六边形网格建模和对 A*算法的改进可以增加算法搜索效率,减少转弯次数,增加路径安全性。
Abstract:
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.

相似文献/References:

[1]郑延斌 李新源 段德全.一种保持Agent团队队形的路径规划方法[J].计算机技术与发展,2009,(07):159.
　ZHENG Yan-bin,LI Xin-yuan,DUAN De-quan.A Path Planning Algorithm with Agent Team Formation Maintained[J].,2009,(11):159.
[2]冯晓辉 马光思.数码谜题求解的算法设计及其扩展研究[J].计算机技术与发展,2009,(08):110.
　FENG Xiao-hui,MA Guang-si.Algorithm Design and Extension Research of N - Puzzle Problem[J].,2009,(11):110.
[3]李培 何中市.基于ArcGIS和GPS的水电气管理系统设计与实现[J].计算机技术与发展,2009,(01):172.
　LI Pei,HE Zhong-shi.Design and Implementation Water, Electricity and Gas Management System Based on ArcGIS and GPS[J].,2009,(11):172.
[4]朱永红 张燕平.用VC＋＋实现基于A＊算法的八数码问题[J].计算机技术与发展,2006,(09):32.
　ZHU Yong-hong,ZHANG Yan-ping.Programming for Eight - Figure Puzzle Problem Based on Algorithm A ＊ with Visual C ＋ ＋[J].,2006,(11):32.
[5]陈益富 卢潇 丁豪杰.对Dijkstra算法的优化策略研究[J].计算机技术与发展,2006,(09):73.
　CHEN Yi-fu,LU Xiao,DING Hao-jie.Optimized Strategy Research over Algorithm of Dijkstra[J].,2006,(11):73.
[6]方伟华.基于A＊算法和图遍历的烟草物流VRP的研究[J].计算机技术与发展,2011,(12):63.
　FANG Wei-hua.Research on Tobacco Logistics VRP Based on A ＊ Algorithm and Graph Traversal[J].,2011,(11):63.
[7]刘钰 陆建峰 蔡海舟.基于改进A＊算法的机器人路径规划方法研究[J].计算机技术与发展,2012,(12):108.
　LIU Yu,LU Jian-feng,CAI Hai-zhou.Research on Path Planning Method of Robot Based on Improved A ＊ Algorithm[J].,2012,(11):108.
[8]马静,王佳斌,张雪. A*算法在无人车路径规划中的应用[J].计算机技术与发展,2016,26(11):153.
　MA Jing,WANG Jia-bin,ZHANG Xue. Application of A* Algorithm in Unmanned Vehicle Path Planning[J].,2016,26(11):153.
[9]朱云虹,袁一.基于改进A*算法的最优路径搜索[J].计算机技术与发展,2018,28(04):55.[doi:10.3969/ j. issn.1673-629X.2018.04.012]
　ZHU Yun-hong,YUAN Yi.Optimal Path Search Based on Improved A* Algorithm[J].,2018,28(11):55.[doi:10.3969/ j. issn.1673-629X.2018.04.012]
[10]叶小艳,钟华钧,邓可儿.一种基于改进 A*算法的室内导航路径规划方法[J].计算机技术与发展,2022,32(02):202.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 033]
　YE Xiao-yan,ZHONG Hua-jun,DENG Ke-er.A Path Planning Method of Indoor Navigation Based on Improved A-Star Algorithm[J].,2022,32(11):202.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 033]

更新日期/Last Update: 2020-11-10