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

Ernesto Nunes, Mitchell McIntire, Maria Gini

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


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
Issue number22
StatePublished - Nov 17 2017

Bibliographical note

Funding Information:
Partial support provided by the National Science Foundation [grant number NSF IIP-1439728], [grant number NSF CNF-

Funding Information:
1531330]; Doctoral Dissertation Fellowship program from the University of Minnesota


  • Task allocation
  • precedence constraints
  • temporal constraints


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