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

100

Population size

100

Selection method

Truncation selection with the

truncation threshold of 50%

Mutation probability

(for a single trajectory)

Depends on the trajectory fitness

value (from 0% for perfect trajec-

tories to 100% for unacceptable

ones)

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