Obstacle Avoidance for Ship Navigation Safety Combining Heuristic Search Algorithm and Improved ACO Algorithm

Dan Wang; Yan  Jing

doi:10.61089/aot2024.0ycg1622

Authors

Dan Wang College of Maritime, Beibu Gulf University, Qinzhou, China Author https://orcid.org/0009-0006-1475-5131
Yan Jing College of Maritime, Beibu Gulf University, Qinzhou, China Author https://orcid.org/0009-0008-2876-4607

DOI:

https://doi.org/10.61089/aot2024.0ycg1622

Keywords:

ACO algorithm, a* algorithm, ship navigation, obstacles, path planning

Abstract

The safety of ship navigation has always been a focus of attention in the field of maritime transport and navigation. In the complex marine environment, ships face a variety of obstacles, such as other ships, reefs, buoys, etc., which may pose a threat to navigation safety. Traditional obstacle avoidance methods mainly rely on the navigator's empirical judgement, but there are limitations and risks associated with this method. The standard ant colony optimisation algorithm tends to fall into local optimal solutions during path search, while the A* algorithm is easily limited by the search space when dealing with large-scale problems. Therefore, the study proposes a method that combines a heuristic search algorithm and an improved ACO algorithm to improve the efficiency of obstacle avoidance for vessel navigation safety. Firstly, the standard ant colony optimisation algorithm is improved and applied to the study of obstacle avoidance paths for vessel navigation, and then the A* algorithm is effectively combined with the improved ACO algorithm to improve the performance of planning obstacle avoidance paths. Through simulation experiments and practical applications, the study verifies the capability of the obstacle avoidance planning model. The experimental results show that in simple environments, the hybrid algorithm reduces the path length by 3.8 and 5.5, and the number of iterations by 13.2 and 30.7 compared to Line-of-Sight and Particle Swarm Optimisation algorithms respectively. In moderately complex environments, the proposed algorithm reduces the average path length by 6.51 and 3.93 compared to Particle Swarm Optimisation and Line-of-Sight algorithms respectively. In complex environments, the proposed algorithm reduces the average path length by 15.7 and 12.4 compared to Particle Swarm Optimisation and Line-of-Sight algorithms, and reduces the number of iterations by 49 and 22.2, respectively. The study proposes a novel obstacle avoidance path planning method by effectively integrating the improved ant colony algorithm with the A* algorithm, which significantly improves the efficiency and accuracy of vessel navigation safety. The results show that the hybrid algorithm exhibits superior path planning capability in environments of varying complexity, and is able to quickly adapt to dynamically changing marine environments. This method not only provides a new solution for navigation safety, but also provides a theoretical basis and practical guidance for future autonomous navigation and decision-making of intelligent ships, which has important application value and promotion potential.

References

1. Ai, W. Z., Zhu, P. (2020) Navigation ship's drift angle determination method in curved channel. Journal of Coastal Research. 109(SI): 181-184. https://doi.org/10.2112/JCR-SI109-029.1.

2. Chen, G., Wu, T., Zhou, Z. (2021) Research on ship meteorological route based on A-star algo-rithm. Mathematical Problems in Engineering. 21(22): 1-8. https://doi.org/10.1155/2021/9989731.

3. Chen, Y., Bai, G., Zhan, Y., et al. (2021) Path planning and obstacle avoiding of the USV based on improved ACO-APF hybrid algorithm with adaptive early-warning. IEEE Access. 9(6): 40728-40742. https://doi.org/10.1109/ACCESS.2021.3062375.

4. Gao, P., Zhou, L., Zhao, X., et al. (2023) Research on ship collision avoidance path planning based on modified potential field ant colony algorithm. Ocean & Coastal Management. 235(5): 1-15. https://doi.org/10.1016/j.ocecoaman.2023.106482.

5. Grifoll, M., Borén, C., Castells-Sanabra, M. (2022) A comprehensive ship weather routing system using CMEMS products and A* algorithm. Ocean Engineering. 255(4): 1-15. https://doi.org/10.1016/j.oceaneng.2022.111427.

6. He, Y., Li, Z., Mou, J., et al. (2021) Collision-avoidance path planning for multi-ship encounters considering ship manoeuvrability and COLREGs. Transportation safety and environment. 3(2): 103-113. https://doi.org/10.1093/tse/tdab004.

7. Islam, A., Othman, F., Sakib, N., et al. (2023) Prevention of shoulder-surfing attack using shifting condition with the digraph substitution rules. Artificial Intelligence and Applications. 1(1): 58-68. https://doi.org/10.47852/bonviewAIA2202289.

8. Liang, C., Zhang, X., Han X. (2020) Route planning and track kee control for ships based on the leader-vertex ant colony and nonlinear feedback algorithms. Applied Ocean Research. 101(9): 1-18. https://doi.org/10.1016/j.apor.2020.102239.

9. Liao, H., Wang, W., Wang, S., et al. (2020) Multi-scale ship tracking based on maritime monitoring platform. 2020 15th IEEE Conference on Industrial Electronics and Applications (ICIEA). 15(9): 945-949. https://doi.org/10.1109/ICIEA48937.2020.9248235.

10. Liu, J., Jiang, X., Huang, W., et al. (2022) A novel approach for navigational safety evaluation of inland waterway ships under uncertain environment. Transportation Safety and Environment. 4(1): 29-39. https://doi.org/10.1093/tse/tdab029.

11. Liu, Z., Li, Y., Zhang, Z., et al. (2023) Spatial modeling and analysis based on spatial information of the ship encounters for intelligent navigation safety. Reliability Engineering & System Safety. 238(10): 1-26. https://doi.org/10.1016/j.ress.2023.109489.

12. Öztürk, Ü., Boz, H. A., Balcisoy, S. (2021) Visual analytic based ship collision probability model-ing for ship navigation safety. Expert Systems with Applications. 175(8): 1-17. https://doi.org/10.1016/j.eswa.2021.114755.

13. Wang, A., Zhi, P., Zhu, W., et al. (2021) Path planning of unmanned surface vehicle based on a algorithm optimization considering the influence of risk factors. 2021 4th IEEE International Con-ference on Industrial Cyber-Physical Systems (ICPS). 4(9): 810-815. https://doi.org/10.1109/ICPS49255.2021.9468142.

14. Wei, Y. (2020) Design of ship navigation trajectory analysis and application system based on im-age processing technology. Journal of Coastal Research. 115(SI): 211-213. https://doi.org/10.2112/JCR-SI115-066.1.

15. Yin, J. K., Fu, W. P. (2021) A safety navigation method for integrating global path planning and local obstacle avoidance for self-driving cars in a dynamic environment. Scientia Iranica. 28(3): 1318-1328. https://doi.org/10.24200/SCI.2020.52417.2704.

16. Yu, H., Murray, A. T., Fang, Z., et al. (2021) Ship path optimization that accounts for geographical traffic characteristics to increase maritime port safety. IEEE Transactions on Intelligent Transpor-tation Systems. 23(6): 5765-5776. https://doi.org/10.1109/TITS.2021.3057907.

17. Yu, J., Hou, J., Chen, G. (2020) Improved safety-first A-star algorithm for autonomous vehicles. 2020 5th International Conference on Advanced Robotics and Mechatronics (ICARM). 5(9): 706-710. https://doi.org/10.1109/ICARM49381.2020.9195318.

18. Yuan, M., Shi, H. (2021) An ant colony algorithm model for UAV sense and avoid based on ADS-B. Journal of Northwestern Polytechnical. 39(4): 761-769. https://doi.org/10.1051/jnwpu/20213940761.

19. Zhang, G., Wang, H., Zhao, W., et al. (2021) Application of improved multi-objective ant colony optimization algorithm in ship weather routing. Journal of Ocean University of China. 20(1): 45-55. https://doi.org/10.1007/s11802-021-4436-6.

20. Zhang, L., Zhang, Y., Zeng, M., et al. (2021) Robot navigation based on improved A* algorithm in dynamic environment. Assembly Automation. 41(4): 419-430. https://doi.org/10.1108/AA-07-2020-0095.

21. Zhang, X., Wang, J., Chen, Y., et al. (2020) Density-weighted ant colony algorithm for ship trajec-tory reconstruction. International Journal of Shipping and Transport Logistics. 12(1-2): 19-38. https://doi.org/10.1504/IJSTL.2020.105851.