1.

INTRODUCTION

Ship route planning is an essential part of the ship navigation process, and its criticality directly determines the safety and efficiency of ship navigation at sea. The ship route planning problem involves finding the safest and shortest route from a starting point to a destination point based on available geographic information data. Traditional planning algorithms, such as the visibility graph method, free space method, and artificial potential field method, have certain limitations. In recent years, the ant colony algorithm has been widely used in path planning due to its parallelism, distributed computing, positive feedback mechanism, and robustness. This method has been extensively applied in path planning for robots, aircraft, and other systems. [11] However, considering the basic ant colony algorithm’s long search time and the possibility of stagnation, an improved ant colony algorithm has been proposed. Simulation results demonstrate that the improved ant colony algorithm shows significant improvements in path search efficiency and reliability compared to the basic ant colony algorithm.

2.

THE MECHANISM OF ANT COLONY ALGORITHM

The ant colony algorithm is an emerging bio-inspired algorithm that was first proposed by Italian scholar Dorigo M and others at the First European Conference on Artificial Life held in Paris, France in 1991. In 1992, Dorigo M further elaborated on the core ideas of the ant colony algorithm in his doctoral thesis [9]. In nature, the food sources for ants are randomly distributed around their nests. Although there are multiple paths from the nest to the food source, after a certain period of time, ants are always able to find the shortest path between the nest and the food source. Despite the simplicity of individual ant behavior, the entire ant colony demonstrates a high level of cooperation. Research has shown that ants can leave a substance called pheromone on the paths they traverse during foraging, and ants themselves can sense the presence and intensity of this substance during their movement. These substances can guide the movement of ants themselves and other ants. Ants tend to move towards areas with higher concentrations of pheromone. In the same period of time, more pheromone is left on shorter paths, and more ants choose these shorter paths. This is the positive feedback phenomenon of ants [1]. The ant colony algorithm is designed based on this foraging behavior of ants in nature and is an optimization algorithm that obtains the best path by following a certain search strategy.

3.

MODELING OF SHIP NAVIGATION ENVIRONMENT

3.1

Representation of ship navigation environment

When ships navigate in the open sea, their navigation space is an obstacle space. In order to plan a route for the ship, the navigation space needs to be divided.

The grid method is currently the most widely studied approach for planning spatial navigation. This method decouples the navigation space of a ship into multiple simple regions called grids. These grids form a connected graph, and a path from the starting grid to the target grid is searched on this graph. In this study, a combination of the index method and Cartesian coordinate method is used, where the grids visited by an ant are represented using the index method. This is because the index method is more memory-efficient and concise compared to the Cartesian coordinate method. When evaluating the grids visited by the ant, the index is converted into a coordinate form, as the coordinate method is more suitable for representing the relative positions between grids, calculating path lengths, and verifying path feasibility. [2] The schematic diagram of the Cartesian coordinates and index of the grids is shown in Figure 1.

Figure 1

Schematic diagram of the lattice

The relationship between Cartesian coordinates and indices can be expressed as follows:

In the equation: i represents the grid number that the ant passes through; x and y represent the corresponding Cartesian coordinates. Here, N_x represents X_max / δ; δ represents the side length of a unit grid; X_max represents the maximum value of x; mod represents the modulus function in Matlab; fix represents the function of rounding towards zero.

3.2

Handling of obstacle zones

According to the display standards of S-57 in electronic nautical charts and information systems, obstacle zones are typically composed of one or more polygonal rings. [3] In this study, the obstacle zones for simulating ship navigation are approximated as combinations of multiple squares. When processing obstacle zones, the following methods are employed: (1) If the obstacle occupies less than one grid, it is still considered as occupying one grid. (2) The empty space within an obstacle and the obstacle itself are treated as a single entity, avoiding the occurrence of local dead zones. (3) In the case of adjacent obstacles, if the physical distance between them is relatively small, the intermediate area between them is also considered as an obstacle. Otherwise, they are treated as separate obstacles. The approximation of obstacles with arbitrary shapes is illustrated in Figure 2.

Figure 2

Approximation of obstacles

3.3

Expansion of obstacle zones

Due to the influence of weather conditions (such as, wind, current, waves) on ship navigation, as well as the uncertainty of obstacle positions and variations in the accuracy of navigation positioning systems, the designed route may be affected. Considering the forementioned uncertainties, this study expands the obstacle zones to allow for a margin of safety and reliability. The expanded obstacle zones are shown in Figure 3.

Figure 3

Expanding the obstacle area

3.4

Construction of obstacle matrix

After the processing and expansion of obstacle zones are completed, it is necessary to construct an obstacle matrix. In this study, the grid state of obstacles is set to 1, while the grid state of free areas is set to 0. The simulated space is shown in Figure 4.

Figure 4

The simulated navigation space

4.

ANT COLONY ALGORITHM IMPLEMENTATION

In the ant colony algorithm, ants choose the next path point based on the size of pheromone information. Therefore, the first step is to initialize the pheromone of each grid in the ship navigation area. This facilitates the ants’ next search. Then, all ants are placed at the starting point. According to the state transition probability formula (9) in the ant colony algorithm, the next navigation point is selected, and the passed and selected points are added to the tabu list. This process continues until the target point is found. [5] After all ants have completed one cycle, which is considered as one iteration, feasible paths are determined based on the paths searched by ants and the constraints of the objective function. Then, the pheromone of each path point in the feasible paths is updated. The subsequent search process follows the same steps until the iteration requirements are met.

4.1

Update of pheromone

In the basic ant colony algorithm, when all ants complete one iteration, the adjustment of the pheromone level on the path (i, j) is performed according to the following formula:

In the formula: τ_ij (t + n) represents the amount of pheromone on path(i, j) at time t + n; ρ represents the pheromone evaporation coefficient; 1 – ρ represents the pheromone residual factor; τ_ij (t) represents the increment of pheromone on path (i, j) in the current iteration; Q represents a constant representing the pheromone intensity; L_k represents the length of the path traveled by the k-th ant in the current traversal.

In order to enhance the efficiency and effectiveness of the ant colony algorithm, this paper proposes improvements to the updating mechanism of pheromones. The enhanced algorithm strengthens the amount of pheromones on each node of the optimal path corresponding to the optimal value of the objective function found in each iteration, while weakening the amount of pheromones on each node of the worst path with a feasible solution. This method strengthens the optimization strategy of the ant colony algorithm. [7]

In the equation: L_min represents the minimum value of feasible paths for the k-th ant in the current iteration; L_max represents the maximum value of feasible paths for the k-th ant in the current iteration.

4.2

The selection of the next path point for an ant to move to is determined by the following formula:

In the formula: η_ij represents the heuristic function; d_ij represents the distance from the next path point to the target point;(x_i, y_i) represents the Cartesian coordinates of the current path point; (x_e, y_e) represents the Cartesian coordinates of the target point.

5.

SIMULATION RESULTS

A square area of 200 nautical miles by 200 nautical miles was selected for the sea area. The sea area was divided using a grid method into 40x40 small grids, with each small grid representing 5 nautical miles by 5 nautical miles. The improved ant colony algorithm was applied, and the simulation was programmed using Matlab 7.0 software. [6] The simulation results are shown in Figure 5 and Figure 6. In Figure 5, the gray area represents the obstacle zone composed of shallow water areas, restricted navigation zones, and sunken ship areas. The solid line in Figure 5 represents the optimal route for ships to pass through this sea area. The starting grid of the route is represented by an inverted triangle, and the target grid is represented by a circle. Figure 6 illustrates the convergence curve of the maximum path during each iteration process of the improved ant colony algorithm. [4]

Figure 5

Improved ant colony algorithm for ship route planning

Figure 6

Convergence curve of the improved ant colony algorithm

The simulation results indicate that the improved algorithm used in this study effectively solves the ship’s route problem and reduces the search time. It also improves the search efficiency of the ant colony algorithm.

6.

CONCLUSION

Under the premise of knowing the location of obstacles in the navigational area, the improved ant colony algorithm proposed in this paper can design an optimal route for ships. [8] This algorithm overcomes the shortcomings of low search efficiency and stagnation often encountered in the basic ant colony algorithm. The simulation results demonstrate that this algorithm has significant advantages over traditional manually-drawn routes in terms of efficiency and economy.