Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-11T13:09:39.982Z Has data issue: false hasContentIssue false

Decision Support from Genetic Algorithms for Ship Collision Avoidance Route Planning and Alerts

Published online by Cambridge University Press:  01 December 2009

Ming-Cheng Tsou*
Affiliation:
(National Taiwan Ocean University, Department of Transportation and Navigation Science)
Sheng-Long Kao
Affiliation:
(National Taiwan Ocean University, Department of Transportation and Navigation Science)
Chien-Min Su
Affiliation:
(National Taiwan Ocean University, Department of Electrical Engineering)
Rights & Permissions [Opens in a new window]

Abstract

When an officer of the watch (OOW) faces complicated marine traffic, a suitable decision support tool could be employed in support of collision avoidance decisions, to reduce the burden and greatly improve the safety of marine traffic. Decisions on routes to avoid collisions could also consider economy as well as safety. Through simulating the biological evolution model, this research adopts the genetic algorithm used in artificial intelligence to find a theoretically safety-critical recommendation for the shortest route of collision avoidance from an economic viewpoint, combining the international regulations for preventing collisions at sea (COLREGS) and the safety domain of a ship. Based on this recommendation, an optimal safe avoidance turning angle, navigation restoration time and navigational restoration angle will also be provided. A Geographic Information System (GIS) will be used as the platform for display and operation. In order to achieve advance notice of alerts and due preparation for collision avoidance, a Vessel Traffic Services (VTS) operator and the OOW can use this system as a reference to assess collision avoidance at present location.

Type
Research Article
Copyright
Copyright © The Royal Institute of Navigation 2009

1. INTRODUCTION

With the continued development of the shipping industry, ships have grown larger, become more specialized and capable of operating at faster speeds. The marine traffic environment has become more complicated and the density of shipping traffic has become greater. The navigable areas in channels and ports have become relatively narrow, so that the navigation problems are more challenging and collisions or stranding accidents are increasing in frequency, even though auxiliary ship collision avoidance equipment is widely used at present. These accidents not only cause major human injury and huge property loss, but also constitute a serious threat to the marine environment. In an investigation into reasons for collision accidents it was found that over 80% are caused by human factors (Li et al., Reference Li, Yang, Cao and Li2006).

There are two ways to solve the problem of these human factors: Firstly, to strengthen the technical training and management of crews, to improve the quality and accountability of crews. Secondly, to improve the degree to which decisions are automated and, through realizing automatic navigation, to avoid the mistakes caused by the subjective judgments of people. The advancement of technology has added various navigation instruments onto the bridge to provide a good deal of navigational information. If crews do not get sufficient training, decisions and judgments may be hindered by too much information and if a rough or incorrect decision is made, the cost will usually be enormous. So, the effective way to solve the problem of human factors is to improve intelligent and automatic navigation by technical means, reducing reliance on subjective judgments, lightening the burden of navigators and realizing intelligent design and the automation of ship collision avoidance. For this reason, research into the automation of ship collision avoidance has very real implications for ship safety.

Although the Automatic Radar Plotting Aid (ARPA) can solve part of the information-processing problem in collision avoidance and its operation is easy, it is not a fully automatic collision avoidance system. Ultimately, it is still necessary to depend on subjective judgments based on the experience and professional skills of the navigator, otherwise more serious mistakes might occur (Cockroft, Reference Cockroft1984). Recently, with the application of Automatic Identification System (AIS) in ship collision avoidance as well as VTS, the problem of acquiring the information required for collision avoidance decision support has been solved well. AIS systems can provide static and highly accurate dynamic information on ships, which offers the advantages of large amounts of information and real-time data. It is an important source of information to inform decision-making in collision avoidance, and a helpful advance on previous methods. However, the ship collision avoidance process is a complicated decision-making process, which involves the key factors of environment, ship, and personnel. It also includes various dynamic and static data, certain and uncertain information, quantitative mathematical calculations, qualitative logical reasoning and so on, and thus entails the expertise of many disciplines, such as navigation, computer science and others. It involves data collection, data pre-processing, division of encounter state, calculations for degree of danger of collision, judgment of encounter conditions, selection of collision avoidance method, optimization of collision avoidance action, setup of navigation restoration decisions and multi-target collision avoidance; it is a complicated system engineering problem (Jones, Reference Jones1978, Davis et al., Reference Davis, Dove and Stockel1982, Lamb, Reference Lamb1985, Lee, Reference Lee, Kwon and Joh2004, Statheros, Reference Statheros, Howells and McDonald-Maier2008). Because the ship itself is a complicated system, it is very difficult to use an accurate mathematical model to describe this system. Even if there is a very accurate mathematical model, it is not feasible to apply it in real-time decision environments. So researchers have begun to introduce various artificial intelligence technologies into the collision avoidance field in recent years, including artificial neural networks, fuzzy logic technology and genetic algorithms, thus opening a new research field that employs soft computing instead of pure mathematical models (Statheros, Reference Statheros, Howells and McDonald-Maier2008).

Because the determination of a safe ship collision avoidance route is a multi-criteria, nonlinear planning problem, it should be able to find a balance between navigational safety and economy at the same time (Smierzchalski and Michalewicz, Reference Smierzchalski and Michalewicz2000). This means that the collision avoidance decision mechanism adopted can not only keep relevant danger assessments and collision avoidance measures in navigation, but can also consider deviation from the original route. This research is different from the mathematical model. The genetic algorithm of artificial intelligence is adopted to find a theoretically safety-critical recommendation for the shortest route of collision avoidance from an economic viewpoint, through simulating the biological evolution model, while combining the safety domain of ship and the COLREGS in a more objective, fast and correct way. This route theoretically represents the recommended shortest route for the ship to pass safely. The turning angle and time on this route can be regarded as the critical values in assessing safety. They represent the latest turning point of collision avoidance, and the earliest turning point of turning back. Finally, this research sets up a user interface on an embedded GIS platform, to form a spatial decision support system. The system can provide the functions of collision avoidance alerts and collision avoidance decision support, so that the navigator or VTS operator can use it as a reference for the simulation of collision avoidance measures.

2. SHIP DOMAIN

The concept of the ship domain plays a very important role in marine traffic engineering and has already been applied extensively to ship collision avoidance, danger assessment and VTS design. The earliest concept was proposed by Goodwin (Reference Goodwin1975) who recognized that there is a domain limit around a ship. If another ship or fixed obstacle enters into this domain, it will cause the danger of collision with the home ship. Based on this concept, the ship domain model has been revised by other scholars (Davis et al., Reference Davis, Dove and Stockel1980, Colley et al., Reference Colley1984). But apart from the encounter state, the ship domain is also influenced by ship type and the marine environmental state. It is not feasible to define a unified domain range for all ships. Therefore, Zhu et al. (Reference Zhu, Xu and Lin2001) employed an artificial neural network to estimate the ship domain under different ship types and visibility states by considering visibility, ship manoeuvrability and closest point of approach (CPA) bearings as the input factors. Kao et al. (Reference Kao, Lee, Chang and Ko2007) employed ship length, ship speed and sea state as three parameters to estimate the fuzzy guarding ring, based on the concept of ship domain. Pietrzykowski (2008) studied the calculation of the fuzzy domain of the ship in a narrow water area. This research employs the fuzzy guarding ring of Kao et al. (Reference Kao, Lee, Chang and Ko2007) to estimate the radius of different fuzzy guarding rings under different states, in order to plan a collision avoidance route in respect of the following considerations:

  • Assessment of collision danger.

  • Reference to the timing of ship collision avoidance operations.

  • Reference to the turning angle of ship collision avoidance operations.

  • Reference to the determination of navigation restoration time.

3. DIVISION OF ENCOUNTER SITUATION

This research uses the encounter state of the ship as the basis of collision avoidance calculations. Only when the collision avoidance conditions are satisfied can the calculations of collision avoidance route planning be conducted. The division principle is based on the results of an analysis of the COLREGS, of navigation habits and automatic collision avoidance methods. When two ships approach at sea, there can be several situations, including head-on (F), crossing (A, B, E), and overtaking (C, D), as shown in Figure 1. A ship coming from the angles included in the F, A, B areas is considered the target ship and the home ship will be the give way ship. For a ship coming from the F and A areas, the home ship should turn right for collision avoidance. As for a ship coming from the B area, if the relative board angle is larger, the home ship should turn left for collision avoidance, while for a ship coming from the E, D and C areas, the home ship can go straight ahead without taking any collision avoidance measures. Only when an emergency situation occurs will the home ship adopt collision avoidance measures for a ship coming from these E, D and C areas.

Figure 1. Division diagram for ship encounter situations (Liu et al., Reference Liu, Liu, Wu and Zou2007).

4. DECISION MODEL FOR ROUTE PLANNING OF COLLISION AVOIDANCE

At the start of the encounter, the home ship and the target ship keep their original course and speed. After the target ship enters the observing range (the observational information on the target ship can come from AIS), the relative motion course, the distance of CPA (DCPA) and the time of CPA (TCPA) of the target ship will start to be calculated. The encounter state of both ships will be determined in accordance with COLREGS. It is judged whether the home ship is the give way ship and if there is any danger of collision between the home ship and the target ship. If there is, the decision support system of this research will be used to calculate the route planning for collision avoidance, and to provide the most economic and safe recommendation route. In fact, this route may not be the most feasible route, but the system can at least guarantee a theoretically safe and economic recommendation route, which is helpful both for alerts and for decision-making. So the navigator can use this route as a reference for determining collision avoidance measures. According to the different tasks, the calculation of route planning can be divided into the following three stages:

4.1. Initial alert stage

After the target ship enters the observing and tracking stage, the encounter state of both ships will be determined in accordance with COLREGS. It is judged whether there is a danger of collision with the target ship (DCPA is smaller than the guarding ring of the home ship) and whether the home ship is the way-giving ship; calculations for collision avoidance route planning will be conducted by the system. At this stage, the latest turning point can be determined, and for how long the original navigational course and speed can be maintained. The navigator can use this as a reference for determining collision avoidance measures, and can also simulate the setting of different safe passing distances, which can be used as alerts for early turning.

4.2. Navigational stage of collision avoidance

As for the collision avoidance route after turning, the turning angle should not be so small that the target ship is unable to see the collision avoidance intention of the home ship. It should not be too large, so as to deviate too far from the route. But it must guarantee that the target ship can pass outside the safe range of guarding ring. After it is held for a certain time, navigational restoration can be carried out safely, and a navigational restoration alert can be provided.

Navigational restoration stage

The decisions relating to navigational restoration time and action should be able to guarantee that a dangerous situation will not recur. It should be able to reduce navigational loss from the deviation due to the collision avoidance action as much as possible, and be able to provide the turning point for return to the original navigational route.

5. SHIP COLLISION AVOIDANCE ROUTE PLANNING BY GENETIC ALGORITHM

5.1. Description of genetic algorithm

A genetic algorithm (GA) is a stochastic optimization algorithm based on the principles of natural selection and natural heredity. With the aid of genetics and the evolutionary theory of Charles Darwin (Back, Reference Back1996), the whole problem space is searched randomly and in parallel to get the optimum solution. A genetic algorithm employs a population instead of a unit to search for the optimum solution, and this entails the feature of parallel algorithms. In the evolutionary process of every generation, genetic algorithms carry out the same steps, such as reproduction, crossover, and mutation. Only the fitness function of the question itself is used. It does not need other preconditions and auxiliary information. Because there are fewer restrictions on fitness function and constraint conditions, and because the search range covers the whole independent variable space, optimum solutions can be obtained with a greater probability of iteration. Genetic algorithms use the random transfer rule, which can effectively solve complicated nonlinear problems for optimization in real-world applications.

Compared to traditional optimization, genetic algorithms have better robustness. Their characteristics can be described as follows:

  • They carry out the operation of parameter codes instead of parameters themselves.

  • The search process is iterated from one group of solutions to another group of solutions, to avoid falling into local optimization, and there is a greater probability of achieving a global optimal solution.

  • A random search process is used.

  • They do not have any special request for the fitness function and only utilize fitness information, with no need for any other auxiliary information, such as differentials, and they have a wider scope of application.

As for the application of GA to route planning, it has already been used for obstacle avoidance in robots (Lin et al., Reference Lin, J and Michalewicz1994), and the same principles could be applied to ship collision avoidance. Ito et al. (Reference Ito, Zhang and Yoshida1999) regard the longitude and latitude of turning points on collision avoidance routes as the genes in the chromosome. A good collision avoidance route is selected according to the degree of danger and the curvature of route. Smierzchalski and Michalewicz (Reference Smierzchalski and Michalewicz2000) treated the latitude and longitude of turning points on collision avoidance routes as the genetic code, and added ship speed and time concepts to form the genes in the chromosomes, in order to search the optimum route. These two research studies address the route planning of robots mainly, so COLREGS was not included. Zou and Ni (Reference Zou and Ni2006) have utilized a genetic algorithm to perform applications of collision avoidance decisions. Although navigational practice and the COLREGS were considered, only the optimum turning angle, rather than an entire collision avoidance route was used as the reference for collision avoidance decisions. The present research employs the whole collision avoidance route as the basis of assessment, considers both safety and economy at the same time, and includes the factors of the COLREGS and safety domain, in order to inform collision avoidance measures, such as earliest turning point time, safe angle of collision avoidance, navigational restoration time and the navigational restoration angle, which can be viewed as the basis for genetic coding of the chromosomes.

5.2. Objective function model

When a ship encounters a target ship, the focal point of interest for the research is how to select more rational and effective collision avoidance measure in accordance with the state of encounter. This research employs a safe domain between the home ship and the target ship, confirms the turning angle and turning time, considers the navigational restoration time and angle further, and prevents the generation of new encounter states or domain stress phenomena. The distance from the beginning of turning to the restoration of the original route is the fitness function between the home ship and the target ship. Then the genetic algorithm is used to obtain the shortest collision avoidance route to meet the fitness function and constraint conditions, so that the home ship can satisfy the following:

  • The total distance of collision avoidance shall be as short as possible.

  • The degree of danger of collision shall be minimized, and kept outside the safe domain.

  • Under this passing condition of safety domain, collision avoidance angles shall be minimized.

  • After the least time of navigational detour, the home ship resumes its original route.

  • Where there are no new encounters or other domain stress phenomena, the turning angle shall be minimized.

Assuming we know the course C T, speed V T, bearing Q, distance D of the target ship, and course C O, speed V O of the home ship. If VO is the new course of the home ship after collision avoidance, then the fitness function is:

(1)
Distance \equals \mathop {min}\limits_{i \equals \setnum{1}}^{n} \left\{ {Ds_{i} \plus } \right.\left. {Dr_{i} } \right\}

where Ds i is the distance after collision avoidance, Dr i is the distance of navigational restoration.

(2)
Ds_{i} \equals f^{\,\setnum{3}} \lpar X_{\setnum{1}} \rpar V_{O} \comma \quad Dr_{i} \equals f^{\,\setnum{3}} \lpar X_{\setnum{2}} \rpar V_{O}
  • min f2 (X1) is the turning angle after collision avoidance.

  • min f2 (X2) is the turning angle of navigational restoration.

  • min f3 (X1) is the navigation time after collision avoidance.

  • min f3 (X2) is the navigation time of navigational restoration.

The constraint conditions are:

\quad 30\les X_{\setnum{1}} \les 90\hfill
\quad\minus 60\les X_{\setnum{2}} \les \minus30\hfill
\quad t \prime_{CPA{\setnum{1} }} \les \,f^{\,\setnum{3}} \lpar X_{\setnum{1}} \rpar \les 60\hfill
\quad d \prime_{CPA{\setnum{1} }} \ges Gd\ {\rm and}\ d\prime_{CPA{\setnum{2} }} \ges Gd\hfill

where X 1∊[30, 90] is the decision parameter, which represents the turning angle of collision avoidance (the difference of angle between new course and original course, and the positive value means right turn), X 2∊[−60, −30] represents the turning angle of navigational restoration (the difference of angle between new course and original course, and the negative value means left turn). f 2 (X 1)=X 1 and f 2 (X 2)=X 2 are the objective functions. f 3 (X 1) is the objective function of the home ship after it has turned X 1 degrees. The navigational restoration time should not exceed 60 minutes and should be at least larger than TCPA 1 time (new TCPA time after collision avoidance). f 3 (X 2) is the time for restoration of the home ship to its original route. dCPA1 and dCPA2 are the new DCPA after collision avoidance and the new DCPA of navigational restoration, respectively.

As shown in Figure 2, if the turning angle of the home ship is X 1 (right+ve, left−ve) and new angle between the home ship and the target ship is COT (range: −180° ~ 180°), then new dCPA1 and tCPA1 will be calculated as follows:

(3)
d\prime_{CPA{\setnum{1} }} \equals D \ sin\theta
(4)
t\prime_{CPA{\setnum{1} }} \equals D \ cos\theta \sol V\prime_{R}

where θ is the angle between the relative motion line of the home ship and the bearing of the target ship; VR is the relative speed after collision avoidance; and COT is the angle between the home ship and the target ship after the home ship has turned.

(5)
C\prime_{OT} \equals C\prime_{O} \minus C_{T}
(6)
{\rm If}\ C\prime_{OT} \gt {\rm 0}^\circ \comma \ {\rm then}\ \theta \equals B \plus X_{\setnum{1}} \minus Q
(7)
{\rm If}\ C\prime_{OT} \lt {\rm 0}^\circ \comma \ {\rm then}\ {\rmbeta } \equals \minus \lpar B \plus X_{\setnum{1}} \minus Q\rpar

VR is the relative speed after the home ship has turned:

(8)
V\prime_{R} \equals \sqrt {{V_{T}} ^{\setnum{2}} \plus {V_{O}} ^{\setnum{2}} \minus 2 V_{T} V_{O} cosC\prime_{OT} }

If B is the angle between the relative motion line of the home ship and the heading after the home ship has turned, then the way of calculation is as follows:

(9)
{\rm If}\ C\prime_{OT} \gt 0\comma \ {\rm then}\ B \equals cos^{\minus \setnum{1}} \lpar \lpar {V_{O}} ^{\setnum{2}} \plus {V\prime_{R}} ^{\setnum{2}}\minus {V_{T}} ^{\setnum{2}} \rpar \sol 2V_{O} V\prime_{R} \rpar
(10)
{\rm If}\ C\prime_{OT} \lt 0\comma \ {\rm then}\ B \equals \minus cos^{\minus \setnum{1}} \lpar \lpar {V_{O}} ^{\setnum{2}} \plus {V\prime_{R}} ^{\setnum{2}}\minus {V_{T}} ^{\setnum{2}} \rpar \sol 2V_{O} V\prime_{R} \rpar

If the value of dCPA is “+”, it means that a new relative motion line passes through the bow of the home ship, otherwise it passes through the stern of the home ship. Gd represents the radius of the guarding ring for safe passing, which means that the new DCPA should be at least larger than the radius of the guarding ring. This value depends on marine conditions and ship type, which can be obtained from self setup or other models.

Figure 2. Collision avoidance decision model after the home ship has turned (Liu et al., Reference Liu, Wu and Jia2004).

5.3. The coding form of collision avoidance route

In genetic algorithms, the coding technology of parameters, length of gene strings and searching space are very important for the system's calculation speed. In order to reduce the length of code and to accelerate the search speed, instead of using the latitude and longitude of turning angles as the genetic codes in the chromosome, this research used the following four parameters of collision avoidance route to encode:

  • The required time to the turning point (or the time from TCPA) Q.

  • The required collision avoidance angle for passing the target ship at safe distance CO.

  • The time between the turning to collision avoidance and the turning to navigational restoration Ta.

  • The limited angle upon turning of navigational restoration Cb.

These four parameters constitute a collision avoidance route as a piece of chromosome. The binary form is adopted for coding (as shown in Figure 3). Considering the ship speed and observing distance, it is assumed that the ship can arrive within 100 minutes, thus seven binary bits can fully express the values within 100. When the relative bearing of the bow is head on, the safe collision avoidance angle CO should be limited to within 30~90 degrees starboard in order to prevent over- or insufficient turning, so this also is expressed by seven binary bits. The time between the turning of collision avoidance and the turning to navigational restoration Ta should not exceed 60 minutes for which six binary bits can fully express the values. When the display mode is head up, the turning angle of navigational restoration Cb should be limited within 30~90 degrees port, so it is expressed by six binary bits. Using such a method, 26 binary bits are sufficient to express a route. If there is a big population in the algorithm, calculation space and time will be saved effectively. The optimum gene combination obtained will have more significant navigational use than just a latitude and longitude for the turning point, which needs to be further interpreted by the user.

Figure 3. Binary gene coding of a collision avoidance route.

5.4. Genetic operation

Considering that the real-time requirements of ship collision avoidance might be higher, if the scale of the selected population is too large, this increases the search time, which is unfavourable for decision support in real-time collision avoidance. Synthetically considering the concrete conditions of ship collision avoidance and finely tuning the process, we selected the population number as 100, crossover rate 0·6, and the mutation rate of 0·04. Applying this genetic operation, and using the generated son generation to substitute for the father generation when the optimum value has converged on or reaches the required revolution generation, the search ends, meaning that the optimum route has been found. The steps (see Figure 4) are:

  1. (1) Encode 26 binary bits in the feasible solution space, each binary bit string corresponding to a collision avoidance route.

  2. (2) Set the size of initial population as 100 initialized individuals, meaning to select 100 random collision avoidance routes.

  3. (3) Calculate the value of the fitness function for corresponding binary bits according to Equation (1), and judge which routes are shorter and safer.

  4. (4) Conduct a roulette selection for the population to select shorter and safer routes.

  5. (5) Conduct a single point crossover operation for the population to get a better route.

  6. (6) Conduct a mutation operation for the population to get the global optimum route instead of a local optimum route.

  7. (7) Recalculate the value of the fitness function for corresponding binary bit string according to Equation (1).

  8. (8) Judge whether it meets the criterion for stopping. If it meets the condition, stop the operation, go to step (9), otherwise go to step (4)

  9. (9) Output the optimum route.

Figure 4. Flow chart for genetic algorithm for optimum collision avoidance route.

6. SYSTEM SETUP AND SIMULATION RESULTS

6.1. Setup and operation of spatial decision support system

In order to provide a good collision avoidance decision support function, apart from the model itself (the genetic algorithm), a good user interface is indispensable too. Because collision avoidance decisions involve space attributes and geometrical calculations that belong to the problem area of spatial decisions, GIS is very suitable for the setup of a spatial decision support system. This research is different from traditional GIS software. The GIS COM component and Visual Basic.Net were used for its development. Spatial calculations provided by the GIS component are embedded seamlessly in the general information system. This is a customized spatial decision support system for ship collision avoidance route planning. A decision support system established through this system has the following advantages:

  • It does not need to install a whole set of GIS software, only GIS components with the required functions are introduced into the customized system, and the operation is very simple and convenient.

  • General programming language is used to develop the system and model; the macro language attached to GIS software is not used.

So, not only is the execution efficiency better, but also the I/O interface is much more open. The information is easily exchanged and integrated with other navigation instruments or navigation information systems immediately (Beaubouef and Breckenridge, Reference Beaubouef and Breckenridge2000). Figure 5 shows the user interface of this system. The left side shows the spatial operation and display for the collision avoidance route of the GIS component, including the position, guarding ring, and route of the home ship, the position and route of the target ship, the candidate collision avoidance route generated by the genetic algorithm (dashed line), and the recommendation of optimum collision avoidance route. The right side shows the calculation of the genetic algorithm, the parameter setup of collision avoidance, real-time DCPA, TCPA of target ship and home ship. The simulation of collision avoidance measures can be conducted through the genetic algorithm, and the whole collision avoidance process can be displayed by dynamic simulation, so that the effect of the collision avoidance route can be assessed visually.

Figure 5. Spatial decision support system for collision avoidance route planning by genetic algorithm.

6.2. Simulation result

The following simulation result is described in reference to the setup in Figure 5. Assume that the motion data comes from AIS, the course of the target ship is fixed, and the speed is constant at 15 knots. The speed of the home ship is also constant, at 14 knots, and the initial course of the home ship is 000°. Only course change is used to plan the collision avoidance route. Three encounter situations specified in the COLREGS are simulated. The avoidance operations for the following three shortest collision avoidance routes are obtained in accordance with the genetic algorithm.

  • Case 1: A crossing situation from the right front (Figure 6), area A in Figure 1.

    Figure 6. A cross encounter from the right front part, DCPA=0·69, TCPA=76.

  • Case 2: A crossing situation from the right (Figure 7), area B in Figure 1, wherein the DCPA is less than 0, so the target ship passes through the stern of the home ship.

    Figure 7. A crossing situation from the right, DCPA=−0·13, TCPA=77.

  • Case 3: A head-on situation (Figure 8), area F in Figure 1.

    Figure 8. A head-on situation, DCPA=0·23, TCPA=65.

The number shown on Figures 6 to 8 is time (minutes) passed since the beginning of observation. The ship can pass safely, according to the setup requests and the navigational conventions, through the verification of simulation. Figure 9 is the example of Case 1, which shows the evolutionary process for improvement of the length of collision avoidance route i.e., the convergence process for the fitness function of the genetic algorithm. At the eighth generation and the 35th generation, the results of the algorithm have already converged to local optimization. But the local optimization can be moved through secondary genetic mutation at the 28th generation and the 48th generation, in order to obtain global optimization. It shows the obtained collision avoidance route provides not only safe passing, but also the most economic route. Table 1 shows the simulation data and route planning data for genetic algorithms of these three cases. Among them, DCPA and TCPA are the distance and time of CPA between the home ship and the target ship under the initial state without taking any collision avoidance measures. When DCPA is positive, the target ship passes through the bow of the home ship. When DCPA is negative, the target ship passes through the stern of the home ship. The collision avoidance measure is recommended in a route obtained from the results of the genetic algorithm. T1 represents the avoidance time, how many minutes must be taken in turning away from the original course, which means how many minutes are taken in changing course from the original TCPA for safe passing (it must be smaller than this value), and it can be used as the basis for alerts. C1 is the avoidance turning angle (right turn), which is limited within 30 degrees to 60 degrees at the right side of the original course. This will remind the navigator, if the turning angle is not big enough or is less than this angle (it must be greater than this value), that the danger of collision still exists. T2 represents the navigational restoration time after the collision avoidance measure is taken. It is the shortest time for safe passing. If the navigational restoration time is less than this time (it must be greater than this time), the danger of collision still exists. C2 is the turning angle of navigational restoration (the angle with original course), which is limited within 30 degrees to 60 degrees at the left side of the original course. This will remind the navigator, when the turning angle of navigational restoration (must be smaller than this value) is greater than this angle, that there is an approaching danger again. As for the setup of the guarding ring, it depends closely on the avoidance angle, the navigational restoration angle and the DCPA. In order to keep encounters of ships safe, the DCPA should be kept outside the guarding ring, both in the avoidance stage and navigational restoration stages. As the example shows in Figure 7, when T=70, the collision avoidance measure allows the safe passing of the home ship. When the navigational restoration measure is taken at T=75 or T=80, although the navigational restoration course is similar to the course of the target ship, the target ship can be kept outside the guarding ring.

Figure 9. The evolutionary process for calculation of shortest route length.

Table 1. The recommended data for simulation setup and collision avoidance actions of genetic algorithm.

As for time efficiency of execution, although the whole program has not reached the optimum efficiency of the algorithm, the simulation can be finished within 1 minute by employing a PC with an AMD Sempron 2800 1.61 GHz processor, 1G memory, and using Windows XP Professional Edition, can meet the demands of real-time navigational decision support.

7. CONCLUSIONS

This research combines the safety domain of ship and the concept of the COLREGS, through simulating the biological evolution model, and adopts parameters such as avoidance time, avoidance turning angle, navigational restoration time and navigational restoration angle as the basis for genetic coding of the genetic algorithm. Not only can it save calculation space and time, but it can also provide a practical and meaningful application to the navigator. A safety-critical recommendation for the shortest route of collision avoidance can be obtained by a more objective and correct simulation that meets theoretical restraints from an economical viewpoint. Although the navigator might not adopt such an avoidance route from actual conditions or from psychological cognition, this route represents a recommendation of the shortest route for the safe passing of the ship. The turning angle and time on this route can be regarded as the basis for safe critical values or alerts. Although this research used a single ship as the demonstration, the same principles can be applied to multiple targets. Even after the GIS information is combined, multiple fixed targets and long-distance navigation projects can be planned. In addition, as for the setup of the ship domain, where the symmetrical guarding ring is used as the setup basis at present, in the future, it can combine GIS geometric processing and a spatial analysis function to carry on the collision avoidance route planning of asymmetrical domains, so that simulation results will have more applications. Considering the processing efficiency of distributed processing, the parallel calculation characteristics of genetic algorithms can be used to build an evolutionary mechanism in the parallel processing environment, in order to improve efficiency for problem solving, and to meet the needs of real-time decision support for navigation. When the present collision avoidance model and the GIS platform are used as the basis, and when a suitable decision model, navigation instrument and Electronic Chart Display and Information System (ECDIS) are combined, this can actually be used for decision support in collision avoidance for ship navigation and VTS monitoring on water.

ACKNOWLEDGMENTS

It is appreciated that this research is subsidized by funding from the National Taiwan Ocean University (NTOU-RD972-01-03-34-01).

References

REFERENCES

Back, T. (1996). Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press.CrossRefGoogle Scholar
Beaubouef, T. and Breckenridge, J. (2000). Real-world issues and applications for real-time geographic information systems (RT-GIS). The Journal of Navigation, 53, 124131.CrossRefGoogle Scholar
Cockroft, A. N. (1984). Collision at Sea. Safety at Sea, 1719.Google Scholar
Colley, B. A. (1984). A marine traffic flow and collision avoidance computer simulation. The Journal of Navigation, 37(2), 232250.CrossRefGoogle Scholar
Davis, P. V.Dove, M. J. and Stockel, C. (1980). A computer simulation of marine traffic using domains and arenas. The Journal of Navigation, 33(2), 215222.CrossRefGoogle Scholar
Davis, P. V., Dove, M. J. and Stockel, C. T. (1982). A computer simulation of multi-ship encounters. The Journal of Navigation, 35(2), 347352.CrossRefGoogle Scholar
Goodwin, E. M. (1975). A statistical study of ship domains. The Journal of Navigation, 28(3), 328344.CrossRefGoogle Scholar
Ito, M., Zhang, F. and Yoshida, N. (1999). Collision avoidance of ship with genetic algorithm. Proceedings of 1999 IEEE International Conference on Control Applications, 17911796.CrossRefGoogle Scholar
Jones, K. D. (1978). Decision Making when using collision avoidance system. The Journal of Navigation, 31(2), 173180.Google Scholar
Kao, S.-L., Lee, K.-T., Chang, K.-Y. and Ko, M.-D. (2007). A fuzzy logic method for collision avoidance in vessel traffic service. The Journal of Navigation, 60, 1731.CrossRefGoogle Scholar
Lamb, W. G. P. (1985). The calculation of marine collision danger. The Journal of Navigation, 38(3), 173180.CrossRefGoogle Scholar
Lee, S. M., Kwon, K. Y. and Joh, J. (2004). A fuzzy logic for autonomous navigation of marine vehicles satisfying COLREG guidelines. International Journal Of Control Automation And Systems, 2, 171181.Google Scholar
Li, L.-N., Yang, S.-H., Cao, B.-G. and Li, Z.-F. (2006). A Summary of Studies on the Automation of Ship Collision Avoidance Intelligence (in Chinese). Journal of Jimei University, China, 11(2), 188192.Google Scholar
Lin, H. S., J, X. and Michalewicz, Z. (1994). Evolutionary algorithm for path planning in mobile robot environment. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference, 211216.Google Scholar
Liu, D., Wu, Z. and Jia, C. (2004). Decision making model of dCPA, tCPA and object's movement parameter (in Chinese). Journal of Dalian Maritime University, China, 30(1), 2225.Google Scholar
Liu, Y.-A., Liu, J., Wu, J. and Zou, X.-H. (2007). Application of simulated annealing algorithm in turning angle to avoid collision between ships (in Chinese). Shipbuilding of China, China, 48(4), 5357.Google Scholar
Smierzchalski, R. and Michalewicz, Z. (2000). Modeling of ship trajectory in collision situations by an evolutionary algorithm. IEEE Transactions On Evolutionary Computation, 4, 227241.CrossRefGoogle Scholar
Statheros, T., Howells, G. and McDonald-Maier, K. (2008). Autonomous ship collision avoidance navigation concepts, technologies and techniques. The Journal of Navigation, 61, 129142.CrossRefGoogle Scholar
Zhu, X., Xu, H. and Lin, J. (2001). Domain and its model based on neural networks. The Journal of Navigation, 54(1), 97–103.CrossRefGoogle Scholar
Zou, X.-H. and Ni, T.-Q. (2006). Applied research of genetic algorithm in the amplitude decision of ship steering and collision avoidance (in Chinese). Shipboard Electronic Countermeasure, China, 29(3), 6669.Google Scholar
Figure 0

Figure 1. Division diagram for ship encounter situations (Liu et al., 2007).

Figure 1

Figure 2. Collision avoidance decision model after the home ship has turned (Liu et al., 2004).

Figure 2

Figure 3. Binary gene coding of a collision avoidance route.

Figure 3

Figure 4. Flow chart for genetic algorithm for optimum collision avoidance route.

Figure 4

Figure 5. Spatial decision support system for collision avoidance route planning by genetic algorithm.

Figure 5

Figure 6. A cross encounter from the right front part, DCPA=0·69, TCPA=76.

Figure 6

Figure 7. A crossing situation from the right, DCPA=−0·13, TCPA=77.

Figure 7

Figure 8. A head-on situation, DCPA=0·23, TCPA=65.

Figure 8

Figure 9. The evolutionary process for calculation of shortest route length.

Figure 9

Table 1. The recommended data for simulation setup and collision avoidance actions of genetic algorithm.