|Table of Contents|

Citation:
　Yongjian Zhai,Jianhui Cui,Fanbin Meng,et al.Ship Path Planning Based on Sparse A* Algorithm[J].Journal of Marine Science and Application,2025,(1):238-248.[doi:10.1007/s11804-024-00430-5]
Click and Copy

Ship Path Planning Based on Sparse A* Algorithm

Info

Title:
Ship Path Planning Based on Sparse A* Algorithm
Author(s):
Yongjian Zhai1;  Jianhui Cui1;  Fanbin Meng2;  Huawei Xie2;  Chunyan Hou2;  Bin Li2
Affilations:
Author(s):
Yongjian Zhai1;  Jianhui Cui1;  Fanbin Meng2;  Huawei Xie2;  Chunyan Hou2;  Bin Li2
1. Maritime College, Tianjin University of Technology, Tianjin 300384, China;
2. Tianjin Navigation Instrument Research Institute, Tianjin 300131, China
Keywords:
Sparse A* algorithm; Path planning; Rasterization; Coordinate transformation; Image preprocessing
分类号:
-
DOI:
10.1007/s11804-024-00430-5
Abstract:
An improved version of the sparse A* algorithm is proposed to address the common issue of excessive expansion of nodes and failure to consider current ship status and parameters in traditional path planning algorithms. This algorithm considers factors such as initial position and orientation of the ship, safety range, and ship draft to determine the optimal obstacle-avoiding route from the current to the destination point for ship planning. A coordinate transformation algorithm is also applied to convert commonly used latitude and longitude coordinates of ship travel paths to easily utilized and analyzed Cartesian coordinates. The algorithm incorporates a hierarchical chart processing algorithm to handle multilayered chart data. Furthermore, the algorithm considers the impact of ship length on grid size and density when implementing chart gridification, adjusting the grid size and density accordingly based on ship length. Simulation results show that compared to traditional path planning algorithms, the sparse A* algorithm reduces the average number of path points by 25%, decreases the average maximum storage node number by 17%, and raises the average path turning angle by approximately 10°, effectively improving the safety of ship planning paths.

References:

Bi T, Ye P, Xu Y, Zhang F (2019) Route planning of unmanned aerial vehicle based on sparse A* algorithm. Proceedings of 2019 International Conference on Informatics, Control and Robotics (ICICR 2019), Shanghai, China, 31-37. DOI: 10.26914/c.cnkihy.2019.077835
Chen S, Liu C, Huang Z (2012) Global path planning for AUV based on sparse A* search algorithm. Torpedo Technology 20(4): 271-275. DOI: 10.3969/j.issn.1673-1948.2012.04.007
Chen X, Bose N, Brito M (2022) Risk-based path planning for autonomous underwater vehicles in an oil spill environment. Ocean Engineering 266: 113077.1-113077.13. DOI: 10.1016/j.oceaneng.2022.113077
Chen Z (2020) Using Gauss projection to realize band change of AutoCAD topographic map. Bulletin of Surveying and Mapping 525(12): 138-143. DOI: 10.13474/j.cnki.11-2246.2020.0409
Cheng X, Wang F (2023) Agv path planning based on improved A* algorithm. Computer Systems & Applications∣Comput Syst Appl 32(3): 180-185. DOI: 10.15888/j.cnki.csa.009020
Du Y, Huang J, Zhang H (2021) Multi-direction path planning method of surface unmanned vechicle. Command Control and Simulation 43(4): 7-12. DOI:https://doi.org/10.3969/j.issn.1673-3819.2021.04.002
Feng H, Hu Q, Zhao Z (2022) AUV swarm path planning based on elite family genetic algorithm. Systems Engineering and Electronics 44(7): 2251-2262. DOI: 10.12305/j.issn.1001-506X.2022.07.21
Grifoll M, Boren C, Castells-Sanabra M (2022) A comprehensive ship weather routing system using CMEMS products and A* algorithm. Ocean Engineering 255: 111427.1-111427.15. DOI: 10.1016/j.oceaneng.2022.111427
Hu S, Wu M, Shi J (2023) Research on improved A* algorithm integrating vector cross-product and jump point search strategy. Mechanical Science and Technology for Aerospace Engineering: 1-10. DOI: 10.13433/j.cnki.1003-8728.20230017
Lee T, Kim H, Chung H (2015) Energy efficient path planning for a marine surface vehicle considering heading angle. Ocean Engineering 107: 118-131. DOI: 10.1016/j.oceaneng.2015.07.030
Li M, Zhang Y, Li S (2018) The gradational route planning for aircraft stealth penetration based on genetic algorithm and sparse A* algorithm. 2017 Asia Conference on Mechanical and Aerospace Engineering, 151: 1-5. DOI: 10.1051/matecconf/201815104001
Li J, Liu Q (2017) Dynamic path planning of unmanned aerial vehicle based on sparse A* algorithm and cultura algorithm. Journal of Applied Sciences 35(1): 128-138. DOI: 10.3969/j.issn.0255-8297.2017.01.014
Li X, Li H, Liu G, Bian S (2022a) Optimization of complex function expansions for Gauss-Krüger projections. ISPRS International Journal of Geo-Information 11(11): 566. DOI: 10.3390/ijgi11110566
Li X, Ma X, Wang X (2022b) A survey of path algorithms for mobile robots. Computer Measurement and Control 30(7): 9-19. DOI: 10.16526/j.cnki.11-4762/tp.2022.07.002
Li Y, Duan P, Guo S (2022c) Overview of ship global path planning algorithms. Ship Standardization Engineer 55(5): 26-30+55. DOI: 10.14141/j.31-1981.2022.05.004
Li Y, Ma T, Chen P (2017) Autonomous underwater vehicle optimal path planning method for seabed terrain matching navigation. Ocean Engineering 133: 107-115. DOI: 10.1016/j.ocean-eng.2017.01.026
Li Z, Shi R, Zhang Z (2022d) A new path planning method based on sparse A* algorithm with map segmentation. Transactions of the Institute of Measurement and Control 44(4): 916-925. DOI:https://doi.org/10.1177/01423312211046410
DWA algorithm for mobile robot path planning. Computer Integrated Manufacturing Systems: 1-20. http://kns.cnki.net/kcms/detail/11.5946.TP.20221125.1957.004.html
Miao C, Chen G, Yan C, Wu Y (2021) Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Computers & Industrial Engineering 156(8): 107230-107230. DOI: 10.1016/j.cie.2021.107230
Miao T, El Amam E, Slaets P (2022) An improved real-time collision-avoidance algorithm based on hybrid A* in a multi-object-encountering scenario for autonomous surface vessels. Ocean Engineering 255: 111406.1-111406.15. DOI: 10.1016/j.oceaneng.2022.111406
Phanthong T, Maki T, Ura T, Sakamaki T, Aiyarak P (2014) Application of A* algorithm for real-time path re-planning of an unmanned surface vehicle avoiding underwater obstacles. Journal of Marine Science and Application 13(1): 105-116. DOI: 10.1007/s11804-014-1224-3
Qi J, Yang H, Sun H (2020) MOD-RRT*: A sampling-based algorithm for robot path planning in dynamic environment. IEEE Transactions on Industrial Electronics 68(8): 7244-7251. DOI: 10.1109/TIE.2020.2998740
Sang H, You Y, Sun X (2021) The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations. Ocean Engineering 223: 108709.1-108709.16. DOI: 10.1016/j.oceaneng.2021.108709
Sedeno-noda A, Colebrook M (2019) A biobjective Dijkstra algorithm. European Journal of Operational Research 276(1): 106-118. DOI: 10.1016/j.ejor.2019.01.007
Singh Y, Sharma S, Sutton R (2018) A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents. Ocean Engineering 168:187-201. DOI:https://doi.org/10.1016/j.oceaneng
Thi T, Copot C, Duc T, De K (2017) A hierarchical global path planning approach for mobile robots based on multiobjective particle swarm optimization. Applied Soft Computing 59(68-76): 68-76. DOI: 10.1016/j.asoc.2017.05.012
Wang S, Long T, Wang Z (2018) Dynamic path planning using anytime repairing sparse A* algorithm. Systems Engineering and Electronics 40(12): 2714-2721. DOI: 10.3969/j.issn.1001-506X.2018.12.14
Wei Y, Jin F, Dong K (2023) Improved global path planning A* algorithm based on node optimization. Computer Measurement and Control 31(6): 1-11. DOI: 10.3969/j.issn.1005-1228.2022.02.002
Xie L, Xue S, Huang L (2018) Draught monitoring based on contour cluster analysis. Navigation of China 41(1): 60-63+108. DOI: 10.3969/j.issn.1000-4653.2018.01.012
Ying Z, He Q (2022) Unmanned vehicle path planning in complex waters based on improved A* algorithm. Mechanical & Electrical Technology 144(5): 33-35. DOI: 10.19508/j.cnki.1672-4801.2022.05.010
Zhou S, Wang W, Tang J (2021) Improved sparse A* trajectory planning exploration incorporated with pheromone. Electronics Optics & Control 28(11): 26-30. DOI: 10.3969/j.issn.1671-637X.2021.11.006
Zhou X, Zhou Y, Xu L (2020) A path planning algorithm for lunar cover based on probabilistic roadmap. Aerospace Control and Application 46(6): 43-49+78. DOI: 10.3969/j.issn.1674-1579.2020.06.006
Zhu K (2022) Research and application of image segmentation based on improved FCM algorithm. Journal of Chongqing Technology and Business University (Natural Science Edition) 39(5): 24-33. DOI: 10.16055/j.issn.1672-058X.2022.0005.004

Memo

Memo:
Received date:2023-5-4;Accepted date:2023-11-7。
Foundation item:Supported by the Tianjin University of Technology Graduate R esearch Innovation Project (YJ2281).
Corresponding author:Jianhui Cui,E-mail:jianhuicui@email.tjut.edu.cn
Last Update: 2025-02-26