1 Introduction

Unmanned surface vehicle (USV) is a type of vessel that navigates in water and it is controlled by intelligent algorithms or remote control. USVs are useful for offshore patrol and emergency rescue operations [1]. The primary objectives of route planning and collision avoidance (COLAV) algorithms for unmanned surface vessels are to optimize operations, increase travel safety, and demonstrate their utility in the real world. By providing algorithms that increase the independence level, it is believed that human error, fuel consumption, collision probability, and operating costs will be decreased [2]. One of the main challenges faced by USVs is safe navigation [3], which should be achieved without interference with path planning tasks. The importance of path planning for USV to achieve the defined purposes such as patrolling and rescue missions fast and securely becomes apparent. USV path planning is derived from robot route planning in the presence of obstacles (autonomous ground vehicle (AGV) and autonomous aerial vehicle (AAV)) [4]. In reference [5], a path planning system with a collision avoidance function has been implemented using deep reinforcement learning (DRL). References [6, 7] have addressed various controlling and path planning ways. USV path planning is similar to ship navigation [6,7,8].

To find the optimal path, the energy consumption, the shortest travel time, and the collision-free path should be examined together. Therefore, in this paper, a multi-objective cost function is proposed, which examines the effect of these factors on the path separately and scrutinizes the effect of variations of each factor on the other factors. The majority of collision avoidance studies have accepted the concept of a “safe area” as an area that is not accessible to other vessels. This area is typically circular in shape and its center is the instantaneous position of the obstacle. In the USV path planning, this circular-shaped area is not very commodious, especially when the vessel is moving with high speed and the risk of a forward-facing obstacle is far more than the possibility of collision between the stern and sides. For this reason, in this paper, the safety area of moving obstacles is considered to be elliptical according to their dimensions and speed so that it is closer to the real model. Without safety constraints, the USV cannot perform its mission or tasks in a realistic environment. Given the importance of the safety issue, this paper tries to optimize the safety issue. In addition, To optimize energy consumption and travel time, safety of the generated path for navigation would be acceptable.

The innovations of this article are as follows:

A multi-objective path planning optimization function, including path length, path smoothness, travel time, energy consumption and cost of collision with operational constraints has been defined. Accordingly, the optimal path is selected based on overall cost and mission. The penalty functions are defined to reduce the possibility of collision. USV stops along the path, as a result of which the cost of collision and energy consumption are reduced. A method is proposed to identify the points of convexity and contradiction of the path and illuminate them as possible, consequently the path smoothness and the possibility of reducing travel time and energy consumption increase. Two optimization methods have been proposed based on Ant Colony algorithm named ACOLS Out Teta and ACOLS Curve Path. Finally, the proposed methods have been tested through simulation under different conditions and the results are compared with other methods.

The rest of this paper is organized as follows. Section 2 presents a brief review of articles that consider path planning methods and use difference optimization algorithms. Section 3 introduces the problem and models the vehicle. Section 4 describes the fundamentals of the method, the cost functions and the penalties used in this paper. Section 5 introduces the proposed optimization algorithms, the ACOLS OUT TETA and the ACOLS Curve path in details. The proposed algorithms and methods are verified through simulations under different variations in Sect. 6. Section 7 concludes the principal works of this paper. Finally, the nomenclature Table 3 is in Appendix I.

2 Literature review

In recent years, many effective ways have been presented for global path planning. In reference [9], ACO for AUV path planning has been improved by constructing heuristic information using artificial potential concept. An improved ACO algorithm can create a safe distance between AUVs and obstacles. However, the generated yaw angle is extensive and may divert the vessel from the main path. The heterogeneous distribution of the primary pheromone and heuristic strategy with directional information in an ACO is provided by Zhang et al. for path planning of the omnidirectional mobile vehicle. Additionally, overlapping and updating strategy is defined in the pheromone updating process to avoid duplicate searches. These improvements increase time efficiency and simplicity of the algorithm and reduce the search space for an ant colony algorithm [10]. In Reference [11], a multi-colony ACO algorithm has been used to implement the UAV path planning system, in which N ACO work on a similar problem by redistributing, and the local information of each clone is shared with other colonies at specified intervals. The multi-colony ACO method can reduce the risk of being trapped in local optima, but the algorithm might have a prolonged interruption in the convergence process. The ACO algorithm has been modified in [12] to improve its convergence and search capability. The modified ACO algorithm is then used to solve the global path planning problem for the robot. The modifications are as follows: (1) the amount of pheromone is increased along the shortest path of each cycle, and (2) the rate of pheromone evaporation is dynamically adjusted in response to the changes in each iteration. In [13], the Position Tracking control method and artificial immune network algorithm (AINA) have been combined to solve the multi-robot formation path planning problem, in which the steering direction is determined by the AINA algorithm. The ACO algorithm has been used in [14] to generate a path that utilizes ocean energy and takes advantage of desired ocean currents to move and guide the Multi-modal underwater vehicle (MUV) while collecting ocean data and measurements. To solve problems of the typical ACO, including low convergence speed, possibility of getting trapped in local minimums and poor robustness, the authors of [15] have used the Hybrid quantum ACO (HQACO) method for AUV path planning and it has been shown that HQACO is faster than ACO and QACO. In this paper, QACO and ACO methods have been combined. The authors of [16] have used the ACO algorithm for AUV path planning in a high-risk environment. In [17], the ACO algorithm has been used to navigate a ground robot in a rugged environment with a bumpy road. The authors of [18] have provided online path planning for a mobile robot based on rapid exploring random trees (RRT) method. This method can generate collision-free paths, but the optimal route may connive in some cases. An algorithm based on machine learning has been presented in [19] for detecting moving obstacles. In [20], a system based on fuzzy logic has been used to avoid obstacles. It is worth noting that many of the studies conducted in the field of path planning, have described the path planning problem as a single-objective optimization function, which aims to find the shortest path, the most cost effective path (with minimum travel time or low energy consumption), the safest path and so on. In fact, the shortest path, the most economical path, and the collision-free path plays a vital role in the path planning problem. When it comes to optimal path planning, it is imperative that the shortest, most economical and safest path should be selected.

Obtaining the shortest path from the starting point to the endpoint is the primary goal of many engineering researches in real world. The authors of [21] have proposed the dynamics-constrained global–local (DGL) hybrid path planning scheme that is used to find shortest global path. The authors of [22] have proposed the shortest path problem as a single-objective linear programming function in a grid environment. In reference [23], the ACO algorithm has been used to find the shortest path according to fixed obstacles. In the shortest path planning problem, the simulation field is over-simplified, and little heed has been paid to other issues such as energy consumption, path smoothness and dynamic constraints of the robot. By moving forward in a smooth direction, rapid movements can be avoided, which reduces lifetime of the mechanical equipment [24, 25]. A smooth route navigation guarantees guidance, and control of a USV [24,25,26]. In most studies [27, 28], smooth path is expressed using a polynomial function, and the maneuverability of the vessel has not been considered. During navigation, reference points generated by the navigation system are connected linearly to guide and control the vessel. Choosing the smoothest path is a significant issue in the path planning problem. However, USV operating restrictions should be considered.

USV's economic path can be examined from two aspects, including the shortest travel time or the least energy consumption. Due to the increased cost and energy consumption associated with long-distance travel, one of the primary goals of the path planning system is to reduce travel time and energy consumption. When performing tasks like transportation and scientific research, economic paths are routes of interest for the ships such that travel time and energy consumption are reduced significantly [29,30,31]. Path planning with minimum energy consumption has been presented in [32, 33]. In reference [34], the GA and Voronoi diagrams are integrated to produce energy efficient path by considering sea currents. In [35], considering the time cost function along with the programming techniques and the sliding wave front expansion in terms of mathematical analysis, it is ensured that the least possible travel time is achieved in the presence of strong currents. The authors of [36] have used a reinforcement learning for path planning, aiming to minimize travel time but it has not considered movement and maneuverability constraints. In [37], ACO algorithm has been used to perform path planning for an AUV based on a bi-objective cost function of the shortest and collision-free path. In [38], the QPSO-based path planning algorithm has been used to generate optimal path for an AUV to long range operation in uncertain ocean environment. The aim of this article is to find an optimal route for AUV, using the maximum energy of ocean currents and the shortest time to reach the goal. Finally, they used Monte Carlo simulation to validate the performance of the proposed algorithm.

Generally, static and moving obstacles prevent USVs from safe navigation. In [27, 28], obstacles have been presented in circular and spherical forms in two- and three-dimensional spaces, and safety has been expressed as a limitation in the path planning function. The authors of [39] have proposed a collision-free path planning method for surface vessels, considering a certain amount of distance from obstacles as a safety index. The authors of [35] have used the ACO algorithm and actual sea traffic data to generate a collision-free path for vessels.

3 Problem statement

Consider a USV, aiming to find the optimal path with the path planning approach in the presence of static and dynamic obstacles. As mentioned before, there are three key elements in the path planning approach to find the optimal path, including the shortest travel time, the safe path and the optimal energy consumption. Therefore, the path planning system should be able to trace its current position, identify the static obstacles, and predict the course of dynamic obstacles so that it can plan the optimized path according to the mission and the defined objects. Also, one important element of path planning is the path’s curvature. Most vessels have maneuverability limitation on sharp angels. Therefore, the convexity and contradiction points of the path should be identified and illuminated as possible. Some restrictions are defined for USV. The USV yaw angle changes cannot be more than 22.5 degree in one step. The normal speed of USV is 5 m/s but in acceleration maneuver, the USV’s speed can increase to 7.5 m/s and in deceleration and stop maneuvers, speed reduces to 2.5 m/s and 0 m/s, respectively. Figure 1 illustrates the planar motion of the USV.

Fig. 1
figure 1

Schematic diagram of USV planar motion

Full size image

4 Cost optimization using ACO

4.1 Ant colony optimization algorithm

Ant colony optimization algorithm (ACO) is one of the evolutionary algorithms inspired by the natural behavior of ant colony looking for the shortest path between their nest and food [40]. Among advantages of ACO, positive feedback, ability to optimize and parallel work can be mentioned [41]. Since the process of finding food of the ants is similar to the routing process, path planning systems usually use this method to find the shortest path.

4.1.1 Pheromones updating

When ants seek for purveyance sources, they release a chemical substance, called the pheromone to attract other ants to the path that they have passed. The selection criterion for ants in choosing a path that depends on the power of the diffused pheromone in that direction. The higher the intensity of the pheromone, the greater the probability of choosing that path.

Generally, the pheromone is updated in two steps: in the first step, pheromones evaporate on all edges or points. λ is the parameter that is called the pheromone evaporation factor. If the evaporation coefficient is considered a small value, the old path of previous repetitions will remain more prominent, and the convergence rate will be reduced, and if the evaporation factor is assumed significant, the best path of the old repetitions will be eliminated faster, which will increase the convergence rate. In the second step, the pheromone should be diffused.

The number of ants is represent by Q. τij(t) is the pheromone trail intensity on points (i, j) at iteration t. After all the ants have completed the search in iteration t, the intensity of the pheromone trail is updated using the following equation:

$$\tau_{ij} \left( {t + 1} \right) = \left( {1 - \lambda } \right) \times \tau_{ij} \left( t \right) + \sum \Delta \tau_{ij} ,$$
(1)

where the evaporation of pheromone trail is represented by (1 − λ) and the change of pheromone trail intensity is shown by ∆τij(t), and calculated as

$$\Delta \tau_{ij} = \left\{ {\begin{array}{*{20}c} {Q/{\text{num}}} & {{\text{for}}\;{\text{the}}\;{\text{nodes}}\;{\text{of}}\;{\text{the}}\;{\text{bestants}}} \\ 0 & {{\text{otherwise}}} \\ \end{array} } \right..$$
(2)

4.1.2 Path selection

In the implementation of the ant colony algorithm, m is the number of artificial ants that generate the path in parallel. Each ant, placed on the points is selected circumstantially and the ant will select the first point (i), randomly. It is assumed that ant k is located at point (i), so, the probability law determines the point towards which the ant wants to move. In the first iteration, the amount of primary pheromone is the same for all paths; so, the selection probability for all paths is the same. Nevertheless, after each repetition of the algorithm, the selection probability of some paths increases due to the evaporation and release of pheromone on the paths and based on intensity of the pheromone and the heuristic information of the problem.

The equation below shows the probability of choosing a path for ant k from point i to the point j.

$$P_{ij}^{k} (t) = \frac{{\tau_{ij}^{\alpha } \times \eta_{ij}^{\beta } (t)}}{{\sum\limits_{l} {\tau_{il}^{\alpha } \times \eta_{il}^{\beta } (t)} }},\quad \quad l,j \in {\text{ok}}(i).$$
(3)

In the above formula, \({\eta }_{ij}\) shows the heuristic information, α represents the influence coefficient of pheromone, and β is the impact factor of the heuristic information. These two coefficients establish a balance between the heuristic information and the pheromone level.

4.2 Energy consumption

One of the intended goals is to optimize the vessel energy consumption, while moving from the starting point to the endpoint through solving a constrained optimization problem. The constraints represent the dynamic limitations of the vessel. So, at the beginning, a realistic model of energy consumption of the vessel is required, which is obtained using the following equation:

$$l_{pow} = IV + P_{b} ,$$
(4)

Pb represents the power consumption of the payload items such as computers and sensors on the vessel that have constant power utilization.

The DC electric motor equation is expressed as follows:

$$L_{a} \rho_{b} {\raise0.7ex\hbox{${\text{d}}$} \!\mathord{\left/ {\vphantom {{\text{d}} {{\text{dt}}}}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{${{\text{dt}}}$}} I + R_{a} I = V - K_{e} \dot{\theta },$$
(5)

where \({\rho }_{b}\) is propeller distance from the center of USV, \({R}_{a}\) is armature resistance, \(\dot{\theta }\) is propeller rotational velocity, \({K}_{e}\) is motor back EMF constant, I is motor current, V is motor armature voltage, \({K}_{t}\) is motor torque constant and \({L}_{a}\) is armature inductance.

In this paper, electrical equations of the motors are considered in a steady-state mode. Considering this assumption, the static equations of the motor can be rewritten as follows:

$$V = R_{a} I + K_{e} \dot{\theta }.$$
(6)

Also, the torque equation is considered as follows:

$$I = \tau /K_{t} ,$$
(7)

where \(\uptau\) is driving torque of motor.

By substituting Eqs. 13 and 14 in Eq. 12 and considering the rotational velocity equation:

$$\dot{\theta } = \frac{1}{{\rho_{p} }}\left( {u + \rho_{b} r} \right),$$
(8)

where \({\rho }_{p}\) is propeller radius and \(r\) is rotational velocity.

The instantaneous power equation is

$$L_{{{\text{pow}}}} \left( {u\left( t \right)} \right) = R_{a} \frac{{\tau^{2} }}{{K_{t}^{2} }} + \frac{{K_{e} }}{{K_{t} }}\left( {\frac{\tau }{{\rho_{w} }}\left( {u + \rho_{b} r} \right)} \right) + P_{b} ,$$
(9)

where u(t) is velocity along the x-axis.

4.3 Collision avoidance circumscription

Another requirement is to create paths with minimum possibility of collisions between USV with static and dynamic obstacles. Therefore, at time t, the vessel should not be located closer than the defined safety distance from other obstacles; hence, one constant (CCol) is characterized for dynamic obstacles, which presents the safety distance between the USV and dynamic obstacles. Another constant is presented, which is called Cobs and defines the collision avoidance constraint between USV and static obstacles.

$$C_{{{\text{Col}}}} = \frac{{\left( {x\left( t \right) - x_{i} \left( t \right)} \right)^{2} }}{{\left( {{\text{SD}} + {\text{SD}}_{i} } \right)^{2} }} + \frac{{\left( {y\left( t \right) - y_{i} \left( t \right)} \right)^{2} }}{{\left( {{\text{SD}} + {\text{SD}}_{i} } \right)^{2} }} - 1 \ge o$$
(10)

where i is the number of dynamic obstacles and SD is the safety distance domain of each vessel.

The collision avoidance constraint between USV and static obstacles can be formulated similarly.

$$C_{{{\text{obs}}}} \left( {x\left( t \right).o_{j} } \right) = \frac{{\left( {x\left( t \right) - x_{oj} } \right)^{2} }}{{\left( {R_{oj} + {\text{SD}}} \right)^{2} }} + \frac{{\left( {y\left( t \right) - y_{oj} } \right)^{2} }}{{\left( {R_{oj} + {\text{SD}}} \right)^{2} }} - 1 \ge o$$
(11)

where \(j\in \left\{1.\dots \dots . {N}_{o}\right\}\) and No and Ro represent the number and the radius of the static obstacles, respectively.

4.4 Vessel’s domain area

As noticed before, most researches in the field of path planning have adopted the concept of a “safe area”. The problem of last work is expressed (implementation of circular shape for ship domain) and a suggestion is outlined to solve this problem as described in the following.

The dimension of the vessel’s area is computed using the two following equations, called SDfore and SDstern which calculate fore and stern sections, respectively.

$${\text{SD}}_{{{\text{fore}}}} = \left\{ {\begin{array}{*{20}c} {r_{{{\text{fore}}}} } & {{\text{if}} r_{{{\text{fore}}}} \ge r_{\min } } \\ {r_{\min } } & {{\text{otherwise}}} \\ \end{array} } \right.,$$
(12)
$$r_{{{\text{fore}}}} = \left\{ {\begin{array}{*{20}c} {V \times t} & {{\text{if}} V \times t < {\text{Dislimit}}} \\ {2 \times {\text{Dislimit}} - \left( {v \times t} \right)} & {{\text{otherwise}}} \\ \end{array} } \right.,$$
(13)
$${\text{SD}}_{{{\text{stern}}}} = \left\{ {\begin{array}{*{20}c} {{\text{velocity}} \times {\text{time}}} & {{\text{if}} V \times t < {\text{Dislimit}}} \\ {r_{\min } } & {{\text{otherwise}}} \\ \end{array} } \right.,$$
(14)
$${\text{Total}} {\text{SD}} = {\text{SD}}_{{{\text{fore}}}} + {\text{SD}}_{{{\text{stern}}}} ,$$
(15)

where \({r}_{\mathrm{min}}\) is the minimum distance that must be maintained between two vessels, Dislimit is the maximum permitted distance at the sides and heels of the vessel and t is the sampling time.

One item considered in the cost function, is to calculate the collision probability. Thus, in this paper, four oval-shaped areas are defined for the USV:

  • The red zone: the probability of collision is 1, that is all obstacles are prohibited from entering this area because the collision between USV and obstacles is inevitable.

  • The blue zone: the probability of collision is 0.5e−4, that is the USV can pay the collision probability and pursue its direction without any obligation to re-route.

  • The green zone: the probability of collision is 0.25e−4.

  • Finally, the last area is the white zone. The probability of collision in this zone is zero, that is all vessels and obstacles can move in this area freely.

4.5 Coefficient of smoothness

Due to the dynamic constraints of the USV, a route with least amount of maneuvering should be selected. videlicet, the optimal route is a path with a smaller angle of inclination. Therefore, a path smoothness coefficient is added to the objective function, so that the selected path is as smooth as possible.

$${\text{Delta}} {\text{Teta}} = \frac{1}{45}\mathop \sum \limits_{i = 2}^{n} \left| {\theta_{i} - \theta_{i - 1} } \right|,$$
(16)

where n is the total number of steps and \({\theta }_{i}\) is the vessel angle in step i.

4.6 Total cost function

Given that the defined cost functions are not on an identical scale, the normalization coefficients are added to regulate them on the same datum (or foundation). Finally, the multi-objective cost function is defined as follows:

$${\text{CF}} = \, W_{1} S_{1} F_{1} + \, W_{2} S_{2} F_{2} + \, W_{3} S_{3} F_{3} + \, W_{4} S_{4} F_{4} ,$$
(17)

where

W1 → W4 are the weight impact coefficients. These coefficients are valued according to the defined mission objectives. For example, the coefficient W1 in the cost function is more notable if the optimum energy consumption is chosen as the target in the defined mission. Of course, the value of W depends on several factors, such as vehicle energy consumption, energy costs (electricity, fossil fuels, solar cells, etc.), and vehicle models. It is evident that if value of the coefficient is significant, influence of the cost function on the optimization problem would be more significant.

S1 → S4 The correction factors or normalization of the objective functions to put them on the same datum.

$${\text{F}}_{{1}} = {\text{ Energy}} ; {\text{F}}_{{2}} = {\text{ Time}} ; {\text{F}}_{{3}} = {\text{ Collision}} ; {\text{F}}_{{4}} = {\text{ Delta Teta}}$$

Given that valued numbers of F3 and F4 are always between 0 and 1, they do not need any datum conversion and have used a constant numerical coefficient instead of their normalization coefficient. The calculated normalization coefficient keeps the value of each objective between 0 and 1. However, the normalization coefficients of the energy and time functions are expressed as follows:

\({S}_{1}=\frac{1}{2{l}_{\mathrm{pow}}}\) normalization coefficient of energy function,

\({S}_{2}=\frac{1}{\frac{2\mathrm{Step}}{{V}_{0}}}\) normalization coefficient of time.

4.7 Penalty functions

As previously stated, the primary purpose of this paper is to provide an optimal path planning according to the defined cost function. To make the problem (or simulation) conditions similar to real situations and provide more practical freedom to USV, other functions called penalty functions are defined as follows:

4.7.1 Penalty of collision

Given the variable of climate of sea environment and the fact that this paper divides the robot's safe margin into four areas with different odds of incidence (red, blue, green and white), a penalty function is defined to determine the collision probability in each area, till the collision probability reaches zero:

$${\text{Penalty}}_{{{\text{Colision}}}} = \mathop \sum \limits_{{{\text{Level}} 1}} P_{i} C_{i} ,$$
(18)

where \({P}_{i}\) is the probability of collision and Ci is time that spent in the treatment zone.

4.7.2 Penalty of stop

According to COLREG rules, the robot should perform four maneuvers to prevent collisions: head on, overtaking, and crossing from port and starboard. But in this paper, we consider three more maneuver to prevent collision: accelerate, decelerate and stop. One of the most crucial cost functions defined in the total cost function is the energy consumption function; given that if a complete stop occurs on the path, the robot needs to spend much energy to re-start the movement and reach the previous speed. A penalty function is described below for the time that the USV spends in the stop mode. Thus, the total of these times will be assumed as an additional cost and added to the total cost function.

$$\begin{gathered} {\text{Penalty}}_{{{\text{Stop}}}} = \mathop \sum \limits_{t = 1}^{T} {\text{Time}}\,{\text{in}}\,{\text{Stop}} \hfill \\ {\text{Time}}\,{\text{in}}\,{\text{Stop}}\left( {{\text{TiS}}} \right) = \left\{ {\begin{array}{*{20}c} {0 {\text{USV}}\,{\text{is}}\,{\text{moving}}\,{\text{at}}\,{\text{time}} t} \\ {1 {\text{USV}}\,{\text{has}}\,{\text{been}}\,{\text{Stop}}\,{\text{at}}\,{\text{time }}t} \\ \end{array} } \right.. \hfill \\ \end{gathered}$$
(19)

According to the aforementioned discussion, the total penalty function is expressed as follows:

$${\text{Total}}\,{\text{Penalty}} = W_{{{\text{Colision}}}}^{{ \mathop \sum \limits_{{{\text{Level}} 1}} P_{i} C_{i} }} + W_{{{\text{Stop}}}}^{{\sum\nolimits_{t = 1}^{T} {{\text{Time}} {\text{in}} {\text{Stop}}} }} .$$
(20)

4.8 Total objective function

Given the total cost function and the total penalty function, the objective function is presented as follows:

$${\text{OF}} = \min \left( {{\text{CF}} + {\text{Total}}\,{\text{Penalty}}} \right).$$

The initial ACO algorithm that has been implemented in this paper to perform global path planning and optimize the proposed objective function is shown below:

figure a

5 The proposed local search optimizations

The path planning method can be categorized into two groups: (1) global search path planning and (2) local search path planning. In the global search approach, the robot is fully aware of navigational environment conditions; therefore, it can reach the desired target by a predetermined path. However, in local search path planning, the robot has partial knowledge about the environment. In unknown environments, the global path planning method is less effective than the local search path planning method. In general, in the path planning optimization problems, random paths are more used at the beginning of the algorithm. Given this, the global search is implemented at first, and the local search is required when the process has reached its end. In the local search combination method based on the ACO algorithm, the population in each iteration is divided into two collections. The number of superior ants in each iteration is considered equal to nQ, the first part of the population consists of nPop-nQ × nBest solutions, and the second part contains nQ × nBest solutions; where nPop is the total population of the algorithm and nBest is the number of solutions created in the neighborhood of each superior ant’s solution, nQ. The first part is purely performed in accordance with the rules of the global search ACO, while the second part is done by the proposed local search methods based on the best solutions found by the superior ants (nQ). For each selected ant from the nQ set, the number of nBest paths is generated in the neighborhood of the selected ant’s path from the global path planning. If nBest is calculated to be zero (nBest = 0), the proposed ACO-LS algorithm becomes the proposed ACO algorithm.

In this paper, three methods are presented for the ACO-LS algorithm, which are called Ant Colony Optimization Local Search (ACOLS) Out Teta (ACOLS Out Teta), ACOLS Curve Path and ACOLS O/C, which is a combination of the previous two algorithms.

5.1 Ant colony optimization local search (ACOLS) out Teta algorithm

In the proposed local search method, to create a path in the neighborhood of any selected ants, the interval of local search is first determined randomly path by the length of ∆X. Then, in the whole possible span of the ant’s path, with the length ΔX, the total ∆θ of the steps is calculated from the initial point to the target point, and the range that has the largest ∆θ from the target point is selected for local improvement.

In the ACOLS Out Teta algorithm, the selected ant’s path is divided into two parts called part1 (from the initial point to p1) and part2 (from p1 to target point). Here, part1 is copied exactly from the path of the chosen ant given by global path planning, and part 2 is created using the proposed local search method in the neighborhood of the selected ant’s path from p1 to the target point.

Local search from p1 to the target point is done step by step in the grid network. Each ant in each step will select a point as the next point on its path from the current point i. The probability of choosing a path for ant k from point i to point j is calculated using the equation below:

$$P_{ij}^{k} \left( t \right) = \frac{{D_{ij}^{{\alpha_{LS} }} \times \eta_{ij}^{{\beta_{LS} }} \left( t \right)}}{{\mathop \sum \nolimits_{l} D_{il}^{{\alpha_{LS} }} \times \eta_{il}^{{\beta_{LS} }} \left( t \right)}}.\quad \quad l.j \in {\text{ok}}\left( i \right).$$
(21)

In the above formula, the coefficient α shows effect of the distance from the closest obstacle, and β represents the effect of the heuristic information (inverted distance to the target). D is the distance from the nearest obstacle, and η is calculated according to the ACO algorithm to determine the distance from the target.

5.2 Ant colony optimization local search curve path

The main goal of the proposed method is to eliminate the curves of the path according to the main objective functions (Collision probability, Energy consumption, and Travel time) of the problem. So, the angular differences of the total path (start point to target point) should be calculated and the path with the smallest ∆θ should be selected. This paper uses this method to find the convexity and contradiction points of the path, and then tries to modify them using the ACO rules.

In this optimization method, as in the previous local search approaches, three paths from the best paths generated by ACO are selected. Then, the difference between the angles of the current step and the next step and the difference between the previous one and the first step are calculated. Regarding the ACO algorithm that is selected with 16 grids, and the large number of steps, the small curvatures are ignored. In the 16th grade, the maximum ∆θ of each step is about 22.5 degrees. To do this, the current point is compared with three previous steps and three subsequent steps (because of ignoring small curvatures and preventing reduction of the computation speed), and if ∆θ of the three subsequent steps and the three previous steps are greater than or equal to 22.5 degrees, then the point is a convexity or contradiction point.

Now, for optimization approaches, starting and ending points of the convexity or contradiction are selected, which are named p1 and p2, respectively. By applying the ACO rules and the new condition, \(\mathrm{max }{\theta }_{i}\le 22.5\), it is tried to remove the curves to achieve a smoother path.

$$\max \theta_{i} = \left[ {\left| {{\text{Avg}}\left( {\theta_{i: + 3i} } \right) - {\text{Avg}}\left( {\theta_{i: - 3i} } \right)} \right|} \right],$$
(22)
$${\text{if}}\,\max \theta_{i} \ge 22.5 \to \theta_{i} {\text{is}} \,{\text{Convex}}\, {\text{or}}\, {\text{concave}} \,{\text{point}}{.}$$
(23)

6 Simulation

To verify the proposed algorithms’ effectiveness and integrity, numerical simulations were run on the renowned ship model CyberShip II [42], which is a 1:70 scale replica of a supply ship operated by the Marine Cybernetics Laboratory at the Norwegian University of Science and Technology. The primary parameters of CyberShip II are summarized in [42].

In this section, the proposed methods, ACOLS Out Teta, ACOLS Curve Path and ACOLS O/C are simulated and the four main parameters, including energy consumption, travel time, collision probability and the length of the path obtained from these methods are compared with those of PSO and ACO. It should be noted that to complete validation of the proposed methods, they are tested in many repetitions with various populations and different parameters.

Simulations have been performed using a computer with the following configuration: CPU Intel Core i7 6700 HQ- RAM 16 GB DDR4, Hard Disk 128 SSD.

6.1 Numerical simulation

The first workspace is implemented by exerting the following parameters:

The initial speed of the USV is 5 m/s, the USV’s initial angle with respect to the starting point is 0°, the number of static and moving obstacles is designated as 9 and 4, respectively. The parameters of the algorithm are presented in terms of grid number 16, number of populations is 30, Lambda = 0.5, Q = 0.5, the initial pheromone value is 0.5, number of best-selected ants for local optimization is 3, initial strength of the heuristic information is 1, the final value of beta is 2. In divergent scenarios, the mission objectives are different. As a result of changing goals, the importance of coefficients such as energy consumption, time-traveling, etc. may also be interchanged. In this paper, the scenario is defined as USV traveling the planned path with minimum probability of collision and practicable energy consumption at a reasonable time. In this paper, W is assumed [0.3 0.2 1 0.1] and Wstop is 0.01.

The algorithm’s path is displayed individually. Figure 2 illustrates the path created using the standard ACO algorithm. Figure 3 illustrates the ACOLS Out Teta path creation process, considering the vessel’s direction of motion, its future location, and any moving obstacles. As previously stated, the ACOLS Out Teta algorithm combines two path planning methods: global and local search. At the initial stage, the path is generated using global technology, then the neighborhood of selected ants (local technology) is explored and the optimal path to the next point is chosen based on the cost function. As illustrated in Fig. 3, the ACOLS Out Teta algorithm offers a new direction that is distinct from the ACO reference path. As a result of this improvement, the penalty, travel time, energy consumption, and other constraints have been reduced. The ACO-LS Curve path algorithm is illustrated in Fig. 4. As illustrated in Fig. 4, the ACO-LS Curve path algorithm eliminates the majority of path curves (by calculating the path angle and taking the restriction into account) and returns a path with minimum curves. Furthermore, Fig. 5 illustrates the path taken by the PSO algorithm in conjunction with the movement paths of dynamic obstacles.

Fig. 2
figure 2

The path traversed by the ACO algorithm with the movement paths of dynamic obstacles

Full size image
Fig. 3
figure 3

The path traversed by the ACO-LS Out Teta algorithm with the movement paths of dynamic obstacles

Full size image
Fig. 4
figure 4

The path traversed by the ACO-LS Curve Path algorithm with the movement paths of dynamic obstacles

Full size image
Fig. 5
figure 5

The path traversed by the PSO algorithm with the movement paths of dynamic obstacles

Full size image

Figure 6 illustrates the path obtained using the ACOLS O/C hybrid algorithm (which is a combination of two algorithms: ACOLS Out Teta and ACOLS Curve Path). Although this method has a slightly lower smoothness coefficient than ACOLS Out Teta, other cost function constraints such as energy consumption, travel time, and path lengths have been improved.

Fig. 6
figure 6

The path traversed by the ACO-LS O/C algorithm with the movement paths of dynamic obstacles

Full size image

Figure 7 illustrates all the paths generated by various algorithms. As illustrated in Fig. 7, the proposed methods generally outperformed the ACO and PSO methods.

Fig. 7
figure 7

The path traversed by all algorithms

Full size image

The simulation results are shown in Table 1. The objective cost function, energy consumption, travel time, total collision probability (Pi Ci), smoothness coefficient (Delta Teta), and run time of each algorithm used to generate the path are all compared in this table. As shown in the table, the proposed algorithms outperform the standard ACO and PSO algorithms. For example, the ACOLS O/C reduced energy consumption, travel time, and objective cost function by 20%, 3.68%, and 7.4%, respectively.

Table 1 Comparison of objective functions values using different algorithms in workspace 1
Full size table

For more verification of the proposed methods, another simulation has been conducted with different environmental conditions and variables. The simulation results are presented in Table 2.

Table 2 Comparison of objective functions values using different algorithms in workspace 2
Full size table

7 Conclusions

This paper presented three multi-objective optimization methods for a USV path planning system based on the ACO algorithm. These methods are referred to as ACOLS Out Teta, ACOLS Curve Path, and ACOLS O/C. At the ACOLS Out Teta method, all neighborhood selected ants are checked, the total ∆θ of steps from the initial point to the target point is calculated, and the largest ∆θ is chosen. As a result, sharp angles are avoided and rapid maneuvers are avoided. The ACOLS Curve Path attempts to eliminate as many curves as possible from the path based on collision probability, energy consumption, and travel time. This method calculates the angles of all feasible paths and selects the one with the smallest ∆θ. Additionally, the ACOLS Out Teta and the ACOLS Curve Path are combined to generate the final algorithms. This hybrid algorithm considers the constraints imposed by the previous two algorithms to generate an optimal path.

Energy consumption, travel time, path smoothness, and collision probability are used to define the multi-objective function. Additionally, penalty functions are defined to make the circumstances more realistic. To begin, the presented ACO performs global path planning in this paper. Then, using the three proposed local search optimization methods, the objective function is further optimized and a smoother path is created. Finally, the algorithms presented are evaluated under a variety of simulation conditions. The simulation results demonstrate that the proposed algorithms performed admirably well at optimizing.