License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.3
URN: urn:nbn:de:0030-drops-111247
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11124/
Go to the corresponding LIPIcs Volume Portal

Akitaya, Hugo A. ; Arkin, Esther M. ; Damian, Mirela ; Demaine, Erik D. ; Dujmovic, Vida ; Flatland, Robin ; Korman, Matias ; Palop, Belen ; Parada, Irene ; van Renssen, André ; Sacristán, Vera

Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers

pdf-format:
LIPIcs-ESA-2019-3.pdf (1 MB)

Abstract

We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra "helper" modules ("musketeers") suffice to reconfigure the remaining n modules between any two given configurations. Our algorithm uses O(n^2) pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive "sliding" moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.

BibTeX - Entry

@InProceedings{akitaya_et_al:LIPIcs:2019:11124,
  author =	{Hugo A. Akitaya and Esther M. Arkin and Mirela Damian and Erik D. Demaine and Vida Dujmovic and Robin Flatland and Matias Korman and Belen Palop and Irene Parada and Andr{\'e} van Renssen and Vera Sacrist{\'a}n},
  title =	{{Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11124},
  URN =		{urn:nbn:de:0030-drops-111247},
  doi =		{10.4230/LIPIcs.ESA.2019.3},
  annote =	{Keywords: Reconfiguration, geometric algorithm, pivoting squares, modular robots}
}

Keywords: Reconfiguration, geometric algorithm, pivoting squares, modular robots
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI