A game-theoretic formulation of the homogeneous self-reconfiguration problem

Daniel Pickem, Magnus Egerstedt, Jeff S. Shamma

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

Abstract

In this paper we formulate the homogeneous two- and three-dimensional self-reconfiguration problem over discrete grids as a constrained potential game. We develop a game-theoretic learning algorithm based on the Metropolis-Hastings algorithm that solves the self-reconfiguration problem in a globally optimal fashion. Both a centralized and a fully decentralized algorithm are presented and we show that the only stochastically stable state is the potential function maximizer, i.e. the desired target configuration. These algorithms compute transition probabilities in such a way that even though each agent acts in a self-interested way, the overall collective goal of self-reconfiguration is achieved. Simulation results confirm the feasibility of our approach and show convergence to desired target configurations.

Original languageEnglish (US)
Title of host publication54rd IEEE Conference on Decision and Control,CDC 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2829-2834
Number of pages6
ISBN (Electronic)9781479978861
DOIs
StatePublished - Feb 8 2015
Externally publishedYes
Event54th IEEE Conference on Decision and Control, CDC 2015 - Osaka, Japan
Duration: Dec 15 2015Dec 18 2015

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume54rd IEEE Conference on Decision and Control,CDC 2015
ISSN (Print)0743-1546

Other

Other54th IEEE Conference on Decision and Control, CDC 2015
CountryJapan
CityOsaka
Period12/15/1512/18/15

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'A game-theoretic formulation of the homogeneous self-reconfiguration problem'. Together they form a unique fingerprint.

Cite this