The multi-dimensional dynamic programming method is applied to the long-term route planning of an autonomous sailboat from Shanghai to Qingdao. The sailed voyage length out of the current position is adopted to be the third-dimensional state variable. The short-term route planning between the neighboring waypoints is defined as the control variable. A group of optimal routes with minimum voyage time can be obtained corresponding to different voyage length. The result shows that by adding the state variable dimension, more optional routes are kept in the final results, which is valuable for better decision support.
Since only a few variables can be considered in the planning process of A* algorithm, it is difficult to handle
complex environmental factors and constraints. United States Naval Academy selected Northern Route and
Southern Route as two feasible plans for “Spirit of Annapolis” transatlantic navigation based on the pilot charts,
and then compared the strengths and weaknesses of the two routes according to hurricanes, currents, sea ice,
wind fields, and seaports
The total length of the sailboat model is 1.5m. Based on the existing hull design scheme
Dynamic programming is an effective method to solve multi-stage decision problems. By establishing the recursive
relationship between two neighboring stages, the optimal decision at each stage can be obtained. The optimal
decision at each stage establishes the optimal decision sequence for the entire process
J ∗(→−X(k), k) =
k min {X αq(→−X(q), →−U(q − 1), q)} →−U(q−1),q=2,···,k q=2 =
min {αk(→−X(k), →−U(k − 1), k) + J ∗(→−X(k − 1), k − 1)} →−U(k−1)
J ∗(→−X(1), 1) = 0 k = 2, 3, · · · , N where k is the stage variable. →−X(q) is the state variable of stage k. →−U(q − 1) is the control variable which can make the sailboat transfer from state →−X(q − 1) at the stage (q − 1) to state →−X(q) at stage q. αq(→−X(q), →−U(q − 1), q) q=2 αq(→−X(q), →−U(q − 1), q) is the objective function at the current is the cost function from stage (q − 1) to q. Pk stage k. The control sequence →−U(q − 1) corresponding to the minimum objective function J ∗(→−X(k), k) is the best decision sequence.
The recursive relationship between J ∗(→−X(k), k) and J ∗(→−X(k − 1), k − 1) in the equation above reflects the multi-stage thinking of dynamic programming. From the minimum of J ∗(→−X(k − 1), k − 1) at stage (k − 1) and all cost function αk(→−X(k), →−U(k − 1), k), the optimal control variable →−U(k − 1) and the minimum objective function J ∗(→−X(k), k) at stage k can be obtained. One dimensional or multi-dimensional programming can be used depending on the dimension of the state variable →−X(q).
In this research, the stage variable is k = 1, 2, 3, · · · , 31. k=1 is in Shanghai and k=31 is in the destination Qingdao. In the state variable X(i, j, k), (i, k) represents the grid point shown in Figure3, and j is a state variable of the route length Li,k from the departure to the current waypoint (i, k). The route length Li,k is equally devided into 30 groups labelled with the state variable j by using the following rounding equation: j =
Li,k − Lk,min (Lk,max − Lk,min)/30 + 1 where Lk,min is the minimum route length of the great circle route from the departure to the current stage k, and Lk,max is the double value of Lk,min. After division of the route length by stete variable j, all the routing scheme from the departure to the current waypoint are divided into 30 groups and from each group one optimal route plan can be obtained. Obviously, the additional dimension of the state variable j provides more alternatives for decision support. The scheme is illustrated in Figure 4. The control variable U (i,, j,, k − 1) which makes the sailboat transfer from the state variable X(i,, j,, k − 1) at stage (k −1) to the state variable X(i, j, k) at stage k is actually the short-term routing scheme from the waypoint (i,, k − 1) to (i, k). In this paper, the straight path scheme with the maximum speed is used for downwind and beamwind sailing, and the tacking scheme with the maximum speed is used for sailing against wind. The cost function t(X(i, j, k), U (i,, j,, k − 1), k) is the sailing time from waypoint (i,, k − 1) to (i, k) under the control variable U (i,, j,, k − 1). The maximum speed when sailing downwind or beamwind is obtained according to polar diagram of sailboat speed and wind field. When sailing against wind the maximum speed is defined as CtackΔuπ/4 where Ctack is the cost coefficient of tacking and uπ/4 is the maximum speed when wind direction is π/4. Thus, the dynamic recurrence relation of the long-term route planning of the sailboat is expressed as below, and the detailed process of dynamic planning is shown in Figure 5.
Jp∗(X(i, p, k), k) = U(i,,j,m,ki−n1),j=p{t(X(i, j, k), →−U(i,, j,, k − 1), k) + Jj∗(→−X(i,, j,, k − 1), k − 1)} p = 1, 2, · · · , 30 i = 1, 2, · · · , 31
J1∗(X(16, 1, 1), 1) = 0 4 4.1
Steady Uniform Wind Field 3DDP was adopted in the route planning from Shanghai to Qingdao. The wind speed was 6m/s steadily and the wind direction was north, south, west and east respectively. As shown in Figure 6, a group of routes with the shortest time was obtained in different route length. In the cases of south, east and west wind, the total length of the route is positively correlated with the minimum voyage time. The route with the shortest length and sailing time is almost a straight line between the starting point and the destination. The minimum voyage time for those three cases is about 100 hours. With the total length increasing, the route with the minimum voyage time gradually moves away from the coastline. Obviously, by adding the total length of the route as a planning variable, the planning result provides more selections and plays a better role in decision support. In the case of north wind, the minimum voyage time is about 160 hours with a total route length of 750km, which is significantly longer than that of other three cases. The total length of the route is positively correlated with the minimum voyage time when the route length is over 750km. However, when the route length is less than 750km, the minimum voyage time increases significantly with the decreasing of route length. The short route less than 750km restricts the tacking operation to a smaller upwind angle which causes slower speed and longer sailing time. 4.2
As shown in Figure 7, the instantaneous wind field on May 20th, 2017 was adopted according to National Centers for Environmental Prediction. The maximum wind speed is about 10m/s. A group of alternative routes with minimum voyage time in different voyage length from Shanghai to Qingdao was obtained by using 3DDP method. The simulation result in Figure 8 is similar to that of steady north wind. The minimum voyage time is 150h corresponding to a total voyage length of 750km. But the route is close to the coastline and is risky of collision. Thus, the final sailing route could be selected from the other alternatives.
In this research, 3DDP is adopted to long-term route planning for an autonomous sailboat. Apart from the current position of the sailboat, the sailed voyage length is defined as the third state variable. Without that variable, only one optimal path is obtained from all the path schemes. However, in 3DDP method, all path schemes from the departure to the current point are divided into up to 30 groups according to the total length of the route. Each group can generate a planning result with minimum voyage time. 3DDP provides more alternatives for decision support.
When the sailboat sails downwind or beamwind, the total length of the route is positively correlated with the minimum voyage time. The route with the shortest length and sailing time is almost a straight path between the departure and the destination.
When the sailboat sails against wind, if the total length of the route is less than a certain critical value, the minimum sailing time will increase significantly with the total length of the route decreasing restricted by tacking operation.