An improved ant colony algorithm based on artificial potential field and quantum evolution theory

Abstract

The optimal evacuation route in emergency evacuation can further reduce casualties. Therefore, path planning is of great significance to emergency evacuation. Aiming at the blindness and relatively slow convergence speed of ant colony algorithm path planning search, an improved ant colony algorithm is proposed by combining artificial potential field and quantum evolution theory. On the one hand, the evacuation environment of pedestrians is modeled by the grid method. Use the potential field force in the artificial potential field, the influence coefficient of the potential field force heuristic information, and the distance between the person and the target position in the ant colony algorithm to construct comprehensive heuristic information. On the other hand, the introduction of quantum evolutionary theory. The pheromone is represented by quantum bits, and the pheromone is updated by quantum revolving door feedback control. In this way, it can not only reflect the high efficiency of quantum parallel computing, but also have the better optimization ability of ant colony algorithm. A large number of simulation experiments show that the improved ant colony algorithm has a faster convergence rate and is more effective in evacuation path planning.

Keywords

Emergency evacuation path planning ant colony algorithm (ACO)quantum evolution theory

1 Introduction

With the acceleration of urbanization, there are more and more super high-rise multi-functional buildings. High-rise buildings make evacuation more and more complicated. In the event of a fire, how to quickly evacuate the stranded personnel becomes the primary problem to be solved. However, the fire situation changes all the time, and the behavior of personnel is random. It is impossible to rely on large-scale evacuation drills to solve the fire escape under actual conditions [1]. The actual evacuation model is established with the help of a computer, and an intelligent algorithm is used to solve the optimal evacuation route. This can improve the evacuation capacity of the building while also taking into account the economics of actual engineering application, and the feasibility is strong [2]. Therefore, efficient and reliable indoor fire emergency evacuation methods have become one of the focuses of research in the field of public safety at home and abroad.

Optimal path planning is one of the core technologies of the fire emergency evacuation intelligent system. A good escape route can shorten the escape time, improve the escape efficiency, and reduce the loss of personnel and property. The problem of escape path planning is to find an optimal path in the environment of indoor complex obstacles, in accordance with certain requirements, under the condition of no collision, as smooth as possible and the shortest possible path. Then guide personnel to evacuate safely, efficiently and quickly to a safe area. Intelligent optimization algorithm is a new method for solving complex optimization problems proposed by people inspired by the principles of biological evolution and some physical phenomena [3]. With the development and maturity of intelligent simulation optimization algorithms, its excellent optimization characteristics have been widely used in fire evacuation route planning. The route planning problem of fire evacuation is to analyze the evacuation route and the distribution of people in the evacuation area through the relevant intelligent evacuation algorithm. And through dynamic optimization calculations, the best evacuation path planning is obtained. Currently, many intelligent optimization algorithms used in evacuation route optimization include Artificial Bee Colony (ABC) [4], Partical Swarm Optimization (PSO) [5], Ant Colony Optimization (ACO)) [6, 7] and so on. The artificial bee colony algorithm has strong stability, however the search time of the algorithm is longer, and it is easy to fall into the local optimum. The convergence speed of the particle swarm algorithm is relatively fast, and it can be adjusted adaptively by using its own experience. However, the calculation accuracy is not enough, and the search ability of the local optimal solution is poor. Ant colony algorithm is currently one of the most widely used intelligent optimization algorithms in the field of evacuation path planning, with strong stability and optimization capabilities. As one of the most representative swarm intelligence algorithms, ant colony algorithm has the characteristics of positive feedback, robustness, distributed computing and easy combination of other algorithms, and has achieved good results in solving path planning problems. Moreover, the group belonging and self-organization of the evacuated people in the evacuation process have many things in common with the ant colony system. The behavior of evacuees is similar to the foraging behavior of ant colony, and ant colony algorithm is particularly prominent in solving the problem of fire evacuation route planning [8].

However, ant colony algorithm has problems such as slow convergence speed when solving large-scale path planning problems. In order to overcome these problems, many experts and scholars have made improvements and optimizations. Xu proposed an improved pheromone secondary update and local optimization strategy, which enhanced the search ability and has better diversity, but the convergence problem needs to be improved [9]. Reference [10] uses global pheromone and local update The combined method dynamically allocates the pheromone of the current optimal path, so that the algorithm jumps out of the local optimal and avoids stagnation. Zhang merged the ant colony with the bacterial foraging algorithm to improve the ant colony algorithm’s shortcomings of easy deadlock and slow convergence [11].

Reference [12] proposes a method of limiting the information degree and pheromone volatilization coefficient adaptive method to avoid the stagnation of the ant colony algorithm and only obtain the local optimal solution. However, the problem of slow convergence speed has not been greatly improved. Reference [13] improves the ant colony algorithm on the basis of Reference [12], and uses an adaptive probability transfer function to improve the convergence speed of the algorithm to a certain extent.

Although various improved ant colony algorithms continue to emerge. However, the artificial potential field method has a wide range of applications in path planning by virtue of its easy-to-understand theoretical system and other advantages. In order to solve the problem of slow convergence of ant colony algorithm, in 2015, Zeng proposed an improved ant colony optimization with potential field heuristic. The pheromone diffusion and geometric local optimization are combined in the process of searching for the globally optimal path [14]. To solve the problems of convergence speed in the ant colony algorithm, In 2017, Liu proposed an improved ant colony optimization algorithm for path planning of mobile robots in the environment [15]. In 2018, Wang further verified the effectiveness of the artificial potential field ant colony algorithm. This algorithm makes the advantages of potential field and ant colony algorithm in different stages of program operation and shows good features in searching for the optimal path [16]. In 2020, Zhu proposed a new optimization method, which is combined with artificial potential field method, to enhance the robustness of original algorithm [17].

However, although the ant colony algorithm based on the artificial potential field method can improve the convergence speed, it has the problem of partial minimum. In response to this problem, a new algorithm, which based on ant colony algorithm and quantum revolving gate is designed in Reference [18]. In Reference [19], a global path planning algorithm based on an improved quantum ant colony algorithm is proposed. The improved quantum ant colony algorithm is an algorithm that benefits from the high efficiency of quantum computing and the optimization ability of the ant colony algorithm.

According to the above research, although the introduction of artificial potential field method can improve the convergence speed of ant colony algorithm, it is prone to the problem of local minimum. However, quantum evolutionary algorithms can solve local and small-value problems well. Based on the above analysis, this paper proposes an improved ant colony algorithm that takes into account both the convergence speed and the optimization ability. On the one hand, the potential field force of the artificial potential field algorithm is introduced into the heuristic information of the ant colony algorithm. The heuristic information of the potential field force can reduce the blindness of the search caused by the insignificant positive feedback effect of the ant colony algorithm in the early stage of path planning. On the other hand, the quantum evolution algorithm is introduced into the pheromone update. The pheromone is represented by quantum bits, and the pheromone is updated by quantum revolving door feedback control. In this way, it can not only reflect the high efficiency of quantum parallel computing, but also have the better optimization ability of ant colony algorithm.

The rest of this paper is organized as follows: The principle of algorithms are described in Section 2, which include ant colony algorithm, artificial potential Field, and quantum evolution theory. Section 3 introduces improved ant colony algorithm, which introduced potential field force analysis, synthetic heuristic information structure, pheromone structure and update, and the proposed algorithm flow. In Section 4, the results are given for simulation to verify the proposed algorithm. Finally, conclusions are drawn in section 5.

2 Introduction of algorithms

2.1 Principles of ant colony Algorithm

The traditional ant colony algorithm is a bionic algorithm that simulates the foraging process of ant colonies in nature. Entomologists have discovered that ant colonies can find the shortest path between the nest and the food source without visual information and central control. Studies have found that during the foraging process, ants release a special chemical substance called pheromone on the path of travel to help find the shortest path. In an unknown environment, the ants will randomly choose a path to the food source and release pheromone during the round trip. The strength of the pheromone is inversely proportional to the length of the path. When other ants make path selection, they will choose the path according to the intensity of the pheromone on the path, and the path with high pheromone intensity will have a greater probability of being selected. Therefore, there will be more ants to choose a shorter path, and more and more pheromone will accumulate, which will attract more ants to follow this path, forming a positive feedback mechanism, and making the optimal path more Selection of ants [20, 21].

Ant colony algorithm is an algorithm proposed by Italian scholar Marco Dorigo in the early 1990 s to simulate ant foraging and to solve traveling salesman and distributed optimization problems [22]. Research has found that when ants are foraging, they leave behind a chemical substance that is attractive to the same species: pheromone. Each ant will be affected by other ant pheromones and will release pheromones along the path it passes. When ants choose a path, they will choose a path with more pheromone with a greater probability. This positive feedback effect makes the passing ants tend to choose the shortest path. Ant colony algorithm includes two parts: path construction and pheromone update.

➀ Path construction rules

Assuming that the total number of ants in the ant colony is M, each ant moves in a grid environment, and the next grid is selected according to the state transition rule. Assuming that at time t, ant k is located on grid i, then the probability that ant k selects the next grid j is:

$P_{ij}^{k} (t) = {\begin{matrix} \frac{τ_{ij}^{α} (t) η_{ij}^{β} (t)}{\sum_{v \in V} τ_{iv}^{α} (t) η_{iv}^{β} (t)}, j \in V \\ 0, j \notin V \end{matrix}$ (1) where, V represents the set of the next grid that ant k can choose, α represents the heuristic factor of pheromone concentration. The larger the α is, the more the ant k tends to choose the path that most ants traverse. β represents the visibility heuristic factor, which reflects the effect of visibility information on the ant’s choice of the next position. The larger the value of β is, the more the ant k tends to select the grid that is closer to the end point. τ_ij (t) represents the pheromone concentration on the path (i, j) at time t. η_ij (t) represents the heuristic information on the path (i, j) at time t, which is defined as [23, 24]:

$η_{ij} (t) = \frac{1}{d_{ig}}$ (2) where g is the target grid, and d_ig represents the Euclidean distance from grid i to grid g. The greater the distance between two points, the smaller the heuristic, and the smaller the probability of the ant choosing node g at node i. Heuristic information is a kind of local information, which can guide the ants to quickly construct better solutions in the initial stage, which greatly improves the efficiency of the algorithm in the early stage.

➁ Pheromone update:

When the ant colony passes a certain grid, it will leave a pheromone, and the pheromone will disappear over time. Therefore, after each ant walks through a grid, it must update the local pheromone. The update formula is as follows:

$τ_{ij} (t + 1) = p \cdot τ_{ij} (t) + Δ τ_{ij}^{k}$ (3)

$Δ τ_{ij}^{k} = {\begin{matrix} \frac{Q}{L_{se}}, se \in i, j \\ 0, otherwise \end{matrix}$ (4) where p represents the residual degree of pheromone, and the value range is (0 < p < 1), Q is a constant, and L_se represents the length of the path traversed by the ant, which can be expressed as:

$L_{se} = \sum_{l = 1}^{w} d_{l}$ (5)

Where w is the number of steps that ant k has walked in this cycle, and d_l is the length of the side that ant k has walked.

2.2 Principle of artificial potential field

The artificial potential field method was proposed by KHATIB. Artificial potential field method is a path planning algorithm widely used in the field of robots and smart cars [25]. A virtual force field is used to establish a constraint relationship between the robot, the exit position, and the obstacle [26]. The basic principle is shown in Fig. 1. In the working environment of the robot, the gravitational force of the target point on the robot is unique. The gravitational force guides the robot to the exit. However, the repulsion force received by the robot is not unique, and the amount of repulsion force received corresponds to the number of obstacles. There are two obstacles in Fig. 1, so there are two repulsive forces, F₁ and F₂ respectively. The sum of these two repulsive force vectors F₃ is the total repulsive force experienced by the robot. The vector sum of the repulsive force F₃ and the gravitational force F₄ is the resultant force F received by the robot, which will guide the robot to avoid collision with obstacles when moving to the exit point.

Fig. 1

Schematic diagram of force analysis in artificial potential field.

2.3 Quantum evolution theory

Quantum computing is a newly emerging research field in recent years. It is produced by the intersection of information science and quantum mechanics. In 1994, Shor [27] proposed a quantum algorithm for solving the prime factorization of large numbers. In 1996, Grover [28] proposed a quantum quadratic acceleration algorithm for searching disordered databases, and the powerful computing power of quantum computing began to be widely concerned in the world [29]. Quantum evolutionary algorithm is an evolutionary algorithm based on quantum evolution theory. It mainly includes qubits and quantum revolving gates.

➀ Quantum bit:

In classic QEA, a quantum bit the smallest information unit, that is, a Q bit. A simple qubit is a two-state system, and its state space consists of two bases |0 and |1. | > is the representation of the quantum state. In addition to the 0 state and 1 state, a qubit can also be in their superposition state, which is expressed as: |φ_i > = α_i|0 > + β_i|1 >, i = 1, 2, ⋯ n. Where α and β are arbitrary complex numbers that satisfy the superposition condition |α|² + |β|² = 1. The |α|² and |β|² values represent the probability that the qubit is in the “0” state or the “1” state. It can be expressed as:

$q_{j} = [\begin{matrix} α α_{2} \dots α_{n} \\ β β_{2} \dots β_{n} \end{matrix}]$ (6)

The qubit has 2ⁿ states, for example, the following formula has 3 bits:

$q_{3} = [\begin{matrix} \frac{1}{\sqrt{2}} \frac{1}{\sqrt{2}} \frac{1}{2} \\ \frac{1}{\sqrt{2}} \frac{- 1}{\sqrt{2}} \frac{\sqrt{3}}{2} \end{matrix}]$ (7)

Can be expressed as:

$\begin{matrix} \frac{1}{4} | 000 > + \frac{\sqrt{3}}{4} | 001 > - \frac{\sqrt{3}}{4} | 011 > + \frac{1}{4} | 100 > \\ + \frac{\sqrt{3}}{4} | 101 > - \frac{1}{4} | 110 > - \frac{\sqrt{3}}{4} | 111 > \end{matrix}$ (8)

Its state probability is |001 > , |010 > , |011 > , |100 > , |101 > , |110 > , |111 >. It can be expressed as: 1/16, 3/16, 1/16, 3/16, 1/16, 3/16, 1/16, 3/16.

➁ Quantum revolving door:

In quantum theory, the change of qubits is achieved through quantum gates [30]. The quantum revolving gate has a great influence on the performance of the algorithm, and its update formula is as follows:

$[\begin{matrix} α_{i}^{'} \\ β_{i}^{'} \end{matrix}] = [\begin{matrix} \cos θ_{i} - \sin θ_{i} \\ \sin θ_{i} \cdot \cos θ_{i} \end{matrix}] [\begin{matrix} α_{i} \\ β_{i} \end{matrix}]$ (9)

Where θ_i represents the angle of rotation, and its size and direction can be obtained by dynamic adjustment or a look-up table. i = (1, 2, ⋯ , m) , [α_iβ_i] ^T represents the probability amplitude of the i-th qubit before and after the quantum spin gate processing, which satisfies the normalization condition:

${| α_{i} |}^{2} + {| β_{i} |}^{2} = 1$ (10)

3 Proposed improved ant colony algorithm

3.1 Potential field force analysis

In this paper, the heuristic information of artificial potential field force is introduced into the heuristic information of traditional ant colony algorithm. The artificial potential field force information enables pedestrians to quickly avoid obstacles and move toward the target grid during the movement [31, 32]. The heuristic information of potential field force is constructed by the artificial potential field force received by pedestrians. This part of the heuristic information can be:

$η_{F} (t) = a^{F_{tot} \cos θ}$ (11) where a > 1 is a constant, F_tot represents the force of the people, and θ represents the angle between the situational force F_tot and the direction of the pedestrian’s feasible path. The derivation of the F_tot theory of the potential situation force in the heuristic information is as follows: Assuming that the current position of the pedestrian is P and the target position is G, the repulsion potential field function in this paper can be expressed as:

$\begin{matrix} U_{rep} (P) \\ = {\begin{matrix} \frac{1}{2} K_{rep} {(\frac{1}{d (P, O)} - \frac{1}{d_{0}})}^{2} d^{n} (P, G), d (P, O) < d_{0} \\ 0, d (P, O) ⩾ d_{0} \end{matrix} \end{matrix}$ (12)

The traditional repulsion function can be expressed as:

$U_{rep} (P) = {\begin{matrix} \frac{1}{2} K_{rep} {(\frac{1}{d (P, O)} - \frac{1}{d_{0}})}^{2}, d (P, O) < d_{0} \\ 0, d (P, O) ⩾ d_{0} \end{matrix}$ (13)

Compared with the traditional repulsion function, this paper introduces the distance between the current position and the target position. Under the action of the new repulsion function, this ensures that the entire potential field is globally minimized at the target position. This solves the problem that the artificial potential field algorithm is easy to fall into target unreachable and local stability.

The repulsion in this paper can be expressed as follows:

$\begin{matrix} {\bar{F}}_{rep} (P) = {grddU}_{rep} (P) \\ = {\begin{matrix} {\bar{F}}_{rep 1} (P) + {\bar{F}}_{rep 2} (P), d (P, O) < d_{0} \\ 0, d (P, O) ⩾ d_{0} \end{matrix} \end{matrix}$ (14)

Where

$\begin{matrix} {\bar{F}}_{rep 1} (P) = \\ K_{rep} (\frac{1}{d (P, O)} - \frac{1}{d_{0}}) \frac{1}{d^{2} (P, O)} d^{n} (P, G) {\bar{n}}_{OP} \end{matrix}$ (15)

$\begin{matrix} {\bar{F}}_{rep 2} (P) = \\ \frac{n}{2} K_{rep} {(\frac{1}{d (P, O)} - \frac{1}{d_{0}})}^{2} d^{n - 1} (P, G) {\bar{n}}_{OG} \end{matrix}$ (16)

Where K_rep represents the constant repulsion field, O represents the position of the obstacle, and G represents the target position. d (P, O) is expressed as the Euclidean distance between the two positions of P and O. The vector direction is on the line connecting the two positions and points from the obstacle position to the pedestrian position. d (P, G) represents the Euclidean distance between the two positions of P and G, and the vector direction is on the line connecting the two positions and points to the target position. ${\bar{n}}_{PG}$ represents the unit vector from the pedestrian’s current position P to the target position G. d₀ represents the range of influence of the repulsive force field. When the distance between the obstacle and the pedestrian is greater than d₀, the repulsive force field will no longer affect the movement path of the pedestrian. The direction of the vector ${\bar{F}}_{rep 1} (P)$ is from the obstacle position to the pedestrian position. The direction of the vector ${\bar{F}}_{rep 2} (P)$ is from the pedestrian position to the target position. The physical relationship between the repulsion force and the two partial repulsion forces is shown in Fig. 2.

Fig. 2

The new potential field function is used to analyze the force on the pedestrian.

The attractive potential field function is defined as:

$U_{att} (P) = \frac{1}{2} K_{att} d^{2} (P, G)$ (17)

Attraction can be expressed as:

${\bar{F}}_{att} (P) = {gradU}_{att} (P) = K_{att} d (P, G) {\bar{n}}_{PG}$ (18)

Where K_att represents the gravitational potential field constant, then the potential field force can be expressed as:

$\begin{matrix} {\bar{F}}_{tot} (P) = {\bar{F}}_{att} (P) + {\bar{F}}_{rep} (P) = \\ {\begin{matrix} K_{att} d^{2} (P, G) {\bar{n}}_{PG} + {\bar{F}}_{rep 1} (P) + {\bar{F}}_{rep 2} (P) \\ , d (P, O) < d_{0} \\ K_{att} d^{2} (P, G) {\bar{n}}_{PG}, d (P, O) ⩾ d_{0} \end{matrix} \end{matrix}$ (19)

When evacuating in a complex environment, pedestrians move to the exit position by quickly avoiding obstacles under the influence of the situation. Combined with the distance heuristic information in the ant colony algorithm, it can achieve the purpose of path planning more quickly.

3.2 Synthetic heuristic information structure

First, construct the influence coefficient χ of the potential field force heuristic information. The influence coefficient of potential field force heuristic information χ is mainly used to strengthen or reduce the influence of artificial potential field force heuristic information in the path planning process. Its value decreases with the increase of the number of ant colony iterations, as the following formula:

$χ = \frac{N_{\max} - N_{m}}{N_{\max}}$ (20)

Where N_max represents the maximum number of iterations, and N_m represents the current number of iterations. Under the effect of the influence coefficient χ of the potential field force heuristic information, the heuristic information of the potential field ant colony algorithm in the early stage of path planning mainly depends on the potential field force heuristic information. In this way, the ants can quickly find the sub-optimal solution to reach the target position, and it can also avoid the situation that a large number of inferior solutions are generated due to the lack of pheromone in the initial stage. As the number of ant cycles increases, it is necessary to reduce the role of the potential field force to enlighten information. Otherwise, the ants are excessively concentrated in the direction of the gradient of the potential field distribution. In turn, the pheromone concentration on these paths is too strong, thereby weakening the search for better quality paths. The influence coefficient χ of the potential field force function can also effectively solve this phenomenon.

The enlightenment information of traditional ant colony algorithm is shown in formula (2). Thecomprehensive heuristic information constructed by the artificial potential field algorithm is as follows:

$η_{ij} (t) = η_{F} (t) \cdot η_{d} (t) \cdot χ = \frac{a^{F_{tot} \cos θ}}{d (P, G)} \cdot χ$ (21)

Under the action of the comprehensive heuristic information η_ij (t), pedestrians can effectively avoid collisions with obstacles, avoid blind search in the initial stage, and pedestrians can quickly plan their paths.

3.3 Pheromone structure and update

This paper introduces quantum evolution theory to construct pheromone. Pheromone qubits can be expressed as:

$Q = (q_{1}, q_{2}, \dots, q_{j}, \dots, q_{m}), j = 1, 2, \dots, t$ (22)

For each individual, q_j has n bits, as shown in formula (6).

In the classic ant colony, there will be more and more pheromones along the path that the ants pass. The pheromone on the non-passing path is less and less, and the number of iterations is used as the exponential decrease. Finally, the pheromone on one path is the largest, and the other paths are reduced to 0, making the algorithm fall into the local optimum. In the later stage of the search, the convergence rate slows down due to the small change in pheromone. The quantum ant colony algorithm introduces the quantum revolving door, and the revolving door is used to update the pheromone, which can effectively prevent premature maturity and speed up the convergence.

After the introduction of quantum theory, the update process (α_ji, β_ji) ^T of the i-th pheromone for the j-th ant individual in the qubit in the ant colony algorithm is as follows:

$[\begin{matrix} α_{ji}^{″} \\ β_{ji}^{″} \end{matrix}] = Q [\begin{matrix} α_{ji} \\ β_{ji} \end{matrix}]$ (23)

$Q = [\begin{matrix} \cos θ_{ji} - \sin θ_{ji} \\ \sin θ_{ji} \cos θ_{ji} \end{matrix}]$ (24)

The size of the revolving door is:

$θ_{ji} = Δ θ_{ji} \times s (α_{ji}, β_{ji}), i = 1, 2, \dots, n$ (25)

$Δ θ = 0.5 \cdot π \cdot \exp (\frac{- t}{t_{\max}})$ (26)

Where ${(α_{ji}^{″}, β_{ji}^{″})}^{T}$ represents the update bit, θ_ji represents the rotation angle, and Δθ represents a variable related to the number of iterations, which determines the quantum rotation angle value, convergence speed and performance. However, this paper uses a dynamic adjustment strategy to define Δθ as formula (26). Among them, π represents the circumference ratio, t represents the current iteration number, t_max represents the upper limit of the iteration, and s (α_ji, β_ji) represents the function of controlling the direction of rotation. When s (α_ji, β_ji) > 0, the quantum revolving door rotates counterclockwise. When s (α_ji, β_ji) < 0, the quantum revolving door rotates clockwise. Figure 3 shows the polar coordinates of the rotating gate of the qubit.

Fig. 3

Quantum gate rotating polar coordinate diagram.

3.4 The proposed algorithm flow

The proposed improved ACO Algorithm steps are as follows:

Step 1: Based on the grid method to model the environment of the pedestrian evacuation space. Set the pedestrian starting grid, target exit grid and obstacle grid.

Step 2: Initialize the relevant parameters of the algorithm, including the gravitational constant K_att of the artificial potential field, the repulsion constant K_rep, and the obstacle repulsion range d₀. The number of ants m, the number of iterations N_max, the heuristic factors α, β, the pheromone concentration Q and the pheromone concentration volatilization coefficient ρ are initialized for the ant colony search mechanism.

Step 3: Place m ants at the starting position.

Step 4: Under the comprehensive heuristic information of formula (21), the ant selects the next arrival position according to the transfer rule formula (1), and stores the position in the taboo table.

Step 5: Judge whether m ants reach the target position. If yes, calculate the length of each ant’s search path to find the optimal path for the current search. Otherwise, go to step 4.

Step 6: According to formulas (23) (26), the pheromone concentration of the ant colony algorithm is updated through the quantum revolving door.

Step 7: Determine whether the maximum number of iterations is reached. If it has reached the maximum number of iterations, the algorithm will be terminated, and the length of each search path will be output to find the optimal path; otherwise, go to step 3.

4 Simulation and analysis

In order to verify the effectiveness of the improved ant colony algorithm proposed in this paper, a simulation experiment is designed. The simulation experiment is divided into three parts according to the complexity of the simulation environment, which include simulation environment 1, simulation environment 2 and simulation environment 3. The complexity of the simulation environment increases successively, and the simulation environment 3 is the most complicated. In terms of algorithm comparison, two other algorithms are introduced to verify the effectiveness of the method proposed in this paper. The three algorithms are as follows:

Original ACO: original ant colony algorithm.

Algorithm in [33]: the artificial potential field ant colony algorithm (APF-ACO) proposed in Reference [33].

Improved ACO: the improved ACO algorithm is proposed in this paper, which based on artificial potential field and quantum evolution theory.

Equipment information used for experimental analysis: CPU i5-8265U, main frequency 1.6 GHz, RAM 8GB. And the experiment was carried out on a grid map of (20 m×20 m). Each algorithm is performed in Matlab2018a, and the OS is windows 10.

The simulation assumption parameters is listed in Table 1.

Table 1
Simulation assumption parameters

Parameter Value

Pheromone factor (α) 1

Heuristic factor (β) 3

Number of ants 50

The maximum number of iterations 100

Pheromone volatilization factor 0.2

Pheromone initial value 10

Pheromone intensity 10

Potential field gravity (ξ) 0.005

Parameter	Value
Pheromone factor (α)	1
Heuristic factor (β)	3
Number of ants	50
The maximum number of iterations	100
Pheromone volatilization factor	0.2
Pheromone initial value	10
Pheromone intensity	10
Potential field gravity (ξ)	0.005

4.1 Path planning simulation environment 1

Figs. 4, 5, and 6 are the path diagrams of the three methods in the simulation environment 1 respectively.

Fig. 4

The path of original ACO in simulation environment 1.

Fig. 5

The path of algorithm in [33] in simulation environment 1.

Fig. 6

The path of improved ACO in simulation environment 1.

In the grid graph of simulation environment 1, the coordinates of the starting point are (0 m, 20 m), and the coordinates of the target point are (20 m, 0 m). It can be seen from the figure that all three methods can effectively plan the route and reach the target point. In order to further analyze the performance of the three methods, the iterative convergence diagrams are drawn on the basis of the above results, as shown in Figs. 7, 8, and 9 respectively.

Fig. 7

Iterative convergence graph of original ACO in simulation environment 1.

Fig. 8

Iterative convergence graph of algorithm in [33] in simulation environment 1.

Fig. 9

Iterative convergence graph of improved ACO in simulation environment 1.

It can be roughly seen from the figure that the original ACO has a longer iteration time, while the improved ACO proposed in this paper has the least iteration time. The iteration time, average path length, optimal path length, and worst path length of the three methods are listed in Table 2.

Table 2

Simulation results of different methods in simulation environment 1

	Original ACO	Algorithm in [33]	Improved ACO
Iteration time (s)	6.41	6.28	5.82
Average path length (m)	33.07	31.93	31.81
Optimal path length (m)	31.55	31.55	31.54
Worst path length (m)	46.87	40.87	39.21

It can be seen from Table 2 that the iteration time of the improved ACO proposed in this paper is 5.82 s, which has the least iteration time compared to the original ACO and Algorithm in [33]. In terms of average path length, the average path lengths of the three methods are 33.07 m, 31.93 m and 31.81 m. It can be seen that the improved ACO proposed in this paper is optimal in terms of iteration time, average path length, and worst path length. In the simulation environment 1, the optimal path lengths of the three methods are roughly the same.

In order to verify the repeatability of the proposed method in the simulation environment 1. For the three methods, 10 repeated experiments were carried out. The iteration time and average path length results are shown in Figs. 10 and 11, respectively.

Fig. 10

Iterative time of different methods in simulation environment 1.

Fig. 11

Average path length of different methods in simulation environment 1.

It can be seen from Fig. 10 that the improved ACO (red line) proposed in this paper has the least iteration time in 10 repeated experiments. It can be seen from Fig. 11 that, compared to the original ACO, both Algorithm in [33] and the improved ACO have a shorter average path length. And the improved ACO proposed in this paper has the shortest average path length.

Next, on the basis of simulation environment 1, the influence of the parameters α and β on the iteration time is analyzed.

α is the information heuristic factor, which reflects the role of the pheromone accumulated during the movement of the ant during the movement of the ant. The larger the value of α, the greater the probability of choosing the path that has been traversed before, and the less randomness of the search path. If the α value is too small, the positive feedback function of the algorithm is reduced, the search range is reduced, and it is easy to fall into the local optimum.

β is the expected heuristic factor, which reflects the importance of the heuristic information in the ant’s selection path during the movement. The larger the value of β, the faster the algorithm converges, but the search randomness decreases. The smaller the value of β, the stronger the global search capability, but the convergence speed decreases. The simulation results of α and β in simulation environment 1 is listed in Table 3.

Table 3

Simulation results of α and β in simulation environment 1

Value	Iteration time (s)	Value	Iteration time (s)
α = 1, β = 1	7.54	α = 1, β = 1	7.54
α = 2, β = 1	7.23	α = 1, β = 2	7.13
α = 3, β = 1	6.68	α = 1, β = 3	5.82
α = 4, β = 1	6.32	α = 1, β = 4	6.12
α = 5, β = 1	6.97	α = 1, β = 5	6.59

4.2 Path planning simulation environment 2

On the basis of the grid simulation environment 1, the complexity of the simulation environment is further improved, as shown in the following figure. Figures 12, 13, and 14 are the path diagrams of the three methods in the simulation environment 2 respectively.

Fig. 12

The path of original ACO in simulation environment 2.

Fig. 13

The path of algorithm in [33] in simulation environment 2.

Fig. 14

The path of improved ACO in simulation environment 2.

It is obvious from the three figures that the path in Fig. 12 is longer than that in Figs. 13 and 14. With the complexity of the simulation environment, this effect will become more and more obvious.

In order to further analyze the performance of the three methods, the iterative convergence diagrams are drawn on the basis of the above results, as shown in Figs. 15, 16, and 17 respectively.

Fig. 15

Iterative convergence graph of original ACO in simulation environment 2.

Fig. 16

Iterative convergence graph of algorithm in [33] in simulation environment 2.

Fig. 17

Iterative convergence graph of improved ACO in simulation environment 2.

It can be seen from Fig. 15 that the original ACO only stabilized after 80 iterations. It can be seen from Fig. 16 that Algorithm in [33] stabilizes only after about 10 iterations. Then, in Fig. 17 of the improved ACO proposed in this paper, it can be seen that it can stabilize after about 5 iterations. Compared with simulation environment 1, this effect is more obvious in simulation environment 2.

The simulation results of different methods in simulation environment 2 is listed in Table 4. It can be seen from Table 4 that the iteration time of the improved ACO proposed in this paper is 5.93 s, which has the least iteration time compared to the original ACO and Algorithm in [33]. In terms of average path length, the average path lengths of the three methods are 32.87 m, 30.15 m and 29.86 m respectively. It can be seen that the improved ACO proposed in this paper is optimal in terms of iteration time, average path length, and worst path length.

Table 4

Simulation results of different methods in simulation environment 2

	Original ACO	Algorithm in [33]	Improved ACO
Iteration time (s)	6.80	6.57	5.93
Average path length (m)	32.87	30.15	29.86
Optimal path length (m)	29.79	29.78	29.78
Worst path length (m)	44.28	38.04	33.21

In order to verify the repeatability of the method proposed in this paper in the simulation environment 2. For the three methods, 10 repeated experiments were carried out. The iteration time and average path length results are shown in Figs. 18 and 19, respectively.

Fig. 18

Iterative time of different methods in simulation environment 2.

Fig. 19

Average path length of different methods in simulation environment 2.

It can be seen from Fig. 18 that the improved ACO (red line) proposed in this paper has the least iteration time in 10 repeated experiments. It can be seen from Fig. 19 that, compared to the original ACO, both Algorithm in [33] and the improved ACO have a shorter average path length. And the improved ACO proposed in this paper has the shortest average path length.

4.3 Path planning simulation environment 3

In order to further verify the performance of the method proposed in this paper under different simulation environments, the complexity of the simulation environment is further improved on the basis of the grid simulation environment 2, as shown in the following figure.

Figures 20, 21 and 22 are the path diagrams of the three methods in the simulation environment 3 respectively. It can be seen from the figure that the path of the method proposed in this paper is smoother. In order to further analyze the performance of the three methods, the iterative convergence diagrams are drawn on the basis of the above results, as shown in Figs. 23, 24 and 25 respectively.

Fig. 20

The path of original ACO in simulation environment 3.

Fig. 21

The path of algorithm in [33] in simulation environment 3.

Fig. 22

The path of improved ACO in simulation environment 3.

Fig. 23

Iterative convergence graph of original ACO in simulation environment 3.

Fig. 24

Iterative convergence graph of algorithm in [33] in simulation environment 3.

Fig. 25

Iterative convergence graph of improved ACO in simulation environment 3.

It can be seen from Fig. 23 that the original ACO only stabilized after iterated 100 times. Then, Algorithm in [33] and improved ACO stabilized after about 25 iterations. In the three simulated evacuation environments, the improved ACO has the fastest convergence speed.

The simulaiton results of different methods in simulation environment 3 is listed in Table 5. It can be seen from Table 5 that the iteration time, average path length, optimal path length, and worst path length of the improved ACO are 6.19 s, 35.37 m, 30.97 m and 42.28 m, respectively. Compared with the original ACO and Algorithm in [33], the results are both optimal.

Table 5

Simulation results of different methods in simulation environment 3

	Original ACO	Algorithm in [33]	Improved ACO
Iteration time (s)	6.36	6.27	6.19
Average path length (m)	37.61	35.81	35.37
Optimal path length (m)	33.21	32.04	30.97
Worst path length (m)	53.70	42.87	42.28

In addition, in simulation environment 3, the effect of improving the optimal path length of ACO is more obvious than the other two methods. It shows that as the complexity of the environment increases, the effect of improving ACO in optimal path planning is getting better and better.

In order to verify the repeatability of the proposed method in simulation environment 3. For the three methods, 10 repeated experiments were carried out. The iteration time and average path length results are shown in Figs. 26 and 27, respectively. Because the optimal path length of the improved ACO proposed in this paper is obvious in simulation environment 3. Therefore, the optimal path length results for 10 repeated experiments are drawn as shown in Fig. 28.

Fig. 26

Iterative time of different methods in simulation environment 3.

Fig. 27

Average path length of different methods in simulation environment 3.

Fig. 28

Optimal path length of different methods in simulation environment 3.

The improved ACO has the best results in multiple repeated experiments in a complex simulation environment.

According to simulation environment 3, we can get the computational complexity of different algorithm, which is listed in Table 6.

Table 6

The computational complexity of different algorithm

	Original ACO	Algorithm in [33]	Improved ACO
Time (s)	0.197	0.233	0.254

From the Table 5, we know that the proposed improved ACO has the greatest complexity. However, on the one hand, the complexity of the three algorithms is very close. On the other hand, the proposed improved ACO algorithm has a faster convergence rate. Therefore, although it takes a long time, the overall number of iterations is small and the total time is short.

In the simulation analysis part, this paper verifies the performance of the improved ACO from two aspects of simulation environment of different complexity and repeated experiments. The following conclusions can be drawn from the simulation results:

The improved ACO proposed in this paper is better than the original ACO and Algorithm in [33] in terms of iteration speed, average path length, optimal path length, and worst path length.

As the complexity of the environment increases, the improved ACO path planning proposed in this article is more effective

The improved ACO simulation results presented in this paper have good repeat stability.

5 Conclusion

An improved ant colony algorithm is proposed in this paper. Artificial potential field and quantum evolution theory are introduced in proposed algorithm, which based on ant colony algorithm. Compared with the traditional ant colony algorithm, the proposed algorithm can take into account both the convergence speed and optimization ability of path planning. In order to verify the effectiveness of the proposed algorithm, three different evacuation environments are designed. The following conclusions can be drawn from the simulation results: 1. Compared with the ant colony algorithm, the proposed improved ant colony algorithm has a faster convergence rate and can effectively avoid falling into the local optimum; 2. the proposed algorithm can be applied to It has good application value in different complex scenarios; 3. As the evacuation environment becomes more and more complex, the effect of the proposed algorithm becomes more obvious.

Footnotes

Acknowledgments

This work was supported by China Civil Aviation Administration Project (Grant Nos. ASSA2018/17 and ASSA2017/12).

References

Fang

, Song

, Zhang

and Wu

, Experiment and modeling of exit-selecting behaviors during a building evacuation, Physica A: Statistical Mechanics and its Applications 389(4) (2010), 815–824.

Kang

, Jeong

I.J.

and Kwun

J.B.

, Optimal facility–final exit assignment algorithm for building complex evacuation, Computers & Industrial Engineering 85 (2015), 169–176.

Khalid

A.M.N.

and Yusof

U.K.

, Dynamic crowd evacuation approach for the emergency route planning problem: Application to case studies, Safety Science 102 (2018), 263–274.

Fang

, Li

, Zhu

, Li

and Xiong

, An artificial bee colony-based multi-objective route planning algorithm for use in pedestrian navigation at night, International Journal of Geographical Information Science 31(10) (2017), 2020–2044.

Góez-Sánchez

G.D.

, Jaramillo-Garzón

J.A.

and Velásquez

R.A.

, Performance comparison of particle swarm optimization and Cuckoo search for online route planning, IEEE Aerospace and Electronic Systems Magazine 33(10) (2018), 40–50.

Kumar

, Amgoth

and Annavarapu

C.S.

, ACO-based mobile sink path determination for wireless sensor networks under non-uniform data constraints, Applied Soft Computing 69 (2018), 528–540.

Donta

P.K.

, Amgoth

and Annavarapu

C.S.

, An extended ACO-based mobile sink path determination in wireless sensor networks, Journal of Ambient Intelligence and Humanized Computing 1 (2020), 1–16.

Zhang

and Xiong

, Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithm, Applied Soft Computing 71 (2018), 917–925.

K.B.

, Lu

H.Y.

, Cheng

B.Y.

and Huang

, Improved pheromone secondary update and local optimization ant colony algorithm for solving tsp, Journal of Computer Applications 37(6) (2017), 1686–1691.

10.

Meng

X.P.

, Pian

Z.Y.

, Shen

Z.Y.

and Yuan

Q.D.

, Ant colony algorithm based on directional pheromone coordination, Control and Decision 28(5) (2013), 782–786.

11.

Zhang

L.Y.

, Xiao

and Fei

, Improved Ant Colony Algorithm Based on Bacteria Foraging, Computer Engineering and Science 40(10) (2018), 170–177.

12.

Chen

and Yang

, An Ant Colony Algorithm for Robot Path Planning, Systems Engineering and Electronics 30(5) (2008), 952–955.

13.

Brand

, Masuda

and Wehner

, Ant colony optimization algorithm for robot path planning, international conference on computer design and applications. IEEE 3 (2010), 436–440.

14.

Zeng

M.R.

, Xu

X.Y.

and Liu

, Improved ant colony optimization with potential field heuristic for robot path planning, Comput Eng Appl 51(22) (2015), 33–37.

15.

Liu

, Yang

and Liu

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

16.

Wang

, Yu

and Wang

, Ant colony optimization with improved potential field heuristic for robot path planning, 2018 37th Chinese Control Conference (CCC). IEEE (2018), 5317–5321.

17.

Zhu

, Ma

and Hong

Q.Y.

, Improvement of Ant Colony Method Track Planning Based on Artificial Potential Field Method, 2020 16th International Conference on Control, Automation, Robotics and Vision (ICARCV). IEEE (2020), 1394–1398.

18.

Zhang

, Yang

and Lin

, A test suite reduction method based on novel quantum ant colony algorithm, 2017 4th International Conference on Information Science and Control Engineering (ICISCE). IEEE (2017), 825–829.

19.

Xia

, Han

and Zhao

, Global path planning for unmanned surface vehicle based on improved quantum ant colony algorithm, Mathematical Problems in Engineering 1 (2019), 1–6.

20.

Chen

and Long

, Task scheduling of cloud computing using integrated particle swarm algorithm and ant colony algorithm, Cluster Computing 22(2) (2019), 2761–2769.

21.

Liao

, Research on PAGV path planning based on artificial immune ant colony fusion algorithm, Journal of Intelligent & Fuzzy Systems 35(3) (2018), 2821–2826.

22.

Dorigo

, Maniezzo

and Colorni

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

23.

Zhang

L.Y.

, Tseng

M.L.

, Wang

C.H.

, Xiao

and Fei

, Low-carbon cold chain logistics using ribonucleic acid-ant colony optimization algorithm, Journal of Cleaner Production 233 (2019), 169–180.

24.

Jovanovic

, Tuba

and Voß

, An efficient ant colony optimization algorithm for the blocks relocation problem, European Journal of Operational Research 274(1) (2019), 78–90.

25.

Chen

Y.B.

, Luo

G.C.

, Mei

Y.S.

, Yu

J.Q.

and Su

X.L.

, UAV path planning using artificial potential field method updated by optimal control theory, International Journal of Systems Science 47(6) (2016), 1407–1420.

26.

Park

S.O.

, Lee

M.C.

and Kim

, Trajectory planning with collision avoidance for redundant robots using jacobian and artificial potential field-based real-time inverse kinematics, International Journal of Control, Automation and Systems 18(8) (2020), 2095–2107.

27.

Shor

P.W.

, Algorithms for quantum computation: discrete logarithms and factoring, In Proceedings 35th annual symposium on foundations of computer science, (1994), 124–134.

28.

Grover

L.K.

, A fast quantum mechanical algorithm for database search, In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (1996), 212–219.

29.

, Liu

and Xu

, A quantum ant colony multi-objective routing algorithm in WSN and its application in a manufacturing environment, Sensors 19(15) (2019), 3334.

30.

Thakral

and Bansal

, Improved ant colony optimization for quantum cost reduction, Bulletin of Electrical Engineering and Informatics 9(4) (2020), 1525–1532.

31.

Panda

, Das

, Subudhi

and Pati

B.B.

, A comprehensive review of path planning algorithms for autonomous underwater vehicles, International Journal of Automation and Computing 17(3) (2020), 321–352.

32.

Song

, Liu

and Bucknall

, A multi-layered fast marching method for unmanned surface vehicle path planning in a time-variant maritime environment, Ocean Engineering 129 (2017), 301–317.

33.

Kumar

P.B.

, Rawat

and Parhi

D.R.

, Path planning of humanoids based on artificial potential field method in unknown environments, Expert Systems 36(2) (2019), 1–12.

An improved ant colony algorithm based on artificial potential field and quantum evolution theory

Abstract

Keywords

1 Introduction

2 Introduction of algorithms

2.1 Principles of ant colony Algorithm

3.1 Potential field force analysis

4 Simulation and analysis

Table 1 Simulation assumption parameters Parameter Value Pheromone factor (α) 1 Heuristic factor (β) 3 Number of ants 50 The maximum number of iterations 100 Pheromone volatilization factor 0.2 Pheromone initial value 10 Pheromone intensity 10 Potential field gravity (ξ) 0.005

Footnotes

Acknowledgments

References

Table 1
Simulation assumption parameters

Parameter Value

Pheromone factor (α) 1

Heuristic factor (β) 3

Number of ants 50

The maximum number of iterations 100

Pheromone volatilization factor 0.2

Pheromone initial value 10

Pheromone intensity 10

Potential field gravity (ξ) 0.005