Iterated local search for time-extended multi-robot task allocation with spatio-temporal and capacity constraints

Hakim Mitiche, Dalila Boughaci, Maria Gini

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

We propose a method for task allocation to multiple physical agents that works when tasks have temporal and spatial constraints and agents have different capacities. Assuming that the problem is over-constrained, we need to find allocations that maximize the number of tasks that can be done without violating any of the constraints. The contribution of this work is the study of a new multi-robot task allocation problem and the design and the experimental evaluation of our approach, an iterated local search that is suitable for time critical applications. We created test instances on which we experimentally show that our approach outperforms a state-of-the-art approach to a related problem. Our approach improves the baseline's score on average by 2.35% and up to 10.53%, while responding in times shorter than the baseline's, on average, 1.6 s and up to 5.5 s shorter. Furthermore, our approach is robust to run replication and is not very sensitive to parameters tuning.

Original languageEnglish (US)
Pages (from-to)347-360
Number of pages14
JournalJournal of Intelligent Systems
Volume28
Issue number2
DOIs
StatePublished - Apr 1 2019

Bibliographical note

Funding Information:
Research supported: This work was supported by the Algerian Ministry of Higher Education and Scientific Research, scholarship number 187/PNE/USA/2013–2014.

Keywords

  • Multi-robot task allocation
  • iterated local search
  • routing

Fingerprint Dive into the research topics of 'Iterated local search for time-extended multi-robot task allocation with spatio-temporal and capacity constraints'. Together they form a unique fingerprint.

Cite this