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.

Keywords

• Bloch sphere
• path planning
• Quantum Optimization Algorithm
• quantum genetic algorithm
• quantum bee colony algorithm