1. Introduction
With the rapid development of intelligence and electrification in the automobile industry, autonomous driving technology plays a crucial role in modern traffic systems [
1]. Path planning, as an important task for autonomous driving [
2,
3,
4], can give the target vehicle priori information on the traffic network, contributing to driving safety and control robustness. However, the quality of the planning trajectory and the complexity of iterative calculation cannot be balanced well in practice when the algorithms face a complex traffic network environment [
5,
6,
7]. Therefore, it is crucial to optimize and develop advanced path planning algorithms to improve the efficiency of path generation in various transportation network environments.
In the field of autonomous driving, particularly in robotic and UAV path planning, neural network technologies like cellular neural networks and global brainstorming have been widely applied [
8]. For instance, in reference [
9], by drawing an analogy between path planning and neural dynamics and propagating through the state space using neural dynamics, real-time collision-free planning was achieved. Its advantage lies in the lack of prerequisite information while treating target activity as an energy source, demonstrating parameter independence and physical validity. However, this method relies on complex neural dynamic models, requiring substantial computational resources to process data in real time. Reference [
10] proposed a heat conduction method that establishes a transient heat conduction model and a cellular neural network to simulate heat conduction, generating the globally optimal path. Its strength lies in the natural avoidance of obstacles through heat conduction simulation. However, its transient model may be insufficiently responsive when dealing with dynamic environments. In the literature [
11], an improved Hopfield-type neural network model is used to represent the local connectivity of the neural system as harmonic functions, propagating target activity via physical heat conduction. The advantage is that it allows for real-time obstacle avoidance without prior knowledge of dynamic environments. However, significant experimentation is needed to optimize model parameters. In reference [
12], the global-best brainstorming optimization algorithm (GBSO) based on crossover recombination was designed to optimize paths with continuous curvature. This algorithm is particularly suitable for solving complex optimization problems with multiple constraints, but its efficiency is limited by the complexity of the constraints.
Automatic driving path planning algorithms can be categorized into two categories according to the generating principle of vehicle trajectory, including sampling-based and search-based trajectory planning algorithms [
13,
14]. To explore the principles and usage characteristics of different types of planning algorithms, this study conducted analyses on selected representative algorithms corresponding to the aforementioned two distinct planning principles.
Table 1 shows a series of algorithms related to intelligent vehicle routing planning and their application scenarios.
In terms of the sampling-based algorithms [
15,
16,
17], such as rapidly-exploring random trees (RRT) and probabilistic roadmap (PRM), always sample the vehicle state in the test space to find a feasible trajectory connecting the starting node and the goal node. RRT uses random sampling and the extension of the tree structure to find feasible paths in complex environments. It efficiently explores high-dimensional spaces and is suitable for real-time applications. However, it cannot find the globally optimal path due to its probabilistic nature as well as the sensitivity to parameter settings [
18,
19]. PRM constructs a road network by randomly sampling points in an obstacle environment to find the optimal path [
20,
21,
22,
23]. Nevertheless, constructing the network leads to burdensome computational intensity [
24]. Random sampling cannot guarantee that the sample points cover the optimal path, posing a challenge to the efficiency of path generation in planning [
25,
26]. In conclusion, sampling-based algorithms can avoid local minima in non-convex spaces, and their advantage lies in their ability to handle planning problems in high-dimensional spaces and complex environments, demonstrating good adaptability. Despite the potential optimizations such as introducing heuristic functions, increasing sampling density, and improving connection strategies to address the computational challenges caused by the excessive sampling requirements of the sampling-based algorithm. In complex environments, the quality of paths planned by sampling-based algorithms is still influenced by the randomness in the distribution of sampling points.
In contrast to sampling-based approaches, search-based planning algorithms have the advantage of generating high-quality paths while reducing computational time and space complexity, such as Dijkstra’s algorithm and A* algorithm [
27]. Dijkstra’s algorithm iteratively selects the vertex closest to the source point and updates the distances of its adjacent vertices using a priority queue [
28]. The advantage of Dijkstra’s algorithm lies in its efficient ability to find the shortest paths from a single source point to all other vertices in the graph, provided that the edge weights in the graph are non-negative. However, a significant limitation of Dijkstra’s algorithm is its inability to handle graphs with negative edge weights, as the algorithm assumes that the shortest path is gradually constructed through vertices with the smallest known distances. The A* algorithm inherits the advantages of the Dijkstra algorithm, while improving search efficiency by introducing a heuristic function [
29]. Nevertheless, it has some limitations in terms of heuristic function design and local optimal solutions, especially in the complex traffic environments encountered by unmanned vehicles [
30]. Graph-based algorithms commonly face issues such as computational complexity and local optimum. The global nature of the search algorithm has led to challenges with insufficient computing resources and issues related to finding local optimal solutions [
31]. Therefore, it is essential to address these issues through optimization techniques such as introducing parallel computing, refining heuristic functions, and enhancing algorithmic strategies. These measures aim to improve algorithm performance and mitigate the problem of local optima. Therefore, many experts and scholars, both domestically and internationally, mainly focus on improving the original algorithms and algorithm fusion orientation as the primary research directions in path planning [
32,
33,
34,
35].
An ideal method for autonomous driving path planning should be based on obstacle perception information, quickly and stably determining safe and reasonable paths, while considering their applicability to subsequent trajectory optimization and speed control [
36]. The A* algorithm, as a classical heuristic search algorithm, has achieved significant success in the field of path planning [
37]. However, when dealing with large-scale road networks, the traditional A* algorithm still faces challenges [
38,
39,
40]. Researchers have proposed various methods to improve the global path quality in optimized path planning, addressing the shortcomings of a simple heuristic search, redundant control nodes, and low safety. Specifically, weighted heuristic functions, safety distance matrices, and key point selection strategies have been introduced into the traditional A* algorithm and integrated into the algorithm. In terms of the weighted heuristic function, a weighted heuristic function to enhance the computational speed of the A* algorithm is proposed in [
41]. They retained only the turning points of the path and applied fifth-degree polynomial smoothing to effectively address the issue of path roughness. The method offers advantages such as improved computational speed, enhanced memory efficiency, and smoother paths. Nevertheless, due to the simplification of the search space, it cannot always yield the shortest path. Furthermore, its sensitivity to the initial heuristic function could lead to suboptimal solutions. In reference [
42], the safety distance matrix was introduced into the A* algorithm, and the redundant nodes were removed from the path using a simplified method of separate terms. They also used arc transition at turning points to improve the safety and smoothness of the path. The advantages of this method include safer, smoother paths and higher computational efficiency. However, a fixed safety distance may not be suitable for complex environments or dynamic situations, and the removal of some nodes may lead to suboptimal paths. In addition, a key point selection strategy is proposed in the literature [
43], which uses forced point-guided search to reduce the calculation of irrelevant points, deletes redundant points through secondary programming, and smooths dynamic tangent circles around the watershed. The advantages of this method include reduced computational time, better path smoothing, and further removal of redundant points. However, the processed path may be too close to obstacles, which is not safe, and it may also generate suboptimal paths due to the removal of some nodes.
In fact, in order to be more effectively applied to autonomous driving path planning, the improvement of the quality of traditional A* trajectories mainly faces three challenging problems, including the following:
- (1)
More absolute obstacle avoidance: In the face of the oblique arrangement and sparse occurrence of obstacles, the global path planned by the traditional A* algorithm will have the wrong path through the obstacles, which is a key problem affecting the feasibility of the planned path.
- (2)
Trajectory safety: The path nodes based on raster maps are often represented in the center of the grid, the distance between the nodes and the obstacles cannot be adjusted, and safety problems are caused by ignoring the safety distance constraint in the generated path.
- (3)
Concise control: The paths generated by traditional algorithms often have the problem of redundancy in control points, which leads to an unnecessary complexity of subsequent local optimization and control.
To optimize the A* path planning algorithm, some improvements mainly focus on reducing the number of traversed nodes, minimizing the total turning angle, incorporating safety distance, and shortening the path distance. In this context, an optimization strategy for A* path planning algorithm is proposed in this paper, aiming at getting the shortest global path based on reducing the number of traversed nodes and incorporating safety distance. To be specific, firstly, an optimized cost function based on the introduction of an obstacle raster coefficient and turn penalty function is introduced to enhance the adaptability and directionality of the search path to the map and minimize the total turning angle. Secondly, in order to solve the problem that the trajectory will pass through sparse obstacles, an efficient search strategy is designed and optimized to reduce the search space and computational complexity. Finally, the safety distance is integrated to improve the safety and self-adjustment performance of the path, and the redundant nodes are eliminated from the path data, and the control points and the total length of the path are greatly reduced, so that the path of the improved algorithm can take into account the requirements of efficiency and safety.
To enhance the performance of the A* algorithm and address its limitations in specific scenarios, this study introduces three core improvements aimed at optimizing the algorithm’s efficiency, safety, and applicability:
- (1)
By introducing an obstacle raster coefficient and a turning penalty function, this research develops a more accurate heuristic function. This function optimizes the cost calculation method as well as enhances the adaptability and directionality of the search path to map features, thereby improving the precision and practicality of path planning.
- (2)
In response to the issue of paths potentially traversing through sparse obstacles, this study has designed and optimized an efficient search strategy. By reducing the search space and computational complexity, this strategy significantly improves the reliability of path planning. It ensures that the planned paths avoid obstacles while also meeting the requirements for quick response.
- (3)
This research incorporates the concept of safety distance, substantially improving the safety and self-adjustment capabilities of the path. By eliminating redundant nodes from the path data and significantly reducing the number of control points and the total path length, an optimal balance between efficiency and safety in path planning is achieved.
The remainder of this study is organized as follows. The planning method of the traditional A* algorithm is provided in
Section 2.
Section 3 elaborates on the improvement process of the developed A* optimization algorithm.
Section 4 discusses the simulation results and validates the superior performance of the raised strategy, followed by the main conclusions drawn in
Section 5.
2. A* Algorithm Principle
The A* algorithm is a heuristic search algorithm that combines the Dijkstra algorithm and the greedy algorithm (depth-first). Its core concept is to find the minimum-cost path from the starting position to the target position in a specified global path map. Prior to planning, the A* algorithm requires a two-dimensional raster map for environment modeling. The environment information within the vehicle’s moving area in the world coordinate system is mapped onto a grid diagram. In
Figure 1, a 30 × 50 grid map in the world coordinate system is depicted, which will serve as the test experimental map. The grid side length is denoted as “m = 1”, where the black areas represent obstacles, and the white areas signify feasible regions.
In the search process, the moving cost estimation function from the start position to the target position
is defined as follows:
where,
is the cost estimate from the initial state through state
n to the target state,
is the actual cost in the state space from the initial state to state
n, and
is the heuristic function of the best path from state
n to the target state, that is, the estimated moving cost. The relationship between the planning node and the cost function in the search process is shown in
Figure 2.
in
Figure 2 represents the actual single-step moving distance from parent node
n − 1 to current node n;
represents the actual single-step moving distance from the current node n to the next node n + 1; and
is the sum of the real moving distance
from the start node to the
n − 1 node and the actual single-step moving distance
from the
n − 1 node to the current node n, that is, the sum of the distance of each planned path. Thus, the expression of the true moving distance function
can be given as:
If the evaluation value of is much less than , then will be approximately equal to . At this time, the algorithm A* is similar to Dijkstra algorithm, and the number of traversal nodes will increase, and the search efficiency will be greatly reduced. If is much larger than , the A* algorithm gradually evolves into the best first search algorithm, and the path planning speed becomes faster, but the local optimal solution is prone to occur. Therefore, the performance of the A* algorithm depends on the selection of heuristic functions. Common estimation methods include Euclidean distance, Manhattan distance, and diagonal distance.
Suppose the starting point coordinates are , and the ending point coordinates are .
Then the Euclidean distance heuristic function is shown as follows:
The heuristic function of Manhattan distance is expressed as follows:
The heuristic function of the diagonal distance is shown as follows:
where,
Since the calculation accuracy of Euclidean distance is higher than that of Manhattan and diagonal distance, it is more likely to get the optimal path. Therefore, this paper chooses Euclidean distance as a heuristic function to predict the moving cost.
Based on the above algorithm principle, the path planning effect of the traditional A* algorithm displayed in the test map shown in
Figure 1 is shown in
Figure 3.