DECENTRALIZED AREA ALLOCATION FOR COMPLETE COVERAGE BY A UAV GROUP BASED ON A MODIFIED AUCTION ALGORITHM

Abstract

This paper addresses the problem of decentralized allocation of coverage zones among a group of unmanned aerial vehicles (UAVs) for aerial photography, territory monitoring, search-and-rescue, and similar missions. It is noted that existing methods for allocating coverage zones for subsequent complete coverage (scanning) by UAVs rely on a central coordinator that is vulnerable to failures due to unstable communication and mission dynamics, scale poorly, and cannot reliably adapt to the dynamic conditions of a multi-agent coverage mission, whereas decentralized auction-based methods address the allocation of discrete point tasks, which limits their applicability to areal coverage. The aim of the work is to adapt the decentralized auction-based Consensus-Based Bundle Algorithm (CBBA) to the area-coverage problem, taking into account UAV heterogeneity in speed, sensor footprint width, and maneuvering cost while minimizing the total mission completion time. A modification of CBBA is proposed in which Voronoi zones are represented as separate algorithm tasks; after allocation, each zone is covered by the assigned agent (UAV) along a boustrophedon trajectory, which ensures complete scanning of the specified area. A task evaluation (score) function is formulated that accounts for the zone area, geometric complexity (turns), coverage and transit times, and individual UAV parameters; it is shown that the diminishing-marginal-gain property holds naturally, which guarantees auction convergence. A computational experiment (1080 runs) confirmed complete (100%) coverage of the operational space, consensus convergence within 10–23 iterations, and a planning time acceptable for onboard application. For heterogeneous UAV groups, the modified algorithm achieved the shortest mission completion time for all agent-count values, reducing the median mission time by 9%–77.6% on average relative to five comparison methods; for homogeneous groups it remains competitive. The predicted linear growth of mission time with an increasing number of agents enables scaling to large UAV groups and collective-mission tasks. Future work will extend the evaluation function to account for zone convexity (3D aspects) and the residual battery charge of UAVs.