Research on Global Ship Path Planning Method Based on Improved Ant Colony Algorithm

To solve the global path planning problem of the ship in the static and dynamic environment, we propose an improved ant colony algorithm to plan the ship’s navigation path. We use the artificial potential field method to compute the force direction of the ship at the initial iteration stage. The attraction potential field function is modified to improve the iteration efficiency of the hybrid ant colony algorithm. We design the pseudo-random state transition rule and improve the convergence of the hybrid algorithm by strengthening the selection of good paths. When updating the pheromone, we consider the path’s length, safety, and smoothness to plan a safer navigation path. The simulation results show that the improved ant colony algorithm has a faster convergence speed than the original ant colony algorithm. The optimal solution quality is higher, which can realize global ship path planning in static and dynamic environments.

SECTION I. Introduction

In Recent years, ships are gradually developing toward intelligence and autonomy. As the basis for realizing ship intelligence, path planning has become a research hotspot in academia. Ship path planning refers to a path from the starting port to the destination port without the risk of collision in the current environment. The planned path should consider not only the economy and practicability of the route but also meet the constraints of ship collisions. The common method is to plan the global path for the static environment information and plan the dynamic local path for the uncertain environmental factors to make the planned path reach an ideal state.

Currently, the commonly used global path planning methods include the ant colony algorithm, Dijkstra algorithm, neural network based approach and genetic algorithm. The commonly used local path planning methods include the artificial potential field method, case based learning method, behavior decomposition method. The performance of the path planning algorithm directly affects the safety and efficiency of ship navigation.

In the navigation field, scholars applied various methods to the path planning of ships. Literature [1] proposes a path planning model for inland ships based on the safety potential field theory. The obstacles in the navigation environment are classified with different potential field functions and the optimal path is obtained by the minimum navigation risk points. Literature [2] proposed an improved rapidly random tree algorithm for ship path planning in complex navigation environments of inland waterways. Literature [3] proposed an improved ant colony optimization algorithm with fuzzy logic to solve the local path planning problem of dynamic obstacle avoidance in the complex environment. Literature [4] proposed a ship collision avoidance path planning method based on a heuristic algorithm, using stochastic schemata exploiter and genetic algorithm to optimize the path for ship collision avoidance. In addition to the above mainstream path planning algorithms, the linear programming method is used for ship path planning [5], [6]. This type of method is flexible enough to handle different constraints. However, it faces expensive computational costs in high-dimensional space.

As one of the most commonly used meta-heuristic algorithms [7], [8], the ant colony algorithm has achieved good results in path planning problems, but there are still some defects [9], [10]. First, the algorithm easily falls into the local optimum, making it difficult to jump out independently. Second, the initial pheromone concentration distribution method and pheromone update rules are not targeted, and unnecessary exploration reduces the algorithm’s convergence.

Scholars proposed various solutions for the two main problems of the ant colony algorithm. Literature [11] introduced the corner function in the traditional ant colony algorithm to reduce the number of inflection points on the path and combines the bidirectional search strategy to address its tendency to fall into local optima. Aiming at the problem of ship path planning and tracking control, literature [12] improved the pheromone update strategy of the ant colony algorithm based on the artificial potential field method. Literature [13], [14] designed a distance heuristic function in the ant colony algorithm and improved the state transition rules to increase the convergence speed of the algorithm. Literature [15] combines the crossover and mutation operations of the genetic algorithm to improve the solution quality of the ant colony algorithm. Literature [16] proposed a path planning method for ship navigation based on an improved neural network to increase path safety. Literature [17] combines the artificial potential field method with the ant colony algorithm, which solves the defect that the traditional artificial potential field method can not consider the interference of the external navigation environment. For the particularity of navigation in the ice area, literature [18] proposed an improved ant colony algorithm. They established a multi-objective programming model which considers the distance of path and operation complexity in navigation and ice avoidance and conducted experimental verification based on electronic charts. Literature [19] added the influence of the worst ant colony to the ant colony algorithm and modified the pheromone update mechanism to improve the convergence speed of path planning. Literature [20] proposed a method to build an extensive data-driven framework that automatically generates ship planning routes under different sailing conditions. Literature [21] proposed a hybrid multi-standard ship path planning method based on improved particle swarm optimization and genetic algorithm, which can optimize fuel consumption and voyage time.

Based on the above research background, the current ship path planning algorithms still have the problems, such as poor planning ability in complex environments [11], [18], unsafe path [19], defects in algorithm [22], [23]. Therefore, we use heuristic and fusion strategies to improve the ant colony algorithm according to the task requirements of ship path planning. In the initial iteration stage of the ant colony algorithm, we use the artificial potential field method to compute the ship’s motion direction. The attraction potential field function is modified to improve the iteration efficiency of the algorithm. In addition, we design a pseudo-random state transition rule to prevent the ant colony algorithm from falling into the local optimum prematurely, which can improve the algorithm’s convergence by strengthening the path with higher quality. The length, safety, and smoothness constraint functions are also integrated into the pheromone update rules to ensure the safety of the ship’s navigation path. Our contributions are summarized as follows:

1. We use heuristic and fusion strategies to improve the ant colony algorithm, and the planned path considers the path length, path security, and path smoothness.

2. We compare our method with the ant colony optimization algorithm and other improved ant colony algorithms in the simulation environment under various scenarios.

SECTION II. Hybrid Ant Colony Algorithm

A. Basic Ant Colony Algorithm

1) Basic Principles

The basic idea of the ant colony algorithm comes from the foraging process of ants in nature. When ants are looking for food, they release pheromones which can be detected by other ants within a specific range and affect their movement direction. The pheromones on the path gradually accumulate and also volatilize over time. Therefore, the more the number of ants, the higher concentration of pheromone per unit of time on the shorter path, affecting subsequent ants’ path selection. The positive feedback mechanism causes more ants to travel the shortest path between the nest and the food.

2) Mathematical Model of Ant Colony Algorithm

The ant colony algorithm calculates the probability of path selection through the distance heuristic function and pheromone concentration. First, assume that the number of ants in the ant colony system is $m$ , and the pheromone values between any two path points in the feasible domain are the same. At time $n$ , the formula for calculating the probability of ant $l=1,2,\ldots, m$ choosing any path point $j$ from current path point $i$ is as follows: $$\begin{align*} Q_{ij}^{l}(n)= \begin{cases} \frac {\left [{I_{ij}(n)}\right]^{\kappa }*\left [{H_{ij}(n)}\right]^{\lambda }}{\sum _{s\in D_{l}}\left [{I_{is}(n)}\right]^{\kappa }*\left [{H_{is}(n)}\right]^{\lambda }}, &\quad s\in D_{l} \\ 0, &\quad s\notin D_{l}, \end{cases} \tag{1}\end{align*}$$ where $Q_{ij}^{l}$ is the probability that the ant $l$ choose the path point $j$ from the path point $i$ , and $\kappa$ , $\lambda$ denote the information heuristic factor and the expected value heuristic factor. $I_{is}$ is the pheromone value between the path points $i$ and $j$ , $H_{is}$ is the distance heuristic function, $D_{l}$ is the set of path points that path point $i$ can choose at the next moment.

Assuming that the coordinates of the path points $i$ and $j$ are $(x_{i},y_{i})$ and $(x_{j},y_{j})$ , respectively. The heuristic function in the transition probability formula (1) equal to the reciprocal value of the Euclidean distance between the path points $i$ and $j$ $$\begin{equation*} H_{ij}(n)=\frac {1}{\sqrt {\left ({x_{i}-x_{j}}\right)^{2}+\left ({y_{i}-y_{j}}\right)^{2}}}. \tag{2}\end{equation*}$$

According to equation (2), the larger the value of the Euclidean distance, the smaller the heuristic information value of the two path points, and vice versa. To ensure that the residual pheromone concentration on the path is not too high, which can unduly affect the path selection of follow-up ants, we devise a reasonable pheromone volatilization and update mechanism. The pheromone between path points $i$ and $j$ is updated according to the following formula: $$\begin{align*} \begin{cases} \Delta I_{ij}(n) = \sum _{l=1}^{m}\Delta I_{ij}^{l}(n) \\ I_{ij}(n+1) = \left ({1-\delta }\right)I_{ij}(n)+\Delta I_{ij}(n), \end{cases} \tag{3}\end{align*}$$ where $\delta \in [{0,1}]$ is the pheromone volatilization coefficient, $\Delta I_{ij}(n)$ represents the increase of pheromone on the path $(i,j)$ at time $n$ , and $\Delta I_{ij}^{l}(0) = 0$ . $\Delta I_{ij}^{l}(n)$ is the pheromone released by the ant $l$ when passing through the path $(i,j)$ at time $n$ : $$\begin{equation*} \Delta I_{ij}^{l}(n) = \frac {C}{W_{l}},\tag{4}\end{equation*}$$ where $C$ is the constant pheromone intensity, and $W_{l}$ is the length of path $(i,j)$ in the current iteration.

B. Improvement of Hybrid Ant Colony Algorithm

As one of the most commonly used heuristic algorithms, the ant colony algorithm achieved good results in path planning, scheduling optimization, and network routing allocation, but it still has some problems. First, the positive feedback mechanism of the ant colony algorithm causes the algorithm to fall into a local optimum in some cases, which is challenging to jump out autonomously. Second, the uniform distribution of the initial pheromone and the pheromone update rules leads to unnecessary path exploration and reduces the algorithm’s convergence.

1) Improved Artificial Potential Field Method

When planning a local path, the artificial potential field method has the characteristics of initial solid guidance, convenient calculation, and strong robustness. Therefore, we introduce the artificial potential field method to improve the initial iteration speed of the ant colony algorithm. However, the artificial potential field method has two main problems. First, if the repulsion force is greater than the target attraction force when the obstacle is near the destination, the ship may not reach the destination. Second, it may happen that the repulsive force and the attraction force completely cancel each other out, causing the ship to fall into the local optimum. The flaw of the artificial potential field method is shown in Fig. 1.

Fig. 1.

The flaw of artificial potential field. $F_{r}$ represents the total repulsive force of the obstacles and $F_{a}$ denotes the attraction force of the destination.

Since the attraction potential field function is proportional to the square of the distance $G$ from the ship to the destination, the attraction force tends to infinity when $G$ is large. This can increase the risk of collision between the ship and the obstacle. To avoid collision accidents between the ship and the obstacle, we set the influence boundary line $R$ of the attraction potential field. When $G\leq R$ , the value of the attraction potential field is proportional to the square of $G$ . When $G > R$ , the value of the attraction potential field is proportional to $G$ , which can reduce the influence range of the attraction potential field. The improvement of the attraction potential field function is as follows: $$\begin{align*} U_{a}= \begin{cases} \frac {1}{2}K_{a} G^{2}, &\quad G\leq R \\ R K_{a} G, &\quad G > R, \end{cases} \tag{5}\end{align*}$$ where $K_{a}$ is the attraction potential field coefficient.

In addition, to solve the problem that the ship cannot reach the destination due to the repulsive force value being greater than the gravitational force value, we employ a modified repulsive force potential field function. In this paper, we introduce the relative distance between the ship and the target point in the original repulsion function, which can ensure that the target point is at the global minimum position in the entire potential field. The modified repulsive potential field function is as follows: $$\begin{align*} U_{r}= \begin{cases} \frac {1}{2}K_{r} \left [{\frac {1}{E}-\frac {1}{E_{0}}}\right]^{2} G^{2}, &\quad E\leq E_{0} \\ 0, &\quad E > E_{0}, \end{cases} \tag{6}\end{align*}$$ where $K_{r}$ is the repulsive potential field coefficient. $E$ is the distance between the ship and the obstacle, and $E_{0}$ is the influence range of the repulsive potential field of the obstacle.

2) Pseudo-Random State Selection

The traditional ant colony algorithm uses the product of the pheromone concentration in the path and the heuristic information function as the selection probability of the roulette wheel, also called biased exploration. This selection pattern only focuses on the search for new paths and often ignores the current excellent paths, which increases the time complexity of the algorithm and reduces the search speed.

To solve this problem, we introduce the random number $r$ and fixed parameters $r_{0}$ to improve the selection probability of the traditional ant colony algorithm. When $r \leq r_{0}$ , we take the product of the heuristic information function and the pheromone concentration as the evaluation value and choose the path with the largest value, which can strengthen the selection of the current excellent path. When $r > r_{0}$ , we choose the roulette wheel strategy of the basic ant colony algorithm as the selection probability, i.e., exploring new paths. The improvement of state selection probability balances the development of the current path and the exploration of the new path. This can reduce the extra time overhead of exploring the new path and avoid falling into local optimum prematurely. The improved probability formula is as follows: $$\begin{align*} Q_{ij}^{l}(n)= \begin{cases} \mathrm {max} \left \{{ \left [{I_{ij}(n)}\right]^{\kappa }*\left [{H_{ij}(n)}\right]^{\lambda } }\right \}, &\quad r \leq r_{0} \\ \begin{cases} \frac {\left [{I_{ij}(n)}\right]^{\kappa }*\left [{H_{ij}(n)}\right]^{\lambda }}{\sum _{s\in D_{l}}\left [{I_{is}(n)}\right]^{\kappa }*\left [{H_{is}(n)}\right]^{\lambda }} \\ 0, &\quad s\notin D_{l} \end{cases} &\quad r > r_{0}, \end{cases} \tag{7}\end{align*}$$ where $r \in [{0,1}]$ is the random number and $r_{0} \in [{0,1}]$ is the fixed parameters. In our algorithm, $r_{0}$ is an empirical parameter usually determined by previous experience and repeated experiments. The parameter $r_{0}$ means the relative importance between developing the currently chosen path and exploring the new paths. When $r_{0}$ is small, it is easier for the algorithm to explore new paths. On the contrary, the algorithm prefers the nodes connected by short edges and a large number of pheromones, that is, the excellent paths.

3) Improved Pheromone Update Rules

The traditional ant colony algorithm only considers the path length when updating the pheromone. However, in addition to the length of the path, the safety and smoothness of the path should also be considered in the ship path planning problem. The path’s safety directly affects whether the planned path is practical, and the smoothness directly affects whether the path meets the requirements of ship dynamics. To ensure the safety and economy of the planned path, we add the path’s length, safety, and smoothness goal constraints to the pheromone update rule. The modified formula of the pheromone update is as follows: $$\begin{align*} \begin{cases} \Delta I_{ij}^{l}(n) = \frac {C}{W_{l}}\\ \omega = \omega _{1} F_{l} + \omega _{2} F_{s} + \omega _{3} F_{w} \end{cases}\tag{8}\end{align*}$$ where $\omega _{1}, \omega _{2}, \omega _{3}$ are the weighted coefficient of the constraint function. $F_{l}, F_{s}, F_{w}$ denote the constraint function of path’s length, safety and smoothness, respectively. The formula of the constraint function are as follows: $$\begin{align*} \begin{cases} F_{l} = \sum _{i=1}^{t-1}d\left ({i,i+1}\right) \\ F_{s} = \sum _{i=1}^{t-1}S_{i,i+1} \\ F_{w} = \sum _{i=1}^{t-2}\left |{ \theta \left ({i+1,i+1}\right) - \theta \left ({i,i+1}\right) }\right | \end{cases}\tag{9}\end{align*}$$ where $t$ is the number of path points. $d(i,i+1)$ denotes the distance from path point $i$ to $i+1$ . And $S(i,i+1)$ is the safety degree between the path point $i$ and $i+1$ . $\theta (i,i+1)$ is steering angle from path point $i$ to $i+1$ . The calculation formula is as follows: $$\begin{align*} S_{i,i+1}=&\begin{cases} 1, &\quad S_{i,i+1}> S_{DA}\left ({i,i+1}\right) \\ 0.5, &\quad S_{DA}\left ({i,i+1}\right)/2 \leq S_{i,i+1} \leq S_{DA}\left ({i,i+1}\right) \\ 0.1, &\quad S_{i,i+1} < S_{DA}\left ({i,i+1}\right)/2. \end{cases} \tag{10}\\ \theta \left ({i,i+1}\right)=&\begin{cases} \frac {y_{i+1}-y_{i}}{x_{i+1}-x_{i}}, &\quad x_{i+1} \neq x_{i} \\ \frac {\pi }{2}, &\quad x_{i+1} = x_{i} \end{cases} \tag{11}\end{align*}$$ where $S_{DA}(i,i+1)$ is the safe encounter distance of ship between path point $i$ and $i+1$ .

SECTION III. Implementation of Hybrid Ant Colony Algorithm

A. Static Hybrid Ant Colony Algorithm

The core steps of the static hybrid ant colony algorithm (SHACA) mainly include environment setting, parameter initialization, pheromone update, and path result output. The specific implementation process is introduced as follows:

• Step 1:

  Use the grid to discretize the ship’s navigation environment, and set the position of starting point, destination and obstacle. Establish the conversion relationship between the coordinate systems of the navigation environment and the ship;

• Step 2:

  Set initial values for the parameters, such as the number of ants $m$ , the coefficient of pheromone volatilization $\delta$ , the initial intensity of pheromone $Q$ , the attraction potential field coefficient $K_{a}$ , and the artificial potential field influence coefficient $R$ .

• Step 3:

  Construct and initialize the taboo table of the improved ant colony algorithm.

• Step 4:

  Calculate the pheromone concentration of each path point according to formula (8).

• Step 5:

  Compute the total force acting on the ship according to formula (5), calculate the transition probability of the current position according to formula (6) to determine the position at the next step, and add the position to the taboo list.

• Step 6:

  Determine if the ants have reached the destination. If the ants have not reached the destination, continue to step 5. Otherwise, record the length and information of path, and enter step 7.

• Step 7:

  Let the ant index $l = l + 1$ , and judge whether $l$ is equal to $m$ . If not, return to step 4. Otherwise, update the pheromone concentration.

B. Dynamic Hybrid Ant Colony Algorithm

Based on the static hybrid ant colony algorithm, we incorporate the collision risk calculation, recognition of encounter situation and selection of avoidance action into the dynamic hybrid ant colony algorithm (DHACA). The ship travels along the initial path planned by SHACA, and obtains the surrounding environmental information and traffic conditions in real time.

We define the safe encounter radius of the target ship as $D_{safe} = S_{DA}$ . If the closest encounter distance $D_{cpa}$ between the own ship and the target ship is less than $D_{safe}$ , there may be a risk of collision between the two ships. In Fig. 2, $v_{R}^{\prime }$ is speed of the own ship relative to the target ship. We define the time $T_{cpa}$ when the own ship and the target ship arrive at the nearest meeting point, and $T = {}\frac {G}{v_{R}^{\prime }}$ . When $T_{cpa} \geq 2T$ , the own ship will not collide with target ship. When $T \leq T_{cpa} \leq 2T$ , the own ship should pay close attention to the movement of the target ship. When $T_{cpa} \leq T$ , the own ship may collide with target ship.

Fig. 2.

Collision detection of ships.

If the own ship is in danger of collision and has the duty to avoid, the own ship should take appropriate avoidance measures. To simplify the calculation, we realize avoidance by veering the ship. In the case of single-ship encounter, the own ship has two tangent points with the safe circle of the target ship, $R_{p}(x_{rp},y_{rp})$ and $L_{p}(x_{lp},y_{lp})$ as shown in Fig. 3. In the actual navigation, steering avoidance always take a right turn, we use the left tangent point of the safety circle as the guiding point for ship avoidance.

Fig. 3.

Avoidance with single ship.

In Fig. 4, there are three target ships, namely target ship A, target ship B, and target ship C. In the case of a multi-ship encounter, we compute the angle between the own ship and the target ship’s left tangent point according to the position of target ship. In this paper, the left tangent point of the target ship with the smallest angle is selected as the avoidance guidance point. The angle of the tangent point is computed according to the formula (12). $$\begin{equation*} \theta _{goal} = \mathrm {min}\left \{{\theta _{AL},\theta _{BL},\theta _{BL}}\right \} \tag{12}\end{equation*}$$

Fig. 4.

Avoidance with multi-ships.

Due to the constraints of the grid, the ship can only turn in eight directions. Therefore, we choose the nearest direction to the right of the $\theta _{goal}$ among the eight directions as the final steering direction. We propose a dynamic hybrid ant colony algorithm (DHACA) based on the above analysis. The detailed steps of DHACA are as follows:

• Step 1:

  Use the grid to discretize the ship’s navigation environment and set the position of starting point, destination, obstacle, and target ship. Establish the conversion relationship between the coordinate systems of the navigation environment and the ship.

• Step 2:

  Use the HACSA algorithm to plan an initial navigation path, and the ship will sail along the initial path.

• Step 3:

  Compute $T_{cpa}$ , $D_{cpa}$ , and the relative orientation of the own ship and target ships.

• Step 4:

  Determine whether the own ship needs to take avoidance measures. If not, the own ship continues sailing along the original path and goes to step 3 until the own ship arrives at the destination. Otherwise, go to step 5;

• Step 5:

  Determine whether $D_{cpa} \leq D_{safe}$ and $T_{cpa} \leq T$ are true at the same time. If $D_{cpa} \leq D_{safe}$ and $T_{cpa} \leq T$ are not met, the ship continues sailing along the initial path. If $D_{cpa} \leq D_{safe}$ and $T_{cpa} \leq T$ are met, compute the angle between the own ship and the left tangent point of the target ship, use formula (12) to compute $\theta _{goal}$ and take steering measures.

• Step 6:

  After the avoidance is over, use the SHACA to plan the path and go to step 3.

SECTION IV. Results

A. Parameter Study

1) The Influence of m on the Algorithm

The number of ant $m$ has an important influence on the pheromone concentration and the ability of path planning. When $m$ is small, the algorithm has a better convergence speed. However, it is easy to converge prematurely, which is not conducive to the algorithm finding the optimal solution. With the increase of $m$ , the ability of global path planning of the algorithm is gradually strengthened to obtain the optimal solution, but the convergence speed becomes slower. When $m$ increases to a specific range, the searchability can be further improved, but the convergence speed is greatly reduced due to the excessive pheromone on the path. To quantitatively describe the impact of $m$ on the algorithm, we give the path planning effect of the algorithm using different $m$ . The path planning results are shown in Fig. 5 (a).

Fig. 5.

The optimal ship path with different (a) number of ants $m$ and (b) pheromone volatilization coefficient $\delta$ .

Figure 6 (a) shows the length of the optimal path $L_{a}$ with different $m$ . When $m$ is less than 20, the convergence speed of the optimal path slowly decreases as $m$ increases. When $m \in [{20,50}]$ , the results are basically close to the optimal solution. When $m > 50$ , the results are far from the optimal solution, and the computation cost is higher.

Fig. 6.

The length of the optimal path $L_{a}$ with different (a) number of ants $m$ and (b) pheromone volatilization coefficient $\delta$ .

2) The Influence of $\delta$ on the Algorithm

The pheromone volatilization coefficient $\delta$ represents the loss speed of the pheromone in the iteration process. The value of $\delta$ has a significant influence on the searchability of the algorithm. When $\delta$ is small, the remaining pheromone in the path plays a leading role, which can improve the random ability to search the path of the algorithm and reduce the speed of iteration. When $\delta$ is big, the influence of the residual pheromone decrease and the positive feedback effect of the pheromone is improved. As a result, the random ability of searching the path of the algorithm is reduced and the speed of iteration is increased. To quantitatively describe the impact of $\delta$ on the algorithm, we give the path planning effect (see Fig. 5 (b)) and the length of the optimal path $L_{a}$ (see Fig. 6 (b)) of the algorithm using different $\delta$ . From Fig. 6 (b), we can see that the random search performance of the algorithm decreases with the increase of $\delta$ . Sometimes the algorithm fails to converge to the optimal solution.

B. Path Planning Experiments

This paper designs the path planning simulation experiments of static and dynamic environments. In the static environment experiment, we perform the comparison simulation scenes of a simple and complex environment. Our examples are performed on a workstation with an 8-core 2.80 GHz CPU. In all experiments, the parameters of our hybrid ant colony algorithm are shown in Tab. I, including the number of ants $m$ , the pheromone volatilization coefficient $\delta$ , the information heuristic factor $\kappa$ , the expected value heuristic factor $\lambda$ , the constant pheromone intensity $C$ , the weighted coefficient of the constraint function $\omega _{1}$ , $\omega _{1}$ , $\omega _{1}$ , the attraction potential field coefficient $K_{a}$ and the repulsive potential field coefficient $K_{r}$ .

TABLE I Parameter settings of the hybrid ant colony algorithm.

1) Experiments of Static Path Planning

(1) Comparison With Simple Environment: To prove the advantage of SHACA, we compare SHACA with the traditional ant colony algorithm, the algorithm in literature [18], and the algorithm in literature [19] in the simple navigation environment. The size of the grid is 30*30 (n mile). We set 205 obstacles in the navigation environment. To ensure fairness, the four algorithms use the same navigation environment and parameter settings, including the number of ants, the pheromone volatilization coefficient, the constant pheromone intensity, etc.

The optimal ship path obtained by the above algorithm in the simple environment is shown in Fig. 7. The convergence of the algorithm is shown in Fig. 8. Tab. II gives the important statistic of the above algorithm, including the length of the optimal ship path $L_{a}$ (n mile), the average length of the planned path $L_{v}$ (n mile), the number of inflection points $N_{v}$ , the iteration number of convergence $N_{c}$ , the iteration time of convergence $T_{c}$ (s) and the number of unsafe path points $N_{nc}$ .

TABLE II Statistics of path planning algorithm in the simplex environment.

Fig. 7.

The optimal ship path of each algorithm in the simple environment. (a) the traditional ant colony algorithm; (b) algorithm in literature [18]; (c) the algorithm in literature [19]; (d) our SHACA.

Fig. 8.

The convergence of algorithms in simple environment.

From Tab. I, we can see that all algorithms can find their respective optimal paths, and the path obtained by the algorithm in the literature [19] is the shortest. Compared with the algorithm in the literature [19], SHACA considers the ship safety constraint, ensuring that the ship’s path does not intersect with the obstacle. Under the safety constraints, $L_{a}$ of SHACA is 46.28 (n mile), and $N_{nc}$ is zero. In contrast, $N_{nc}$ of algorithm in literature [19] is 11. It can be seen that the SHACA can better coordinate the relationship between the length of the ship path and safety constraints compared with the algorithm in the literature [19].

From Fig. 8, we can see that the algorithm in literature [18], [19], and SHACA converge at the $26 th$ , $12 th$ , and $8 th$ iteration. The traditional ant colony algorithm can not converge. This result shows that SHACA has better convergence than the other three algorithms. Our algorithm requires less computation time to achieve convergence due to fewer iterations than other algorithms. In Tab. II, we make a horizontal comparative analysis of the four algorithms through path length, the number of iterations, computation time, and ship safety. It can be seen that SHACA has relatively optimal results in the evaluation indicators.

(2) Comparison With Complex Environment: To verify the stability of SHACA, we increase the size of the simulation domain and place more obstacles. The size of the grid is 50*50 (n mile). We set 484 obstacles in the navigation environment. The path results of the traditional ant colony algorithm, algorithm in literature [18], algorithm in literature [19], and HACSA are shown in Fig. 9. The convergence of the algorithm is shown in Fig. 10. Tab. III gives the important statistic of the above algorithm.

TABLE III Statistics of path planning algorithm.

Fig. 9.

The optimal ship path of each algorithm in the complex environment. (a) the traditional ant colony algorithm; (b) algorithm in literature [18]; (c) the algorithm in literature [19]; (d) our SHACA.

Fig. 10.

The convergence of algorithms in complex environment.

From Tab. III, SHACA and the algorithm in literature [18], [19] can converge to get their optimal paths. In the complex environment, the path obtained by SHACA is the shortest, which is 74.6 n miles. Although the navigation environment is more complex, SHACA still converges at the $8th$ iteration, while the algorithm in literature [19] converges at the $20th$ iteration. Similar to the experiments in the simple environment, our algorithm uses the least computation time to converge in the complex environment. The complex environment hardly affects the efficiency of our algorithm. In addition, the algorithm in the literature [18] also considers the constraint of ship safety. Compared with the algorithm in literature [19], the ship path planned by SHACA is safer in complex environments.

2) Experiments of Dynamic Path Planning

(1) Dynamic Path Planning for Single Target Ship: To verify the rationality of DHACA for planning the dynamic path, we set some static obstacles and a moving ship in the navigation domain. The size of the simulation domain is $20*20$ (n mile). The start coordinate of the navigation is $(1,20)$ , and the end coordinate is $(20,1)$ . We set the navigation course 45 degrees and the speed $20 (n mile / s)$ . The start coordinate, the course and the speed of the target ship is $(20,9)$ , 180 degrees and $16 (n mile/h)$ , respectively. In addition, there are three obstacles in the navigation domain, include two convex obstacles and a rectangular obstacle.

Figure 11 gives the results of dynamic path planning for a single target ship. In the initial navigation stage, we use SHACA to plan a safe path from start point to end. Subsequently, the own ship sails along the path. When the own ship arrives at the cell of $(12,9)$ , $D_{cpa}$ between the own ship and the target ship is $0.98 n mile$ , and $\theta _{T}$ is 30.46 degrees. The distance between the two ships is $5.85 n mile$ , the relative speed is $32 (n mile/h)$ , $T_{cpa}$ is 11.3 minutes.

Fig. 11.

Dynamic path planning of Single-objective.

Fig. 12.

Distance change of single target ship encounter. $D_{ot}$ is the distance between the own ship and target ship.

According to DHACA, there is a risk of collision between the two ships, and the ship should turn right to avoid the collision. During the process of avoidance, we use DHACA to plan the new local path from the current position to the destination in real-time, as shown in Fig. 11 (b). When the own ship sails to the cell of $(12,13)$ , the danger of collision are removed (see Fig. 11 (c)). Once the process of avoidance is over, the own ship sails along the new path. The complete navigation path is shown in Fig. 11 (d). Figure 10 shows the distance change between the own ship and the target ship in the process of avoidance. We can see that the closest encounter distance between the two ships is far enough, which proves the safety of the path planned by the DHACA algorithm.

(2) Dynamic Path Planning Fot Multi-Target Ship: To verify the stability of DHACA for planning the dynamic path, we set multiple static obstacles and three moving ship in the navigation domain. The size of the simulation domain is $20*20$ (n mile). The start coordinate of the navigation is $(1,20)$ , and the end coordinate of the navigation is $(20,1)$ . We set the navigation course 45 degrees and the speed $20 (n mile / s)$ . The start coordinate, the course, and speed of the No.1 target ship are $(17,13)$ , 180 degrees, and $16 (n mile/h)$ , respectively. The start coordinate, the course, and the speed of the No.2 target ship are $(18,7)$ , 225 degrees, and $10 (n mile/h)$ , respectively. The start coordinate, the course, and the speed of the No.3 target ship are $(1,5)$ , 315 degrees, and $10 (n mile/h)$ , respectively.

Figure 13 gives the results of dynamic path planning with multi-target ships. Similar to the path planning for a single target ship, we use SHACA to plan a safe path from start point to end in the initial stage of navigation (see Fig. 13 (a)). When the own ship arrives at the cell of $(6,15)$ , $D_{cpa}$ between the own ship and the No.1 target ship is $0.94 n mile$ , and $\theta _{T}$ is 18.65 degrees. The distance between the two ships is $6.07 n mile$ , the relative speed is $36 (n mile/h)$ , $T_{cpa}$ is 10.4 minutes. Subsequently, the own ship turns right to avoid the collision.

Fig. 13.

Dynamic path planning of multi-objective.

When the own ship arrives at the cell of $(10,15)$ , the collision risk between the own ship and the No.1 target ship is removed. The own ship sails to the destination along a new local path, as shown in Fig. 13 (b). When the own ship arrives at the cell of $(11,14)$ , DHACA detects that there is a risk of collision between the own ship and the No.2 target ship and plans a new path (see Fig. 13 (c)). Finally, the own ship sails to destination as shown in Fig. 13 (d). In Fig. 13, the own ship can dynamically identify multiple dynamic obstacles and can correctly judge the encounter situation between the own ship and the target ships to complete avoidance.

SECTION V. Conclusion

We propose an improved ant colony algorithm to improve the safety and economy of ship path planning. The ant colony algorithm has a slow iteration speed and easily falls into the local optimum. We introduce the artificial potential field method in the algorithm’s initial stage to improve the iterative speed and ability for searching optimization results. In addition, to further make the planned path conform to the actual situation, we integrate the constraints of path length, safety, and smoothness into the pheromone update rules and consider the constraints of navigation rules. The simulation results prove the feasibility and effectiveness of our algorithm.

In this paper, we mainly study the ship path planning in the static environment and only realize the dynamic path planning with the multi-target ship in the simplex environment. In the future, how to achieve ship dynamic path planning in complex environments is an interesting research direction. In addition, both the static and dynamic path planning algorithms proposed in this paper discretize the navigation environment on the grid, so the output path is a discontinuous grid trajectory, which causes the problem of low control accuracy in real navigation environment. Another useful research direction to explore is to apply curve smoothing technology to the algorithm to make the output path smoother. We assume that the target ship sails at a constant direction and speed for the dynamic path planning in the multi-ship encounter. In the future, it can be considered how the own ship takes measures to avoid when the target ship has the duty of avoidance but does not take avoidance measures.