# Hybrid A-Star Path Planning Method Based on Hierarchical Clustering and Trichotomy
## 2 Single Linkage Hierarchical Clustering Algorithm
### Single Linkage Hierarchical Clustering Algorithm  
Clustering is the process of dividing a dataset into different classes according to a specific criterion, such as distance, aiming to minimize the intra-class differences of data objects within the same class while maximizing the inter-class differences of data objects not in the same class. In this way, the obstacles are partitioned to achieve the purpose of hierarchical clustering. Suppose there is currently a partition \(P_{K}=(C_{1},C_{2},\cdots,C_{K})\), dividing the sample population into \(K\) classes. The total intra-class difference of this partition can be represented by Equation (4). \[\text{W}(P_{K})=\sum_{k=1}^{K}Int(C_{k}) \tag{4}\]  
where \(Int(C_{k})\) represents the within-cluster variance of class \(C_{k}\), and \(Int(C_{k})\) is also the sum of the Euclidean distances between all the data objects in the class. Commonly used within-cluster variances include variance, the maximum distance between any two points within the class, the longest edge in the minimum spanning tree, etc. The smaller the value of \(\text{W}(P_{K})\), the more homogeneous the partition of class \(K\) tends to be. Assuming there are \(N\) samples in the dataset to be clustered, hierarchical clustering initially forms \(N\) classes, with each sample forming its own class, resulting in \(N\) initial classes. By computing the inter-cluster differences between any two classes, the method iteratively merges the two classes with the smallest inter-cluster difference. The two classes are designated as any two of the \(K\) classes for example calculation, that is, all the classes between the \(K\) classes should be calculated, reducing the number of classes from \(K+1\) to \(K\). In other words, from \(P_{K+1}\), two classes, \(A\) and \(B\), are merged to obtain a new partition, \(P_{K}\), while satisfying Equation (5):  
\[arg\min_{A,B\in P_{K+1}}W(P_{K}) \tag{5}\]  
where \(P_{K}=\frac{P_{K+1}}{\{A,B\}}\cup\{A\cap B\}\) represents the new partition obtained by merging \(A\) and \(B\); and \(W(P_{K})=W(P_{K+1})-Int(A)-Int(B)+Int(A\cup B)\) represents the total intra-class difference of the new partition. Equation (5) is equivalent to Equation (6):  
\[\min_{A,B\in P_{K+1}}Int(A\cup B)-Int(A)-Int(B) \tag{6}\]  
Figure 1: Templates for the Prewitt operator. (**a**) Template 1: \(G(x)\). (**b**) Template 2: \(G(y)\). Equation (7), denoting the inter-class difference between two classes \(A\) and \(B\) as \(D_{A,\ B}\), is defined as follows:  
\[D_{A,B}=Int(A\cup B)-Int(A)-Int(B) \tag{7}\]  
As deduced above, the inter-class difference between two classes is the increment of the total intra-class difference after merging the two classes. The smaller the inter-class difference, the greater the similarity between the two classes. The essence of hierarchical clustering is to find the two classes with the smallest inter-class difference in each iteration, minimizing the increment of the total intra-class difference after merging [27]. Common computational methods for hierarchical clustering include the centroid method, [PERSON]'s minimum variance method, single linkage method, complete linkage method, and group average method [28]. Single linkage clustering, also known as nearest neighbor clustering, is selected in this paper. It defines the inter-class difference between two classes as the shortest distance between any two points in different classes calculated by Equation (8). \[D_{A,B}^{sin}=\underset{x_{i}\in A,x_{j}\in B}{\min}d(\overline{x}_{A}, \overline{x}_{B}) \tag{8}\]  
Single linkage clustering imposes no constraints on the shape of clusters and exhibits good scalability, capable of identifying irregular and elongated clusters. After merging two classes \(A\) and \(B\) to form a new class \(M\), it is necessary to recalculate the inter-class difference between the new class \(M\) and any other class \(C\).