Online Multi-Robot Task Assignment with Stochastic Blockages

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Downloads (Pure)


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 languageEnglish
Title of host publicationProceedings of the IEEE 61st Conference on Decision and Control (CDC 2022)
ISBN (Print)978-1-6654-6761-2
Publication statusPublished - 2022
EventIEEE 61st Conference on Decision and Control (CDC 2022) - Cancún, Mexico
Duration: 6 Dec 20229 Dec 2022


ConferenceIEEE 61st Conference on Decision and Control (CDC 2022)

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project
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.


  • Costs
  • Uncertainty
  • Heuristic algorithms
  • Computational modeling
  • Stochastic processes
  • Routing
  • Robustness


Dive into the research topics of 'Online Multi-Robot Task Assignment with Stochastic Blockages'. Together they form a unique fingerprint.

Cite this