International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 3
Number 2
June 2009
163
1 MATHEMATICAL MODELS OF SAFE SHIP
CONTROL PROCESS
1.1 Base model
As the process of steering the ship in collision situa-
tions, when a greater number of objects is encoun-
tered, often occurs under the conditions of indefi-
niteness and conflict, accompanied by an inaccurate
co-operation of the objects within the context of
COLREG Regulations then the most adequate model
of the process which has been adopted is a model of
a dynamic game, in general of j tracked ships as ob-
jects of steering (Cahill 2002, Lisowski 2004b,
2005d, 2007b, Sandom 2004).
The diversity of selection of possible models directly
affects the synthesis of the ship’s handling algo-
rithms which are afterwards effected by the ship’s
handling device directly linked to the ARPA system
and determines the effects of the safe and optimal
control. The properties of the process are described
by the state equation (Isaacs 1965):
]t),u,u(),x,x[(fx
j
0
j
0
v
j
v
0j0ii
ϑ
ϑ
=
j=1,…, m (1)
where
( )
tx
0
0
ϑ
-
0
ϑ
dimensional vector of the process
state of the own ship determined in a time span
]t,t[t
k0
∈
;
( )
tx
j
j
ϑ
-
j
ϑ
dimensional vector of the
process state for the j-th met ship;
( )
tu
0
o
ν
- ν
0
dimen-
sional control vector of the own ship;
)t(u
j
j
ν
- ν
j
di-
mensional control vector of the j-th met ship.
The constraints of the control and the state of the
process are connected with the basic condition for
the safe passing of the ships at a safe distance D
s
in
compliance with COLREG Rules, generally in the
following form (Engwerda 2005):
0)u,x(g
jj
jjj
≤
νϑ
(2)
Goal function has form of the payments – the in-
tegral payment and the final one:
min)t(d)t(rdt)]t(x[I
k
t
t
kj
2
0
j
0
k
0
0
→++=
∫
ϑ
(3)
The integral payment represents loss of way by
the own ship while passing the encountered ships
and the final payment determines the final risk of
collision r
j
(t
k
) relative to the j-th ship and the final
deflection of the own ship d(t
k
) from the reference
trajectory (Lisowski 2000a, 2002, 2005a,c, 2008b,
Nisan 2007, Nowak 2005, Osborna 2004).
1.2 Approximate models
Having regard to a high complexity of the base
model in the form of a model of a dynamic game for
the practical synthesis of safe steering algorithms
various simplified models are formulated, such as
for example:
− multi-stage positional game
− non-cooperative game
− cooperative game
− multi-step matrix game
− dynamic model with neural constraints
The Comparison of Safe Control Methods in
Marine Navigation in Congested Waters
J. Lisowski
Gdynia Maritime University, Gdynia, Poland
ABSTRACT: The paper introduces comparison of five methods of safe ship control in collision situation:
multi-stage positional non-cooperative and cooperative game, multi-step matrix game, dynamic and kinemat-
ics optimisation with neural constrains of state control process. The synthesis of computer navigator decision
supporting algorithms with using dual linear programming and dynamic programming methods has been pre-
sented. The considerations have been illustrated an examples of a computer simulation the algorithms to de-
termine the safe own ship's trajectory in situation of passing a many of the ships encountered at sea.
164
− kinematic model
− classical model
− fuzzy model
− static model
− speed triangle model.
The degree of simplification is dependent on a con-
trol method applied (Lavalle 2006, Lisowski 2005b,
2006b, 2007a,c, 2008d, Straffin 2001).
2 ALGORITHMS OF SAFE SHIP CONTROL
Each particular approximated model of process may
be assigned respective methods of safe control of
ship (Table 1).
Table 1. Algorithms of determining ship strategies.
___________________________________________________
Process Control Computer Type
models methods supporting of decision
algorithms
___________________________________________________
Multi-stage Dual linear NPG Positional
positional programming CPG game trajectory
game
Mult-step Dual linear MG Risk game
matrix programming trajectory
game
Dynamic Dynamic DO Dynamic
programming, optimal
Artificial trajectory
neural network
Kinematic Linear KO Kinematic
programming optimal
Fuzzy trajectory
Control
Static Linear OM Optimal
programming manoeuvre
Fuzzy
control
___________________________________________________
In practice, methods of selecting a manoeuvre as-
sume a form of appropriate steering algorithms sup-
porting navigator decision in a collision situation.
Algorithms are programmed into the memory of a
Programmable Logic Controller PLC.
This generates an option within the ARPA anti-
collision system or a training simulator (Fig. 1).
Figure 1. The system structure of computer support of naviga-
tor decision in collision situation.
2.1 Algorithm of non-cooperative positional game
NPG
The optimal steering of the own ship
)t(u
0
∗
, equiva-
lent for the current position p(t) to the optimal posi-
tional steering
)p(u
0
∗
, is determined:
− for the measured position p(t
k
) of the steering sta-
tus at the moment t
k
sets of the acceptable strate-
gies
( )
[ ]
k
0
j
tpU
are determined for the encoun-
tered objects in relation to the own ship, and the
output sets
( )
[ ]
k
jw
0
tpU
of the acceptable strategies
of the own ship in relation to each one of the en-
countered objects,
− a pair of vectors
m
j
u
and
j
0
u
, is determined in re-
lation to each j-th object and then the optimal po-
sitional strategy of the own ship
)p(u
0
∗
from the
condition:
[ ]
=
=
∗
∈
∈
=∈
∗
=
)L,x(SL),t(xSI
k00kk00
)u(Uu
Uu
UUu
min
max
min
j
j
0
j
0
j
m
j
m
1j
j
0
00
(4)
[ ]
∫
=
Lk
0
t
t
0k00
dt)t(uL),t(xS
(5)
where S
0
refers to the continuous function of the
manoeuvring goal of the own ship, characterising
the distance of the ship at the initial moment t
0
to the
nearest turning point L
k
on the reference p
r
(t
k
) route
of the voyage.
The optimal steering of the own ship is calculated
at each discrete stage of the ship’s movement by ap-
plying the SIMPLEX method to solve the problem
of the linear programming, assuming the relationship
(4) as the goal function and the control constraints
(2).
Using the function of lp – linear programming
from the Optimisation Toolbox Matlab, the position-
al multi-stage game non-cooperative manoeuvring
NPG program has been designed for the determina-
tion of the own ship safe trajectory in a collision sit-
uation (Lebkowski 2001, Lisowski 2001a, 2008b,
Segal 1998).
2.2 Algorithm of cooperative positional game CPG
Goal function (4) for cooperative game has the form:
[ ]
=
=
∗
∈∈
=∈
∗
=
)L,x(SL),t(xS
mi nmi nmi n
I
k00kk00
)u(UuUu
UUu
j
j
0
j
0
j
m
j
m
1j
j
0
00
(6)
2.3 Algorithm of matrix game MG
The dynamic game is reduced to a multi-step matrix
game of a j number of participants (Lisowski 2001b,
165
2004a, 2006a, Radzik 2000). The matrix game R
)],(r[
0jj
νν
=
includes the values determined previ-
ously on the basis of data taken from an anti-
collision system ARPA the value a collision risk r
j
with regard to the determined strategies ν
0
of the
own ship and those ν
j
of the j-th encountered objects.
The matrix risk contains the same number of col-
umns as the number of participant I (own ship) strat-
egies and the number of lines which correspond to a
joint number of participant II (j objects) strategies
(Fig. 2).
Figure 2. Navigational situation representing the passing of the
own ship with the j-th object.
The value of the risk of the collision r
j
is defined
as the reference of the current situation of the ap-
proach described by the parameters
j
min
D
and
j
min
T
,
to the assumed assessment of the situation defined as
safe and determined by the safe distance of approach
D
s
and the safe time T
s
– which are necessary to exe-
cute a manoeuvre avoiding a collision with consid-
eration actual distance D
j
between own ship and en-
countered j-th ship:
2
1
2
s
j
2
s
j
min
2
2
s
j
min
1j
D
D
T
T
w
D
D
wr
−
+
+
=
(7)
where the weight coefficients (w
1
, w
2
) are depended
on the state visibility at sea, dynamic length and dy-
namic beam of the ship, kind of water region.
The constraints affecting the choice of strategies
(ν
0
, ν
j
) are a result of COLREG recommendations.
Player I may use
ν
0
of various pure strategies in a
matrix game and player II has
ν
j
of various pure
strategies.
As the game, most frequently, does not have sad-
dle point the state of balance is not guaranteed –
there is a lack of pure strategies for both players in
the game. The problem of determining an optimal
strategy may be reduced to the task of solving dual
linear programming problem. Mixed strategy com-
ponents express the distribution of probability
),(p
0jj
νν
of using pure strategies by the players.
As a result of using the following form for the steer-
ing criterion:
( )
j
j
0
rmaxminI
j0
νν
=
∗
(8)
the probability matrix P
=
[p
j
(ν
j
, ν
0
)] of using particu-
lar pure strategies may be obtained.
The solution for the steering goal is the strategy
of the highest probability:
( )
{ }
max0jjo0
)],(p[uu
00
νν
νν
=
∗
(9)
Using the function of lp – linear programming
from the Optimisation Toolbox Matlab, the matrix
multi-step game manoeuvring MG program has been
designed for the determination of the own ship safe
trajectory in a collision situation (Cichuta 2000).
2.4 Algorithm of dynamic optimisation DO
The description of the own ship dynamic allows for
the following representation of the state equations in
a discrete form:
7,...,2,1i)u,u,x(xxx
21ik,ik,i1k,i
=+=
+
∆
(10)
where x
1
=X
0
, x
2
=Y
0
, x
3
=
ψ
, x
4 =
max
ψ
,
x
5
=V, x
6
=
V
,
x
7
=t, u
1
=
maxr
/
αα
, u
2
=n
r /
n
max
The basic criterion for the ship's control is to en-
sure safe passing of the objects, which is considered
in the state constraints:
0)t,Y,X(g
jjj
≤
(11)
This dependence is determined by the area ship's
domain of the collision hazard and which assumes
the form of a circle, parable, ellipse or hexagon (Ba-
ba 2001, Lisowski 2000b).
The ships domains may have a permanent or var-
iable shapes generated, for example, by Neural Net-
work Toolbox Matlab. Moreover, a criterion of op-
timisation is taken into consideration in the form of
smallest possible way loss for safe passing of the ob-
jects, which, at a constant speed of the own ship,
leads to the time-optimal control:
166
mindtxdtx)u,u(I
kk
t
0
5
t
0
521
→
∫
≅
∫
=
(12)
Determination of the optimal control of the ship
in terms of an adopted control quality index may be
performed by applying Bellman's principle of opti-
misation. The optimal time for the ship to go
through k stages is as follows:
+=
++
∗
−
∗
−−
])x,x,x,x,x(tt[mint
k,51k,21k,1k,2k,1k1k
u,u
k
2k,22k,1
∆
(13)
The optimal time for the ship to go through the k
stages is a function of the system state at the end of
the k-1 stage and control
)u,u(
2k,22k,1 −−
at the k-2
stage (Levine 1996).
By going from the first stage to the last one the
formula (13) determines the Bellman's functional
equation for the process of the ship's control by the
alteration of the rudder angle and the rotational
speed of the screw propeller (Nise 2008).
The constraints for the state variables and the
control values generate the NEUROCONSTR proce-
dure in the dynamic optimal control DO program for
the determination of the own ship safe trajectory in a
collision situation (Skogestad 2005).
2.5 Algorithm of kinematics optimisation KO
Goal function (4) for kinematics optimisation has the
form:
[ ]
{ }
==
∗
=∈
∗
=
)L,x(SL),t(xSI
k00kk00
UUu
mi n
m
1j
j
0
00
(14)
3 COMPUTER SIMULATION
Computer simulation of NPG, CPG, MG, DO and
KO algorithms was carried out in Matlab/Simulink
software on an examples of a real navigational situa-
tions at sea of passing j encountered objects (Pachci-
arek 2007, Lisowski 2008c).
3.1 Situation for j=4 encountered ships
Figure 3. The 6 minute speed vectors of own and 4 encountered
ships in situation in Kattegat Strait
Figure 4. The safe trajectory of own ship for NPG algorithm in
good visibility D
s
=1 nm in situation of passing j=4 encoun-
tered ships, r(t
k
)=0, d(t
k
)=2.99 nm.
Figure 5. The safe trajectory of own ship for CPG algorithm in
good visibility D
s
=1 nm in situation of passing j=4 encoun-
tered ships, r(t
k
)=0, d(t
k
)=1.10 nm.
167
Figure 6. The safe trajectory of own ship for MG algorithm in
good visibility D
s
=1 nm in situation of passing j=4 encoun-
tered ships, r(t
k
)=0, d(t
k
)=0.83 nm.
Figure 7. The safe trajectory of own ship for DO algorithm in
good visibility D
s
=1 nm in situation of passing j=4 encoun-
tered ships,
h16.1t
K
=
∗
.
Figure 8. The safe trajectory of own ship for KO algorithm in
good visibility D
s
=1 nm in situation of passing j=4 encoun-
tered ships, r(t
k
)=0, d(t
k
)=0.38 nm.
Figure 9. The comparison of own ship safe trajectories in good
visibility D
s
=1 nm in situation of passing j=4 encountered
ships.
3.2 Situation for j=8 encountered ships
Figure 10. The 6 minute speed vectors of own and 8 encoun-
tered ships in situation in Kattegat Strait.
Figure 11. The safe trajectory of own ship for NPG algorithm
in good visibility D
s
=1 nm in situation of passing j=8 encoun-
tered ships, r(t
k
)=0, d(t
k
)=2.10 nm.
168
Figure 12. The safe trajectory of own ship for CPG algorithm
in good visibility D
s
=1 nm in situation of passing j=8 encoun-
tered ships, r(t
k
)=0, d(t
k
)=0.68 nm.
Figure 13. The safe trajectory of own ship for MG algorithm in
good visibility D
s
=1 nm in situation of passing j=8 encoun-
tered ships, r(t
k
)=0, d(t
k
)=2.74 nm.
Figure 14. The safe trajectory of own ship for DO algorithm in
good visibility D
s
=1 nm in situation of passing j=8 encoun-
tered ships,
h93.0t
K
=
∗
.
Figure 15. The safe trajectory of own ship for KO algorithm in
good visibility D
s
=1 nm in situation of passing j=8 encoun-
tered ships, r(t
k
)=0, d(t
k
)=0.26 nm.
Figure 16. The comparison of own ship safe trajectories in
good visibility D
s
=1 nm in situation of passing j=8 encoun-
tered ships.
3.3 Situation for j=19 encountered ships
Figure 17. The 6 minute speed vectors of own and 19 encoun-
tered ships in situation on the North Sea.
169
Figure 18. The safe trajectory of own ship for NPG algorithm
in good visibility D
s
=1 nm in situation of passing j=19 encoun-
tered ships, r(t
k
)=0, d(t
k
)=2.92 nm.
Figure 19. The safe trajectory of own ship for CPG algorithm
in good visibility D
s
=1 nm in situation of passing j=19 encoun-
tered ships, r(t
k
)=0, d(t
k
)=1.95 nm.
Figure 20. The safe trajectory of own ship for MG algorithm in
good visibility D
s
=1 nm in situation of passing j=19 encoun-
tered ships, r(t
k
)=0, d(t
k
)=3.81 nm.
Figure 21. The safe trajectory of own ship for DO algorithm in
good visibility D
s
=1 nm in situation of passing j=19 encoun-
tered ships,
h10.1t
K
=
∗
.
Figure 22. The safe trajectory of own ship for KO algorithm in
good visibility D
s
=1 nm in situation of passing j=19 encoun-
tered ships, r(t
k
)=0, d(t
k
)=0.84 nm.
Figure 23. The comparison of own ship safe trajectories in
good visibility D
s
=1 nm in situation of passing j=19 encoun-
tered ships.
170
3.4 Situation for j=47 encountered ships
Figure 24. The 6 minute speed vectors of own and 47 encoun-
tered ships in situation in the English Channel.
Figure 25. The safe trajectory of own ship for NPG algorithm
in good visibility D
s
=1 nm in situation of passing j=47 encoun-
tered ships, r(t
k
)=0, d(t
k
)=0.11 nm.
Figure 26. The safe trajectory of own ship for CPG algorithm
in good visibility D
s
=1 nm in situation of passing j=47 encoun-
tered ships, r(t
k
)=0, d(t
k
)=1.17 nm.
Figure 27. The safe trajectory of own ship for MG algorithm in
good visibility D
s
=1 nm in situation of passing j=47 encoun-
tered ships, r