A Metropolis-Hastings Algorithm for Task Allocation

Doha Hamza, Sarah Toonsi, Jeff S. Shamma

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider a robot-location assignment problem. The problem is confounded by a location network that restricts robots' motion to neighboring locations. The problem can be optimally solved using a centralized Hungarian algorithm. We propose a distributed game-theoretic algorithm, based on the Metropolis-Hastings mechanism, to eliminate the need for a central coordinator. Agents are activated at random. Agents compare their action, location, against a neighboring one based on the location network. If the new location represents an improvement in agent's utility, they move with probability one, otherwise, they move with a probability proportional to the difference in the two locations' utilities. Our algorithm converges to the optimal assignment of robots to locations. We provide extensive simulations, compare with previous work, and demonstrate the versatility of the proposed algorithm to various task allocation scenarios.

Original languageEnglish (US)
Title of host publication60th IEEE Conference on Decision and Control, CDC 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages7
ISBN (Electronic)9781665436595
StatePublished - 2021
Event60th IEEE Conference on Decision and Control, CDC 2021 - Austin, United States
Duration: Dec 13 2021Dec 17 2021

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370


Conference60th IEEE Conference on Decision and Control, CDC 2021
Country/TerritoryUnited States


  • Metropolis-Hastings algorithm
  • Task allocation
  • distributed learning
  • game-theoretic algorithm

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'A Metropolis-Hastings Algorithm for Task Allocation'. Together they form a unique fingerprint.

Cite this