# Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy
## 3 Hybrid A-Star Algorithm and Trichotomy Search  
### Hybrid A-Star Algorithm  
The A-star algorithm, as a hybrid of Dijkstra and BFS, differs from these two algorithms by employing an evaluation function, which is the core of the algorithm. The evaluation function takes the form of Equation (10):  
\[f(n)=g(n)+h(n) \tag{10}\]  
where \(f(n)\) represents the overall priority of a node. When selecting a node, this overall priority, also known as the evaluation function, is considered; \(g(n)\) represents the cumulative cost from the starting point to the current node, also known as the cumulative cost function; and \(h(n)\) represents the estimated cost from the current node to the destination point, also referred to as the heuristic cost function. \(g(n)\) and \(h(n)\) are typically calculated using either the Manhattan distance or Euclidean distance. To calculate these two values, \(g(n)\) and \(h(n)\) must use the same unit of measurement. In this paper, the Euclidean distance is chosen. The Euclidean distance is one of the most common distance measurement methods. In two-dimensional space, it measures the shortest linear distance between two points. Choosing the Euclidean distance can more accurately calculate the cumulative cost function and the heuristic cost function, and it can guide the algorithm nodes to expand towards a shorter path direction.  
A-star algorithm controls the points in the map by establishing an open list and a closed list. First, the starting point is added to the open list. Then, the following process is repeated:  
* Traverse the open list to find the node with the minimum \(f(n)\) value, which becomes the node to be processed. Remove it from the open list to prevent node reuse;
* Add the node to be processed to the closed list;
* For the nodes adjacent to the current node, the following procedures are applied: If a node is unreachable or already on the closed list, it is ignored. If a node is not on the open list, it is added to the open list. The current node is then set as its parent node, and the \(f(n)\), \(g(n)\), and \(h(n)\) values of the current node are recorded. If a node is already on the open list, the algorithm checks if the path (i.e., from the current node to the adjacent node) is better using the \(g(n)\) value as a reference. A smaller \(g(n)\) value indicates a better path. If the new path is better, the parent node is set as the current node, and the \(g(n)\) value and \(f(n)\) value are recalculated. If the open list is sorted based on \(f(n)\) values, reordering is necessary after the change;
* When the destination point has been added to the open list, indicating that either the path has been found or the search for the endpoint has failed, and the open list is empty, indicating that there is no path, the loop ends and the search stops;  
Figure 2: Map preprocessing. (**a**) The original map; (**b**) The discrete map. (**c**) Visual diagram of the clustering tree. (**d**) Rasterized map after cluster expansion.  
* The Hybrid A-star algorithm and the A-star algorithm both belong to graph-based search algorithms, with the Hybrid A-star algorithm being an improvement on the A-star algorithm. While the Hybrid A-star algorithm and the A-star algorithm share a similar process, the Hybrid A-star algorithm does not limit expansion to the center of the grid. Instead, a set of step sizes, a turning radius, and a discrete number of front wheel steering angles form the basis for expanding nodes. This allows child nodes to be located at any position within the grid rather than just at the grid center. Since the Hybrid A-star algorithm considers vehicle kinematic constraints during state node expansion, the resulting path is executable by the vehicle. However, the Hybrid A-star algorithm sacrifices completeness and optimality [29]. The node expansion methods of the Hybrid A-star algorithm and the A-star algorithm are illustrated in Figure 3.