Multi-Ship Collision Avoidance Method based on Markov Decision Process

Authors

Keywords:

autonomous navigation, collision avoidance, colreg rules, decision-process, grid-world, markov property, optimization, policy search, safe trajectory, ship motion, value iteration

Abstract

The maritime industry has been incorporating advanced technology to enhance mission planning and ensure safe navigation, including autonomous collision avoidance systems that follow International Regulations for Preventing Collisions at Sea (COLREG). Ongoing research in this field encompasses a wide range of approaches, from optimal control analysis to heuristic and metaheuristic methods, and solutions based on artificial intelligence. In this study, we propose an autonomous collision avoidance algorithm for ships based on Markov decision process. This work focuses on the development of a COLREG-compliant autonomous collision avoidance algorithm for ships using a Markov decision process. The algorithm considers the subject ship's position and aims to resolve potential collision conflicts with target ships while keeping the vessel on its initial trajectory, in compliance with regulations. The system is modeled as a Markov decision process using the ship's three coordinates position as states, actions generated from degrees-of-freedom, and constraints such as safe path, trip cost, and respect for rules to design the reward. The proposed policy search algorithm is implemented using python and its convergence and efficiency are tested through multiple scenarios.

Downloads

Download data is not yet available.

References

A. Miller, “Model Predictive Control of the ship’s motion in presence of wind disturbances,” Zesz. Nauk. Morska W Szczecinie, no. 39 (111), pp. 107–115, 2014.

M. Breivik, “MPC-based mid-level collision avoidance for ASVs using nonlinear programming,” presented at the 2017 IEEE Conference on Control Technology and Applications (CCTA), 2017, pp. 766–772.

I. B. Hagen, D. K. M. Kufoalor, E. F. Brekke, and T. A. Johansen, “MPC-based collision avoidance strategy for existing marine vessel guidance systems,” presented at the 2018 IEEE International Conference on Robotics and Automation (ICRA), 2018, pp. 7618–7623.

M.-C. Tsou and C.-K. Hsueh, “The study of ship collision avoidance route planning by ant colony algorithm,” J. Mar. Sci. Technol., vol. 18, no. 5, p. 16, 2010.

A. Lazarowska, “Swarm intelligence approach to safe ship control,” Pol. Marit. Res., vol. 22, no. 4, pp. 34–40, 2015.

Y. Zhao, W. Li, S. Feng, W. Y. Ochieng, and W. Schuster, “An improved differential evolution algorithm for maritime collision avoidance route planning,” presented at the Abstract and Applied Analysis, 2014, vol. 2014.

S. Xie, X. Chu, M. Zheng, and C. Liu, “A composite learning method for multi-ship collision avoidance based on reinforcement learning and inverse control,” Neurocomputing, vol. 411, pp. 375–392, 2020.

S. Temizer, M. Kochenderfer, L. Kaelbling, T. Lozano-Pérez, and J. Kuchar, “Collision avoidance for unmanned aircraft using Markov decision processes,” presented at the AIAA guidance, navigation, and control conference, 2010, p. 8040.

H. Y. Ong and M. J. Kochenderfer, “Markov decision process-based distributed conflict resolution for drone air traffic management,” J. Guid. Control Dyn., vol. 40, no. 1, pp. 69–80, 2017.

M. J. Kochenderfer and J. P. Chryssanthacopoulos, “Collision avoidance using partially controlled Markov decision processes,” presented at the Agents and Artificial Intelligence: Third International Conference, ICAART 2011, Rome, Italy, January, 28-30, 2011. Revised Selected Papers 3, 2013, pp. 86–100.

M. Li, H. Bai, and N. Krishnamurthi, “A markov decision process for the interaction between autonomous collision avoidance and delayed pilot commands,” IFAC-Pap., vol. 51, no. 34, pp. 378–383, 2019.

Y. Fu, X. Yu, and Y. Zhang, “Sense and collision avoidance of unmanned aerial vehicles using Markov decision process and flatness approach,” presented at the 2015 IEEE International Conference on Information and Automation, 2015, pp. 714–719.

W. Wang, L. Huang, K. Liu, X. Wu, and J. Wang, “A COLREGs-Compliant Collision Avoidance Decision Approach Based on Deep Reinforcement Learning,” J. Mar. Sci. Eng., vol. 10, no. 7, p. 944, 2022.

X. Ding, S. L. Smith, C. Belta, and D. Rus, “Optimal control of Markov decision processes with linear temporal logic constraints,” IEEE Trans. Autom. Control, vol. 59, no. 5, pp. 1244–1257, 2014.

A. U. Udom, “A Markov decision process approach to optimal control of a multi-level hierarchical manpower system,” CBN J. Appl. Stat., vol. 4, no. 2, pp. 31–49, 2013.

T. I. Fossen, Handbook of marine craft hydrodynamics and motion control. John Wiley & Sons, 2011.

I. Scholberg, “Modeling and control of underwater vehicle-manipulator systems,” presented at the Proc. Conf. Marine Craft Maneuvering and Control, Southampton, UK, 1994, 1994.

M. Zhu, A. Hahn, Y.-Q. Wen, and W.-Q. Sun, “Optimized support vector regression algorithm-based modeling of ship dynamics,” Appl. Ocean Res., vol. 90, p. 101842, 2019.

Y. Melhaoui, A. Kamil, M. Riouali, K. Mansouri, and M. Rachik, “Optimal control of ship collision avoidance problem,” J Math Comput Sci, vol. 12, p. Article-ID, 2022.

M. Abdelaal, M. Fränzle, and A. Hahn, “Nonlinear Model Predictive Control for trajectory tracking and collision avoidance of underactuated vessels with disturbances,” Ocean Eng., vol. 160, pp. 168–180, 2018.

E. L. Porteus, “Stochastic inventory theory,” Handb. Oper. Res. Manag. Sci., vol. 2, pp. 605–652, 1990.

F. Garcia and E. Rachelson, “Markov decision processes,” Markov Decis. Process. Artif. Intell., pp. 1–38, 2013.

H. S. Chang, J. Hu, M. C. Fu, and S. I. Marcus, Simulation-based algorithms for Markov decision processes, vol. 68. Springer, 2013.

J. Lisowski, “Computational intelligence methods of a safe ship control,” Procedia Comput. Sci., vol. 35, pp. 634–643, 2014.

X. Yu, X. Zhou, and Y. Zhang, “Collision-free trajectory generation and tracking for UAVs using Markov decision process in a cluttered environment,” J. Intell. Robot. Syst., vol. 93, pp. 17–32, 2019.

Maneuvers required for various COLREG situations.

Downloads

Published

17.02.2023

How to Cite

Melhaoui, Y. ., Kamil, A. ., Mansouri, K. ., & Rachik, M. . (2023). Multi-Ship Collision Avoidance Method based on Markov Decision Process. International Journal of Intelligent Systems and Applications in Engineering, 11(2), 921–927. Retrieved from https://ijisae.org/index.php/IJISAE/article/view/2970

Issue

Vol. 11 No. 2 (2023)

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.

IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.