Ship Collision Avoidance by Distributed Tabu Search

• Autorzy: Kim D. , Hirayama K. , Okimoto M.

Identyfikatory

DOI

10.12716/1001.09.01.03

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

safety of navigation; Collision Avoidance; Distributed Tabu Search Algorithm (DTSA); Distributed Local Search Algorithm (DLSA); Quasi-Local Minimum (QLM); Tabu Search Algorithm; Local Search Algorithm; Distributed Tabu Search

• Wydawca: Faculty of Navigation, Gdynia Maritime University
• Czasopismo: TransNav : International Journal on Marine Navigation and Safety of Sea Transportation
• Rocznik: 2015
• Tom: Vol. 9, no. 1
• Strony: 23--29
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Kim D.

• Kobe University, Kobe‐shi, Hyogo‐ken, Japan

autor

Hirayama K.

• Kobe University, Kobe‐shi, Hyogo‐ken, Japan

autor

Okimoto M.

• Kobe University, Kobe‐shi, Hyogo‐ken, Japan

Bibliografia

• 1 Fan, L. & Ajit, N. 2014. 17th International Conference on Principles and Practice of Multi‐Agent Systems (PRIM 2014): 190‐205.
• 2 Fujii, Y. & Tanaka, K. 1971. Traffic Capacity. Journal of Navigation 24:543‐552.
• 3 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.
• 4 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.
• 5. International Maritime Organization, 1972. Convention on the International Regulations for Preventing Collisions at Sea.
• 6 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.
• 7 Kim, E., Kang, I., & Kim, Y. 2001. Collision Risk Decision System for Collision Avoidance. Korean Institute of Intelligent Systems 11:524‐527.
• 8 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.
• 9 Russell, S. & Norvig, P. 2003. Artificial Intelligence: A Modern Approach, Pearson: 137‐160.
• 10 Szlapczynski, R. 2006. A Unified Measure of Collision Risk Derived from the Concept of a Ship Domain. Journal of Navigation 59:477‐490.
• 11 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.
• 12 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.
• 13 Wang, N., Meng, X., Xu, Q., & Wang, Z. 2009. A Unified Analytical Framework for Ship Domains. Journal of Navigation 62:643‐655.
• 14 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.
• 15 Yokoo, M. & Hirayama, K. 1996. Distributed Breakout Algorithm for Solving Distributed Constraint. Second Int. Conf. on Multiagent Systems : 401‐408.