69
1 INTRODUCTION
Theprocessoftheownshippassingothershipsatsea
very often occurs in conditions of uncertainty and
conflict accompanied by an inadequate co‐operation
of the ships with regard to the International
Regulations for Preventing Collisions at Sea
(COLREG).Itis,therefore,reasonabletoinvestigate,
develop and represent the methods of a ship’s safe
handlingusingtherulesoftheoryba
sedondynamic
gamesandmethodsofcomputationalintelligence.
In practice, the process of handling a ship as a
control object depends both on the accuracy of the
details concerning the current navigational situation
obtained from the ARPA (Aut
omatic Radar Plotting
Aids) anti‐collision system and on the form of the
process model used for determining the rulesofthe
handling synthesis. The ARPA system ensures
automatic monitoring of at least 20j‐th encountered
objects, determining their movement parameters
(speedV
j,courseψj)andelementsofapproachingto
ownship(
j
j
DCPAD
mi
n
– DistanceoftheClosest
Point of Approach,
j
j
TCPAT
mi
n
– Time to the
ClosestPointofApproach)andalsoassesstheriskr
j
of collision (Bist 2000, Cahill 2002, Gluver & Olsen
1998).
However, the range of functions of a standard
ARPA system ends up with a simulation of a
manoeuvre selected by navigator. The problem of
selecting such a manoeuvre is very difficult as the
processofcontrolisverycomplexsinceitisdynamic,
non‐linear,multi‐dimensionalandgamema
kinginits
nature (Figures 1 and 2) (Fang & Luo 2005, Fossen
2011,Lisowski2013b,Perez2005).
While formulating the model of the process it is
essential to take into consideration both the
kinematicsandthedynamicsoftheship’smovement,
the disturbances, the strategy of the encountered
objects and the formula assumed as the goal of
control.Thediversityofselect
ionofpossiblemodels
Game Strategies of Ship in the Collision Situations
J
.Lisowski
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT:Thepaperintroducedthebasicmodel ofprocessofsafeshipcontrolinacollisionsituationusinga
gamemodelwithjobjects,whichincludesnon‐linearstateequationsandnon‐linear,timevaryingconstraints
ofthestatevariablesaswellasthequalitygame controlindexintheformsofthegameint
egralpaymentand
thefinalpayment.Approximatedmodeloftheprocesscontrolasthemodelofmulti‐stepmatrixgameinthe
form of dual linear programming problem has been adopted here. The Game Ship Control GSC computer
program has been designed in the Mat
lab/Simulink software in order to determine the own ship’s safe
trajectory.TheseconsiderationshavebeenillustratedwithexamplesofacomputersimulationusinganGSC
program for determining the safe shipʹs trajectory in real navigational situation. Simulation research were
passedforfivesetsofstrategiesoftheownshipandmetships.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 8
Number 1
March 2014
DOI:10.12716/1001.08.01.08
70
directly affects the synthesis of the ship’shandling
algorithms which are afterwards affected by the
ship’s handling device, directly linked to the ARPA
system and, consequently, determines the effects of
safeandoptimalcontrol.
Figure1.Parametersdescribingtheprocessoftheownship
passingj‐thencounteredship.
Figure2.Vectorsofownshipandencounteredobjects.
2 BASICMODELOFGAMESHIPCONTROL
The most general description of the own ship’s
passingthejnumberofotherencounteredshipsisthe
modelofadifferentialgameofajnumberofobjects
(Figure3).
General dynamic features of the process are
describedbyasetofstateequationsinthefollowing
form:
),,,,(
00
00
tuuxxfx
jj
v
j
v
jii
(1)
where
tx
0
0
is
0
dimensional vector of the
process state of the own ship determined in a time
span
],[
0 k
ttt ,
tx
j
j
is
j
dimensional vector
of the process state for the j‐th object,
tu
o
0
is ν0
dimensional control vector of the own ship and
)(tu
j
j
is νj dimensional control vector of the j‐th
object(Isaacs1965,Keesman2011).
The state variable
0
0
x
is represented by the
values: course, angular turning speed, speed, drift
angle, rotational speed of the screw propeller and
controllable pitch propeller‐of the own ship and
j
j
x
by the values: distance, bearing, course and
speed‐of the j‐th object. While the control va lue
0
0
u
is represented by: reference rudder angle,
reference rotational speed screw propeller and
reference controllable pitch propeller‐of the own
shipand
j
j
u
bythevalues:courseandspeed‐ofthe
j‐thobject(Isil&Koditschek2001).
Theconstraintsofthecontrolandthestateofthe
processareconnectedwiththebasicconditionforthe
safe passing of the ships at a safe distance D
s in
compliance with COLREG Rules, generally in the
followingform(Mesterton‐Gibbons2001):
[ ( ), ( )] 0 1, 2,...,
jj
jj j
gx tu t j m
(2)
Theconstraints(2)as„ship’sdomains”takeaform
of a circle, ellipse, hexagon or parable and may be
generated,forexample,bytheneuralnetwork(Figure
4) (Cockcroft & Lameijer 2006, Landau et al. 2011,
Lisowski2014a,Millington&Funge2009,Zio2009).
Figure3.Blockdiagramofamodelship’sdifferentialgame
includingjparticipants.
Figure4. The shapes of the neural ship’s domains in the
situationof10encounteredobjects.
71
Thesynthesisofthedecisionmakingpatternofthe
ship’s handling leads to the determination of the
optimal strategies of the players who determine the
mostfavourable,undergivenconditions,conduct of
theprocess.Fortheclassofnon‐coalitiongames,often
used in the control techniques, the most beneficia l
conductoftheownshipasapla
yerwithj‐thobjectis
theminimizationofhergoalfunctioninthe formof
the payments – the integral payment and the final
one:
0
0
2
00
[ ()] () () min
k
t
j
jk k
t
Ixtdtrtdt
(3)
The integralpayment determines the loss of way
of the own ship to reach a safe passing of the
encounteredobjectsandthefinal onedeterminesthe
risk of collision and final game trajectory deflection
fromreferencetrajectory(Straffin2001).
Generallytwotypesofthesteeringgoalsaretaken
into considerat
ion‐programmed steering u0(t) and
positional steeringu
0[x0(t),t]. The basis for the
decision making steering are the decision making
patterns of the positional steering processes, the
patternswiththefeedbackarrangementrepresenting
thedifferentialgames.
Theapplicationofreductionsinthedescriptionof
theownship’sdynamicsandthedynamicofthej‐th
encountered object and their movement kinematics
lead to the a
pproximated matrix game model
(Cymbaletal.2007,Engwerda2005,Lisowski2013a).
3 APPROXIMATEDMODELOFGAMESHIP
CONTROL
3.1 Stateandcontrolvariables
Thedifferentialgameisreducedtoamatrixgameofa
j number of participants who do not co‐operate
amongthem(Figure5)(Lisowski2014b
).
Figure5. Block diagram of a model ship’s approximated
gamejparticipants.
Thestateandcontrolva riablesarerepresentedby
thefollowingvalues:
mj
Vuu
Vuu
NxDxYxXx
jjjj
jjjj
...,,2,1
,
,,
,,,,
21
2
0
1
0
212
0
1
0
(4)
3.2 Riskofcollision
The matrix game includes the values determined
previously on the basis of data taken from an anti‐
collision system ARPA the value a collision risk rj
with regard to the determined strategies of the own
shipandthoseofthej‐thencounteredobjects.
Theformofsuchagameisrepresentedbytherisk
ma
trix R=[r
j(ν0,νj)] containing the same number of
columns as the number of participant I (own ship)
strategies.Shehas;e.g.aconstantcourseandspeed,
alterationofthecourse20
o
tostarboard,to20
o
port
etc.,andcontainsanumberoflineswhichcorrespond
to a joint number of participant II (j‐th object)
strategies:
00
00
010111
00
00
1,21
1,21
1,21
21,22221
11,11211
0
....
....................
....
....................
....
....................
....
....
)],([
mmmm
jjjj
rrrr
rrrr
rrrr
rrrr
rrrr
rR
jj
(5)
Thevalue oftheriskofthecollisionr
jisdefinedas
thereferenceofthecurrentsituationoftheapproach
describedbytheparameters
j
D
min
and
j
min
T ,tothe
assumed assessment of the situation defined as safe
and determined by the safe distance ofapproach D
s
andthesafetimeTs–whicharenecessarytoexecutea
manoeuvre avoiding a collision with consideration
actualdistanceD
jbetweenownshipandencountered
j‐thship:
2
1
2
3
2
min
2
2
min
1
s
j
s
j
s
j
j
D
D
T
T
D
D
r
(6)
where the weight coefficients
1, 2 and 3 are
depended on the state visibility at sea (good or
restricted),kindofwaterregion(open or restricted),
speedVoftheship,staticLanddynamicL
dlengthof
ship, static B and dynamic B
d beam of ship, and in
practiceareequal(Figures6and7):
20),,(1
321
(7)
)345.0(1.1
6.1
VLL
d
(8)
)767.0(1.1
4.0
LVBB
d
(9)
72
Figure6. The surface of the collision risk value rj in
dependence on relative values distance and time of j‐th
objectapproach.
Figure7a. Dependenceof thecollision riskon thestrategy
the own ship and that of the j‐th encountered object to
approachingfromtheLB.
Figure7b. Dependenceofthe collisionriskon thestrategy
the own ship and that of the j‐th encountered object to
approachingfromtheSB.
Figure7c. Dependenceof the collisionrisk on thestrategy
the own ship and that of the j‐th encountered object to
approachingfromthestern.
The constraints affecting the choice of strategies
are a result of the recommendations of the way
priority at sea. Player I (own ship) may use
0 of
variouspurestrategiesinamatrixgameandplayer
II (encountered object) has
j of various pure
strategies(Osborne2004).
3.3 Controlalgorithm
Asthegame,mostfrequently, does not have saddle
pointthestateofbalanceisnotguaranteed,thereisa
lackofpurestrategiesforbothplayersinthegame.In
ordertosolvethisproblemduallinearprogramming
may be used (Pant
oja 1988, Seghir 2012, Speyer &
Jacobson2010).
In a dual problem player I having
0 various
strategies to be chosen tries to minimize the risk of
collision(Modares2006):
j
rI
0
min
0
(10)
whileplayerIIhaving
jstrategiestobechosentryto
maximizetheriskofcollision(Mehrotra1992):
j
j
rI
j
max (11)
The problem of determining an optimal strategy
may be reduced to the task of solving dual linear
programmingproblem:
j
j
rI
j
maxmin
0
0
(12)
Mixed strategy components express the
probability distribution P=[p
j(ν0,νj)] of using pure
strategiesbytheplayers:
73
00
00
010111
00
00
1,21
1,21
1,21
21,22221
11,11211
0
....
....................
....
....................
....
....................
....
....
)],([
mmmm
jjjj
pppp
pppp
pppp
pppp
pppp
pP
jj
(13)
Thesolutionforthesteeringgoalisthestrategyof
the highest probability and will also be the optimal
valueapproximatedtothepurestrategy:
max0
0
)],([
0
0
jjo
puu
(14)
The safe trajectory of the own ship has been
treated here as a sequence of changes course and
speed.
Thevaluesestablishedareasfollows:safepassing
distances among the ships under given visibility
conditionsatseaD
s,timedelayofmanoeuvringand
the duration of one stage of the trajectory as one
calculation step. At each step the most dangerous
object is determined withregard to the value of the
collision risk r
j. Consequently, on the basis of the
semantic interpretation of the COLREG Regulations
thedirectionofa turnoftheownshipisselected to
the most dangerous encountered object (Flechter
1987).
The collision matrix risk R is determined for the
admissiblestrategiesofthe ownship
0and those
j
for j‐th object encountered. By applying dual linear
programminginordertosolvethematrixgameyou
obtaintheoptimalvaluesoftheowncourseandthat
ofthe j‐thobjectatthesmallest deviationfromtheir
initialvalues.
If, at a givenstep, no solution can be found at a
speedoftheownshipV,thecalculat
ionsarerepeated
atthespeedreducedby25%untilthegamehasbeen
solved. The calculations are repeated step by step
untilthemomentwhenall elements ofthematrixR
becomeequaltozeroandtheownship,afterhaving
passedtheencountered objects, returns toherinit
ial
courseandspeed.
Inthismanneroptimalsafetrajectoryoftheshipis
obtained in a collision situation (Fadali & Visioli
2009).
Usingthefunctionoflp–linearprogrammingfrom
the Optimization Toolbox contained in the Matlab
software, the Game Ship Control GSC progra
m has
beendesignedforthedeterminationofthesafeship’s
trajectoryinacollisionsituation.
4 COMPUTERSIMULATION
4.1 GSC1program
Simulation tests in Matlab/Simulink of the GSC
programhavebeencarriedoutwithreferencetoreal
situationofpassingj=10encounteredships.
ForthefirstbaseversionGSC1oftheprogra
m,the
followingvaluesforthestrategieshavebeenadopted
(Figure8)(Lisowski&Lazarowska2013,Nisanetal.
2007):
oo
60013
0
foreachofthe
o
5 ,
oo
j
606025 foreachofthe
o
5 .
Figure8. Possible mutual strategies of the own ship and
thoseofthej‐thencounteredobjectinprogramGSC1.
Thecomputersimulation,performedonversionof
theGSC1programispresentedonFigure9.
4.2 GSC2program
For the second version GSC2 of the program, the
number of own ship strategies has been reduced to
(Figure10):
oo
60013
0
foreachofthe
o
5
,
ooo
j
30,0,303 .
Thecomputersimulation,performedonversionof
theGSC2programispresentedonFigure11.
74
Goodvisibility:Ds=0.5nm
r(tk)=0,d(tk)=2.89nm
Restrictedvisibility:Ds=2.5nm
r(tk)=0,d(tk)=4.73nm
Figure9. The shipʹs game trajectories for the GSC1
algorithm.
Figure10.Possiblemutualstrategiesoftheownshipand
thoseofthej‐thencounteredobjectinprogramGSC2.
Goodvisibility:Ds=0.5nm
r(tk)=0,d(tk)=2.83nm
Restrictedvisibility:Ds=2.5nm
r(tk)=0,d(tk)=6.75nm
Figure11. The shipʹs game trajectories for the GSC2
algorithm.
4.3 GSC3program
FortheversionGSC3oftheprogra m,thenumberof
ownshipstrategieshasbeenreducedto(Figure12):
oooo
60,40,20,04
0
,
ooo
j
30,0,303 ,
75
Figure12. Possible mutual strategies of the own ship and
thoseofthej‐thencounteredobjectinprogramGSC3.
Thecomputersimulation,performedonversionof
theGSC3programispresentedonFigure13.
Goodvisibility:Ds=0.5nm
r(tk)=0,d(tk)=2.08nm
Restrictedvisibility:Ds=2.5nm
r(tk)=0,d(tk)=6.68nm
Figure13.TheshipʹsgametrajectoriesfortheGSC3
algorithm.
4.4 GSC4program
FortheversionGSC4oftheprogra m,thenumberof
ownshipstrategieshasbeenreducedto(Figure14):
ooo
60,30,03
0
,
ooo
j
30,0,303 ,
Figure14. Possible mutual strategies of the own ship and
thoseofthej‐thencounteredobjectinprogramGSC4.
Thecomputersimulation,performedonversionof
theGSC4programispresentedonFigure15.
4.5 GSC5program
For the version GSC5, the number of the own ship
strategieshasbeenreducedto(Figure16):
oo
60,02
0
,
ooo
j
30,0,303 .
Figure16. Possible mutual strategies of the own ship and
thoseofthej‐thencounteredobjectinprogramGSC5.
Thecomputersimulation,performedonversionof
theGSC5programispresentedonFigure17.
76
Goodvisibility:Ds=0.5nm
r(tk)=0,d(tk)=1.52nm
Restrictedvisibility:Ds=2.5nm
r(tk)=0,d(tk)=2.42nm
Figure15. The shipʹs game trajectories for the GSC4
algorithm.
5 CONCLUSIONS
Analysis of the computer simulation studies of GSC
program for different amounts of possible strategies
of own ship and met objects allows to draw the
followingconclusions:
Thesynthesisofanoptimalon‐linecontrolonthe
baseofmodelofamulti‐stepmatrixgamemakes
itpossibletodeterminethesafegametrajectoryof
the own ship in situations when she passes a
greaterjnumberoftheencounteredobjects;
The trajectory has been described as a certain
sequence of manoeuvres with the course and
speed;
Goodvisibility:Ds=0.5nm
r(tk)=0,d(tk)=1.20nm
Restrictedvisibility:Ds=2.5nm
r(tk)=0,d(tk)=6.68nm
Figure17. The shipʹs game trajectories for the GSC5
algorithm.
The computer program designed in the Matlab
also takes into consideration the following:
regulationsoftheConventionontheInternational
Regulations for Preventing Collisions at Sea,
advance time for a manoeuvre calculated with
regard to the ship’s dynamic features and the
assessmentofthefinaldeflectionbetweenthereal
trajectory
anditsassumedvalues;
Theessentialinfluencetoformofsafeandoptimal
trajectory and value of deflection between game
and reference trajectories has the number of
admissiblestrategiesofownshipandencountered
objects;
It results from the performed simulation testing
this algorithm is able to determine the correct
gametrajectorywhentheshipisnotinasituation
when she approaches too large number of the
observed objects or the said objects are found at
longdistancesamongthem;
77
In the case of the high traffic congestion the
program is not able to determine the safe game
manoeuvre.Thissometimesresultsinthebacking
oftheownobjectwhichiscontinueduntilthetime
whenahazardoussituationimproves.
REFERENCES
Bist,D.S.2000.Safetyandsecurityatsea.Oxford‐NewDelhi:
ButterHeinemann.
Cahill, R.A. 2002. Collisions and thair causes. London: The
NauticalInstitute.
Cockcroft, A.N. & Lameijer, J.N.F. 2006. The collision
avoidancerules.Amsterdam‐Tokyo:Elsevier.
Cymbal, N. N., Burmaka, I.A. & Tupikov, I.I. 2007.
Elastic strategies of the passing ships. Odessa: KP
OGT,(inRussian).
Engwerda, J.C. 2005. LQ dynamic optimization and
differentialgames.WestSussex:JohnWiley&Sons.
Fadali, M.S. & Visioli, A. 2009. Digital control
engineering.Amsterdam‐Tokyo:Elsevier.
Fang, M.C. & Luo, J.H. 2005. The nonlinear
hydrodynamic model for simulating a ship
steering in waves with autopilot system. Ocean
Engineering11‐12(32):1486‐1502.
Fletcher,R.1987.Practicalmethodsofoptimization.New
York:JohnWileyandSons.
Fossen, T.I. 2011. Marine craft hydrodynamics and
motioncontrol.Trondheim:Wiley.
Gluver, H. & Olsen, D. 1998. Ship collision analysis.
Rotterdam‐Brookfield:A.A.Balkema.
Isaacs, R. 1965. Differential games. New York: John
Wiley&Sons.
IsilBozma,H.&Koditschek,D.E.2001.Assemblyasa
non‐cooperativegameofitspieces:AnalysisofID
sphereassemblies.Robotica19:93‐108.
Keesman, K.J. 2011. System identification. London‐
NewYork:Springer.
Landau, I.D., Lozano, R., M’Saad, M. & Karimi, A.
2011.Adapivecontrol.London‐NewYork:Springer.
Lisowski,J.2013.Thesensitivityofcomputersupport
game algorithms of a safe ship control.
International
Journal of Applied Mathematics and
ComputerScience23(2):439‐446.
Lisowski, J. 2013. Optimal and game control
algorithms of ship in collision situations at sea.
ControlandCybernetics(42)4:1‐20.
Lisowski, J. & Lazarowska, A. 2013. The radar data
transmission to computer supportsystem of ship
safety.SolidStatePhenomena196:95‐101.
Lisowski, J. 2014. Optimization‐supported decision‐
making in the marine game environment. Solid
StatePhenomena210:215‐222.
Lisowski, J. 2014. The characteristics of the matrix
gamesensitivityofthesafepassingofshipsatsea.
SolidStatePhenomena210:258‐264.
Mehrotra,S.1992.Ontheimplementationofaprimal‐
dual interior point method. SIAM Journal on
Optimization4(2):575‐601.
Mesterton‐Gibbons, M. 2001. An introduction to game
theoretic modeling. Providence: American
MathematicalSociety.
Millington,I.&Funge,J.2009.Artificialintelligencefor
games.Amsterdam‐Tokyo:Elsevier.
Modarres, M. 2006. Risk analysis in engineering. Boca
Raton:Taylor&FrancisGroup.
Nisan, N., Roughgarden, T., Tardos, E. & Vazirani,
V.V. 2007. Algorithmic game theory. New York:
CambridgeUniversityPress.
Osborne, M.J. 2004. An introduction to game theory.
NewYork:OxfordUniversityPress.
Pantoja, J.F.A. 1988. Differential dynamic
programmingandNewton’smethod.International
JournalofControl5(47):1539‐1553.
Perez,T.2005.Shipmotioncontrol.London:Springer.
Straffin, P.D. 2001. Game theory and strategy.
Warszawa:Scholar(inpolish).
Seghir, M.M. 2012. Safe ship’s control in a fuzzy
environment using genetic algorithm. Solid State
Phenomena180:70‐75.
Speyer,J.L.&Jacobson,D.H.2010. Primer on optimal
controltheory.Philadelphia:SIAM.
