Online Multi-Robot Task Assignment with Stochastic Blockages

Online Multi-Robot Task Assignment with Stochastic Blockages

Wilde, N. (TU Delft Learning & Autonomous Control)
Alonso-Mora, J. (TU Delft Learning & Autonomous Control)

2022

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.

Costs
Uncertainty
Heuristic algorithms
Computational modeling
Stochastic processes
Routing
Robustness

http://resolver.tudelft.nl/uuid:987a714d-5cf0-451c-ab29-84f843c78704

https://doi.org/10.1109/CDC51059.2022.9993099

IEEE

2023-07-01

978-1-6654-6761-2

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

IEEE 61st Conference on Decision and Control (CDC 2022), 2022-12-06 → 2022-12-09, Cancún, Mexico

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.

Institutional Repository

conference paper

© 2022 N. Wilde, J. Alonso-Mora