Research on Application of Improved Quantum Optimization Algorithm in Path Planning

Abstract

For the building emergency evacuation path planning problem, existing algorithms suffer from low convergence efficiency and the problem of getting trapped in local optima. The Bloch Spherical Quantum Genetic Algorithm (BQGA) based on the least-squares principle for single-robot path planning and Bloch Spherical Quantum Bee Colony Algorithm (QABC) for multi-robots path planning are studied. Firstly, the characteristics of three-dimensional path planning are analyzed, and a linear decreasing inertia weighting approach is used to balance the global search ability of chromosomes and accelerate the search performance of the algorithm. Then, the application algorithm can generate a clear motion trajectory in the raster map. Thirdly, the least squares approach is used to fit the results, thus obtaining a progressive path. Finally, multi-robots path planning approaches based on QABC are discussed, respectively. The experimental results show that BQGA and QABC do not need to have a priori knowledge of the map, and they have strong reliability and practicality and can effectively avoid local optimum. In terms of convergence speed, BQGA improved by 3.39% and 2.41%, respectively, while QABC improved by 13.31% and 17.87%, respectively. They are more effective in sparse paths.

1. Introduction

In recent years, path planning has been a hot problem in the research field, such as in robot path planning and evacuation path planning [1,2]. Commonly used path planning algorithms include the ant colony algorithm [1], artificial potential field algorithm [3], genetic algorithm [4], and A* algorithm [5]. The core requirement of path planning is to plan the optimal and safest path from the starting point to the target one according to the optimization characteristics, such as shortest distance, shortest time, and lowest energy consumption [6,7,8]. With the development of emerging technologies, methods based on deep learning and quantum optimization algorithms have also been applied to the field of path planning [9,10,11,12].

Sabzekar et al. employed a deep deterministic policy gradient algorithm to model continuous environments, concurrently proposing an innovative inner product reward function, thereby enhancing the objective tracking and obstacle avoidance capabilities of unmanned aerial vehicles [9]. Liu et al. delved into the study of deep Q-learning models, greedy table-based Q-learning models, and online optimization frameworks for addressing the shortest path problem between two points and the issue of random obstacles [10]. The Quantum Optimization Algorithm (QOA) is a brand new evolutionary algorithm proposed by Ajit Narayanan and Mark Moore, who combined quantum computing theory into the classical genetic algorithm in 1996 [13]. Built upon quantum principles, the quantum optimization algorithm utilizes quantum bit encoding and updates populations through quantum gates to pursue the global optimal solution. Contrasting with traditional evolutionary algorithms, it boasts features like smaller population size, faster computation speed, and robust global optimality detection. The Quantum Genetic Algorithm (QGA) amalgamates the merits of quantum computing and genetic algorithms, finding applications in various domains such as function optimization, combinatorial optimization, image processing, data mining, and production scheduling. Consequently, it offers significant advantages and exhibits robust vitality, holding substantial theoretical value and promising application prospects for QOA.

Lewandowski et al. utilized Bloch spherical descriptions to model systems during the design of quantum reversible logic. Subsequently, Bloch spherical coordinates have frequently been employed in quantum logic operations and algorithms [14,15]. A QGA for asymptotic Bloch spherical search was proposed by Sheng Li, and applied to the extreme value optimization problem of multivariate functions [16]. Compared with the traditional optimization algorithm for solving complex nonlinear problems, the quantum genetic algorithm is generated under the guiding idea of de-coarsening, inheriting the strengths of the genetic algorithm while also mitigating some of the drawbacks, such as oversized populations and long convergence time, to some extent [17]. It achieves better optimization results than traditional algorithms.

With the rapid development of the social economy, building designs are becoming more complex and taller, resulting in more intricate internal passage distributions. However, most current algorithm research focuses on solving problems in two-dimensional building environments, which presents numerous limitations when dealing with the relatively complex three-dimensional space of modern buildings [18,19]. Hamacher et al. characterized the indoor path planning problem as a dynamic net-work flow problem, applying dictionary optimization algorithms to minimize evacuation time [20]. Pursals improved evacuation and inverse evacuation functions, proposing a novel evacuation formula to address evacuation problems [21]. Lujak, building upon shortest path indoor path planning, considering the unpredictability of hazardous conditions, introduced evacuation betweenness centrality and evacuation centrality, thereby enhancing the safety of evacuation routes [22]. Hong et al. addressed path planning problems in 3D scene-constrained spaces, presenting a three-stage heuristic approach for constructing route networks based on minimum weighted set covering to enhance the utilization efficiency of escape exits [23].

The path planning problem for the interior of a building is a typical non-deterministic polynomial problem. That is, it is the problem of shortest path usage time formed by a fixed number of branch nodes with constant start and end nodes [24]. In the whole path planning process, it is important to control the direction and distance of the path [25]. In the Bloch Sphere Quantum Genetic Algorithm (BQGA), the entire Bloch sphere is the search range for the optimal solution, especially since there is no clear direction for the search, so the blindness and uncertainty of the search greatly reduce the search efficiency and optimality. At the same time, the size of ∆θ and ∆φ in this algorithm usually needs to be determined according to the specific problem. If they take too small a value, they will make the optimization process slow and thus reduce efficiency. If they take too large a value, they will make the algorithm cross the global optimal solution or fall into premature convergence [26].

This paper focuses on researching evacuation path planning for large-scale buildings. To address the issues of local optima and low efficiency in path planning inside buildings, a Bloch spherical coordinate algorithm incorporating least squares theory and the Bloch Spherical Quantum Bee Colony Algorithm (QABC) are employed. Firstly, the characteristics of three-dimensional path planning are analyzed, and a linear decreasing inertia weighting approach is used to balance the global search ability of chromosomes and accelerate the search performance of the algorithm. Then, the application algorithm can generate a clear motion trajectory in the raster map. Thirdly, the least squares is used to fit the results, thus obtaining a progressive path. Finally, multi-robots path planning approaches based on QABC are discussed, respectively. The performance is verified by comparing with Ant Colony Algorithm (ACA), Genetic Algorithm (GA) and Artificial Bee Colony Algorithm (ABA).

2. Bloch Sphere Quantum Genetic Algorithm

The quantum genetic algorithm is a probabilistic optimization algorithm based on quantum computing principles, aiming to search for the optimal solution through the evolution and mutation operations of chromosome genes. Its advantages include a small population size, fast convergence, and robust global search capabilities. However, the quantum genetic algorithm requires measuring the state of quantum bits to obtain binary solutions, involving highly random and blind probabilistic operations. Comparing with the traditional QGA, an improved one uses Bloch spherical coordinates for encoding. It extends the search on each dimension to a three-dimensional search in space, with each chromosome occupying three positions in space, to increase the randomness and diversity of quantum chromosomes, and it constructs a new update strategy for quantum chromosomes by incorporating the coordinate transformation of the least square principle. Meanwhile, a selection formula for the variation angle is constructed to improve the search capability.

2.1. Quantum Chromosome Model

In quantum computing, the smallest unit of information is the quantum bit [27,28]. On the three-dimensional Bloch sphere, a qubit can be represented as (1).

$$\left|\phi \right.〉=\cos \frac{\theta }{2}\left|0\right.〉+e^{i\phi }\sin \frac{\theta }{2}\left|1\right.〉,$$

(1)

where $\cos \frac{\theta }{2}$ and $e^{i\phi }\sin \frac{\theta }{2}$ are complex numbers, which are called the probability amplitudes of the corresponding states of a qubit, and ${\left|\cos \frac{\theta }{2}\right|}^2$ and ${\left|e^{i\phi }\sin \frac{\theta }{2}\right|}^2$ represent the probability that the qubit is in $\left|0\right.〉$ or $\left|1\right.〉$, respectively [29,30]. The normalization condition is satisfied as (2).

$${\left|\cos \cos \frac{\theta }{2}\right|}^2+{\left|e^{i\phi }\sin \sin \frac{\theta }{2}\right|}^2=1,$$

(2)

On the Bloch sphere, a point p can be determined by two angles $\theta$ and $\phi$, as shown in Figure 1.

On the three-dimensional Bloch sphere, any qubit corresponds to a point on the sphere, after which the qubit can be expressed in Bloch spherical coordinates as:

$$\left|\phi \right.〉={\left[\cos \phi \sin \theta \hspace{1em}\sin \phi \sin \theta \hspace{1em}\cos \theta \right]}^{\mathrm{T}},$$

(3)

In the BQGA process, the Bloch spherical coordinate encoding of the qubit is directly adopted. Considering the three coordinates of the qubit as three juxtaposed genes, each chromosome contains three juxtaposed gene chains, and each gene chain represents an optimal solution [31]. Therefore, let $P_i$ be the i chromosome in the population, and the BQGA encoding method is shown as (4).

$$P_i=\left|\begin{array}{c}\cos {\phi }_{i1}\sin {\theta }_{i1}\\ \sin {\phi }_{i1}\sin {\theta }_{i1}\\ \cos {\theta }_{i1}\end{array}\right|\cdots \left|\begin{array}{c}\cos {\phi }_{in}\sin {\theta }_{in}\\ \sin {\phi }_{in}\sin {\theta }_{in}\\ \cos {\theta }_{in}\end{array}\right|,$$

(4)

where $0\le \theta \le \pi ,0\le \phi \le 2\pi$, $i=1,2,\cdots ,m.j=1,2,\cdots n.$

2.2. Solution Space Transformation and Coordinate Fitting

Then, apply solution space transformation and coordinate fitting to the chromosomes encoded with Bloch coordinates. Each chromosome within the population comprises 3n Bloch coordinates, representing n quantum bits [32]. Through linear transformation, these 3n coordinates can be mapped onto the solution space of the optimization problem, with each coordinate corresponding to an optimization variable within the solution space [33,34].

Let the corresponding solution space transformation formula of the j quantum bit on the i chromosome $p_i$ be

$$\left\{\begin{array}{c}{X}_{ix}^j=\frac{1}{2}\left[b_j\left(1+x_{ij}\right)+a_j\left(1-x_{ij}\right)\right]\\ X_{iy}^j=\frac{1}{2}\left[b_j\left(1+y_{ij}\right)+a_j\left(1-y_{ij}\right)\right]\\ X_{iz}^j=\frac{1}{2}\left[b_j\left(1+z_{ij}\right)+a_j\left(1-z_{ij}\right)\right]\end{array}\right.,$$

(5)

where $i=1,2,\cdots ,m\mathrm{a}\mathrm{n}\mathrm{d}j=1,2,\cdots n$. m is the population size and n is the number of qubits.

Least squares space fitting is introduced to seek the best function, which is matched for the data. The least squares criterion is a tool that has been widely used in disciplines such as uncertainty prediction [35]. Least-squares fitting is used in fitting linear equations to points in three-dimensional space, and can provide insight into the trend of variation between points, predict future changes in points, and ultimately enable the optimal solution to be determined.

Assuming that there are n data points that need to be fitted, $\left(x_1,y_1,z_1\right),\cdots ,\left(x_i,y_i,z_i\right)$. It can be obtained from the two plane equations as shown in (6).

$$Ax+By+Cz+D=0\left(C\ne 0\right),$$

(6)

Then it can be deduced that

$$z=-\frac{A}{C}x-\frac{B}{C}y-\frac{D}{C},$$

(7)

marked as $a=-\frac{A}{C}$, $b=-\frac{B}{C}$, $c=-\frac{D}{C}$, and $z=ax+by+c$.

The standard equation is

$$\frac{x-x_0}{X}=\frac{y-y_0}{Y}=\frac{z-z_0}{Z},$$

(8)

So the spatial straight line can be obtained from the intersection of the two planes above, and it van be fitted to fit the equations of these two planes. The least-squares principle is as follows.

$$M={\displaystyle \sum }_{i-1}^n{\left(a{x}_i+b{y}_i+c-z\right)}^2,$$

(9)

The partial derivative of (9) can be obtained, that is, the model parameters obtained by the least squares fitting.

$$\left\{\begin{array}{c}{\displaystyle \sum }2\left(a{x}_i+b{y}_i+c-z\right)x_i=0\\ {\displaystyle \sum }2\left(a{x}_i+b{y}_i+c-z\right)y_i=0\\ {\displaystyle \sum }2\left(a{x}_i+b{y}_i+c-z\right)=0\end{array}\right.,$$

(10)

Formula (10) can be derived.

$$\left\{\begin{array}{c}a{\displaystyle \sum }{x_i}^2+b{\displaystyle \sum }{x}_i{y}_i+c{\displaystyle \sum }{x}_i={\displaystyle \sum }{x}_i{z}_i\\ a{\displaystyle \sum }{x}_i{y}_i+b{\displaystyle \sum }{y_i}^2+c{\displaystyle \sum }{y}_i={\displaystyle \sum }{y}_i{z}_i\\ a{\displaystyle \sum }{x}_i+b{\displaystyle \sum }{y}_i+n={\displaystyle \sum }{z}_i\end{array}\right.,$$

(11)

$$\left[\begin{array}{ccc}{\displaystyle \sum }{x_i}^2& {\displaystyle \sum }{x}_i{y}_i& {\displaystyle \sum }{x}_i\\ {\displaystyle \sum }{x}_i{y}_i& {\displaystyle \sum }{y_i}^2& {\displaystyle \sum }{y}_i\\ {\displaystyle \sum }{x}_i& {\displaystyle \sum }{y}_i& n\end{array}\right]\left[\begin{array}{c}a\\ b\\ c\end{array}\right]=\left[\begin{array}{c}{\displaystyle \sum }{x}_i{z}_i\\ {\displaystyle \sum }{y}_i{z}_i\\ {\displaystyle \sum }{z}_i\end{array}\right],$$

(12)

Solutions include

$$\left\{\begin{array}{c}a=\frac{n{\displaystyle \sum }{x}_i{z}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{z}_i}{n{\displaystyle \sum }{x_i}^2-{\displaystyle \sum }{x}_i{\displaystyle \sum }{x}_i}-b\frac{n{\displaystyle \sum }{x}_i{y}_i-{\displaystyle \sum }{y}_i{\displaystyle \sum }{x}_i}{n{\displaystyle \sum }{x_i}^2-{\displaystyle \sum }{x}_i{\displaystyle \sum }{x}_i}\\ b=\frac{\left(n{\displaystyle \sum }{y}_i{z}_i-{\displaystyle \sum }{y}_i{\displaystyle \sum }{z}_i\right)\left(n{\displaystyle \sum }{x_i}^2-{\displaystyle \sum }{x}_i{\displaystyle \sum }{x}_i\right)-\left(n{\displaystyle \sum }{x}_i{z}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{z}_i\right)\left(n{\displaystyle \sum }{x}_i{y}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{y}_i\right)}{\left(n{\displaystyle \sum }{y_i}^2-{\displaystyle \sum }{y}_i{\displaystyle \sum }{y}_i\right)\left(n{\displaystyle \sum }{x_i}^2-{\displaystyle \sum }{x}_i{\displaystyle \sum }{x}_i\right)-\left(n{\displaystyle \sum }{x}_i{y}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{y}_i\right)\left(n{\displaystyle \sum }{x}_i{y}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{y}_i\right)}\\ c=\frac{{\displaystyle \sum }{z}_i-a{\displaystyle \sum }{x}_i-b{\displaystyle \sum }{y}_i}{n}\end{array}\right.,$$

(13)

We can substitute the obtained result into (7) to get:

$$\begin{array}{l}z=\left(\frac{n{\displaystyle \sum }{x}_i{z}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{z}_i}{n{\displaystyle \sum }{x_i}^2-{\displaystyle \sum }{x}_i{\displaystyle \sum }{x}_i}-b\frac{n{\displaystyle \sum }{x}_i{y}_i-{\displaystyle \sum }{y}_i{\displaystyle \sum }{x}_i}{n{\displaystyle \sum }{x_i}^2-{\displaystyle \sum }{x}_i{\displaystyle \sum }{x}_i}\right)x\\ \hspace{0.17em}\hspace{0.17em}+\frac{\left(n{\displaystyle \sum }{y}_i{z}_i-{\displaystyle \sum }{y}_i{\displaystyle \sum }{z}_i\right)\left(n{\displaystyle \sum }{x_i}^2-{\displaystyle \sum }{x}_i{\displaystyle \sum }{x}_i\right)-\left(n{\displaystyle \sum }{x}_i{z}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{z}_i\right)\left(n{\displaystyle \sum }{x}_i{y}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{y}_i\right)}{\left(n{\displaystyle \sum }{y_i}^2-{\displaystyle \sum }{y}_i{\displaystyle \sum }{y}_i\right)\left(n{\displaystyle \sum }{x_i}^2-{\displaystyle \sum }{x}_i{\displaystyle \sum }{x}_i\right)-\left(n{\displaystyle \sum }{x}_i{y}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{y}_i\right)\left(n{\displaystyle \sum }{x}_i{y}_i-{\displaystyle \sum }{x}_i{\displaystyle \sum }{y}_i\right)}y\\ \hspace{0.17em}\hspace{0.17em}+\frac{{\displaystyle \sum }{z}_i-a{\displaystyle \sum }{x}_i-b{\displaystyle \sum }{y}_i}{n}\end{array},$$

(14)

Finally, the variation formula of the solution space coordinate fitting that integrates the least squares principle can be obtained.

2.3. Updating and Vaviation of Quantum Chromosome

Thirdly, perform update and variation operations on the quantum chromosomes. In BQGA, the update of quantum chromosomes is generally realized by changing the quantum phase through a revolving gate [36]. The purpose of qubit phase rotation is to use each chromosome in the current population to approximate the contemporary optimal chromosome. In the process of approximation, it is possible to produce better contemporary optimal chromosomes, such that the population continues to evolve. The form of updating will be:

$$U=\left[\begin{array}{ccc}\cos \Delta \phi \cos \Delta \theta & -\sin \Delta \phi \cos \Delta \theta & \sin \Delta \theta \cos \left(\phi +\Delta \phi \right)\\ \sin \Delta \phi \cos \Delta \theta & \cos \Delta \phi \cos \Delta \theta & \sin \Delta \theta \sin \left(\phi +\Delta \phi \right)\\ -\sin \Delta \theta & -\tan \left(\raisebox{1ex}{$\phi $}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)\sin \Delta \theta & \cos \Delta \theta \end{array}\right],$$

(15)

The corresponding rules are proposed for the direction of the turning angle, which can be judged by the algebraic operation of the three-qubit coordinates of the current chromosome and the optimal chromosome. Based on the optimization theory and the changing trend of the objective function, this paper proposes a progressive Bloch spherical search method, which makes the search process more convenient, and avoids the blindness of the search.

As the number of iterations increases, Δθ and Δφ should gradually become stable. Therefore, Δθ and Δφ can be calculated asymptotically on the Bloch sphere with the least-squares theory. The sizes of the two corners of the quantum revolving doors can be derived by fitting the calculation to prevent the algorithm from losing the global optimal solution or prematurely converging.

Assuming that the algorithm evolves to the t generation, the updated formulas of $∆{\theta }_{i+1}$ and $∆{\phi }_{i+1}$ would be:

$$\Delta {\theta }_{i+1}=\left(i+1\right)\frac{{{\displaystyle \sum }}_{i=1}^{t}i\Delta {\theta }_i-{{\displaystyle \sum }}_{i=1}^t\Delta {\theta }_i}{{{\displaystyle \sum }}_{i=1}^t{i}^2-{{\displaystyle \sum }}_{i=1}^{t}i},$$

(16)

$$\Delta {\phi }_{i+1}=\left(i+1\right)\frac{{{\displaystyle \sum }}_{i=1}^{t}i\Delta {\phi }_i-{{\displaystyle \sum }}_{i=1}^t\Delta {\phi }_i}{{{\displaystyle \sum }}_{i=1}^t{i}^2-{{\displaystyle \sum }}_{i=1}^{t}i},$$

(17)

where $i=0,1,2,\cdots ,t.$

Since the purpose of mutation operation is to achieve population diversity and break through premature convergence, in BQGA, a quantum revolving gate is used to operate $\theta$ and $\phi$.

$$\theta =\frac{1}{t}{\displaystyle \sum }_{i=1}^t{\theta }_i,$$

(18)

$$\phi =\frac{1}{t}{\displaystyle \sum }_{i=1}^t{\phi }_i,$$

(19)

The quantum mutation operation seeks to change the state of the superposition of the qubit states, so that the original tendency to collapse to the state “1/0” becomes the tendency to collapse to the state “0/1”. At the same time, the variation of quantum chromosomes helps to increase the diversity of the population and helps to avoid premature convergence.

2.4. Selection of Fitness Function

The selection of the fitness function directly affects the convergence speed of GA and whether it can find the optimal solution. This is because the genetic algorithm does not use external information in the evolutionary search, and it searches with the adaptation of each individual of the population degree only based on the fitness function [37,38,39]. The complexity of the fitness function is the main component of the complexity of GA, and the design of the fitness function should be as simple as possible to minimize the time complexity of the calculation. By establishing a mapping relationship between the objective function of the optimization problem and the fitness of the individual, the optimization of the objective function of the optimization problem can be realized in the process of group evolution.

There are three gene chains for each chromosome, which correspond to three objective function values. The chromosome should be represented by the best gene chain. Considering the size of the obstacle region and the distance between the starting point and the target one, an adaptive individual initialization mechanism is proposed. By calculating the Euclidean distance between the starting point and the target one, the fitness function can be derived as

$$Fit\left(i\right)=sqrt{\left(B1\left(1\right)-B2\left(1\right)\right)}^2+{\left(B1\left(2\right)-B2\left(2\right)\right)}^2+{\left(B1\left(3\right)-B2\left(3\right)\right)}^2,$$

(20)

The chromosome with the smallest fitness value in the population is selected as the contemporary optimal chromosome, and the one with the smallest objective function value among its three gene chains is the contemporary optimal chain. $B_i(i=1,2,3)$ represents the position of each point, and the shortest distance or the fitness function is obtained according to the shortest distance formula of the three-dimensional graph.

The quality of the chromosomes in the iterative process needs to be measured in order to drive the chromosomes to keep approaching the best position in the whole region. The main consideration of the metric fitness in three-dimension path planning in intelligent construction is the shortest path. To make the planned paths shorter in time, a three-sample method is used for interpolation, and the path length of the scatter is obtained by calculating the three samples after differencing the interpolated values. The adaptation value formula is shown as (21).

$$Fitness={\displaystyle \sum }_{k=1}^{K}sqrt{\left(x_{k+1}-x_k\right)}^2+{\left(y_{k+1}-y_k\right)}^2+{\left(z_{k+1}-z_k\right)}^2,$$

(21)

where K represents the number of interpolations, and k represents the order of interpolation. The total path length is obtained by summing the distances of all path segments. The smaller the value is, the shorter the path is.

The inertial weight $\omega$ is an important parameter for the speed of chromosome memory predecessors. In the early stage of the algorithm, for a larger search range, larger inertia weights are needed to improve the performance of a large search range, while in the later stage a more refined search is needed. Therefore, a linear decreasing strategy is used to adjust the weights, and the inertia weights will vary linearly between the maximum and minimum values to balance the search capability. Also, to balance the range difference between the inertia weight values and the chromosome velocity, the path range coefficient A which prevents the divergence of the weight values, is introduced as follow.

$$\omega \left(x\right)=\mathrm{A}\ast {\omega }_{\max }\ast \left({\omega }_{\max }-{\omega }_{\min }\right)\left(\mathit{max}gen-x\right)/\mathit{max}gen,$$

(22)

where ${\omega }_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is the maximum inertia weight, ${\omega }_{\mathrm{m}\mathrm{i}\mathrm{n}}$ is the minimum inertia weight and maxgen is the maximum number of iterations.

2.5. Algorithm Steps

In the ideal algorithm, the object is considered as a point without dimensions. The building as a whole is simplified by the grid method [40,41] to obtain a grid of 21 × 21 of equal size, and each grid is assigned a value, and the size of the value in the grid represents the height. The following are the steps of BQGA.

Step 1—Population initialization, setting the population size popsize, the number of iterations maxgen, the corner step shiftstep, the variation probability $p_m$, the maximum inertia weight ${\omega }_{\max }$ and the minimum inertia weight ${\omega }_{\min }$;

Step 2—Three-stranded gene coding, encoding the chromosomal genes by expressions (1), (2), (3) and (4);

Step 3—Spatial transformations solving. Combine the specific optimization problem with expression (5) to perform the solution space transformation and coordinate mapping to the solution space of the optimization problem. Then the obtained solution space coordinates are fit with (14);

Step 4—Chromosome updating. Update the chromosomes by using the quantum rotation gate in expression (15) to obtain new populations;

Step 5—Chromosomal variation. Correction of the direction of chromosome updating by (18) and (19);

Step 6—Adaptation function for screening. The obtained chromosomes are used to calculate the fitness of individual chromosomes based on Equations (20) and (21), and the optimal chromosomes and optimal gene chains are also used as the historical optimal chromosomes and gene chains. If $Fit\left(i\right)<Fit(i-1)$, the contemporary optimal solution is updated. Otherwise, the previous solution is kept unchanged;

Step 7—Iterate. Retain the optimal solution of the algorithm. Determine whether the number of iterations reaches the set value. If yes, the iteration ends and stops, otherwise, go back to Step 3;

Step 8: Algorithm termination. When the iteration reaches the maximum number of evolutionary generations, the algorithm stops iterating.

3. Bloch Sphere Quantum Bee Colony Algorithm

3.1. Bloch Coordinate Coding of Nectar Source

Firstly, encode the nectar sources using Bloch coordinate encoding. The coding approach is similar to the quantum genetic algorithm. The coordinates of nectar source are determined by defining a point p for each pair of parameters $\theta$ and $\phi$, and any qubit corresponds to a point on the spherical surface. Finally, P_i which is the ith food source in the population, is obtained, and three feasible solutions in the corresponding space are calculated.

The original nectar source is coded with Bloch coordinates of qubits directly, and the ith individual R_i in the population is encoded as follows:

$$R_i=\left|\begin{array}{c}\cos {\phi }_{i1}\sin {\theta }_{i1}\\ \sin {\phi }_{i1}\sin {\theta }_{i1}\\ \cos {\theta }_{i1}\end{array}\right|\cdots \left|\begin{array}{c}\cos {\phi }_{ij}\sin {\theta }_{ij}\\ \sin {\phi }_{ij}\sin {\theta }_{ij}\\ \cos {\theta }_{ij}\end{array}\right|\cdots \left|\begin{array}{c}\cos {\phi }_{in}\sin {\theta }_{in}\\ \sin {\phi }_{in}\sin {\theta }_{in}\\ \cos {\theta }_{in}\end{array}\right|,$$

(23)

$$\left\{\begin{array}{c}{\phi }_{ij}=2\pi \times rand(0,1)\\ {\theta }_{ij}=2\pi \times rand(0,1)\end{array}\right.,$$

(24)

where 1 ≤ i ≤ m, 1 ≤ j ≤ n, m is the population size, and n is the spatial dimension.

Each food source R_i consists of three chains, each corresponding to a feasible solution x_ix, x_iy or x_iz in the original solution space.

$$\left\{\begin{array}{c}{x}_{ix}=(x_{i1}^{(1)},x_{i2}^{(1)},\dots ,x_{in}^{(1)})\\ x_{iy}=(x_{i1}^{(2)},x_{i2}^{(2)},\dots ,x_{in}^{(2)})\\ x_{iz}=(x_{i1}^{(3)},x_{i2}^{(3)},\dots ,x_{in}^{(3)})\end{array}\right.,$$

(25)

3.2. Solution Space Transformation and Food Sources Updating

Apply solution space transformation to the chromosomes encoded with Bloch coordinates, and perform an update operation on the quantum chromosomes. The search space for each dimension of the QABC algorithm is [−1,1]. In order to calculate the fit value of the artificial bee, the solution space needs to be transformed, and the corresponding transformation of the jth qubit of the ith food source R_i in the Bloch spherical coordinate system is

$$\left\{\begin{array}{c}{X}_{ij}^{\left(1\right)}=\frac{1}{2}\left[b_j\left(1+\cos {\phi }_{ij}\sin {\theta }_{ij}\right)+a_j\left(1-\cos {\phi }_{ij}\sin {\theta }_{ij}\right)\right]\\ X_{ij}^{\left(2\right)}=\frac{1}{2}\left[b_j\left(1+\sin {\phi }_{ij}\sin {\theta }_{ij}\right)+a_j\left(1-\sin {\phi }_{ij}\sin {\theta }_{ij}\right)\right]\\ X_{ij}^{\left(3\right)}=\frac{1}{2}\left[b_j\left(1+\cos {\theta }_{ij}\right)+a_j\left(1-\cos {\theta }_{ij}\right)\right]\end{array}\right.,$$

(26)

where $i=1,2,\cdots ,m\mathrm{a}\mathrm{n}\mathrm{d}j=1,2,\cdots n$.

In QABC, updating quantum chromosomes is usually finished by changing the quantum phase with revolving gates. Updating the location of the honey source essentially involves changing the angles between each Bloch coordinate.

The honey sources have the capacity for evolution, that is, they gradually move towards the optimal solution at the same time. Consider adjusting for the change in $\phi$ by the cosine of the difference between $\theta$ and ${\theta }_{gbest}$ and for the change in $\theta$ by the cosine of the difference between $\phi$ and ${\theta }_{gbest}$.

$$\left\{\begin{array}{c}{\phi }_{ij}={\phi }_{ij}+\cos \left({\theta }_{ij}-{\theta }_{gbest}\right)\ast \left({\phi }_{ij}-{\phi }_{gbest}\right)\\ {\theta }_{ij}={\theta }_{ij}+\cos \left({\phi }_{ij}-{\phi }_{gbest}\right)\ast \left({\theta }_{ij}-{\theta }_{gbest}\right)\end{array}\right.,$$

(27)

where ${\phi }_{ij}$ and ${\theta }_{ij}$ are the Bloch coordinate phase angles of the ith food source at the jth quantum position, and ${\phi }_{gbest}$ and ${\theta }_{gbest}$ are the globally optimal Bloch coordinate phase angles in each generation.

3.3. Multi-Robots Path Planning Based on QABC

A two-level planning method is adopted for multi-robots based on QABC: the first level is for each robot to plan its global trajectory with QABC, and the second level is to solve the trajectory conflict problem between multi-robots and the external circular collision method to detect other robots in the nearby environment.

3.3.1. External Circle Collision Detection Algorithm

In this paper, the priority method is used to deal with the collision strategy. The priorities of robots in the whole system are defined. When a path conflict occurs, the low-priority robot obeys the command of the high-priority robot and coordinates with the action of the high-priority robot to resolve the conflict. The robot operates on the grid using the action of the octagonal structure, and the motion step size is 1 or $\sqrt{2}$. The position of the robot at time t is (x_t, y_t, z_t). Then,

$$\left\{\begin{array}{c}{x}_t-x_{t-1}=0\\ \begin{array}{c}{y}_t-y_{t-1}=0\\ z_t-z_{t-1}=0\end{array}\end{array}\right. or\left\{\begin{array}{c}{x}_t-x_{t-1}=1\\ \begin{array}{c}{y}_t-y_{t-1}=1\\ z_t-z_{t-1}=1\end{array}\end{array}\right.,t\in \left[1,end\right],$$

(28)

3.3.2. Conflict Resolution Algorithm

If the priorities of the robots are the same, then the robot with the shortest expected initial path will avoid the robot with the longest expected initial path for optimal efficiency.

• Conflict type;

Conflict type I and the collision prediction are shown in Figure 2. Two robots travel in opposite directions on segment AB, and S₂ is moving along BA, while S₁ is moving along AB. S₁ is predicted to collide with S₂ at P point.

In order to avoid collision, S₂ passes in accordance with the established path, while S₁ defines the safety range around the collision course of the outer ring as the restricted area of S₁, according to the priority, and S₁ waits for S₂ to pass. The shadow area in the figure shows the superposition of the circular part with radius d.

2.

Conflict type II

When the paths of two robots engaged in circumferential collision walking intersect, a collision may occur. Suppose that S₁ moves along the line S₁P, and S₂ moves along the line S₂P; the path intersection is P. If S₁ moves along the planned path to point C and S₂ arrives at point D with the same speed, their direction of movement is d. When the distance between two robots DC is less than the safe distance, that is $0\le d\le a$, $0\le d\le b$, they are expected to collide. Conflict type I and the collision prediction are shown in Figure 3. The collision prediction diagram is shown in Figure 4.

To avoid a collision, S₂ with low priority actively avoids the robot S₁ and waits at a safe distance, while S₁ maintains its initial speed until it leaves the outer circle of S₂. Finally, S₂ continues along its original path and speed.

3.

Conflict type III

Taking the position of the parked robot as the center of the circle, the circle corresponding to the radius and safety distance is divided into small areas, and the local route is designed according to the improved algorithm. To avoid collision, the robot path needs to change, as shown in Figure 5.

4. Analysis of Evacuation Path Planning Model Experiment

4.1. Basic Assumptions

The following assumptions and parameter settings need to be made for the set-up algorithm before establishing the mathematical model of the evacuation path optimization problem:

(a)

The initial node is the accident site, the endpoint is the safe area, and all the nodes between them are evacuation points;

(b)

Each evacuation point can be passed only once;

(c)

When starting the operation, the route must be executed to completion without interruption;

(d)

During the execution of the task, the speed change is uniform;

(e)

Human factors and obstacle changes are ignored when the accident occurs.

4.2. Raster Data Capture

Commonly used methods for modeling the environment include the grid map method [42], the free space method [43] and the geometric information method [44]. In this paper, the grid method is chosen to establish the three-dimensional path planning space, which is an approach of map modeling to fill in the obstacles in the environment, i.e., environment optimization. The planning space is decomposed into a number of network cells with binary information consisting of a matrix of 0s and 1s. 0 represents a free form, indicating that there are no obstacles and there is a free passage, colored white. 1 represents an obstacle grid, indicating that there are obstacles that need to be moved around, colored black [45]. The workspace is decomposed into cells and then an algorithm is used to search for safe paths in the cells. The method is simple to implement and easy to extend to three-dimensional environments. We use a plane to uniformly divide the three-dimensional space, from which the discrete points required for three-dimensional path planning are extracted. Assuming that each grid represents a sparse point, and that each grid has the same size, the size length set to unit 1.

Firstly, the eight adjacent grids in the square grid are anlyzed from a steering perspective, with the horizontal positive direction as the 0° reference, 45°, 90°, 135° clockwise, 45°, 90°, 135° counterclockwise, and 180° backwards. Next, the OABC-O₁A₁B₁C₁ three-dimensional space is constructed with O as the vertex, shown in Figure 6.

The three-dimensional space is divided uniformly with a plane, from which the discrete points required for three-dimensional path planning are extracted. The space OABC-O₁A₁B₁C₁ is first divided into n equal parts along the OC side to obtain n + 1 planes ${\Omega }_i(i=1,2,\cdots n)$, and then the n + 1 planes are divided into m equal parts along the OA side and l equal parts along OO’ to obtain each intersection point in the space. The planes are divided as shown in Figure 7.

Through the above steps, the entire planning space OABC-O₁A₁B₁C₁ is decomposed into a collection of spatially discrete points, which form the paths searched by the BQGA.

The schematic diagrams of the simulated obstacle avoidance movement in different raster maps are shown in Figure 8, and the adjacent 8 rasters are used as optional evacuation locations under different real-life conditions. The specific evacuation locations depend on the update direction and the size of the quantum revolving door.

The data, such as the length, width and height of the building, are simulated, and the point data obtained are converted into a grid of 21 × 21. Next, each grid to be interpolated is assigned the value of the building heights. Its coordinates are set as $\left(x_i,y_j,z_k\right)$ by labeling each grid in the raster layer. The original path planning space is transformed into a set of raster numbers, and one only needs to select this set of data points when path planning is carried out. In the rasterized three-dimensional terrain, only 19 raster points need to be selected from the accident occurrence point to the safety zone to form an evacuation path in turn.

4.3. Experimental Analysis of Single-Robot Path Planning

In order to verify the effectiveness of the Bloch Spherical Quantum Genetic Algorithm, the model is solved by simulation. The simulations of BQGA, ACA and GA were conducted for comparison tests, respectively. In order to reflect the fairness of the comparison results, the same population size and evolutionary generation were used for three algorithms. The parameters were set as follows: evolutionary generation maxgen = 100, number of populations popsize = 100, number of quantum bits n = 2, and 19 evacuation nodes. Then the performances of the three algorithms are verified in Figure 9, Figure 10 and Figure 11.

4.3.1. Results Analysis

The visualization of the spatially optimal route of the evacuation path three-dimensional raster model is given in Figure 11. The best path route based on the ACA search took 1.362073 s to run, the best path route based on the GA search took 1.304934 s to run, and the best path route based on the BQGA search took 1.256061 s.

In Figure 11, the trends of the best individual fitnesses under different algorithms are represented. Figure 11 shows the trend of the best individual fitness for the BQGA, from the initial 128 to 118, with a difference of 10, the trend of the best individual fitness for the ACA, from the initial 126 to 115, with a difference of 11, and the trend of the best individual fitness for the GA, from the initial 128 to 110, with a difference of 18.

For ACA, it is easy to fall into local optimum prematurely, and the computational search time is too long because of its complexity. It is easy to encounter a stagnation phenomenon, that is, after the search is carried out to a certain degree, it cannot search the solution space further, which is not conducive to discovering better solutions. ACA’s optimization efficiency is low.

For GA, the encoding of ordinary algorithms does not fully represent the constraints of the optimization problem, and therefore it requires the consideration of thresholds for infeasible solutions, which in turn increases the workload and solution time, making the iteration time larger.

BQGA avoids the random characteristics brought by generating binary codes with measuring quantum bits, and expands the planar unit circle description of quantum bits to Bloch spherical description, so that the quantum behavior can be fully reflected. Then, the frequent binary number decoding process can be avoided, and the time will be reduced. Thirdly, BQGA expands the number of global optimal solutions and improves the probability of obtaining global optimal solutions. Finally, the number of global optimal solutions can be expanded and the probability of obtaining global optimal solutions will be improved.

4.3.2. Path Instance Analysis

The three algorithms were run 30 times, respectively, and the evaluation indicators were recorded. Three groups of different populations with popsize = 100, popsize = 150, and popsize = 200 were set. The comparisons of the optimization results of the best individual fitness functions of the three algorithms are listed in

Table 1. Comparison of ACA, GA and BQGA under evacuation conditions of Maxgen = 100, Popsize = 100.

Algorithm	Best Result	Worst Result	Average Result	Time/s
ACA	126	110	118	1.2914
GA	127	113	120	1.2784
BQGA	128	118	123	1.2476

,

Table 2. Comparison of ACA, GA and BQGA under evacuation conditions of Maxgen = 100, Popsize = 150.

Algorithm	Best Result	Worst Result	Average Result	Time/s
ACA	127	110	118.5	1.8490
GA	126	112	119	1.8043
BQGA	128	118	123	1.7658

and

Table 3. Comparison of ACA, GA and BQGA under evacuation conditions of Maxgen = 100, Popsize = 200.

Algorithm	Best Result	Worst Result	Average Result	Time/s
ACA	126	112	119	2.3565
GA	125	111	118	2.3367
BQGA	128	118	123	2.3102

.

For the continuous optimization problem, in BQGA, the two parameters $\theta$ and $\phi$ of the quantum bit can be adjusted simultaneously by using the current quantum bit to rotate around a certain rotation axis toward the target quantum bit, and the corresponding Bloch coordinates can be directly obtained by the projection measurement of the quantum bit, which achieves the best matching of the amount of adjustment of the two parameters in the quantum bit adjustment. Obviously, this best-matched rotation has higher optimization efficiency. Therefore, the optimization efficiency of BQGA is higher than that of ACA and GA, i.e., the shorter the time, the larger the average result value, which indicates its effectiveness and efficiency. The optimization efficiency of BQGA is improved by approximately 3.39% and 2.41% compared to the other two algorithms, respectively.

4.3.3. Influence Analysis of BQGA and ACA, GA Stability Results

With the expansion of the problem scale, the size of the problem scale has a strong influence on the algorithm’s running time, and the overall trend of the running time of the algorithms increases from the analysis of the path instance. So the algorithms should be evaluated according to the size of the actual problem. Therefore, the results are further explored for each of the two algorithms in the case of increasing problem size, based on the fitting, using the control variables method. The number of location points and the running time are roughly linear in BQGA, while in ACA and GA, the number of location points and the running time tend to show a more quadratic correlation. When the number of location points is large, the running time of ACA and GA is obviously longer than that of BQGA. The relationship between the number of iterations and the degree of adaptation can be plotted according to the data obtained from the two algorithms, as shown in Figure 12.

4.4. Experimental Analysis of Multi-Robots Path Planning

In order to verify the effectiveness of the QABC, the model is solved by simulation. The simulations of QABC, ACA and ABC were conducted for comparison tests, respectively. The parameters were set as follows: population size N = 200, limiting frequency limit = 50, maximum cycle number maxcycle = 1000, number of quantum bits n = 2 and 19 evacuation nodes.

4.4.1. Collision Detection

As shown in Figure 13a, each robot moves towards the target point from the initial position, and robots A and C detect each other in their own peripheral circles. In order to prevent collision, the method shown in collision type II is adopted. Meanwhile, the robots with a lower priority will actively avoid the one with a higher one.

As shown in Figure 13b, robots A and B detect the existence of each other by using the external circle method. In this case, collision type III is required for conflict resolution and avoidance, so that the robots can pass smoothly.

As shown in Figure 13c, robots A and B detect each other using external circles, which belongs to collision type I. The corresponding conflict resolution method needs to be used to let the one with higher priority pass first, and the one with lower priority can pass only when the external circle is larger than the security zone.

4.4.2. Results Analysis

The results for the three approaches are shown in

Table 4. Comparison of ACA, ABA and QABC.

Algorithm	Robot	Estimate Path Length	Actual Path Length	Time/s
ACA	S1	11.983	11.983	1.291
	S2	14.678	14.678	1.339
ABC	S1	11.346	12.237	1.343
	S2	12.327	12.438	1.433
QABC	S1	12.628	12.682	1.153
	S2	15.729	15.720	1.127

. It can be seen from the data in the table that multiple robots S₁ and S₂, based on the quantized artificial bee colony algorithm, increase the path length and shorten the running time by using priority-based path planning compared with those in S₁ and S₂ in QABC. After the introduction of the circular collision detection operator, the safety and directivity of the second layer’s local path planning in the two-layer programming method are enhanced, and the ability to search the optimal solution using QABC is improved. Meanwhile, the application saves time, reduces work cost, and effectively improves the work efficiency of multi-robots. The optimization efficiency of QABC is improved by approximately 13.31% and 17.87% compared to the other two algorithms, respectively.

4.4.3. Influence Analysis of QABC, ACA and ABC Stability Results

According to the data obtained by the three algorithms, the relationship between iteration times and fitness can be drawn, as shown in Figure 14. The use of QABC reduces the possibility of collision between robots, and improves the safety of robots. When the number of location points is large, the running times of ABC and ACA are obviously longer than that of QABC. Comparing the stability of the three algorithms, it is found that QABC is more stable.

5. Conclusions

In this paper, the Bloch Spherical Quantum Genetic Algorithm model fused with the least-squares principle for a single robot and the Bloch Spherical Quantum Bee Colony Algorithm for multi-robots are proposed to seek the optimal path. From a progressive point of view, consider the least-squares method and quantum optimization; the discrete grid division approach deals with the unpredictable evacuation problem caused by emergencies. In the case of uncertain building conditions, a fusion least-squares method is established for studying the three-dimensional path planning problem. The principle of the quantum model and quantum optimization algorithm based on a Bloch sphere is designed. On the basis of verifying the validity of the algorithm, the algorithm comparison is carried out, and the running time and fitness of the algorithm are compared, as well as the influence of stability.

Experiments show that the rasterization of building floors is more convenient for finding the shortest safe path. Compared with ACA, GA and ABC, the methods in this paper can effectively deal with the problems of slow convergence and long execution time caused by the traditional algorithms. The solution to these problems can enable humans to quickly evacuate from dangerous areas when an emergency occurs, thereby improving the safety factor for human activities in the building.

Future research will focus on improved qubit encoding, which can make the food source more evenly traversable throughout the solution space to improve the search efficiency of the algorithm.