# Clustering Method of Large-Scale Battlefield Airspace Based on Multi A * in Airspace Grid System
## 4 Airspace Clustering Steps Based on Multi-A \({}^{*}\) Algorithm
### Using Multi A \({}^{\star}\) Algorithm to Generate Edge Cluster Lines  
Compared with the _Dijkstra_ algorithm, the A \({}^{\star}\) algorithm is more \"heuristic\", reducing the search for points with less possibility of passing through, and improving the efficiency of computing. Before the algorithm operation, the initialization parameters such as the starting point, the ending point and the obstacles need to be clear. The core of the algorithm is the heuristic function \(F\) that drives the grid path generation:  
\[F=G+H \tag{5}\]  
where \(G\) is the mobile generation value (grid quantity value) that moves from the starting point to a specific node, and the value depends on the information of known nodes; \(H\) is the  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Grid Size** & **Grid Code** \\ \hline \(10\) km & \(N020D4452\) \\ \(1\) km & \(N020D445720\) \\ \(100\) m & \(N020D44572203\) \\ \(10\) m & \(N020D4457252039\) \\ \(1\) m & \(N020D445725120395\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Rectangular grid code table of sample points.  
Figure 9: Schematic Diagram of Battlefield Airspace Grid Generation.  
estimated cost of a specific node moving to the target point, which is usually calculated by the estimation method. The value comes from the estimation of the information of unknown points. By constantly updating the comparison parameter values, it is determined to save the node grid and generate the required path by connecting the node grids. The Multi A * algorithm proposed in this paper retains the operation logic and the core heuristic function \(F\) of the traditional A * algorithm. Through the idea of finding points first, then connecting lines, and finally generating airspace clusters, it meets the different accuracy requirements of airspace clustering by setting multiple groups of \"starting points--ending points\".  
The specific process of A * algorithm to generate clustering edge lines is omitted here. Set the number of target clusters m = 6, and the battlefield airspace clustering diagram can be preliminarily obtained (as shown in the Figure 10). The final airspace clustering results are recorded shown in the Table 3.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Airspace Number** & **Airspace Position** & **Airspace Shape** & **Airspace Size (km)** & **Usage Time** &
\begin{tabular}{c} **Communication** \\ **Frequency** \\ \end{tabular} \\ \hline
1 & B316 & Rectangle & 120 \(\times\) 20 & 8:00–10:00 & 87.975 MHz \\
2 & E222 & Rectangle & 30 \(\times\) 70 & 9:00–10:00 & 67.975 MHz \\
3 & E418 & Rectangle & 45 \(\times\) 40 & 7:00–8:00 & 77.975 MHz \\
4 & B411 & Rectangle & 100 \(\times\) 20 & 7:00–9:00 & 87.975 MHz \\
5 & C206 & Rectangle & 70 \(\times\) 80 & 8:00–10:00 & 87.975 MHz \\
6 & E209 & Rectangle & 20 \(\times\) 60 & 9:00–11:00 & 77.975 MHz \\
7 & F006 & Rectangle & 80 \(\times\) 80 & 14:00–16:00 & 67.975 MHz \\
8 & D122 & Rectangle & 20 \(\times\) 60 & 15:00–17:00 & 67.975 MHz \\
9 & B221 & Circle & 25 & 7:00–10:00 & 87.975 MHz \\
10 & A222 & Circle & 20 & 8:00–9:00 & 87.975 MHz \\
11 & F025 & Circle & 30 & 9:00–10:00 & 77.975 MHz \\
12 & A303 & Circle & 25 & 8:00–11:00 & 87.975 MHz \\
13 & B206 & Circle & 40 & 15:00–16:00 & 67.975 MHz \\
14 & F204 & Circle & 25 & 13:00–17:00 & 67.975 MHz \\
15 & D119 & Circle & 20 & 16:00–18:00 & 87.975 MHz \\ \hline \hline \end{tabular}
\end{table}
Table 2: Characteristic parameter table of task airspace.  
Figure 10: Battlefield airspace clustering diagram.