## 2 Methodology
### A* Algorithm for Route Segment Connection  
By utilizing Voronoi-vertex-based search models, drones can already plan feasible flight routes in certain scenarios. For instance, in Figure 3, a flyable path can be determined using only three line segments. However, as the complexity of obstacles increases, situations where it is impossible to quickly generate paths using existing vertices may arise. In such cases, all Voronoi vertices within the known search space have a weight value of 0, or  
Figure 2: Schematic of fast path search using Voronoi vertices.  
the distance values, \(D\), no longer decrease. Typically, at this point, the starting point has advanced closer to the planned endpoint from its initial position, necessitating an extension of the trajectory to obtain new connectable Voronoi vertices and thereby transforming the problem into a local trajectory search method.  
The A* algorithm is a classic heuristic search algorithm. The heuristic function is calculated based on the minimum objective function value from the starting point to the current node combined with the estimated function value from the current node to the target point [39]. The entire trajectory search relies on this heuristic function. In a two-dimensional plane, the search space of the A* algorithm typically consists of the 8 pixels surrounding the current point. For each pixel in the search space, the cost is computed, and the node with the lowest cost is selected and added to the path as the new starting point. The cost function for node M in the search space is defined as follows:  
\[f(M)=g(M)+h(M) \tag{13}\]  
where, \(g(M)\) represents the heuristic factor, indicating the true cost from the initial node to the current node M, and \(h(M)\) represents the minimum cost estimate from the current node M to the target node. The search principle is to prioritize expanding nodes with lower \(f(M)\) values, which guarantees finding the optimal path. Generally, the A* algorithm demonstrates superior pathfinding performance and high robustness. However, in global route planning, due to the increase in search area, obtaining an optimal path requires a long convergence time and substantial memory space. However, by introducing a quick search strategy based on Voronoi vertices, the search and computation time can be significantly reduced. At this point, the A* algorithm serves as a localized searching algorithm for existing segments. As the search principle of the A* algorithm is well-established, this study does not elaborate on this topic further. We only provide an example of the initiation timing of the A* algorithm as a connection algorithm for route segments.  
The connection of flight route segments using the A* algorithm is shown in Figure 4. After the UAV reaches the point \(v_{3}\) by rapidly searching the path through the Voronoi vertices, with point \(v_{3}\) as the new starting point, the only directly connectable Voronoi vertices are \(v_{1}\), \(v_{2}\), and \(v_{4}\). By comparing the distance to the endpoint vector, point  
Figure 3: Schematic diagram of Voronoi vertex generation.  
is already the nearest connectable Voronoi vertex to the end point. At this point, the A* search mechanism is introduced, and the local path toward the endpoint is generated as a connection path, continuing until a new starting point appears in the A* path, where a new quick connection path can be generated in the search space.