Online Multi-Robot Task Assignment with Stochastic Blockages

N. Wilde; J. Alonso-Mora

doi:10.1109/CDC51059.2022.9993099

Online Multi-Robot Task Assignment with Stochastic Blockages

Learning & Autonomous Control

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

3 Citations (Scopus)

12 Downloads (Pure)

Abstract

In this paper we study the multi-robot task assignment problem with tasks that appear online and need to be serviced within a fixed time window in an uncertain environment. For example, when deployed in dynamic, human-centered environments, the team of robots may not have perfect information about the environment. Parts of the environment may temporarily become blocked and blockages may only be observed on location. While numerous variants of the Canadian Traveler Problem describe the path planning aspect of this problem, few work has been done on multi-robot task allocation (MRTA) under this type of uncertainty. In this paper, we introduce and theoretically analyze the problem of MRTA with recoverable online blockages. Based on a stochastic blockage model, we compute offline tours using the expected travel costs for the online routing problem. The cost of the offline tours is used in a greedy task assignment algorithm. In simulation experiments we highlight the performance benefits of the proposed method under various settings.

Original language	English
Title of host publication	Proceedings of the IEEE 61st Conference on Decision and Control (CDC 2022)
Publisher	IEEE
Pages	5259-5266
ISBN (Print)	978-1-6654-6761-2
DOIs	https://doi.org/10.1109/CDC51059.2022.9993099
Publication status	Published - 2022
Event	IEEE 61st Conference on Decision and Control (CDC 2022) - Cancún, Mexico Duration: 6 Dec 2022 → 9 Dec 2022

Conference

Conference	IEEE 61st Conference on Decision and Control (CDC 2022)
Country/Territory	Mexico
City	Cancún
Period	6/12/22 → 9/12/22

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Costs
Uncertainty
Heuristic algorithms
Computational modeling
Stochastic processes
Routing
Robustness

Access to Document

10.1109/CDC51059.2022.9993099

Online_Multi-Robot_Task_Assignment_with_Stochastic_BlockagesFinal published version, 1.72 MB

Cite this

@inproceedings{987a714d5cf0451cab2984f843c78704,

title = "Online Multi-Robot Task Assignment with Stochastic Blockages",

abstract = "In this paper we study the multi-robot task assignment problem with tasks that appear online and need to be serviced within a fixed time window in an uncertain environment. For example, when deployed in dynamic, human-centered environments, the team of robots may not have perfect information about the environment. Parts of the environment may temporarily become blocked and blockages may only be observed on location. While numerous variants of the Canadian Traveler Problem describe the path planning aspect of this problem, few work has been done on multi-robot task allocation (MRTA) under this type of uncertainty. In this paper, we introduce and theoretically analyze the problem of MRTA with recoverable online blockages. Based on a stochastic blockage model, we compute offline tours using the expected travel costs for the online routing problem. The cost of the offline tours is used in a greedy task assignment algorithm. In simulation experiments we highlight the performance benefits of the proposed method under various settings.",

keywords = "Costs, Uncertainty, Heuristic algorithms, Computational modeling, Stochastic processes, Routing, Robustness",

author = "N. Wilde and J. Alonso-Mora",

note = "Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; IEEE 61st Conference on Decision and Control (CDC 2022) ; Conference date: 06-12-2022 Through 09-12-2022",

year = "2022",

doi = "10.1109/CDC51059.2022.9993099",

language = "English",

isbn = "978-1-6654-6761-2",

pages = "5259--5266",

booktitle = "Proceedings of the IEEE 61st Conference on Decision and Control (CDC 2022)",

publisher = "IEEE",

address = "United States",

}

TY - GEN

T1 - Online Multi-Robot Task Assignment with Stochastic Blockages

AU - Wilde, N.

AU - Alonso-Mora, J.

N1 - Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2022

Y1 - 2022

N2 - In this paper we study the multi-robot task assignment problem with tasks that appear online and need to be serviced within a fixed time window in an uncertain environment. For example, when deployed in dynamic, human-centered environments, the team of robots may not have perfect information about the environment. Parts of the environment may temporarily become blocked and blockages may only be observed on location. While numerous variants of the Canadian Traveler Problem describe the path planning aspect of this problem, few work has been done on multi-robot task allocation (MRTA) under this type of uncertainty. In this paper, we introduce and theoretically analyze the problem of MRTA with recoverable online blockages. Based on a stochastic blockage model, we compute offline tours using the expected travel costs for the online routing problem. The cost of the offline tours is used in a greedy task assignment algorithm. In simulation experiments we highlight the performance benefits of the proposed method under various settings.

AB - In this paper we study the multi-robot task assignment problem with tasks that appear online and need to be serviced within a fixed time window in an uncertain environment. For example, when deployed in dynamic, human-centered environments, the team of robots may not have perfect information about the environment. Parts of the environment may temporarily become blocked and blockages may only be observed on location. While numerous variants of the Canadian Traveler Problem describe the path planning aspect of this problem, few work has been done on multi-robot task allocation (MRTA) under this type of uncertainty. In this paper, we introduce and theoretically analyze the problem of MRTA with recoverable online blockages. Based on a stochastic blockage model, we compute offline tours using the expected travel costs for the online routing problem. The cost of the offline tours is used in a greedy task assignment algorithm. In simulation experiments we highlight the performance benefits of the proposed method under various settings.

KW - Costs

KW - Uncertainty

KW - Heuristic algorithms

KW - Computational modeling

KW - Stochastic processes

KW - Routing

KW - Robustness

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

U2 - 10.1109/CDC51059.2022.9993099

DO - 10.1109/CDC51059.2022.9993099

M3 - Conference contribution

SN - 978-1-6654-6761-2

SP - 5259

EP - 5266

BT - Proceedings of the IEEE 61st Conference on Decision and Control (CDC 2022)

PB - IEEE

T2 - IEEE 61st Conference on Decision and Control (CDC 2022)

Y2 - 6 December 2022 through 9 December 2022

ER -

Online Multi-Robot Task Assignment with Stochastic Blockages

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this