An Algorithm for Planning Coverage of an Area with Obstacles with a Heterogeneous Group of Drones Using a Genetic Algorithm and Parameterized Polygon Decomposition

The paper presents an algorithm for planning agricultural field surveying routes in the presence of obstacles, designed to address precision agriculture tasks. Unlike classical methods, which are typically limited to straightforward zigzag (Zamboni) traversal and basic perimeter-based obstacle avoidance, the proposed algorithm accounts for heterogeneous unmanned aerial vehicles (UAVs) of varying types, ranges, costs, and speeds, along with a mobile ground platform that enables drone takeoff and landing at multiple points along the road. The key innovation lies in a two-stage optimization procedure: initially, a random set of field partitions into multiple sub-polygons with predefined area proportions (considering internal obstacles) is generated. Subsequently, the optimal partitioning is selected, and based on this, a genetic algorithm is applied to optimize flight parameters, including flight angle, entry points, composition, and sequence of drone launches, and the ground platform route. This approach achieves more localized coverage of individual field segments, with each segment serviced by an appropriate drone type, while also enabling flexible movement of the ground platform, thereby reducing unnecessary flights. This brings down the price of the coverage by 10–30% in some cases. The concluding section discusses future directions, including the incorporation of three-dimensional terrain considerations, dynamic factors (such as changing weather conditions and drone stoppages due to technical issues), and automated collision avoidance in intersecting route segments.