Efficient heuristics for a time-extended multi-robot task allocation problem

Hakim Mitiche, Dalila Boughaci, Maria L Gini

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

In this paper, we define a time-extended multirobot task allocation problem, design and analyze some heuristics to tackle the problem complexity in computational resource constrained settings. The robots (or agents) can perform a limited amount of work per unit of time, while the tasks have durations and deadlines by which they must be completed. These constraints, in addition to a relatively small number of agents, may not allow the allocation of all tasks. The heuristics we present are easy-to-implement, tuning free and fast. We analyze these heuristics theoretically with respect to computational complexity. Then, we empirically compare them with respect to performance criteria on a synthetic testset. In so doing, we offer solutions for devices with computation power limitations. The same algorithms can also be embedded into metaheuristics or hyper-heuristics to efficiently and effectively solve the problem.

Original languageEnglish (US)
Title of host publicationNTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781467366854
DOIs
StatePublished - Dec 29 2015
Event1st International Conference on New Technologies of Information and Communication, NTIC 2015 - Mila, Algeria
Duration: Nov 8 2015Nov 9 2015

Publication series

NameNTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding

Other

Other1st International Conference on New Technologies of Information and Communication, NTIC 2015
CountryAlgeria
CityMila
Period11/8/1511/9/15

Keywords

  • Multi-robot systems
  • heuristic algorithms
  • vehicle routing and scheduling

Fingerprint Dive into the research topics of 'Efficient heuristics for a time-extended multi-robot task allocation problem'. Together they form a unique fingerprint.

Cite this