Inland lake unmanned boat path planning based on improved A* algorithm

LIN Tanqi, LI Cunrong, LIU Shuaiwen

doi:10.16411/j.cnki.issn1006-7736.2024.03.010

Journal of Dalian Maritime University >

2024 , Vol. 50 >Issue 3: 87 - 96

DOI: https://doi.org/10.16411/j.cnki.issn1006-7736.2024.03.010

Inland lake unmanned boat path planning based on improved A* algorithm

Expand

(1.School of Mechanical and Electronic Engineering, Wuhan University of Technology, Wuhan 430070；2.Industrial Research Institute of Suizhou Wuhan University of Technology，Suizhou 441399，China)

Online published: 2024-04-29

Fold

Abstract

An improved A* and path smoothing algorithm was proposed to overcome the defects of A* based paths for unmanned boats in inland lake environments including collision avoidance insufficiency, maneuver redundancy, and steering non-smoothness. Firstly, the evaluation function was enhanced by incorporating obstacle avoidance and steering costs. Secondly, the redundant path of the A* algorithm was removed by iteratively generating the segmentations in a reversal manner. Finally, the steering trajectory was further optimized by addressing steering performance of the unmanned boat. Simulation experiments on a real inland lake map show that the improved algorithm significantly reduces the collision probability, steering angle and traveling distance, simultaneously, and thereby improving the steering performance of the unmanned boat.

Key words： unmanned vessel; A* algorithm; cyclotron performance; path smoothing

Cite this article

LIN Tanqi, LI Cunrong, LIU Shuaiwen . Inland lake unmanned boat path planning based on improved A* algorithm[J]. Journal of Dalian Maritime University, 2024 , 50(3) : 87 -96 . DOI: 10.16411/j.cnki.issn1006-7736.2024.03.010

References

[1]刘蔚,谈果戈,邹劲等.基于快速行进平方法的水面无人船路径规划[J].信息与控制,2021,50(03):308-320.

LIU W, TAN G G, ZOU J, et al. Fast Marching Square Method Based Path Planning of the Unmanned Surface Vehicle[J]. Information and Control, 2021, 50(03): 308-320. (in Chinese)

[2]高鹏程. 内河无人船路径规划研究[D].江苏：江苏科技大学,2023.

GAO P C. Research on path planning of unmanned surface vehicle in inland waters [D].Jiangsu: Jiangsu University of Science and Technology,2023. (in Chinese)

[3]朱大庆. 基于改进哈里斯鹰算法的复杂水域船舶路径规划[D].大连：大连海事大学,2023.

ZHU D Q. Ship Path Planning in Complicated Water Areas Based on Improved Harris Hawk Optimization Algorithm [D].Dalian: Dalian Maritime University, 2023. (in Chinese)

[4]张浩,庞宁林,胡安康等. 基于改进A~*算法融合角度信息的船舶路径规划 [J]. 上海海事大学学报, 2023, 44 (02): 6-10.

ZHANG H, PANG N L, HU A K, et al. Ship path planning based on improved A* algorithm and adding angle information [J]. Journal of Shanghai Maritime University, 2023, 44 (02): 6-10. (in Chinese)

[5]张树凯,刘正江,蔡垚等.无人船艇航线自动生成研究现状及展望[J].中国航海,2019,42(03):6-11.

ZHANG S K,LIU Z J,CAI Y, et al. Review on Automatic Routing Technologies for Unmanned Vehicles [J]. Navigation of China, 2019, 42(03): 6-11. (in Chinese)

[6]WANG N, ZHANG Y, AHN C K, et al. Autonomous Pilot of Unmanned Surface Vehicles: Bridging Path Planning and Tracking, IEEE Transactions on Vehicular Technology, vol. 71, no. 3, pp. 2358-2374, March 2022

[7]肖娟娟,张金奋,吴达等.动态海冰状态下极地船舶改进D~*Lite路径规划方法[J].大连海事大学学报, 2023,49(04):20-27+36.

XIAO J J, ZHANG F J, WU D, et al. An improved D*Lite path planning methodology for polar ships under dynamic ice conditions [J]. Journal of Dalian Maritime University, 2019, 42(03): 6-11. (in Chinese)

[8]郭晓宇, 鲁旭涛.基于LPA*优化算法的察打一体无人机远距离飞行航线规划[J].战术导弹技术, 2023(04): 148-155+164.

GUO X Y, LU X T. Long-distance flight route planning of surveillance and strike integrated UAV based on LPA* optimization algorithm [J]. Tactical Missile Technology, 2023(04): 148-155+164. (in Chinese)

[9]刘浩. 基于改进粒子群法的船舶路径规划研究[D].江苏：江苏科技大学, 2023.

LIU H. Research on ship route planning based on improved particle swarm optimization [D]. Jiangsu: Jiangsu University of Science and Technology, 2023. (in Chinese)

[10]SAHU C, PARHI D R, KUMAR P B. An Approach to Optimize the Path of Humanoids using Adaptive Ant Colony Optimization[J]. Journal of Bionic Engineering, 2018, 15(4).

[11]王璇.遗传算法的改进及其应用研究[D].北京：华北电力大学（北京）.

WANG X. The Studies on the Improvement of Genetic Algorithm and Application [D]. Beijing: North China Electric Power University. (in Chinese)

[12]阮晓钢,周静,张晶晶等.基于子目标搜索的机器人目标导向RRT路径规划算法[J].控制与决策, 2020, 35(10): 2543-2548.

RUAN X G, ZHOU J, ZHANG J J, et al. Robot goal guide RRT path planning based on sub-target search [J]. Control and Decision,2020,35(10):2543-2548. (in Chinese)

[13]魏阁安,张建强.基于改进动态窗口法的无人艇编队集结研究[J].舰船科学技术,2023,45(23):91-95+99.

WEI A G,ZHANG J Q. Research on USV formation aggregation based on improved DWA algorithm [J]. Ship Science and Technology,2023,45(23):91-95+99. (in Chinese)

[14]王征,杨洋,周帅等.基于A*-动态窗口法的无人船动态路径规划算法[J/OL].海军工程大学学报:1-7[2024-03-04].

WANG Z,YANG Y,ZHOU S ,et al. Dynamic path planning algorithm of unmanned ship based on A*-dynamic window approach [J/OL]. Journal of Naval University of Engineering:1-7[2024-03-04]. (in Chinese)

[15]贾薇,王宁,张富宇等.基于多传感器融合SLAM的无人船靠泊技术[J].大连海事大学学报,2023,49(04):65-75.

JIA W, WANG N, ZHANG F Y, et al. Unmanned surface vehicle berthing technology based on multi-sensor fusion SLAM [J]. Journal of Dalian Maritime University,2023,49(04):65-75. (in Chinese)

[16]BING F, LIN C, ZHOU Y T, et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics & Autonomous Systems, 2018, 106.

[17]王殿君. 基于改进A~*算法的室内移动机器人路径规划 [J]. 清华大学学报(自然科学版), 2012, 52 (08): 1085-1089.

WANG D J. Indoor mobile-robot path planning based on an improved A* algorithm [J]. Journal of Tsinghua University (Science and Technology), 2012, 52 (08): 1085-1089. (in Chinese)

[18]崔金龙,李元奎,索基源等. 基于改进A~*算法的船舶航向航速协同优化方法 [J]. 大连海事大学学报, 2022, 48 (04): 29-37+47.

CUI J L, LI Y K, SUO J Y, et al. Collaborative optimization method of ship course and speed based on improved A* algorithm [J]. Journal of Dalian Maritime University, 2022, 48 (04): 29-37+47. (in Chinese)

[19]王远渊.基于Simulink的ULOC旋回降速仿真研究[J].电子测试,2013(07):92-93.

WANG Y Y. Speed simulation research based on Simulink in ULOC cycles [J]. Electronic Test, 2013(07): 92-93. (in Chinese)

[20]李纪强,张国庆.浅析船舶旋回过程及MATLAB仿真[J].船舶,2021,32(02):16-22.

LI J Q, ZHANG G Q. Analysis of Ship Turning Process and MATLAB Simulation [J]. Ship & Boat, 2021, 32(02): 16-22. (in Chinese)

[21]赵春宇,姜皓,徐茂竹等.改进A*算法在无人船路径规划中的应用[J].浙江工业大学学报,2022,50(06):615-620.

ZHAO C Y, JIANG H, XU M Z, et al. Application of improved A algorithm in unmanned ship path planning [J]. Journal of Zhejiang University of Technology, 2022, 50(06): 615-620. (in Chinese)

[22]谢凤云,金雁. 乌江航道千吨级船舶K、T指数计算方法 [J]. 造船技术, 2021, 49 (03): 6-10.

XIE F Y, JIN Y. K and T Indices Calculation Method of Kiloton Ship on Wujiang River Waterway [J]. Marine Technology, 2021, 49 (03): 6-10. (in Chinese)

[23]安礼瑞,刘梦薇,刘甜等.基于BP神经网络的船舶旋回运动仿真研究[J].广州航海学院学报, 2022, 30(03): 16-21.

AN R L, LIU M W, LIU T, et al. Modeling of Ship Turning Motion Simulation Based on BP Neural Network [J]. Journal of Guangzhou Maritime University, 2022, 30(03): 16-21. (in Chinese)

[24]翟宏睿,罗亮,杨萌等.基于最大熵强化学习的自主船舶航迹跟踪研究[J].舰船科学技术,2023,45(23):78-84.

ZHAI H R, LUO L, YANG M, et al. Research on autonomous ship track tracking based on maximum entropy reinforcement learning [J]. Ship Science and Technology,2023,45(23):78-84. (in Chinese)

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

References