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 | |
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-careOtherwise 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