Auction-based dynamic task allocation for foraging with a cooperative robot team

Changyun Wei, Koen V. Hindriks, Catholijn M. Jonker

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Many application domains require search and retrieval, which is also known in the robotic domain as foraging. An example domain is search and rescue where a disaster area needs to be explored and transportation of survivors to a safe area needs to be arranged. Performing these tasks by more than one robot increases performance if tasks are allocated and executed efficiently. In this paper, we study the Multi-Robot Task Allocation (MRTA) problem in the foraging domain. We assume that a team of robots is cooperatively searching for targets of interest in an environment which need to be retrieved and brought back to a home base. We look at a more general foraging problem than is typically studied where coordination also requires to take temporal constraints into account. As usual, robots have no prior knowledge about the location of targets, but in addition need to deliver targets to the home base in a specific order. This significantly increases the complexity of a foraging problem. We use a graph-based model to analyse the problem and the dynamics of allocating exploration and retrieval tasks. Our main contribution is an extension of auction-based approaches to deal with dynamic foraging task allocation where not all tasks are initially known. We use the Blocks World for Teams (BW4T) simulator to evaluate the proposed approach.

Original languageEnglish
Title of host publicationMulti-Agent Systems - 12th European Conference, EUMAS 2014, Revised Selected Papers
EditorsNils Bulling
PublisherSpringer/Verlag
Pages159-174
Number of pages16
ISBN (Print)9783319171296
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event12th European Conference on Multi-Agent Systems, EUMAS 2014 - Prague, Czech Republic
Duration: 18 Dec 201419 Dec 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8953
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th European Conference on Multi-Agent Systems, EUMAS 2014
CountryCzech Republic
CityPrague
Period18/12/1419/12/14

Fingerprint

Task Allocation
Foraging
Auctions
Robot
Robots
Target
Retrieval
Temporal Constraints
Multi-robot
Disasters
Disaster
Robotics
Prior Knowledge
Simulators
Simulator
Evaluate
Graph in graph theory

Keywords

  • Auctions
  • Foraging
  • Multi-Robot task allocation

Cite this

Wei, C., Hindriks, K. V., & Jonker, C. M. (2015). Auction-based dynamic task allocation for foraging with a cooperative robot team. In N. Bulling (Ed.), Multi-Agent Systems - 12th European Conference, EUMAS 2014, Revised Selected Papers (pp. 159-174). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8953). Springer/Verlag. https://doi.org/10.1007/978-3-319-17130-2_11
Wei, Changyun ; Hindriks, Koen V. ; Jonker, Catholijn M. / Auction-based dynamic task allocation for foraging with a cooperative robot team. Multi-Agent Systems - 12th European Conference, EUMAS 2014, Revised Selected Papers. editor / Nils Bulling. Springer/Verlag, 2015. pp. 159-174 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{73cffaec058e4b43bd8ee235376486a0,
title = "Auction-based dynamic task allocation for foraging with a cooperative robot team",
abstract = "Many application domains require search and retrieval, which is also known in the robotic domain as foraging. An example domain is search and rescue where a disaster area needs to be explored and transportation of survivors to a safe area needs to be arranged. Performing these tasks by more than one robot increases performance if tasks are allocated and executed efficiently. In this paper, we study the Multi-Robot Task Allocation (MRTA) problem in the foraging domain. We assume that a team of robots is cooperatively searching for targets of interest in an environment which need to be retrieved and brought back to a home base. We look at a more general foraging problem than is typically studied where coordination also requires to take temporal constraints into account. As usual, robots have no prior knowledge about the location of targets, but in addition need to deliver targets to the home base in a specific order. This significantly increases the complexity of a foraging problem. We use a graph-based model to analyse the problem and the dynamics of allocating exploration and retrieval tasks. Our main contribution is an extension of auction-based approaches to deal with dynamic foraging task allocation where not all tasks are initially known. We use the Blocks World for Teams (BW4T) simulator to evaluate the proposed approach.",
keywords = "Auctions, Foraging, Multi-Robot task allocation",
author = "Changyun Wei and Hindriks, {Koen V.} and Jonker, {Catholijn M.}",
year = "2015",
month = "1",
day = "1",
doi = "10.1007/978-3-319-17130-2_11",
language = "English",
isbn = "9783319171296",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer/Verlag",
pages = "159--174",
editor = "Nils Bulling",
booktitle = "Multi-Agent Systems - 12th European Conference, EUMAS 2014, Revised Selected Papers",

}

Wei, C, Hindriks, KV & Jonker, CM 2015, Auction-based dynamic task allocation for foraging with a cooperative robot team. in N Bulling (ed.), Multi-Agent Systems - 12th European Conference, EUMAS 2014, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8953, Springer/Verlag, pp. 159-174, 12th European Conference on Multi-Agent Systems, EUMAS 2014, Prague, Czech Republic, 18/12/14. https://doi.org/10.1007/978-3-319-17130-2_11

Auction-based dynamic task allocation for foraging with a cooperative robot team. / Wei, Changyun; Hindriks, Koen V.; Jonker, Catholijn M.

Multi-Agent Systems - 12th European Conference, EUMAS 2014, Revised Selected Papers. ed. / Nils Bulling. Springer/Verlag, 2015. p. 159-174 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8953).

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Auction-based dynamic task allocation for foraging with a cooperative robot team

AU - Wei, Changyun

AU - Hindriks, Koen V.

AU - Jonker, Catholijn M.

PY - 2015/1/1

Y1 - 2015/1/1

N2 - Many application domains require search and retrieval, which is also known in the robotic domain as foraging. An example domain is search and rescue where a disaster area needs to be explored and transportation of survivors to a safe area needs to be arranged. Performing these tasks by more than one robot increases performance if tasks are allocated and executed efficiently. In this paper, we study the Multi-Robot Task Allocation (MRTA) problem in the foraging domain. We assume that a team of robots is cooperatively searching for targets of interest in an environment which need to be retrieved and brought back to a home base. We look at a more general foraging problem than is typically studied where coordination also requires to take temporal constraints into account. As usual, robots have no prior knowledge about the location of targets, but in addition need to deliver targets to the home base in a specific order. This significantly increases the complexity of a foraging problem. We use a graph-based model to analyse the problem and the dynamics of allocating exploration and retrieval tasks. Our main contribution is an extension of auction-based approaches to deal with dynamic foraging task allocation where not all tasks are initially known. We use the Blocks World for Teams (BW4T) simulator to evaluate the proposed approach.

AB - Many application domains require search and retrieval, which is also known in the robotic domain as foraging. An example domain is search and rescue where a disaster area needs to be explored and transportation of survivors to a safe area needs to be arranged. Performing these tasks by more than one robot increases performance if tasks are allocated and executed efficiently. In this paper, we study the Multi-Robot Task Allocation (MRTA) problem in the foraging domain. We assume that a team of robots is cooperatively searching for targets of interest in an environment which need to be retrieved and brought back to a home base. We look at a more general foraging problem than is typically studied where coordination also requires to take temporal constraints into account. As usual, robots have no prior knowledge about the location of targets, but in addition need to deliver targets to the home base in a specific order. This significantly increases the complexity of a foraging problem. We use a graph-based model to analyse the problem and the dynamics of allocating exploration and retrieval tasks. Our main contribution is an extension of auction-based approaches to deal with dynamic foraging task allocation where not all tasks are initially known. We use the Blocks World for Teams (BW4T) simulator to evaluate the proposed approach.

KW - Auctions

KW - Foraging

KW - Multi-Robot task allocation

UR - http://www.scopus.com/inward/record.url?scp=84942814399&partnerID=8YFLogxK

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

U2 - 10.1007/978-3-319-17130-2_11

DO - 10.1007/978-3-319-17130-2_11

M3 - Conference contribution

SN - 9783319171296

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 159

EP - 174

BT - Multi-Agent Systems - 12th European Conference, EUMAS 2014, Revised Selected Papers

A2 - Bulling, Nils

PB - Springer/Verlag

ER -

Wei C, Hindriks KV, Jonker CM. Auction-based dynamic task allocation for foraging with a cooperative robot team. In Bulling N, editor, Multi-Agent Systems - 12th European Conference, EUMAS 2014, Revised Selected Papers. Springer/Verlag. 2015. p. 159-174. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-17130-2_11