# Optimal Route Planning for Maritime Autonomous Surface Ships Using a Nonlinear Model Predictive Control

## Article information

## Abstract

With the increase of interest in developing Maritime Autonomous Surface Ships (MASS), an optimal ship route planning is gradually gaining popularity as one of the important subsystems for autonomy of modern marine vessels. In the present paper, an optimal ship route planning model for MASS is proposed using a nonlinear MPC approach together with a nonlinear MMG model. Results drawn from this study demonstrated that the optimization problem for the ship route was successfully solved with satisfaction of the nonlinear dynamics of the ship and all constraints for the state and manipulated variables using the nonlinear MPC approach. Given that a route generation system capable of accounting for nonlinear dynamics of the ship and equality/inequality constraints is essential for achieving fully autonomous navigation at sea, it is expected that this paper will contribute to the field of autonomous vehicles by demonstrating the performance of the proposed optimal ship route planning model.

**Keywords:**maritime autonomous surface ships; route planning; optimization; model predictive control; nonlinear dynamics

## 1. Introduction

A ship's route should be determined before the start of a voyage with consideration given to a ship's maneuvering behavior as well as the critical factors on the route features. With the increase of interest in developing Maritime Autonomous Surface Ships (MASS), an optimal route planning is gradually gaining popularity as one of the important subsystems for the autonomy of modern marine vessels (Li et al, 2019). It should be mentioned that planning an optimal route is of great importance in order to achieve fully autonomous navigation at sea, which can contribute to ensuring safe and efficient autonomous navigation operations of ships.

For route planning optimization, it is imperative to ensure the safety of ship operations at sea when a ship follows a predefined route. The route planning that does not take into account the maneuvering performance of a ship can cause large deviations from the predefined route, resulting in navigational casualties such as grounding and collision. In other words, the route planning algorithm for MASS should take into account the accurate maneuvering performance of a ship, i.e., the complicated interactions between the hull, propeller, and rudder during its operation when generating a reference route. However, numerous past studies in the field of route planning for marine vehicles have been devoted to employing a simplified mathematical ship model in the assumption that vehicles use a constant velocity during their operations for simplicity. For example, Rhoads et al. (2010) dealt with the problem of steering a fixed-speed autonomous underwater vehicle to the desired target position in minimum time by solving a dynamic Hamilton Jacobi Bellman equation for the optimal “time-to-go” and related optimal feedback control law. The velocities of autonomous marine vehicles were maintained constant in Zeng et al. (2017), where a distributed shell-space decomposition for rendezvous route planning by means of a B-spline-based quantum particle swarm optimization technique. Due to changes in engine power and rudder deflection, it has been observed in real operations that marine vehicles experience continual variations in their velocities such as surge, sway and yaw velocities. Given this, this paper was motivated to take into account the nonlinear dynamic aspect of a maneuvering ship when performing route planning optimization by means of a nonlinear Model Predictive Control (MPC) technique.

MPC has its roots in optimal control, and its fundamental principle is to use a nonlinear dynamic model to forecast system behavior and optimize the forecast with the aim to make the best decision (Rawlings et al, 2017). When solving a route planning problem, MPC has the advantage of efficiently handling hard constraints for the input constraints and soft constraints for the output or state constraints. Sandeepkumar et al.(2022) claimed in their paper that “MPC owes its popularity to its constraint handling capabilities enabling maximum performance to be extracted when the system is pushed to the operational limits”.

The present study is devoted to the route planning optimization problem for marine vehicles, using a nonlinear MPC model combined with a Maneuvering Modelling Group (MMG) model. The complicated mutual interactions between the hull, propeller, and rudder during manoeuvres can be taken into account by adopting the MMG model for route optimization, consequently capable of accurately dealing with complex constraints.

## 2. Problem formulation

This section will present the problem of distance-optimal route planning of marine vehicles, with a detailed description of the mathematical ship model and MPC approach in the included sub-sections.

### 2.1 Route planning

Marine vehicles should be capable of following the predefined route based on the Estimated Time of Arrival (ETA), ensuring navigational safety at sea. Thus, a route planning procedure should impose constraints on states (e.g., kinematic parameters) or outputs (e.g., engine power or rudder angle) for safety and operational reasons, as depicted in Fig. 1.

### 2.2 Ship geometry and coordinate systems

In this study, the well-known benchmarking KVLCC2 (KRISO Very Large Crude Carrier 2) was adopted for the optimal ship route planning problem. Fig. 2 depicts the overview of the ship geometry, which is characterized by a traditional single rudder / single propeller configuration, and the principal particulars of the ship are listed in Table 1.

For the route planning problem for the ship, three right-handed coordinate frames were defined as displayed in Fig. 3: (1) Earth-fixed frame (*o _{e}* −

*x*), (2) Ship-fixed frame (

_{e}y_{e}z_{e}*o*−

_{s}*x*), and (3) Rudder-fixed frame (

_{s}y_{s}z_{s}*o*−

_{r}*x*).

_{r}y_{r}z_{r}### 2.3 Nonlinear state space model

The governing equations of rigid body motion (for 3 DoF) were used to resolve the nonlinear dynamics of the ship operating at sea, which can be expressed as follows (Yasukawa, H., & Yoshimura, Y.,2015):

*m*is the mass of body (unit:

*kg*)

*u*, *v*, *r* are the surge/sway/yaw velocities (units: *m/s*, *m/s*, and *deg/s*, respectively)

*u̇*, *v̇*, *ṙ* are the surge/sway/yaw accelerations (units: *m/s*^{2}, *m/s*^{2}, and *deg/s*^{2}, respectively)

*m _{x}*,

*m*are the added masses of

_{y}*x*axis direction and

*y*axis direction (unit:

*kg*)

*x _{G}* is the longitudinal coordinate of center of gravity of the ship (unit:

*m*)

*I _{ZG}* is the moment of inertia about the

*z*axis (unit:

*kg·m*

^{2})

*J _{Z}* is the added moment of inertia about the

*z*axis (unit:

*kg·m*

^{2})

*X*, *Y* are the surge/sway resultant forces acting on the ship (unit: *N*)

*N* is the yaw resultant moment acting on the ship (unit: *N·m*)

The hydrodynamic forces (*X*, *Y*) and moment (*N*) in Eq. (1) are decomposed into three components in the MMG model: the bare hull, rudder, and propeller.

*H*,

*R*,

*P*denote hull, rudder, and propeller, respectively.

*X*,

_{W}*Y*,

_{W}*N*mean the external forces and moment acting on the hull induced by waves. In this work, the nonlinear and linear MMG models were used for the validation study about the accuracy of the ship’s maneuvering performance. The hydrodynamic derivatives for the nonlinear maneuvering MMG model are expressed in Eq. (3), whereas the hydrodynamic derivatives for the linear MMG model are given in Eq. (4).

_{W}*X*,

_{u}*X*,

_{vv}*X*,

_{vr}*X*,

_{rr}*X*,

_{vvvv}*Y*,

_{v}*Y*,

_{r}*Y*,

_{vvv}*Y*,

_{vvr}*Y*,

_{vrr}*Y*,

_{rrr}*N*,

_{v}*N*,

_{r}*N*,

_{vvv}*N*,

_{vvr}*N*, and

_{vrr}*N*are called the hydrodynamic derivatives. For more details on the MMG model, reference can be made to Yasukawa, H., & Yoshimura, Y. (2015).

_{rrr}It has to be stated that the hydrodynamic coefficients, propeller thrust, rudder forces and moments for the KVLCC2 were determined from the captive model experiment reported in Yasukawa, H., & Yoshimura, Y. (2015). In addition, second-order wave loads for the KVLCC2 were determined from the circular motion tests reported in Jeon et al. (2021).

The numerical simulations of the turning, zigzag characteristics were carried out to ensure that the nonlinear MMG model accurately assessed the maneuvering behavior of the KVLCC2 (Fig. 4, 5, and 6). It was found that the linear MMG model could not estimate the maneuvering behaviors accurately due to the only consideration of the linear terms on the right-hand side of Eq. (3), as shown in the figures. Such considerations lowered the accuracy of the hydrodynamic forces and moment acting on the ship, demonstrating that the linear MMG model cannot accurately predict the complicated interaction between the hull, propeller, and rudder during maneuvers.

When using the nonlinear MMG model adopted in this work, the agreement is reasonable for the predicted ship trajectories and kinematic parameters during the maneuver.

Based on the aforementioned equations, the nonlinear dynamic system of the ship for the MPC can be given in state-space form as a set of continuous Ordinary Differential Equations (ODEs) consisting of the state (*x̄*) and manipulated inputs (*ū*) vector as follows (Sandeepkumar et al, 2022):

*x̄*= [

*u v r x y ψ*]

*is the state vector,*

^{T}*ū*= [

*n δ*]

*is the manipulated input vector.*

^{T}*x*and

*y*are the x and y position expressed with respect to the earth-fixed coordinate (unit: m),

*ψ*is the ship's heading angle (unit: degree),

*n*is the propeller rotational speed (unit: RPS),

*δ*is the rudder angle (unit: degree).

### 2.4 Nonlinear MPC

Nonlinear MPC is a high-fidelity tool for route planning problems as it solves an open-loop constrained nonlinear optimization problem taking into account the current system states. Improved accuracy in MPC's decision-making is made possible with the use of a nonlinear dynamic model, as conducted in this work.

The prediction horizon of interest, i.e., for all *t* ∈ [0,*T _{P}* ] (where

*T*is the horizon length), should be defined for the problem of optimal route planning, representing the time from the start to the end of the route planning. When the system dynamics are given in continuous time as reported in Eq. (3), a finite-horizon optimal route planning problem can be formulated as follows (Rawlings et al, 2017):

_{P}*x*(

_{f}*t*) and

*y*(

_{f}*t*) are the final position in the earth-fixed coordinate at a given time. As an equality constraint,

The optimal ship route planning problem in this work was solved by means of the fmincon function in the MATLAB optimization toolbox with the SQP (Sequential Quadratic Programming). The key advantage of the SQP for solving nonlinear optimization problems is that it can handle any degree of nonlinearity, including nonlinear constraints. It should be borne in mind that important parts of the numerical optimization algorithm include computing the gradient of the objective function, and the Jacobian of the constraints (Sandeepkumar et al, 2022). Since the analytic computation of derivatives can become cumbersome when dealing with large problems with many variables or constraints, the automatic differentiation algorithm (Griewank, A. and Walther, A., 2008) was applied to estimate the Jacobian matrices.

## 3. Results (Case study)

This section was organized to solve the route planning optimization problem for the KVLCC2 in accordance with the modelling setup described in Section 2, taking into account the MPC controller parameters (Table 2) and the imposed constraints (Table 3).

An iteration process for finding an optimum is required in the optimization toolbox solver. The solver begins at a given initial value *x*_{0} and then performs intermediate computations that result in a new point *x*_{1}. It then repeats the process in order to obtain successive approximations *x*_{2}, *x*_{3}, ⋯ of the local minimum. It should be highlighted that the number of iterations in the optimization computation depends on the solver's stopping criteria consisting of Step tolerance and Function tolerance. Step tolerance is a lower bound on the size of a step, indicating the norm of (*x _{i}* −

*x*

_{i}_{+ 1}), whereas Function tolerance is a lower bound on the change in the objective value during a step (|

*f*(

*x*) −

_{i}*f*(

*x*

_{i}_{+ 1})|). For the route planning optimization in this work, the iterations end if |

*x*−

_{i}*x*

_{i}_{+ 1}| < Step tolerance and |

*f*(

*x*) −

_{i}*f*(

*x*

_{i}_{+ 1})| < Function tolerance.

The imposed constraints on the state and manipulated input variables were determined to simply demonstrate the performance of the nonlinear MPC model proposed in this work for the optimal route planning problems. As reported in Table 3, the propeller rotational speed was constrained from −1RPS to 1.78RPS, and the rudder deflection was bounded from −35° to 35° based on the ship particulars. It should be noted that the surge velocity for the KVLCC2 was constrained between 0 and 3.5 m/s (6.8 knots) based on the assumption that the ship was operating in an area with a speed restriction of 3.5 m/s. The constraints of the parameters related to the ship velocities, propeller, and rudder characteristics shown in Table 3 were imposed in a realistic way based on the experimental results of the KVLCC2 (Kim et al, 2019). The results obtained for solving a class of nonlinear constrained route planning optimization problems using the nonlinear MPC approach are presented in Fig. 7 and Fig. 8. Five different cases for distance-optimal ship route planning problems were taken into consideration within this work; positions (−10LBP, −10LBP) and (0,0) in Fig. 7 indicate the initial and final positions of the ship, respectively. It should be noted that Case 4 was carried out in the regular head wave condition, while Case 5 was performed in the regular head sea together with the ahead current condition (0.5 knots). The effects of the current on the ship's performance can be solved within the hydrodynamic damping terms, considering the direction and speed of the current to be applied.

The ship should comply with all the imposed constraints reported in Table 3 while operating from its initial position to its final position in all cases. As clearly evidenced in the figures, the optimization problems were observed to be successfully solved by the MPC, satisfying the equality and inequality constraints. In other words, the ship route was generated with the consideration of the nonlinear dynamics of the system and all the constraints regarding the state (*x̄*) and manipulated (*ū*) variables.

## 4. Conclusions and discussion

In the present work, an optimal ship route planning model for autonomous marine navigation has been proposed by means of the nonlinear MPC approach together with the nonlinear MMG model.

Given the previous studies related to optimal ship route planning, the effectiveness of the applied controller is generally evaluated depending on whether the imposed constraints on the state (*x̄*) and manipulated (*ū*) variables satisfy equality and inequality conditions. In this regard, it can be argued that the effectiveness of the MPC controller adopted in this study is demonstrated by presenting that the optimal ship route was successfully generated with the satisfaction of the nonlinear dynamics of the ship and all the constraints for the state and manipulated variables.

It has to be stated that the comparison between the MPC controller and the PID controller in terms of optimal route planning is not feasible since the PID controller does not take into account the cost function. When considering another controller that can consider the cost function for comparison, it is thought that the optimal ship route varies depending on the applied cost function. Given this, the comparison between the MPC controller reported in this study and other controllers for optimal ship route planning was not a focus of this study.

Given that the ship route generation system capable of accounting for the nonlinear dynamics of the ship and equality/inequality constraints is essential for safe autonomous navigation, it is expected that this paper will contribute to the field of autonomous vehicles by demonstrating the performance of the proposed optimal ship route planning model. Proposed future work should incorporate the presence of different environmental loads, as these will have a noticeable effect on the ship route planning optimization problem for marine vehicles.

## Acknowledgements

This work was supported by the Development of Autonomous Ship Technology [grant number 20200615], funded by the Ministry of Oceans and Fisheries (MOF, Korea).