DFGP: Computational framework for makespan-aware multi-robot task allocation in obstacle-rich environments
Journal of Computational Design and Engineering · 04.08.2026 · 13 (8) · 133-149
DOI: 10.1093/jcde/qwag070 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Computational Design and Engineering, online erschienen am 25.07.2026. Verfasst von JangHo Seo und 1 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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 organizing assignment decisions in static depot-aware multi-robot task allocation. In a centralized, 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 $\sigma =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.
Zitieren
APA
Seo, J., & Lee, J. (2026). DFGP: Computational framework for makespan-aware multi-robot task allocation in obstacle-rich environments. Journal of Computational Design and Engineering, 13(8), 133-149. https://doi.org/10.1093/jcde/qwag070
Vancouver
Seo J, Lee J. DFGP: Computational framework for makespan-aware multi-robot task allocation in obstacle-rich environments. Journal of Computational Design and Engineering. 2026;13(8):133-149. doi:10.1093/jcde/qwag070
BibTeX
@article{Seo2026,
author = {Seo, JangHo and Lee, Joonwoo},
title = {DFGP: Computational framework for makespan-aware multi-robot task allocation in obstacle-rich environments},
journal = {Journal of Computational Design and Engineering},
year = {2026},
volume = {13},
number = {8},
pages = {133--149},
doi = {10.1093/jcde/qwag070}
}
EUVIMED