DFGP: Computational framework for makespan-aware multi-robot task allocation in obstacle-rich environments

Abstract

Static multi-robot task allocation in obstacle-rich environments becomes more challenging as the problem size increases because trivial and contested assignments are typically addressed during the same planning process. This paper presents the computational depot-frontier growth partitioning (DFGP) framework for organising assignment decisions in static depot-aware multi-robot task allocation. In a centralised, full-information setting, DFGP expands depot-centred frontiers so that tasks exposed to a single frontier are absorbed in parallel, whereas only boundary tasks shared by multiple frontiers are resolved through entropy-based priority. Residual budget constraints limit frontier expansion, and the planning process is completed using dead-end recovery and bottleneck-oriented refinement. A benchmark evaluation across 18 scenarios encompassing six maps and robot counts of 5, 10, and 20 demonstrates that DFGP achieved an average lower-bound gap of 8.5%, compared with 20.4% for the strongest LKH-Minmax baseline, and attained the theoretical lower bound in six scenarios. In addition, DFGP also exhibits fixed-seed reproducibility with σ = 0, an allocation runtime of 1.3–2.5 s, and consistent lower-bound proximity across four maps in the 20-robot setting. Active construction indicators reveal that most assignments are absorbed uncontested, with frontier-based contested resolution and rescue confined to boundary cases; this resolution is most decisive in the intermediate-load regime, where task–robot competition is highest, whereas the headline gap reflects the combined effect of all framework stages. These results position DFGP as a benchmarked computational framework for obstacle-aware multi-robot planning that combines a low lower-bound gap with deterministic and practical execution.