HomePage
 




 


 

ISSN 2083-6473
ISSN 2083-6481 (electronic version)
 

 

 

Editor-in-Chief

Associate Editor
Tomasz Neumann
 

Published by
TransNav, Faculty of Navigation
Gdynia Maritime University
3, John Paul II Avenue
81-345 Gdynia, POLAND
www http://www.transnav.eu
e-mail transnav@am.gdynia.pl
Ship Collision Avoidance by Distributed Tabu Search
1 Kobe University, Kobe, Japan
ABSTRACT: More than 90% of world trade is transported by sea. The size and speed of ships is rapidly increasing in order to boost economic efficiency. If ships collide, the damage and cost can be astronomical. It is very difficult for officers to ascertain routes that will avoid collisions, especially when multiple ships travel the same waters. There are several ways to prevent ship collisions, such as lookouts, radar, and VHF radio. More advanced methodologies, such as ship domain, fuzzy theory, and genetic algorithm, have been proposed. These methods work well in one-on-one situations, but are more difficult to apply in multiple-ship situations. Therefore, we proposed the Distributed Local Search Algorithm (DLSA) to avoid ship collisions as a precedent study. DLSA is a distributed algorithm in which multiple ships communicate with each other within a certain area. DLSA computes collision risk based on the information received from neighboring ships. However, DLSA suffers from Quasi-Local Minimum (QLM), which prevents a ship from changing course even when a collision risk arises. In our study, we developed the Distributed Tabu Search Algorithm (DTSA). DTSA uses a tabu list to escape from QLM that also exploits a modified cost function and enlarged domain of next-intended courses to increase its efficiency. We conducted experiments to compare the performance of DLSA and DTSA. The results showed that DTSA outperformed DLSA.
REFERENCES
Fan, L. & Ajit, N. 2014. 17th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2014): 190-205.
Fujii, Y. & Tanaka, K. 1971. Traffic Capacity. Journal of Navigation 24:543-552.
Glover, F. 1989. Tabu Search-Part I. ORSA Journal on Computing 1(3):190-206.
Goodwin, E.M. 1975. A Statistical Study of Ship Domains. Journal of Navigation 28:329-341.
Hasegawa, K., Kouzuki, A., Muramatsu, T., Komine, H., & Watabe, Y. 1989. Ship Auto-navigation Fuzzy Expert System (SAFES). Journal of the Society of Naval Architecture of Japan 166.
International Maritime Organization, 1972. Convention on the International Regulations for Preventing Collisions at Sea.
Kim, D., Hirayama, K., & Park, G. 2014. Collision Avoidance in Multiple-ship Situations by Distributed Local Search. Journal of Advanced Computational Intelligence and Intelligent Informatics 18(5):839-848.
Kim, E., Kang, I., & Kim, Y. 2001. Collision Risk Decision System for Collision Avoidance. Korean Institute of Intelligent Systems 11:524-527.
Lee, S., Kwon, K., & Joh, J. 2004. A Fuzzy Logic for Autonomous Navigation of Marine Vehicles Satisfying COLREG Guidelines. International Journal of Control, Automation and Systems 2:171-181.
Russell, S. & Norvig, P. 2003. Artificial Intelligence: A Modern Approach, Pearson: 137-160.
Szlapczynski, R. 2006. A Unified Measure of Collision Risk Derived from the Concept of a Ship Domain. Journal of Navigation 59:477-490.
Szlapczynski, R. 2007. Determining the Optimal Course Alteration Manoeuvre in a Multi-target Encounter Situation for a Given Ship Domain Model. Annual of Navigation 12:75-85.
Tsou, M., Kao, S., & Su, C. 2010. Decision Support from Genetic Algorithms for Ship Collision Avoidance Route Planning and Alerts. Journal of Navigation 63:167-182.
Wang, N., Meng, X., Xu, Q., & Wang, Z. 2009. A Unified Analytical Framework for Ship Domains. Journal of Navigation 62:643-655.
Yokoo, M., Durfee, E., Ishida, T., & Kuwabara, K. 1998. The Distributed Constraint Satisfaction Problem: Formalization and Algorithms. IEEE Trans. on Knowledge and Data Engineering 10:673-685.
Yokoo, M. & Hirayama, K. 1996. Distributed Breakout Algorithm for Solving Distributed Constraint. Second Int. Conf. on Multiagent Systems : 401-408.
Citation note:
Kim D., Hirayama K., Okimoto T.: Ship Collision Avoidance by Distributed Tabu Search. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 9, No. 1, doi:10.12716/1001.09.01.03, pp. 23-29, 2015

File downloaded 762 times








Important: TransNav.eu cookie usage
The TransNav.eu website uses certain cookies. A cookie is a text-only string of information that the TransNav.EU website transfers to the cookie file of the browser on your computer. Cookies allow the TransNav.eu website to perform properly and remember your browsing history. Cookies also help a website to arrange content to match your preferred interests more quickly. Cookies alone cannot be used to identify you.
Akceptuj─Ö pliki cookies z tej strony