International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 4
Number 2
June 2010
191
1 INTRODUCTION
The main approaches to the problem of planning
optimal ship trajectories in encounter situations are
the methods based on either differential games and
evolutionary method. The methods based on dif-
ferential games were introduced by Lisowski
(Lisowski, 2005). They assume that the process of
steering a ship in multi-ship encounter situations
can be modelled as a differential game, played by
all ships involved, each having their strategies.
The second approach – the evolutionary method
of finding the trajectory of the own ship has been
developed by Śmierzchalski (Śmierzchalski, 1998).
For a given set of pre-determined trajectories the
method finds a safe trajectory, which is optimal
according to the fitness function – the optimal safe
trajectory. The method’s main limitation is that it
assumes the target motion parameters not to
change and if they do change, the own trajectory
has to be recomputed.
The approach proposed here combines some of
the advantages of both methods: the low computa-
tional time, supporting all domain models and han-
dling stationary obstacles (all typical for evolution-
ary method), with taking into account the changes
of motion parameters (changing strategies of the
players involved in a game). Therefore, instead of
finding the optimal own trajectory for the un-
changed courses and speeds of the targets, a set of
optimal cooperating trajectories of all ships is
searched for. The early version of this method has
already been described by the author in
(Szlapczynski, in press). The method had been
successfully implemented and tested and the paper
presents some representative simulation results
covering different use cases.
The rest of the paper is organized as follows.
Section 2 contains simulation parameters and is
followed by several types of scenarios, where the
proposed method is able to predict the behaviour of
targets and plan own collision avoidance manoeu-
vre in advance, even though sometimes there is
seemingly no need to perform a manoeuvre at the
moment. These scenarios include the following
situations: a target changing its course because of
landmass (Section 3), a prioritised target changing
its course because of another target (Section 4) and
finally multi-ship encounters with all ships
manoeuvring to avoid collisions on open waters
(Section 5) and restricted area (Section 6). The last
section contains the paper’s summary and conclu-
sions.
2 SIMULATION PARAMETERS
In the scenarios below each stationary constraint is
surrounded by a domain of the size specified by
the user; the default safe distance of 0.25 nautical
mile has been used. As for ship domains – a
Coldwell domain (Coldwell, 1982) has been as-
sumed for all ships. Its default dimensions (used in
all scenarios) are given in Table 1.
Evolutionary Sets of Cooperating Trajectories
in Multi-Ship Encounter Situations - Use Cases
R. Szłapczynski
Gdansk University of Technology, Gdansk, Poland
ABSTRACT: The paper discusses the advantages of a new approach to solving ship encounter situations by
combining some of the assumptions of game theory with evolutionary programming techniques. A multi-ship
encounter is here modeled as a game played by “thinking players” – the ships of different and possibly chang-
ing strategies. The solution – an optimal set of cooperating (non-colliding) trajectories is then found by means
of evolutionary algorithms. The paper contains the results obtained for different cases of situations including
open waters and restricted water regions and the discussion of these results. The already developed version of
the method is fast enough to be applied in the real time on-board collision avoidance systems or VTS systems.
192
Table 1 The dimensions of Coldwell domain used in the sim-
ulation scenarios
Ellipse’s
semi
axes
[n.m.]
Domain centre moved
from the ship’s position
Towards
starboard
[n.m.]
Towards
bow
[n.m.]
Coldwell domain
0.77
0.33
0.1
0.2
The evolutionary parameters values are listed in
Table 2.
Table 2 The evolutionary parameters values used in the simu-
lation scenarios
Number of generations
Population size
Selection method
Mutation probability
(for a single trajectory)
value (from 0% for perfect trajec-
tories to 100% for unacceptable
3 SCENARIO 1: A TARGET MANOEUVRING
TO AVOID COLLISION WITH LANDMASS
The positions, destination points and speeds of the
ships are given in Table 3.
Table 3 The motion parameters of both ships
Speed
[knots]
Course
[degrees]
Position
coordinates
at the start
time [n.m.]
Coordinates
of the desti-
nation point
[n.m.]
x
y
x
y
Own ship
12
90
0
2
10
2
Target 1
12
270
10
3
0
3
The current course of the own ship does not col-
lide with neither the landmass (Figure 1) nor the
target ship (Figure 2).
Figure 12 The own ship’s current course does not collide
with the landmass (black) or its domain (grey).
Figure 13 The own ship (left) course does not collide with
the current course of the target (right). Landmass is not
shown
However, the target’s course collides with the
landmass and the target will perform a collision
avoidance manoeuvre (Figure 3).
Figure 14 The target’s current course collides with the land-
mass so the target will perform a collision avoidance ma-
noeuvre.
The method predicts the target’s manoeuvre and
plans the own ship’s manoeuvre in advance. The
final evolutionary set of two cooperating trajecto-
ries of both ships is shown in Figure 4.
193
Figure 15 The evolutionary set of the two ships’ cooperating trajectories, which avoid collisions with the landmass and each other.
4 SCENARIO 2: A TARGET MANOEUVRING
TO AVOID COLLISION WITH ANOTHER
TARGET
The positions, destination points and speeds of the
ships are given in Table 4.
Table 4 The motion parameters of all ships
Speed
[knots]
Course
[degrees]
Position
coordinates
at the start
time [n.m.]
Coordinates
of the desti-
nation point
[n.m.]
x
y
x
y
Own ship
12
45
0
0
10
5
Target 1
8
0
5
0
5
5
Target 2
17
270
10
2.5
0
2.5
The current course of the own ship does not col-
lide with neither of the two prioritised ships. The
safe trajectories for encounters with either target 1
only or target 2 only are shown in Figure 5 and
Figure 6 respectively. As can be seen – no ma-
noeuvres are needed.
Figure 16 The own ship’s current course (left) does not col-
lide with target 1 (right).
Figure 17 The own ship’s current course (left) does not col-
lide with target 2 (right).
194
However, the first target’s course collides with
target 2 and the target 2 is a “stand-on vessel” ac-
cording to COLREGS (Cockcroft, 1993). As a re-
sult, the first target will perform a collision avoid-
ance manoeuvre (Figure 7).
The method predicts the manoeuvre of target 2
and plans the own ship’s manoeuvre in advance.
The final evolutionary set of three cooperating tra-
jectories is shown in Figure 8.
Figure 18 The first target’s current course (left) collides with
target 2 (right) and target 1 performs collision avoidance ma-
noeuvre.
Figure 19 The evolutionary set of the three ships cooperating trajectories, which avoid collisions with each other.
195
5 SCENARIO 3: A GROUP OF SHIPS
MANOEUVRING TO AVOID COLLISIONS
WITH EACH OTHER ON OPEN WATERS
The positions, destination points and speeds of the
ships are given in Table 5.
The current courses of the ships are such that all
of the ships would collide in the central point of
the area. The final evolutionary set of the safe co-
operating trajectories, which avoid collisions with
each other, is shown in Figure 9.
Table 5 The motion parameters of all ships
Speed
[knots]
Course
[degrees]
Position
coordinates
at the start
time [n.m.]
Coordinates
of the desti-
nation point
[n.m.]
x
y
x
y
Ship 1
5
0
5
0
5
5
Ship 2
14
45
0
0
10
10
Ship 3
10
90
0
2.5
10
2.5
Ship 4
14
135
0
5
10
0
Ship 5
5
180
5
5
5
0
Ship 6
14
225
10
5
0
0
Ship 7
10
270
10
2.5
0
2.5
Ship 8
14
315
0
10
0
5
Figure 20 The evolutionary set of the eight ships’ cooperating trajectories, which avoid collisions with each other.
6 SCENARIO 4: A GROUP OF SHIPS
MANOEUVRING TO AVOID COLLISIONS
WITH EACH OTHER AND OBSTACLES
The positions, destination points and speeds of the
ships are given in Table 6.
Table 6 The motion parameters of all ships
Speed
[knots]
Course
[degrees]
Position
coordinates
at the start
time [n.m.]
Coordinates
of the desti-
nation point
[n.m.]
x
y
x
y
Ship 3
10
90
0
2.5
10
2.5
Ship 4
14
135
0
5
10
0
Ship 6
14
225
10
5
0
0
Ship 7
10
270
10
3
0
3
The current courses of all four ships collide
with each other or the landmass. The final evolu-
tionary set of four cooperating safe trajectories is
shown in Figure 10.
196
Figure 21 The evolutionary set of the four ships’ cooperating trajectories, which avoid collisions with each other and the landmass
(landmass in black, landmass domain in grey).
7 SUMMARY AND CONCLUSIONS
In the paper some examples of use of evolutionary
approach to solving ship encounter situations have
been proposed. This approach is a generalization of
evolutionary trajectory determining: a set of trajecto-
ries of all ships involved, instead of just the own tra-
jectory, is determined. The method avoids violating
the target ship domains and the given stationary con-
straints, while minimizing way loss and obeying the
COLREGS. As has been shown in case of simple
scenarios (where ship priorities are clearly described
by COLREGS), the method is able to predict the
probable manoeuvre of a target and plan own ship
manoeuvre in advance. Because of its low computa-
tional time the method can be applied to both on-
board collision-avoidance systems and VTS sys-
tems. In the former it could be used for solving sim-
ple scenarios and assessment of more complex ones,
in the latter it could successfully solve any given
scenario involving multiple ships and stationary
constraints.
REFERENCES
Cockcroft A.N., Lameijer J.N.F 1993: A Guide to Collision
Avoidance Rules, Butterworth-Heinemann Ltd.
Coldwell T.G. 1982. Marine Traffic Behaviour in restricted
Waters, The Journal of Navigation vol. 36: pp. 431-444.
Lisowski J.2005 Dynamic games methods in navigator deci-
sion support system for safety navigation, Proceedings of
the European Safety and Reliability Conference vol. 2, pp
1285 – 1292.
Szlapczynski R (in press). Evolutionary approach to solving
multi-ship encounter situations, Polish Journal of Environ-
mental Studies.
Śmierzchalski R. 1998 Synteza metod i algorytmów wspoma-
gania decyzji nawigatora w sytuacji kolizyjnej na morzu.
Prace Naukowe Wyższej Szkoły Morskiej w Gdyni.