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:
- 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.
- 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.
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).
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