P. Abramowski et al. Síntesis Tecnológica. N° 1 (2004) 45-49
DOI:10.4206/sint.tecnol.2004.n1-08

FORMAL SOLUTION OF SHIP WEATHER ROUTING PROBLEM VIA PONTRYAGIN’S MAXIMUM PRINCIPLE

PRZEMYSLAW ABRAMOWSKI
TOMASZ ABRAMOWSKI
ZENON ZWIERZEWICZ

Maritime University of Szczecin, MSc, pabramowski@szczecin.home.pl, Waly Chrobrego 1/2, 70-500 Szczecin, Poland.
Technical University of Szczecin, PhD, tomasz.abramowski@ps.pl, Al.Piastow 41, 71-065 Szczecin, Poland.
Maritime University of Szczecin, Prof. Waly Chrobrego 1/2, 70-500 Szczecin, Poland.

Abstract

The paper presents a formulation of a general optimal control problem together with the main tool for finding its solutions - the Pontryagin’s maximum principle. Zermello’s problem of optimal ship routing in an area of drift currents is also outlined as an exemplary task of this class. A numerical solution for the case of vortex-type current field is presented and explained, and a short discussion of obtained results is given.

Keywords: Dynamic optimisation, optimal weather routing, Zermello’s navigational problem, Pontryagin’s maximum principle.

1. INTRODUCTION

The underlying paper presents a formulation of optimal control problem, Bryson and Ho(1969), Leitman(1966), together with the main tool for finding (deriving) its optimal solution, which is the Pontryagin’s maximum principle. Due to general formulation of the problem, as well as non-standard form of presented transversality conditions, Zwierzewicz (1993), to be satisfied by co-state vector on the boundary of target set, the two-point boundary value task ensuing here could be reduced to the standard, parametrised Cauchy’s initial value problem. This problem, in turn, is intuitively simple and easy to solve using a computer, thereby a simple shooting method can be applied for its numerical solution. In other words, we can generate a family of optimal trajectories backward in time, starting from the boundary of the target set. The associated problem of selecting the trajectory which connects with a given initial condition is now a relatively easy task. With the help of computer, and especially for low dimensional problems, such a trajectory can be located at once. For more complicated tasks, however, one can apply some of the well-known finite dimensional optimisation procedures.

The subsequent part discusses the effectiveness of so developed theory through solving of a specific optimal navigation problem, which is the Zermello’s navigational problem, Poppe (1984), Zwierzewicz (1993), as known in the calculus of variations. The task is to find an optimal ship route in a region influenced by environmental (external) factors affecting the ship motion (wind, waves, currents etc.). Such a problem is also referred to in the literature as an optimal routing problem, or ship weather routing. The sea conditions data (influence factors) that could be obtained from various weather data sources are aggregated here in the given velocity vector field assumed as a known.

A case of velocity field in form of a symmetrical vortex obtained by a full rotation of radius function is considered and solved further on, with the related time-minimum routes calculated using the computer program written in MATLAB.

2. GENERAL INDICATIONS

The main elements of a typical optimal control problem (o.c.p) are the following:

- state equations with initial conditions:

x= ƒ (x(t), u (t)); x(t₀) = x₀          (1)

where x ∈ Rⁿ ; u ∈ R^m

- cost functional

- target set:

L = {(t, x) : lⁱ (t, x) ≤ 0; i = 1,2,..., r}          (3)

where lⁱ are class C¹ scalar functions

- duration of the process (time of termination) :

t_f = inf {t ∈ R ⁺ : (t, x ( t)) ∈ ∂ L}         (4)

-control constraints:

u(t) ∈ U ⊂ R ^m control vector           (5)

The standard matrix-vector notation is used below. A single vector x is considered as a column-vector while x^T designates its transposition (row). By ƒ_x we denote a column-vector of partial derivatives in x, while ƒ is the scalar function or Jacoby’s matrix for the case where ƒ is a vector function.

2.1. Maximum Principle

The solution of the routing problem presented below is based on Pontryagin’s maximum principle whose adequate version can be put here as follows. If, in the o.c.p as formulated above, u*(t) and x*(t) are respectively the optimal control and the corresponding trajectory, then there exists a nontrivial (non-zero) co-state trajectory p(t) such that the following conditions are satisfied: state equations (1),

co-state equations:

with transversality conditions:

such that the hamiltonian function:

attain its maximum in u at u(t) = u*(t) i.e. the maximum principle holds:

for all t ∈ [t_o,t_f]

3. OPTIMAL ROUTING PROBLEM FORMULATION

Simplifying the routing problem, and assuming the currents field data to be a known, one can define it as follows. A ship whose movement is described by the equations below, must travel through the region of strong currents. The magnitude and direction of the currents are known as functions of position: V_cr= =[φ₁(x₁,x₂),φ₂(x₁,x₂)]^T, where (x₁,x₂) are rectangular coordinates and [φ₁,φ₂]^T are the velocity components of the current in the x₁ and x₂ directions, respectively. The magnitude of the ship's velocity relative to the water is V, a constant. The kinematical model of ship motion adopted here seems to be satisfactory when long distances are assumed. The state vector coordinates (x₁,x₂) represent the ship's position whereas the ship course ψ (denoted here by u) is interpreted as a control variable:

The objective of the ship starting from the point x₀=(x₁^o,x₂^o) is to reach the target set (e.g. the destination point x_f=(x₁^f,x₂^f) in minimal time, which implies that the performance functional takes here the form:

The effective solution of this problem in real time is a vital task for navigators to plan and optimise the sea routes in their everyday duties.

3.1. Problem solution

Now let us apply the conditions of sec.1 to solve the above formulated Zermello problem. The hamiltonian of the system is:

Co-state equations:

Target set:

Transversality conditions:

Maximising the hamiltonian H at the time t_ƒ we can obtain λ as well as the value u*(t_ƒ)

hence:

The values of p(t_ƒ) coordinate are:

Now starting from this final conditions and the target point x_ƒ, we can simultaneously stepwise integrate (backward in time) the state and co-state equations, maximising at each step the Hamiltonian:

Where on the basis of co-linearity conditions

we obtain optimal control

within the whole time interval [0,t_ƒ]

So, we have obtained a parametrical family of optimal controls which imply a corresponding family of ship motion optimal trajectories. Having obtained now the starting point of the process, the parameter α can be found by one of many existing numerical procedures for solving algebraic equations of single variable (e.g. the method of chords ). Note that the described method is effective not only for any current field but even for cases of the co-state equations depending on u, which is not considered here. In simple cases, however, the optimal control may be found fully analytically, Zwierzewicz (1990).

Now we specify these results for the numerical data. At the unit of length a nautical mile (nm) is adopted, while the speed is measured in knots.

3.2. Example

Case definition data.

1. Geometry parameters (normalised):

Route origination point = (-1,-1)
Target set = (0,0)
Ship’s speed V = 1

2. Current vector field

Current vector field is defined as a vertex created by full clockwise rotation of vertex profile function, which is based on radius from vertex centre. The function used here is

F = k • r • e^-r2                        (20)

where r is radius from vertex centre.

Relations

define a Cartesian coordinates (x^r₁,x^r₂) in relation to the vortex center.

Based on the function F, the current field vector components φ₁, φ₂ are defined as follows:

where:

The function value scale coefficient k has been set as 1.5, while r axis scale has been compressed 6 times to make the vortex fit inside the {0,0}, {-1,-1} square. The actual vertex profile thus obtained is shown in Fig.1.

Fig. 1. Vertex profile function F used for this case.

3. Cost functional is as per (11) (time-minimal).

Since Pontryagin’s maximum principle is the necessary (but not sufficient) condition for optimality, the trajectories found in this way form so-called family of extremals i.e. a family of solutions among which the candidates for optimality might in fact exist.

The family of extremal trajectories (extremals) has been calculated by backward integration of the system composed of state (10) and co-state equations (13) starting from final (0,0) and transversality conditions (17) and using each step the control found via (19). The two extremals that hit the initial conditions (-1,-1) era illustrated in Figure 2 and 3. To select the optimal one, a simple comparison of related “time to go” corresponding to each one suffices.

Fig. 2. Optimal trajectories (extremals) obtained for vertex centered in (-0.65, -0.35).

Figure 2 – in this position of the vortex the time T1 is obviously much shorter than T2 (the route is shorter and drift current is helping) so 1 is the optimal trajectory. The graphic function F (downscaled to fit) is shown in a position illustrating the clockwise rotation of the vertex.

Fig. 3. Optimal trajectories (extremals) obtained for vertex centered in (-0.35, -0.65).

Figure 3 – T1 is still slightly shorter in spite of going along a much longer route, which is probably due to a relatively high drift speed. (up to 65% of ship’s speed), which carries the ship forward when passing close to the center of the vortex.

In both cases presented above, the “downwind” vortex-accelerated trajectory proved to be superior, but it is intuitively quite obvious that at some point, with the vortex moved further aside and its “upwind” side providing the shorter path, the “upwind” trajectory is going to turn out as a better choice. In fact such results were also obtained by the authors. However, there is no general solution even for this simple model, as the locations of points having equal times both ways around the vortex are also dependant on the vortex speed profile and its relation to ship’s speed. Such points, when assumed to be starting points of the journey, form so-called dispersal line which divides the whole plane into two areas. The points located on the dispersal line have equal times along both routes around the vortex along their respective extremal trajectories, and both areas are defined by "better go upwind"/"better go downwind" criterion. Consequently, the dispersal line is never crossed by any optimal trajectory – those that cross it are extremals which have chosen a wrong way around the vortex.

4. CONCLUSIONS

In real life the situation is much more complex as, for example, the upwind courses are preferred for better stability of the ship in rough seas. Such factors, however, may be accounted for by using a more sophisticated quality criterion, or using a field of external influences which would account for factors such as sea state - not only the drift speed value. There is a lot of possibilities for further research in the field of ship optimal weather routing, and the authors firmly believe that the mathematical approach to this problem is the most promising in the long perspective.

REFERENCES

[1] M. Breitner, W. Grimm, H. Pesch, “Barrier trajectories of a realistic missile/target pursuit evasion game”, Lecture Notes in Control and Information Sciences, N^o 3, 156, pp. 48-57, 1991.

[2] A.E. Bryson, Y.C. Ho., Applied optimal control, Blaisdel Publ. Co. 1969.

[3] G. Leitman, An introduction to optimal control, McGraw-Hill, New York 1966.

[4] H. Poppe, “Beitarge zum Problem der optimalen Routung I“, Wissenschaftiche Beitrage der ICH fur Seefahrt Warnemunde-Wustrow, Rostock 11, 1984.

[5] B. Wisniewski, Problemy wyboru drogi morskiej statku, Wydawnictwo Morskie, Gdansk 1991.

[6] Z. Zwierzewicz, “Methods of mathematical control theory and their application to some optimization problems of modern marine navigation”, Maritime University of Szczecin, 1993.

[7] Z. Zwierzewicz, “Caratheadory’s Method of Equivalent problem in Optimal Control”, Zeszyty Naukowe WSM Szczecin N^o 39, 1990.