Ship Path Planning Based on Sparse A* Algorithm

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.

Keywords

Sparse A* algorithm / Path planning / Rasterization / Coordinate transformation / Image preprocessing

References

[1] 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: https://doi.org/10.26914/c.cnkihy.2019.077835

[2] Chen S, Liu C, Huang Z. Global path planning for AUV based on sparse A* search algorithm. Torpedo Technology, 2012, 20(4): 271-275

[3] Chen X, Bose N, Brito M. Risk-based path planning for autonomous underwater vehicles in an oil spill environment. Ocean Engineering, 2022, 266: 113077.1-113077.13

[4] Chen Z. Using Gauss projection to realize band change of AutoCAD topographic map. Bulletin of Surveying and Mapping, 2020, 525(12): 138-143

[5] Cheng X, Wang F. Agv path planning based on improved A* algorithm. Computer Systems & Applications∣Comput Syst Appl, 2023, 32(3): 180-185

[6] Du Y, Huang J, Zhang H. Multi-direction path planning method of surface unmanned vechicle. Command Control and Simulation, 2021, 43(4): 7-12

[7] Feng H, Hu Q, Zhao Z. AUV swarm path planning based on elite family genetic algorithm. Systems Engineering and Electronics, 2022, 44(7): 2251-2262

[8] Grifoll M, Boren C, Castells-Sanabra M. A comprehensive ship weather routing system using CMEMS products and A* algorithm. Ocean Engineering, 2022, 255: 111427.1-111427.15

[9] 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: https://doi.org/10.13433/j.cnki.1003-8728.20230017

[10] Lee T, Kim H, Chung H. Energy efficient path planning for a marine surface vehicle considering heading angle. Ocean Engineering, 2015, 107: 118-131

[11] Li M, Zhang Y, Li S. The gradational route planning for aircraft stealth penetration based on genetic algorithm and sparse A* algorithm. 2017 Asia Conference on Mechanical and Aerospace Engineering, 2018, 151: 1-5

[12] Li J, Liu Q. Dynamic path planning of unmanned aerial vehicle based on sparse A* algorithm and cultura algorithm. Journal of Applied Sciences, 2017, 35(1): 128-138

[13] Li X, Li H, Liu G, Bian S. Optimization of complex function expansions for Gauss-Krüger projections. ISPRS International Journal of Geo-Information, 2022, 11(11): 566

[14] Li X, Ma X, Wang X. A survey of path algorithms for mobile robots. Computer Measurement and Control, 2022, 30(7): 9-19

[15] Li Y, Duan P, Guo S. Overview of ship global path planning algorithms. Ship Standardization Engineer, 2022, 55(5): 26-30

[16] Li Y, Ma T, Chen P. Autonomous underwater vehicle optimal path planning method for seabed terrain matching navigation. Ocean Engineering, 2017, 133: 107-115

[17] Li Z, Shi R, Zhang Z. A new path planning method based on sparse A* algorithm with map segmentation. Transactions of the Institute of Measurement and Control, 2022, 44(4): 916-925

[18] 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

[19] Miao C, Chen G, Yan C, Wu Y. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Computers & Industrial Engineering, 2021, 156(8): 107230-107230

[20] Miao T, El Amam E, Slaets P. An improved real-time collision-avoidance algorithm based on hybrid A* in a multi-object-encountering scenario for autonomous surface vessels. Ocean Engineering, 2022, 255: 111406.1-111406.15

[21] Phanthong T, Maki T, Ura T, Sakamaki T, Aiyarak P. Application of A* algorithm for real-time path re-planning of an unmanned surface vehicle avoiding underwater obstacles. Journal of Marine Science and Application, 2014, 13(1): 105-116

[22] Qi J, Yang H, Sun H. MOD-RRT*: A sampling-based algorithm for robot path planning in dynamic environment. IEEE Transactions on Industrial Electronics, 2020, 68(8): 7244-7251

[23] Sang H, You Y, Sun X. The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations. Ocean Engineering, 2021, 223: 108709.1-108709.16

[24] Sedeno-noda A, Colebrook M. A biobjective Dijkstra algorithm. European Journal of Operational Research, 2019, 276(1): 106-118

[25] Singh Y, Sharma S, Sutton R. 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, 2018, 168: 187-201

[26] Thi T, Copot C, Duc T, De K. A hierarchical global path planning approach for mobile robots based on multiobjective particle swarm optimization. Applied Soft Computing, 2017, 59(68–76): 68-76

[27] Wang S, Long T, Wang Z. Dynamic path planning using anytime repairing sparse A* algorithm. Systems Engineering and Electronics, 2018, 40(12): 2714-2721

[28] Wei Y, Jin F, Dong K. Improved global path planning A* algorithm based on node optimization. Computer Measurement and Control, 2023, 31(6): 1-11

[29] Xie L, Xue S, Huang L. Draught monitoring based on contour cluster analysis. Navigation of China, 2018, 41(1): 60-63

[30] Ying Z, He Q. Unmanned vehicle path planning in complex waters based on improved A* algorithm. Mechanical & Electrical Technology, 2022, 144(5): 33-35

[31] Zhou S, Wang W, Tang J. Improved sparse A* trajectory planning exploration incorporated with pheromone. Electronics Optics & Control, 2021, 28(11): 26-30

[32] Zhou X, Zhou Y, Xu L. A path planning algorithm for lunar cover based on probabilistic roadmap. Aerospace Control and Application, 2020, 46(6): 43-49

[33] Zhu K. Research and application of image segmentation based on improved FCM algorithm. Journal of Chongqing Technology and Business University (Natural Science Edition), 2022, 39(5): 24-33