3.1. Why evolutionary method?

It may be argued that Rule 19 of the COLREGS (1972) may be directly applied by means of a deterministic algorithm. Such an algorithm is relatively easy to implement and furthermore is characterised by low computational complexity, which means it could be relied on to return the results instantly. If so, then why invest time in an evolutionary method, which is indeterminist and much more complex? The reason for this lies in the flexibility of the evolutionary approach. It is true that a deterministic algorithm can easily handle an isolated situation of an encounter of two ships in open waters. However, when restricted waters are considered, there are additional problems of stationary obstacles, limited sea room etc., which also have to be taken into account when proposing a collision avoidance manoeuvre. Unfortunately, a simple deterministic algorithm cannot deal with that. Although there are deterministic methods for finding paths in an environment containing obstacles and barriers (e.g., maze routing algorithms or methods based on graph theory), their computational complexity is a squared function of a geographical distance (Chang et al., Reference Chang, Jan and Parberry2003), which translates to a high computational time. What is more, basic versions of these methods handle only eight moving directions and the computational time additionally rises when higher resolutions of course alterations are taken into account. Evolutionary algorithms on the other hand are particularly fitted for operating within these kinds of constraints and their flexibility allows for applying the COLREGS (1972). Therefore they are appropriate for applying in a more general problem of an encounter of vessels not in sight of one another, both in open or restricted waters.

3.2. Detecting collisions and stationary constraint violations

Detecting stationary constraint violations is relatively easy. It is assumed that, based on an electronic chart, it is possible to decide for a given cell of a map whether it is passable or not for a particular ship. Knowing this, all ship tracks are checked, segment by segment, to see if they do not cross impassable cells and if there are no impassable cells in the vicinity of ship tracks.

As for collisions with other vessels, it is assumed that each violation of a ship domain is a collision and that it should be avoided. Ship domain violations are detected by comparing ship tracks with each other. It is assumed that each track can be approximated by a sequence of straight segments joined by short arcs (to reflect dynamics of course alteration manoeuvres). For a given pair of ship tracks, a check is made of which of their segments overlap in time. The overlapping segments are compared and points of closest approach are found either in a classic sense (Closest Point of Approach) or in a domain sense. In the latter case, a domain-dependent approach factor is computed. If a ship's domain is violated in any of these points of closest approach or in any of the segments' endpoints, a collision is registered and the degree of domain violation is stored.

3.3. Collision avoidance operators

If a collision risk has been registered for a ship track, the track is checked segment by segment to determine ships' positions and courses, when the distance to a target is about six nautical miles. For these data it is then checked whether the target is forward of the beam, abeam or abaft the beam. In case of the target forward of the beam it is additionally checked whether this target is to be overtaken or not and in case of the target abaft the beam, whether this target is overtaking the central ship. Based on these data, the range of correct course alterations is determined, as well as the time when the course alteration manoeuvre should be initiated. For the target forward of the beam the manoeuvres are always planned for a distance of at least four nautical miles. In case of the target abaft the beam, the manoeuvres are either planned for a distance of three nautical miles (if the target is overtaking the central ship) or for a distance of four nautical miles (otherwise). In case of a whole range of possible course alterations, a course alteration is chosen randomly from this range. Once a course alteration has been determined, it is decided for how long the new course should be kept, before a ship can safely get back to its route.

3.4. Detecting violations of Rule 19

Violations are detected according to the following algorithm:

1. 1. It is assumed that we are given a pair of ships' tracks, one belonging to the own ship (the ship of interest here) and the other to a target (the other ship). Ships' tracks are checked segment by segment to determine positions and courses of both ships when their distance is 6 NM.

2. 2. Based on the motion parameters, the type of encounter is decided:

   1. a) overtaking the target (the target vessel forward of the beam and the own ship approaching her at more than 22·5 degrees abaft her beam),

   2. b) the target forward of the beam but not being overtaken,

   3. c) the target abaft the beam overtaking the own ship (a target approaching the own ship at more than 22·5 degrees abaft her beam),

   4. d) the target abaft the beam but not overtaking the own ship.

   In case of c) (being overtaken by the target) the own ship is expected to keep its course until the distance decreases to 3 NM. In all other cases it is expected to initiate a manoeuvre at a distance of 4–6 NM.

3. 3. If the own ship is supposed to manoeuvre at a distance of 4–6 NM (all cases except being overtaken), the behaviour of the own ship directly following the 6 NM distance point is analysed. If the own ship has not executed any manoeuvre before a 4 NM distance has been reached, has turned to port when not overtaking, or her manoeuvre was insufficient, a major violation is registered. To make sure that a manoeuvre of the own ship is sufficient, apart from checking it against the real track of the target, it is also additionally checked against a virtual manoeuvre-free track of the target. If the own track collides with this virtual manoeuvre-free track of the target, it means that the own ship's manoeuvre has been insufficient and it is registered as a major violation.

4. 4. If the own ship is to be overtaken, the behaviour of the target is analysed and it is checked whether the target ship has changed her course before a 4 NM distance has been reached and whether this turn has been sufficient. If so, then any course alteration of the own ship performed prior to the target's manoeuvre is registered as a minor violation. (The target is allowed to turn to starboard or to port when overtaking so the overtaken ship should make sure she does turn in the same direction.)

5. 5. If the own ship is being overtaken and the target does not initiate a correct manoeuvre before a 4 NM distance is reached, then the own ship is expected to initiate an evasive action herself at a 3 NM distance. The own ship's track is therefore checked. If the own ship does not perform a manoeuvre, performs it too quickly, or the course alteration is insufficient or towards the target then a major violation is registered.

6. 6. Any manoeuvres of the own ship towards the target abeam or abaft the beam are registered as a major violation, even if the own ship is not being overtaken.

It might be argued that in some cases (e.g., limited sea room, stationary obstacles etc.), a course alteration compliant with Rule 19 may not be possible and therefore the lack of it should not be considered a violation. However, deciding if such a situation occurs is not always feasible on the computational level and applying such a policy would be in conflict with the indeterminist nature of EA. Therefore all course alterations not compliant with Rule 19 are registered and then penalised (Section 3.6) but the penalties are smaller than those received for domain violations or navigating in direct vicinity of an impassable area. As a result ship tracks whose only fault are lack of manoeuvres will always be favoured over those which collide with other ships or obstacles.

3.5. Eliminating violations of Rule 19 by means of specialised operators

Evolutionary operators, which are used for eliminating these violations, work similarly to collision avoidance operators. What is different is the fact that instead of a collision, a violation of Rule 19 has been detected. Usually this means that a ship avoided a collision by executing an incorrect manoeuvre. A ship track is therefore analysed and the incorrect manoeuvre is replaced with one compliant with Rule 19. It is done almost identically to applying a collision avoidance operator (described in Section 3.3).

3.6. Penalising violations of Rule 19

Six kinds of violations and corresponding penalties are introduced. The first two violation types (a and b) are mutually exclusive for a single ship track.

1. a) Lack of manoeuvre when needed or an insufficient manoeuvre (a ship is obliged to manoeuvre but its track collides with a straight, manoeuvre-free track of a target so an escape action of a target is needed):

   (1)$$violation\_penalty = target\_domain\_violation$$
   The penalty is proportional to the degree of a target's domain violation that would happen if the target did not take an escape action.

2. b) Incorrect value of course alteration:

   (2)$$violation\_penalty = (course\_alteration\_difference/90)*0.1$$
   The penalty is proportional to a difference between the current course alteration and the nearest one that would be acceptable according to Rule 19.

3. c) Too large or too small distance to a target, when initiating a manoeuvre

   • • for too small distance from a target (less than 3 NM in case of being overtaken or less than 4 NM in all other cases):

     (3)$$violation\_penalty = distance\_difference*0.2$$

   • • for too large distance from a target (more than 4 NM in case of being overtaken or more than 6 NM in all other cases):

     (4)$$violation\_penalty = distance\_difference*0.1$$
     It might be argued that it is not a problem if a distance from a target is too large (more than 6 NM), when initiating a manoeuvre. However, were this not penalised, the method would regularly plan ship tracks with manoeuvres being made too soon, which is undesired. Therefore such behaviour is penalised moderately to discourage the method from doing this, but still enable it, if there is no other option.

4. d) Too frequent manoeuvres (after changing her course a ship changes it again too soon).

   (5)$$violation\_penalty = \left[ {(\min \_seg\_l - actual\_seg\_l)/\min \_seg\_l} \right]*0.1$$
   A minimal acceptable value of a track's segment length is defined (2 NM by default). All segments shorter than this minimal value are penalised proportionally to the difference between the actual segment length and the defined minimal segment length.

The values and formulas for penalties presented in this section have been subject to modifications in the course of simulation experiments. The presented values are the ones that resulted in the best performance of the method.

3.7. Evaluation of ship tracks

In EA all sets of ship tracks are evaluated by the specially designed fitness function, which should reflect optimisation criteria and constraints (Michalewicz and Fogel, Reference Michalewicz and Fogel2004). The fitness function used here is a sum of fitness values of all tracks in a set:

(6)$$fitness = \sum\limits_{i = 1}^n {\left[ {track\_fitness_i} \right]} $$

where:

(7)$$track\_fitness_i = track\_economy\_factor_i * scf_i * caf_i * rvf_i $$

Track_economy_factor _i, scf_i (static constraint factor) and caf _i (collision avoidance factor) have been described in Szlapczynski (Reference Szlapczynski2012). The new element in Equation (7) is rvf _i– a restricted visibility compliance factor, which is computed for each track as follows:

(8)$$rvf_i = 1 - \sum\limits_{\,j = 1}^n {violation\_penalty_j} $$

where violation_penalty _j are the penalties listed a) to d) in section 3.6.

4.1. Ship encounters in restricted visibility in open waters

In this section it is assumed that ships have practically unlimited sea room for manoeuvres and it is tested whether the method is capable of planning simple course alteration manoeuvres in compliance with Rule 19. Six types of encounters were chosen to cover typical situations, where various ships' behaviour is expected according to Rule 19. The initial courses and speeds are set to such values that the encounter would lead to a collision or near-collision had none of them manoeuvred.

In the first example (Figure 2) two ships move in opposite directions. Both of them turn to their starboards when the distance between them diminishes to about 5 NM and later they change their courses again having safely passed each other. In the second example (Figure 3) two ships have initially perpendicular courses and approach the same point. Again, they both manoeuvre to starboard and get back to their original trajectories once the situation is safe. In the third example (Figure 4) one of the ships is overtaking the other. The overtaking ship turns to her starboard and then returns to her original course, while the overtaken one manoeuvres to her port. Both ships return to their trajectories once the faster of the ships has overtaken the slower one. The fourth example (Figure 5), similarly to the first two examples, illustrates an encounter where each ship has the other forward of her beam, though this time their courses are neither opposite nor perpendicular. As expected, both ships turn to their starboards and get back to their trajectories after passing each other. The last two encounters (Figure 6 and Figure 7) are both overtaking situations, with the overtaking ship being either to starboard of the overtaken one (Figure 6) or on her port (Figure 7). In both cases the ships turn away from each other, navigate nearly parallel for some time and finally get back to their trajectories once the overtaking is over and the distance is safe. In general, in all cases the results are compliant with Rule 19. In Figures 3 and 5 both ships manoeuvre differently to when in good visibility conditions, where one of them would be a stand-on vessel. In Figures 4, 6 and 7 both the overtaken and overtaking vessels manoeuvre (in good visibility the overtaking vessel would be obliged to keep out of the way of the overtaken one).

Figure 2.

A solution found for example 1.

Figure 3.

A solution found for example 2.

Figure 4.

A solution found for example 3.

Figure 5.

A solution found for example 4.

Figure 6.

A solution found for example 5.

Figure 7.

A solution found for example 6.

4.2. Ship encounters in restricted visibility conditions in restricted waters

In this section it is assumed that ship tracks must be planned taking into account a map of a particular area, a part of which might not be passable. As a result we are facing a more complex problem. For some examples it might be impossible to separate a course alteration manoeuvre made to avoid collision with another ship from a course alteration manoeuvre made to avoid running aground etc., as these two may be combined in one manoeuvre. Therefore test examples in this section have been specially prepared in such a way that another ship is encountered first and a stationary obstacle is encountered second. For the same reason only one-on-one encounters are depicted, though the method is capable of solving multi-ship encounter situations. As a result, full compliance with Rule 19 can be expected here, despite the environment being different than in the previous subsection.

In Figures 8 to 13 six encounter situations are shown. The manoeuvres are similar to those from Figures 2–7, except that in each example one of the ships has to avoid collision with a landmass after passing the target ship. In Figures 8 and 9 two overtaking situations are shown. In the former the overtaking ship directly follows the overtaken one, and in the latter it approaches from her starboard. In both cases the ships turn away from each other and the overtaking ship passes ahead at a safe distance. In Figures 10 and 11 the two ships have each other forward of the beam, moving either on perpendicular courses (Figure 10) or opposite ones (Figure 11). Both ships manoeuvre to their starboards and change their courses again once the crossing point has been safely passed. In Figure 12 both ships meet similarly to Figure 5 from Section 4.1 (each one forward of the other one's beam), though this time it is impossible for one of the ships to manoeuvre to her starboard because of the high risk of grounding. Therefore the other ship is the only one that manoeuvres here: it navigates parallel to the target and changes her course again after passing the target safely. In Figure 13 an encounter situation is shown, however, unlike in Figures 8 and 9, the overtaking ship approaches from port and the overtaken one cannot manoeuvre to her starboard because of limited sea room. Therefore she keeps her course still while the overtaking ship changes her course to a nearly parallel one for a few miles and then crosses ahead at a safe distance. Analogically to Section 4.1, it is worth noting that the behaviour of ships here is different from that in good visibility: both ships manoeuvre in Figures 8 to 10 and in Figure 13, whereas only one of them would usually manoeuvre if vessels were in sight of one another.

Figure 8.

A solution found for example 1.

Figure 9.

A solution found for example 2.

Figure 10.

A solution found for example 3.

Figure 11.

A solution found for example 4.

Figure 12.

A solution found for example 5.

Figure 13.

A solution found for example 6.

In all of the presented examples (Sections 4·1 and 4·2) safe solutions have been found within the given time for computations (30 seconds) and speed alteration has not been necessary. This was due to the fact that initial distances between ships have always been larger than four nautical miles. In case of a lesser distance when triggering the method's run (especially when already in close quarters situation) speed alteration could have been a necessity, but this is beyond the method's working scope – it is assumed that in such cases the navigator would not consult the system.