Whether search directions number affects the efficiency of the path planning algorithm: Taking an improved ACO algorithm with 32 directions for example

Abstract

An improved Ant Colony Optimization (ACO) algorithm, named IACO, is proposed to address the inherent limitation of slow convergence, susceptibility to local optima and excessive number of inflection in traditional ACO when solving path planning problems. To this end, firstly, the search direction number is expanded from 4 or 8 into 32; Secondly, the distance heuristic information is replaced by an area heuristic function, which deviated from the traditional approach that only considers pheromone information between two points; Then, the influence of path angle and number of turns is taken into account in the local pheromone update. Additionally, a reward and punishment mechanism is employed in the global pheromone update to adjust the pheromone concentrations of different paths; Furthermore, an adaptive update strategy for pheromone volatility factor adaptive is proposed to expand the search range of the algorithm. Finally, simulation experiments are conducted under various scenarios to verify the superiority and effectiveness of the proposed algorithm.

Keywords

Ant colony optimization mobile robot path planning search direction area-inspired grid map

1 Introduction

The increasing prevalence of mobile robot attributed to the rapid development of the high technology, among various technologies, path planning stands out as a core technology that enables mobile robots to perform tasks effectively [1 –6]. Path planning entails the ability to navigate from a specified start point to an end point in a safe and collision-free manner within an environment considering criteria such as path length, travel time and travel cost [7 –11]. In general, path planning is an optimization problem, and numerous algorithms have been proposed to address it. Initially, algorithms like Artificial Potential Field (APF) [12] and Rapidly-exploring Random Trees (RRT) [13], were proposed to solve the problem. Furthermore, intelligent algorithms such as Particle Swarm Optimization (PSO) [14], Genetic Algorithm (GA) [15], Ant Colony Optimization (ACO) [16] and Artificial Neural Networks (ANNs) [17] have been employed to obtain the optimal paths for the mobile robots. Beyond meta-heuristic search approaches, alterative blind search methods, such as Breadth First Search (BFS) [18] and Depth First search (DFS) [19] are also available. These methods are straightforward to implement and invariably arrive at a solution eventually. Nevertheless, when dealing with extensive and intricate test cases, optimization methods can often yield some of the quickest and most effective solutions.

Among the aforementioned algorithms, ACO is a method which has strong global optimization capability and the ability to easily integrate with other algorithms, making it well-suited for problems such as global path planning for robots [20 –23]. Notably, Dorigo et al. [24] proposed an enhanced ACO inspired by the foraging behavior of ant colonies in nature. Compared to other algorithms, ACO has the advantage of not requiring highly optimized initial routes and exhibits robustness. Its positive feedback mechanism facilitates continuous convergence during the search process, ultimately leading to an optimal solution. Additionally, the distributed computation employed in the search process allows for parallel computation by multiple individuals, significantly enhancing computational efficiency and operational effectiveness of the algorithm [25 –27]. However, practical applications have revealed that the ACO algorithm is prone to slow convergence, redundant planning paths, and local optima, many scholars have made significant improvement to the algorithm from various perspectives [28 –34].

Li et al. [35] proposed an ACO algorithm based on an adaptive greedy strategy, allowed the ant colony to continuously explore areas with high pheromone concentrations. Miao et al. [36] introduced an improved adaptive ACO algorithm that incorporated an angular guidance factor in the transfer probability, a heuristic information adaptive adjustment factor and an adaptive pheromone volatility factor in the pheromone update rule, respectively. They also proposed a multi-objective performance index to transform the path planning problem into a multi-objective optimization problem. Luo et al. [37] constructed the initial pheromone allocation unequally, employed a pseudo-random state transfer rules is employed for path selection, and a dynamic penalty method is introduced to solve the deadlock problem. Li et al. [38] proposed a new ACO algorithm that can reduce the number of access node and select more feasible directions by extracting feature points as access nodes, the location of the selected feature points determines the range of the pathfinding field of view, but the paths are not secure enough since their feature points are close to obstacles. Ajeil et al. [39] incorporated ant age modification into the ACO algorithm and implemented grid-based static and dynamic environment modeling to solve path planning problems. Yang et al. [40] divided path planning into two parts: path generation and trajectory optimization, they proposed a two-layer ACO algorithm where two algorithms run in different layer in parallel. Gao et al. [41] introduced a backtracking strategy and path merging strategy into ACO, and they developed a pheromone diffusion gradient formula that emphasizes the spreading of pheromones left on the path to form a gradient distribution in the region. Ali et al. [42] utilized the information from A* multidirectional algorithm to determine the nearest region for the search and established a trajectory evaluation model to improve the path quality. However, the A* multidirectional algorithm in this study alone does not sufficiently select the best nodes enough to complete the global path.

Although the aforementioned literature has made improvements to the path planning performance of ACO for mobile robots, it fails to adequately consider the global search capability of paths, path security and path smoothing. Building upon these gaps, this paper presents the main research focus. The contributions of this paper are outlined as follows.

Improved 32 search directions: The paper proposes an enhancement to the ACO algorithm by introducing 32 search directions. This allows for a wider range of choices and a larger search range during the path search process, leading to improved exploration capabilities.

Area-based heuristic information calculation: A novel method for calculating heuristic information based on the area is designed. This method takes into account the characteristics of the surrounding environment, providing more accurate guidance for path selection.

Consideration of turn angle and turn point: The paper considers the effects of turn angles and turn points in the process of pheromone updating. By incorporating these factors, the proposed method aims to improve the smoothness of the generated paths, resulting in more efficient and natural trajectories.

Adaptive update strategy for pheromone volatile factor: An adaptive update strategy for the pheromone volatile factor is presented. This strategy dynamically adjusts the volatility of pheromone based on the characteristics of the environment, allowing for better adaptability and performance in different scenarios.

Development of a mathematical model: A mathematical model is developed, taking into account path length, convergence performance, and smoothness. This comprehensive model provides a balanced evaluation of the generated paths, ensuring a high-quality solution for the path planning problem.

Simulation-based verification: The proposed method is validated through various simulations. These simulations assess the performance and effectiveness of the algorithm in different scenarios, providing empirical evidence to support the proposed contributions.

The rest of this paper is organized as follows: Section 2 briefly introduces the environmental modeling and problem modeling; Section 3 presents the traditional ant colony optimization; followed by a demonstration of the improved algorithm in Section 4; Section 5 provides the simulation results and analysis; whilst the conclusion and future work are presented in the final section.

2 Environmental and problem modeling

The ultimate target of mobile robot is minimizing the path length and the energy consumption while achieving the smoothest trajectory possible. For simplicity, assume the mobile robot operates in an environment with static obstacles and maintains a constant velocity. Additionally, the size of the robot is considered by expanding the obstacle [43].

2.1 Environmental modeling

There are three common used methods for environmental modeling: the grid method, the geometric method and the topological map method [44]. Among these methods, the grid method stands out due to its standardized representation and ease of implementation. Therefore, this paper chooses to adopt the grid method to build the environmental model.

As shown in Fig. 1, Fig. 1(a) illustrates an environment with obstacles of various shapes, while its corresponding grid map is depicted in Fig. 1(b). It is important to note that the shapes of obstacles may be irregular, requiring them to be expanded outward until they occupy the entire grid. Consequently, the modified grid map is shown in Fig. 1(c), where the obstacle grids are shaped in grey, and the white grids indicate the areas that are freely accessible to robots.

Fig. 1

Grid map ((a) Original map; (b) Grid map; (c) Obstacle expanding; (d) Grid mapping matrix).

To convert the environmental information into data that can be utilized for the mathematical model, a serial of numbers are sequentially marked on the grid map, as shown in Fig. 1(c). This allows for the formation of a grid mapping matrix, as depicted in Fig. 1(d). In this matrix, a value of 1 represents a grid occupied by obstacle(s), while a value of 0 indicates a grid that is freely accessible.

For a grid map with coordinates, each grid is assigned a unique coordinate. In an x×y environment, the position corresponding to the i-th grid, denote as (x_i, y_i), can be represented by the following equation. ${\begin{matrix} x_{i} = a \times [\mod (i, y) - \frac{a}{2}] \\ y_{i} = a \times [x + \frac{a}{2} - ceil (\frac{i}{x})] \end{matrix}$ (1) where, a is the side length of the grid, ceil (·) is a round up function, and mod (·) denotes the modulo operation.

2.2 Problem modeling

To ensure accurate and efficient path estimation, three evaluation indexes, namely path length, convergence performance, and smoothness, are utilized as the objective functions for the optimization problem. These indexes serve to determine whether the path is the optimal choice for the mobile robot.

2.2.1 Path length

Path length, denoted as L, directly estimates whether a path is the shortest path. It can be calculated using the following equation $L (p) = \sum_{i = 1}^{n - 1} d (p_{i}, p_{i + 1})$ (2) $d (p_{i}, p_{i + 1}) = \sqrt{(x_{i + 1} - x_{i})^{2} + (y_{i + 1} - y_{i})^{2}}$ (3) where n is the number of grids on the path; p_i is the i-th grid on the path and (x_i, y_i) is the location value of p_i, and d (p_i, p_i+1) is the Euclidean distance from p_i to p_i+1.

2.2.2 Convergence performance

The convergence performance index is influenced by the number of iterative convergence and time taken. A smaller number of iterative convergences and a shorter running time indicate faster algorithm convergence, better convergence performance, and a more optimal path. This relationship can be expressed in the following equation. $C (p) = δ_{1} k_{0} + δ_{2} t_{0}$ (4) where k₀ is the number of iterations of convergence and t₀ is the iteration convergence time, δ₁ and δ₂ are the weighting coefficients for the number of iterations and the running time, respectively, and δ₁ + δ₂ = 1.

2.2.3 Smoothness

A smooth path ensures the robot’s movement is fluid and natural, thus minimizing energy consumption. Therefore, smoothness is considered an important factor in estimating the quality of a path. In this paper, path turning angle and the number of turning points are chosen as the primary influencing factors for smoothness evaluation. Without loss of generality, taking Fig. 2 as an example, and the calculation of its smoothness can be determined by Equation (5). $S (p) = \sum_{i = 2}^{n - 1} angle (l_{i - 1}, l_{i}) + r$ (5) where, r is the number of path turns, as shown in Fig. 2. angle (l_i-1, l_i) is the angle variable from line l_i-1 to line l_i, expressed in radians, it can be calculated by Equation (6).

$\begin{matrix} angle (l_{i - 1}, l_{i}) = (π - angle (acos \\ ((x_{i} - x_{i - 1}) (x_{i + 1} - x_{i - 1}) + (y_{i} - y_{i - 1}) (y_{i + 1} - y_{i - 1})) / \\ (\sqrt{(x_{i - 1} - x_{i})^{2} + (y_{i - 1} - y_{i})^{2}} + \\ \sqrt{(x_{i} - x_{i + 1})^{2} + (y_{i} - y_{i + 1})^{2}}))) \end{matrix}$ (6)

Fig. 2

Schematic diagram of the path angle variable.

3 Traditional ant colony optimization

The ACO algorithm is a bio-inspired intelligence algorithm that mimics the forging behavioral characteristics of an ant colony. When ants search for food, they release a substance called pheromone, once the concentration of pheromone in a path is higher, the probability of ants choosing that path is corresponding higher [45]. Additionally, the probability of ants selecting a path is influences by the distance heuristic function, which can be expressed as Equation (7). $p_{ij}^{m} (t) = {\begin{matrix} \frac{{[τ_{ij} (t)]}^{α} {[η_{ij} (t)]}^{β}}{\sum_{k \in {allowed}_{m}} {[τ_{ik} (t)]}^{α} {[η_{ik} (t)]}^{β}}, & j \in {allowed}_{m} \\ 0, & otherwise \end{matrix}$ (7) $η_{ij} (t) = \frac{1}{d_{ij}} = \frac{1}{\sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}}}$ (8) where, $P_{ij}^{m} (t)$ denotes the transfer probability of ant m moving from node i to node j at time t; τ_ij (t) is the amount of pheromones from node i to node j at time t; η_ij (t) denotes the value of heuristic information from node i to node j at time t; α is the pheromone heuristic factor and β is the distance heuristic factor; allowed_m denotes the next allowable path of ant m set of nodes.

As previously discussed, ants deposit a specific quantity of pheromones when traversing, resulting in a gradual accumulation of pheromone concentration along the path. Simultaneously, the pheromone will also evaporate. After the entire population completes one iteration, the pheromone concentration on the path undergoes an update in accordance with Equations (9) and (10). $τ_{ij} (t + 1) = (1 - ρ) τ_{ij} (t) + \sum_{m = 1}^{M} Δ τ_{ij}^{m} (t)$ (9) $Δ τ_{ij}^{m} (t) = {\begin{matrix} \frac{Q}{L_{m}}, & ant m passes through path i, j \\ 0, & otherwise \end{matrix}$ (10) where, ρ is the pheromone volatility coefficient, ρ ∈ (0, 1); $\sum_{m = 1}^{M} Δ τ_{ij}^{m} (t)$ denotes the total amount of pheromone left on the path from node i to node j by M ants at time t; $Δ τ_{ij}^{m} (t)$ denotes the amount of pheromone left by ant m on path from node i to node j; Q is the pheromone enhancement coefficient; and L_m denotes the length of the path traveled by ant m.

4 Improved ACO algorithm

To better solve the shortcomings of traditional ACO algorithm, this paper improves four parts of the algorithm, including search method, heuristic function, pheromone update mechanism and pheromone volatile factor.

4.1 Search method

Apparently, ants can move in any direction, except where there are obstacles, to search for food sources. However, in the traditional grid-based ACO algorithms, the effective search direction and search field of ants are limited by the small number of available directions. Typically, ACO has 4 or 8 search directions and fields (refer to Fig. 3(a)) and (b)), which is not particularly practical. To enhance the precision of the search range and improve path optimization, this paper increases the search direction of ants and the grid point of search field into 32 and 48, respectively, Fig. 3(c) illustrates this enhancement.

Fig. 3

3 different ant search method directions((a) 4 search directions and 4 search fields; (b) 8 search directions and 8 search fields; (c) 32 search directions and 48 search fields).

The benefits of refined search direction and expanded search neighborhood for ants in finding shorter paths are highlighted. The advantage of the ant search strategy proposed in this paper, compared to the traditional approach, is illustrated through a simple example below.

As shown in Fig. 4, an ant starts at point S and reaches point E. Figure 4(a) and (b) depict the paths explored using 4 and 8 search directions, respectively, while Fig. 4(c) illustrates the path obtained through the method proposed in this paper. Assuming a grid with a side length of 1, the optimal path lengths discovered by the ants using different search methods can be calculated and presented in Table 1. It is evident from Table 1 that the search method proposed in this paper can identify the shortest feasible path, which is highlighted in bold.

Fig. 4

The paths planned by ants using different search methods ((a) path of 4 search directions; (b) path of 8 search directions; (c) path of 32 search directions).

Table 1

Results of different search methods

Search method	Path length
4 search directions	4
8 search directions	3.414
32 search directions	3.162

4.2 The improving heuristic function

The heuristic function of traditional ACO solely considers the distance between adjacent grids, without accounting for the distance to the end point. Consequently, it fails to effectively guide ants towards exploring the end point, resulting in limited global search capability and a propensity to converge to local optima. To address these shortcomings, an area heuristic function that incorporates both local and global search is proposed.

To describe the improved method, two distinct scenarios are discussed below:

The area of the formed triangle is non-zero

As depicted in Fig. 5, S represents the start point, E represents the end point, i represents the current node, j₁, j₂ and j₃ represent the available points. It is evident that s_{ij
₂
E} < s_{ij
₃
E} < s_{ij
₁
E}, indicating that that smaller triangle signifying is closer to the end point. Consequently, the probability of selecting point, j₂ in Fig. 5 is higher.

Fig. 5

Schematic diagram of the area heuristic function.

The area of the formed triangle is zero

In this scenario, there is a special case where three points are collinear,i.e., the area of the triangle is equal to zero, shown as Fig. 6.

Fig. 6

Special scenario.

Equation (11) is utilized to describe the situation depicted in Figs. 5 and 6: $η_{ij} (t) = {\begin{matrix} \frac{ω_{1}}{s_{ijE}}, & s_{ijE} \neq 0 \\ \frac{ω_{2}}{(d_{iE} + d_{jE})}, & s_{ijE} = 0 \end{matrix}$ (11) $s_{i j E} = \frac{(x_{i} \times y_{j}) + (x_{j} \times y_{E}^{}) + (x_{E} \times y_{i})}{2} - \frac{(x_{i} \times y_{E}^{}) - (x_{j} \times y_{i}) - (x_{E} \times y_{j})}{2}$ (12) $d_{iE} = \sqrt{{(x_{i} - x_{E})}^{2} + {(y_{i} - y_{E})}^{2}}$ (13) $d_{jE} = \sqrt{{(x_{j} - x_{E})}^{2} + {(y_{j} - y_{E})}^{2}}$ (14) where i is the current node, j is the next node, E represents the target point, d_iE represents the Euclidean distance between the two points i, E, and d_jE is the Euclidean distance between the two points j, E. ω₁ and ω₂ are the angle coefficients, where ω₁ ∈ [0, 1] and ω₂ ∈ [0, 2]. Figure 5 illustrates that, when S_ijD ≠ 0, the value of ω₁ is divided into two cases: when the ant’s forward direction is the green area, ω₁ = 0.05 is taken; when the ant’s forward direction is other than the green area, ω₁ = 1 is taken. As shown in Fig. 6, when S_ijD = 0, the value of θ_ijE is only θ_ijE = 0^° and θ_ijE = 180^° two cases, θ_ijE = 0^° indicates that the ants toward the target point, take ω₂ = 2; θ_ijE = 180^° indicates that the ants are moving towards the target point in the opposite direction, take ω₂ = 0.5(θ_ijE is the angle of ∠ijE).

Different angle coefficients are assigned to various ranges of ant advancement. The underlying concept is to assign larger angle coefficients to ants moving towards the end point compared to ants moving towards the starting point, this ensures the ants are motivated appropriately. The specific values of ω₁ and ω₂ are determined based on experimental observations and analysis.

The improved heuristic function improves the effectiveness of the algorithm’s search path, thereby reducing the likelihood of getting trapped in local minima.

4.3 Improving the pheromone update mechanism

Based on the existing drawbacks of ACO pheromone update mechanism, the paper presents an improved update strategy that incorporates both local and global pheromone updates. The approach aims to strike a balance between exploration and exploitation in the algorithm. The improved pheromone update function is represented by Equation (15). $τ_{ij} (t + 1) = (1 - ρ) τ_{ij} (t) + \sum_{m = 1}^{M} Δ τ_{ij}^{m} {(t)}^{'} + μ_{ij} (t)$ (15) where μ_ij (t) is the reward and punishment function.

In this paper, the selection of optimal path is determined by considering not only high pheromone concentration and collisions avoidance but also minimizing of turns and the angles of the turns. By taking all these factors into account, it increases the likelihood of finding the most optimal path.

Taking Fig. 7 as an example, S represents the start point and E represents the end point. In this case, the total path turning angle is ∠A + ∠ B + ∠ C, and there are 3 turning points is 3. It is worth noting that a smoother and shorter path is more likely to be chosen as the optimal path when both the total turning angle and the number of turning points are smaller.

Fig. 7

Path turning angle diagram.

Based on the aforementioned analysis, Equation (16) is proposed to enhance the local exploration capability by updating the local pheromone update mechanism. This equation pertains specifically to the movement of the m-th ant moves from node i to node j. $Δ τ_{ij}^{m} {(t)}^{'} = ɛ \frac{Q}{L_{m}} + \frac{1}{Δ_{1} {angle}_{ij} (t) + Δ_{2} r}$ (16) $ɛ = {\begin{matrix} ɛ_{1}, & L_{m} = L_{min} \\ ɛ_{2}, & L_{min} < L_{m} \leq 1.05 L_{min} \\ ɛ_{3}, & 1.05 L_{min} < L_{m} \leq 1.2 L_{min} \\ ɛ_{4}, & 1.2 L_{min} < L_{m} \end{matrix}$ where, angle_ij (t) is the angle made by nodes i and j at the current position, expressed in radians; r is the number of path turns; Δ₁ and Δ₂ are ratio factors, respectively; coefficient ɛ ∈ [0, 2]; L_m is the path length of the m-th ant; L_min is the current optimal path, when the value of L_min is less than or equal to L_best, then the path of m-th ant is the best, therefore, more pheromones will be kept on this path, in other words, should satisfy the condition ɛ₁ > ɛ₂ > ɛ₃ > ɛ₄, which will be further verified through experimental analysis.

While for global pheromone update, the aim is to enhance the global exploitation ability. To achieve this, the current minimum path length and the minimum path length of the global optimal path are taken into considered. Additionally, a reward and penalty mechanism is employed in the global pheromone update. The specific relationship between factors is described in Equation (17). $μ_{ij} (t) = λ \frac{L_{min}}{L_{best}}$ (17) $λ = {\begin{matrix} λ_{1}, & L_{min} < = L_{best} \\ λ_{2}, & L_{best} < L_{min} \leq 1.05 L_{best} \\ λ_{3}, & 1.05 L_{best} < L_{min} \leq 1.2 L_{best} \\ λ_{4}, & 1.2 L_{best} < L_{min} \end{matrix}$ where, punishment coefficient is denotes as λ ∈ [- 1, 1]; L_min represents the shortest path length obtained in the current iteration, L_best denotes the length of the current best path. If the value of L_min is less than or equal to L_best, it indicates that the current path is better than the previous optimal path. In order to obtain the best solution, better paths will be rewarded with more pheromones, while inferior paths will be penalized. This is achieved by satisfying the condition λ₁ > λ₂ > λ₃ > λ₄, and the specific values of these coefficients will be further verified through experimental analysis.

4.4 Pheromone volatile factor update

In traditional ACO, the pheromone volatility factor is typically a constant is a constant. However, this can lead to the algorithm easily getting stuck in local optimum, making it challenging to converge to the global optimal solution. Moreover, the constant volatility factor hinders the algorithm from discovering the global optimal path efficiently, resulting in increased time and resource consumption. In this paper, an adaptive update strategy for the pheromone volatile factor is proposed and its update formula is listed as follows: $ρ (t + 1) = {\begin{matrix} \frac{K}{K + k} \times \frac{1}{e^{1 - ρ (t)}}, & ρ \geq ρ_{min} \\ ρ_{min}, & otherwise \end{matrix}$ (18) where, K is the maximum number of iterations; k denotes the current iterations; and ρ_min is the minimum value of pheromone volatility factor, serves as the lower bound for of volatility factor, ensuring that it does not drop below this threshold.

Obviously, K is a crucial parameter for updating ρ. To determine the most appropriate value, various attempts are made. Figure 8 illustrates the curve of the pheromone volatility changes as K ranges from 0 to 100. It is worth noting that the initial volatility factor ρ₀ is set to 0.4.

Fig. 8

Trend of pheromone volatility factor.

As depicted in Fig. 8, the behavior of pheromone volatility factor can be observed. When the number of iterations is small, coefficient remains low, allowing ant to retain more pheromones on the paths they traverse. As the number of iterations increases, the volatility coefficient rises, causing the pheromone on each path evaporates rapidly, which helps prevent the algorithm from getting stuck in local optima. Eventually, the pheromone volatility coefficient gradually decreases, leading to an increase in pheromone content on the paths. This enhanced concentration of pheromones has stronger guiding effect on the ant colony. Once the number of iterations reaches a certain threshold, the ant colony will converge to the path with higher pheromone content, making the increasing pheromone concentration on the path favorable to the convergence of the algorithm.

4.5 Algorithm steps

The flowchart of the improved ACO algorithm is shown in Fig. 9, and the pseudocode of the algorithm steps is listed as Algorithm 1 shown.

Fig. 9

Flow of the proposed algorithm.

5 Simulation and analysis

All simulation experiments are conducted within a 2D environment. The obstacles within this environment are static and randomly generated. Specially, grid map environments below 50×50 are considered general scenes, while grid environments with dimensions of 50×50 or larger are considered more complex scenes.

5.1 Parameter setting

To verify the proposed method, this section presents several scenarios where the proposed method is compared with different existing methods. All the methods were implemented and executed using Matlab2022b, with the parameters set the same as specified in Table 2. The simulation environment utilized for these experiments was: Windows 11 (64-bit), AMD Ryzen 5 5500U with 2.10 GHz, 16 GB.

Table 2
Algorithm parameter settings

Algorithm Grid size: 10×10, 20×20, 30×30

M K Q α β ρ Δ ₁ Δ ₂ δ ₁ δ ₂

ACO-8 50 200 1 1 7 0.3 / / / /

IACO-16(Ref. [46]) 50 50 1 1.5 6 0.4 / / / /

IACO-32 50 50 1 1 4 (0.25, 0.7) 1.2 2 0.6 0.4

Algorithm	Grid size: 10×10, 20×20, 30×30
ACO-8	50	200	1	1	7	0.3	/	/	/	/
IACO-16(Ref. [46])	50	50	1	1.5	6	0.4	/	/	/	/
IACO-32	50	50	1	1	4	(0.25, 0.7)	1.2	2	0.6	0.4

To determine the optimal values of ɛ and λ, parametric experiments were conducted using the scenario depicted in Fig. 12(b). The range for each parameter was set as follows: ɛ ∈ [0, 2] λ ∈ [- 1, 1]. In each experiment, only one parameter was changed, while keep the other parameters fixed. To minimize the impact of algorithm randomness, the average value of the results from 10 independent runs was used for comparison and analysis.

The experimental results for each group of parameter ɛ combinations are shown in Table 3. The minimum values in the experimental data are highlighted in bold. Based on the results in Table 3, it can be observed that in Groups 1, 2, and 3 (corresponding to ɛ₁ > ɛ₂ > ɛ₃ > ɛ₃), the algorithm yields better results. On the other hand, in Groups 4, 5, and 6 (corresponding to ɛ₁ ≤ ɛ₂ ≤ ɛ₃ ≤ ɛ₄), the algorithm performs worse or fail to find effective paths. These findings align with the theoretical results discussed in Section 4.3. Consequently, a set of parameters from the first three groups of experiments is selected, with the parameters from Group 3 being chosen as the default value of ɛ for the subsequent experiments.

Table 3

Results for different values of parameter ɛ

Groups	ɛ ₁	ɛ ₂	ɛ ₃	ɛ ₄	Mean value of L (p)	Mean value of C (p)			Mean value of S (p)
						k ₀	t₀(s)	C (p)	r	angle (rad)	S (p)
1	2	1.4	0.8	0.2	32.1421	14.5	1.5562	9.32248	8	37.8562	45.8562
2	1.6	1.2	0.8	0.4	32.1421	13.9	1.5351	8.95404	8	37.6991	45.6991
3	1.2	1.0	0.8	0.5	32.1421	10.9	1.3321	7.07284	8	37.8562	45.8562
4	0.8	1.2	1.6	2	34.0007	14.9	1.6058	9.58232	10.7	40.6836	51.3836
5	0.4	0.8	1.2	1.6	34.1421	16	1.6397	10.25588	11	40.8407	51.8407
6	0	0.4	0.8	1.2

The experimental results for each group of parameter λ combinations are presented in Table 4. From the results in Table 4, it can be seen that the first three groups of cases with λ₁ > λ₂ > λ₃ > λ₄ yields better results in both Group 2 and 3 experiments. On the other hand, in the last three groups of cases with λ₁ ≤ λ₂ ≤ λ₃ ≤ λ₄, only Group 6 managed to find a valid path. Based on these findings, the parameter value from group 3 is chosen as the default value of the parameter λ for subsequent experiments.

Table 4

Results for different values of parameter λ

Groups	λ ₁	λ ₂	λ ₃	λ ₄	Mean value of L (p)	Mean value of C (p)			Mean value of S (p)
						k ₀	t₀(s)	C (p)	r	angle (rad)	S (p)
1	1	0.5	0	–0.5	/	/	/	/	/	/	/
2	0.5	0	–0.5	–1	32.2593	13.8	1.4968	8.87872	8	38.0133	46.0133
3	0.5	0	–0.3	–0.4	32.1421	10.9	1.3321	7.07284	8	37.8562	45.8562
4	0	–0.5	–1	–1	/	/	/	/	/	/	/
5	–0.5	0	0.5	1	/	/	/	/	/	/	/
6	–1	-0.5	0	0.5	32.6207	8.6	1.1661	5.62644	9.9	38.3274	48.2274

According to the analysis above, for IACO-32, the optimized values of the and parameters are set as ɛ = { ɛ₁ = 1.2, ɛ₂ = 1.0, ɛ₃ = 0.8, ɛ₄ = 0.5 } , λ ={ λ₁ = 0.5, λ₂ = 0, λ₃ = -0.3, λ₄ = -0.4 }, respectively.

5.2 Improved strategies effectiveness analysis

The paper proposed four improvement strategies in order to validate their effectiveness. Based on the traditional ACO, only one strategy in this paper is utilized in this paper, while the remaining strategies are kept unchanged. As a result, four experiments will be conducted, comparing each strategy with IACO-32 to determine their impact on the improvement of the three indicators in IACO-32. To ensure fairness, all simulations will run in a 20×20 grid map environment, and the final solution will be determined by the average results of 10 runs. The parameter settings are provided in Table 5, where Strategy I represents the search pattern strategy, Strategy II represents the heuristic function strategy, Strategy III represents the pheromone updating mechanism strategy, and Strategy IV represents the pheromone fluctuation factor adaptive updating strategy.

Table 5
Parameter table of the four strategies

Strategy Grid size: 20 × 20

M K Q α β ρ Δ ₁ Δ ₂

Strategy I 50 150 1 1 7 0.3 / /

Strategy II 50 150 1 1 4 0.3 / /

Strategy III 50 150 1 9 4 0.3 1.2 2

Strategy IV 50 150 1 1 7 (0.25, 0.7) / /

Strategy	Grid size: 20 × 20
Strategy I	50	150	1	1	7	0.3	/	/
Strategy II	50	150	1	1	4	0.3	/	/
Strategy III	50	150	1	9	4	0.3	1.2	2
Strategy IV	50	150	1	1	7	(0.25, 0.7)	/	/

The optimal path diagrams obtained in two different map scenarios using the four proposed strategies and IACO-32 in this paper are depicted in Figs. 10 (a) and 11(a). It is evident from the figures that the optimal paths can be efficiently planned using both the four strategies and IACO-32. The iterative convergence curves are illustrated in Figs. 10 (b) and 11(b), wherein the horizontal axis represents the number of iterations and the vertical axis represents the shortest path length for each iteration.

Fig. 10

Results of Map 1 runs ((a) Optimal path diagram of the four strategies; (b) Iterative convergence graph).

Fig. 11

Results of Map 2 runs ((a) Optimal path diagram of the four strategies; (b) Iterative convergence graph).

Table 6 lists the average experimental data obtained from 10 simulation runs for each of the four strategies and IACO-32 in Maps 1 and 2. Based on the data, the following conclusions can be drawn, where “+” indicates larger data than IACO-32, “-” indicates smaller data than IACO-32, and “∼” indicates similar data.

Table 6

Experimental data of the four strategy simulations

Map	Algorithms/Strategies	The average value of L (p)	The average value of C (p)			The average value of S (p)
			k ₀	t₀(s)	C (p)	r	angle (rad)	S (p)
Map 1	Strategy I	30.4604∼	77+	5.2923+	48.31692+	10∼	15.7-	25.7-
	Strategy II	29.799∼	1.7-	0.6915-	1.2966-	10.7∼	38.9557+	49.6557+
	Strategy III	35.6703+	14.75+	1.8975∼	9.609∼	16.5+	45.9458+	62.4458+
	Strategy IV	30.0233∼	29.7+	2.2181+	18.70724+	9.6∼	41.4690+	51.069+
	IACO-32	29.3895	10.1	1.3251	6.59004	9.1	31.2588	40.3588
Map 2	Strategy I	30.1278∼	72+	4.5664+	45.02656+	8.4-	15.0796-	23.4796-
	Strategy II	29.799∼	2.5-	0.7237-	1.78948-	13.4+	39.5841+	52.9841+
	Strategy III	40.5165+	13.5-	1.578-	8.7312-	21.5+	41.4436+	62.9436+
	Strategy IV	29.3304∼	56.6+	4.0421+	35.57684+	10.7-	38.4845+	49.1845∼
	IACO-32	29.4514	24.6	2.0924	15.59696	11.5	33.7721	45.2721

In map 1, the path length metric L (p) of Strategy I is similar to IACO-32 and the smoothness metric S (p) is smaller than IACO-32. Meanwhile, the path length metric L (p) of Strategy II is similar to IACO-32 and the convergence performance metric C (p) is smaller than IACO-32. As for Strategy III, the convergence performance metric C (p) is similar to IACO-32; and the path length metric L (p) of Strategy IV is similar to IACO-32.

In map 2, the path length metric L (p) of Strategy I is similar to IACO-32, while the smoothness metric S (p) is smaller than IACO-32. Similarly, the path length metric L (p) of Strategy II is similar to IACO-32, while the convergence performance metric C (p) is smaller than IACO-32. For Strategy III, the convergence performance metric C (p) is similar to IACO-32; and the path length metric L (p) of Strategy IV is similar to IACO-32.

Overall, Strategy I, Strategy II and Strategy IV are effective in terms of the path length metric L (p); Strategy II and Strategy III are effective in terms of the convergence performance metric C (p); while Strategy I is effective in terms of the smoothness metric S (p). Based on these findings, it can be concluded that all four strategies are effective in different aspects.

5.3 Simulation experiments in three different scenarios

To evaluate the path search ability of the search method and heuristic information calculation method proposed, scenarios of different sizes (10×10, 20×20 and 30×30) are tested. The detailed environments for these scenarios are illustrated in Fig. 12. Additionally, two comparison algorithms are employed, and the parameters for all three algorithms are listed in Table 2.

Fig. 12

Three map environments ((a) 10×10 map; (b) 20×20 map; (c) 30×30 map).

Each algorithm is run 10 times, and their performance is compared based on average path length, average number of convergence iterations, average running time, number of turning points and turning angle. The number of convergence iterations and running time reflect the convergence speed of the algorithm, and the number of turning points and turning angle reflect the smoothness of the path. The statistical results of these metrics can be found in Tables 7–9. Furthermore, the optimal paths for different scenarios are listed in Fig. 13.

Table 7

Simulation results in 10 × 10 raster map

Algorithm	The average value of L (p)	The average value of C (p)			The average value of S (p)
		k ₀	t₀(s)	C (p)	r	angle (rad)	S (p)
ACO-8	21.5563	54.4	3.1924	33.91696	11	26.7035	37.7035
IACO-16 (Ref. [46])	20.3200	14.9	2.6350	9.994	10.3	26.7035	37.0035
IACO-32	15.9573	6.5	0.8811	4.25244	7.1	21.5199	28.6199

Table 8

Simulation results in 20×20 raster map

Algorithm	The average value ofL (p)	The average value ofC (p)			The average value ofS (p)
		k ₀	t₀(s)	C (p)	r	angle (rad)	S (p)
ACO-8	32.2461	164.5714	11.7776	103.45388	9.7143	46.0019	55.7162
IACO-16 (Ref. [46])	32.7279	11	1.4149	7.16596	8	43.9823	51.9823
IACO-32	32.2595	10	1.2242	6.48968	8	38.0133	46.0133

Table 9

Simulation results in 30×30 raster map

Algorithm	The average value of L (p)	The average value of C (p)			The average value of S (p)
		k ₀	t₀(s)	C (p)	r	angle (rad)	S (p)
ACO-8	/	/	/	/	/	/	/
IACO-16 (Ref. [46])	46.3870	11.4	5.3310	8.9724	15	51.8363	66.8363
IACO-32	44.8383	6.1	3.7476	5.15904	14	47.1239	61.1239

Fig. 13

Optimal paths of the three algorithms in different grid map environments ((a) 10×10 map; (b) 20×20 map; (c) 30×30 map).

In the scenario depicted in Fig. 13(a), the data presented in Table 7 highlights the notable advantages of IACO-32 over the other two ACO algorithms. Specially, the path length metrics of IACO-32 demonstrate a reduction of 25.97% and 21.47% compared to the other algorithms. Additionally, the convergence performance metrics C (p) shows a reduced of 87.46% and 57.45%, while the smoothing metrics S (p) demonstrate a reduced by 24.09% and 22.67%, respectively. These results clearly indicate that the proposed method outperforms the two compared algorithms in this particular environment.

For the scenario shown in Fig. 13(b), an examination of Table 8 reveals that the path length metrics L (p) of IACO-32 exhibit minimal changes when compared to the other two ACO algorithms. However, a significant improvement is observed in the convergence performance metrics C (p), with reductions of 93.07% and 9.44%, respectively. Similarly, the smoothing metrics S (p) demonstrate a reduction of 17.41% and 11.48% for the proposed method. Consequently, it can be concluded that in this particular environment, the proposed method surpassed the two compared algorithms in terms of convergence performance and smoothness.

Upon analyzing Table 9 and considering the 30×30 map, it becomes evident that the path length metrics L (p) showcase a reduction of 3.34% in comparison of the IACO-16 algorithm. Additionally, the convergence performance metrics C (p) present a reduction of 42.50%, while the smoothing metrics S (p) exhibit a reduction of 8.55%. Consequently, it can be concluded that in this specific environment, the traditional ACO-8 algorithm fails to generate an effective path. On the other hand, the proposed method outperforms the IACO-16 algorithm in all three performance metrics.

Based on the statistical results, it is evident that ACO-8 exhibits the poorest search performance in terms of path finding effectiveness. Particularly, when the grid map reaches a certain scale, ACO-8 fails to discover an effective path. Conversely, IACO-32 demonstrates significant advantage in terms of path length, running time and path smooth, establishing its superiority in path finding.

By observing Fig. 13, it becomes apparent that ACO-8 yields the shortest path. However, it is notable that this path contains several inflection points and lack smoothness. Conversely, the path generated by IACO-16 [46] exhibits fewer redundant points compared to ACO-8, yet it is not the shortest path. On the other hand, the path planned by the IACO-32 algorithm displays fewer redundant points and achieves a higher level of smoothness.

5.4 Comparison with other algorithms

To further validate the efficacy of the proposed algorithm in this paper, a comparison is conducted with four distinct types of algorithms: Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Sticky Mushroom Algorithm (SMA), and Sparrow Search Algorithm (SSA). This evaluation takes place within the confines of 20×20 maps, employing a population size of 50 and an iteration number of 50.

Figure 14 illustrates the optimal paths obtained by the five algorithms, and Fig. 15 displays their convergence curves. Upon analyzing these figures several observations can be made. Firstly, the path generated by GA and PSO planning in Fig. 14 exhibit noticeable redundant points. Secondly, the paths produced by SMA and SSA planning appear similar, showing no evident redundant points, but with right-angle turns the lack smoothness. In contrast, the path planned by IACO-32 display no obvious redundant points and demonstrate a high level of smoothness.

Fig. 14

Path diagram of simulation run results ((a) Results of GA; (b) Results of PSO; (c) Results of SMA; (d) Results of SSA; (e) Results of IACO-32).

Fig. 15

Convergence graph of five algorithms.

Figure 15 reveals that GA and PSO perform relatively worse than IACO-32 in terms of path length and number of convergences. While SMA achieves a slightly shorter path length than IACO-32, it experiences a significantly higher number of convergences. On the other hand, SSA exhibits a slightly smaller number of convergences smaller than IACO-32’s, but its path length is not as short as IACO-32.

Table 10 provides detailed results, indicating that the paths planned by the IACO-32 algorithm proposed in this paper are shorter than GA, PSO and SSA in terms of path length. Furthermore, the IACO-32 algorithm achieves fewer iterative convergence compared to GA, PSO and SMA. Additionally, the number of path inflection points gained by IACO-32 is fewer than GA’s.

Table 10

Comparison results of five algorithms

Algorithms	Average shortest path length	Average number of convergence iterations	Number of inflection points
GA	31.25786	24.4	15.7
PSO	31.38061	11.8	11.3
SMA	30.71024	12.2	11.7
SSA	30.9701	2	11
IACO-32	30.7924	10.7	14.2

In summary, the main advantage of IACO-32 algorithm lies in its minimal fluctuation in the convergence curve and its ability to quickly approach the optimal path value during the pre-iteration phase. Conversely, the other four algorithms exhibit significantly longer path lengths during the pre-iteration phase and require gradual iterations to gradually reduce the path length. This phenomenon is observed even in the latest proposed SSA algorithm. While the SSA algorithm surpassed the IACO-32 algorithm in terms of the number of iterations, it compromised on two important indicators: path length and the volatility of the convergence curve.

5.5 Simulation in larger and more complex scenarios

To verify the effectiveness of IACO-32 in larger and more complex scenarios, we conducted experiments in a 50×50 environment size. We compared the performance of the traditional ACO algorithm with the IACO-32 algorithm on two different map environments. In order to ensure the reliability of the algorithm in these complex scenarios, the maximum number of iterations of the algorithm is set to 150 in the scenario depicted in Fig. 16, and 100 in the scenarios in Fig. 17, respectively, β = 7, and other parameters remained consistent with the settings mentioned earlier.

Fig. 16

Results the first complex scenario ((a) Search path diagram;(b) Optimal path;(c) Iterative convergence curve).

Fig. 17

Results the second complex scenario ((a) Search path diagram;(b) Optimal path;(c) Iterative convergence curve).

In the two different scenarios, the optimal paths obtained by IACO-32 algorithm are illustrated in Figs. 16 (b) and 17(b), respectively. The corresponding search trajectories are presented in Figs. 16 (a) and 17(a). These figures demonstrate that the IACO-32 algorithm effectively finds optimal paths in complex maps.

The convergence curves, depicting the path length changing over iterations, are shown in Figs. 16 (c) and 17(c). The horizontal axis represents the iteration number, while the vertical axis represents the path length. It is evident that the algorithm proposed in this paper gradually converges within the set maximum number of iterations. In contrast, the traditional ACO algorithm fails to converge within the given maximum number of iterations, thus unable to search for an effective path.

Table 11 provides a data table of the simulation results, and the standard deviation indicates that the convergence performance of the algorithm proposed in this paper is more stable and less volatile.

Table 11

Operational results data table

Map	Data type	L(p)	k ₀	t₀(s)	C (p)	r	angle (rad)	S (p)
Map 1	Average value	80.6756	31.9	50.7846	39.45384	23	94.8761	117.8761
	Standard deviation	0.1766	27.1394	32.4617	29.26832	3.1972	5.6974	8.8946
Map 2	Average value	71.8701	45.7	65.3182	53.54728	16.4	79.6394	96.0394
	Standard deviation	0.1682	32.0349	38.0460	34.43934	1.2649	1.2932	2.5581

Overall, the results confirm the effectiveness and stability of the IACO-32 algorithm in larger and more complex scenarios. It successfully obtains optimal paths while ensuring convergence within the specified number of iterations.

6 Conclusion

In this paper, we address the low search efficiency and slow convergence issues associated with traditional ACO algorithms. To overcome these challenges, we proposed an improved ACO algorithm with 32 search directions, referred to as IACO-32. The IACO-32 introduces enhancements in heuristic function, pheromone update mechanism and pheromone volatility factor. These improvements enable the algorithm to expand the search range of the ant colony and significantly improve convergence speed. Simulation results demonstrate that IACO-32 algorithm possessed superior search capabilities compared to traditional ACO algorithms. It not only generates smoother planner path but also reduces energy loss of the robot. The effectiveness and superiority of the proposed algorithm are further verified through experiments conducted in both simple and complex simulation environments. The results confirm the feasibility and effectiveness of the IACO-32 algorithm in addressing the limitations of traditional ACO algorithm.

What needs illustration is that the robots working environment in this study is assumed to be static, however, in many real-world practical applications, the environment is often more complex, including semi-static outdoor scenes and dynamic environments. This complexity posed additional challenges for effective path planning algorithms. In light of these challenges, our further work will be dedicated to further improving the performance of existing algorithms. One approach we will explore is integrating the advantage of multiple algorithms to optimize their overall performance. By combining the strengths of different algorithms, we aim to develop more robust and efficient path planning approaches. Additionally, we recognize the needs to address dynamic obstacle avoidance in complex multidimensional environments, this is a crucial aspect that requires consideration in real-world scenarios.

Acknowledgements

This work was supported by the Natural Science Research of Jiangsu Higher Education Institutions of China (22KJA580003) and Xuzhou Science and Technology Project of China KC23008).

References

Palacín

, Salse

J.A.

, Valgañón

and Clua

, Building a mobile robot for a floor-cleaning operation in domestic environments, IEEE Transactions on Instrumentation and Measurement 53 (2004), 1418–1424.

Garduno-Aparicio

, Rodriguez-Resendiz

, Macias-Bobadilla

and Thenozhi

, A multidisciplinary industrial robot approach for teaching mechatronics-related courses, IEEE Transactions on Education 61 (2018), 55–62.

Peng

, Vougioukas

, Slaughter

, Fei

and Arikapudi

, A strawberry harvest-aiding system with crop-transport collaborative robots: Design, development, and field evaluation, Journal of Field Robotics 39 (2022), 1231–1257.

Topolsky

, Topolskaya

, Plaksina

, Shaburov

, Yumagulov

, Fedorov

and Zvereva

, Development of a mobile robot for mine exploration, Processes 10 (2022), 865.

Kim

S.-D.

and Bae

C.-O.

, Unmanned engine room surveillance using an autonomous mobile robot, Journal of Marine Science and Engineering 11 (2023), 634.

Bulut

and Erol

M.H.

, A real-time dynamic route control approach on google maps using integer programming methods, International Journal of Next-Generation Computing 9 (2018), 189–202.

Wang

, Liu

, Li

and Prorok

, Mobile robot path planning in dynamic environments through globally guided reinforcement learning, IEEE Robotics and Automation Letters 5 (2020), 6932–6939.

Aggarwal

and Kumar

, Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges, Computer Communications 149 (2020), 270–299.

Liu

, Wang

, Yang

, Liu

, Li

and Wang

, Path planning techniques for mobile robots: Review and prospect, Expert Systems with Applications 227 (2023), 120254.

10.

Loganathan

and Ahmad

N.S.

, A systematic review on recent advances in autonomous mobile robot navigation, Engineering Science and Technology, an International Journal 40 (2023), 101343.

11.

Patle

B.K.

, Ganesh Babu,

, Pandey,

, Parhi

D.R.K.

and Jagadeesh,

, A review: On path planning strategies for navigation of mobile robot, Defence Technology 15 (2019), 582–606.

12.

, Dai

, Jiang

and Reza Karimi,

, Robot path planning based on artificial potential field with deterministic annealing, ISA Transactions 138 (2023), 74–87.

13.

Zhang

, Lin

, Wang

and He

, Rapidly-exploring random trees multi-robot map exploration under optimization framework, Robotics and Autonomous Systems 131 (2020), 103565.

14.

and Chou

, Path planning for mobile robot using self-adaptive learning particle swarm optimization, Science China Information Sciences 61 (2017), 1–18.

15.

Suresh

K.S.

, Venkatesan

and Venugopal

, Mobile robot path planning using multi-objective genetic algorithm in industrial automation, Soft Computing 26 (2022), 7387–7400.

16.

Liu

, Yang

, Liu

, Tian

and Gao

, An improved ant colony algorithm for robot path planning, Soft Computing 21 (2016), 5829–5839.

17.

Xiao

, Wang

, Cheng

, Huang

and Yan

, Optimized neural network based path planning for searching indoor pollution source, Journal of Ambient Intelligence and Humanized Computing 14 (2021), 191–205.

18.

Ryu

, Graph search-based exploration method using a frontier-graph structure for mobile robots, Sensors 20 (2020), 6270.

19.

Tang

, Tang

, Zhou

, Claramunt

and Men

, R-DFS: A coverage path planning approach based on region optimal decomposition, Remote Sensing 13 (2021), 1525.

20.

Sui

, Tang

, Dong

, Gan

, Luo

and Sun

, ACO+PSO+A*: A bi-layer hybrid algorithm for multi-task path planning of an auv, Computers & Industrial Engineering 175 (2023), 108905.

21.

Juang

C.-F.

and Yeh

Y.-T.

, Multiobjective evolution of biped robot gaits using advanced continuous ant-colony optimized recurrent neural networks, IEEE Transactions on Cybernetics 48 (2018), 1910–1922.

22.

Viseras

, Losada

R.O.

and Merino

, Planning with ants: Efficient path planning with rapidly exploring random trees and ant colony optimization, International Journal of Advanced Robotic Systems 13 (2016), 1–16.

23.

Dong

, Guo

W.W.

and Tickle

, Solving the traveling salesman problem using cooperative genetic ant systems, Expert Systems with Applications 39 (2012), 5006–5011.

24.

Dorigo

and Gambardella

L.M.

, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Trans Evolutionary Computation 1 (1997), 53–66.

25.

Hou

, Xiong

, Wang

and Chen

, Enhanced ant colony algorithm with communication mechanism for mobile robot path planning, Robotics and Autonomous Systems 148 (2022), 103949.

26.

Y.-N.

, Gong

Y.-J.

, Xiao

C.-F.

, Gao

and Zhang

, Path planning for autonomous underwater vehicles: An ant colony algorithm incorporating alarm pheromone, IEEE Transactions on Vehicular Technology 68 (2019), 141–154.

27.

Jiao

, Ma

, Rong

, Wang

, Zhang

and Wang

, A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs, Journal of Computational Science 25 (2018), 50–57.

28.

Mavrovouniotis

, Yang

, Van

, Li

and Polycarpou

, Ant colony optimization algorithms for dynamic optimization: A case study of the dynamic travelling salesperson problem, IEEE Computational Intelligence Magazine 15 (2020), 52–63.

29.

, You

and Liu

, A heterogeneous guided ant colony algorithm based on space explosion and long-short memory, Applied Soft Computing 113 (2021), 107991.

30.

Chen

, You

and Liu

, Ant colony algorithm with stackelberg game and multi-strategy fusion, Applied Intelligence 52 (2021), 6552–6574.

31.

Cao

, Zhang

, Guan

, Zhous

and Wen

, A chaotic ant colony optimized link prediction algorithm, IEEE Transactions on Systems, Man, and Cybernetics: Systems 51 (2021), 5274–5288.

32.

, Ju

, Xu

and Dai

, Collaborative motion planning based on the improved ant colony algorithm for multiple autonomous vehicles, IEEE Transactions on Intelligent Transportation Systems (2023), 1–11.

33.

Yang

, Chen

W.-N.

, Yu

, Gu

, Li

, Zhang

and Zhang

, Adaptive multimodal continuous ant colony optimization, IEEE Transactions on Evolutionary Computation 21 (2017), 191–205.

34.

Uslu

M.F.

, Uslu

and Bulut

, An adaptive hybrid approach: Combining genetic algorithm and ant colony optimization for integrated process planning and scheduling, Applied Computing and Informatics 18 (2020), 101–112.

35.

, Xia

, Huang

and Mahmoodi

, An ant colony optimization algorithm with adaptive greedy strategy to optimize path problems, Journal of Ambient Intelligence and Humanized Computing 13 (2021), 1557–1571.

36.

Miao

, Chen

, Yan

and Wu

, Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm, Computers & Industrial Engineering 156 (2021), 107230.

37.

Luo

, Wang

, Zheng

and He

, Research on path planning of mobile robot based on improved ant colony algorithm, Neural Computing and Applications 32 (2019), 1555–1566.

38.

and Qi

, Ant colony algorithm for path planning based on grid feature point extraction, Journal of Shanghai Jiaotong University 28 (2023), 86–99.

39.

Ajeil

F.H.

, Ibraheem

I.K.

, Azar

A.T.

and Humaidi

A.J.

, Grid-based mobile robot path planning using aging-based ant colony optimization algorithm in static and dynamic environments, Sensors 20 (2020), 1880.

40.

Yang

, Qi

, Miao

, Sun

and Li

, A new robot navigation algorithm based on a double-layer ant algorithm and trajectory optimization, IEEE Transactions on Industrial Electronics 66 (2019), 8557–8566.

41.

Gao

, Tang

, Ye

, Yang

and Yao

, An enhanced heuristic ant colony optimization for mobile robot path planning, Soft Computing 24 (2020), 6139–6150.

42.

Ali

, Gong

, Wang

and Dai

, Path planning of mobile robot with improved ant colony algorithm and MDP to produce smooth trajectory in grid-based environment, Front Neurorobot 14 (2020), 44.

43.

Tharwat

, Elhoseny

, Hassanien

A.E.

, Gabel

and Kumar

, Intelligent Bézier curve-based path planning model using chaotic particle swarm optimization algorithm, Cluster Computing 22 (2018), 4745–4766.

44.

Cheng

, Sha

, He

and Li

, Path planning and obstacle avoidance for AUV: A review, Ocean Engineering 235 (2021), 109355.

45.

Dorigo

, Maniezzo

and Colorni

, Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man and Cybernetics, Part B 26 (1996), 29–41.

46.

, Fu

, Jiang

and Li

, Mobile robots path planning based on 16-directions 24-neighborhoods improved ant colony algorithm, Control and Decision 36 (2021), 1137–1146.

Algorithm	Grid size: 10×10, 20×20, 30×30
	M	K	Q	α	β	ρ	Δ ₁	Δ ₂	δ ₁	δ ₂
ACO-8	50	200	1	1	7	0.3	/	/	/	/
IACO-16(Ref. [46])	50	50	1	1.5	6	0.4	/	/	/	/
IACO-32	50	50	1	1	4	(0.25, 0.7)	1.2	2	0.6	0.4

Whether search directions number affects the efficiency of the path planning algorithm: Taking an improved ACO algorithm with 32 directions for example

Abstract

Keywords

1 Introduction

2 Environmental and problem modeling

2.1 Environmental modeling

2.2.1 Path length

4.1 Search method

5.1 Parameter setting

Table 2 Algorithm parameter settings Algorithm Grid size: 10×10, 20×20, 30×30 M K Q α β ρ Δ 1 Δ 2 δ 1 δ 2 ACO-8 50 200 1 1 7 0.3 / / / / IACO-16(Ref. [46]) 50 50 1 1.5 6 0.4 / / / / IACO-32 50 50 1 1 4 (0.25, 0.7) 1.2 2 0.6 0.4

Table 5 Parameter table of the four strategies Strategy Grid size: 20 × 20 M K Q α β ρ Δ 1 Δ 2 Strategy I 50 150 1 1 7 0.3 / / Strategy II 50 150 1 1 4 0.3 / / Strategy III 50 150 1 9 4 0.3 1.2 2 Strategy IV 50 150 1 1 7 (0.25, 0.7) / /

Acknowledgements

References

Table 2
Algorithm parameter settings

Algorithm Grid size: 10×10, 20×20, 30×30

M K Q α β ρ Δ ₁ Δ ₂ δ ₁ δ ₂

ACO-8 50 200 1 1 7 0.3 / / / /

IACO-16(Ref. [46]) 50 50 1 1.5 6 0.4 / / / /

IACO-32 50 50 1 1 4 (0.25, 0.7) 1.2 2 0.6 0.4

Table 5
Parameter table of the four strategies

Strategy Grid size: 20 × 20

M K Q α β ρ Δ ₁ Δ ₂

Strategy I 50 150 1 1 7 0.3 / /

Strategy II 50 150 1 1 4 0.3 / /

Strategy III 50 150 1 9 4 0.3 1.2 2

Strategy IV 50 150 1 1 7 (0.25, 0.7) / /