Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2021/13809/
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: |
|
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 | |
| Seminar: | 37th International Symposium on Computational Geometry (SoCG 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 02.06.2021 |
