# Research on Application of Improved Quantum Optimization Algorithm in Path Planning
## 4 Analysis of Evacuation Path Planning Model Experiment
### 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 analyzed from a steering perspective, with the horizontal positive direction as the 0\({}^{\circ}\) reference, 45\({}^{\circ}\), 90\({}^{\circ}\), 135\({}^{\circ}\) clockwise, 45\({}^{\circ}\), 90\({}^{\circ}\), 135\({}^{\circ}\) counterclockwise, and 180\({}^{\circ}\) backwards. Next, the OABC-O\({}_{1}\)A\({}_{1}\)B\({}_{1}\)C\({}_{1}\) 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\({}_{1}\)A\({}_{1}\)B\({}_{1}\)C\({}_{1}\) 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.  
Figure 6: (a) Grid plan model; (b) three-dimensional space occupation; (c) three-dimensional model space.  
Through the above steps, the entire planning space OABC-O\({}_{1}\)A\({}_{1}\)B\({}_{1}\)C\({}_{1}\) 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 \(\times\) 21. Next, each grid to be interpolated is assigned the value of the building heights. Its coordinates are set as \(\left(x_{i},y_{i},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.