Vehicle Path Planning Based on Gradient Statistical Mutation Quantum Genetic Algorithm

Hui Li, Huiping Qin, Zi’ao Han, Kai LüInternational Journal of Advanced Computer Science and Applications 2023 · DOI

Abstract

In the field of vehicle path planning, traditional intelligent optimization algorithms have the disadvantages of slow convergence, poor stability and a tendency to fall into local extremes. Therefore, a gradient statistical mutation quantum genetic algorithm (GSM-QGA) is proposed. Based on the dynamic rotation angle adjustment by the chromosome fitness value, the quantum rotation gate adjustment strategy is improved by introducing the idea of gradient descent. According to the statistical properties of chromosomal change trends, the gradient-based mutation operator is designed to realize the mutation operation. The shortest path is used as the metric to build the vehicle path planning model, and the effectiveness of the modified algorithm in vehicle path planning is demonstrated by simulation experiments. Compared with other optimization algorithms, the path length planned by the improved algorithm is shorter and the search stability is better. The algorithm can be effectively controlled to fall into local optimums.

Introduction

Path planning serves as the "brain" of autonomous driving, tasked with identifying the shortest, collision-free route between two points. Mathematically, this is an NP-hard problem; as environmental complexity increases, the computational resources required to find an optimal path grow exponentially. Traditional heuristic methods, such as Genetic Algorithms (GA), often struggle with slow convergence and the tendency to get trapped in local optima—finding a "good enough" path rather than the global minimum. While Quantum Genetic Algorithms (QGA) introduced qubits to represent multiple states simultaneously, they still face challenges regarding search stability and premature convergence.

The GSM-QGA Methodology

To address these limitations, the Gradient Statistical Mutation Quantum Genetic Algorithm (GSM-QGA) introduces two primary innovations:

  1. Adaptive Quantum Rotation Gate (Gradient-Based): Standard QGAs typically use fixed lookup tables for rotation gates to update qubit probabilities. GSM-QGA employs a gradient descent approach based on chromosome fitness. The algorithm dynamically adjusts the rotation angle: increasing it when far from the optimum to accelerate the search, and decreasing it as it nears the target for fine-tuned convergence.
  2. Gradient Statistical Mutation Operator: Unlike standard random bit-flipping, which can disrupt high-quality solutions, the GSM-QGA utilizes a mutation operator informed by the statistical properties of previous generations. By analyzing improvement trends and applying a Gaussian mixture distribution, the algorithm can "jump out" of local traps with greater precision.
Flowchart of the GSM-QGA algorithm illustrating the iterative process from initialization to optimal output.

Experimental Results and Discussion

The researchers evaluated GSM-QGA in a simulated $20 \times 20$ grid environment representing an industrial park. The task was to navigate from (1, 1) to (20, 20) while avoiding obstacles. The algorithm was benchmarked against standard GA, basic QGA, and N-QGA (QGA with a standard NOT-gate mutation).

Simulation results showing the paths planned by GSM-QGA across five independent data runs, demonstrating high consistency and efficiency.

Key performance metrics from the simulation include:

  • Path Efficiency: GSM-QGA achieved an average path length of 1.566 km, a 10.26% improvement over the 1.745 km average of standard GA.
  • Convergence Speed: The algorithm converged in an average of 15.8 iterations, representing a 50.63% increase in speed compared to traditional GA.
  • Search Stability: The variance between the best and worst paths was only 0.0586 km, indicating high reliability across multiple runs.

Conclusion

The GSM-QGA demonstrates significant improvements in path planning efficiency and stability by integrating gradient descent and statistical mutation into the quantum genetic framework. While highly effective in static grid environments, future research will focus on dynamic obstacle avoidance, incorporating vehicle kinematics (such as turning radii), and scaling the algorithm for higher-dimensional search spaces.

Summary updated

Abstract

In the field of vehicle path planning, traditional intelligent optimization algorithms have the disadvantages of slow convergence, poor stability and a tendency to fall into local extremes. Therefore, a gradient statistical mutation quantum genetic algorithm (GSM-QGA) is proposed. Based on the dynamic rotation angle adjustment by the chromosome fitness value, the quantum rotation gate adjustment strategy is improved by introducing the idea of gradient descent. According to the statistical properties of chromosomal change trends, the gradient-based mutation operator is designed to realize the mutation operation. The shortest path is used as the metric to build the vehicle path planning model, and the effectiveness of the modified algorithm in vehicle path planning is demonstrated by simulation experiments. Compared with other optimization algorithms, the path length planned by the improved algorithm is shorter and the search stability is better. The algorithm can be effectively controlled to fall into local optimums.
BibTeX
@article{li2023vehicle,
  author = {Hui Li and Huiping Qin and Zi’ao Han and Kai Lü},
  title = {{Vehicle Path Planning Based on Gradient Statistical Mutation Quantum Genetic Algorithm}},
  journal = {International Journal of Advanced Computer Science and Applications},
  year = {2023},
  doi = {10.14569/ijacsa.2023.0140664},
}
Figure