Multi-factor of path planning based on an ant colony optimization algorithm

ABSTRACT

We propose an improved ant colony algorithm for avoiding obstacles in complex static environments that addresses the problems of a single evaluation factor and low path quality of the traditional ant colony algorithm in path planning. The improvements are: 1) a fuzzy planner is constructed according to the comprehensive evaluation method of fuzzy mathematics and the analytic hierarchy process to comprehensively evaluate and determine the impact of environmental factors, 2) the probability selection formula of the ant colony algorithm is optimized, 3) the pheromone update formula is optimized, and 4) the corner system mechanism is introduced as a post-processing method of path optimization to further smooth the path. Results from simulation experiments of the traditional ant colony algorithm were analysed and compared with those of the improved ant colony algorithm, showing that the latter has a stronger path planning ability and higher algorithm efficiency, resulting in a smoother path with a lower negative impact by environmental factors. Thus, the proposed algorithm is expected to provide a computational basis for effective multi-factor path planning in realistic environments, thereby saving human and material resources.

KEYWORDS:

• Path planning
• ant colony algorithm
• fuzzy mathematics comprehensive evaluation method
• analytic hierarchy process

1. Introduction

Path planning is an important aspect of the navigation technology of mobile robots, and is also an essential function of autonomous robot movement (Zhou et al. 2018). Its main purpose is to determine the optimal or sub-optimal path without collision events from the starting point to the target point in an obstacle environment (Dai et al. 2019). In different regions, with complex and changeable terrain, varying geomorphology types, and complicated geological conditions, path planning becomes a complicated task. An optimal path should not just represent the route from the beginning to the end but also reflect the shortest possible distance. It should also comprehensively account for the influence of environmental factors (such as land use, geologic hazard, slope factors, and geological factors). Thus, robust path planning is key to path safety along the artery of economic development, thereby ensuring construction safety, energy distribution, and minimal economic cost.

There are two broad categories of path planning algorithms: traditional and intelligent. Traditional path planning algorithms include the simulated annealing algorithm (Steinbrunn, Moerkotte, and Kemper 1997), potential function theory (Nair et al. 2015), and fuzzy logic algorithm (Li et al. 2013). The capability of traditional algorithms in path planning is nearly saturated and cannot be further optimized. Intelligent path planning algorithms include the ant colony algorithm (Dorigo and Stützle 2000), a bee colony algorithm (Liang and Lee 2015; Cheng, Qi, and Sen 2018), and the A* algorithm (Liang et al. 2018).

The ant colony algorithm was introduced in the early 1990 s as a new technique for solving combinatorial optimization problems. It is a kind of simulation based on ant behaviour and communication (Yang et al. 2017) and a type of swarm intelligence heuristic algorithm that is based on the study of ant foraging behaviour, forming a bionic algorithm (Yu et al. 2018) currently in the early stages of its life cycle (Dorigo and Blum 2005). Initially proposed by Marco Dorigo in 1992, it draws its inspiration from the paths carved by ants searching for food. The positive feedback mechanism is adopted to converge the search process and finally approximate to an optimal solution. The basic principle of applying the ant colony algorithm to the path planning problem is that the optimal solution is represented by a walking path of the ant while all the paths of the whole ant colony constitute the solution space. Under similar conditions, the concentration of the pheromone released by the ants on the shorter path is relatively high. With time, the accumulated pheromone concentration on the shorter path gradually increases, and the number of ants choosing this path, in turn, also increases. Finally, the whole ant colony focuses on the optimal path under the action of positive feedback (Dorigo and Caro 2002; Liu et al. 2017). The ant colony algorithm is different from other path planning techniques (such as heuristic search or potential field). It is a probabilistic technique that can solve computing problems and can be simplified to find acceptable paths by graphs (Jiao et al. 2018). It is robust, attracting considerable interest in its improvement. Stützle et al. (Stützle and Hoos 2000) proposed a swarm system algorithm, which could accelerate the convergence rate of the ant colony algorithm by updating the pheromone parameters on the optimal path of each ant generation. Zhao, Cheng, and Hao (2016) proposed few intelligent algorithms to generate the initial path and convert it into the initial pheromone distribution; thus, avoiding blind search. Liu and Cheng 2008) (introduced elite strategy and visual visitation function to the ant colony algorithm, and explored a safe and non-touching robot walking path from the source point to the target point with the cooperation of ordinary and elite ants. Yue, Cui, and Cui (2006) added goal-oriented behaviour, inertial behaviour, and walking along obstacles into individual ant behaviour, and included weighted fusion to improve the performance of the traditional ant colony algorithm. Although these algorithms are promoted to address path planning problems, in actual applications, the path is also affected by various factors such as land use, geologic hazard, slope factors, and geological factors. The algorithms unilaterally consider the distance factor but not the other factors.”

A mobile robot is a complex control system that integrates environmental perception, dynamic decision making and planning, behaviour control and execution, etc. When it performs tasks in a working environment, it needs to reach its destination safely and quickly. Therefore, it is necessary to plan a fast, safe, and effective path. This study comprehensively considers the various factors influencing path planning to improve the ant colony algorithm. The analytic hierarchy process and fuzzy mathematical theory are widely used in the multi-criteria decision-making process (Ahmed and Kemal 2019). Therefore, in this study, we introduced a fuzzy planner by combining the fuzzy mathematics comprehensive evaluation method and analytic hierarchy process, and used it to comprehensively evaluate the impact factors (land use, geological disasters, slope, geological factors) of path planning to obtain grid weight data, and improve the probability selection formula and pheromone update formula of the ant colony algorithm. Finally, we introduce the corner system mechanism as a post-processing method of the algorithm to further smooth the path. Compared with the traditional ant colony algorithm, the improved algorithm in this paper comprehensively considers a variety of geographical factors in realistic and complex environments, has better convergence and stability, and improves the path planning ability in complex environments.

2. Ant colony algorithm

2.1. Probability selection of the ant colony algorithm

According to the probability selection formula, the forward node is selected using the roulette method as follows:

(1) $P^m\left(i,j\right)=\left\{\begin{array}{cc}\frac{\tau {\left(i,j\right)}^{\alpha }\cdot \eta {\left(i,j\right)}^{\beta }}{{\sum }_{j\in J_i}\tau {\left(i,j\right)}^{\alpha }\cdot \eta {\left(i,j\right)}^{\beta }}& j\in J_i\\ 0& Else\end{array}\right.$(1)

where P^m(i,j) is the probability that the m^th ant will travel from node i to node j and τ(i,j) is the pheromone content of the m^th ant from node i to the edge of node j; the initial value of each side pheromone is a constant. Each ant can only advance towards adjacent nodes in eight directions. J_i indicates that the eight nodes do not contain the set of obstacles and taboo nodes, and η(i,j) is the expected value of the two nodes, i and j, which is inversely proportional to the distance between these two nodes. α and β are the importance parameters of the pheromone and expected value, respectively (Wan et al. 2014). A representation of movement decisions from left to right is established. In the left panel, the ants in the solid black node can move to one node in any direction. In the centre panel, nodes at the top and left appear in the taboo table along with the adjacent nodes. The ants select a move towards the diagonal lower right direction from the three viable options by using the roulette method (right panel) (Figure 1).

Figure 1. Probability selection model: initial probability set (left panel), reduced options by taboo node table (centre panel), and selection by the roulette method (right panel).

2.2. Pheromone update mechanism

In the process of ant foraging, pheromones are left in the path. As the pheromone is volatile, its concentration in the algorithm needs to be updated in real time as follows:

(2) $T_{k+1}=\left(1-\rho \right){\tau }_k\left(i,j\right)+\mathrm{\Delta }\tau \left(i,j\right)$(2)

(3) $\mathrm{\Delta }\tau \left(\mathrm{i},\mathrm{j}\right)={\sum }_{m\in M_{i,j}}\mathrm{\Delta }\tau \left(i,j\right)$(3)

(4) $\mathrm{\Delta }{\tau }^m\left(i,j\right)=Q/L_m$(4)

In the model, the algorithm is provided with a volatilization coefficient, ρ (0 < ρ < 1), and an initial pheromone concentration, C, which is a constant. T_k(i,j) is the pheromone concentration between nodes i and j at time k. ${\tau }_k\left(i,j\right)$ is the pheromone concentration between nodes i and j at time k, and Δτ(i,j) is the increment of pheromone between node i and node j, in this cycle. The increment of the pheromone, M_{i, j}, is the set of ants passing through nodes i and j, and $\mathrm{\Delta }{\tau }^m\left(i,j\right)$ is the pheromone increment between nodes i and j for the m^th ant. L_m is the length of the path sought by the m^th ant, and $Q$ is the increasing strength coefficient of the pheromone, which is a normal number (Hojat et al. 2018). After all the ants complete a path search, the pheromone is updated along each path.

2.3. Iterative loop

In the algorithm, after searching for the path, the ant will be re-positioned at the starting point of the (robot) path, and then, the algorithm will be used to perform path optimization in the next round. After multiple iterations, the shortest optimal path will be selected.

3. Optimization of the ant colony algorithm

Path planning involves factors related to land use, geologic hazard, slope factors, and geological factors, wherein each factor has a different effect on the path. In actual line selection, it is necessary to assign different weights to various impact factors and finally make a comprehensive evaluation of the weights of these factors. It is understood that a higher comprehensive weight corresponds to a lower path quality. Finally, the path with the least impact and shortest line length is selected as the optimal path. Therefore, by implementing the proposed optimization technique, the algorithm can comprehensively consider various impact factors to obtain a path that is smoother and less affected by these factors. By contrast, the traditional ant colony algorithm cannot provide an optimal path based on the impact of a comprehensive list of external factors.

3.1. The related concepts of analytic hierarchy processes and fuzzy mathematics comprehensive evaluation

3.1.1. Analytical hierarchy processes

The analytic hierarchy process (AHP) is an analytical method that considers complex multi-objective decision-making problems as systems. It identifies the objective as a set of multiple criteria and decomposes it into multiple indicators or constraints. The hierarchical single ranks are weighed, and the total ranking is calculated using a qualitative index fuzzy quantification method with an objective (multi-indicators) and a multi-scheme optimal decision-making system (Chen et al., 2018). Although it might be difficult to assign weights directly to each factor, it is relatively easy to rank the importance between two factors. The relative importance of two factors is from 1 to 9. If the value of the importance of A compared to B is closer to 9 (or the importance of B relative to A is closer to 1/9), then A is relatively greater in degree of importance to B; if the value of the importance of A compared to B is closer to 1, then the importance of A relative to B is closer to equal.

If a particular criterion is adopted, the corresponding schemes are compared in two ways and graded according to their importance. A grade is defined as the ratio of the importance of factor a to factor b. A matrix consisting of two by two comparisons is called a judgement matrix. After the judgement matrix is filled in, the weight value can be solved and the rationality of the weights can be verified.

3.1.2. Fuzzy mathematics comprehensive evaluation

Traditional analytical techniques have been found to be non-effective when dealing with problems wherein the dependencies between variables are complex or vaguely defined (Kalinic and Krisp 2019). Therefore, we used a fuzzy comprehensive evaluation method to solve these problems. The main processes involved in this method are the establishment of the subset, evaluation set, and membership degree. The membership degree represents the fuzzy set of weight values of evaluation index. In fuzzy comprehensive evaluation, as long as the same membership function is used and the selection of the actual measurement point of the index is objective, the evaluation results are considered fair and reliable. In this study, the path planning factor set U = {land use, geological hazard, slope factor, geological factor}, and the evaluation set V = {first-level impact, second-level impact, third-level impact, fourth-level impact}. The higher the level, the more serious will be the negative impact on path planning. The establishment of membership is based on the following formulae:

A functional formula with the membership degree of ‘first-level influence’ is defined as

(5) ${\text{R}}_{i1}=\text{ left{ {matrix{}1x_i\le S_{i1}\text{ cr}\frac{I_{i1}-x_i}{I_{i1}-S_{i1}}{S}_{i1}\text{ lt}{x}_i\text{ lt}{I}_{i1}\text{ cr {}0\text{}{x}_i\ge I_{i1}\text{} cr } } right}\text{.}$(5)

A functional formula with the membership degree of ‘second-level influence’ is defined as

(6) ${\mathrm{R}}_{i2}=\left\{\begin{array}{cc}\frac{x_1-S_{i1}}{I_{i1}-S_{i1}}& S_{i1}<x_1<I_{i1}\\ 1& I_{i1}\le x_i\le S_{i2}\\ \begin{array}{c}\frac{I_{i2}-x_i}{I_{i2}-S_{i2}}\\ 0\end{array}& \begin{array}{c}{S}_{i2}<x_i<I_{i2}\\ x_i\ge I_{i2},x_i\le S_{i1}\end{array}\end{array}\right.$(6)

A functional formula with the membership degree of ‘third-level influence’ is defined as

(7) ${\mathrm{R}}_{i3}=\left\{\begin{array}{cc}\frac{x_i-S_{i2}}{I_{i2}-S_{i2}}& S_{i2}<x_i<I_{i2}\\ 1& I_{i2}\le x_i\le S_{i3}\\ \begin{array}{c}\frac{I_{i3}-x_i}{I_{i3}-S_{i3}}\\ 0\end{array}& \begin{array}{c}{S}_{i3}<x_i<I_{i3}\\ x_i\ge I_{i3},x_i\le S_{i2}\end{array}\end{array}\right.$(7)

A functional formula with the membership degree of ‘fourth-level influence’ is defined as

(8) ${\mathrm{R}}_{i4}=\left\{\begin{array}{cc}0& x_i\le S_{i3}\\ \frac{x_i-S_{i3}}{I_{i3}-S_{i3}}& S_{i3}<x_i<I_{i3}\\ 1& x_i\ge I_{i3}\end{array}\right.$(8)

where i corresponds to each evaluation factor, S_i1–S_i4 represents the standard values of four grades of the evaluation set, and I_i1–I_i4 is the upper limit of the excessive interval between the evaluation centres. The contents of the evaluation set are measured values of selected random points and upper limit values of large intervals between bit evaluation sets. On the premise of obtaining the measured values, a membership function is established from a single factor index for determining the membership degree of a factor for each element in the evaluation set. The membership degree of the first element for the factor set to the j^th element in the evaluation set is expressed as a fuzzy set, and the evaluation matrix of a single factor is obtained as a fuzzy set as follows:

$\mathrm{R}=\left[\begin{array}{c}\begin{array}{cc}{R}_{11}& R_{12}\end{array}\begin{array}{cc}\dots \dots & R_{1n}\end{array}\\ \begin{array}{cc}{R}_{21}& R_{22}\end{array}\begin{array}{cc}\dots \dots & R_{2n}\end{array}\\ \dots \dots \\ \begin{array}{cc}{R}_{41}& R_{42}\end{array}\begin{array}{cc}\dots \dots & R_{nn}\end{array}\end{array}\right]$

From the perspective of environmental assessment, the fuzzy comprehensive evaluation method is performed based on the single factor evaluation method. The weight value obtained by an AHP is multiplied with the fuzzy set obtained through fuzzy mathematics. The formula is as follows:

(9) $\mathrm{B}=\mathrm{W}\mathrm{b}\times \mathrm{R}$(9)

where B is a row in a 4-column matrix, where each column corresponds to an evaluation set, Wb is the weight obtained by AHP. We hypothesize that the corresponding level of the largest element in B is the evaluation result of the fuzzy evaluation method. After the evaluation results are obtained, the weights 0.1, 0.2, 0.3, and 0.4 are assigned to the first-, second-, third-, and fourth-level influences, respectively, to determine the information for the environmental impact factors.

3.2. Fuzzy planner design

Fuzzy mathematics is a theory and method for studying and managing ambiguous phenomena. The AHP is a simple and flexible mathematical method for multi-dimensional criteria decision-making problems. It can quantitate information, provide complex problems with systematic hierarchies, and calculate factor weights (Chen et al., 2018). The fuzzy planner combines fuzzy maths comprehensive evaluation approaches with the AHP to determine the weight of each image grid. It permits the construction of grid weight data based on remote sensing images, digital elevation models, geology, and geological hazard maps.

To ensure reasonable weight, factors are determined and the consistency verification process is introduced. The fuzzy maths comprehensive evaluation method is used for comprehensive evaluation, and thus the membership degree matrix is established. The formula with the operator M ($\oplus$) is given as:

(10) $B_k={\sum }_{j=1}^m{a}_j{r}_{jk}$(10)

where B_k is a comprehensive membership vector, $a_j$ is the weight of each factor obtained by the AHP, and $r_{jk}$ is the membership matrix. Once calculation is complete, according to the maximum membership degree principle, max(B_k) is the comprehensive evaluation value of the grid, which is the weight value of the grid for the path planning environment evaluation.

3.3. Probability selection optimization

According to formula (1), when a subsequent node is selected, the current ant colony algorithm advances based on the expected inverse value of the distance from the current node, i, to the optional adjacent node, j. As only η(i,j) has been considered, it is impossible to determine if the ant is facing the distance end point. The ant might be closer to the target, but not necessarily moving in the best direction.

(11) $P^m\left(i,j\right)=\left\{\begin{array}{c}\frac{\tau {\left(i,j\right)}^{\alpha }\cdot \eta {\left(j,E\right)}^{\beta }}{{\sum }_{j\in J_i}\tau {\left(i,j\right)}^{\alpha }\cdot \eta {\left(j,E\right)}^{\beta }},\\ 0\end{array}\begin{array}{c}j\in J_i\\ Else\end{array}\right.$(11)

In this study, formula (1) was modified to formula (11) as the probability selection formula. Here, η(j, E) represents the expected value of node j to the end node E with the value 1/D_jE, where D_jE is the distance from j to E. The expected value of the reciprocal distance between node j and end node E is inversely proportional. In other words, the expected value of the advance improves through terminal traction. This further improves the expected value of the advancement. Thus, the path that is promoted is comprised of advancements in the direction towards the end point. This would prevent the creation of paths in a direction away from the end point, and, in turn, save search time. Thus, this improves the efficiency of the ant colony algorithm.

3.4. Pheromone update mechanism optimization

In this study, formula (4) was modified to formula (12) for improvement. In the ant colony algorithm, the amount of pheromone added by the m^th ant through the i and j segments is an inverse proportional function of the length of the path taken by the m^th ant, that is, the longer the distance, the smaller the increase. In this study, we added inflection point parameters and weight sum parameters to the pheromone update mechanism. There are only three angles between the forward direction and the end node in the path: sharp, straight, and obtuse. They are assigned 3, 2, and 1 in order, and summated once over all the values on the path-finding route to obtain the value of the inflection point parameter. The pheromone concentration increases as the path in the end direction increases. The addition of the weight sum parameters can create a path where the sum of the weights is small, that is, the pheromone increment on the path with more negative influence factors becomes larger. In the end, more ants are advancing towards the path that is closer to the end point and has the least overall weight.

(12) $\mathrm{\Delta }{\tau }^m\left(i,j\right)=\frac{Q}{L_m+\lambda \cdot T_m}\ast \frac{P}{W}$(12)

where $T_m$ is the inflection point parameter of the m^th ant walking path, $\lambda$ is the weighted coefficient of the inflection point, P is the weighting coefficient of the sum of weights, and W is the parameters of weight sum.

3.5. Corner system mechanisms

If several unnecessary corners are created by a path planning project, it will inevitably and excessively increase the overall cost. To further smooth the path and minimize unnecessary corners, we introduced a novel corner evaluation mechanism as a post-processing method for the algorithm. The basic idea is to check whether two consecutive corners can be replaced by a single line (Figure 2). Consider the route from point A to point C, after the first search is completed, the route from point A to point B is parsed after the route follower encounters the corner of an obstacle (Figure 2, black box). Additionally, the corner system mechanism first judges if there is an obstacle between the virtual line AC, and then checks if the combination of the AB path weight (WAB) and BC path weight (WBC) is greater than WAC. If WAB + WBC > WAC, the AC path is considered to be more optimal than the AB→BC path. In terms of virtual lines, the AB→BC path can be directly replaced by AC, which makes the path smoother by reducing unnecessary corners, and thus significantly saving construction cost.

Figure 2. Mechanism diagram of corner system.

4. Optimization steps to calculate the ant colony algorithm

The flow of the algorithm is as follows (Figure 3):

(1) Build an environmental model and initialize each parameter;(2) Run the fuzzy planner to determine the grid weight data;(3) Initialize the parameters by positioning the ant at the starting point, and placing the starting point on the taboo table; (4) Start the loop. Calculate the forward node of the ant and move it by using the optimized probability formula; (5) Determine whether it is in an infinite loop and place any ant caught in the infinite loop into the taboo list; (6) Ants that are not in an infinite loop continue to progress until the end point. Record the weight of the path, update the pheromone parameter, and start the next iteration; (7) When the number of iterations reaches the maximum, the optimal path is the output.

Figure 3. Flow chart of optimized ant colony algorithm.

5. Simulation experiment

The improved ant colony algorithm was applied to robot obstacle avoidance simulations to evaluate its feasibility. Grid method modelling was used with K = 100 (parameter initialization iteration), M = 50 (number of ants), α = 2 (pheromone importance degree), β = 2 (expected value importance degree), ρ = 0.3 (pheromone evaporation coefficient), Q = 5 (increase in pheromone intensity coefficient), and P = 5 (the weighting parameter). These experiments enable a comparison of the performance of the traditional and improved ant colony algorithms.

After the fuzzy planner establishes a hierarchical structure, the membership relationship between the upper and lower elements is determined. The calculation flow of the fuzzy planner is as follows:

1. We provide the input values of the judgement matrix A (Table 1).

2. Column normalization of the input matrix A to obtain the column normalization matrix $\bar{A}$ (Table 2).

3. The column normalization matrix is calculated using rows to obtain the vector $W_a={\left[\begin{array}{c}\begin{array}{cc}1.74476& 0.31476\end{array}\begin{array}{cc}0.60143& 1.33905\end{array}\end{array}\right]}^T$.

4. The vector, $W_a$, is normalized to obtain the eigenvector $\overline{Wa}={\left[\begin{array}{c}\begin{array}{cc}0.09043& 0.50526\end{array}\begin{array}{cc}0.28026& 0.12404\end{array}\end{array}\right]}^T$.

5. We introduced consistency verification to obtain the following relationships:

Table 1. Judgement matrix of environmental quality evaluation factors for transmission line paths.

	Land use	Geologic hazard	Slope factors	Geological factors
Land use	1	1/4	1/3	1/2
Geologic hazard	4	1	3	4
Slope factors	3	1/3	1	4
Geological factors	2	1/4	1/4	1

Table 2. Normalization of judgement matrix columns of the evaluation factor.

	Land use	Geologic hazard	Slope factors	Geological factors
Land use	0.10000	0.13636	0.07273	0.05263
Geologic hazard	0.40000	0.54545	0.65455	0.42105
Slope factors	0.30000	0.18182	0.21818	0.42105
Geological factors	0.20000	0.13636	0.05455	0.15263

The maximum characteristic root: ${\lambda }_{max}=\frac{1}{n}{\sum }_{k=1}^n\frac{{\left(A\bar{W}\right)}_k}{{\bar{W}}_k}\text{break}=$4.21456

Consistency indicator: $CI=\frac{{\lambda }_{max}-n}{n-1}$, CI = 0.07152110

Consistency ratio: $CR=\frac{CI}{RI},$CR = 0.08036078

where RI is the average random consistency index of the judgement matrix, the fourth order of which is 0.89 (Ma, Tian, and Wang 2013). When CR < 0.10, the matrix shows acceptable consistency. The ranking weights are: 0.09043 for the land use CR, 0.50526 for the geological disaster CR, 0.28026 for the slope CR, and 0.12404 for the geological factors CR. The fuzzy comprehensive evaluation method is adopted to obtain the degree of influence by environmental factors, and thence, the corresponding path weight map (Figure 4).

Figure 4. Weight map for environmental assessment of the line path.

Figure 5. Results of simulation experiment A. Optimal paths of the traditional ant colony algorithm (left panel), optimized ant colony algorithm (centre panel), and a combination of the optimized ant colony algorithm and the corner system mechanism, i.e., the improved algorithm (right panel).

Figure 6. Results of simulation experiment B. Optimal paths of the traditional ant colony algorithm (left panel), optimized ant colony algorithm (centre panel), and a combination of the optimized ant colony algorithm and the corner system mechanism, i.e., the improved algorithm (right panel).

Table 3 is the result statistics of simulation experiment A shown in Figure 5. The route length of the ant colony algorithm is 36.1421 unit length, the path weight sum is 4.4349, and the number of corners is 19. The length of the optimized ant colony algorithm is 30.9706 unit length, the path weight sum is 3.6799, and the number of corners is 15. After optimization of the ant colony algorithm and addition of the corner system mechanism, the path length is 29.1776, its weight sum is 3.3924, and the number of corners is nine. Table 4 is the result statistics of simulation B shown in Figure 6. The route length of the ant colony algorithm is 33.8995 unit length, the path weight sum is 4.8728, and the number of corners is 17. The length of the optimized ant colony algorithm is 29.7990 unit length, the path weight sum is 3.8249, and the number of corners is 13. After optimization of the ant colony algorithm and the addition of the corner system mechanism, the path length is 28.9756, its weight sum is 3.7303, and the number of corners is eight. Both experiments show that under similar conditions, compared to the traditional ant colony algorithm, the improved algorithm proposed in this paper can effectively reduce the number of path corners; thus, the path is smoother and shorter, less negatively affected by external factors, and more robust.

Table 3. Results of simulation experiment A.

	The numbers of corners	The sum of the weights	The length of path
Ant colony algorithm path	19	4.4349	36.1424
Optimization of ant colony algorithm	15	3.6799	30.9706
Optimization of ant colony algorithm + Corner system mechanisms	9	3.3924	29.1776

Table 4. Results of simulation experiment B.

	The numbers of corners	The sum of the weights	The length of path
Ant colony algorithm path	17	4.8728	33.8995
Optimization of ant colony algorithm	13	3.8249	29.7990
Optimization of ant colony algorithm + Corner system mechanisms	8	3.7303	28.9756

Table 5. Results of transmission line path planning.

	The numbers of corners	The sum of the weights	The length of path(km)
Ant colony algorithm path	927	159.3881	52.4552
Optimization of ant colony algorithm	673	115.7007	39.1582
Optimization of ant colony algorithm + Corner system mechanisms	27	67.1601	22.8453

6. Path planning of transmission lines

To verify the superiority of the improved ant colony algorithm, transmission line path planning was considered as an example with selected remote sensing images, 30-metre resolution digital elevation model (DEM), and corresponding geological maps as data sources. The DEM was resampled and resized to the size of the images. The study area, located at the junction of Meihekou City and Panshi City, Jilin Province, is bound by longitude: 125°46′17″–125° 56′50″and latitude: 42°48′10″–42°48′43″. The straight-line distance in the north-south direction of the area is 17.55 km, and the straight-line distance in the east-west direction is 12.92 km, with an area of 226.75 km². Typical features such as water system, residential land, forest, and farmland exist within this area. The land use classification map was obtained by the maximum likelihood value of the image, and the slope map of the study area was obtained based on the DEM. Geological hazard maps were obtained by manual interpretation (Figure 7). The experimental parameter settings are the same as discussed in Section 5. Figure 8 shows the experimental results.

In Table 5, the experimental results show that the path length of the ant colony algorithm is 52.4552 km, the path weight sum is 159.3881, and the number of corners is 927. The path length of the optimized ant colony algorithm is 39.1582 km, the path weight is 115.7007, and the number of corners is 673. The path length, path weight, and the number of corners of the optimized ant colony algorithm combined with the corner system mechanisms are 22.8453 km, 67.1601, and 27, respectively. While laying power transmission lines, geological disasters, land use, geological factors, and slopes, along with excessive turning points, can inevitably have a huge impact on the entire transmission line project, leading to excessive costs. Without a path plan that can comprehensively consider these factors, it will only lead to more human, material, and financial losses. The experimental verification showed that the path weight of the proposed algorithm was significantly reduced compared to the traditional algorithm. It can also be seen in Figure 8 that the optimal path from the proposed algorithm has few turning points, indicating that this algorithm can shorten the path length while avoiding obstacles. Thus, the improved ant colony algorithm was demonstrated to produce a path with a small number of corners and minimal negative impact from environmental factors, providing a viable computational basis for transmission line path planning.

Figure 7. Data preparation with various maps.

Figure 8. Results of transmission line path planning. Optimal paths of the traditional ant colony algorithm (bottom left panel), optimized ant colony algorithm (bottom centre panel), and a combination of the optimized ant colony algorithm and the corner system mechanism, i.e., the improved algorithm (bottom right panel).

7. Conclusions

Traditional robot path planning includes the selection of a non-collision path or a path that satisfies a certain optimal criterion in an obstacle environment given the starting and target points. However, in reality, the merits of a path additionally depend on minimizing the negative impact of environmental factors (land use, geologic hazard, slope factors, geological factors) in non-collision environments. The shortcomings of the ant colony algorithm in path planning include poor path searching ability, excessive turning angles, and importantly, the algorithm does not account for environmental factors. The proposed ant colony optimization algorithm focused on addressing the abovementioned limitations. The membership degree of the environmental factors of each grid was calculated using a fuzzy planner resulting in a weight map for the entire study area. The probability selection formula was optimized so that advancement in the direction of the destination is promoted. When the inflexion point and weight sum parameters were introduced to update the pheromone parameter, the path tended to proceed in the direction of the destination with minimal negative influence by environmental factors. The corner system mechanism was used to further smooth and optimize the path. Thus, this study demonstrated that the proposed algorithm can provide a methodical computational basis for effective multi-factor path planning, thereby saving human and material resources.

Disclosure statement

No potential conflict of interest was reported by the authors

Additional information

Funding

This work was supported by the National Natural Science Foundation of China Grant No: 41472243; the Open Fund of Key Laboratory of Urban Land Resources Monitoring and Simulation, MNR, Grant No. KF-2018-03-020 and KF-2019-04-080.