基于改进A~*算法的无人航道测量船路径规划方法
|
摘要
无人航道测量船由于具有低成本、高效率、便捷等优点,在航道测量领域受到越来越多的关注。在避碰过程中,为保证无人航道测量船测量数据的有效性,新规划的避碰路线应尽可能地与原规划测量航线一致。针对传统A~*算法所规划的路径在避开障碍物之后无法快速回到预设航线上的问题,提出了一种改进的A~*算法。该算法主要是在原始代价函数的基础上,新增了一个与当前点到预设航线的垂直距离相关的代价值,且该代价值的取值与无人航道测量船所处的位置相关。首先在MATLAB仿真环境下对改进A*算法进行仿真实验,然后利用无人航道测量船实船平台开展航行验证实验并进行围栏分析。实验结果表明,相比于传统A~*算法,在保证安全的前提下,改进A~*算法能够使无人航道测量船在避开障碍物之后更快地回到预设航线。
In recent years, owing to the advantages of low cost, high efficiency and convenience, an unmanned waterway survey ship has received more and more attention in the area of waterway survey. In the process of collision avoidance, reducing the deviation between the newly planned collision avoidance route and the preplanned route is key to complete the waterway survey duties with accurate survey data by an unmanned waterway survey ship. Due to the problem that the path planned by the traditional A~* algorithm cannot quickly approach the preplanned route after obstacle avoidance, an improved A* algorithm is proposed. Based on the original cost function of the A* algorithm, the improved A* algorithm adds a new cost value associated with the vertical distance from the current point to the preplanned route. The value is related to the location of the unmanned waterway survey ship. Firstly, the improved A* algorithm is carried out under the MATLAB simulation environment, and then the actual ship navigation test is carried out by using an unmanned waterway survey ship platform. Moreover, the experimental data are analyzed based on geo-fencing. Experimental results show that compared with the traditional A* algorithm under the premise of safety, the improved A~* algorithm can make the unmanned waterway survey ship approach the preplanned route more quickly after avoiding obstacles.
In recent years, owing to the advantages of low cost, high efficiency and convenience, an unmanned waterway survey ship has received more and more attention in the area of waterway survey. In the process of collision avoidance, reducing the deviation between the newly planned collision avoidance route and the preplanned route is key to complete the waterway survey duties with accurate survey data by an unmanned waterway survey ship. Due to the problem that the path planned by the traditional A~* algorithm cannot quickly approach the preplanned route after obstacle avoidance, an improved A* algorithm is proposed. Based on the original cost function of the A* algorithm, the improved A* algorithm adds a new cost value associated with the vertical distance from the current point to the preplanned route. The value is related to the location of the unmanned waterway survey ship. Firstly, the improved A* algorithm is carried out under the MATLAB simulation environment, and then the actual ship navigation test is carried out by using an unmanned waterway survey ship platform. Moreover, the experimental data are analyzed based on geo-fencing. Experimental results show that compared with the traditional A* algorithm under the premise of safety, the improved A~* algorithm can make the unmanned waterway survey ship approach the preplanned route more quickly after avoiding obstacles.
引文
[1] Li Jialiang. Development and Application of Unmanned Surface Vehicle[J]. Fire Control and Command Control,2012,37(6):203-207(李家良.水面无人艇发展与应用[J].火力与指挥控制,2012,37(6):203-207)
[2] Liu Chenguang,Chu Xiumin,Wu Qing,et al. A Review and Prospect of USV Research[J].Shipbuilding of China,2014,55(4):194-205(柳晨光,初秀民,吴青,等. USV发展现状及展望[J].中国造船,2014,55(4):194-205)
[3] Huang Guoliang,Xu Heng,Xiong Bo,et al. Design of Unmanned Vessel for Inland River Channel Measurement[J]. Port and Waterway Engineering,2016(1):162-168(黄国良,徐恒,熊波,等.内河无人航道测量船系统设计[J].水运工程,2016(1):162-168)
[4] Liu Chenguang,Chu Xiumin,Xie Shuo,et al. Review and Prospect of Ship Intelligence[J]. Ship Engineering,2016(3):77-84(柳晨光,初秀民,谢朔,等.船舶智能化研究现状与展望[J].船舶工程,2016(3):77-84)
[5] Yan Xinping,Liu Chenguang. Review and Prospect for Intelligent Waterway Transportation System[J].CAAI Transactions on Intelligent Systems,2016,11(6):807-817(严新平,柳晨光.智能航运系统的发展现状与趋势[J].智能系统学报,2016,11(6):807-817)
[6] Zhang Lihua,Liu Yanchun,Zhu Qing,et al. Analysis of Feasibility of Routing Based on Changing Water Levels[J]. Geomatics and Information Science of Wuhan University,2008,33(9):892-895(张立华,刘雁春,朱庆,等.基于动态水位的航线可行性分析方法[J].武汉大学学报·信息科学版,2008,33(9):892-895)
[7] Zhu Gengqing. Implementation and Application of A*Algorithm[J]. Fujian Computer,2008(2):74-75(朱耿青. A*算法实现及其应用[J].福建电脑,2008(2):74-75)
[8] Zhan Weiwei,Wang Wei,Chen Nengcheng,et al.Path Planning Strategies for UAV Based on Improved A*Algorithm[J]. Geomatics and Information Science of Wuhan University,2015,40(3):315-320(占伟伟,王伟,陈能成,等.一种利用改进A*算法的无人机航迹规划[J].武汉大学学报·信息科学版,2015,40(3):315-320)
[9] Jasika N,Alispahic N,Elma A,et al. Dijkstra’s Shortest Path Algorithm Serial and Parallel Execution Performance Analysis[C]. The 35th International Convention MIPRO,Opatija,Croatia,2012
[10] Zhu Yi,Zhang Tao,Song Jingyan. Path Planning for Nonholonomic Mobile Robots Using Artificial Potential Field Method[J]. Control Theory and Applications,2010,27(2):152-158(朱毅,张涛,宋靖雁.非完整移动机器人的人工势场法路径规划[J].控制理论与应用,2010,27(2):152-158)
[11] Jiang Longcong,Liu Jiangping. Revised Simulated Annealing Algorithm[J]. Chinese Journal of Engineering Geophysics,2007,4(2):135-140(蒋龙聪,刘江平.模拟退火算法及其改进[J].工程地球物理学报,2007,4(2):135-140)
[12] Ma Yongjie,Yun Wenxia. Research Progress of Genetic Algorithm[J]. Application Research of Computers,2012,29(4):1 201-1 206(马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(4):1 201-1 206)
[13] Reed M,Yiannakou A,Evering R. An Ant Colony Algorithm for the Multi-compartment Vehicle Routing Problem[J]. Applied Soft Computing,2014,15(2):169-176
[14] Liu Kun,Zhang Yonghui,Ren Jia. Path Planning Algorithm for Unmanned Surface Vehicle Based on an Improved Artificial Potential Field Method[J].Natural Science Journal of Hainan University,2016,34(2):99-104(刘琨,张永辉,任佳.基于改进人工势场法的无人船路径规划算法[J].海南大学学报(自然科学版),2016,34(2):99-104)
[15] Chen Jia. The Research of Path Planning Algorithm for Unmanned Rescue Ship[D]. Wuhan:Wuhan University of Technology,2013(陈佳.无人驾驶救助船路径规划算法的研究[D].武汉:武汉理工大学,2013)
[16] Lu Yanshuang. Research on Path Planning Algorithm of Unmanned Surface Vehicle[D]. Harbin:Harbin Engineering University,2010(卢艳爽.水面无人艇路径规划算法研究[D].哈尔滨:哈尔滨工程大学,2010)
[17] Zhu M. A Global Path Planning Algorithm of Unmanned Vessel in Inland Waterway[C]. The International Conference on Transportation Information and Safety,Wuhan,China,2013
[18] Praczyk T,Szymak P. Using Genetic Algorithms to Fix a Route for an Unmanned Surface Vehicle[C].The 17th International Conference on Methods&Models in Automation&Robotics(MMAR),Miedzyzdrojie,Poland,2012
[19] Wu Jingyan,Sui Xin,Sun Yuchang,et al. Designing of the Public Bicycle Anti-Theft System Based on BeiDou and Geo-Fencing[J]. Geomatics Science and Technology,2017,5(3):119-126(吴竞妍,隋芯,孙昱昌,等.基于北斗和地理围栏的公共自行车防盗系统设计[J].测绘科学技术,2017,5(3):119-126)
[2] Liu Chenguang,Chu Xiumin,Wu Qing,et al. A Review and Prospect of USV Research[J].Shipbuilding of China,2014,55(4):194-205(柳晨光,初秀民,吴青,等. USV发展现状及展望[J].中国造船,2014,55(4):194-205)
[3] Huang Guoliang,Xu Heng,Xiong Bo,et al. Design of Unmanned Vessel for Inland River Channel Measurement[J]. Port and Waterway Engineering,2016(1):162-168(黄国良,徐恒,熊波,等.内河无人航道测量船系统设计[J].水运工程,2016(1):162-168)
[4] Liu Chenguang,Chu Xiumin,Xie Shuo,et al. Review and Prospect of Ship Intelligence[J]. Ship Engineering,2016(3):77-84(柳晨光,初秀民,谢朔,等.船舶智能化研究现状与展望[J].船舶工程,2016(3):77-84)
[5] Yan Xinping,Liu Chenguang. Review and Prospect for Intelligent Waterway Transportation System[J].CAAI Transactions on Intelligent Systems,2016,11(6):807-817(严新平,柳晨光.智能航运系统的发展现状与趋势[J].智能系统学报,2016,11(6):807-817)
[6] Zhang Lihua,Liu Yanchun,Zhu Qing,et al. Analysis of Feasibility of Routing Based on Changing Water Levels[J]. Geomatics and Information Science of Wuhan University,2008,33(9):892-895(张立华,刘雁春,朱庆,等.基于动态水位的航线可行性分析方法[J].武汉大学学报·信息科学版,2008,33(9):892-895)
[7] Zhu Gengqing. Implementation and Application of A*Algorithm[J]. Fujian Computer,2008(2):74-75(朱耿青. A*算法实现及其应用[J].福建电脑,2008(2):74-75)
[8] Zhan Weiwei,Wang Wei,Chen Nengcheng,et al.Path Planning Strategies for UAV Based on Improved A*Algorithm[J]. Geomatics and Information Science of Wuhan University,2015,40(3):315-320(占伟伟,王伟,陈能成,等.一种利用改进A*算法的无人机航迹规划[J].武汉大学学报·信息科学版,2015,40(3):315-320)
[9] Jasika N,Alispahic N,Elma A,et al. Dijkstra’s Shortest Path Algorithm Serial and Parallel Execution Performance Analysis[C]. The 35th International Convention MIPRO,Opatija,Croatia,2012
[10] Zhu Yi,Zhang Tao,Song Jingyan. Path Planning for Nonholonomic Mobile Robots Using Artificial Potential Field Method[J]. Control Theory and Applications,2010,27(2):152-158(朱毅,张涛,宋靖雁.非完整移动机器人的人工势场法路径规划[J].控制理论与应用,2010,27(2):152-158)
[11] Jiang Longcong,Liu Jiangping. Revised Simulated Annealing Algorithm[J]. Chinese Journal of Engineering Geophysics,2007,4(2):135-140(蒋龙聪,刘江平.模拟退火算法及其改进[J].工程地球物理学报,2007,4(2):135-140)
[12] Ma Yongjie,Yun Wenxia. Research Progress of Genetic Algorithm[J]. Application Research of Computers,2012,29(4):1 201-1 206(马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(4):1 201-1 206)
[13] Reed M,Yiannakou A,Evering R. An Ant Colony Algorithm for the Multi-compartment Vehicle Routing Problem[J]. Applied Soft Computing,2014,15(2):169-176
[14] Liu Kun,Zhang Yonghui,Ren Jia. Path Planning Algorithm for Unmanned Surface Vehicle Based on an Improved Artificial Potential Field Method[J].Natural Science Journal of Hainan University,2016,34(2):99-104(刘琨,张永辉,任佳.基于改进人工势场法的无人船路径规划算法[J].海南大学学报(自然科学版),2016,34(2):99-104)
[15] Chen Jia. The Research of Path Planning Algorithm for Unmanned Rescue Ship[D]. Wuhan:Wuhan University of Technology,2013(陈佳.无人驾驶救助船路径规划算法的研究[D].武汉:武汉理工大学,2013)
[16] Lu Yanshuang. Research on Path Planning Algorithm of Unmanned Surface Vehicle[D]. Harbin:Harbin Engineering University,2010(卢艳爽.水面无人艇路径规划算法研究[D].哈尔滨:哈尔滨工程大学,2010)
[17] Zhu M. A Global Path Planning Algorithm of Unmanned Vessel in Inland Waterway[C]. The International Conference on Transportation Information and Safety,Wuhan,China,2013
[18] Praczyk T,Szymak P. Using Genetic Algorithms to Fix a Route for an Unmanned Surface Vehicle[C].The 17th International Conference on Methods&Models in Automation&Robotics(MMAR),Miedzyzdrojie,Poland,2012
[19] Wu Jingyan,Sui Xin,Sun Yuchang,et al. Designing of the Public Bicycle Anti-Theft System Based on BeiDou and Geo-Fencing[J]. Geomatics Science and Technology,2017,5(3):119-126(吴竞妍,隋芯,孙昱昌,等.基于北斗和地理围栏的公共自行车防盗系统设计[J].测绘科学技术,2017,5(3):119-126)
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |