Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers
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 t...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl, Leibniz Center for Informatics
2020
|
| Online Access: | https://hdl.handle.net/1721.1/128812 |
| _version_ | 1826211397494636544 |
|---|---|
| author | Demaine, Erik D |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | 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(n2) 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. |
| first_indexed | 2024-09-23T15:05:15Z |
| format | Article |
| id | mit-1721.1/128812 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:05:15Z |
| publishDate | 2020 |
| publisher | Schloss Dagstuhl, Leibniz Center for Informatics |
| record_format | dspace |
| spelling | mit-1721.1/1288122022-09-29T12:37:39Z Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers Demaine, Erik D Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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(n2) 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. National Science Foundation (U.S.). Origami Design for Integration of Self-assembling Systems for Engineering Innovation (Grant EFRI-1240383) National Science Foundation (U.S.) ( Expedition Grant CCF-1138967) 2020-12-11T14:43:12Z 2020-12-11T14:43:12Z 2019-09 2020-12-09T16:35:46Z Article http://purl.org/eprint/type/ConferencePaper 1868-8969 https://hdl.handle.net/1721.1/128812 Akitaya, Hugo A. et al. “Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers.” Leibniz International Proceedings in Informatics, LIPIcs, 144, 3 (September 2019): 1-14 © 2019 The Author(s) en 10.4230/LIPIcs.ESA.2019.3 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 3.0 unported license https://creativecommons.org/licenses/by/3.0/ application/pdf Schloss Dagstuhl, Leibniz Center for Informatics DROPS |
| spellingShingle | Demaine, Erik D Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers |
| title | Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers |
| title_full | Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers |
| title_fullStr | Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers |
| title_full_unstemmed | Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers |
| title_short | Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers |
| title_sort | universal reconfiguration of facet connected modular robots by pivots the o 1 musketeers |
| url | https://hdl.handle.net/1721.1/128812 |
| work_keys_str_mv | AT demaineerikd universalreconfigurationoffacetconnectedmodularrobotsbypivotstheo1musketeers |