Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)

Miltzow, Tillmann; Parada, Irene; Sonke, Willem; Speckmann, Bettina; Wulms, Jules

doi: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.

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

Author Details

Tillmann Miltzow

Utrecht University, The Netherlands

Irene Parada

TU Eindhoven, The Netherlands

Willem Sonke

TU Eindhoven, The Netherlands

Bettina Speckmann

TU Eindhoven, The Netherlands

Jules Wulms

TU Eindhoven, The Netherlands

Funding

This work was initiated at the 5th Workshop on Applied Geometric Algorithms (AGA 2020).

Miltzow, Tillmann: Supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250.
Speckmann, Bettina: Partially supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.023.208.
Wulms, Jules: Supported by the Netherlands eScience Center (NLeSC) under project no. 027.015.G02.

Acknowledgements

We thank Tim Ophelders for his help with the computational verification of the properties of our configuration.

Supplementary Materials

The code used, along with a list of coordinates of the cubes in the construction, can be found at https://github.com/tue-aga/cubes-checker.

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.

Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)

Authors Tillmann Miltzow, Irene Parada , Willem Sonke , Bettina Speckmann , Jules Wulms

File

Document Identifiers

Subject Classification

ACM Subject Classification

Keywords

Metrics

Abstract

Cite As Get BibTex

Author Details

Acknowledgements

References

Thanks for your feedback!

Could not send message