Abstract
Along with the very actively progressing field of autonomous ground and aerial vehicles, the advent of autonomous vessels has brought up new research and technological problems originating from the specifics of marine navigation. Autonomous ships are expected to navigate safely and avoid collisions following COLREG navigation rules. Trustworthy navigation of autonomous ships presumes applying provably correct navigation algorithms and control strategies. We introduce the notion of maritime game as a special case of Stochastic Priced Timed Game and model the autonomous navigation using UPPAAL STRATEGO. Furthermore, we use the refinement technique to develop a game model in a correct-by-construction manner. The navigation strategy is verified and optimized to achieve the goal to safely reach the manoeuvre target points at a minimum cost. The approach is illustrated with a case study inspired by COLREG Rule 15.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The game model is found in: https://github.com/fshokri/Game-model.
References
Ahmed, Y.A., Hasegawa, K.: Fuzzy reasoned waypoint controller for automatic ship guidance. IFAC-PapersOnLine 49(23), 604–609 (2016)
Ahvenjärvi, S.: The human element and autonomous ships. TransNav Int. J. Mar. Navig. Saf. Sea Transp. 10 (2016)
Back, R.-J., von Wright, J.: Refinement Calculus: A Systematic Introduction. Graduate Texts in Computer Science. Springer, Heidelberg (1998). https://doi.org/10.1007/978-1-4612-1674-2
Basile, D., Fantechi, A., Rucher, L., Mandò, G.: Statistical model checking of hazards in an autonomous tramway positioning system. In: Collart-Dutilleul, S., Lecomte, T., Romanovsky, A. (eds.) RSSRail 2019. LNCS, vol. 11495, pp. 41–58. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-18744-6_3
Basile, D., ter Beek, M.H., Legay, A.: Strategy synthesis for autonomous driving in a moving block railway system with Uppaal Stratego. In: Gotsman, A., Sokolova, A. (eds.) FORTE 2020. LNCS, vol. 12136, pp. 3–21. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-50086-3_1
Behrmann, G., David, A., Larsen, K.G.: A tutorial on Uppaal. In: Bernardo, M., Corradini, F. (eds.) SFM-RT 2004. LNCS, vol. 3185, pp. 200–236. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30080-9_7
Benjamin, M.R., Curcio, J.A., Leonard, J.J., Newman, P.M.: Navigation of unmanned marine vehicles in accordance with the rules of the road. In: Proceedings 2006 IEEE International Conference on Robotics and Automation, ICRA 2006, pp. 3581–3587. IEEE (2006)
David, A., Jensen, P.G., Larsen, K.G., Legay, A., Lime, D., Sørensen, M.G., Taankvist, J.H.: On time with minimal expected cost!. In: Cassez, F., Raskin, J.-F. (eds.) ATVA 2014. LNCS, vol. 8837, pp. 129–145. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11936-6_10
David, A., Jensen, P.G., Larsen, K.G., Mikučionis, M., Taankvist, J.H.: Uppaal Stratego. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 206–211. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46681-0_16
Höyhtyä, M., Huusko, J., Kiviranta, M., Solberg, K., Rokka, J.: Connectivity for autonomous ships: architecture, use cases, and research challenges. In: 2017 International Conference on Information and Communication Technology Convergence (ICTC), pp. 345–350. IEEE (2017)
IMO: Convention on the international regulations for preventing collisions at sea (COLREGs) (1972)
Jenie, Y.I., van Kampen, E.-J., Remes, B.: Cooperative autonomous collision avoidance system for unmanned aerial vehicle. In: Chu, Q., Mulder, B., Choukroun, D., van Kampen, E.J., de Visser, C., Looye, G. (eds.) Advances in Aerospace Guidance. Navigation and Control, pp. 387–405. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38253-6_24
Karra, S.L., Larsen, K.G., Lorber, F., Srba, J.: Safe and time-optimal control for railway games. In: Collart-Dutilleul, S., Lecomte, T., Romanovsky, A. (eds.) RSSRail 2019. LNCS, vol. 11495, pp. 106–122. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-18744-6_7
Katz, S.: A superimposition control construct for distributed systems. ACM Trans. Program. Lang. Syst. (TOPLAS) 15(2), 337–356 (1993)
Kutila, M., Pyykönen, P., Holzhüter, H., Colomb, M., Duthon, P.: Automotive LIDAR performance verification in fog and rain. In: 2018 21st International Conference on Intelligent Transportation Systems (ITSC), pp. 1695–1701. IEEE (2018)
Larsen, K.G., Mikučionis, M., Taankvist, J.H.: Safe and optimal adaptive cruise control. In: Meyer, R., Platzer, A., Wehrheim, H. (eds.) Correct System Design. LNCS, vol. 9360, pp. 260–277. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23506-6_17
Lee, S.-M., Kwon, K.-Y., Joh, J.: A fuzzy logic for autonomous navigation of marine vehicles satisfying COLREG guidelines. Int. J. Control Autom. Syst. 2(2), 171–181 (2004)
Mühlegg, M., Dauer, J.C., Dittrich, J., Holzapfel, F.: Adaptive trajectory controller for generic fixed-wing unmanned aircraft. In: Chu, Q., Mulder, B., Choukroun, D., van Kampen, E.J., de Visser, C., Looye, G. (eds.) Advances in Aerospace Guidance, Navigation and Control, pp. 443–461. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38253-6_27
Perera, L.P., Carvalho, J.P., Soares, C.G.: Autonomous guidance and navigation based on the COLREGs rules and regulations of collision avoidance. In: Proceedings of the International Workshop Advanced Ship Design for Pollution Prevention, pp. 205–216 (2009)
Snook, C., Waldén, M.: Refinement of statemachines using Event B semantics. In: Julliand, J., Kouchnarenko, O. (eds.) B 2007. LNCS, vol. 4355, pp. 171–185. Springer, Heidelberg (2006). https://doi.org/10.1007/11955757_15
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (2011)
Teo, K., Ong, K.W., Lai, H.C.: Obstacle detection, avoidance and anti collision for MEREDITH AUV. In: OCEANS 2009, pp. 1–10. IEEE (2009)
Varas, J.M., et al.: MAXCMAS project: autonomous COLREGs compliant ship navigation. In: Proceedings of the 16th Conference on Computer Applications and Information Technology in the Maritime Industries (COMPIT), pp. 454–464 (2017)
Wuchen, S., Renxiang, B., Yong, L., Xinyu, L., Liangqi, L., Pengfei, F.: Prediction of leeway and drift angle based on empirical formula. In: Proceedings of the Asia-Pacific Conference on Intelligent Medical 2018 & International Conference on Transportation and Traffic Engineering 2018, pp. 196–199 (2018)
Acknowledgments
This study has been partly supported by the project ESC funded by the Academy of Finland (grant No.308980) and the Estonian Ministry of Education and Research institutional research grant no. IUT33-13. We would like to thank Marius Mikučionis for his assistance with UPPAAL STRATEGO. We also thank the anonymous reviewers for their inputs and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Shokri-Manninen, F., Vain, J., Waldén, M. (2020). Formal Verification of COLREG-Based Navigation of Maritime Autonomous Systems. In: de Boer, F., Cerone, A. (eds) Software Engineering and Formal Methods. SEFM 2020. Lecture Notes in Computer Science(), vol 12310. Springer, Cham. https://doi.org/10.1007/978-3-030-58768-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-58768-0_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58767-3
Online ISBN: 978-3-030-58768-0
eBook Packages: Computer ScienceComputer Science (R0)