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

Hakim Mitiche; Dalila Boughaci; Maria Gini

doi:10.1109/NTIC.2015.7368756

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

Hakim Mitiche, Dalila Boughaci, Maria Gini

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

14 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 language	English (US)
Title of host publication	NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781467366854
DOIs	https://doi.org/10.1109/NTIC.2015.7368756
State	Published - Dec 29 2015
Event	1st International Conference on New Technologies of Information and Communication, NTIC 2015 - Mila, Algeria Duration: Nov 8 2015 → Nov 9 2015

Publication series

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

Other

Other	1st International Conference on New Technologies of Information and Communication, NTIC 2015
Country/Territory	Algeria
City	Mila
Period	11/8/15 → 11/9/15

Bibliographical note

Publisher Copyright:
© 2015 IEEE.

Keywords

Multi-robot systems
heuristic algorithms
vehicle routing and scheduling

Publisher link

10.1109/NTIC.2015.7368756

Find It

Find It at U of M Libraries

Cite this

Mitiche, H., Boughaci, D., & Gini, M. (2015). Efficient heuristics for a time-extended multi-robot task allocation problem. In NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding Article 7368756 (NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/NTIC.2015.7368756

Efficient heuristics for a time-extended multi-robot task allocation problem. / Mitiche, Hakim; Boughaci, Dalila; Gini, Maria.
NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding. Institute of Electrical and Electronics Engineers Inc., 2015. 7368756 (NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Mitiche, H, Boughaci, D & Gini, M 2015, Efficient heuristics for a time-extended multi-robot task allocation problem. in NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding., 7368756, NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding, Institute of Electrical and Electronics Engineers Inc., 1st International Conference on New Technologies of Information and Communication, NTIC 2015, Mila, Algeria, 11/8/15. https://doi.org/10.1109/NTIC.2015.7368756

Mitiche H, Boughaci D, Gini M. Efficient heuristics for a time-extended multi-robot task allocation problem. In NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding. Institute of Electrical and Electronics Engineers Inc. 2015. 7368756. (NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding). doi: 10.1109/NTIC.2015.7368756

Mitiche, Hakim ; Boughaci, Dalila ; Gini, Maria. / Efficient heuristics for a time-extended multi-robot task allocation problem. NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding. Institute of Electrical and Electronics Engineers Inc., 2015. (NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding).

@inproceedings{829696d56a7a40f89eb65c5f108474a9,

title = "Efficient heuristics for a time-extended multi-robot task allocation problem",

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.",

keywords = "Multi-robot systems, heuristic algorithms, vehicle routing and scheduling",

author = "Hakim Mitiche and Dalila Boughaci and Maria Gini",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 1st International Conference on New Technologies of Information and Communication, NTIC 2015 ; Conference date: 08-11-2015 Through 09-11-2015",

year = "2015",

month = dec,

day = "29",

doi = "10.1109/NTIC.2015.7368756",

language = "English (US)",

series = "NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "NTIC 2015 - 2015 1st International Conference on New Technologies of Information and Communication, Proceeding",

}

TY - GEN

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

AU - Mitiche, Hakim

AU - Boughaci, Dalila

AU - Gini, Maria

PY - 2015/12/29

Y1 - 2015/12/29

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

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

KW - Multi-robot systems

KW - heuristic algorithms

KW - vehicle routing and scheduling

UR - https://www.scopus.com/pages/publications/84963533897

UR - https://www.scopus.com/inward/citedby.url?scp=84963533897&partnerID=8YFLogxK

U2 - 10.1109/NTIC.2015.7368756

DO - 10.1109/NTIC.2015.7368756

M3 - Conference contribution

AN - SCOPUS:84963533897

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

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

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1st International Conference on New Technologies of Information and Communication, NTIC 2015

Y2 - 8 November 2015 through 9 November 2015

ER -

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

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this