A Metropolis-Hastings Algorithm for Task Allocation

Doha Hamza; Sarah Toonsi; Jeff S. Shamma

doi:10.1109/CDC45484.2021.9683575

A Metropolis-Hastings Algorithm for Task Allocation

Doha Hamza, Sarah Toonsi, Jeff S. Shamma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English (US)
Title of host publication	60th IEEE Conference on Decision and Control, CDC 2021
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4539-4545
Number of pages	7
ISBN (Electronic)	9781665436595
DOIs	https://doi.org/10.1109/CDC45484.2021.9683575
State	Published - 2021
Event	60th IEEE Conference on Decision and Control, CDC 2021 - Austin, United States Duration: Dec 13 2021 → Dec 17 2021

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
Volume	2021-December
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	60th IEEE Conference on Decision and Control, CDC 2021
Country/Territory	United States
City	Austin
Period	12/13/21 → 12/17/21

Keywords

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

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Online availability

10.1109/CDC45484.2021.9683575

Library availability

Discover UIUC Full Text

Cite this

A Metropolis-Hastings Algorithm for Task Allocation. / Hamza, Doha; Toonsi, Sarah; Shamma, Jeff S.
60th IEEE Conference on Decision and Control, CDC 2021. Institute of Electrical and Electronics Engineers Inc., 2021. p. 4539-4545 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2021-December).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hamza, D, Toonsi, S & Shamma, JS 2021, A Metropolis-Hastings Algorithm for Task Allocation. in 60th IEEE Conference on Decision and Control, CDC 2021. Proceedings of the IEEE Conference on Decision and Control, vol. 2021-December, Institute of Electrical and Electronics Engineers Inc., pp. 4539-4545, 60th IEEE Conference on Decision and Control, CDC 2021, Austin, United States, 12/13/21. https://doi.org/10.1109/CDC45484.2021.9683575

@inproceedings{f4b9f445972c4d61b54a1300e0ba9387,

title = "A Metropolis-Hastings Algorithm for Task Allocation",

abstract = "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.",

keywords = "Metropolis-Hastings algorithm, Task allocation, distributed learning, game-theoretic algorithm",

author = "Doha Hamza and Sarah Toonsi and Shamma, {Jeff S.}",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 60th IEEE Conference on Decision and Control, CDC 2021 ; Conference date: 13-12-2021 Through 17-12-2021",

year = "2021",

doi = "10.1109/CDC45484.2021.9683575",

language = "English (US)",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "4539--4545",

booktitle = "60th IEEE Conference on Decision and Control, CDC 2021",

address = "United States",

}

TY - GEN

T1 - A Metropolis-Hastings Algorithm for Task Allocation

AU - Hamza, Doha

AU - Toonsi, Sarah

AU - Shamma, Jeff S.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Metropolis-Hastings algorithm

KW - Task allocation

KW - distributed learning

KW - game-theoretic algorithm

UR - http://www.scopus.com/inward/record.url?scp=85125997729&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85125997729&partnerID=8YFLogxK

U2 - 10.1109/CDC45484.2021.9683575

DO - 10.1109/CDC45484.2021.9683575

M3 - Conference contribution

AN - SCOPUS:85125997729

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 4539

EP - 4545

BT - 60th IEEE Conference on Decision and Control, CDC 2021

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 60th IEEE Conference on Decision and Control, CDC 2021

Y2 - 13 December 2021 through 17 December 2021

ER -

A Metropolis-Hastings Algorithm for Task Allocation

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this