International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 1
Number1
March 2007
11
The Dynamic Game Models of Safe Navigation
J. Lisowski
Gdynia Maritime University, Gdynia, Poland
ABSTRACT: The paper introduce the application of selected methods of a game theory for automation of the
processes of moving object steering, the game control processes in marine navigation and mathematical
models of the safe ship control. The control goal has been defined first and then description of the base model,
the approximated models of multi-stage positional game and multi-step matrix game of the safe ship steering
in a collision situation has been presented.
1 INTEGRATED NAVIGATION
1.1 Multilevel system
The control of the ship’s movement may be treated
as a multilevel problem shown on Figure 1, which
results from the division of the entire control system
of ship - within the frame of the performance of the
cargo carriage by the ship’s operator - into clearly
determined subsystems which are ascribed appropriate
layers of control (Lisowski 2004b).
Fig. 1. Multilevel ship movement steering system
This is connected both with a large number of
dimensions of the steering vector and of the status of
the process, its random, fuzzy and decision making
characteristics - which are affected by strong
interference generated by the current, wind and the
sea wave motion on the one hand, and a complex
nature of the equations describing the ship’s
dynamics with non-linear and non-stationary
characteristics. The determination of the global
control of the steering systems has in practice
become too costly and ineffective (Lisowski 2005e).
1.2 Control processes
The integral part of the entire system is the process
of the ship’s movement control, which may be
described with appropriate differential equations of
the kinematics and dynamics of a ship being an
object of the control under a variety of the ship’s
operational conditions such as:
− stabilisation of the course or trajectory,
− adjustment of the ship’s speed,
− precise steering at small speeds in port with
thrusters or adjustable-pitch propeller,
− stabilisation of the ship’s rolling,
− commanding the towing group,
− dynamic stabilisation of the drilling ship’s or the
tanker’s position.
12
The functional draft of the system corresponds to
a certain actual arrangement of the equipment. The
increasing demands with regard to the safety of
navigation are forcing the ship’s operators to install
the systems of integrated navigation on board their
ships. By improving the ship’s control these systems
increase the safety of navigation of a ship - which is
a very expensive object of the value, including the
cargo, and the effectiveness of the carriage goods by
sea (Lisowski 2000a, 2005b, 2007).
2 SAFE SHIP CONTROL
2.1 ARPA acquisition and tracking
The challenge in research for effective methods to
prevent ship collisions has become important with
the increasing size, speed and number of ships
participating in sea carriage. An obvious
contribution in increasing safety of shipping has
been firstly the application of radars and then the
development of ARPA (Automatic Radar Plotting
Aids) anti-collision system (Cahill 2002).
The ARPA system enables to track automatically
at least 20 encountered j objects as is shown on
Figure 2, determination of their movement parameters
(speed V
j
, course ψ
j
) and elements of approach to the
own ship (
j
j
DCPAD
=
min
- Distance of the Closest
Point of Approach,
j
j
TCPAT
=
min
- Time to the
Closest Point of Approach) and also the assessment
of the collision risk r
j
(Lisowski 2001a).
Fig. 2. Navigational situation representing the passing of the
own ship with the j-th object
The risk value is possible to define by referring
the current situation of approach, described by
parameters
j
D
min
and
j
T
min
, to the assumed evaluation
of the situation as safe, determined by a safe distance
of approach D
s
and a safe time T
s
– which are
necessary to execute a collision avoiding manoeuvre
with consideration of distance D
j
to j-th met object -
shown on Figure 3 (Lisowski 2001b, 2004a, 2006):
2
1
2
2
2
2
1
−
+
+
=
s
j
s
j
min
s
j
min
j
D
D
T
T
k
D
D
kr
(1)
The weight coefficients k
1
and
k
2
are depended on
the state visibility at sea, dynamic length L
d
and
dynamic beam B
d
of the ship, kind of water region
and in practice are equal:
10
21
≤≤ )],(),,([
dddd
BLkBLk
(2)
).(.
.61
3450111
VL
d
+=
(3)
).(.
.40
767011
LVBB
d
+=
(4)
Fig. 3. The ship's collision risk space in a function of relative
distance and time of approaching the j-th object
2.2 ARPA manoeuvre simulation
The functional scope of a standard ARPA system
ends with the simulation of the manoeuvre altering
the course
ψ
∆±
or the ship's speed
V∆±
selected
by the navigator as is shown on Figure 4.
13
Fig. 4. The screen of SAM Electronics ARPA on the sailing
vessel s/v DAR MLODZIEZY
2.3 Computer support of navigator
The problem of selecting such a manoeuvre is very
difficult as the process of control is very complex
since it is dynamic, non-linear, multi-dimensional,
non-stationary and game making in its nature.
In practice, methods of selecting a manoeuvre
assume a form of appropriate steering algorithms
supporting 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 (Lisowski 2005a, c, d).
3 GAME CONTROL IN MARINE NAVIGATION
3.1 Dynamic game of ship control
The classical issues of the theory of the decision
process in marine navigation include the safe
steering of a ship. The problem of non-collision
strategies in the steering at sea appeared in the
Isaacs' works (Isaacs 1965) called "the father of the
differential games" and was developed by many
authors both within the context of the game theory
(Baba & Jain 2001, Segal & Miloh 1998), and also
in the steering under uncertainty conditions
(Engwerda 2005).
The definition of the problem of avoiding a
collision seems to be quite obvious, however, apart
from the issue of the uncertainty of information
which may be a result of external factors (weather
conditions, sea state), incomplete knowledge about
other objects and imprecise nature of the
recommendations concerning the right of way
contained in International Regulations for Preventing
Collision at Sea COLREG.
The problem of determining safe strategies is still
an urgent issue as a result of an ever increasing
traffic of vessels on particular water areas. It is also
important due to the increasing requirements as to
the safety of shipping and environmental protection,
from one side, and to the improving opportunities to
use computer supporting the navigator's duties. In
order to ensure safe navigation the ships are obliged
to observe legal requirements contained in the
COLREG Rules.
However, these Rules refer exclusively to two
ships under good visibility conditions, in case of
restricted visibility the Rules provide 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
indefiniteness and conflict accompanied by an
imprecise co-operation among the ships in the light
of the legal regulations.
Consequently, it is reasonable - for ship
operational purposes - to present this process and to
develop and examine methods for a safe steering of
the ship by applying the rules of the game theory.
A necessity to consider simultaneously the
strategies of the encountered objects and the dynamic
properties of the ships as the steering objects is a
good reason for the application of the differential
game model - often called the dynamic game - for
the description of the processes (Osborne 2004,
Straffin 2001).
3.2 Processes of game ship control
Assuming that the dynamic movement of the ships
in time occurs under the influence of the appropriate
sets of steering:
],[
)(
)(
j
j
UU
µ
µ
0
0
(5)
where:
)(
0
0
µ
U
– a set of the own ship's strategies,
)(
j
j
U
µ
– a set of the j-th ship's strategies,
0
0
=),(
j
µµµ
– denotes course and trajectory
stabilisation,
1
0
=),(
j
µµµ
– denotes the execution of the anti-
collision manoeuvre in order to minimize
the risk of collision, which in practice is
achieved by satisfying the following
inequality:
sj
j
DtDD
≥= )(min
min
(6)
14
j
D
min
– the smallest distance of approach of the
own ship and the j-th encountered object,
D
s
– safe approach distance in the prevailing
conditions depends on the visibility
conditions at sea, the COLREG Rules and
the ship's dynamics.
D
j
– current distance to the j-th object taken
from the ARPA anti-collision system.
1
0
−=),(
j
µµµ
– refers to the manoeuvring of the ship
in order to achieve the closest point of
approach, for example during the approach of
a rescue vessel, transfer of cargo from ship to
ship, destruction the enemy's ship, etc.).
In the adopted describing symbols we can
discriminate the following type of steering ship in
order to achieve a determined goal:
− basic type of steering – stabilization of the course
or trajectory:
][
)()( 00
0
j
UU
− avoidance of a collision by executing:
− own ship's manoeuvres:
][
)()( 01
0
j
UU
− manoeuvres of the j-th ship:
][
)()( 10
0
j
UU
− co-operative manoeuvres:
][
)()( 11
0
j
UU
− encounter of the ships:
][
)()( 11
0
−−
j
UU
− situations of a unilateral dynamic game:
][][
)()()()( 10
0
01
0
−−
jj
UUandUU
Dangerous situations resulting from a faulty
assessment of the approaching process by one of
the party with the other party's failure to conduct
observation - one ship is equipped with a radar or
an anti-collision system, the other with a damaged
radar or without this device (Lisowski 2002).
− chasing situations which refer to a typical con-
flicting dynamic game:
][][
)()()()( 11
0
11
0
−−
jj
UUandUU
.
The first case usually represents regular optimal
control, the second and third are unilateral games
while the fourth and fifth cases represent the
conflicting games.
4 MATHEMATICAL MODELS OF SAFE SHIP
CONTROL
4.1 Base model
As the process of steering the ship in collision
situations, when a greater number of objects is
encountered, often occurs under the conditions of
indefiniteness 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 objects of steering.
The diversity of selection of possible models
directly affects the synthesis of the ship’s handling
algorithms which are afterwards effected by the
ship’s handling device directly linked to the ARPA
system and, consequently, determines the effects of
the safe and optimal control.
4.1.1 State equation
The most general description of the own control
object passing the j number of other encountered
moving objects is the model of a differential game of
a j number of objects - shown on Figure 5.
Fig. 5. Block diagram of a base dynamic game model
The properties of the process are described by the
state equation:
]),,...,,...,,(),,...,,...,,[(
tuuuuxxxxfx
m
j
m
j
m
v
j
v
v
mjii
νϑ
ϑ
ϑ
ϑ
1
0
1
0
1010
=
( )
0
21
ϑϑ
+⋅=
j
ji
...,,,
, j = 1, 2, …, m (7)
where:
( )
tx
0
0
ϑ
–
0
ϑ
dimensional vector of the process
state of the own control object determined in a
time span
],[
k
ttt
0
∈
,
( )
tx
j
j
ϑ
–
j
ϑ
dimensional vector of the process
state for the j-th object,
( )
tu
o
0
ν
– ν
0
dimensional control vector of the own
control object,
)(
tu
j
j
ν
– ν
j
dimensional control vector of the j-
th object.
Taking into consideration the equations reflecting
the own ship's hydromechanics and equations of the
own ship's movement relative to the j-th encountered
object, the equations of the general state of the
process (7) take the following specific form (8).
15
( )
2
5
44
11
4
13
4
2
0
3
3312
0
2
332
0
23
0
1
3
04
6
011
6
0
2
03
5
010
5
0
1
0
3
02
2
09
4
0
2
05
4
0
4
0
3
04
4
0
3
03
4
0
1
0
3
0
4
0
3
02
6
0
5
0
5
08
3
0
3
07
4
0
3
0
2
06
4
0
4
0
3
0
2
05
4
0
4
0
4
0
3
0
3
04
3
0
1
0
3
0
3
01
3
0
3
02
3
0
2
01
2
0
2
0
1
0
1
jjjj
j
j
jjjj
jjjj
jjjj
ubxxax
uxbxx
xsinxxxx
xcosxxxxx
ubxax
ubxax
uxbxaxxaxxxaxxax
uxxxbxxxaxxaxxxa
xxxxaxxxxxax
uxxbxxaxxax
xx
+
+
+
+=
+−=
+−=
++−=
+=
+=
++++=
+++
+++=
++=
=
(8)
The state variables are represented by the
following values:
ψ
=
1
0
x
– course of the own ship,
ψ
=
2
0
x
– angular turning speed of the own ship,
Vx
=
3
0
– speed of the own ship,
β
=
4
0
x
– drift angle of the own ship,
nx
=
5
0
– rotational speed of the screw propeller
of the own ship,
H
x
=
6
0
– pitch of the adjustable propeller of the
own ship,
jj
Dx
=
1
– distance to j-th object, or x
j
– its
coordinate,
jj
Nx
=
2
– bearing of the j-th object, or y
j
– its
coordinate,
jj
x ψ
=
3
– course of the j-th object, or β
j
–
relative meeting angle,
jj
Vx
=
4
– speed of the j-th object,
where:
46 ==
jo
ϑϑ
,
.
While the control values are represented by:
r
u α
=
1
0
– reference rudder angle of the own ship,
or
ψ
- angular turning speed of the own ship, or
ψ
- course of the own ship, depending of a kind
approximated model of process,
r
nu
=
2
0
– reference rotational speed of the own
ship’s screw propeller, or force of the propeller
thrust of the own ship, or speed of the own ship,
r
Hu
=
3
0
– reference pitch of the adjustable
propeller of the own ship,
jj
u ψ
=
1
– course of the j-th object, or
j
ψ
-
angular turning speed of the j-th object,
jj
Vu
=
2
– speed of the j-th object, or force of the
propeller thrust of the j-th object,
where:
23 ==
jo
νν
,
.
Values of coefficients of the process state
equations (8) for the 12 000 DWT container ship are
given in Table 1.
Table 1. Coefficients of basic game model equations
Coefficient
Measure
Value
a
1
m
-1
- 4.143∙10
-2
a
2
m
-2
1.858∙10
-4
a
3
m
-1
- 6.934∙10
-3
a
4
m
-1
- 3.177∙10
-2
a
5
-
- 4.435
a
6
-
- 0.895
a
7
m
-1
- 9.284∙10
-4
a
8
-
1.357∙10
-3
a
9
-
0.624
a
10
a
11
s
-1
s
-1
- 0.200
- 0.100
a
11+j
s∙m
-1
- 7.979∙10
-4
b
1
m
-2
1.134∙10
-2
b
2
m
-1
- 1.554∙10
-3
b
3
s
-1
0.200
b
4
s
-1
0.100
b
4+j
m
-1
- 3.333∙10
-3
b
5+j
m∙s
-1
9.536∙10
-2
In example for j=20 objects the base game model
is represented by i=86 state variables of process
control.
4.1.2 Constraints
The constraints of the control and the state of the
process are connected with the basic condition for
the safe passing of the objects at a safe distance D
s
in
compliance with COLREG Rules, generally in the
following form:
0≤),(
jj
jjj
uxg
νϑ
(9)
The constraints referred to as the ships domains in
the marine navigation, may assume a shape of a
circle, ellipse, hexagon, or parabola and may be
generated for example by an artificial neural network
as is shown on Figure 6 (Lisowski et al. 2000b).
16
Fig. 6. The shapes of the neural ship’s domains in the situation
of three encountered objects on Gdanska Bay
4.1.3 Goal function
The synthesis of the decision making pattern of
the object control leads to the determination of the
optimal strategies of the players who determine the
most favourable, under given conditions, conduct of
the process. For the class of non-coalition games,
often used in the control techniques, the most
beneficial conduct of the own control object as a
player with j-th object is the minimization of her
goal function in the form of the payments – the
integral payment and the final one:
min)()()]([ →++=
∫
k
t
t
kj
j
tdtrdttxI
k
0
0
2
00
ϑ
(10)
The integral payment represents loss of way by
the ship while passing the encountered objects and
the final payment determines the final risk of
collision r
j
(t
k
) relative to the j-th object and the final
deflection of the ship d(t
k
) from the reference
trajectory.
Generally two types of the steering goals are
taken into consideration - programmed steering u
0
(t)
and positional steering u
0
[x
0
(t)]. The basis for the
decision making steering are the decision making
patterns of the positional steering processes, the
patterns with the feedback arrangement representing
the dynamic games.
The application of reductions in the description of
the own ship’s dynamics and the dynamic of the j-th
encountered object and their movement kinematics
lead to approximated models.
4.2 Approximate models
4.2.1 Multi-stage positional game
The general model of dynamic game is simplified
to the multi-stage positional game of j participants
not co-operating among them.
State variables and control values are represented
by:
=
====
====
mj
VuuVuu
YxXxYxXx
jjjj
jjjj
...,,,
,,,
,,,
)()()()(
)()()()(
21
212
0
1
0
21
0
2
00
1
0
ψψ
(11)
The essence of the positional game is to
subordinate the strategies of the own ship to the
current positions p(t
k
) of the encountered objects at
the current step k. In this way the process model
takes into consideration any possible alterations of
the course and speed of the encountered objects
while steering is in progress. The current state of the
process is determined by the co-ordinates of the own
ship's position and the positions of the encountered
objects:
17
( )
( )
=
==
mj
YXxYXx
jjj
...,,,
,,,
21
000
(12)
The system generates its steering at the moment t
k
on the basis of data received from the ARPA anti-
collision system pertaining to the positions of the
encountered objects:
Kkmj
tx
tx
tp
kj
k
k
,...,,,...,,
)(
)(
)( 2121
0
==
=
(13)
It is assumed, according to the general concept of
a multi-stage positional game, that at each discrete
moment of time t
k
the own ship knows the positions
of the objects.
The constraints for the state co-ordinates:
( ) ( )
{ }
Ptxtx
j
∈,
0
(14)
are navigational constraints, while steering
constraints:
mjUuUu
jj
,...,,, 21
00
=∈∈
(15)
take into consideration: the ships' movement
kinematics, recommendations of the COLREG Rules
and the condition to maintain a safe passing distance
as per relationship (6).
The closed sets
j
U
0
and
0
j
U
, defined as the sets of
acceptable strategies of the participants to the game
towards one another:
)]}([,)]([{
tpUtpU
j
j
0
0
(16)
are dependent, which means that the choice of
steering u
j
by the j-th object changes the sets of
acceptable strategies of other objects.
Fig. 7. Positional game trajectories in good visibility, D
s
=0.6
nm, r(t
k
)=0, d(t
k
)=4.67 nm in a situation of passing 42
encountered objects
Fig. 8. Positional game trajectories in restricted visibility,
D
s
=3.0 nm, r(t
K
)=0, d(t
K
)=12.11 nm in a situation of passing 42
encountered objects
Examples of safe positional game trajectories are
shown on Figures 7 and 8.
4.2.2 Multi-step matrix game
When leaving aside the ship's dynamics equations
the general model of a dynamic game for the process
of preventing collisions is reduced to the matrix
game of j participants non-co-operating among them
(Lisowski 2004b).
The state and steering variables are represented
by the following values:
mj
VuuVuuNxDx
jjjjjjjj
...,,,
,,,,,
)()()()()()(
21
212
0
1
0
21
=
======
ψψ
(17)
The game matrix R[r
j
(ν
j
, ν
o
)] includes the values
of the collision risk r
j
determined from relation (1)
on the basis of data obtained from the ARPA anti-
collision system for the acceptable strategies ν
0
of
the own ship and acceptable strategies ν
j
of any
particular number of j encountered objects.
In a matrix game player I -own ship has a
possibility to use
ν
0
pure various strategies, and
player II -encountered objects have
ν
j
various pure
strategies:
nmmmm
njjjj
n
n
n
rrrr
rrrr
rrrr
rrrr
rrrr
rR
jj
νννννν
νννννν
νννννν
νν
νν
νν
121
121
121
2122221
1111211
0
0
0
10111
0
0
−
−
−
−
−
==
,
,
,
,
,
....
....................
....
....................
....
....................
....
....
)],([
(18)
18
The constraints for the choice of a strategy
( )
j
νν
,
0
result from the recommendations of the way priority
at sea.
Examples of safe risk game trajectories are shown
on Figures 9 and 10.
Fig. 9. Risk game trajectories in good visibility, D
s
=0.6 nm,
r(t
k
)=0, d(t
k
)=3.81 nm in a situation of passing 42 encountered
objects
Fig. 10. Risk game trajectories in restricted visibility, D
s
=3.0 nm,
r(t
K
)=0, d(t
K
)=8.43 nm in a situation of passing 42 encountered
objects
5 CONCLUSION
The application of the models of a game theory for
the synthesis of an optimal manoeuvring makes it
possible to determine the safe game trajectory of the
own ship in situations when she passes a greater
number of the encountered objects.
To sum up it may be stated that the control
methods considered in this study are, in a certain
sense, formal models for the thinking processes of a
navigating officer steering of own ship and making
decisions on manoeuvres.
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.
Engwerda J.C., 2005. LQ Dynamic Optimization and
Differential Games. West Sussex: John Wiley and Sons.
Isaacs R., 1965. Differential games. New York: John Wiley
and Sons.
Lisowski J., 2000. Computational intelligence and optimization
methods applied to safe ship’s control – the dynamic
programming and neural network methods. Journal of
Shanghai Maritime University. No 3, Vol. 21: 33-41.
Lisowski J., Rak A. & Czechowicz W., 2000. Neural network
classifier for ship domain assessment. Journal of Mathema-
tics and Computers in Simulation. No 3-4, Vol. 51:399-
406.
Lisowski J., 2001a. Computational intelligence methods in the
safe ship control process. Polish Maritime Research.
No 1,Vol. 8: 18-24.
Lisowski J., 2001b. Optimal and safe ship control as a multi-
step matrix game. Systems Science. No 3, Vol. 27: 97-113.
Lisowski J., 2002. Game control of moving objects. Proc. of
the 15
th
IFAC World Congress, Barcelona.
Lisowski J., 2004a. Multi-step matrix game with the risk of
ship collision. Risk Analysis IV: Simulation and Hazard
Mitigation. Southampton, Boston: WIT Press Computational
Mechanics Inc.: 669-680.
Lisowski J., 2004b. Safety of navigation based on game theory
– mathematical models of game ship control. Journal of
Shanghai Maritime University, No 104, Vol. 25: 65-74.
Lisowski J., 2005a. Dynamic games methods in navigator
decision support system for safety navigation. Advances in
Safety and Reliability, Vol. 2, London-Singapore: Balkema
Publishers: 1285-1292.
Lisowski J., 2005b. Comparative analysis of safe ship control
methods. Proc. of the 11
th
Int. Conf. on Methods and
Models in Automation and Robotics, Międzyzdroje: 149-
154.
Lisowski J., 2005c. Game and computational intelligence
decision making algorithms for avoiding collision at sea.
Proc. of the IEEE Int. Conf. on Technologies for Homeland
Security and Safety, Gdańsk: 71-78.
Lisowski J., 2005d. Game control methods in navigator
decision support system. The Archives of Transport. No 3-4,
Vol. XVII: 133-147
Lisowski, J. 2005e. Mathematical modeling of a safe ship
optimal control process. Polish Journal of Environmental
Studies. Vol. 14: 68-75.
Lisowski J., 2006. The dynamic game theory methods applied
to ship control with minimum risk of collision. Risk
Analysis V: Simulation and Hazard Mitigation. Sout-
hampton, Boston: WIT Press: 293-302.
Lisowski J., 2007. Intelligent safe ship control methods in
collision avoidance. Proc. of European Control Con-
ference, Kos: 1-6.
Osborne M.J., 2004. An Introduction to Game Theory. New
York: Oxford University Press.
Segal A. & Miloh T., 1998. A new three dimensional
differential game of pursuit and evasion. Proc. of the 8
th
International Symposium on Dynamic Games and
Applications. Maastricht.
Straffin P.D., 2001. Game Theory and Strategy. Warszawa:
Scholar (in Polish).
