Paper Info
Title
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots - The O(1) Musketeers.
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.
Year
DOI
Venue
2019
10.4230/LIPIcs.ESA.2019.3
Leibniz International Proceedings in Informatics
Keywords
Field
DocType
Reconfiguration,geometric algorithm,pivoting squares,modular robots
Discrete mathematics,Computer science,Theoretical computer science,Self-reconfiguring modular robot,Facet (geometry),Control reconfiguration
Conference
Volume
Issue
ISSN
144
5
1868-8969
Citations 
PageRank 
References 
0
0.34
0
Authors
11
Name
Order
Citations
PageRank
Hugo A. Akitaya1119.76
Esther M. Arkin21207158.07
Mirela Damian321228.18
erik d demaine421616.91
Vida Dujmovic541643.34
Vida Dujmovic641643.34
Robin Y. Flatland76313.23
Matias Korman817837.28
Belén Palop900.34
André van Renssen1034.74
Vera Sacristán11857.86