Keywords

1 Introduction

Path planning refers to find the best path from the beginning to the end in a specific environment under the premise of optimizing one or several performance indicators, and in other cases, it also refers to find the best path to accomplish reconnaissance, search and other tasks. There are many applications of path planning, including the movement of robot in industry, the reconnaissance and search task of unmanned aerial vehicles (UAVs) and unmanned vehicles (UVs) in military field, the movement of scavenging robot in the smart home, and so on. The methods of path planning on UAVs and UVs are various. In [1], the receding-horizon path planning method is proposed to realize positioning and autonomous search functions of manned aircraft with the use of multi-step planning for systems with limited sensor footprints. Coverage path planning, an energy-aware path planning algorithm, is mentioned in [2], in which the path covering all target points or other requirements is searched with little energy consumed in UVs. The collaborative path planning algorithm for target tracking is developed in [3], which makes use of dynamic occupied grids, Bayesian filters, just name a few, to enable the tracking movement of UAVs and UVs in urban environments. Although path planning has been studied for a long time, there are still some problems. For example, scholars only consider geometric constraints but do not pay attention to the characteristics and practical significance of UVs and UAVs. The convergence speed and optimization result in path planning will also affect the application degree of the algorithm. And swarm intelligence bionic algorithms have achieved good results in this respect.

Up to today, scholars have developed sorts of advanced path planning algorithms on the basis of traditional optimization algorithms, including A* algorithm [4, 5], roadmap algorithm (RA) [6, 7], cell decomposition method (CD) [8, 9], artificial potential field method (APF) [10, 11], to name but a few. However, with the change of search environment, the expansion of search space, and the passage of time, the computational cost and the demand of storage space of the classical traditional path planning algorithm will increase geometrically. To this end, researchers proposed swarm intelligence optimization algorithms, including the ant colony optimization algorithm (ACO) [12], neural network [13, 14], genetic algorithm (GA) [15, 16], cuckoo algorithm [15, 17], particle swarm optimization (PSO) [16, 18], and artificial bee colony algorithm (ABC) [19, 20], etc. ACO is a heuristic random search algorithm proposed in the 1990s [12]. When an ant colony is searching for some food, the pheromone [21] on the path will affect the ant’s choice of path, and eventually form the best path from the nest to the food. However, ACO also has some obstacles when applied to path planning. For example, a small pheromone volatilization coefficient will reduce the randomness of the algorithm’s search, while a large one will reduce the convergence speed. In addition, the convergence rate of ACO is slow and local best results are easy to appear. Therefore, international scholars have also improved ACO for these problems. In [22], the authors used ACO for UAV path planning while also meeting the requirement of obstacle avoidance. But when the number of obstacles is too large or the complexity is relatively large, the performance of the algorithm proposed by [22] will decrease. In [23], the idea of fuzzy logic (FL) is applied to ACO, using the rank-based ant system and virtual path length to realize the path planning of UVs. However, the calculation time of this method needs to be further reduced. Liu Guoliang and others [24] used ACO to design a UAV location-assignment method in the problem of multi-UAV formation path planning, and then adopted a new strategy to select the next target node to find the globally best path. However, the improved ant colony algorithm in [24] has not been tested in other application environments. Green Ant (G-Ant) [25] not only considers the path length of the vehicle but also considers the energy consumed during the driving of the vehicle in the path planning of the unmanned ground vehicle (UGV). But the route found by the green ants is not necessarily the path with the shortest energy consumption. In [26], authors proposed and designed a dynamic viewable method based on the local environment model, a new rule of ant colony state transfer, and a reverse eccentric expansion method to improve ACO to realize the unmanned surface vehicle (USV) in the static position and dynamic state. Know the path planning in the environment to avoid collisions. In [27], ACO was used to draw a digital map of the drone’s mission environment, and a mathematical model of the drone’s horizontal and vertical flight trajectory was established to simulate the flight trajectory of the drone’s mission. We can see from the above description that scholars have improved ACO through various means, allowing ACO to show better performance in path planning and be applied in more fields. However, the research of path planning algorithms is still in the stage of solving problems such as convergence speed, local optimization, unmanned vehicle modeling, dynamic environment, and path planning in emergencies. In addition, It should also consider the actual performance of the research object to improve the practicality of the algorithm.

The variation of pheromone volatilization coefficient is rarely considered in ACO algorithms. An improved ant colony method is proposed to change the pheromone volatilization coefficient. As such, the convergence speed is enhanced and the local optimum phenomena is largely avoided. We set up the search space by the Cartesian coordinate system, other than the raster map. The pheromone volatility coefficient changes along with the iteration times. In the beginning of the search, we use a relatively large pheromone volatilization coefficient. Afterwards, in the middle and late stages of a search, the pheromone volatilization coefficient turns to be small, to improve the searching accuracy.

The rest of this paper is organized as follows. Section 2 introduces the classical ant colony optimization algorithm and its application in path planning. Section 3 addresses the main results of this paper, including task environment modeling, improvement of pheromone volatilization coefficient, and the flow of improving ant colony optimization algorithm. Section 4 exhibits the comparison of experimental simulation with other UV path planning methods. Finally, Sect. 5 concludes the whole paper.

2 Path Planning Using ACO Algorithm

2.1 Classical Ant Colony Optimization Algorithm

In the biological world, when ants search for food [12, 28, 29], they secrete pheromones along the path that they traveled, as such clues are left for the ants behind them. Therefore, after a period of time, through the evaporation and accumulation of pheromones, a path with the largest pheromones from the ant nest to the object will be formed, which is also the optimal path. Ant colony algorithm uses artificial ants to simulate this process. Each artificial ant is placed at the starting point, and then the artificial ant independently selects the next target point according to the pheromone residue, path and heuristic information after evaporation. At time t, the probability \({p}_{ij}^{k}(t)\) of ant k moving from target i to target j is.

$$ p_{ij}^{k} \left( t \right) = \left\{ {\begin{array}{*{20}c} {\frac{{\left[ {\tau_{ij} \left( t \right)} \right]^{\alpha } \cdot \left[ {\eta_{ij} \left( t \right)} \right]^{\beta } }}{{\mathop \sum \nolimits_{{S \in J_{k} \left( i \right)}} \left[ {\tau_{is} \left( t \right)} \right]^{\alpha } \cdot \left[ {\eta_{is} \left( t \right)} \right]^{\beta } }},} & {j \in J_{k} \left( i \right)} \\ {0,} & {otherwise} \\ \end{array} } \right. $$
(1)

where, α and β represent the relative importance of pheromones and heuristic factors, respectively; \({\tau }_{ij}\) is the amount of pheromone between target points i and j; \({\eta }_{ij}\) is the heuristic information, representing the expectation extent of ants from the target point i to j, and \({\eta }_{ij}\) = 1/\({d}_{ij}\), where \({d}_{ij}\) is the distance between i and j. \({J}_{k}(i)\) = {1, 2, …, n} is the set of target points that ant k is allowed to choose in the next step;\({tabu}_{k}\) records the current target point that ant k has passed. When the path cost from target i to target j decreases, the state transition probability of the road segment will increase. Therefore, when the ant chooses the next moving target, it will be more inclined to choose target j.

When all ants traverse n targets once, the pheromone quantity on each path should be updated according to (2).

$$ \tau_{ij} \left( {t + n} \right) = \left( {1 - \rho } \right) \cdot \tau_{ij} \left( t \right) + \varDelta \tau_{ij} $$
(2)

where, \(\rho \) represents pheromone volatility coefficient; \( \varDelta {\tau }_{ij}\) represents the pheromone increment between i and j in this iteration, which can be obtained as.

$$ \varDelta \tau_{ij} = \sum\nolimits_{k = 1}^{m} {\varDelta \tau_{ij}^{k} } $$
(3)

where, \(\varDelta {\tau }_{ij}^{k}\) represents the amount of pheromone left between i and j by the k ant in this iteration. If the ant does not pass through two points i and j, t is equal to zero. \(\varDelta {\tau }_{ij}^{k}\) can be expressed by.

$$ \varDelta \tau_{ij}^{k} = \left\{ {\begin{array}{*{20}c} {\frac{Q}{{L_{k} }},} & {when\,ant\,k\,passes\,i\,and\,j\,in\,this\,iteration} \\ {0,} & {otherwise} \\ \end{array} } \right. $$
(4)

where, Q is the positive constant, and \({L}_{k}\) represents the length of the path traveled by the k ant in this iteration.

Fig. 1.
figure 1

Flow chart of basic ant colony optimization algorithm

Full size image

The flow chart of the basic ACO is shown in Fig. 1. The process of path planning based on the basic ACO is briefly described as follows. In the initial time, the number of search targets n, the number of ants m, the importance factor α of pheromone, the importance factor β of heuristic information, the volatility coefficient ρ, pheromone slight Q, the initial iteration number iter and the maximum allowable iteration number \({iter}_{max}\) are set. The target distance matrix, pheromone matrix, path distance matrix, optimal path recording matrix of each generation, and optimal path length recording vector of each generation are established. Then put the ants on the starting point of the driverless car. The ant chooses the next search target according to the target selection probability formula (1), and updates the ant taboo. When all the targets are visited and the ant returns to the starting position, the ant’s search ends. Then the next ant searches until all the ants have finished the search. At this point, an iteration is completed, and the best path of the iteration is recorded. Then, according to formula (2) to formula (4), the pheromone on each path is updated, and the tabu list is cleared before the next iteration. The algorithm finds the best path before the end of iteration. So far, the basic ant colony algorithm has completed the whole optimization process.

2.2 Application of Basic Ant Colony Optimization Algorithms

ACO is essentially a parallel algorithm with a positive feedback mechanism and strong robustness. It has many applications, including traveling salesman problem (TSP), optimal tree problem, integer programming problem, general continuous optimization problem, vehicle routing problem (VRP), etc. Figure 2 shows the result of simple obstacle avoidance path planning for robots using the basic ant colony algorithm.

Fig. 2.
figure 2

Obstacle avoidance path diagram of mobile robot

Full size image

In Fig. 2, the black area represents the obstacle, the white area represents the passable area, and the black dotted line refers to the moving trajectory of robot. In this simple experiment, the robot mobile environment is constructed as a 10*10 grid map. In the grid map, obstacles like “concave” or “L” will appear. This kind of obstacle is likely to lead artificial ants into a deadlock state, thus reducing the number of ants participating in the search and affecting the final search results. Therefore, we consider a completion method to solve the ant deadlock problem.

3 Path Planning Using Improved ACO Algorithm

3.1 Task Environment Modeling

There are many kinds of search environment modeling in path planning, such as Cartesian coordinate system, raster map, probability path diagram, and so on. In the common raster maps, if ants encounter “concave” and “L” obstacles in the search process, ants are prone to the deadlock phenomenon, which affects the optimality of search results. Therefore, in view of the shortcomings of grid map, we use the Cartesian coordinate system to model the search environment, and represents the task points in the form of coordinates. The environment modeling is shown in Fig. 3.

Fig. 3.
figure 3

Search environment modeling schematic

Full size image

According to the task point coordinates to be searched, the task environment is constructed as a plane Cartesian coordinate system of (4500–500) * (4500–500), as depicted in Fig. 3. The X-axis and Y-axis in the figure represent the transverse distances and longitudinal distances between any two task points respectively, in meters. The task point coordinates are composed of the two, and each task point is labeled, as shown in the black circle in Fig. 3. Treat the driverless car as a particle, search all mission points in the environment map and return to the starting point.

As for the deadlock phenomenon of ants in the grid map, we consider a fence method to solve this problem. In the process of driving, UVs often encounter obstacles of various shapes. We consider using straight line segments to enclose the obstacle into a polygon, as shown in Fig. 4. The black areas represent obstacles, and the black dotted line segments are straight line segments surrounding the obstacle. To avoid affecting the optimization results, we should make the area of the polygon as small as possible, and avoid “concave”-shaped and “L”-shaped edges. In this way, in the process of ant search, deadlock phenomenon can be effectively avoided, and the optimization accuracy is improved as well.

Fig. 4.
figure 4

Diagram of obstacle handling

Full size image

3.2 Improvement of Pheromone Volatilization Coefficient

The pheromone volatilization coefficient of the classical ACO is a small constant. As such, when using the basic ACO for path search, the residual pheromone amount in the search after the initial pheromone volatilization is large. For the next iteration ants with a larger impact on target selection, they are more inclined to choose the path of the pheromone, consequently leading to the reduction of search range and search randomness. Thus, the locally optimal solution is made. To solve the issues of slow convergence and local optimal in classical ACO, we change the pheromone volatilization coefficient in this paper. The improved expression of the pheromone volatilization coefficient is.

$$ \rho \left( {iter} \right) = \left\{ {\begin{array}{*{20}c} {\left( {1 - \frac{iter}{{iter_{max} }}} \right)\rho \left( {iter - 1} \right), } & {if\,iter\left\langle {\left[ {\frac{{iter_{max} }}{b}} \right]\,and\,\rho } \right\rangle \rho_{min} } \\ {\rho_{min } ,} & {otherwise} \\ \end{array} } \right. $$
(5)

where iter represents the current number of iterations and \({iter}_{max}\) represents the maximum number of iterations; \({\rho }_{min}\) represents the minimum pheromone volatility coefficient. Parameter of b is an adjustable positive parameter with a value range of 3 to \(\sqrt{{iter}_{max}}\), and the specific value of b is determined according to the maximum number of iterations.

In (5), the pheromone volatility coefficient varies with iterations. With the increase of iteration, \(\rho (iter)\) decreases from large to small until it decreases to the minimum value. In this improvement, the parameter of b is used to divide the whole iteration process into two parts. In the early part of the iteration, \(\rho (iter)\) varies with iterations; the second part is the middle and late part of the iteration, and the pheromone volatilization coefficient takes its minimum value. The value range of parameter b is determined according to the maximum number of iterations, and the maximum value is \(\sqrt{{iter}_{max}}\). When the value of \(\frac{{iter}_{max}}{b}\) is not an integer, let [\(\frac{{iter}_{max}}{b}\)] be the integer that is less than or equal to \(\frac{{iter}_{max}}{b}\) and close to \(\frac{{iter}_{max}}{b}\).

3.3 The Flow of Improved Ant Colony Algorithm

Fig. 5.
figure 5

The flow chart of improved ant colony optimization algorithm

Full size image

The flow chart of the improved ant colony algorithm is shown in Fig. 5. The process of path planning realized by the improved ACO is briefly described as follows: at the initial time, the number of search targets n, the number of ants m, the importance factor of pheromone α, the importance factor of heuristic information β, the minimum value of pheromone volatility coefficient \({\rho }_{min}\), the initial value of pheromone volatility coefficient ρ, the light value of pheromone Q, the initial number of iterations iter and the maximum allowable number of iterations \({iter}_{max}\) were set. The target distance matrix, pheromone matrix, path distance matrix, optimal path recording matrix of each generation, and optimal path length recording vector of each generation are established. Then put the ants on the starting point of the driverless car. The ant chooses the next search target according to the target selection probability formula (1), and updates the ant taboo. When all the targets are visited and the ant returns to the starting position, the ant’s search ends. Then the next ant searches until all the ants have finished the search. At this point, an iteration is completed, and the best path of the iteration is recorded. Firstly, the pheromone fluctuation coefficient is updated according to formula (5), and then the pheromone on each path is updated to formula (4) according to the global pheromone update formula (2), and the next iteration is started after the tabu list is cleared. The algorithm finds the best path before the end of iteration.

4 The Experimental Results

To illustrate the effectiveness of the improved algorithm proposed in this paper and to improve the convergence speed of the algorithm, this section uses MATLAB software to conduct experimental verification. We compare it with the basic ACO and other improved ACO based on regulating pheromone volatility [30,31,32,33]. The basic idea of an adaptive ant colony algorithm is: after each iteration, the current optimal solution is obtained and retained. When the issue scale becomes large, because of the existence of \(\rho \), the pheromones of paths that have never been searched gradually dwindle or even disappear. Thus, this will reduce the globality of the algorithm. When \(\rho \) is too large, the probability of the previously searched path being selected here is very high. And this will also affect the globality of the algorithm. Therefore, it is necessary to adaptively change the value of \(\rho \). The adaptive formula is shown in (6).

$$ \rho \left( t \right) = \left\{ {\begin{array}{*{20}c} {0.95\rho \left( {t - 1} \right), } & {If\,0.95\rho \left( {t - 1} \right) \ge \rho_{min} } \\ {\rho_{min} , } & {Otherwise} \\ \end{array} } \right. $$
(6)
Fig. 6.
figure 6

Path results of basic ant colony optimization algorithm

Full size image
Fig. 7.
figure 7

Path results of improved ant colony optimization algorithm

Full size image
Fig. 8.
figure 8

Path results of adaptive ant colony optimization algorithm

Full size image
Fig. 9.
figure 9

Comparison diagram of algorithm convergence speed

Full size image

To simplify the experiment, the analysis and experimental simulation are carried out based on a two-dimensional plane. The initial parameters of the algorithm are as follows: the number of search targets n = 30; the number of ants m = 50; pheromone importance factor α = 1; heuristic information importance factor β = 5; pheromone intensity Q = 100; the minimum value of pheromone volatilization coefficient \({\rho }_{min}\) = 0.1. The maximum number of iterations allowed is \({iter}_{max}\) = 100. Figures 6, 7 and 8 show the optimal path obtained by the basic ACO, improved ACO and adaptive ACO, respectively. Figure 9 shows the convergence curve comparison of these methods and those in [31,32,33]. It can be seen from Fig. 9 that the proposed improved ACO algorithm has the highest convergence speed among all. The path length comparisons are as shown in Table 1, from which we can find that our proposed result has the shortest path length, as well.

Table 1. The path length of the experimental results
Full size table

5 Conclusions

Ant colony algorithm is widely used in path planning, whereas, there still are unsolved problems, such as slow convergence speed, local optimization in real applications. To this end, this paper proposes an improved ACO algorithm on UV path planning with high convergence speed and global optimization ability by using a time-varying pheromone volatilization coefficient. The iterative process consists of two parts. In the beginning paragraph, the pheromone volatilization coefficient decreases from a large value along with iteration times. In the second part, the pheromone volatilization coefficient remains at a small value and gradually reduced. There is still a lot of room for improvement. In our next work, we shall consider the constraints of the actual working environment and the performance of UV itself to enhance the applicability of the ACO algorithm.