A UAV Penetration Method Based on the Improved A* Algorithm

This paper presents an algorithm for addressing the penetration problem between coverage regions. The algorithm combines the subregion coverage sequence determination and the A* algorithm-based drone obstacle avoidance methods to achieve path planning from the drone’s starting point to the destination. The boustrophedon algorithm is employed to calculate optimal paths for independent subregions, while a genetic algorithm is utilized to determine an optimized coverage sequence, thereby minimizing the overall path length between regions. Additionally, the Laguerre graph construction algorithm is introduced, leveraging the Laguerre graph derived from the Voronoi graph to effectively describe the positional relationships of a given set of disjoint circles. To ensure obstacle avoidance, the A* algorithm is then applied to search for the shortest path within the Laguerre graph.