125

1 INTRODUCTION

The safe conduct of a commercial ship in situations of

passing by with more of the ships they meet is to keep

the least risk of collision with each of them. The

source of information on the current state of the vessel

traffic control process and the collision risk

assessment is the Automatic Radar Plotting Aid

(ARPA) radar anti-collision system, which enables the

operator of the vessel through the TRIAL

MANOEUVRE function to determine the anti-

collision manoeuvre in relation to the most dangerous

vessel, including the rules of the International

Regulations for Preventing Collision at Sea

(COLREGs) maritime route according to International

Maritime Organization (IMO). The COLREGs rules

apply only to two ships met, separately for the

conditions of good and restricted visibility at sea.

Over 80% of ship collisions are caused by the

human factor, during the subjective assessment of the

navigational situation and maneuvering decision in

the game environment (Engwerda 2005, Kun 2001,

Lebkowski 2018, Millington & Funge 2009).

It is assumed that about half of these losses can be

avoided using computer-aided navigator decision

support software using artificial intelligence, game

theory and optimization methods (Bist 2000, Isaacs

1965, Lazarowska 2017, Miloh 1974, Perez 2005,

Szlapczynski & Szlapczynska 2016).

The aim of this article is to present a multi-step

matrix game that contain the risk of ship collisions,

determining the safe trajectory of the ship in terms of

multi-criteria optimization, allowing for the degree of

cooperation in avoiding collisions (Kouemou, 2009,

Lisowski 2016, Olsder & Walter 1977).

This article proposes a new mathematical

formulation model of the collision-risk index,

depending on ships proximity parameters and the

distance between them.

Multi-criteria Optimization of Multi-step Matrix Game

in Collision Avoidance of Ships

. Lisowski

Gdynia Maritime University, Gdynia, Poland

ABSTRACT: This research article formulates a mathematical model of the matrix game of the safe ship control

process containing: state variables and control, collision risk definition and the form of a collision risk matrix.

Multicriteria optimization of the matrix game was introduced, leading to non-cooperative and cooperative

game control algorithms and non-game control. Simulation safe trajectories of own ship for various types of

control were compared to the example of the real situation at sea.

http://www.transnav.eu

the International Journal

on Marine Navigation

and Safety of Sea Transportation

Volume 13

Number 1

March 2019

DOI: 10.12716/1001.13.01.12

126

2 THE MATHEMATICAL MODEL OF A MATRIX

GAME

Figure 1 presents a matrix game of the process of

controlling your own ship in the situation of passing

by with the ships at sea.

Figure 1. Matrix game of ships.

2.1 State and control variables

Process state variables are represented by the distance

between the encountered ships D

j, bearing Nj and the

risk of collision r

j and the coordinates of the own-ship

position (X,Y) on the reference trajectory of movement

(Kazimierski & Stateczny 2013).

The control variables of the own-ship are: the

course

 and the speed V, and the control quantities

of the j-th encountered ship in question are its course

j and the speed Vj (Tomera 2012).

State variables in the ship control process in

collision situations are measurable by means of the

on-board ARPA anti-collision system.

2.2 Collision-risk

The forms of the collision-risk r

j of own-ship with the

j-th encountered ship as the mean square reference of

a safe situation are determined by the value of the

assumed safe distance D

s and safe approach time Ts

with the current situation of the ships approximation

which are determined by the smallest expected

distance D

j,min and time to the largest approximations

of T

j,min and the distance between ships Dj:





,min











,min

















(1)

where the coefficients a

1 and a2 determine: the type of

visibility at sea - good or restricted and the type of

navigation area - open or closed (Modarres 2006, Xu

2014) (Fig. 2).

Figure 2. Collision-risk characteristics in the situation of

concentrated ship traffic at: a

1 = a2 = 0.4, Ds/Dj = 0.5 (above)

and in the situation of larger distances between ships at: a

1 =

2 = 0.5, Ds/Dj = 0.1 (below).

The mathematical collision-risk model proposed

here was taken into account not only the approach

parameters of D

j,min and Tj,min, but also the distances

between ships

Dj. The value of collision-risk also

depends on the density of the position of the

encountered ships (Lisowski 2014).

2.3 Matrix of collision-risk

The game matrix R, in which own ship with clean s

strategies and m encountered ships with clean

strategies, can each be presented each in the following

equation form:













...







...



...



...



(2)

The numbers of rows are corresponded to the

amount W of the acceptable own-hip's strategy in the

w set, in the form of changes in its course  and the

speed

V to avoid collision (Mesterton-Gibbons 2001,

Polak et al. 2016):

127

 

12 3

0, , , ...

1, 2, ...,

wwi w w w

Ss s s s V



  



(3)

The numbers of columns were corresponded to the

total amount of K = mW

j admissible strategies for all m

ships in the set S

j, in the form of changes in their

courses

j and speeds Vj in order to avoid

collisions:

 

12 3

0, , , ...

1, 2, ...,

jji j j jj j

Ss s s s V



  



(4)

The Constraint-set C(s

w,sj) of the permissible

strategies result from the rules of the right of the

COLREGs sea route are shown in Figures 3 and 4.

Figure 3. Met j-th ship on the starboard side: the sets of

acceptable game strategies of own-ship S

w and j-th

encountered ship S

j (above), and hyperplane of collision-risk

j depending on the  own-ship course changes and the

encountered j-th ship 

j (below).

Figure 4. Met j-th ship on the port side: the sets of

acceptable game strategies of own-ship S

w and j-th

encountered ship S

j (above), and hyperplane of collision-risk

j depending on the  own-ship course changes and the

encountered j-th ship 

j (below).

3 TYPES OF OPTIMIZATION OF THE MULTI-STEP

MATRIX GAME

In most real transport and logistics processes, the

matrix game does not reach the saddle point and then

has no solution when using pure strategy in game

theory. Therefore, an approximate solution to the

game is the use of the mixed strategy chain as the

probability of using pure strategies (Ehrgott 2005,

Ehrgott & Gandibleux 2002).

First, the probability matrix for using pure

strategies is determined as shown in equation 5:











...







...



...



...



(5)

Then, the most probable strategy is the optimal

control used of the own-ship (Eshenauer et al. 1990,

Osborne 2004):

128







max

ww j

uup











(6)

The game ends after bringing the collision-risk of

each ship to the value of zero and reaching a certain

value of the final payment p

f, in the form of the final

deviation of the safe trajectory from its initial value.

3.1 The criterion of a non-co-operative matrix game

The algorithm of MMG_nc multi-step non-co-

operative matrix game uses the following

optimization criterion (Nisan et al. 2007, Straffin

2001):



min max

nc j





(7)

3.2 The criterion of the co-operative matrix game

The MMG_c algorithm of multi-step co-operative

matrix game uses the following optimization criterion

(Basar & Bernhard 2008, Wells 2013):



min min





(8)

3.3 The criterion of non-game control

The MNG algorithm of multi-step non-game control

uses the following optimization criterion:

min

ng j





(9)

The MMG_nc, MMG_c and MNG algorithms for

determining a safe own-ship trajectory in a collision

situation were developed using the linprog function

from the Matlab Optimization Toolbox package

(Breton & Szajowski 2010).

The method of entering the initial data for

calculations describing the navigational situation is

shown in Figure 5, and the form of calculations results

of the safe trajectory of the ship is illustrated in Figure

Figure 5. Algorithm window with initial data of the

navigational situation.

Figure 6. The algorithm window with the results of

calculations of the safe own-ship trajectory and own-ship

control by change of speed V or course .

4 COMPUTER SIMULATION OF GAME

CONTROL ALGORITHMS

The safe trajectories of own ship in the situation of 33

ships in the Kattegat Strait, in conditions of good and

restricted visibility of the sea, are determined

according to algorithms of multi-criteria optimization:

129

MMG_nc, MMG_c and MNG, and this are shown in

Figures 7-13.

Figure 7. The six-minute speed vectors of own ship and 33

encountered ships in a navigational situation in Kattegat

Strait.

Figure 8. A safe trajectory of own-ship in non-co-operative

matrix game, in conditions of good visibility in the sea, for

s = 1.0 nm, final payment pf = 1.88 nm (nautical mile).

Figure 9. A safe trajectory of own-ship in non-co-operative

matrix game, in conditions of restricted visibility of the sea,

for D

s = 2.6 nm, pf = 2.18 nm (nautical mile).

Figure 10. A safe trajectory of own-ship in co-

operative matrix game, in conditions of good visibility

in the sea, for D

s = 1.0 nm, pf = 0.57 nm (nautical mile).

130

Figure 11. A safe trajectory of own-ship in co-operative

matrix game, in conditions of restricted visibility of the sea,

for Ds = 2.6 nm, pf = 1.19 nm (nautical mile).

Figure 12. A safe trajectory of own-ship in non-game

control, in conditions of good visibility on the sea, for D

s =

2.6 nm, p

f = 0.69 nm (nautical mile).

Figure 13. A safe trajectory of own-ship in non-game

control, in conditions of restricted visibility on the sea, for

s = 2.6 nm, pf = 0.71 nm (nautical mile).

5 CONCLUSIONS

The use of a matrix game with collision-risk for the

synthesis of algorithms for computer-aided

navigating maneuvering decision makes it possible to

take into account the degree of indeterminacy of the

navigational situation caused by the imperfection of

the law of the sea route and the subjectivity of the

navigator making the maneuvering decision to avoid

a collision.

The multi-criteria approach to the task of

optimizing the safe control of the ship's movement

allows taking into account of both the non-co-

operative and co-operative game control and the

control of the non-target ships.

Obtained safe ship trajectories differ mainly in the

value of the final deviation from the set trajectory of

the movement.

REFERENCES

Basar, T. & Bernhard, P. 2008. H-Infinity optimal control

and related mini-max design problems: A dynamic

game approach. Berlin: Springer.

Bist, D.S. 2000. Safety and security at sea. Oxford-New

Delhi: Butter Heinemann.

Breton, M., & Szajowski, K. 2010. Advances in dynamic

games: theory, applications, and numerical methods for

differential and stochastic games. Boston: Birkhauser.

Ehrgott, M. 2005. Multicriterial optimization. Berlin:

Springer.

Ehrgott, M. & Gandibleux, X. 2002. Multiple criteria

optimization: state of the art annotated bibliographic

surveys. New York: Kluwer Academic Press.

Engwerda, J.C. 2005. LQ dynamic optimization and

differential games. New York: John Wiley & Sons.

131

Eshenauer, H., Koski, J., Osyczka, A. 1990. Multicriteria

design optimization: procedures and application. Berlin:

Springer-Verlag.

Isaacs, R. 1965. Differential games. New York: John Wiley &

Sons.

Kazimierski, W. & Stateczny. A. 2013. Fusion of Data from

AIS and Tracking Radar for the Needs of ECDIS, Proc. of

the Signal Processing Symp., Jachranka, Poland.

Kouemou, G. 2009. Radar technology. Chapter 4 by Józef

Lisowski: Sensitivity of safe game ship control on base

information from ARPA radar. Croatia, In-tech, 61-86.

Kun, G. 2001. Stabilizability, controllability, and optimal

strategies of linear and nonlinear dynamical games.

PhD. Thesis. Aachen: RWTH.

Lazarowska, A. 2017. A new deterministic approach in a

decision support system for ship’s trajectory planning.

Expert Systems with Applications, Vol. 71, Issue C: 469–

478.

Lebkowski, A. 2018. Design of an Autonomous Transport

System for Coastal Areas. TransNav, the International

Journal on Marine Navigation and Safety at Sea, Vol. 12,

No. 1: 117-124.

Lisowski, J. 2014. Optimization-supported decision-making

in the marine game environment. Solid State

Phenomena, Vol. 210: 215-222.

Lisowski, J. 2016. Analysis of methods of determining the

safe ship trajectory. TransNav, the International Journal

of Marine Navigation and Safety of Sea Transportation,

Vol. 10, No. 2:223-228.

Mesterton-Gibbons, M. 2001. An introduction to game

theoretic modeling. Providence: American Mathematical

Society.

Millington, I. & Funge, J. 2009. Artificial intelligence for

games. Amsterdam-Tokyo: Elsevier.

Miloh, T. 1974. Determination of critical manoeuvres for

collision avoidance using the theory of differential

games. Hamburg: Inst. Fur Schiffbau.

Modarres, M. 2006. Risk analysis in engineering. Boca

Raton: Taylor & Francis Group.

Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. 2007.

Algorithmic game theory. New York: Cambridge

University Press.

Olsder, G.J. & Walter, J.L. 1977. A differential game

approach to collision avoidance of ships. Proc. of the 8

IFIP Symp. on Optimization Techniques, Novosibirsk,

264-271.

Osborne, M.J. 2004. An introduction to game theory. New

York: Oxford University Press.

Perez, T. 2005. Ship motion control. London: Springer.

Polak, E., Lee. S., Bustany, I., Madhan, A. 2016. Method of

approximations and adaptive approximations for a class

of matrix games. Journal of Optimization Theory and

Applications, Vol. 170, No. 3: 876-899.

Straffin, P.D. 2001. Game theory and strategy. Warszawa:

Scholar.

Szlapczynski, R. & Szlapczynska, J. 2016. An analysis of

domain-based ship collision risk parameters, Ocean

Eng., Vol. 126: 47-56,

Tomera, M. 2012. Nonlinear Observers Design for

Multivariable Ship Motion Control, Polish Maritime

Research, Vol. 19, Special Issue 1: 50-56

Xu, Q. & Wang, N. 2014. A survey on ship collision risk

evaluation. Promet – Traffic & Transportation, Vol. 26,

No. 6: 475-486.

Wells, D. 2013. Games and mathematics. Cambridge:

Cambridge University Press.