基于改进A*算法的无人船完全遍历路径规划  

Unmanned Surface Vehicle Full Traversal Path Planning Based on Improved A* Algorithm

作　　者：吕霞付[1] 程啟忠 李森浩 林政 LÜXia-fu;CHENG Qi-zhong;LI Sen-hao;LIN Zheng(Chongqing University of Posts and Telecommunications,Key Laboratory of Industrial Internet of Things&Network Control,Ministry of Education,Chongqing 400065,China)

机构地区：[1]重庆邮电大学工业互联网与网络化控制教育部重点实验室

出　　处：《水下无人系统学报》2019年第6期695-703,共9页Journal of Unmanned Undersea Systems

基　　金：国家自然科学基金(61071117);重庆市研究生科研创新项目(CYS14151)

摘　　要：针对无人船在复杂环境下完全遍历路径规划算法效率差、普适性低的问题,文中提出了一种基于改进A*算法的无人船完全遍历路径规划方法。首先通过地面站上位机电子地图界面发布任务区域,将该任务区域转换为栅格地图;然后通过内螺旋算法开始对栅格地图进行遍历;最后当无人船陷入死角时,通过改进A*算法搜索最优路径,逃逸死角继续遍历,直到完成所有可达区域的遍历。仿真结果表明,相比现有完全遍历的优化方法,该方法规划的路径步数从814步减少到784步,重复率从优化前的7.8%改善至3.98%,改善了性能指标,具有较好的应用前景。To improve the efficiency and universality of full traversal path planning algorithm for unmanned surface vehicle(USV)in complex environment,a new full traversal path planning algorithm based on the improved A*algorithm is proposed.Firstly,user publishes the task area through the electronic map interface of the host computer in ground station,and converts the task area into a grid map.Then,the grid map is traversed through the inner spiral algorithm.Finally,when the USV is going into the dead angle,optimal path is searched through the improved A*algorithm,and the escape dead angle is traversed until all the reachable areas are traversed.Simulation results show that compared with the existing full traversal optimization method,the proposed algorithm reduces the planned path steps from 814 to 784,and improves the repetition rate from 7.8%to 3.98%.The algorithm improves the performance and has a good application prospect.

关 键 词：无人船 路径规划 完全遍历 A*算法 

分 类 号：U664.82[交通运输工程—船舶及航道工程] TP301.6[交通运输工程—船舶与海洋工程]