# A Novel Energy-Saving Route Planning Algorithm for Marine Vehicles
## 3 Methods
### Smoothing of Cubic B-Spline Curve  
The initial alter points obtained by the optimized ant colony will form many polylines, causing the ship to alter course frequently and increase energy consumption, so it is necessary to smooth the initial path formed by many polylines. This goal is achieved by designing a two-level smoothing strategy.  
[PERSON]'s algorithm is a classic one for drawing straight lines in graphics, and its principle is as follows. In a grid chart drawn by horizontal and vertical straight lines, connect the starting point and the destination, then calculate the intersection of this connection line and each vertical grid line or horizontal grid line in order, and finally determine the pixel that is closest to the intersection on the grid line. The pixels here can be seen as raster.  
The time of altering course at the waypoints will be reduced by the traditional first-level smoothing, but there are still discontinuities. To make the path meet with the kinematics of the ship, the cubic B-spline curve method is applied to perform a secondary smoothing to the path points.  
The B-spline curve makes up for the disadvantage of the Bezier curve in that it does not have local properties in the overall description, but it retains the advantages of the Bezier curve and solves the connection problem while representing complex shapes. Usinga spline composed of a third-order polynomial, the principle of the cubic B-spline method is to connect a set of control points, that is, the waypoints on the path, so the interval between the two control points has the form of a polynomial function.  
\[f_{k}(x)=P_{3k}(x-x_{k})^{3}+P_{2k}(x-x_{k})^{2}+P_{1k}(x-x_{k})+P_{0k} \tag{22}\]  
where \(k\) is the index of the control point. By giving the coordinate value of each control point, the coefficients of the polynomial \(P_{0k}\), \(P_{1k}\), \(P_{2k}\), and \(P_{3k}\) can be calculated via the following constraints.  
\[\left\{\begin{array}{l}f_{k}(x_{k})=y_{k}\\ f_{k}(x_{k+1})=y_{k+1}\\ f_{k-1}^{\prime}(x_{k})=f_{k}^{\prime}(x_{k})\\ f_{k-1}^{\prime\prime}(x_{k})=f_{k}^{\prime}(x_{k})\\ \end{array}\right. \tag{23}\]  
where the values of the matching equation of the cubic polynomial at both ends of the interval are \((x_{k},y_{k})\) and \((x_{k+1},y_{k+1})\). The cubic spline function has the same value for the first (velocity, i.e., \(f_{k-1}^{\prime}(x_{k})=f_{k}^{\prime}(x_{k})\) in the equation) and quadratic (acceleration, i.e., \(f_{k-1}^{\prime\prime}(x_{k})=f_{k}^{\prime\prime}(x_{k})\)) derivatives at each interval control point. In this way, the first derivative at the starting point is the initial velocity, and the first derivative at the end is equal to the final velocity. The quadratic derivative of the start and end points are zero, thus ensuring smoothness and continuity of the path.  
Traditional thoughts hold that the path point obtained by one-time smoothing is used as the control point of the cubic B-spline curve, which will cause the optimized path point to pass through the obstacle grid. In this paper, the number of control points is increased by implementing linear interpolation, so as to change the shape of the spline and prevent the optimized path from passing through the obstacle area.