2. CONTRASTING HUMAN COGNITIVE ABILITIES AND INTELLIGENT ALGORITHMS FOR SHIP COLLISION AVOIDANCE

Collision avoidance is one of the major issues that mariners face. Therefore, it is not surprising that autonomous ship navigation success depends on the development of efficient real-time intelligent algorithms for collision avoidance. Most of these algorithms attempt to imitate human piloting cognitive abilities (Robert et al., Reference Robert, Hockey, Healey, Crawshaw, Wastell and Sauer2003). To understand better the cognitive abilities of the “captain” within the ship, and their similarities or differences to the intelligent navigation algorithms, we must take into consideration all the human operations that are performed for collision avoidance purposes. These operations can be understood better by observing the factors that influence ship collision avoidance. These factors illustrated in Figure 1 are now introduced and discussed.

• • Ship Type. The ship type (e.g. sail boat, speed boat, commercial ship, passenger ship etc.) defines the properties of the transport (e.g. manoeuvrability, speed, pay-load, weather conditions tolerance etc.) within the water medium. Each type of ship employs different kinds of evasive manoeuvres for collision avoidance, since speed and agility can differ significantly from one ship type to another. For each ship type, the captain and crew have special training. Then again, the CA autonomous navigation algorithms “understand” ship type as “ship dynamic” or “ship mathematical model” (e.g.(Lisowski, Reference Lisowski1985, Browning, Reference Browning1991, Yavin et al., Reference Yavin, Frangos, Miloh and Zilman1997, Abril et al., Reference Abril, Salom and Calvo1997)). These models provide a prediction of ship behaviour (based on inertial and fluid mechanics rules) but sometimes are very simplistic producing erroneous predictions, or very complex to operate in real-time.

• • Traffic Categories. All forms of sea traffic, (e.g. a vessel, during its journey from the port to the target destination) can collide with another vessel or an obstacle. We can divide the types of traffic into two main categories: 1) traffic within confined environment (e.g. ports or canals) (El-Kader et al., Reference El-Kader, El-Soud, El-Serafy and Hassan2003) and 2) traffic in open sea waterways. In both traffic categories, we have to take into consideration the additional traffic complexity caused by the under surface environment (seabed level, wrecks and other underwater obstacles), as well as the random dynamic and static sea obstacles. Ship collision avoidance in a confined environment is based on guidance via the communication between the local traffic control station (port or canal traffic control) and the piloting crew of the ship. On the other hand, open sea collision-free navigation is based on the communication of the captain and the encountered ship or ships, as well as the COLREGs guidelines. It is important to note that most of the intelligent algorithms for ship navigation do not communicate among themselves or with the traffic control station. Therefore, these algorithms calculate the safe and optimal trajectory for collision avoidance (Lisowski and Smierzchalski, Reference Lisowski and Smierzchalski1994, Lisowski and Smierzchalski, Reference Lisowski and Smierzchalski1995, Graczyk et al., Reference Graczyk, Jarzebski, Brebbia and Burns1995, Smierzchalski and Michalewicz, Reference Smierzchalski and Michalewicz2000, Smierzchalski and Michalewicz, Reference Smierzchalski and Michalewicz1998, Hong et al., Reference Hong, Harris and Wilson1999) relying on first, the current state (speed, direction) of each encounter vessel or ship and second, the COLREGs (Wilson et al., Reference Wilson, Harris and Hong2003, Lee and Kim, Reference Lee and Kim2004).

• • Weather. The weather conditions in the water and atmosphere influence every aspect of the ship navigation. The weather manipulates each type of ship differently (e.g. sailing boat or engine powered vessels). Collision avoidance in different weather conditions requires different evasive manoeuvres from the piloting crew. For example, in severe weather conditions, the ship manoeuvres have to combine safety (avoid capsizing or sinking) and collision avoidance concurrently. In most autonomous navigation algorithms, the sea weather conditions are rarely considered (Zeng, Reference Zeng2003).

• • Navigation Technology. Last but not least, on-board technologies assist the ship-crew to navigate safely and efficiently. Nowadays, maritime aid technologies include Global Positioning System (GPS), Radar, Automatic Radar Plotting Aid (ARPA) (Zeng, Reference Zeng2003, Pedersen, Reference Pedersen1999) and atmospheric and water weather monitoring instruments. A considerable number of the algorithms for ship autonomous collision avoidance consider that the ships are equipped with GPS and ARPA (Zeng et al., Reference Zeng, Ito and Shimizu2000, Xiao-Ming and Ito, Reference Xiao-Ming and Ito2001). But none of these algorithms take into consideration all the instrumentation, navigational data and communication for collision avoidance that most of the modern ships have available.

Figure 1. Ship navigation factors influence collision avoidance.

Each of the above factors and any combination of them require human operation for ship collision free navigation. These operations are subjective to each individual captain and his or her training and cognitive abilities. The clarification or the human cognitive abilities for collision avoidance is the key point of the design, of any nature of the CA intelligent algorithms. Consequently, the investigation of human cognitive demands for collision avoidance (Robert et al., Reference Robert, Hockey, Healey, Crawshaw, Wastell and Sauer2003) is useful. Part of this investigation shows that mariners' preference of collision avoidance manoeuvres varies quite significantly (Curtis, Reference Curtis1978). In real-life tasks, piloting crews frequently make course changes up to 30 degrees to minimise uncertainty but there is also a significant number of occasions when piloting crews are reluctant to make large course or speed changes (Cahill, Reference Cahill1983), since there is a trade-off between collision avoidance and track-keeping. It is worth noting that one of the reasons for the Titanic tragedy (Lord, Reference Lord1955) was the unwillingness of the piloting crew to change the ship's speed.

Ship navigators have the ability to cope with CA by planning ahead a sequence of possible evasive manoeuvres, which are updated in real-time to sustain a safe path for the ship. The sequence of these manoeuvres assembles the evasive trajectory of the ship that can be considered as knowledge-based (Rasmussen, Reference Rasmussen1983, Stefik, Reference Stefik1995) and have a degree of uncertainty. This degree of uncertainty can be minimised by COLREGs. However, COLREGs define vessels' actions for collision avoidance between two ships. Therefore, even if COLREGs are in place to dictate the decisions of evasive actions, the analysis and performance of these guidelines are highly subjective (especially in many-ship encounters that incorporate uncertainty and unpredictability). These can lead to marine accidents (James, Reference James1994, Wagenaar and Groeneweg, Reference Wagenaar and Groeneweg1987).

Marine accidents can also be reduced by ship navigation aid technologies used by an experienced officer. Nowadays, the majority of commercial and transportation ships are equipped with Automated Radar Plotting Aid (ARPA). ARPA replaces the radar handmade plots for the graphical representation of navigational status of the tracking objects. Then again, it has been observed that mariners are more likely to overlook the COLREGs when performing “get away” manoeuvres with the support of ARPA (Lee, Reference Lee and Sanquist1996). Subsequently, the use of ARPA can have negative results when operated by inexperienced officers, since reported data shows that 56% of major maritime collision includes violation of “the rules of the road” (COLREGs) (Cockroft, Reference Cockroft1984, Perrow, Reference Perrow1984).

In addition to the above, radar navigation has its risk for collision, since the probability of the target ship reaching the future position varies (Imazu et al., Reference Imazu, Sugisaki and Min1979). To minimise this problem, and further to improve the collision avoidance of a ship, an electronic-mapping intelligent support for ship navigator system is proposed by (Dmitriev et al., Reference Dmitriev, Kolesov, Osipov and Romanycheva2003). A further study of how mariners have to cross alleys safely is detailed in (Gung, Reference Gung1990).

Another technique to reduce the violation of collision avoidance rules by the piloting crew is by knowledge acquisition (Hammer A., and K., Reference Hammer, and 1990). Knowledge acquisition refers mainly to the information of the near future (1 sec-1 min) trajectory of possible encounter to the own-ship surface vehicles. Furthermore, a quantitative risk assessment of the possible collision avoidance manoeuvre can be automatically produced by the obtained marine data (Jones, Reference Jones1978). A similar study of how to provide suitable navigation information for the mariners and a risk analysis of evasive manoeuvres is proposed (Colley et al., Reference Colley, Curtis and Stockel1984, Lamb, Reference Lamb1985).

In conclusion, the lawful collision free guidance of a ship requires a highly trained and experienced officer in charge (Zhao, Reference Zhao1996) who will minimise the human error in ship navigation by utilising appropriately ARPA, knowledge acquisition and safety domain processing intelligent support systems. On the other hand, intelligent algorithms for CA may possibly suppress the navigational error to zero, since they approach the collision avoidance problem in a more objective way than humans. Nevertheless, the real-time demands of the collision avoidance navigation, the vastly poor (compared to humans) pattern recognition performance and the one-dimensional or non-existing communication operations among these algorithms place them far below the average piloting crew collision avoidance abilities.

3. SHIP COLLISION AVOIDANCE MATHEMATICAL MODELS AND ALGORITHMS

Currenly, collision avoidance problems at sea have also been addressed by mathematical models and algorithms. These models and algorithms simulate a variety of factors that influence water based collision avoidance, such as, ship's dynamics, ship's vector of motion (map location, speed and direction), ship's manoeuvres and trajectories, etc. Most of the ship's dynamics mathematical models (Browning, Reference Browning1991) consider the ship to have six degrees of freedom as shown in Figure 2.

(1)

Equation 1 expresses the six degrees of freedom of a ship based on Newton's second law of motion. The mathematical algorithms that generate a sequence of real-time manoeuvres can be based on static, kinetic, dynamic and matrix models (Lisowski, Reference Lisowski1985), and various methods for solving them (Lisowski and Smierzchalski, Reference Lisowski and Smierzchalski1995). On the other hand, some other models that are focused on the safe path obtain the safe path trajectory with different methods but with almost the same assumptions. In particular, these assumptions are: first, the potential collision occurs in the open sea (no land or water depth). Second, the target ships do not change their velocity (speed and course). Finally, the encountered ships do not communicate amongst themselves.

Figure 2. Six degrees of freedom.

(Graczyk et al., Reference Graczyk, Jarzebski, Brebbia and Burns1995) proposes the use of a Potential Collision Threat Area (PCTA). This algorithm is founded on a single change of course AND/OR the speed of the own-ship. The principle of the PCTA is that the vector of the own-ship is outside the dangerous area that is defined. The above model forms a general guideline for a ship to follow the safe path but not the optimal trajectory. An optimal trajectory method proposed by (Lisowski and Smierzchalski, Reference Lisowski and Smierzchalski1995) dictates that a series of delicate evasive manoeuvres of the own-ship has to be performed. The problem of evasive manoeuvres is modelled as a non-linear programming task. The non-linearity of the tasks depends on the kinetics of the own-ship. The overall approach of the model is that the safe course deviation is based on the nonlinear admittance restrictions. A more specific own-ship course optimisation model for a predefined marine environment can be achieved by point-mass models for ship motion (Skjong and Mjelde, Reference Skjong and Mjelde1982). An alternative model for ship get away manoeuvres in confined waters is also the rigid-body dynamic model for ship motion (Yavin et al., Reference Yavin, Zilman and Miloh1994, Yavin et al., Reference Yavin, Miloh and Zilman1995) based on stochastic optimum control (Lewis, Reference Lewis1986). On the other hand, a specialised model for collision free overtaking is proposed (Curtis, Reference Curtis1986).

More general methods for collision avoidance include the modelling of the own-ship and its immediate environment (Burns et al., Reference Burns, Blackwell and Calvert1988). For example, (Yavin et al., Reference Yavin, Frangos, Miloh and Zilman1997) proposes a tanker realistic model for collision avoidance manoeuvres between strange-ships and other offshore installations and obstacles. The collision avoidance problem can be seen from a different angle, like the Line of Sight Counteraction Navigation (LOSCAN) algorithm (Wilson et al., Reference Wilson, Harris and Hong2003) in which the problem of two ship encounters is solved by reversing the idea of a traditional missile proportional navigation, recognising that the target is to avoid the strange-ship. The main concept of the algorithm is to generate acceleration commands in order to increase the misalignment between the ships relative velocity and the line-of-sight.

From the above, we can categorise the mathematical models and algorithms for collision avoidance into three main categories:

• • Firstly, the mathematical models that simulate ship dynamics.

• • Secondly, the multi-ship collision avoidance algorithms that optimise the ships trajectory for CA.

• • Finally, the real-time collision avoidance algorithms.

The last category is not based on a predefined trajectory generation as happens in the second category. Both the second and third categories can use the first (ship dynamics) to obtain more accurate collision avoidance results.

4. SOFT COMPUTING TECHNIQUES FOR SHIP COLLISION AVOIDANCE

Hybrid Systems

Ships form a non-linear and ill-defined system. This means that ships and their immediate environments constitute an extremely complex system to be described in terms of precise mathematical models. Even if we have precise mathematical models for an autonomous system, the time for the decision making of the system will potentially not be reasonable for a real-time application under, for example, severe weather and navigation conditions. For the above reasons, a fuzzy approach (Zadeh, Reference Zadeh1965) to navigational systems has been considered. However, sometimes fuzzy logic itself is insufficient, so neuro-fuzzy or fuzzy hybrid expert-systems come to complete the picture of the autonomous ship navigation challenge. A general explanation of fuzzy logic expert-systems and rule-based control is presented in (Efstathiou, Reference EFstathiou1988).

Neural networks (Khanna, Reference Khanna1990, Anderson, Reference Anderson1995) have succeeded in many applications (Patterson, Reference Patterson1996), including 2 dimensional robot navigation (Xianyi, Reference Xianyi1999), with their distinct ability to learn. In addition, NN with the aid of fuzzy logic can form neuro-fuzzy systems. This combination of neural networks and fuzzy systems is proposed by (Harris et al., Reference Harris, Hong and Wilson1999). This intelligent guidance system is based on the introduction of neuro-fuzzy networks multi-step ahead predictor for ship obstacle avoidance. The approach is generic, includes the line of sight concept and its use can be extended to aircraft and missile guidance problems where the dynamics change significantly and unpredictably. After all, a data-fusion algorithm generates the desired waypoints of the own-ship route.

Going further to more complex hybrid systems for ship autonomous navigation, it is necessary to introduce the term Virtual Field Force (VFF) that originates from mobile robots research (Borenstein and Koren, Reference Borenstein and Koren1989) and is based on the concept of “artificial potential field” (Khatib, Reference Khatib1985). The general concept of the VFF is illustrated in Figure 3 where VFF related forces are illustrated. is the vector of the force between the ship and the desired waypoint. is the vector of the force between the obstacle and the ship. The resultant force from the above two forces is the direction of the ship for obstacle avoidance. An example of VFF utilisation in conjunction with evolutionary programming and neural networks for mobile robots is proposed by (Im and Oh, Reference Im and Oh2000). In ship autonomous navigation, (Lee et al., Reference Lee, Kwon and Joh2004) introduces a fuzzy logic autonomous navigation algorithm based on VFF, which satisfies COLREGs. For the purpose of autonomous ship navigation, a Modified VFF is used. This method is suitable for both track-keeping and collision avoidance. Furthermore, the algorithm has the ability to handle an immediate static and dynamic environment. From Figure 3, we can see the VFF concept of two forces at any given point in time. It is apparent that the VFF concept cannot provide a track-keeping capability. The modified algorithm provides true track-keeping as well as collision avoidance in static and dynamic ship environment within COLREGs guideline. This is achieved by the addition of a perpendicular force to the desired course as shown in Figure 4.

Figure 3. VFF general concept illustration.

Figure 4. Modified VFF with the addition of force vector.

Another category of hybrid systems for collision avoidance is proposed by (Lee and Kim, Reference Lee and Kim2004). This technique is based on heuristic search reinforced by fuzzy relational products (Bandler and Kohout, Reference Bandler and Kohout1980) and COLREGs. Generally, COLREGs define a guideline for collision avoidance between two encounter ships. On the other hand, the applications utilising the heuristic search technique can cope with many-ship encounters, but at the same time they introduce an inclination to violate COLREGs. The inclination of COLREGs to be violated in a multi-ship environment can be minimised by the method of (Lee and Kim, Reference Lee and Kim2004).

Finally, a hybrid system for collision avoidance and track-keeping is proposed by (Hwang et al., Reference Hwang, Yang and Chiang2001). These systems combine fuzzy logic, expert systems and state space H _∞ (Hwang et al., Reference Hwang, Yang and Chiang2001). The collision avoidance is carried out by the fuzzy expert system. The system utilises a knowledge-base of facts and rules with the aid of an inference engine. The inference engine is also responsible for the simulation of the expert system decisions for ship collision avoidance. Finally, a robust state space H _∞ controller guides the autopilot safely on the route that is predetermined by the fuzzy-expert system. The main purpose of the state space H _∞ control is to keep the closed-loop system stable by the use of an optimal control law. This control law can be defined by a transfer function involving exogenous inputs (weather, seaways traffic) with endogenous ship control actions maintaining the control actions minimal. At the end of the algorithm's routines, the H _∞ autopilot system materialises the avoidance action dictated by the fuzzy collision avoidance expert system under the worst exogenous systems inputs.

Evolutionary Algorithms

An alternative technique for collision avoidance involves the utilisation of evolutionary techniques in the framework of evolutionary computation (Vonk et al., Reference Vonk, Jain and Johnson1997), which are a collection of stochastic optimisation algorithms loosely based on the biological evolutionary theory of Charles Darwin (Glick and Kohn, Reference Glick and Kohn1996). Evolutionary computation is in general an optimisation tool. More specifically, it is a search strategy for an infeasible large search space. In addition to the above, evolutionary algorithms have proved their potential for solving complex real world (Back, Reference Back1996, Zeng, Reference Zeng2003) problems. The underlying generic principle of these techniques is based upon the “survival of the fittest”. For instance, in collision avoidance, they maintain a population of assign paths, and through a process of variation and selection, find a near-optimum solution. Finally, they also constitute an interesting category of heuristic search (Stewart et al., Reference Stewart, Liaw and White1994), which is also to aid the autonomous ship navigation. We define heuristic search as the technique that does not follow a strict algorithmic solution to a problem. More specifically, heuristics are a group of effective rules guiding a system to perform searches in a problem space.

The category of GAs has been widely employed successfully in mobile robots (Lin et al., Reference Lin, , and Michalewicz1994) where ship collision free navigation is analogous to the similar problem of safe navigation of a mobile robot. Therefore, the evolutionary method named evolutionary planner navigator (EP/N) system originally designed for mobile robot evasive steering and path generation in predefined environment presented in (Jing et al., Reference Jing, Michalewicz, Lixin and Trojanowski1997) is potentially useful for ship navigation and it has been further modified for ship encounter free navigation in (Smierzchalski and Michalewicz, Reference Smierzchalski and Michalewicz2000). This study is named θEP/N++ and it adds the concept of time to the system. The element of time allows for evaluation of the system's behaviour and performance under real-time constraints (e.g. moving obstacles). Finally, it introduces own-ship variable speed, so a safe-path of a ship can be tracked in dynamic or static environment. All of the above variables can be controlled and optimised by the aid of evolutionary theory by using genes to form chromosomes. Each gene contains information such as the ship coordinates. In the above study, each chromosome has a variable-length sequence of genes. These genes specify coordinates (x _i, y _i) of the turning points, speed of the ship and interconnections between the genes within the same chromosome. A more simplistic model of collision avoidance based on a single gene approach is proposed by (Ito et al., Reference Ito, Zhang and Yoshida1999). This gene contains only the geographical position of the ship (latitude, longitude). On the other hand, a more realistic genetic algorithm for ship collision avoidance is proposed by (Zeng, Reference Zeng2003). This genetic algorithm coding introduces a gene with additional information to that in the conventional coding. These genes include, additionally to the position and speed of own-ship described in the above, the weather conditions, which are defined as “noise” (wind, wave and sea current). The mathematical representation of every chromosome is shown in equation 2.

(2)

Where: x is the chromosome, s is the gene, and k is the length of the chromosome (number of genes in one chromosome). In this system, the chromosome length is also a variable quantity and it is strongly dependant on the navigation conditions, (weather or traffic density). In other words, when no ship or obstacle is in the own-ship vicinity, the chromosome for the ship's safe trajectory contains only two genes, which is a straight line between the planned route waypoints. On the other hand, when additional obstacles that pose a potential threat of collision are added to the ship's neighbourhood, the enhanced system is modelled by the introduction of two genes in the variable length chromosome. A representation of the chromosomes of the study (Zeng, Reference Zeng2003) is shown in Figure 5. The black genes represent the current and the target ship location. They are parts of the planned route. The white genes are randomly selected within the boundaries between the two black ones.

Figure 5. Chromosome structure of Zheng study.