Improved Hybrid A* Algorithm Based on Lemming Optimization for Path Planning of Autonomous Vehicles
Path planning for autonomous vehicles is a core component of intelligent transportation systems, playing a key role in ensuring driving safety, improving driving efficiency, and optimizing the user experience. To address the challenges of safety, smoothness, and search efficiency in path planning fo...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-07-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/14/7734 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849714642158354432 |
|---|---|
| author | Yong Chen Yuan Liu Wei Xu |
| author_facet | Yong Chen Yuan Liu Wei Xu |
| author_sort | Yong Chen |
| collection | DOAJ |
| description | Path planning for autonomous vehicles is a core component of intelligent transportation systems, playing a key role in ensuring driving safety, improving driving efficiency, and optimizing the user experience. To address the challenges of safety, smoothness, and search efficiency in path planning for autonomous vehicles, this study proposes an improved hybrid A* algorithm based on the lemming optimization algorithm (LOA). Firstly, this study introduces a penalized graph search method, improves the distance heuristic function, and incorporates the Reeds–Shepp algorithm in order to overcome the insufficient safety and smoothness in path planning originating from the hybrid A* algorithm. The penalized graph search method guides the search away from dangerous areas through penalty terms in the cost function. Secondly, the distance heuristic function improves the distance function to reflect the actual distance, which makes the search target clearer and reduces the computational overhead. Finally, the Reeds–Shepp algorithm generates a path that meets the minimum turning radius requirement. By prioritizing paths with fewer reversals during movement, it effectively reduces the number of unnecessary reversals, thereby optimizing the quality of the path. Additionally, the lemming optimization algorithm (LOA) is combined with a two-layer nested optimization framework to dynamically adjust the key parameters of the hybrid A* algorithm (minimum turning radius, step length, and angle change penalty coefficient). Leveraging the LOA’s global search capabilities avoids local optima in the hybrid A* algorithm. By combining the improved hybrid A* algorithm with kinematic constraints within a local range, smooth paths that align with the actual movement capabilities are generated, ultimately enhancing the path search capabilities of the hybrid A* algorithm. Finally, simulation experiments are conducted in two scenarios to validate the algorithm’s feasibility. The simulation results demonstrate that the proposed method can efficiently avoid obstacles, and its performance is better than that of the traditional hybrid A* algorithm in terms of the computational time and average path length. In a simple scenario, the search time is shortened by 33.2% and the path length is reduced by 11.1%; at the same time, in a complex scenario, the search time is shortened by 23.5% and the path length is reduced by 13.6%. |
| format | Article |
| id | doaj-art-54a39031ae3e4581842870db8042e310 |
| institution | DOAJ |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-54a39031ae3e4581842870db8042e3102025-08-20T03:13:39ZengMDPI AGApplied Sciences2076-34172025-07-011514773410.3390/app15147734Improved Hybrid A* Algorithm Based on Lemming Optimization for Path Planning of Autonomous VehiclesYong Chen0Yuan Liu1Wei Xu2College of Mechanical and Electronic Engineering, Beijing Information Science and Technology University, No. 12 Xiaoying-East Road, Haidian District, Beijing 100192, ChinaCollege of Mechanical and Electronic Engineering, Beijing Information Science and Technology University, No. 12 Xiaoying-East Road, Haidian District, Beijing 100192, ChinaCollege of Mechanical and Electronic Engineering, Beijing Information Science and Technology University, No. 12 Xiaoying-East Road, Haidian District, Beijing 100192, ChinaPath planning for autonomous vehicles is a core component of intelligent transportation systems, playing a key role in ensuring driving safety, improving driving efficiency, and optimizing the user experience. To address the challenges of safety, smoothness, and search efficiency in path planning for autonomous vehicles, this study proposes an improved hybrid A* algorithm based on the lemming optimization algorithm (LOA). Firstly, this study introduces a penalized graph search method, improves the distance heuristic function, and incorporates the Reeds–Shepp algorithm in order to overcome the insufficient safety and smoothness in path planning originating from the hybrid A* algorithm. The penalized graph search method guides the search away from dangerous areas through penalty terms in the cost function. Secondly, the distance heuristic function improves the distance function to reflect the actual distance, which makes the search target clearer and reduces the computational overhead. Finally, the Reeds–Shepp algorithm generates a path that meets the minimum turning radius requirement. By prioritizing paths with fewer reversals during movement, it effectively reduces the number of unnecessary reversals, thereby optimizing the quality of the path. Additionally, the lemming optimization algorithm (LOA) is combined with a two-layer nested optimization framework to dynamically adjust the key parameters of the hybrid A* algorithm (minimum turning radius, step length, and angle change penalty coefficient). Leveraging the LOA’s global search capabilities avoids local optima in the hybrid A* algorithm. By combining the improved hybrid A* algorithm with kinematic constraints within a local range, smooth paths that align with the actual movement capabilities are generated, ultimately enhancing the path search capabilities of the hybrid A* algorithm. Finally, simulation experiments are conducted in two scenarios to validate the algorithm’s feasibility. The simulation results demonstrate that the proposed method can efficiently avoid obstacles, and its performance is better than that of the traditional hybrid A* algorithm in terms of the computational time and average path length. In a simple scenario, the search time is shortened by 33.2% and the path length is reduced by 11.1%; at the same time, in a complex scenario, the search time is shortened by 23.5% and the path length is reduced by 13.6%.https://www.mdpi.com/2076-3417/15/14/7734autonomous vehiclespath planninggraph search methodshybrid A* algorithmglobal optimization |
| spellingShingle | Yong Chen Yuan Liu Wei Xu Improved Hybrid A* Algorithm Based on Lemming Optimization for Path Planning of Autonomous Vehicles Applied Sciences autonomous vehicles path planning graph search methods hybrid A* algorithm global optimization |
| title | Improved Hybrid A* Algorithm Based on Lemming Optimization for Path Planning of Autonomous Vehicles |
| title_full | Improved Hybrid A* Algorithm Based on Lemming Optimization for Path Planning of Autonomous Vehicles |
| title_fullStr | Improved Hybrid A* Algorithm Based on Lemming Optimization for Path Planning of Autonomous Vehicles |
| title_full_unstemmed | Improved Hybrid A* Algorithm Based on Lemming Optimization for Path Planning of Autonomous Vehicles |
| title_short | Improved Hybrid A* Algorithm Based on Lemming Optimization for Path Planning of Autonomous Vehicles |
| title_sort | improved hybrid a algorithm based on lemming optimization for path planning of autonomous vehicles |
| topic | autonomous vehicles path planning graph search methods hybrid A* algorithm global optimization |
| url | https://www.mdpi.com/2076-3417/15/14/7734 |
| work_keys_str_mv | AT yongchen improvedhybridaalgorithmbasedonlemmingoptimizationforpathplanningofautonomousvehicles AT yuanliu improvedhybridaalgorithmbasedonlemmingoptimizationforpathplanningofautonomousvehicles AT weixu improvedhybridaalgorithmbasedonlemmingoptimizationforpathplanningofautonomousvehicles |