iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.4230/LIPIcs.SoCG.2020.78
Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)
Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.78.pdf
  • Filesize: 3.49 MB
  • 5 pages

Document Identifiers

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.

Cite AsGet 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)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Zachary Abel and Scott Duke Kominers. Universal reconfiguration of (hyper-)cubic robots. ArXiv e-Prints, 2011. URL: http://arxiv.org/abs/0802.3414v3.
  2. 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.
  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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact