International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 6
Number 3
September 2012
345
1 INTRODUCTION
A desired solution to a multi-ship encounter situa-
tion would include a set of planned, optimal trajecto-
ries for all the ships involved in an encounter, such
that no collision or domain violations occur when
these ships follow the trajectories. When solving this
situation the key difficulty is that even a single
course change performed by one ship involved in the
encounter may force one or even more the other
ships to manoeuvre. Thus the optimisation method
utilized to find a solution to the problem should be
flexible enough to efficiently look through the vast
search space and handle even minor changes in the
ship’s behaviour e.g. in its motion parameters.
There is a number of approaches to solving a
multi-ship encounter situation. Two basic trends are
either utilization of differential games (Lisowski
2005) or searching for a single trajectory (for the
own ship) by evolutionary algorithms (Smierzchal-
ski et al. 2000). The former method assumes that the
process of steering a ship in multi-ship encounter
situations can be modeled as a differential game
played by all ships involved, each having their strat-
egies. Unfortunately, high computational complexity
is its serious drawback. The latter approach is the
evolutionary method focused on finding only a sin-
gle trajectory of the own ship. In short, the evolu-
tionary method uses genetic algorithms, which, for a
given set of pre-determined input trajectories find a
solution that is optimal according to a given fitness
function. However, the method’s limitation is that it
assumes targets motion parameters not to change
and if they do change, the own trajectory has to be
recomputed. This limitation becomes a serious one
on restricted waters. If a target’s current course col-
lides with a landmass or another target of a higher
priority, there is no reason to assume that the target
would keep such a disastrous course until the crash
occurs. Consequently, planning the own trajectory
for the unchanged course of a target will be futile in
the majority of such cases. Also, the evolutionary
method does not offer a full support to VTS opera-
tors, who might face the task of synchronizing tra-
jectories of multiple ships with many of these ships
manoeuvring.
Therefore, the authors have proposed a new ap-
proach, which combines some of the advantages of
both methods: the low computational time, support-
ing all domain models and handling stationary ob-
Evolutionary Sets of Safe Ship Trajectories:
Evaluation of Individuals
R. Szlapczynski
Gdansk University of Technology, Gdansk, Poland
J. Szlapczynska
Gdynia Maritime University, Gdynia, Poland
ABSTRACT: The paper presents a description of the evaluation phase of the Evolutionary Sets of Safe Ship
Trajectories method. In general, the Evolutionary Sets of Safe Ship Trajectories method combines some of the
assumptions of game theory with evolutionary programming and finds an optimal set of cooperating trajecto-
ries of all ships involved in an encounter situation. While developing a new version of this method, the au-
thors decided to use real maps instead of a simplified polygon modelling and also to focus on better handling
of COLREGS. The upgrade to the method enforced re-designing the evaluation phase of the evolutionary
process. The new evaluation is thoroughly described and it is shown how evaluation affects final solutions re-
turned by the method.
346
stacles (all typical for evolutionary method), with
taking into account the changes of motion parame-
ters (changing strategies of the players involved in a
game). Instead of finding the optimal own trajectory
(from the own ship’s perspective) for the unchanged
courses and speeds of targets, an optimal set of safe
trajectories of all ships involved is searched for
(from the coast, e.g. VTS, perspective). The method
is called evolutionary sets of safe trajectories and its
early version has been presented by one of the au-
thors in (Szlapczynski 2010).
The newly developed version of the method uses
real maps instead of simplified polygon modelling
and focuses on COLREGS compliance. The upgrade
to the method enforced changes in all phases of the
evolutionary process including evaluation. The pa-
per presents a description and a discussion of the
new evaluation phase.
The rest of the paper is organized as follows. In
the next section a brief description of the problem is
given, including basic constraints of the optimization
problem as well as the additional constraints - the
COLREGS rules, which are taken into account. Sec-
tion 3 covers the issue of detecting various con-
straints violations. This is followed by a Section 4,
where it is shown, how, on the basis of previous sec-
tions, the fitness function is formulated. In section 5
different evaluation approaches and the consequenc-
es of applying them are compared by means of simu-
lation experiments. Finally the summary and conclu-
sions are given in Section 6.
2 SOLVING MULTI-SHIP ENCOUNTER
SITUATIONS AS AN OPTIMIZATION
PROBLEM
It is assumed that we are given the following data:
stationary constraints (such as landmasses and
other obstacles),
positions, courses and speeds of all ships in-
volved,
ship domains,
times necessary for accepting and executing the
proposed manoeuvres.
Ship positions and ship motion parameters are
provided by ARPA (Automatic Radar Plotting Aid),
or, if there is no reliable identification assured, AIS
(Automatic Identification System) systems. A ship
domain can be determined based on the ship’s
length, its motion parameters and the type of water
region. Since the shape of a domain is dependent on
the type of water region, the authors have assumed
and used a ship domain model by Davis (Davis et al.
1982), which updated Goodwin model (Goodwin
1975), for open waters and to use a ship domain
model by Coldwell (Coldwell 1982), which updated
Fuji model (Fuji et al. 1971), for restricted waters.
As for the last parameter the necessary time, it
is computed on the basis of navigational decision
time and the ship’s manoeuvring abilities. By default
an assumed 6-minute value is used here.
Knowing all the abovementioned parameters, the
goal is to find a set of trajectories, which minimizes
the average way loss spent on manoeuvring, while
fulfilling the following conditions:
none of the stationary constraints are violated,
none of the ship domains are violated,
the minimal acceptable course alteration is not
lesser than 15 degrees (assumed to eliminate slow
and insignificant turns),
the maximal acceptable course alteration is not to
be larger than assumed 60 degrees,
speed alteration are not to be applied unless nec-
essary (collision cannot be avoided by course al-
teration up to 60 degrees),
a ship manoeuvres, if and only if she is obliged
to,
it is assumed that manoeuvres to starboard are fa-
voured over manoeuvres to port board.
The first two conditions are obvious: all obstacles
have to be avoided and the ship domain is an area
that should not be violated by definition. All the oth-
er conditions are either imposed by COLREGS
(IMO 1977) and good marine practice or by the eco-
nomics. In particular, the course alterations lesser
than 15 degrees might be misleading for the ARPA
systems (and therefore may lead to collisions) and
the course alterations larger than 60 degrees are not
recommended due to efficiency reasons. Also, ships
should only manoeuvre when necessary, since each
manoeuvre of a ship makes it harder to track its mo-
tion parameters for the other ships ARPA systems
(Wawruch 2002). Apart from these main constraints,
additional constraints selected COLREGS rules
have to be directly handled.
The COLREGS rules, which are of interest here
are:
Rule 13 overtaking: an overtaking vessel must
keep well clear of the vessel being overtaken.
Rule 14 - head-on situations: when two power-
driven vessels are meeting head-on both must al-
ter course to starboard so that they pass on the
port side of the other.
Rule 15 - crossing situations: when two power-
driven vessels are crossing, the vessel, which has
the other on the starboard side must give way.
Rule 16 - the give-way vessel: the give-way ves-
sel must take early and substantial action to keep
well clear.
Rule 17 - the stand-on vessel: the stand-on vessel
may take action to avoid collision if it becomes
347
clear that the give-way vessel is not taking appro-
priate action.
There are also some additional COLREGS-related
assumptions, namely:
there are always good visibility conditions,
all considered ships are equally privileged,
all considered ships have motor engine (no sailing
ships taken into account),
no narrow passages are taken into account
no port board manoeuvres are assumed when
overtaking,
no manoeuvres to bypass navigational signs are
taken into account.
In the following sections it will be analysed how
these constraints violations can be detected, in what
order should they be taken into account and how se-
verely should they be penalized during the evalua-
tion phase by the fitness function of the evolutionary
method.
3 DETECTING CONSTRAINTS VIOLATIONS
Below it is described how the constraints violations
can be detected and, in case of various possible ap-
proaches, which one has been chosen by the authors
and why.
3.1 Detecting static constraints violations
(collisions with landmasses and safety isobate)
In the first version of the method (Szlapczynski
2009) simplified polygon modelling of the static
constraints have been applied, instead of using real
maps. Therefore it was natural to find collisions by
detecting all crossings of the ships’ trajectories with
polygons’ edges. This is shown in Figure 1. A num-
ber of operations that the algorithm has to perform to
find collisions in such situation is proportional to the
number of the edges of all polygons in a given area.
Figure 1. A ship’s trajectory crossing a landmass modeled as a
polygon. The geometrical crossings of the trajectory and poly-
gon edges are marked in black
However, the current version of the method uses
a vector map of a given area. While vector maps also
uses polygons defined by coordinates of their verti-
ces, the number of vertices and thus the edges rises
drastically, when compared to the simplification
used before. Even after limiting the map to a certain
area, the numbers of the edges that have to be
checked for possible crossings are still much larger.
This is shown in Figure 2.
Figure 2. A ship’s trajectory crossing a landmass on a bitmap
Therefore the authors have decided not to process
vector map directly for crossing detection, but to use
it for generating bitmap of an area. Although it is a
time-taking operation, fortunately, it is enough to
generate such bitmaps offline and only once for each
area. Then, when the method is running in real time,
instead of checking the edges for geometrical cross-
ings, each bitmap cell, which the trajectory of a ship
traverses, is read and checked if it belongs to land-
mass, water or safety isobate. For a bitmap, whose
detail level reflects this of a given vector map, the
computational time would be much shorter: propor-
tional to the number of traversed cells, instead of a
number of all vertices. This approach is also more
flexible in terms of future implementation of ba-
thymetry: if every cell contained information on the
water depth, it would be easy to check, whether a
cell is passable or not for a particular ship.
348
3.2 Detecting collisions with other ships
Figure 3. Algorithm for ship-to-ship collision detection
The algorithm for detecting ship-to-ship collisions
(Figure 3) is as follows. Each ship’s trajectory is
checked against all other ships. For each pair of
ships, the start time and end time of each trajectory’s
segments are computed. If two segments of the two
trajectories overlap in time, they are checked for ge-
ometrical crossing. In case of a crossing, the ap-
proach factor value is computed. Then, if the ap-
proach factor value indicates collision, the type of an
encounter (head-on, crossing or overtaking) is de-
termined on the basis of the ships’ courses and it is
decided, which ship is to give way (both ships in
case of head-on). The collision is only registered for
the give way ship and the information on the colli-
sion are stored in the trajectory data structure.
3.3 Detecting COLREGS violations
Detecting COLREGS violations is much more diffi-
cult than violations described in the previous two
sub-sections. In general, there may be three types of
COLREGS violations:
a ship does not give way, when it should,
a ship gives way, when it should not, because it is
a stand-on ship,
a ship manoeuvres to port-board when it should
manoeuvre to starboard.
Each of these three situations may happen on ei-
ther open or restricted waters, which gives us a total
of six cases to handle. The difficulty with deciding,
whether a ship has acted lawfully, or not, lies in the
nature of evolutionary algorithms as well as in the
nature of the problem itself: COLREGS specify only
the procedures for ship-to-ship encounters. Looking
at a set of ship trajectories for a multi-target encoun-
ter it is sometimes impossible to tell, what was the
reason for a particular manoeuvre: which ship was
given way intentionally, and which one benefited
from it only as a side effect. A partial solution to this
problem is storing in the trajectory data the infor-
mation on the reasons of the manoeuvres. The possi-
ble reasons might be:
landmass avoidance or other static constraint vio-
lation avoidance,
giving way to a privileged ship,
any other, e.g. due to the ship’s passage plan.
However, the course alterations that each trajecto-
ry contains may be made intentionally as a result
of applying a collision avoidance operator or unin-
tentionally as a result of crossing or mutation. A
manoeuvre which resulted accidentally from cross-
ing or mutation may be just as good as the one being
the effect of a specialised operator’s more ‘con-
scious’ work. Therefore the ‘any other’ manoeuvre’s
reason cannot always be registered as COLREGS
violation. All this considered, the authors have de-
cided to limit the used types on the manoeuvre’s rea-
sons to: obstacle avoidance and any other. The final
COLREGS violations detection rules are:
1 On open waters:
a) if a ship is not obliged to give way to any oth-
er ship, any manoeuvre (other than the ma-
noeuvres given by the passage plan) it per-
forms is registered as COLREGS violation,
b) if a ship is obliged to give way, and does not
perform a manoeuvre it is registered as
COLREGS violation,
c) all manoeuvres to port board are registered as
COLREGS violations.
The c) point may raise some doubts, but it must
be emphasized that COLREGS violations regis-
tration is done for the sake of future penalizing of
349
violations, when the final fitness function values
is being computed. Therefore, the only effect of
penalizing the manoeuvres to port board will be
additional favouring of manoeuvres to starboard,
which are already favoured by domain models. In
no way does penalizing make it impossible to
choose a manoeuvre to port board. It is only less
profitable for most cases.
2 On restricted waters: here, as explained before
every trajectory node, which is a part of a ma-
noeuvre, contains special information on the rea-
son why this particular node has been inserted or
shifted: land or other stationary obstacle avoid-
ance, target avoidance or accidental manoeuvre
generated by evolutionary mechanisms. Based on
this, COLREGS violations are registered as fol-
lows:
a) if a ship does not initially have to give way to
any target and its first manoeuvre has reason
other than static constraint violation avoid-
ance, it is registered as COLREGS violation,
b) any manoeuvre to port board of reason other
than static constraint violation avoidance is
registered as COLREGS violation.
Point b) means that occasionally the correct ma-
noeuvres introduced by crossing or mutation and
avoiding static constraint violation will be penal-
ized unjustly. However, it is not a problem, as
long as penalties for static constraint violations
will be larger and trajectories avoiding them will
still be selected for next generations. After all, we
are interested in the final sets of trajectories
themselves much more than in their slightly im-
precise fitness function values.
4 FORMULATING FITNESS FUNCTION
In the evolutionary method all individuals (sets of
trajectories) are evaluated by the specially designed
fitness function, which should reflect optimisation
criteria and constraints (Michalewicz et al. 2004). In
this section it is shown, how, on the basis of previ-
ous sections, this fitness function is formulated.
4.1 Basic criterion – minimizing way loss
The basic criterion is the economic one minimiz-
ing way losses of trajectories in a set. For each of the
trajectories, a trajectory_economy_factor is comput-
ed according to the formula (1).
,
_
__
__
=
i
ii
i
lengthtrajectory
losswaylengthtrajectory
factoreconomytrajectory
(1)
where:
i – the index of the current ship [/],
trajectory_length
i
the total length of the i-th
ship’s trajectory [nautical miles],
way_loss
i
the total way loss of the i-th ship’s
trajectory [nautical miles] computed as a difference
between the trajectory length and length of a seg-
ment joining trajectory’s start point and endpoint.
As can be seen, the trajectory_economy_factor is
always a number from a (0,1] range.
4.2 Penalizing static constraint violation
After the trajectory economy factor has been com-
puted the static constraints are handled by introduc-
ing penalties for violating them. For each trajectory
its static constraint factor scf
i
is computed. The static
constraints are always valid and their violations must
be avoided at all cost, therefore penalties applied
here are the most severe hence the square in the
formula (2).
,
_
___
2
=
i
ii
i
lengthtrajectory
lengthcrosstrajectorylengthtrajectory
scf
(2)
where:
trajectory_cross_length
i
the total length of the
parts of the i-th ship’s trajectory, which violate sta-
tionary constraints [nautical miles].
The static constraint factor is a number from a
[0,1] range, where “1” value means no static con-
straint violation (no landmasses or other obstacles
are crossed) and “0” value is for trajectories crossing
landmasses on their whole length.
4.3 Penalizing collisions with other ships
Analogically to the static constraint factor, collision
avoidance factor caf
i
is computed to reflect the
ship’s collisions with all other privileged ships as
shown by (3).
(3)
where:
n – the number of ships [/],
j – the index of a target ship [/],
fmin
i,j
the approach factor value for an encounter
of ships i and j, if i-th ship is the privileged one, the
potential collision is ignored and the approach factor
value is equal to 1 by definition. [/].
The collision avoidance factor is a number from a
[0,1] range, where “1” value means no ship domain
violation and “0” means a crash with at least one of
the targets.
350
4.4 Penalizing COLREGS violations
The COLREGS violations are secondary to static
constraint violations and to collisions with other
ships and therefore the authors have decided to pe-
nalize it moderately, to make sure that constraints
from the previous two points are met first.
COLREGS compliance factor ccf
i
is computed ac-
cording to the following formula (4).
[ ]
,__1
1
=
=
m
k
ki
penaltyviolationCOLREGS
ccf
(4)
where:
m the number of COLREGS violation registered
for the current ship as has described in sec-
tion 3.3 [/],
kthe index of a registered violation [/],
COLREGS_violation_penalty
k
the penalty for the
k-th of the registered COLREGS violation [/].
The penalty values for all registered COLREGS
violations described in section 3.3 by points 1. a) - c)
and 2. a) - b) are configurable in the method and are
set to 0.05 by default.
4.5 Fitness function value
Once all aforementioned factors have been comput-
ed, the fitness function value is calculated. The au-
thors wanted the fitness function to be normalized,
which is convenient for further evolutionary opera-
tions, mostly for selection purposes. When fitness
function values are normalized, we do not need any
additional operations on them and they can directly
be used for random proportional and modified ran-
dom proportional selection in the reproduction and
succession phases of the evolutionary algorithm. We
can also easily measure and see progress we make
with each generation. However, normalized fitness
function is harder to obtain, because we have to
make sure that we keep the high resolution of evalu-
ating the individuals, namely that we differ between
various levels of penalties: stationary constraints, be-
ing more important than collision avoidance and col-
lision avoidance being more important than
COLREGS compliance.
Here, we succeeded in formulating a normalized
fitness function, while keeping relatively high reso-
lution of evaluation: minor stationary constraints vi-
olations are penalized similarly as major collisions
with other ships and minor collisions with other
ships are penalized similarly as multiple COLREGS
violations. The final fitness function is as follows:
,
_
1
=
=
n
i
i
n
fitnesstrajectory
fitness
(5)
where:
,***__
_
iiii
i
ccfcafscffactoreconomytrajectory
fitnesstrajectory
=
=
(6)
The final fitness function value assigned to an in-
dividual is an arithmetical average of fitness func-
tion values computed for all trajectories. It is dis-
cussable, whether all trajectories should have the
same impact on final fitness function value (as it is
done here), or should the trajectory fitness function
values be taken with weights proportional to the tra-
jectory lengths. When combined with the formula
for trajectory economy factor, the current approach
means that we are trying to minimize average rela-
tive way loss computed over all trajectories, instead
of total absolute way loss (with weights being used).
However, experiments have shown, that minimizing
total absolute way loss leads to discrimination of
ships, whose basic trajectories are shorter and to
their large relative way losses (section 5.2).
5 COMPARING DIFFERENT EVALUATION
APPROACHES
In the following subsections different evaluation ap-
proaches and the consequences of applying them are
compared.
5.1 Penalizing COLREGS violations: how it affects
solutions returned by the method
Even when a domain model, which favours
COLREGS is applied, it is possible to find an en-
counter situation, where additional COLREGS vio-
lations penalties must be used, as has been described
in section 4.4 or otherwise the method will return in-
correct solution. A simple example is a head-on en-
counter of two ships, whose parameters are shown in
Figure 4. In this scenario, following the Rule 14 of
COLREGS for head-on situations, it is required that:
“(…) both (vessels) must alter course to starboard so
that they pass on the port side of the other
.
Figure 4. Parameters of two ships in a head-on encounter
Because the method tends to propose manoeuvres
no lesser than 15 degrees, a manoeuvre from one
ship only would be enough to avoid collision. From
the way loss minimization point of view, the extra
manoeuvre from the second ship is redundant. Con-
sequently, individuals containing trajectories with
manoeuvres from both ships would be ranked lower