Decentralized multi-robot allocation of tasks with temporal and precedence constraints

Ernesto Nunes, Mitchell McIntire, Maria Gini

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

We present an auction-based method for a team of robots to allocate and execute tasks that have temporal and precedence constraints. Temporal constraints are expressed as time windows, within which a task must be executed. The robots use our priority-based iterated sequential single-item auction algorithm to allocate tasks among themselves and keep track of their individual schedules. A key innovation is in decoupling precedence constraints from temporal constraints and dealing with them separately. We demonstrate the performance of the allocation method and show how it can be extended to handle failures and delays during task execution. We leverage the power of simulation as a tool to analyze the robustness of schedules. Data collected during simulations are used to compute well-known indexes that measure the risk of delay and failure in the robots’ schedules. We demonstrate the effectiveness of our method in simulation and with real robot experiments.

Original languageEnglish (US)
Pages (from-to)1193-1207
Number of pages15
JournalAdvanced Robotics
Volume31
Issue number22
DOIs
StatePublished - Nov 17 2017

Keywords

  • Task allocation
  • precedence constraints
  • temporal constraints

Fingerprint Dive into the research topics of 'Decentralized multi-robot allocation of tasks with temporal and precedence constraints'. Together they form a unique fingerprint.

Cite this