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

Clicks: 63
ID: 322526
2026
Free PDF
Article Quality & Performance Metrics
Overall Quality
Not rated
Combines reader engagement with the AI quality analysis. This article has not been analysed, so there is no overall score — reader engagement is measured and shown alongside.
AI Quality Assessment
Not analyzed
Readership in this journal
Steady

Ranked #9 of 44 articles by views in journal of computational design and engineering

Most read Least read

Bar heights use a square-root scale.

Mint this article as an NFT
Not yet minted

Create a permanent, verifiable on-chain record of this article on the Scimatic Network. The NFT is held in your Journament account, and you can withdraw it to your own wallet at any time.

5 SUSD one-off · no wallet required
Sign in to mint
Abstract
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.
Reference Key
openalex_W7171072802 Use this key to autocite in the manuscript while using SciMatic Manuscript Manager or Thesis Manager
Authors JangHo Seo, Joonwoo Lee
Are you one of these authors? Claim your profile
Journal journal of computational design and engineering
Year 2026
DOI
10.1093/jcde/qwag070
URL
https://doi.org/10.1093/jcde/qwag070
Keywords Keywords not found

Citations

No citations found. To add a citation, contact the admin at info@scimatic.org

Comments

No comments yet. Be the first to comment on this article.