Improved ant colony optimization algorithm based on islands type for mobile robot path planning

Abstract

According to the characteristics of ant colony optimization (ACO) algorithm in mobile robot path planning, such as local optimal solution, slow convergence speed, low search efficiency, and propensity to produce numerous deadlock ants, an improved ACO algorithm based on island type (insular ACO (INACO)) is introduced. In this algorithm, firstly, several islands are established between the starting and the ending position of environment, serving as intermediate nodes for the paths searched by the ants. This greatly reduces the number of deadlock ants. Additionally, rectangular areas are initialized with non-uniform pheromone levels between adjacent islands, while other areas are set to a constant minimum pheromone value. This prevents blind searches during the initial stages of path planning. Furthermore, an adaptive volatilization coefficient is introduced into the global pheromone update rules to balance the convergence and global search ability. Finally, optimal parameter combinations of INACO are determined by simulation. INACO algorithm is simulated in various grid maps and compared with other improved ACO algorithms. Results demonstrate its superior global optimal search capability and rapid convergence speed. The average iterative times is 2.7 in a 20 × 20 grid environment and 4.7 in a 30 × 30 grid environment. Notably, INACO produces very few lost ants, with mean values of 50.1 and 95.2 in 20 × 20 and 30 × 30 grid environments, respectively.

Introduction

Navigation is an important research direction which can be used in mobile robot ¹ and visually impaired individuals, ² the optimal path from the starting position to the target position without collision can be found through path planning. ³ Path planning stands as a crucial prerequisite for enabling mobile robots to independently navigate intricate environments. Its significance spans various domains, including facilitating autonomous robot actions to prevent collisions, ⁴ obstacle avoidance, ⁵ conducting unmanned aerial vehicle (UAV) penetration flights, ⁶ urban road network planning, ⁷ addressing vehicle routing challenges in logistics management, and so on. ⁸ Arduino Uno and Raspberry Pi are common control systems capable of sensing the environment through various sensors such as distance sensors, LiDAR, etc., and controlling lights, motors, etc., to provide feedback and influence the environment. They have been widely used by researchers in the design of unmanned vehicles. Samrat et al. ⁹ installed various sensors on the autonomous driving vehicle and utilized commands from Arduino and Raspberry Pi to implement an optimized path planning algorithm, aiming to find the optimal route to the destination. Oltean ¹⁰ proposed a mobile robot platform with a fixed four-wheel chassis and designed electronic systems around Raspberry Pi and Arduino Uno interfaces. This platform can be used for applications such as autonomous guided robots in indoor environments. Mohan and Ignatious ¹¹ designed a mobile robot controlled by an Arduino Uno board to assess the enhanced A* algorithm for path planning. Therefore, path planning holds high engineering application value and garnered considerable attention from scholars.

Path planning has emerged as a prominent research topic, garnering significant attention across various industries. A multitude of methodologies and algorithms, such as the Dijkstra algorithm, A* algorithm, simulated annealing (SA), artificial potential field (APF) method, and rapidly exploring random tree (RRT), among others, have been extensively investigated. The Dijkstra algorithm is widely recognized for computing the shortest route between a source and destination point. ¹² Wu et al. ¹³ utilized it to tackle urban traffic path planning in Nanling town, while Li et al. ¹⁴ implemented it in selecting the optimal service composition path, providing a feasible solution for selecting service composition modes. The A* algorithm, refined from the Dijkstra algorithm, incorporates global information to approximate the distance between the current position and the destination point. Hassani et al. ¹⁵ employed the A* algorithm to optimize robot path planning, while Duchon et al. ¹⁶ and Akshay et al. ¹⁷ enhanced the original A* algorithm for mobile robot path planning across various grid environments. Nevertheless, the A* algorithm's memory computation can significantly increase computational demands, especially in complex environments. The SA is a stochastic algorithm extensively applied to address combinatorial optimization challenges, including the traveling salesman problem and graph coloring problem. Xiao et al. ¹⁸ introduced an enhanced SA method for UAV coverage path planning, demonstrating its high-quality effectiveness. The vehicle routing optimization problem was addressed by Xi et al. ¹⁹ through their proposal of an SA-hybrid neural network (SA-HNN) algorithm. The APF stands as another commonly employed algorithm for path planning. ²⁰ In addressing the challenge of real-time drone path planning in complex environments, Yao et al. ²¹ incorporated a constrained artificial potential field method into their proposed path planning approach, leveraging the D*Lite algorithm for enhanced effectiveness. Xiong et al. ²² introduced the Rapid Annotation using Subsystem Technology star (RAST*) algorithm, a novel approach that merges concepts from the RRT star (RRT*) with tournament selection techniques and informative heuristics to enhance exploration and adaptability. Additionally, Zhang et al. ²³ proposed a target bias search strategy and a new metric function to address the poor real-time performance and rough planned paths of the basic RRT algorithm. Zhang et al. ²³ devised a targeted bias search strategy along with a novel metric function to mitigate the challenges associated with the basic RRT algorithm, including its sluggish real-time performance and the generation of coarse planned paths. With the advancements in bionic algorithms and artificial intelligence, intelligent path optimization algorithms such as genetic algorithm (GA),^6,7 particle swarm optimization (PSO), ²⁴ and ant colony optimization (ACO),^25,26 have become extensively employed in path planning tasks. The GA operates by searching for optimal solutions based on Darwinian evolution principles. ²⁷ Chong et al. ²⁸ utilized an improved adaptive GA to optimize the initial weights and thresholds of the backpropagation neural network, enhancing the reliability of underwater path planning for autonomous underwater vehicles. In another study, Zhang et al. ²⁹ improved the GA by incorporating adaptive crossover and mutation rates, resulting in refined path planning for multi-UAV scenarios to enhance effective flight time and mission completion rates. Similarly, PSO, known for its rapid convergence speed and minimal parameter requirements, has found widespread application in the realm of path planning. The improved PSO algorithm based on Gaussian processes, as presented by Kathen et al., ³⁰ achieves a better balance between exploration and exploitation for the movement of each autonomous surface vehicle on Lake Ypacarai's surface. Moreover, Ahmed et al. ³¹ introduced a trajectory planner leveraging the PSO algorithm to optimize path planning for achieving distributed full coverage by a swarm of UAVs.

The ACO algorithm, which was introduced by Dorigo and Gambardella, ³² is a meta-heuristic evolutionary algorithm based on group foraging and has the advantages of parallel processing, distributed computing, high robustness, and positive feedback.^33,34 Consequently it has been widely used in solving numerous combinational optimization problems ³⁵ and has demonstrated significant success in path planning for mobile robots. Despite its effectiveness, ACO still has some defects of stagnation and premature convergence, low search efficiency, difficulty in determining control parameters, local optimization, a large number of lost ants, and extended search durations. As the complexity of the environmental map increases, these deficiencies become more obvious. In an effort to improve the performance of ACO, several enhancements have been proposed by researchers. Zhao et al. ³⁶ introduced a variant of the ACO aimed at minimizing the effect of ant population size on algorithm performance. This was achieved through the implementation of information pheromone coverage and an updated strategy. Miao et al. ³⁷ proposed an improved adaptive ACO algorithm by enhancing transfer probability and implementing an adaptive adjustment method to the pheromone update rule. Wu et al. ³⁸ incorporated the rollback strategy into basic ACO, enabling more ants to reach the target while reducing the impact of invalid pheromones on ACO evolution. Yue et al. ³⁹ proposed a penalty strategy aimed at improving ants’ ability to explore unknown regions by volatilizing the poor path pheromone. An adaptive polymorphic ACO algorithm proposed by Jiao et al. ⁴⁰ can solve the problem of deadlock and improve the global search ability. Furthermore, Jiang et al. ⁴¹ introduced a novel improved algorithm rooted in ACO. This approach increased the initial pheromone concentration, dynamically controlled the pseudorandom transfer strategy, updated the pheromones of high-quality ants, and adjusted the volatility coefficient adaptively. This resulted in significant improvements in the global search ability, convergence speed, and computational efficiency. Zhang et al. ⁴² introduced an improved ant colony system (EACSPGO), which effectively accelerates the convergence rate and produces a better solution. Ajeil et al. ⁴³ devised an aging-based ACO (ABACO) that incorporates grid-based modeling across various grid maps to address navigation problems. Through comparisons with traditional algorithms in various static environments, they demonstrated the superiority of ABACO, offering new perspectives for improving ACO algorithms.

According to the literature mentioned above, optimization measures have improved the performance of ACOs in previous studies. However, some shortcomings remain, such as a large number of lost ants are not considered, especially in complex environments. There remains potential for enhancing both the convergence speed and the quality of solutions. In this paper, a variant of ACO, namely an improved ACO algorithm based on islands type (insular ACO (INACO)), is proposed. The main characteristics of this algorithm are summarized as follows:

Several island points are evenly distributed between the starting grid and the destination grid, resulting in a significant decrease in deadlocked ants and enhancing the success rate of finding the optimal path, especially in complex grid maps.

The acceleration of the convergence rate is achieved through the implementation of non-uniform pheromone distribution between adjacent islands during the initialization stage.

An adaptive evaporation coefficient is introduced to update the pheromone adaptively. Additionally, additional pheromones are increased along the optimal path as a reward, while they are reduced along the worst path as a form of punishment. With the improvements above, the global optimal path can be found quickly.

The optimal parameter combination is determined through the simulation studies, and the effectiveness of this algorithm is validated across different grid maps.

Environment modeling

For environment modeling, the grid method is employed due to its simplicity and efficiency. In the grid environment modeling, free grids are represented by 0 and are filled with white, while obstacle grids are represented by 1 and are filled with black. This paper utilizes a Cartesian coordinate system along with serial number notation to define the location of each grid. ⁴⁴ The grid method of environment modeling (Environment 1) is illustrated in Figure 1. Environment 1 comprises 10 × 10 grids. As depicted in Figure 2, the left-up grid represents an obstacle grid, while the remaining grids are free and available for robot path planning.

Figure 1.

Grid map.

Figure 2.

Alternative options for movement direction.

In a Cartesian coordinate system, the center of each grid can be uniquely represented by absolute coordinates (x, y). In the serial number method, grids are numbered sequentially from left to right and top to bottom, starting at 1 and increasing by 1. Each grid corresponds to a specific number. The serial number of all grids in the environment are formed as a set, which is described as follows ⁴⁵ :

$$G=[1,2,3,\dots ,g],g=m\times n$$

(1)

As follows, OBG denotes the set of obstacle grids, while FG denotes the set of free grids ⁴⁵

$$\mathrm{OBG}=[o{b}_1,o{b}_2,o{b}_3,\dots ,o{b}_l]$$

(2)

$$\mathrm{FG}=[f_1,f_2,f_3,\dots ,f_w]$$

(3)

The coordinate representation and serial number representation of any grid are calculated as follows ⁴⁵ :

$$g=\left({\displaystyle \frac{x}{{\delta }_x}+0.5}\right)+n\times \left[m-\left({\displaystyle \frac{y}{{\delta }_y}+0.5}\right)\right]$$

(4)

$$x=\{\begin{array}{c}[\mathrm{mod}(g,n)-0.5]\times {\delta }_x\mathrm{when}\mathrm{mod}(g,n)\ne 0\\ (n-0.5)\times {\delta }_x\mathrm{when}\mathrm{mod}(g,n)=0\end{array}$$

(5)

$$y=\left[m-\mathrm{ceil}\left({\displaystyle \frac{g}{n}}\right)+0.5\right]\times {\delta }_y$$

(6)

In equations (1) to (3), g, n, and m represent the grid number, the row count, and the column count in the grid map, respectively. ${\delta }_x$ and ${\delta }_y$ represent the length and width of the mobile robot, respectively, mod() is a remainder operation, and ceil() is an upward rounding operation.

Brief introduction of ACO

The ACO is utilized to solve optimization problems by imitating the food-seeking behavior of real ant colonies, which relies on the shortest route of pheromone from their nest to the food source. As ants search for food, they explore the environment randomly, while leaving pheromones on the path they traverse. Pheromone concentration increases as ants continue along paths with stronger pheromones. Consequently, an increased number of ants will be drawn to the path, leading to further amplifying the pheromone concentration, and so forth. The ants usually use the behavior mentioned above to search for the shortest path.

Assuming that the kth ant moves from position i to position j at time t, where position i is the current grid of the ant and position j is the unvisited grid to which the ant will move. If there is more than one unvisited grid j around current grid i, the transition probability $P_{ij}^k(t)$ is calculated by equation (7), and the grid j is determined by the roulette model. Equation (7) can be described as follows ⁴² :

$$P_{ij}^k\left(t\right)=\{\begin{array}{c}{\displaystyle \frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }*{\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }}{{\sum }_{S\in A_k}\left[{\tau }_{is}\left(t\right){]}^{\alpha }*\right[{\eta }_{is}\left(t\right){]}^{\beta }}j\in A_k}\\ 0j\notin A_k\end{array}$$

(7)

where ${\tau }_{ij}(t)$ represents the pheromone amount between position i and position j at the time t, while $\alpha$ and $\beta$ represent the pheromone concentration factor and expected heuristic factor, respectively. A_k denotes the collection of unvisited grids around the position i and ${\eta }_{ij}(t)$ is the heuristic value calculated by equation (8) ⁴⁷ :

$${\eta }_{ij}={\displaystyle \frac{1}{d_{jg}}}$$

(8)

where d_jg represents the distance between the next position j and the ending position, calculated by Euclidean distance formula as shown below ⁴² :

$$d_{jg}=\sqrt{{(x_j-x_g)}^2+{(y_j-y_g)}^2}$$

(9)

where (x_j, y_j) represents the grid coordinate of the next position j, and (x_g, y_g) represents the grid coordinate of the ending position.

Once all ants finished an iterative search, the pheromone on each path is adjusted according to equation (10) ⁴² :

$${\tau }_{ij}(t+1)=(1-\rho ){\tau }_{ij}(t)+\sum _{k=1}^m{\mathrm{\Delta }}_{ij}^k$$

(10)

where $\rho$ represents a parameter of pheromone evaporating rate, ${\mathrm{\Delta }}_{ij}^k$ represents the pheromone increment of kth ant from position i to position j in the current iterative cycle, and m is the total number of ants. The parameter ${\mathrm{\Delta }}_{ij}^k$ can be calculated as follows ⁴⁷ :

$$\mathrm{\Delta }{\tau }_{ij}^k=\{\begin{array}{c}{\displaystyle \frac{Q}{L_k}ifedge(i,j)ispassedbykthant}\\ 0otherwise\end{array}$$

(11)

where L_k is the length of the path searched by kth ant, and Q, the value is a positive constant, is the pheromone accumulation parameter.

Introduction of INACO

The traditional ACO has shortcomings in that it often falls into local optimization at the initial stage, as the optimal solution cannot always be attained through the selection of transition probability. Additionally, the algorithm's convergence rate may decelerate due to the limitations of heuristic search constraints. As a result, when the environment becomes more complex, ants are prone to becoming trapped. As illustrated in Figure 3, when an ant reaches position P1, there are no other grids to traverse, and similarly, there are no unvisited grids around position P2, leading to the failure to reach the target grid. To enhance the performance of ACO and reduce the number of lost ants, we introduce a variant algorithm of ACO, which is abbreviated as INACO. This algorithm improves four major aspects of ACO: the island division strategy between starting and target grids, the pheromone distribution in the initial stage, the modification of the heuristic function, and the global pheromone updating rule.

Figure 3.

Status of deadlock.

Island division principle

In response to reducing the number of lost ants in complex grid maps, several intermediate grids are added between the starting grid (S) and the end grid (E) before path planning, which we refer to as intermediate islands. To determine the location of the intermediate islands, we need to calculate the radius of the search circle (r_s), and it can be expressed as follows:

$$r_s={\displaystyle \frac{d_{\mathrm{SE}}}{N-1}}$$

(12)

where d_SE represents the Euclidean distance between S and E, if the two grids are regarded as islands, then N is the total number of islands. The search circle is drawn with the center of the grid of the beginning position as the center, r_s as the radius, the grid within the range of the search circle is the alternative island, as shown in equation (13).

$$\begin{array}{rl}Is& =[v_1,v_2,v_3,\dots ,v_z,\dots v_{ncircle}]\\ & v_z\in \mathrm{G}\mathrm{and}{v}_z\in \mathrm{FG}\end{array}$$

(13)

where $z\in [1,2,3,\dots ,n_{\mathrm{circle}}]$ and $n_{\mathrm{circle}}$ represents quantity of free grids in the search circle, $v_z$ represents the Zth alternative island, the coordinate values of alternative island $v_z$ and ending grid E are $(x_{v_z},y_{v_z})$ and $(x_{\mathrm{E}},y_{\mathrm{E}})$ , respectively, which can be calculated by formulas (5) and (6). $I_{\mathrm{coordinate}}$ represents best island coordinate and can be expressed by

$$I_{\mathrm{coordinate}}=\mathrm{argmin}\left[\sqrt{{(x_{v_z}-x_{\mathrm{E}})}^2+{(y_{v_z}-y_{\mathrm{E}})}^2}\right]$$

(14)

By analogy, the locations of all best islands are determined in turn, and the order of islands required for path planning is as follows:

$$I_{\mathrm{order}}=[I_1,I_2,\dots ,I_z,\dots I_N]$$

(15)

where $I_z$ is the serial number of the Zth best island, $I_1$ represents the beginning position (S), $I_N$ represents the ending position (E), N represents the total number of all the best islands.

Take Environment 1 as a example. As shown in Figure 4, 3 and 100 represent the starting and target positions, respectively. Assuming that the map requires five islands to be set, the final path planning sequence is $I_{\mathrm{order}}=[3,25,47,68,100]$ , the local optimal path is generated for two adjacent sequence numbers by INACO algorithm in turn, and then connecting all local optimal paths from beginning to end forms the global optimal for the entire complex map.

Figure 4.

Schematic map of island search.

Modify heuristic function

In basic ACO, the heuristic value of each grid, calculated by the heuristic function, remains constant throughout the process. However, to accelerate the convergence rate, it is desirable for the heuristic value to start with a higher value at the initial stages of the iteration calculation. As the iteration progresses, the heuristic value gradually decreases. Therefore, the heuristic function is modified accordingly, the specific calculation is shown as follows in equation (16):

$${\eta }_{ij}=\epsilon \times {\displaystyle \frac{N{c}_{max}-Nc+1}{N{c}_{max}}\times {\displaystyle \frac{1}{d_{jg}}}}$$

(16)

where $\epsilon$ is the scaling factor, $N{c}_{max}$ and $Nc$ represent the maximum and current iterations, respectively.

Improved distribution of initial pheromones

In the initial stage of ACO, all the pheromone values in the environment remain constant. At the outset of the path search, the ant colony exhibits a certain degree of blindness, which leads to the slow convergence rate of the algorithm. This article proposes an uneven initial pheromone distribution strategy, namely. Specifically, the rectangular region with the adjacent island numbers $I_z$ and $I_{z+1}$ as the vertices are designated as the favorable regions. The initial pheromone value of this region is calculated by equation (17), and the initial pheromone values of other adjacent island favorable regions in the environment are calculated sequentially, the pheromone value of the unfavorable region is set to a minimum among all favorable regions, The specific implementation is shown in equation (18).

$${\tau }_{ij}^{\mathrm{\prime }}(0)=\frac{d_{I_z{I}_{z+1}}}{d_{I_{z}i}+d_{ij}+d_{j{I}_{z+1}}}\times a_{0}i,j\in favorableregionand{I}_z\in I_{order}$$

(17)

$${\tau }_{ij}(0)=\{\begin{array}{c}{\tau }_{ij}^{\mathrm{\prime }}(0)i,j\in favorableregion\\ min\{{\tau }_{ij}^{\mathrm{\prime }}(0)\}i,j\notin favorableregion\end{array}$$

(18)

where $d_{I_z{I}_{z+1}}$ , $d_{I_{z}i}$ , $d_{ij}$ , and $d_{j{I}_{z+1}}$ represent the Euclidean distances between the island number $I_z$ and the next island number $I_{z+1}$ , the island number $I_z$ and position i, position i and position j, position j and next island number $I_{z+1}$ , respectively. $min\{{\tau }_{ij}^{\mathrm{\prime }}(0)\}$ denotes the minimum of all favorable region pheromone values. Under the condition that $d_{I_z{I}_{z+1}}$ is a certain value, through formula (16), it is evident that ${\tau }_{ij}(0)$ is inversely proportional to $d_{I_{z}i}+d_{ij}+d_{j{I}_{z+1}}$ , implying that the smaller value of $d_{I_{z}i}+d_{ij}+d_{j{I}_{z+1}}$ , the larger value of ${\tau }_{ij}(0)$ becomes. By sequentially computing the pheromone values of all paths across the entire map, the non-uniform initial pheromone distribution for the entire map can be obtained, which provides guidance for the subsequent ants to search global optimum route and accelerates the convergence rate of the algorithm. An example of an uneven initial pheromone distribution is illustrated in Figure 5, where each red rectangle represents a favorable area between adjacent islands.

Figure 5.

A case of non-uniform initial pheromone distribution.

Adaptive pheromone update rule

Once all ants complete an iterative cycle, the original path's pheromones evaporate at a certain rate, while new pheromones are deposited by ants that traverse the path. After many iterations, a path with the most concentrated pheromones emerges, representing the optimal route. An improvement in the pheromone update rule is proposed in this paper, which enhances the rate of pheromone accumulation on the optimal route while weakening the accumulation rate on the suboptimal route. Additionally, a dynamic adaptive volatilization coefficient is introduced. These adjustments improve the convergence rate of the algorithm. The specific calculations are outlined as follows:

$${\tau }_{ij}(t+1)=(1-\rho ){\tau }_{ij}(t)+\sum _{k=1}^m{\mathrm{\Delta }}_{ij}^k+\rho \mathrm{\Delta }{\tau }_{ij}*$$

(19)

$$\mathrm{\Delta }{\tau }_{ij}*=\{\begin{array}{c}{\displaystyle \frac{Q}{L_{\mathrm{best}}}edge(i,j)belongs\mathrm{to}theoptimumpath}\\ -{\displaystyle \frac{Q}{L_{\mathrm{worst}}}edge(i,j)belongs\mathrm{to}theworstpath}\\ 0otherwise\end{array}$$

(20)

$$\rho =\kappa \left({\displaystyle \frac{d_{\mathrm{SE}}}{L_{\mathrm{best}}}}\right)$$

(21)

Upon completion of each iteration by all ants, the pheromones of entire map are updated based on equation (19), where $(1-\rho ){\tau }_{ij}(t)$ represents term for volatilization, indicating the evaporation of the original pheromone, ${\sum }_{k=1}^m{\mathrm{\Delta }}_{ij}^k$ is the term of pheromones addition, indicating the addition of new pheromones to the path which the ants have passed, and $\rho \mathrm{\Delta }{\tau }_{ij}*$ represents the term of reward or punishment, $\mathrm{\Delta }{\tau }_{ij}*$ denotes the value of reward or punishment from position i to position j in the current iterative cycle, which can be calculated according to formula (20). This process involves adding additional pheromones to the optimal path to enhance guidance of subsequent iterations, or to reducing certain pheromones on the worst path to mitigate misleading effects on subsequent iterations. $L_{\mathrm{best}}$ is the optimum route length and $L_{\mathrm{worst}}$ is the length of the worst route during current iteration, $\rho$ represents adaptive volatilization rate, which can be calculated by formula (21), where $\kappa$ is the adjustment coefficient with a value range from 0 to 1. Through this formula, we can observe that in the early stages of the algorithm, $\rho$ is very small as $L_{\mathrm{best}}$ is very large, resulting in minimal differences in pheromone values on each path and strong global path planning ability within the ant colony. As the value of $L_{\mathrm{best}}$ becomes smaller and smaller, the value of $\rho$ increases gradually, leading to larger differences in pheromone values on each path. This guides more ants to choose the optimal path, enabling the algorithm to achieve faster convergence speed in the later stages.

Process of INACO for path planning

The concrete steps of INACO for path planning are as follows:

Step 1: Initialize parameters. The parameters, including S, G, m, $\alpha$ , $\beta$ , Q, $\kappa$ and N are initialized. Simultaneously, the maximum and current iterations are set to $N{c}_{max}$ and $Nc$ , respectively.

Step 2: Calculate the number of divided islands. The number of divided islands is calculated according to equations (12) to (15).

Step 3: Calculate ${\tau }_{ij}(0)$ , which represents the initial pheromone, according to formulas (17) and (18).

Step 4: Path selection. Initially, the starting position S is set as first island, and ending point G is set as $N\mathrm{th}$ island. The sequence of all islands can be represented as $[I_1,I_2,\dots ,I_z,\dots I_N]$ , and the quantity of deadlock ants initialized to 0. An ant is placed at the first island, according to formulas (7) to (9), the next grid j is calculated. The grid j passed by the ant is then added to the tabu list, and this process repeats. If the ant successfully reaches the next island, the next island becomes the new beginning position for the ant, and the path planning continues as described above, sequentially passing through the intermediate islands until reaching the target point. The path formed by all the nodes passed by the ant constitutes the desired path. If the ant encounters a deadlock between any two adjacent islands, the ant terminates the route search, and the count of lost ants increases by 1. Finally, another ant is positioned at the first island to search path from grid S to grid G similar to the process described above. This iterative cycle continues until all ants have completed the path planning.

Step 5: Global update of the pheromones. After each iterative search, the paths traversed by all ants are recorded from the beginning position S to the ending position G, the longest and the shortest path lengths are then determined from these records. The adaptive volatilization coefficient $\rho$ is calculated by formula (21). Subsequently, according to equation (20), pheromones on the shortest path are reinforced, while those on the longest path are penalized. Finally, the global pheromones of the whole map are updated by equation (19).

Step 6: Search end. If $Nc$ is greater than $N{c}_{max}$ , the algorithm outputs the optimal path length and its sequence number, the quantity of deadlocked ants, and other parameters. Otherwise, let $Nc=Nc+1$ and clear the tabu list, and return to Step 4 to continue path planning until the stopping condition is reached.

The specific procedure of INACO for route planning is depicted in Figure 6.

Figure 6.

Procedure of insular ant colony optimization (INACO) for route planning.

The algorithm proposed in this paper sets several islands between the starting point and the endpoint, which can also be seen as sub-target points. All ants are guided to reach these sub-target points sequentially, eventually reaching the endpoint. This approach employs a divide-and-conquer strategy. Once the islands are properly set, the ant colony can quickly complete the path planning, significantly reducing the loss of ants. It is particularly suitable for large-scale or complex map environments. Compared with other variants of ACO algorithms, this algorithm also improves the heuristic function, distribution of initial pheromones, and pheromone update rule to achieve faster convergence speed and better path solutions.

Simulation and analysis

Determination of parameter optimization combination

In an attempt to identify the optimal combination of parameters, numerous simulation experiments were conducted using empirical and experimental methods ⁴⁴ in this paper. The arbitrary simulation environment, hereafter referred to as Environment 2, is shown in Figure 7. The sequence number of the start position is 3, and the sequence number of the end position is 225.

Figure 7.

Environment 2: the test grid map.

A group of parameters is set for simulation experiments. In each experiment, parameters $\alpha$ , $\beta$ , m, $N{c}_{max}$ and Q have been studied by many researchers,^42,47 so the values of these parameters were determined based on references in each experiment. The newly designed parameters $\epsilon$ , $\kappa$ , and N also have significant impacts on the algorithm, each parameter's value is altered independently while keeping the others constant. Each experiment was run 10 times under the same parameters to avoid accidental situations. The average of all the results is computed, and the advantages and disadvantages of different parameter combinations were analyzed, including iteration times, the global optimum route length, and the quantity of deadlock ants of the algorithm.

In the environment 2, parameters are set as follows: $m=50$ , $N{c}_{max}=100$ , $\alpha =1.1$ , $\beta =7$ , $Q=100$ , $\kappa =0.8$ , and $N=3$ . The iterative times, global optimum route length, and amount of deadlock ants are checked, respectively, when $\epsilon =1$ , $\epsilon =20$ , $\epsilon =40,\dots ,240$ . The detailed simulation outcomes of INACO are depicted in Figures 8 to 10.

Figure 8.

The change of the iterative times with different scaling factor.

Figure 9.

The change of global optimal path length with different scaling factor.

Figure 10.

The change of amount of lost ants with different scaling factor.

From Figures 8 to 10, it can be observed that with the increase of the scaling factor, the number of iterations and the optimal path length of the algorithm change very slightly, but the number of lost ants increases gradually, when $\epsilon \in [1,100]$ , INACO exhibits good performance in three aspects mentioned above.

Under the condition of the same grid map, the setting parameters are set as follows: $m=50$ , $N{c}_{max}=100$ , $\alpha =1.1$ , $\beta =7$ , $Q=100$ , $N=3$ , $\epsilon =20$ , $\kappa =0.3$ , $\kappa =0.4,\dots ,1.3$ . The simulation results are plotted as curves, as shown in Figures 11 to 13.

Figure 11.

The change of the iterative times with different adaptive coefficient.

Figure 12.

The change of global optimal path length with different adaptive coefficient.

Figure 13.

The change of amount of lost ants with different adaptive coefficient.

Through analyzing Figures 11 to 13, regardless of the adaptive coefficient $\kappa$ , INACO consistently calculates the global optimum path, and the algorithm converges in only 1.5–2.0 iterations. When $\kappa \in [0.7,0.8]$ , the quantity of deadlock ants is the least.

In the same environment, experiments are conducted with parameters $N=2$ , $N=3,\dots ,12$ , while the remaining parameters are set as $m=50$ , $N{c}_{max}=100$ , $\alpha =1.1$ , $\beta =7$ , $Q=100$ , $\epsilon =20$ , and $\kappa =0.8$ . The simulation results are depicted as a curves shown in Figures 14 to 16.

Figure 14.

The change of the iterative times with different island number.

Figure 15.

The change of global optimal path length with different island number.

Figure 16.

The change of amount of lost ants with different island number.

Analyzing Figures 14 to 16 reveals that as the number of islands increases, the iterations required for convergence and the occurrence of deadlock ants decrease. The minimum number of iterations is 1 and the minimum number of lost ants is 0.2. However, as the number of islands increases, the optimal route length fluctuates. This occurs because while an island may appear optimal locally, it may not be the best choice for the entire map, resulting in convoluted paths. Therefore, minimizing the generation of deadlocked ants and selecting fewer islands is crucial.

Generally, INACO demonstrates superior performance than ACO. The better parameter combination is $\epsilon \in [1,100]$ and $\kappa \in [0.7,0.8]$ , and N is determined by grid map size.

To compare with other algorithms

Environment with 20 × 20 grids

To verify the algorithm's effectiveness, we employed a grid map used in simulation experiments by researchers in the literature.^46–48 Liu et al. ⁴⁶ proposed ACO with artificial potential field (APFACO) in the literature, ⁴⁶ Luo et al. ⁴⁷ proposed improved ACO (IACO) in literature, and a new variation of ACO called modified adaptive ACO (MAACO) algorithm was introduced in the literature. ⁴⁸ For the convenience of comparison, the same grid map was selected for our test environment in simulation experiments, the initialization parameters are set as follows: $m=50$ , $N{c}_{max}=50$ , $Q=100$ , $\alpha =1.1$ , $\beta =7$ , $\epsilon =20$ , $\kappa =0.8$ , and $N=4$ , with the sequence numbers of the start and ending positions being 1 and 400, respectively. The initial pheromone distribution of INACO is depicted in Figure 17, and the pheromone distribution of different iterations is shown in Figure 18. The simulation results of the five algorithms are compared as shown in Figure 19, where five optimum path lines generated by ACO, APFACO, IACO, MAACO, and INACO, respectively, are presented in Figure 19(a). Additionally, the optimal paths produced by A*, Dijkstra, and INACO are shown in Figure 20. To provide a more objective evaluation of the algorithm and avoid accidental cases, INACO was repeated 10 times under the same parameters mentioned above, and the average values of the relevant parameters are calculated. The specific statistical results are shown in Table 1.

Figure 17.

Initial pheromone distribution of insular ant colony optimization (INACO).

Figure 18.

The pheromone distribution of insular ant colony optimization (INACO) at 1, 5, 15, and 30 iterations.

Figure 19.

Simulation results of the five algorithms.

Figure 20.

The optimal path planning of three algorithms.

Table 1.

Statistics of relevant data generated by two simulation algorithms.

Item	Average iterative times	Average of path length	Optimal route length	Standard deviation	Mean value of lost ants
ACO	40.50	30.9706	30.9706	0	1112.7
APFACO	7.7	35.6573	35.0711	—	561.2
IACO	11.4	30.97056	30.97056	0	173.7
MAACO	5.3	30.97056	30.97056	0	74.3
A*	—	30.97056	30.97056	0	—
Dijkstra	—	30.97056	30.97056	0	—
INACO	2.7	30.97056	30.97056	0	50.1

ACO: ant colony optimization; APFACO: ACO with artificial potential field; INACO: insular ACO; MAACO: modified adaptive ACO.

As shown in Figures 17 and 18, it is evident that the pheromone quickly concentrates on the optimal path as the number of iterative times increases. Specifically, in Figure 18(b), it is noticeable that the algorithm can identify the optimal path by the fifth iteration, while pheromone is completely concentrated on the optimal path in the 10th iteration. Simulation results of the five algorithms are demonstrated in Figure 19, while Table 1 presents the statistical data from 10 repeated experiments about seven algorithms in the same environment. The global optimal path length in this environment is 30.97056, achievable by ACO, IACO, MAACO, Dijkstra, and INACO. Concerning convergence iterations, the average iterative times of INACO is 2.7, markedly superior to ACO, APFACO, IACO, and MAACO. It can also be seen from Figure 19(b) that INACO proposed in this paper has the fastest convergence speed. The average lost ants of INACO is 50.1, the smallest among ACO, APFACO, IACO, MAACO, and INACO. The INACO algorithm is comparable to the Dijkstra algorithm in calculating the optimal path length, but spends much less time (12.506 s < 30.27619 s) required to find the optimal path. Although the optimal path length generated by INACO is equal to that of A*, it is shorter than that of APFACO. Overall, the experimental results confirm the excellent performance of INACO.

Environment with 30 × 30 grids

For verifying the availability of INACO in path planning in a complex environment, we selected the grid map from the literature,^47,49 as the simulation environment. Hou et al. ⁴⁹ proposed an enhanced ACO algorithm with communication mechanism (CMEACO) in the literature, for the convenience of comparison, the grid map is also selected for our test environment for simulation experiments, The initialization parameters are set as follows: $m=50$ , $N{c}_{max}=50$ , $Q=100$ , $\alpha =1.1$ , $\beta =7$ , $\epsilon =20$ , $\kappa =0.8$ , and $N=5$ , the sequence number of the start position and ending position are 871 and 30, respectively. The initial pheromone distribution of INACO is depicted in Figure 21 and Figure 22 displays the pheromone distribution of this algorithm at different iterations. The simulation results of the four algorithms are compared in Figure 23 with Figure 23(a) illustrating the global optimum route produced by the four algorithms in a simulation environment. The optimal paths generated by A*, Dijkstra, and INACO are illustrated in Figure 24, INACO was also repeated 10 times in the complex environment to mitigate accidental occurrences. The specific statistical results are presented in Table 2.

Figure 21.

Initial pheromone distribution of insular ant colony optimization (INACO).

Figure 22.

The pheromone distribution of insular ant colony optimization (INACO) at 1, 5, 15, and 30 iterations.

Figure 23.

Simulation results of the four algorithms.

Figure 24.

The optimal path planning of three algorithms.

Table 2.

Statistics of relevant data generated by two simulation algorithms.

Item	Average iterative times	Average of path length	Optimal route length	Standard deviation	Mean value of lost ants
ACO	50	49.51271	46.2843	1.6564	1987.7
IACO	22.1	45.7768	44.5269	0.5409	387.3
CMEACO	11.7	44.70	44.5269	0.2043	237.70
A*	—	44.5269	44.5269	0	—
Dijkstra	—	44.5269	44.5269	0	—
INACO	5.2	44.5269	44.5269	0	95.2

ACO: ant colony optimization; IACO: improved ACO; CMEACO: enhanced ACO algorithm with communication mechanism; INACO: insular ACO.

From Figure 22, it is evident that pheromones began to concentrate on the optimal path by the fifth generation, reaching complete concentration by the 10th generation, showcasing the rapid convergence speed of the proposed algorithm. Figure 23(a) reveals that the path produced by ACO tends to optimize local paths, indicating the difficulty of the ACO algorithm in finding the optimal path in complex environments. In Figure 23(b), all algorithms converge quickly within 50 iterations except for the ACO algorithm, with the INACO algorithm exhibiting the fastest convergence speed. This is mainly attributed to the improved distribution of the initial pheromones and the adaptive pheromone update rule, effectively concentrating the pheromones to the optimal path. As depicted in Figure 23(c), the number of deadlocked ants n the proposed algorithm demonstrates a more rapid downward trend compared to the comparison algorithms. Combining Figure 24 and Table 2, although the optimal path lengths calculated by Dijkstra, A*, and INACO are the same, the calculation time of Dijkstra is significantly longer than that of INACO (94.873796 s > 30.080210 s). The global path length of the complex environment is 44.5269. In the 10 experiments, the average iterative times of the proposed algorithm is 5.2, close to half of the CMEACO, one-fourth of the IACO, and one-tenth of the ACO, indicating a significantly improved convergence speed. The average number of lost ants generated by INACO is 95.2. As the number of iterations increases, the number of deadlock ants of the INACO algorithm presents a sharp downward trend in the early stage and rapidly decreases to zero, which is the smallest among ACO, IACO, and MAACO.

In general, the INACO proposed in this paper is simulated in grid environments of 20 × 20 and 30 × 30 scales, respectively, and the simulation results are compared with other algorithms, the INACO effectively improves the convergence rate and reduces the number of lost ants by strategically setting islands between the starting position and ending position, improving the pheromone initialization strategy, and updating rules. These enhancements indicate promising prospects for practical applications.

The algorithm enhances path planning success by strategically incorporating islands between the starting and ending points in the grid map. It starts from the initial point and systematically searches for routes to reach these islands until smoothly reaching the destination. This increases the success rate of path planning, accelerates convergence speed, and reduces the number of lost ants. It is suitable for complex or large-scale map environments.

Conclusions

By analyzing the traditional ACO, this study proposes an INACO algorithm that effectively reduces the number of deadlock ants and exhibits a fast convergence rate, meanwhile, the length of the optimum path generated by INACO is shorter compared to other improved algorithms. The main results of the study are summarized as follows:

In an arbitrary grid map scenario, the beginning and the ending positions are treated as islands. Several additional island points are evenly distributed between the starting and the ending positions. This approach enables the ant colony to conduct path planning, island by island, from the beginning position to the ending position. Eventually, path planning for the entire grid environment between the beginning and the ending points is completed. This method significantly diminishes the number of lost ants and offers more pronounced advantages for complex grid maps.

The favorable region comprises a rectangular area formed by the vertices of the adjacent islands, while the remaining areas are designated as the non-favorable region. In the favorable region, pheromone values are initialized with non-uniform distribution, while in other regions, the pheromone values are set to a constant, which is the minimum pheromone value of the favorable region. This setup enables the ant colony to navigate effectively during path search and enhances the convergence speed of the algorithm.

The heuristic function has been modified to gradually decrease the heuristic value as the iteration times increase. This adjustment aims to improve the convergence rate of the algorithm.

An adaptive pheromone update rule is introduced to update the global pheromone when all ants complete the iteration. This rule increases the pheromones along the global optimum route as a reward while decreasing the pheromones along the worst route as punishment. This approach further accelerates the convergence rate and optimization efficiency of the algorithm.

The INACO is applied to the robot path planning, and the better parameter combination is determined through the simulation study. By comparing it with other improved algorithms in various grid environments, the effectiveness and superiority of the algorithm are proved.

Although the INACO algorithm proposed in this paper can calculate the optimal path of a two-dimensional map and reduce the number of deadlock ants, it has yet to be validated by real experiments. In future research, the superiority of the algorithm can be further verified by real experiments. In addition, the INACO algorithm will be improved and employed to solve the path planning problem in three-dimensional space environment models.