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

( )

∏

≠=

=

n

ijj

jii

fmincaf

,1

,

)1,min(

(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 [/],

k – the 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