Open AccessArticle

Path Planning of Inspection Robot Based on Improved Ant Colony Algorithm

Haixia Wang

Shihao Wang

and

Tao Yu

Department of Mechanical and Electronic Engineering, Shandong University of Science and Technology, Qingdao 266000, China

Author to whom correspondence should be addressed.

Appl. Sci. 2024, 14(20), 9511; https://doi.org/10.3390/app14209511

Submission received: 31 July 2024 / Revised: 13 October 2024 / Accepted: 15 October 2024 / Published: 18 October 2024

Download

Browse Figures

Versions Notes

Abstract

The conventional Ant Colony Optimization (ACO) algorithm, applied to logistics robot path planning in a two-dimensional grid environment, encounters several challenges: slow convergence rate, susceptibility to local optima, and an excessive number of turning points in the planned paths. To address these limitations, an improved ant colony algorithm has been developed. First, the heuristic function is enhanced by incorporating artificial potential field (APF) attraction, which introduces the influence of the target point’s attraction on the heuristic function. This modification accelerates convergence and improves the optimization performance of the algorithm. Second, an additional pheromone increment, calculated from the difference in pheromone levels between the best and worst paths of the previous generation, is introduced during the pheromone update process. This adjustment adaptively enhances the path length optimality. Lastly, a triangle pruning method is applied to eliminate unnecessary turning points, reducing the number of turns the logistics robot must execute and ensuring a more direct and efficient path. To validate the effectiveness of the improved algorithm, extensive simulation experiments were conducted in two grid-based environments of varying complexity. Several performance indicators were utilized to compare the conventional ACO algorithm, a previously improved version, and the newly proposed algorithm. MATLAB simulation results demonstrated that the improved ant colony algorithm significantly outperforms the other methods in terms of path length, number of iterations, and the reduction of inflection points, confirming its superiority in logistics robot path planning.

Keywords:

path planning; ant colony; triangle pruning method; logistics robot; artificial potential field gravity

1. Introduction

In recent years, inspection robots have gained increasing prominence in the public view. As the core component of a factory, workshops must accelerate the digitization and informatization of their processes while improving environmental monitoring to boost operational efficiency and stability. However, traditional workshop inspection equipment often cannot be rapidly upgraded to intelligent systems, and manual inspections are prone to errors such as missed checks, incorrect assessments, and non-adherence to inspection procedures. These shortcomings hinder the timely detection of equipment abnormalities, causing significant disruptions to production management. Workshop inspection robots, with their flexibility and intelligence, offer a solution to these challenges. Historically, path planning has been a central focus in the research of inspection robots, with the primary goal being the design of an optimal trajectory from the start point to the target location, while effectively navigating around obstacles [1]. In complex outdoor environments, inspection robots not only require advanced hardware but also highly adaptable algorithms [2]. Based on path search principles, path planning can be divided into traditional algorithms [3], such as the Dijkstra algorithm [4], artificial potential field method [5], A* algorithm [6], and Voronoi diagram method [7], and more advanced optimization algorithms, including ant colony optimization [8], particle swarm optimization [9], and genetic algorithms [10].

Since its introduction by Dorigo M., the ant colony optimization (ACO) algorithm [11] has been extensively applied across various fields [12], with path planning being one of its most notable applications. However, the algorithm often exhibits slow convergence and a tendency to become trapped in suboptimal solutions. To overcome these limitations, numerous researchers have proposed modifications to improve the ACO algorithm for route optimization problems [13]. For instance, the study in [14] integrates the heuristic search strategy of the A* algorithm into ACO to address issues such as paths being too close to obstacles, slow convergence, and the presence of redundant nodes. To avoid local optima and enhance the convergence rate when dealing with concave obstacles, several researchers have suggested improvements, including locking the relationship between the α (pheromone heuristic factor) and β (expectation heuristic factor), as well as dynamically adjusting these parameters. In addition, [15] proposes an improved pheromone update rule to achieve more optimal solutions. The study in [16] addresses the issue of search inefficiency by dividing the environment into three regions, using a distance ratio method to allocate pheromones, and employing the “wolf pack allocation strategy” to adjust pheromone updates, which significantly accelerates path optimization. Furthermore, [17] introduces a heuristic function to evaluate the angular measurements formed by feasible nodes, the endpoint, and the starting point, while modifying the distance heuristic function to enhance the search efficiency of ACO-based algorithms [18]. This improvement, alongside optimized pheromone increments allocated to better paths, significantly enhances the efficiency of the path search process.

In this work, we propose an innovative improvement to the conventional ant colony optimization (ACO) algorithm to address its limitations in logistics robot path planning, specifically in a two-dimensional grid environment. The key contributions of our research are as follows: (1) We enhance the heuristic function by incorporating artificial potential field attraction [19], which effectively accelerates convergence and improves optimization performance. (2) We introduce an adaptive pheromone update mechanism [20] that takes into account the difference between the pheromone levels of the best and worst paths, thereby increasing the likelihood of discovering a globally optimal path and preventing stagnation in local optima. (3) We apply a triangle pruning method to reduce redundant turning points in the planned path, making the route more efficient and easier for the robot to follow. Through extensive simulation experiments in different grid-based scenarios, our improved algorithm demonstrates significant advantages in terms of path length, iteration times, and reduced inflection points, outperforming traditional ACO and other benchmark algorithms. These contributions represent a substantial step forward in improving the efficiency and reliability of path planning for logistics robots.

The improved ant colony optimization (ACO) algorithm [21] has a wide range of practical applications across various domains. First, in computer networks, ACO can be employed for dynamic routing to optimize data packet transmission paths, thereby improving overall network performance. Second, in the manufacturing and service industries, the algorithm is useful for task scheduling and resource allocation, enhancing efficiency in production processes. Moreover, the improved ACO is highly effective in solving the Traveling Salesman Problem (TSP) [22], enabling logistics companies to optimize delivery routes and reduce transportation costs. Additionally, in the field of image processing, ACO contributes to image segmentation and feature extraction, resulting in enhanced image quality and improved recognition accuracy. Finally, in electric load scheduling and power grid optimization, the algorithm plays a critical role in resource allocation, reducing energy consumption and improving system stability.

2. Problem Description

2.1. Establishment of Environmental Model

The scenario described involves a patrol robot moving on a 2D plane at a constant speed from an initial point to a designated destination. The robot’s motion trajectory on a 2D grid-structured map is represented as a series of continuous positions. This grid-based approach to environmental mapping is straightforward to implement and intuitive, making it a common technique for representing the surroundings of patrol robots. In this scenario, the environment is divided into a 20 × 20 grid, where each grid cell is classified as either an obstacle (represented by a black cell with a value of 1) or free space (represented by a white cell with a value of 0). The operational zone contains O obstacles, and the autonomous patrol vehicle must navigate around these obstacles to ensure a safe and successful journey. The grid map Z is composed of grid cells

Z_{i j}

, where i and j denote the row and column indices, respectively.

Z = \{Z_{i j} | Z_{i j} = S, 0,1, E\}

In this grid map,

Z_{i j} = S

represents the initial matrix of the delivery autonomous vehicle,

Z_{i j} = 0

represents a free grid,

Z_{i j} = 1

represents an obstacle grid, and

Z_{i j} = E

represents the target grid.

2.2. Traditional Ant Colony Algorithm

The traditional ant colony optimization algorithm is a bio-inspired intelligent optimization method that emulates the foraging behavior of ants in their natural habitat. During the foraging process, ants deposit chemical pheromones along the routes they traverse, and subsequent ants are more likely to select paths with higher concentrations of these pheromones [23].

In the conventional ant colony algorithm, the following formula defines the transition probability:

Q_{i j}^{k} (t) = \{\begin{matrix} \frac{{[ω_{i j} (t)]}^{α} {[γ_{i j} (t)]}^{β}}{\sum_{{s = a l l o w e d}_{k}} {[ω_{i j} (t)]}^{α} {[γ_{i j} (t)]}^{β}}, j \in {a l l o w e d}_{k} \\ 0, o t h e r w i s e \end{matrix}

(1)

The Formula (1) represents the probability;

Q_{i j}^{k} (t)

: the probability that ant k will move from node i to node j at time t.

ω_{i j} (t)

: the pheromone concentration on the edge (path) between nodes i and j at time t. Paths with higher pheromone concentrations are more likely to be chosen.

α

: the parameter that controls the influence of pheromones on the decision-making process. A larger

α

value means more reliance on pheromone trails.

β

: the parameter that controls the influence of the heuristic value (typically distance). A larger

β

value means that the ant is more likely to prioritize shorter paths.

{a l l o w e d}_{k}

: the set of feasible nodes that ant k can move to from its current position (nodes that have not yet been visited.

The first part of the formula applies to paths within the set of allowed nodes for the ant, indicating that the ant has not yet visited these nodes. The probability of selecting a path is a function of both the pheromone level and the heuristic value (such as distance). The denominator serves to normalize the probability by summing over all possible nodes to which the ant can move.

The second part of the formula applies to nodes that the ant cannot access (those that have already been visited), thereby ensuring that the ant does not revisit these nodes.

γ_{i j} (t)

: the heuristic value, typically the inverse of the distance between nodes i and j. This encourages ants to favor shorter paths. The expression is as follows:

\begin{matrix} γ_{i j} (t) = \frac{1}{d_{i j}} \end{matrix}

(2)

d_{i j}

indicates the Euclidean distance from node i to node j; Formula (3) illustrates the Euclidean distance.

\begin{matrix} d_{i j} = \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}} \end{matrix}

(3)

The pheromone update expression is as follows:

\begin{matrix} ω_{i j} (t + n) = (1 - σ) \cdot ω_{i j} + ∆ ω_{i j} \end{matrix}

(4)

∆ ω_{i j} (t) = \sum_{k = 1}^{m} ∆ ω_{i j}^{k} (t)

(5)

\begin{matrix} ∆ ω_{i j}^{k} (t) = \{\begin{matrix} Q / L_{k}, & The path of ant k through this iteration < i, j > \\ 0, & other \end{matrix} \end{matrix}

(6)

In the formula,

σ

denotes the chemical signals evaporation rate, and

1 - σ

is the retention factor following chemical signals evaporation, ranging in value from 0 to 1.

∆ ω_{i j} (t)

is the overall amount of chemical signals increments deposited by M ants on path nodes <i, j> after one iteration, and

∆ ω_{i j}^{k} (t)

is the pheromone residue left on nodes <i, j> by the k-th ant. Q is a constant, representing the pheromone intensity coefficient, and

L_{k}

is the k-th ant’s path distance during this iteration. The settings for each parameter are shown in Table 1.

3. Improved Ant Colony Algorithm

3.1. Improved Heuristic Information Function

The conventional ant colony optimization algorithm has several limitations. At the beginning of the search, the chemical trail levels are identical across all paths, making the heuristic information the primary differentiator. However, the original formula for path selection heuristics lacks robustness, leading to a blind search and suboptimal initial paths. Additionally, while the algorithm’s positive feedback mechanism is effective in reinforcing favorable paths, it can result in slow search progress during the early stages and may cause the algorithm to become trapped in local optima.

To address these challenges, this paper proposes modifying the heuristic information function by incorporating an artificial potential field force. This adjustment aims to enhance the targeting of the heuristic function’s evaluation toward the goal and improve search efficiency. The improved heuristic information

γ_{i j} (t) *

is defined as follows:

\begin{matrix} γ_{i j} (t) * = \frac{ψ}{d_{i j}} \end{matrix}

(7)

ψ = μ^{f a}

(8)

f a = φ \cdot d (j, E)

(9)

Substitute (1) (2) (3) into the expected heuristic information to obtain

{γ_{i j} (t)}^{*}

γ_{i j} (t) * = \frac{μ^{φ \cdot d (j, E)}}{d_{i j}}

(10)

Among these parameters,

ψ

is the factor added to the artificial potential field gravity;

f a

represents the artificial field of potential gravity from the present node j to the destination point;

μ

is a constant with a value range of (0,1); and

φ

is a proportional coefficient.

d (j, E)

denotes the gap from the present node j to the destination point E. With increasing distance, the potential energy level for the inspection robot rises; conversely, the lesser the distance, the lesser the potential energy level.

3.2. Improved Pheromone Update Rules

In the classical ant colony optimization algorithm, as the iteration count increases, the chemical signal levels on the map gradually rise, prompting ants to increasingly follow paths with higher pheromone concentrations. This phenomenon can lead to the algorithm becoming trapped in local optima. To address this issue, this paper proposes an adaptive pheromone update mechanism. Specifically, in addition to the original pheromone update increment, the proposed approach incorporates the disparity between the total pheromone levels on the most effective route from the previous generation and the total pheromone levels on the least optimal route from the same generation. The adaptive pheromone update

{ω_{i j} (t)}^{*}

is expressed as follows (11):

ω_{i j} (t + 1) * = (1 - σ) \cdot ω_{i j} + ∆ ω_{i j} (t) + ∆ ω_{i j}^{*} (t)

(11)

∆ ω_{i j}^{*} (t) = \sum_{k = 1}^{m} ∆ * ω_{i j}^{k} (t)

(12)

∆ * ω_{i j}^{k} (t) = ϑ \times \frac{Q}{L_{m i n}} - ν \times \frac{Q}{L_{m a x}}

(13)

In the formula,

∆ ω_{i j}^{*} (t)

represents the disparity between the sum of chemical signals deposited by ants on the ideal path and the aggregate of chemical signals deposited by ants on the least effective path, serving as a supplementary pheromone increase.

∆^{*} ω_{i j}^{k} (t)

is the pheromone increment left by the kkkth ant on paths i and j.

ϑ

denotes the quantity of ants on the best route for this iteration,

ν

is the quantity of ants on the least optimal route for this iteration,

L_{m i n}

is the distance of the optimal trajectory for this round, and

L_{m a x}

is the length of the least optimal route for this round. The pseudocode for the improved ant colony path planning algorithm is shown as Algorithm 1.

Algorithm 1. Improved ant colony path planning algorithm

initialize environment and parameters
for each node i in the environment:
calculate distance between node i and the target node E
calculate potential attraction fa = sigma * (distance squared)
if node i is not the target node:
Eta(i) = (0.5 ^ fa)/sqrt(distance squared)
else:
Eta(i) = a very large number
for each ant k in K ants:
for each iteration m:
if ant k completes a path in iteration m:
calculate path length PL_km
update pheromone matrix Delta_Tau considering path length PL_km, best path length minkl, and worst path length maxkl
for each step s in the path:
x, y = current step, next step
Delta_Tau(m, n) += Q / PL_km + b * Q / minkl-w * Q / maxkl
Tau = (1-Rho) * Tau + Delta_Tau

3.3. Path Optimization and Update

The presence of unnecessary line segments and excessive bends in the explored path not only increases the overall length of the planned route but also requires the patrol robot to execute multiple turns and changes in direction during motion. This complexity is not conducive to fast and efficient navigation.

The Total Triangle Pruning Algorithm is typically employed to optimize combinatorial problems, particularly in addressing specific graph or path issues. The core principle of this algorithm is to reduce the search space through pruning, thereby enhancing solving efficiency.

1. Triangle relationship: This property utilizes the characteristics of triangles to determine that certain paths or combinations are redundant and can be pruned. For instance, if the cost from point A to point C exceeds the sum of the costs from A to B and from B to C, then the path from A to C can be eliminated.

2. Pruning rules: Specific pruning rules are established to quickly identify which portions can be excluded during the search process. This is achieved by comparing the total cost of the current path with that of existing paths.

3. Search algorithm: search strategies such as Depth-First Search (DFS) or Breadth-First Search (BFS) are combined with pruning techniques to systematically explore the effective solution space.

4. Optimized results: by reducing unnecessary calculations through pruning, the algorithm increases the solving speed, ultimately yielding an optimized solution.

The search rules of the ant colony algorithm on the grid map constrain the path search to directions that are multiples of

\frac{π}{4}

, limiting the movement to either 1 or

\sqrt{2}

search steps, as illustrated by the solid black line in Figure 1. In this figure, the segment A-B-C-D, represented by the solid black line, indicates the most direct route found by the computational method, while the segments A-B (solid black line) and B-D (dashed blue line) depict the actual driving paths of the logistics robot. Consequently, the current approach has not yet identified the minimal distance path for the patrol robot. To address these issues, the triangle pruning method can effectively eliminate unnecessary turning points and line segments. The core concept involves connecting neighboring turning points of the initial path. If the connecting line does not intersect with any obstacles, the unnecessary turning points and segments between the two nodes are removed, and the path is updated accordingly.

Let φ be the set of checkpoints,

P = {P_{1}, P_{2}, \dots, P_{n}}

be the set of turning points in the path that requires optimization, R be the set of all points on the line connecting the turning point

P_{i}

of checkpoint φ_i to be checked, and T be the set of obstacles. The optimization process begins by adding the first turning point

P_{1}

to the checkpoint set

φ

. The turning points in P are then sequentially connected to the first element in the set

φ

, and the points on the connecting line are added to the set R. If

T \cap R = \emptyset

, the connection is deemed valid; if

T \cap R \neq \emptyset

, the connection is discarded. This process continues as elements in the set P are added to the first position in

φ

for verification, until all elements in P have been incorporated into

φ

and the verification is complete. Upon evaluating all the turning nodes in sequence, the path optimization is concluded, resulting in the optimized path points, as illustrated in Figure 1, represented by A-B-D.

The pseudocode for the triangle pruning algorithm is shown as Algorithm 2.

Algorithm 2. Triangle pruning algorithm

function isPathFeasible(G, i, j):
if not isOK(G, i, j):
return False
return True
function is OK(G, i, j):
ix, iy = convertToCoordinates(i)
jx, jy = convertToCoordinates(j)
for each point (m, n) along the line from i to j:
if istouch(i, j, x, y):
if isobstacles(G, x, y):
return False
return True
function istouch(i, j, x, y):
return intersects(i, j, x, y)
function isobstacles(G, x, y):
if G[x, y] == 1:
return True
return False
function convertToCoordinates(point):
x = calculateXCoordinate(point)
y = calculateYCoordinate(point)
return x, y
function intersects(i, j, x, y):
intersects cell at (x, y)

3.4. Improved Pheromone Update Rule and Mathematical Analysis of Convergence

3.4.1. The Pheromone Update Formula in the Original Ant Colony Optimization Algorithm

In the classical ant colony optimization algorithm, the pheromone update formula is as follows:

ω_{i j} (t + 1) = (1 - σ) \cdot ω_{i j} + ω_{i j} (t) + ∆ ω_{i j} (t)

(14)

where

ω_{i j} (t)

represents the pheromone concentration between node i and node j at time t.

σ

: the pheromone evaporation rate, denoted as

σ

, satisfies (0 <

σ

< 1).

∆ ω_{i j} (t)

: the additional pheromone quantity accumulated by all ants on the path (i, j) during this iteration is defined as:

Δ ω_{i j} (t) = \sum_{k = 1}^{m} Δ ω_{i j}^{k} (t)

(15)

Δ ω_{i j}^{k} (t) = \frac{Q}{L_{k}}

(16)

where

Q

is the pheromone intensity coefficient, and

L_{k}

represents the path length found by the k-th ant.

3.4.2. The Improved Pheromone Update Formula

To accelerate the convergence speed of the algorithm, this paper proposes an improved pheromone update rule designed to enhance global search capabilities. This enhancement is achieved by incorporating the differences between the best and worst paths into the pheromone update process. The improved pheromone update formula is expressed as follows:

ω_{i j} (t + 1)^{*} = (1 - σ) \cdot ω_{i j} (t) + Δ ω_{i j} (t) + Δ ω_{i j}^{*} (t)

(17)

where

Δ ω_{i j}^{*} (t)

: the additional pheromone update amount based on the differences between the best and worst paths, used to enhance the probability of selecting the optimal path.

Δ ω_{i j}^{*} (t) = ϑ \times \frac{Q}{L_{m i n}} - ν \times \frac{Q}{L_{m a x}}

(18)

L_{m i n}

: the shortest path length found by all ants in the current iteration.

L_{m a x}

: the longest path length found by all ants in the current iteration.

ϑ

and

ν

: represent the weight factors for the optimal and worst paths, respectively, used to adjust the increase and decrease of the additional pheromone.

3.4.3. Convergence Analysis of the Improved Algorithm

The improved pheromone update formula introduces an additional term,

Δ ω_{i j}^{*} (t)

, which strengthens the correlation between the pheromone concentration on a given path and its performance in the previous generation. For the shortest path, a larger amount of pheromone is deposited, thereby increasing the likelihood of that path being selected in subsequent iterations. Conversely, for the worst-performing path, the pheromone concentration is decreased, reducing its probability of being chosen. This adjustment aids in preventing the algorithm from becoming trapped in local optima, thereby enhancing overall search efficiency.

Mathematical comparison of convergence speed; in the classic ant colony optimization (ACO) algorithm, the transition probability for path selection is determined by the following formula:

P_{i j} (t) = \frac{{(ω_{i j} (t))}^{α} {(η_{i j})}^{β}}{\sum_{k \in a l l o w e d} {(ω_{i k} (t))}^{α} {(η_{i k})}^{β}}

(19)

α

: controls the importance of pheromone concentration in path selection.

β

: controls the importance of heuristic information in path selection.

In the improved formula, the incorporation of the difference between the best and worst paths through

Δ ω_{i j}^{*} (t)

leads to a more rapid rate of change in pheromone concentration, particularly for the optimal path. As a result, for the optimal path (i, j), the pheromone concentration increases after each iteration according to the following expression:

ω_{i j} (t + 1)^{*} > (1 - σ) \cdot ω_{i j} (t) + \sum_{k = 1}^{m} \frac{Q}{L_{m i n}} - ν \cdot \frac{Q}{L_{m a x}}

(20)

Compared to the original formula, the increase of

ω_{i j} (t + 1) *

is more significant, which makes the path selection probability

P_{i j} (t)

more inclined to choose the better paths, thereby accelerating the convergence speed of the algorithm.

3.4.4. Theoretical Proof of Convergence

To demonstrate that the improved algorithm exhibits faster convergence compared to the original algorithm, we can consider the following points:

1. Increased pheromone concentration differences: The improved pheromone update rule enhances pheromone levels for optimal paths while reducing them for suboptimal paths. This creates a greater disparity in pheromone concentrations among different paths. As a result, ants are more likely to select the optimal path during route selection, thereby reducing the randomness of the search process. This targeted exploration effectively accelerates convergence.

2. Bellman equation and expected path length: According to the Bellman equation, the expected path length decreases with each iteration. In the improved pheromone update rule, the rapid adjustment of pheromone concentrations facilitates the repeated selection of optimal paths. This can be likened to the introduction of a reward function term in the Bellman equation, enabling the expected path length

E [L]

to decrease at a faster rate:

E [L] (t + 1) < E [L] (t) - ϑ \cdot \frac{Q}{L_{m i n}} + ν \cdot \frac{Q}{L_{m a x}}

(21)

The reduction in the expected path length occurs at a significantly faster rate compared to the classical ant colony optimization algorithm. Consequently, under the same number of iterations, the improved algorithm converges more rapidly toward the optimal solution.

3.4.5. Conclusions of Mathematical Analysis

Through mathematical derivation, it can be demonstrated that the improved pheromone update rule provides significant convergence advantages over the original ant colony optimization algorithm:

1. Increased pheromone concentration difference: this improvement enhances the directional guidance in path selection.

2. Faster reduction in expected path length: the algorithm achieves the optimal solution with fewer iterations.

The above derivation illustrates that the improved ant colony algorithm not only effectively avoids the trap of local optima but also significantly accelerates convergence. This is accomplished by considering the differences between the best and worst paths during the pheromone update process, which enhances the optimal path while suppressing the influence of suboptimal paths.

3.5. Algorithm Flow

Step 1: Establish a grid environment model. Create a grid model of the grid-based model for the logistics robot environment. Set up free grids, obstacle grids, and define the grid parameters. Set the coordinates for the initial point S and the destination point E.

Step 2: Initialize the fundamental parameters. Initialize the algorithm’s maximum number of iterations K, the count of ants M in the ant colony, the importance factor of pheromone α, the importance factor of heuristic information β, the pheromone evaporation coefficient ρ, and other relevant parameters.

Step 3: Select path nodes. Ant k selects the next feasible node on the route following the formula for transition probability (1), logs the visited nodes in the tabu list

T A B U_{k}

, and continues this process until ant k reaches the target point. This step is repeated until all M ants in the current iteration have completed their search.

Step 4: Record the distance of each route and the count of ants. Record the route traversed by each one of the ants and the extent of the path traversed in the current iteration. Additionally, record the total ant count on each trajectory from the starting point to the target point, and store this information in the

C E L L

database.

Step 5: Update pheromone. Using the tabu list

T A B U_{k}

and the data in

C E L L

, find the highest quality route and the lowest quality route in the current cycle and size of the ant colony on each route. Update pheromone density according to Equations (11)–(13).

Step 6: Complete the iteration by verifying if the algorithm has met the highest allowed count of iterations. If so, output the most effective path. In other cases, clear the tabu list

T A B U_{k}

and repeat from step 3 for the next iteration.

Step 7: Optimize the route. For the obtained optimal path, perform optimization using the triangle pruning method to obtain a simplified route.

4. Experimental Simulation and Analysis

To validate the capabilities and practicality of the improved ant colony algorithm proposed in this study, simulation experiments are conducted in two grid settings with varying degrees of complexity. The proportion of obstacle grids is maintained at no less than 20% of the total grid count. The results are evaluated against those obtained from the traditional algorithm and the improved ant colony algorithm referenced in [12], utilizing four key performance indicators. The testing environment comprises a CPU with a 2.10 GHz Intel(R) Core(TM) i7-14700HX processor and the MATLAB R2023b simulation platform. The parameter settings for the simulation are outlined in Table 2.

4.1. 20 × 20 Simulation Results and Analysis

Figure 2 illustrates the results of path planning and convergence trends for the three algorithms tested in a 20 × 20 static grid environment. In panel (e), the red path indicates the route prior to the application of triangle pruning optimization, while the blue route represents the refined path after unnecessary nodes have been removed. The convergence curve for the potential field ant colony algorithm shows the iteration path length on the vertical axis, allowing for a comparison of the iteration count when the paths are similar. The horizontal axis represents the iteration count, with shorter iteration counts indicating a tendency toward stabilization. The traditional ant colony algorithm demonstrates inadequate guidance during the initial stages due to the heuristic function, resulting in more turning points, longer search paths, and a higher likelihood of becoming trapped in local optima. The improved ant colony algorithm referenced in [12] updates and reassigns the pheromone concentration based on local path information to expedite local optimization, yielding relatively good planned paths. However, it still requires multiple iterations, resulting in a slower convergence speed. In contrast, the improved ant colony algorithm presented in this paper incorporates the influence of artificial potential field force, enhancing guidance toward the target. Additionally, it employs the triangle pruning method for secondary processing of the planned path, which facilitates faster convergence and fewer turning points. According to the data in Table 2, the optimal path length achieved by the traditional ant colony algorithm is 31.17 m, stabilizing after 23 iterations. The improved ant colony algorithm from [12] stabilizes after 12 iterations, with an optimal path length reduced to 29.79 m. In comparison, the improved ant colony algorithm proposed in this research stabilizes after just five iterations, achieving an optimal path length of 28.96 m. These results indicate that the improved ant colony algorithm presented in this study converges quickly and significantly reduces the number of turning points compared to the other two algorithms.

As shown in the comparative results in Table 3, even though each of the three algorithms can successfully complete the path planning from the start to the destination, there are significant differences in algorithm performance as reflected by the indicators. Compared to the traditional ant colony algorithm, the improved ant colony algorithm in [12] shortens the best path length by 4.42%, the count of turning points by 13.63%, and the count of iterations by 10%. The improved ant colony algorithm presented in this research performs considerably superior to the traditional ant colony algorithm. It reduces the minimum path length by 7.09%, and more importantly, it decreases the count of iterations and turning points by 47.8% and 78.2%, respectively. This improvement enhances search efficiency and effectiveness, making it better suited to the practical requirements of inspection robot route planning.

4.2. 30 × 30 Simulation Results and Analysis

To further validate the advantages of the improved algorithm proposed in this research, path planning was conducted using all three algorithms in a more complex 30 × 30 static grid. The resulting paths and convergence curves are illustrated in Figure 3. Due to the larger grid environment and the increased number of obstacles, the performance indicators of the algorithms have varied to different extents. As shown in Table 3, the traditional ant colony algorithm exhibited the poorest performance in the 30 × 30 environment. It required 33 iterations to converge and stabilize, resulting in a path length of 66.18 m and 34 turning points. In comparison, the improved ant colony algorithm referenced in [12] introduces a mutation operation akin to those found in evolutionary algorithms. This adjustment allows for the reassignment of pheromone concentrations on certain paths, thereby enhancing its ability to evade local optima and improving global search capabilities. This algorithm converged after 21 iterations, achieving a path length of 44.52 m and 18 turning points. The improved ant colony algorithm presented in this study incorporates artificial potential field force into the heuristic function and employs a “self-adjusting” pheromone concentration update rule. This approach enables faster convergence, achieving an optimal path length of 43.46 m with only 15 iterations and 13 turning points. These results further demonstrate the efficacy of the improved ant colony algorithm proposed in this research.

A comparison of the data presented in Table 4 reveals that the improved ant colony algorithm developed in this research achieved a path length reduction of 32.72% and 34.33% compared to the traditional ant colony algorithm and the enhanced ant colony algorithm in [12], respectively. Additionally, the proposed algorithm decreased the number of iterations by 36.36% relative to the traditional algorithm and by 54.55% compared to the algorithm in [12]. Furthermore, the volume of turning points was reduced by 47.06% and 61.76%, respectively. Although the improved ant colony algorithm in [12] significantly enhanced path planning length and execution time compared to the traditional algorithm, it still necessitates further refinement concerning the number of iterations. In contrast, the algorithm presented in this paper demonstrates marked superiority over both prior algorithms, showcasing its capability to plan optimal paths with exceptional stability and adaptability in complex environments.

4.3. 50 × 50 Simulation Results and Analysis

To evaluate the performance of three algorithms under increased environmental complexity, path planning was conducted in an expanded 50 × 50 static grid with randomly distributed obstacles, while maintaining consistent parameters across all tests. The resulting paths and convergence curves are illustrated in Figure 4. The traditional ant colony algorithm required 34 iterations to converge, achieving a path length of 120.25 m with 54 turning points. In contrast, the improved ant colony algorithm from reference [12] converged after 30 iterations, reducing the path length to 65.74 m with 28 turning points.

The improved ant colony algorithm proposed in this paper, which incorporates artificial potential field attraction into the heuristic function, demonstrated superior performance, converging in only 25 iterations. This resulted in an optimal path length of 60.79 m with 20 turning points. These results further confirm the effectiveness and reliability of the proposed algorithm in optimizing path planning in complex environments.

The data presented in Table 5 highlights the performance improvements achieved by the proposed ant colony algorithm. Compared to the traditional ant colony algorithm, the path length was reduced by 45.33%, while a 49.45% reduction was observed in comparison to the improved algorithm from reference [12]. Additionally, the number of iterations decreased by 11.76% and 26.47%, respectively. The number of turning points was reduced by 48.15% compared to the traditional algorithm and by 62.96% relative to the improved algorithm in reference [12].These results clearly demonstrate the significant advantages of the algorithm proposed in this paper, which is capable of planning optimal paths in complex and diverse environments. Furthermore, the algorithm exhibits excellent stability and adaptability across a range of conditions, outperforming the other two algorithms in terms of both efficiency and reliability.

5. Experimental Verification

The inspection robot utilized in this experiment is constructed on an R5 series Ackermann chassis, featuring a four-wheel drive system equipped with 125 mm rubber wheels. It is powered by an STM32 microcontroller and utilizes a JETSON NANO as the main control board. The robot is outfitted with various sensors, including a binocular camera, an inertial measurement unit (IMU), and a 2D lidar system, which collectively facilitate precise environmental perception and navigation.

To rigorously assess the reliability and authenticity of the improved algorithm presented in this research, the algorithm was implemented within the Ubuntu 18.04 Melodic operating system, employing the ROS (Robot Operating System) for robotic control. A simulated environment for the four-wheel Ackermann robot was developed in Gazebo. Figure 5 illustrates the planned path.

The physical verification of the improved inspection robot is shown in Figure 6 below.

A real simulation environment incorporating multiple obstacles was constructed to evaluate the performance of the inspection robot. The robot was assigned 2D Nav Goal commands to autonomously navigate to specified target points. The time taken to complete the task was recorded at three intervals, clearly demonstrating the robot’s ability to plan the most efficient path in a complex environment, while autonomously inspecting and avoiding obstacles. These results were further validated through comparison with the contents verified by the Robot Operating System (ROS), confirming the reliability and authenticity of the proposed algorithm.

As shown in the comparison of positions in Table 6, the path length of the improved ant colony algorithm presented in this research was reduced by 33% compared to the traditional ant colony algorithm. Additionally, the quantity of turning points was cut by 50%, and the running time was shortened by 49%. The discrepancy between the simulation results and the tabulated values is within ±5%. Therefore, the algorithm in this research has a significant advantage over the traditional ant colony algorithm. It can plan the most streamlined path in a challenging environment, perform autonomous patrols, and avoid obstacles, verifying the authenticity and reliability of the algorithm.

6. Conclusions

This paper proposes an improved ant colony algorithm to overcome the difficulties associated with slow convergence, excessive turning points, and susceptibility to local optima in the path planning process for patrol robots in a stationary 2D grid environment. Considering the simulation outcomes of the overall path and various performance indicators, the following insights are obtained:

1. By enhancing the heuristic function and pheromone update rule of the traditional ant colony algorithm, and by addressing redundant nodes in the path, the enhanced ant colony algorithm presented in this research demonstrates notable advantages. In two grid environments with varying complexities, it outperforms the other two algorithms in terms of convergence efficiency, optimization ability, number of turning points, and environmental adaptability.

2. While the improved ant colony algorithm in this paper shows significant improvements in various performance metrics, it has not achieved a decrease in execution time compared to the traditional ant colony algorithm, and it is tested within a static 2D grid framework. The next course of action will focus on reducing the algorithm’s running time and addressing the challenge of dynamic obstacle avoidance in local contexts.

Author Contributions

Conceptualization, S.W.; methodology, S.W.; software, S.W.; validation, S.W.; formal analysis, S.W.; investigation, S.W. and T.Y.; writing—original draft preparation, S.W.; writing—review and editing, S.W. and H.W. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

The data presented in this study are available on request from the corresponding author due to privacy.

Conflicts of Interest

The authors declare no conflicts of interest.

References

Qin, H.; Shao, S.; Wang, T. Review of autonomous path planning algorithms for mobile robot. Drones 2023, 7, 211. [Google Scholar] [CrossRef]
Liu, L.; Wang, X.; Yang, X. Path planning techniques for mobile robots: Review and prospect. Expert Syst. Appl. 2023, 227, 120254. [Google Scholar] [CrossRef]
Luo, M.; Hou, X.; Yang, J. Surface optimal path planning using an extended Dijkstra algorithm. IEEE Access 2020, 8, 147827–147838. [Google Scholar] [CrossRef]
Guo, T.; Wang, J.; Wang, Z. Research on path planning of mobile robot with a novel improved artificial potential field algorithm. Math. Probl. Eng. 2022, 2022, 5692350. [Google Scholar] [CrossRef]
Liu, L.; Wang, B.; Xu, H. Research on path-planning algorithm integrating optimization A-star algorithm and artificial potential field method. Electronics 2022, 11, 3660. [Google Scholar] [CrossRef]
Kim, M.; Kang, T.; Ryoo, K. Real-Time Path Planning for Unmanned Aerial Vehicles Based on Compensated Voronoi Diagram. Int. J. Aeronaut. Space Sci. 2024. [Google Scholar] [CrossRef]
Xiao, J.; Yu, X.; Sun, K. Multiobjective path optimization of an indoor AGV based on an improved ACO-DWA. Math. Biosci. Eng. 2022, 19, 12532–12557. [Google Scholar] [CrossRef]
Yuan, Q.; Sun, R.; Du, X. Path planning of mobile robots based on an improved particle swarm optimization algorithm. Processes 2022, 11, 26. [Google Scholar] [CrossRef]
Chen, Z.; Xiao, J.; Wang, G. An effective path planning of intelligent mobile robot using improved genetic algorithm. Wirel. Commun. Mob. Comput. 2022, 2022, 9590367. [Google Scholar] [CrossRef]
Du, G.; Ma, H.; Bai, Y. Process Planning for Large Container Ship Propeller Shaft Machining Based on an Improved Ant Colony Algorithm. J. Mar. Sci. Eng. 2024, 12, 841. [Google Scholar] [CrossRef]
Wu, P.; Wang, Y.; Wang, B. An ant colony algorithm for drone path planning. In Proceedings of the 2020 5th International Conference on Mechanical, Control and Computer Engineering (ICMCCE), Harbin, China, 25–27 December 2020; pp. 1559–1562. [Google Scholar] [CrossRef]
Liu, Z.; Jin, S.; Wang, Q. 2D path planning of mobile robots based on improved ant colony algorithm. Transducer Microsyst. Technol. 2020, 39, 149–152. [Google Scholar]
Luo, Q.; Wang, H.; Zheng, Y. Research on path planning of mobile robot based on improved ant colony algorithm. Neural Comput. Appl. 2020, 32, 1555–1566. [Google Scholar] [CrossRef]
Jin, Q.; Tang, C.; Cai, W. Research on dynamic path planning based on the fusion algorithm of improved ant colony optimization and rolling window method. IEEE Access 2021, 10, 28322–28332. [Google Scholar] [CrossRef]
Tang, Z.; Ma, H. Path guidance method for unmanned vehicle based on improved potential field ant colony algorithm. Int. J. Veh. Des. 2022, 89, 84–97. [Google Scholar] [CrossRef]
Huo, F.; Zhu, S.; Dong, H. A new approach to smooth path planning of Ackerman mobile robot based on improved ACO algorithm and B-spline curve. Robot. Auton. Syst. 2024, 175, 104655. [Google Scholar] [CrossRef]
Bai, X.; Liu, D.; Xu, X. A Review of Improved Methods for Ant Colony Optimization in Path Planning. J. Ship Res. 2024, 22, 77–92. [Google Scholar] [CrossRef]
Han, B.; Qu, T.; Tong, X. Grid-optimized UAV indoor path planning algorithms in a complex environment. Int. J. Appl. Earth Obs. Geoinf. 2022, 111, 102857. [Google Scholar] [CrossRef]
Zhang, Y.; Chen, J.; Chen, M. Integrated the Artificial Potential Field with the Leader–Follower Approach for Unmanned Aerial Vehicles Cooperative Obstacle Avoidance. Mathematics 2024, 12, 954. [Google Scholar] [CrossRef]
Shan, D.; Zhang, S.; Wang, X. Path-Planning Strategy: Adaptive Ant Colony Optimization Combined with an Enhanced Dynamic Window Approach. Electronics 2024, 13, 825. [Google Scholar] [CrossRef]
Cai, Z.; Liu, J.; Xu, L. Cooperative path planning study of distributed multi-mobile robots based on optimised ACO algorithm. Robot. Auton. Syst. 2024, 179, 104748. [Google Scholar] [CrossRef]
Majumder, S.; Singh, A. An evolution strategy with tailor-made mutation operator for colored balanced traveling salesman problem. Appl. Intell. 2024, 1, 13. [Google Scholar] [CrossRef]
Xue, T.; Li, L.; Shuang, L. Path planning of mobile robot based on improved ant colony algorithm for logistics. Math. Biosci. Eng. 2021, 18, 3034–3045. [Google Scholar] [CrossRef] [PubMed]

Figure 1. The principle of triangle pruning method.

Figure 2. A 20 × 20 algorithm simulation comparison. (a) Path planning of the traditional ant colony algorithm. (b) Convergence curve of the traditional ant colony algorithm. (c) Literature [12] improved the ant colony algorithm for path planning. (d) Literature [12] improved the convergence curve of the ant colony algorithm. (e) This paper improves the path planning of the ant colony algorithm. (f) This paper improves the convergence curve of the ant colony algorithm.

Figure 3. A 30 × 30 algorithm simulation comparison. (a) Path planning of the traditional ant colony algorithm. (b) Convergence curve of the traditional ant colony algorithm. (c) Literature [12] improved the ant colony algorithm for path planning. (d) Literature [12] improved the convergence curve of the ant colony algorithm. (e) This paper improves the path planning of the ant colony algorithm. (f) This paper improves the convergence curve of the ant colony algorithm.

Figure 4. A 50 × 50 algorithm simulation comparison. (a) Path planning of the traditional ant colony algorithm. (b) Convergence curve of the traditional ant colony algorithm. (c) Literature [12] improved the ant colony algorithm for path planning. (d) Literature [12] improved the convergence curve of the ant colony algorithm. (e) This paper improves the path planning of the ant colony algorithm. (f) This paper improves the convergence curve of the ant colony algorithm.

Figure 5. The ant colony algorithm planning path. (a) The traditional ant colony algorithm planning path. (b) The improved ant colony algorithm planning path.

Figure 6. The physical verification of inspection robots.

Table 1. Initial parameter settings.

Parameter
Maximum iteration count K	Node i j
Number of ants M	$Factor for artificial potential field attraction γ$
$Pheromone importance factor α$	$Constant μ$
$Importance factor of expected heuristic information β$	$Number of ants on the optimal path in this iteration ε$
$Pheromone evaporation coefficient ρ$	Number of ants on the worst path in this iteration $ϵ$
Pheromone intensity Q	Number of elite ants b

Table 2. Experimental parameter settings.

Parameter	Value
$Maximum number of iterations K$	120
$Number of ants M$	60
$Pheromone importance factor α$	1
$Expectation heuristic information importance factor β$	2
$Pheromone evaporation coefficient ρ$	0.8
$Intensity of pheromone Q$	10
$Number of elite ants b$	10

Table 3. A comparison of the experimental results of the 20 × 20 static grid environment.

Algorithm	Optimal Path Length/m	Running Time/s	The Number of First Convergence Iterations	Turning Point	Compared with the Traditional Algorithm, the Path Length Reduction Rate	Compared with the Traditional Algorithm, the Reduction Rate of Iteration Times	Compared with the Traditional Algorithm, the Reduction Rate of the Number of Inflection Points
Traditional ant colony algorithm	31.17	11.69	23	22	——	——	——
Literature [12] algorithm	29.79	6.25	12	19	4.42	47.8	13.63
Improved ant colony algorithm	28.96	5.12	5	16	7.09	78.2	27.27

Table 4. A comparison of the experimental results of the 30 × 30 static grid environment.

Algorithm	Optimal Path Length/m	Running Time/s	The Number of First Convergence Iterations	Turning Point	Compared with the Traditional Algorithm, the Path Length Reduction Rate	Compared with the Traditional Algorithm, the Reduction Rate of Iteration Times	Compared with the Traditional Algorithm, the Reduction Rate of the Number of Inflection Points
Traditional ant colony algorithm	66.18	31.25	33	34	——	——	——
Literature [12] algorithm	44.52	20.64	21	18	32.72	36.36	47.06
Improved ant colony algorithm	43.46	15.66	15	13	34.33	79.16	54.55

Table 5. A comparison of experimental results of 50 × 50 static grid environment.

Algorithm	Optimal Path Length/m	Running Time/s	The Number of First Convergence Iterations	Turning Point	Compared with the Traditional Algorithm, the Path Length Reduction Rate	Compared with the Traditional Algorithm, the Reduction Rate of Iteration Times	Compared with the Traditional Algorithm, the Reduction Rate of the Number of Inflection Points
Traditional ant colony algorithm	120.25	170.11	34	54	——	——	——
Literature [12] algorithm	65.74	120.45	30	28	45.33	11.76	48.15
Improved ant colony algorithm	60.79	114.62	25	20	49.45	26.47	62.96

Table 6. A comparison of ROS experimental verification results.

Algorithm	Optimal Path Length/cm	Running Time/s	Turning Point
Traditional ant colony algorithm	65	302	6
Improved ant colony algorithm	41	149	3

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Wang, H.; Wang, S.; Yu, T. Path Planning of Inspection Robot Based on Improved Ant Colony Algorithm. Appl. Sci. 2024, 14, 9511. https://doi.org/10.3390/app14209511

AMA Style

Wang H, Wang S, Yu T. Path Planning of Inspection Robot Based on Improved Ant Colony Algorithm. Applied Sciences. 2024; 14(20):9511. https://doi.org/10.3390/app14209511

Chicago/Turabian Style

Wang, Haixia, Shihao Wang, and Tao Yu. 2024. "Path Planning of Inspection Robot Based on Improved Ant Colony Algorithm" Applied Sciences 14, no. 20: 9511. https://doi.org/10.3390/app14209511

APA Style

Wang, H., Wang, S., & Yu, T. (2024). Path Planning of Inspection Robot Based on Improved Ant Colony Algorithm. Applied Sciences, 14(20), 9511. https://doi.org/10.3390/app14209511

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Path Planning of Inspection Robot Based on Improved Ant Colony Algorithm

Abstract

1. Introduction

2. Problem Description

2.1. Establishment of Environmental Model

2.2. Traditional Ant Colony Algorithm

3. Improved Ant Colony Algorithm

3.1. Improved Heuristic Information Function

3.2. Improved Pheromone Update Rules

3.3. Path Optimization and Update

3.4. Improved Pheromone Update Rule and Mathematical Analysis of Convergence

3.4.1. The Pheromone Update Formula in the Original Ant Colony Optimization Algorithm

3.4.2. The Improved Pheromone Update Formula

3.4.3. Convergence Analysis of the Improved Algorithm

3.4.4. Theoretical Proof of Convergence

3.4.5. Conclusions of Mathematical Analysis

3.5. Algorithm Flow

4. Experimental Simulation and Analysis

4.1. 20 × 20 Simulation Results and Analysis

4.2. 30 × 30 Simulation Results and Analysis

4.3. 50 × 50 Simulation Results and Analysis

5. Experimental Verification

6. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI