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):
(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(t
k
)=0, d(t
k
)=3.83 nm.
Figure 28. The safe trajectory of own ship for DO algorithm in
good visibility D
s
=1 nm in situation of passing j=47 encoun-
tered ships,
h03.3t
K
=
∗
.
Figure 29. The safe trajectory of own ship for KO 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.
171
Figure 30. The comparison of own ship safe trajectories in
good visibility D
s
=1 nm in situation of passing j=47 encoun-
tered ships.
4 CONCLUSION
In order to ensure safe navigation the ships are
obliged to observe legal requirements contained in
the COLREG Rules. However, these Rules refer ex-
clusively to two ships under good visibility condi-
tions, in case of restricted visibility the Rules pro-
vide only recommendations of general nature and
they are unable to consider all necessary conditions
of the real process.
Therefore the real process of the ships passing
exercises occurs under the conditions of indefinite-
ness and conflict accompanied by an imprecise co-
operation among the ships in the light of the legal
regulations.
A necessity to consider simultaneously the strate-
gies of the encountered ships and the dynamic prop-
erties of the ships as control objects is a good reason
for the application of the differential game model -
often called the dynamic game.
The control methods considered in this paper are,
in a certain sense, formal models for the thinking
processes of a navigating officer steering of own
ships. Therefore they may be applied in the con-
struction of both appropriate training simulators at
the maritime training centre and also for various op-
tions of the basic module of the ARPA anti-collision
system.
The application of approximate models of the dy-
namic game to synthesis of optimal control allows
the determination of safe trajectory in situations of
passing a greater number of met objects as sequence
of course and speed manoeuvres.
The algorithms NPG and CPG determine game
and safe trajectory of the ship with relation to of all
objects and permits to take into account the degree
of their cooperation.
The algorithm MG determines game and safe tra-
jectory of the ship with relation to of the object of
most dangerous.
The algorithms DO and KO determine the opti-
mal and safe trajectory of the ship most nearing to
the received trajectory from the training simulator
ARPA.
The developed algorithms takes also into consid-
eration the Rules of the COLREG Rules and the ad-
vance time of the manoeuvre approximating the
ship's dynamic properties and evaluates the final de-
viation of the real trajectory from the reference val-
ue.
These algorithms can be used for computer sup-
porting of navigator safe manoeuvring decision in a
collision situations using information from ARPA
anti-collision radar system.
The sensitivity of the final game payment:
− is least relative to the sampling period of the tra-
jectory and advance time manoeuvre,
− most is relative to changes of the own and met
ships speed and course,
− it grows with the degree of playing character of
the control process and with the quantity of ad-
missible strategies.
REFERENCES
Baba, N. & Jain, L.C. 2001. Computational Intelligence in
Games. New York: Physica-Verlag.
Cahill, R.A. 2002. Collisions and thair Causes. London: The
Nautical Institute.
Cichuta, M. & Dalecki, M. 2000. Study of computer program
determining safe ship’s game trajectory with consideration
risk of collision. M.Sc. thesis, Gdynia Maritime Academy,
(in Polish).
Engwerda, J.C. 2005. LQ Dynamic Optimization and Differen-
tial Games. West Sussex: John Wiley and Sons.
Isaacs,. R. 1965. Differential games. New York: John Wiley
and Sons.
Lavalle, S.M. 2006. Planning algorithm. New York: Camridge.
Lebkowski, A. 2001. Study and computer simulation of game
positional control algorithm with consideration ship’s
speed changes in Matlab. M.Sc. thesis, Gdynia Maritime
Academy, (in Polish).
Levine, W.S. 1996. The Control Handbook. Florida: CRC
Press.
Lisowski, J. 2006a. The dynamic game theory methods applied
to ship control with minimum risk of collision. Risk Analy-
sis V: Simulation and Hazard Mitigation. Southampton,
Boston: WIT Press: 293-302.
Lisowski, J. 2006b. Game theory methods in control synthesis
of marine moving objects – mathematical models and com-
puter support algorithms. Proc. of the 10th IEEE Interna-
tional Conference on Methods and Models in Automation
and Robotics, Miedzyzdroje: 21-39.
172
Lisowski, J. 2007a. Intelligent safe ship control methods in col-
lision avoidance. Proc. of European Control Conference,
Kos: 1-6.
Lisowski, J. 2007b. The dynamic game models of safe naviga-
tion. Chapter in Monograph TransNav’2007: Advances in
marine navigation and safety of sea transportation. Gdynia:
Gdynia Maritime University-The Nautical Institute in Lon-
don: 23-30.
Lisowski, J. 2007c. Application of dynamic game and neural
network in safe ship control. Polish Journal of Environmen-
tal Studies. Vol. 16: 114-120.
Lisowski, J. 2008a. Optimal and game ship control algorithms
avoiding collisions at sea. Risk Analysis VI: Computer
Simulation Risk Analysis and Hazard Mitigation. South-
ampton, Boston: WIT Press: 1-10.
Lisowski, J. 2008b. Game and optimal safe ship control. Chap-
ter in monograph Recent Advances in Control and Automa-
tion. Warszawa: Exit: 302-312.
Lisowski, J. 2008c. Sensitivity of safe game ship control. Proc.
of 16
th
IEEE Mediterranean Conference on Control and
Automation, Corsica: 220-225.
Lisowski, J. & Mohamed-Seghir, M. 2008d. Safe ship control
methods based on fuzzy set theory. Polish Journal of Envi-
ronmental Studies. Vol. 17, No 3C: 55-58.
Nisan, N., Roughgarden, T., Tardos, E. & Vazirani, V.V. 2007.
Algorithmic Game Theory. New York: Cambridge Univer-
sity Press: 717-733.
Nise, N.S. 2008. Control systems engineering. New York: John
Wiley & Sons.
Nowak, A.S. & Szajowski, K. 2005 Advances in Dynamic
Games – Applications to Economics, Finance, Optimization
and Stochastic Control. Boston, Basel, Berlin: Birkhauser.
Osborne, M.J, 2004. An Introduction to Game Theory. New
York: Oxford University Press.
Pachciarek, A. 2007. Comparative analysis of safe ship trajec-
tory determining on computer simulation. B.Sc. thesis,
Gdynia Maritime University, (in Polish).
Radzik, T. 2000. Characterization of optimal strategies in ma-
trix games with convexity properties. International Journal
of Game Theory. Vol. 29: 211-228.
Sandom, C. & Harvey, R.S. 2004. Human factors for engi-
neers. London: The Institution of Electrical Engineers.
Segal, A. & Miloh, T. 1998. A new three dimensional differen-
tial game of pursuit and evasion. Proc. of the 8
th
Interna-
tional Symposium on Dynamic Games and Applications.
Maastricht.
Skogestad, S. & Postlethwaite, I. 2005. Multivariable feedback
control. New York: John Wiley & Sons.
Straffin, P.D. 2001. Game Theory and Strategy. Warszawa:
Scholar (in Polish).