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 ( - Distance of the Closest Point of Approach, - Time to the Closest Point of Approach) and also the assessment of the collision risk rj (Lisowski, 2001, 2008a).
The risk value is possible to define by referring the current situation of approach, described by parameters and , to the assumed evaluation of the situation as safe, determined by a safe distance of approach Ds and a safe time Ts – which are necessary to execute a collision avoiding manoeuvre with consideration of distance Dj to j-th met object - shown on Figure 4 (Lisowski, 2005b, 2008c):
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 or the ship's speed selected by the navigator as is shown on Figure 5 (Pasmurow & Zimoviev, 2005).
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:
where:- a set of the own ship strategies, - a set of the j-th ships strategies, - denotes course and trajectory stabilisation, - denotes the execution of the anti-collision manoeuvre in order to minimize the risk of collision, which in practice is achieved by satisfying following inequality:
where:- the smallest distance of approach of the own ship and the j-th encountered object,
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).- 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 control goal:
basic type of control – stabilization of course or trajectory:
avoidance of a collision by executing:
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).
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:
where:- dimensional vector of process state of own ship determined in time , - dimensional vector of the process state for the j-th ship, - ν0 dimensional control vector of the own ship, - νj dimensional control vector of the j-th ship.
The state equations of ship game control process take the following form:
The state variables are represented by the following values:- course of the own ship, - angular turning speed of the own ship, - speed of the own ship, - drift angle of the own ship, - rotational speed of the screw propeller of the own ship, - pitch of the adjustable propeller of the own ship, - distance to j-th ship, - bearing of the j-th ship, - course of the j-th ship, - angular turning speed of the j-th ship, - speed of the j-th ship,
While the control values are represented by:- rudder angle of the own ship, - rotational speed of the own ship screw propeller, - pitch of the adjustable propeller of the own ship, - rudder angle of the j-th ship, - rotational speed of the j-th ship screw propeller,
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 and , defined as the sets of acceptable strategies of the participants to the game towards one another:
are dependent, which means that the choice of steering uj by the j-th object changes the sets of acceptable strategies of other objects.
A set of acceptable strategies of the own ship when passing the j-th encountered object at a distance Ds - while observing the condition of the course and speed stability of the own ship and that of the encountered object at step k is static and comprised within a half-circle of a radius Vr (Fig. 11).
Area is determined by an inequality (Fig. 12):
The value is determined by using an appropriate logical function Zj characterising any particular recommendation referring to the right of way contained in COLREG Rules.
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 of the encountered j-th object relative to the own ship is determined by analogy:
The sing is determined analogically to .
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 , equivalent for the current position p(t) to the optimal positional steering , is determined in the following way:
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 during course manoeuvre or element during speed manoeuvre (Fig. 13).
The dynamic features of the ship during the course alteration by an angle is described in a simplified manner with the use of transfer function:
where:- manoeuvre delay time which is approximately equal to the time constant of the ship as a course control object, - gain coefficient the value of which results from the non-linear static characteristics of the rudder steering.
The course manoeuvre delay time:
Differential equation of the second order describing the ship's behaviour during the change of the speed by is approximated with the use of the first order inertia with a delay:
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 . The optimal steering of the own ship is calculated at each discrete stage of the ship's movement by applying Simplex method for solving the linear programming task.
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 includes the values of the collision risk rj determined on the basis of data obtained from the ARPA anti-collision system for the acceptable strategies of the own ship and acceptable strategies of any particular number of j encountered objects. The risk value is defined by equation (1). In a matrix game player I - own ship has a possibility to use pure various strategies, and player II - encountered ships has various pure strategies:
The constraints for the choice of a strategy result from the recommendations of the way priority at sea (Radzik, 2000). Constraints are limiting the selection of a strategy result from COLREG Rules. As most frequently the game does not have a saddle point, therefore the balance state is not guaranteed. In order to solve this problem we may use a dual linear programming.
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 and that for the j-th encountered object . By applying a principle of the dual linear programming for solving matrix games the optimal course of the own ship and that of the j-th object is obtained at a level of the smallest deviations from their initial values.
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,
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:
Let then represent a set of information from ARPA anti-collision system impaired by measurement and processing errors:
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:
Let then represents a set of information saddled errors of measurement and processing parameters:
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,- duration of one stage of the ship's trajectory,
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: and (Fig. 19).
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.