LIPIcs.SoCG.2020.78.pdf
- Filesize: 3.49 MB
- 5 pages
Document
Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)
Authors
Irene Parada 
,
Willem Sonke ,
Bettina Speckmann ,
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
File
Document Identifiers
Author Details
Acknowledgements
We thank Tim Ophelders for his help with the computational verification of the properties of our configuration.
Cite As Get BibTex
Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, and Jules Wulms. Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 78:1-78:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.78
Abstract
Face-connected configurations of cubes are a common model for modular robots in three dimensions. In this abstract and the accompanying video we study reconfigurations of such modular robots using so-called sliding moves. Using sliding moves, it is always possible to reconfigure one face-connected configuration of n cubes into any other, while keeping the robot connected at all stages of the reconfiguration. For certain configurations Ω(n²) sliding moves are necessary. In contrast, the best current upper bound is O(n³). It has been conjectured that there is always a cube on the outside of any face-connected configuration of cubes which can be moved without breaking connectivity. The existence of such a cube would immediately imply a straight-forward O(n²) reconfiguration algorithm. However, we present a configuration of cubes such that no cube on the outside can move without breaking connectivity. In other words, we show that this particular avenue towards an O(n²) reconfiguration algorithm for face-connected cubes is blocked.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Sliding cubes
- Reconfiguration
- Modular robots
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Zachary Abel and Scott Duke Kominers. Universal reconfiguration of (hyper-)cubic robots. ArXiv e-Prints, 2011. URL: http://arxiv.org/abs/0802.3414v3.
- Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Flatland, Matias Korman, Belen Palop, Irene Parada, André van Renssen, and Vera Sacristán. Universal reconfiguration of facet-connected modular robots by pivots: The O(1) Musketeers. In 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1-3:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.3.
- Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer. Efficient constant-velocity reconfiguration of crystalline robots. Robotica, 29(1):59-71, 2011. URL: https://doi.org/10.1017/S026357471000072X.
- Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer. Linear reconfiguration of cube-style modular robots. Computational Geometry, 42(6):652-663, 2009. URL: https://doi.org/10.1016/j.comgeo.2008.11.003.
- Adrian Dumitrescu and János Pach. Pushing squares around. Graphs and Combinatorics, 22:37-50, 2006. URL: https://doi.org/10.1007/s00373-005-0640-1.
- Robert Fitch, Zack Butler, and Daniela Rus. Reconfiguration planning for heterogeneous self-reconfiguring robots. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and System (IROS 2003), volume 3, pages 2460-2467, 2003. URL: https://doi.org/10.1109/IROS.2003.1249239.
- Ferran Hurtado, Enrique Molina, Suneeta Ramaswami, and Vera Sacristán. Distributed reconfiguration of 2D lattice-based modular robotic systems. Autonomous Robots, 38:383-413, 2015. URL: https://doi.org/10.1007/s10514-015-9421-8.
- Daniela Rus and Marsette Vona. Crystalline robots: self-reconfiguration with compressible unit modules. Autonomous Robots, 10:107-124, 2001. URL: https://doi.org/10.1023/A:1026504804984.