Coefficients of basic game model equations.
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 (Engwerda, 2005; Nowak & Szajowski, 2005), and also in the control under uncertainty conditions (Nisan et al., 2007). 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 ships and imprecise nature of the recommendations concerning the right of way contained in International Regulations for Preventing Collision at Sea (COLREG) (Cockcroft & Lameijer, 2006). The problem of determining safe strategies is still an urgent issue as a result of an ever increasing traffic of ships 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 duties (Bist, 2000; Gluver & Olsen, 1998). 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. A necessity to consider simultaneously the strategies of the encountered ships and the dynamic properties of the ships as control objects is a good reason for the application of the differential game model - often called the dynamic game (Osborne, 2004; Straffin, 2001).
2. Safe ship control
2.1. Integrated of navigation
The control of the ship’s movement may be treated as a multilevel problem shown on Figure 1, which results from the division of entire ship control system, into clearly determined subsystems which are ascribed appropriate layers of control (Lisowski, 2007a), (Fig. 1).
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 2002).
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.
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 (Cymbal et al., 2007; Lisowski, 2005a, 2007b).
2.2. ARPA anti-collision radar system of 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 (Bole et al., 2006; Cahill, 2002), (Fig. 2).
The ARPA system enables to track automatically at least 20 encountered j objects as is shown on Figure 3, determination of their movement parameters (speed Vj, course ψj) and elements of approach to the own ship (
The risk value is possible to define by referring the current situation of approach, described by parameters
The weight coefficients k1 and k2 are depended on the state visibility at sea, dynamic length Ld and dynamic beam Bd of the ship, kind of water region and in practice are equal:
2.3. ARPA anti-collision radar system of manoeuvre simulation
The functional scope of a standard ARPA system ends with the simulation of the manoeuvre altering the course
2.4. Computer support of navigator manoeuvring decision
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 (Fig. 6). This generates an option within the ARPA anti-collision system or a training simulator (Lisowski, 2008a).
3. Game control in marine navigation
3.1. Processes of game ship control
Assuming that the dynamic movement of the ships in time occurs under the influence of the appropriate sets of control:
Ds - safe approach distance in the prevailing conditions depends on the visibility conditions at sea, the COLREG Rules and ship dynamics,
Dj - current distance to the j-th ship taken from the ARPA anti-collision system (Fig. 2).
In the adopted describing symbols we can discriminate the following type of steering ship in order to achieve a determined control goal:
basic type of control – stabilization of course or trajectory:
avoidance of a collision by executing:
own ship's manoeuvres:
manoeuvres of the j-th ship:
encounter of the ships:
situations of a unilateral dynamic game:
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, 2001).
chasing situations which refer to a typical conflicting dynamic game:
3.2. Basic model of dynamic game ship control
The most general description of the own ship passing the j number of other encountered ships is the model of a differential game of j number of moving control objects (Fig. 7).
The properties of control process are described by the state equation:
The state equations of ship game control process take the following form:
The state variables are represented by the following values:
While the control values are represented by:
|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 10 a 11||s -1 s -1||- 0.200 - 0.100|
|a 11+j||s -1||- 5 ·10 -2|
|a 12+j||s -1||- 4 ·10 -3|
|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 encountered ships the base game model is represented by i=86 state variables of process control.
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 Ds in compliance with COLREG Rules, generally in the following form:
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 8 (Lisowski et al., 2000).
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 ship as a player with j-th ship is the minimization of her goal function (10) in the form of the payments – the integral payment and the final one.
The integral payment represents loss of way by the ship while passing the encountered ships and the final payment determines the final risk of collision rj(tk) relative to the j-th ship and the final deviation of the ship d(tk) from the reference trajectory (Fig. 9).
Generally two types of the steering goals are taken into consideration - programmed steering u0(t) and positional steering u0[x0(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 dynamics and the dynamic of the j-th encountered ship and their movement kinematics lead to approximated models: multi-stage positional game, multi-step matrix game, fuzzy matrix game, fuzzy dynamic programming, dynamic programming with neural state constraints, linear programming (LaValle, 2006; Lisowski, 2004).
4. Algorithms of safe game ship control
4.1. Multi-stage positional game trajectory POSTRAJ
The general model of dynamic game is simplified to the multi-stage positional game of j participants not co-operating among them, (Fig. 10).
State variables and control values are represented by:
The essence of the positional game is to subordinate the strategies of the own ship to the current positions p(tk) 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:
The system generates its steering at the moment tk on the basis of data received from the ARPA anti-collision system pertaining to the positions of the encountered objects:
It is assumed, according to the general concept of a multi-stage positional game, that at each discrete moment of time tk the own ship knows the positions of the objects.
The constraints for the state co-ordinates:
are navigational constraints, while steering constraints:
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
are dependent, which means that the choice of steering uj by the j-th object changes the sets of acceptable strategies of other objects.
The form of function Zj depends of the interpretation of the above recommendations for the purpose to use them in the steering algorithm, when:
Interpretation of the COLREG Rules in the form of appropriate manoeuvring diagrams developed by A.G. Corbet, S.H. Hollingdale, E.S. Calvert and K.D. Jones enables to formulate a certain logical function Zj as a semantic interpretation of legal regulations for manoeuvring.
Each particular type of the situation involving the approach of the ships is assigned the logical variable value equal to one or zero:
– encounter of the ship from bow or from any other direction,
– approaching or moving away of the ship,
– passing the ship astern or ahead,
– approaching of the ship from the bow or from the stern,
– approaching of the ship from the starboard or port side.
By minimizing logical function Zj by using a method of the Karnaugh's Tables the following is obtained:
The resultant area of acceptable manoeuvres for m objects:
A set for acceptable strategies
Taking into consideration of navigational constraints – shoal and shore line, presents additional constraints of the set of acceptable strategies:
where: l – the closest point of intersection for the straight lines approximating the shore line (Cichuta & Dalecki, 2000).
The optimal steering of the own ship
sets of acceptable strategies
are determined for the encountered objects relative to the own ship and initial sets of acceptable strategies of the own ship relative to each one of the encountered objects,
a pair of vectors
and relative to each j-th object is determined and then the optimal positional strategy for the own ship from the condition:
refers to the continuous function of the own ship's steering goal which characterises the ship's distance at the moment t0 to the closest point of turn Lk on the assumed voyage route (Fig. 3).
In practice, the realization of the optimal trajectory of the own ship is achieved by determining the ship's course and speed, which would ensure the smallest loss of way for a safe passing of the encountered objects, at a distance which is not smaller than the assumed value Ds, always with respect to the ship's dynamics in the form of the advance time to the manoeuvre tm, with element
The dynamic features of the ship during the course alteration by an angle
The course manoeuvre delay time:
Differential equation of the second order describing the ship's behaviour during the change of the speed by
ToV - time of delay equal approximately to the time constant for the propulsion system: main engine - propeller shaft – screw propeller,
TV - the time constant of the ship's hull and the mass of the accompanying water.
The speed manoeuvre delay time is as follows:
The smallest loss of way is achieved for the maximum projection of the speed vector maximum of the own ship on the direction of the assumed course
At each one stage tk of the measured position p(tk) optimal steering problem is solved according to the game control principle (27) (Fig. 14).
By using function lp – linear programming from Optimization Toolbox of the MATLAB software POSTRAJ algorithm was developed to determine a safe game trajectory of a ship in a collision situation (Łebkowski, 2001).
4.2. Multi-step matrix game trajectory RISKTRAJ
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 (Fig. 15).
The state and steering variables are represented by the following values:
The game matrix R
The constraints for the choice of a strategy
In a dual problem player I aims to minimize the risk of collision, while player II aims to maximize the collision risk. The components of the mixed strategy express the distribution of the probability of using by the players their pure strategies. As a result for the goal control function in the form:
probability matrix P of applying each one of the particular pure strategies is obtained:
The solution for the control problem is the strategy representing the highest probability:
The safe trajectory of the own ship is treated as a sequence of successive changes in time of her course and speed. A safe passing distance is determined for the prevailing visibility conditions at sea Ds, advance time to the manoeuvre tm described by equations (30) or (32) and the duration of one stage of the trajectory ∆tk as a calculation step. At each one step the most dangerous object relative to the value of the collision risk rj is determined. Then, on the basis of semantic interpretation of the COLREG Rules, the direction of the own ship's turn relative to the most dangerous object is selected.
A collision risk matrix R is determined for the acceptable strategies of the own ship
Figure 16 shows an example of possible strategies of the own ship and those of the encountered object while, Figure 17 presents the hyper surface of the collision risk for these values of the strategy.
If, at a given step, there is no solution at the own ship's speed V, then the calculations are repeated for a speed decreased by 25%, until the game has been solved. The calculations are repeated step by step until the moment when all elements of the matrix R are equal to zero and the own ship, after having passed encountered objects, returns to her initial course and speed.
By using function lp – linear programming from Optimization Toolbox of the MATLAB software RISKTRAJ algorithm was developed to determine a safe game trajectory of a ship in a collision situation (Cichuta & Dalecki, 2000).
5. Sensitivity of game ship control
5.1. Definition of sensitivity
The investigation of sensitivity of game control fetch for sensitivity analysis of the game final payment (10) measured with the relative final deviation of d(t k )=d k safe game trajectory from the reference trajectory, as sensitivity of the quality first-order (Wierzbicki, 1977). Taking into consideration the practical application of the game control algorithm for the own ship in a collision situation it is recommended to perform the analysis of sensitivity of a safe control with regard to the accuracy degree of the information received from the anti-collision ARPA radar system on the current approach situation, from one side and also with regard to the changes in kinematical and dynamic parameters of the control process.
Admissible average errors, that can be contributed by sensors of anti-collision system can have following values for:
bearing: ±0,22 ,
form of cluster: ±0,05 ,
form of impulse: ±20 m,
margin of antenna drive: ±0,5 ,
sampling of bearing: ±0,01 ,
sampling of distance: ±0,01 nm,
gyrocompas: ±0,5 ,
log: ±0,5 kn,
GPS: ±15 m.
The sum of all errors, influent on picturing of the navigational situation, cannot exceed for absolute values ±5% or for angular values ±3 .
5.2. Sensitivity of control to inaccuracy of information from ARPA radar
Let X0,j represent such a set of state process control information on the navigational situation that:
Relative measure of sensitivity of the final payment in the game sinf as a final deviation of the ship's safe trajectory dk from the reference trajectory will be:
5.3. Sensitivity of control to process control parameters alterations
Let X param represents a set of parameters of the state process control:
Relative measure of sensitivity of the final payment in the game as a final deflection of the ship's safe trajectory dk from the assumed trajectory will be:
tm - advance time of the manoeuvre with respect to the dynamic properties of the own ship,
Ds – safe distance,
V - reduction of the own ship's speed for a deflection from the course greater than 30o.
5.4. Determination of safe game trajectories
Computer simulation of POSTRAJ and RISKTRAJ algorithms, as a computer software supporting the navigator decision, were carried out on an example of a real navigational situation of passing j=16 encountered ships. The situation was registered in Kattegat Strait on board r/v HORYZONT II, a research and training vessel of the Gdynia Maritime University, on the radar screen of the ARPA anti-collision system Raytheon.
The POSGAME algorithm represents the ship game trajectories determined according to the control index in the form (27) (Fig. 18).
The RISKTRAJ algorithm was developed for strategies:
5.5. Characteristics of control sensitivity in real navigational situation at sea
Figure 20 represents sensitivity characteristics which were obtained through a computer simulation of the game control POSTRAJ and RISKTRAJ algorithms in the Matlab/Simulink software for the alterations of the values X0,j and Xparam within 5% or 3 .
The application of simplified model of the dynamic game of the process to the synthesis of the optimal control allows the determination of the own ship safe trajectory in situations of passing a greater number of the encountered ships as a certain sequence of the course and speed manoeuvres. The developed RISKTRAJ algorithm takes also into consideration the Rules of the COLREG Rules and the advance time of the manoeuvre approximating the ship's dynamic properties and evaluates the final deviation of the real trajectory from the reference value.
The sensitivity of the final game payment:
is least relative to the sampling period of the trajectory 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 admissible strategies.
The considered control algorithm is, in a certain sense, formal model of the thinking process of a navigator conducting a ship and making manoeuvring decisions. Therefore they may be applied in the construction of both appropriate training simulators at the maritime training centre and also for various options of the basic module of the ARPA anti-collision radar system.