As vital transportation carriers in trade, ships have the advantage of stability, economy, and bulk capacity over airplanes, trucks, and trains. Even so, their loss and cost due to collisions and other accidents exceed those of any other mode of transportation. To prevent ship collisions many ways have been suggested, e.g., the 1972 COLREGs which is the regulation for preventing collision between ships. Technologically speaking, many related studies have been conducted. The term “Ship domain” involves that area surrounding a ship that the navigator wants to keep other ships clear of. Ship domain alone is not sufficient, however, for enabling one or more ships to simultaneously determine the collision risk for all of the ships concerned. Fuzzy theory is useful in helping ships avoid collision in that fuzzy theory may define whether collision risk is based on distance to closest point of approach, time to closest point of approach, or relative bearing – algorithms that are difficult to apply to more than one ships at one time. The main purpose of this study is thus to reduce collision risk among multiple ships using a distributed local search algorithm (DLSA). By exchanging information on, for example, next-intended courses within a certain area among ships, ships having the maximum reduction in collision risk change courses simultaneously until all ships approach a destination without collision. In this paper, we introduce distributed local search and explain how it works using examples. We conducted experiments to test distributed local search performance for certain instances of ship collision avoidance. Experiments results showed that in most cases, our proposal applies well in ship collision avoidance amongmultiple ships.

1. [1] International Maritime Organization, “Convention on the International Regulations for Preventing Collisions at Sea, 1972 (COLREGs),” 1972.
2. [2] R. Szlapczynski, “A unified measure of collision risk derived from the concept of a ship domain,” J. of Navigation, Vol.59, pp. 477-490, 2006.
3. [3] R. Szlapczynski, “Determining the Optimal course Alteration Manoeuvre in a Multi-Target Encounter Situation for a Given Ship domain Model,” Annual of Navigation, Vol.12, pp. 75-85, 2007.
4. [4] E. M. Goodwin, “A Statistical Study of Ship Domains,” J. of Navigation, Vol.28, pp. 329-341, 1975.
5. [5] Y. Fuji and K. Tanaka, “Traffic capacity,” The J. of Navigation, Vol.24, pp. 543-552, 1971.
6. [6] K. Hasegawa, A. Kouzuki, T. Muramatsu, H. Komine, and Y. Watabe, “Ship Auto-navigation Fuzzy Expert System (SAFES),” J. of the Society of Naval Architecture of Japan, Vol.166, 1989.
7. [7] N. Wang, X. Meng, Q. Xu, and Z. Wang, “A Unified Analytical Framework for Ship Domains,” J. of Navigation, Vol.62, pp. 643-655, 2009.
8. [8] S. M. Lee, K. Y. Kwon, and J. Joh, “A Fuzzy A Fuzzy Logic for Autonomous Navigation of Marine Vehicles Satisfying COLREG Guidelines,” Int. J. of Control, Automation, and Systems, Vol.2, pp. 171-181, 2004.
9. [9] E. K. Kim, I. K. Kang, and Y. G. Kim, “Collision Risk Decision System for Collision Avoidance,” Korean Institute of Intelligent systems, Vol.11, pp. 524-527, 2001.
10. [10] S. Russell and P. Norvig, “Artificial Intelligence A Modern Approach: Second Edition,” Pearson, pp. 137-160, 2003.
11. [11] M. Yokoo, E. H. Durfee, T. Ishida, and K. Kuwabara, “The Distributed Constraint Satisfaction Problem: Formalization and Algorithms,” IEEE Trans. on Knowledge and Data Engineering, Vol.10, pp. 673-685, 1998.
12. [12] M. Yokoo and K. Hirayama, “Distributed Breakout Algorithm for Solving Distributed Constraint,” Second Int. Conf. on Multiagent Systems, pp. 401-408, 1996.