基于改进A*算法的海上物资投送路径规划  

Path Planning of Goods and Materials Delivery at Sea Based on Improved A* Algorithm

作　　者：李航天 黄子奇 张安琳 黄道颖 李建春 LI Hangtian;HUANG Ziqi;ZHANG Anlin;HUANG Daoying;LI Jianchun(College of Computer and Communication Engineering,Zhengzhou University of Light Industry Zhengzhou 450000,China;North Information Control Research Academy Group Co.,Ltd.,Nanjing 211153,China;Engineering Training Center,Zhengzhou University of Light Industry,Zhengzhou 450000,China)

机构地区：[1]郑州轻工业大学计算机与通信工程学院,郑州450001 [2]北方信息控制研究院集团有限公司,南京211153 [3]郑州轻工业大学工程训练中心,郑州450001

出　　处：《火力与指挥控制》2023年第8期111-117,共7页Fire Control & Command Control

基　　金：国家科技支撑计划项目(2006BAK01A38);河南省教育厅基础研究基金资助项目(15A120020)。

摘　　要：在广阔海域使用传统A*算法为船舶进行物资投送路径规划时,会出现由于栅格地图节点过多而导致的搜索速度慢,路径转折点过多等问题,通过优化搜索策略和使用路径平滑操作对传统A*算法进行了改进。使用基于节点距离大小的子节点拓展方式进行双向搜索,减少无用节点的搜索,加快搜索速度;通过使用基于相邻路径向量夹角的路径平滑处理操作,降低一次改进A*算法所增加的路径冗余转折点的开销,从而减少了船舶的转弯次数和路径长度。仿真对比实验表明,在200*200的小粒度、多节点栅格地图中,所提二次改进A*算法相较于传统A*算法在路径搜索时间上缩短了约96%,转折点个数和路径节点总数分别减少了约74%和96%,对船舶的全局路径规划有更好的效果。When the traditional A*algorithm is used toplan the goods and materials delivery path for ships in vast sea areas,problems such as slow search speed and too many turning points of the path will occur due to too many nodes of the grid map.The traditional A*algorithm is improved by optimizing search strategy and using smoothing path operation.Firstly,bi-directional search is carried out based on the node expansion method of node distance,which reduces the search of useless nodes and speeds up the search.Secondly,by using smoothing path operation based on the included angle between adjacent path vectors,the cost of redundant turning points of the path increased by the first improved A*algorithm is reduced,thus reducing the number of turns of the ships and the length of the path.The simulation and comparison experiments show that in the 200*200 small-granularity and multi-node grid map,compared with the traditional A*algorithm,the secondary improved A*algorithm proposed in this paper reduces the path search time by about 96%,the number of turning points and the total number of path nodes by about 74%and 96%respectively,and has better results in global path planning for ships.

关 键 词：路径规划 A*算法 双向搜索 路径平滑 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] U665.26[自动化与计算机技术—控制科学与工程]