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).