# Improved Hybrid A* Algorithm Based on Lemming Optimization for Path Planning of Autonomous Vehicles
## 1 Introduction  
Autonomous vehicles are equipped with advanced sensors, controllers, and actuators to perceive complex environments, make intelligent decisions, and execute motion control, ultimately achieving human-like driving performance [1, 2]. Path planning, as an indispensable component of autonomous driving systems [3], relies on environmental data from perception layers and transmits planned trajectories to control layers for execution [4]. A fast and robust planning layer directly impacts the performance of autonomous vehicles. In recent years, path planning algorithms have rapidly evolved and can be broadly categorized into five types [5]. 1. Graph Search-Based Algorithms  
The principle of grid-based search algorithms involves discretizing the entire map by dividing it into a number of grids or cells. The vehicle then selects its start and end points based on its needs and plans a path through these cells according to the cost, with the path generated via connections between the cells. This category of algorithms primarily includes the Dijkstra and A* algorithms, among others. Dijkstra [6] is a single-source shortest-path optimal path planning algorithm. In Dijkstra, the state space is typically discretized into grid cells before searching [7]. [PERSON] et al. [8] proposed the Reverse Labeling Dijkstra Algorithm (RLDA) to solve this problem, theoretically proving its correctness and demonstrating its low polynomial time complexity. [PERSON] et al. [9] introduced an alternative implementation of the A* algorithm. By incorporating grid obstacle rates into the evaluation function and enhancing the heuristic function, this method improves the search efficiency and path smoothness. [PERSON] [10] introduced an improved A* algorithm that incorporates the salp swarm algorithm (SSA) for heuristic function optimization and proposed improved B-spline interpolation for path smoothing. Although grid-based search algorithms are easy to implement, they face several challenges during the search process: high computational complexity, limited path accuracy, difficulty in adapting to dynamic environments, an inability to directly account for vehicle kinematic constraints, and heightened sensitivity to perception errors. 2. Sampling-Based Algorithms  
The principle of sampling-based path planning algorithms involves generating a set of sample points in the feasible space through random or strategic sampling and then constructing connections among these points to form a feasible path from the start to the goal. Representative algorithms in this category include rapidly exploring random trees (RRT) and probabilistic roadmaps (PRM). [PERSON] [11] proposed combining an improved artificial potential field method with the RRT algorithm for path planning. This hybrid approach utilizes RRT's obstacle avoidance capability to address path oscillation issues. [PERSON] et al. [12] modified the sampling strategy of the conventional PRM by implementing uniform sampling in obstacle-dense regions while increasing the sampling points in narrow passages, thereby improving the traversal success rates in constrained spaces while achieving shorter path lengths and reduced traversal times. While sampling-based algorithms demonstrate superior computational efficiency in high-dimensional spaces, their generated paths often lack smoothness. Particularly in dense obstacle environments, they exhibit slower convergence rates and tend to produce suboptimal solutions. 3. Interpolation-Based Algorithms  
Interpolation-based planning algorithms [13] operate by generating smooth intermediate waypoints between the start and goal points; then, mathematical interpolation methods are applied to construct constrained smooth trajectories, which ensures feasibilityand continuity. The interpolation-based approaches include polynomial interpolation, spline interpolation, Bezier curve interpolation, and curvature-continuous interpolation.