HGTA: A Hexagonal Grid-Based Task Allocation Method for Multi-Robot Coverage in Known 2D Environments

For multi-robot cooperative coverage, an effective spatial division strategy is essential to ensure balanced and spatially continuous task regions for each robot. Traditional grid-based partitioning approaches like DARP (Divide Areas based on Robots’ Positions) and TASR (Task Allocation based on Spatial Regions) often generate discontinuous sub-regions and imbalanced workloads, particularly in irregular or fragmented task spaces. To mitigate these issues, this paper introduces HGTA (Hexagonal Grid-based Task Allocation), a novel method that employs hexagonal tessellation for environmental representation. The hexagonal grid structure provides uniform neighbor connectivity and minimizes boundary fragmentation, yielding smoother partitions. HGTA integrates a multi-stage wavefront expansion algorithm with an iterative region-correction mechanism, jointly ensuring spatial contiguity and load equilibrium across robots. Extensive evaluations in 2D environments with varying obstacle densities and robot distributions show that HGTA enhances spatial continuity—achieving improvements of 18.2% in connectivity and 17.8% in boundary smoothness over DARP, and 7.5% and 9.5% over TASR, respectively—while also improving workload balance (variance reduction up to 18.5%) without compromising computational efficiency. The core contribution lies in the synergistic coupling of hexagonal tessellation, wavefront expansion, and dynamic correction, a design that fundamentally advances partition smoothness and convergence speed. HGTA thus offers a robust foundation for multi-robot cooperative coverage, area surveillance, and underwater search applications where connected and balanced partitions are critical.