TY - GEN
T1 - A Metropolis-Hastings Algorithm for Task Allocation
AU - Hamza, Doha
AU - Toonsi, Sarah
AU - Shamma, Jeff S.
N1 - Funding Information:
∗CEMSE division, King Abdullah University of Science and Technology (KAUST), Thuwal, KSA. †Industrial and Enterprise Systems Engineering (ISE), University of Illinois Urbana-Champaign, Illinois, USA. Emails:doha.hamzamohamed@kaust.edu.sa, stoonsi2@illinois.edu, jshamma@illinois.edu. The research reported in this publication was supported by funding from KAUST.
Publisher Copyright:
© 2021 IEEE.
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 -