License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.10
URN: urn:nbn:de:0030-drops-138094
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13809/
Go to the corresponding LIPIcs Volume Portal

A. Akitaya, Hugo ; Demaine, Erik D. ; Gonczi, Andrei ; Hendrickson, Dylan H. ; Hesterberg, Adam ; Korman, Matias ; Korten, Oliver ; Lynch, Jayson ; Parada, Irene ; Sacristán, Vera

Characterizing Universal Reconfigurability of Modular Pivoting Robots

pdf-format:
LIPIcs-SoCG-2021-10.pdf (1 MB)

Abstract

We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using O(n³) monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN'18] that we consider of independent interest.

BibTeX - Entry

@InProceedings{a.akitaya_et_al:LIPIcs.SoCG.2021.10,
  author =	{A. Akitaya, Hugo and Demaine, Erik D. and Gonczi, Andrei and Hendrickson, Dylan H. and Hesterberg, Adam and Korman, Matias and Korten, Oliver and Lynch, Jayson and Parada, Irene and Sacrist\'{a}n, Vera},
  title =	{{Characterizing Universal Reconfigurability of Modular Pivoting Robots}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13809},
  URN =		{urn:nbn:de:0030-drops-138094},
  doi =		{10.4230/LIPIcs.SoCG.2021.10},
  annote =	{Keywords: reconfiguration, geometric algorithm, PSPACE-hardness, pivoting hexagons, pivoting squares, modular robots}
}

Keywords: reconfiguration, geometric algorithm, PSPACE-hardness, pivoting hexagons, pivoting squares, modular robots
Collection: 37th International Symposium on Computational Geometry (SoCG 2021)
Issue Date: 2021
Date of publication: 02.06.2021

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