Paper by Erik D. Demaine

Reference:

Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Della H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán, “Characterizing Universal Reconfigurability of Modular Pivoting Robots”, in Proceedings of the 37th International Symposium on Computational Geometry (SoCG 2021), edited by Kevin Buchin and Éric Colin de Verdière, LIPIcs, 2021, 10:1–10:20.

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.

Comments:

This paper is also available from LIPIcs. The full paper is available as arXiv:2012.07556.

Length:

The paper is 20 pages.

Availability:

The paper is available in PDF (1264k).

See information on file formats.

[Google Scholar search]