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