EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

JangHo Seo, Joonwoo Lee

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →