Document Open Access Logo

Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers

Authors Hugo A. Akitaya , Esther M. Arkin , Mirela Damian, Erik D. Demaine , Vida Dujmović, Robin Flatland, Matias Korman, Belen Palop, Irene Parada , André van Renssen , Vera Sacristán

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.3.pdf
  • Filesize: 1.3 MB
  • 14 pages

Document Identifiers

Author Details

Hugo A. Akitaya
  • Tufts University, Medford, MA, USA
Esther M. Arkin
  • State University of New York at Stony Brook, NY, USA
Mirela Damian
  • Villanova University, PA, USA
Erik D. Demaine
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Vida Dujmović
  • University of Ottawa, Canada
Robin Flatland
  • Siena College, Loudonville, NY, USA
Matias Korman
  • Tufts University, Medford, MA, USA
Belen Palop
  • Universidad de Valladolid, Spain
Irene Parada
  • Graz University of Technology, Austria
André van Renssen
  • The University of Sydney, Australia
Vera Sacristán
  • Universitat Politècnica de Catalunya, Barcelona, Spain

Funding

  • Akitaya, Hugo A.: Supported by NSF CCF-1422311 and CCF-1423615.
  • Arkin, Esther M.: Partially funded by NSF (CCF-1526406).
  • Demaine, Erik D.: Supported in part by NSF ODISSEI grant EFRI-1240383 and NSF Expedition grant CCF-1138967.
  • Palop, Belen: Partially supported by MTM2015-63791-R (MINECO/FEDER).
  • Parada, Irene: Supported by the Austrian Science Fund (FWF): W1230.
  • van Renssen, André: Supported by JST ERATO Grant Number JPMJER1201, Japan.
  • Sacristán, Vera: Partially supported by MTM2015-63791-R (MINECO/FEDER) and Gen. Cat. DGR 2017SGR1640.

Acknowledgements

This research started at the 32nd Bellairs Winter Workshop on Computational Geometry in 2017. We want to thank all participants for the fruitful discussions on the topic. We would also like to thank the reviewers for their insightful and valuable comments.

Cite AsGet BibTex

Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmović, 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.3

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Reconfiguration
  • geometric algorithm
  • pivoting squares
  • modular robots

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Z. Abel and S. D. Kominers. Pushing hypercubes around. CoRR, abs/0802.3414, 2008. URL: http://arxiv.org/abs/0802.3414.
  2. B. K. An. EM-Cube: cube-shaped, self-reconfigurable robots sliding on structure surfaces. In Proc. IEEE International Conference on Robotics and Automation (ICRA), pages 3149-3155, 2008. Google Scholar
  3. N. Ayanian, P. J. White, Á. Hálász, M. Yim, and V. Kumar. Stochastic control for self-assembly of XBots. In Proceedings of the ASME International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, 2008. Google Scholar
  4. N. M. Benbernou. Geometric algorithms for reconfigurable structures. PhD thesis, Massachusetts Institute of Technology, 2011. Google Scholar
  5. S. Chennareddy, A. Agrawal, and A. Karuppiah. Modular self-reconfigurable robotic systems: a survey on hardware architectures. Journal of Robotics, 2017(5013532), 2017. Google Scholar
  6. G. S. Chirikjian. Kinematics of a metamorphic robotic system. In Proc. IEEE International Conference on Robotics and Automation (ICRA), volume 1, pages 449-455, 1994. Google Scholar
  7. A. Dumitrescu and J. Pach. Pushing squares around. Graphs and Combinatorics, 22(1):37-50, 2006. Google Scholar
  8. R. Fitch, Z. Butler, and D. Rus. Reconfiguration planning for heterogeneous self-reconfiguring robots. In Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), volume 3, pages 2460-2467, 2003. Google Scholar
  9. A. Hemmerling. Labyrinth problems - labyrinth-searching abilities of automata, volume 14 of Teubner-Texte zur Mathematik (TTZM). Springer-Verlag, 1989. Google Scholar
  10. H. Kurokawa, S. Murata, E. Yoshida, K. Tomita, and S. Kokaji. A 3-D self-reconfigurable structure and experiments. In Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), volume 2, pages 860-865, 1998. Google Scholar
  11. T. Larkworthy and S. Ramamoorthy. A characterization of the reconfiguration space of self-reconfiguring robotic systems. Robotica, 29(1):73-85, 2011. Google Scholar
  12. O. Michail, G. Skretas, and P. G. Spirakis. On the transformation capability of feasible mechanisms for programmable matter. J. Comput. Syst. Sci., 102:18-39, 2019. Google Scholar
  13. S. Murata, H. Kurokawa, and S. Kokaji. Self-assembling machine. In Proc. IEEE International Conference on Robotics and Automation (ICRA), volume 1, pages 441-448, 1994. Google Scholar
  14. S. Murata, E. Yoshida, A. Kamimura, H. Kurokawa, K. Tomita, and S. Kokaji. M-TRAN: self-reconfigurable modular robotic system. IEEE/ASME Transactions on Mechatronics, 7(4):431-441, 2002. Google Scholar
  15. A. Nguyen, L. J. Guibas, and M. Yim. Controlled module density helps reconfiguration planning. In Algorithmic and Computational Robotics: New Dimensions (WAFR), pages 23-25. A. K. Peters, 2001. Google Scholar
  16. E. H. Østergaard, K. Kassow, R. Beck, and H. H. Lund. Design of the ATRON lattice-based self-reconfigurable robot. Autonomous Robots, 21(2):165-183, 2006. Google Scholar
  17. D. Rus and M. Vona. A physical implementation of the self-reconfiguring crystalline robot. In Proc. IEEE International Conference on Robotics and Automation (ICRA), volume 2, pages 1726-1733, 2000. Google Scholar
  18. B. Salemi, M. Moll, and W.-M. Shen. SUPERBOT: a deployable, multi-functional, and modular self-reconfigurable robotic system. In Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3636-3641, 2006. Google Scholar
  19. K. Stoy, D. Brandt, and D. J. Christensen. Self-reconfigurable robots: an introduction. MIT Press, 2010. Google Scholar
  20. C. Sung, J. Bern, J. Romanishin, and D. Rus. Reconfiguration planning for pivoting cube modular robots. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 1933-1940, 2015. Google Scholar
  21. C. Unsal, H. Kiliccote, and P. Khosla. I(CES)-Cubes: a modular self-reconfigurable bipartite robotic system. In Proc. SPIE Conference on Mobile Robots and Autonomous Systems, volume 3839, pages 258-269. SPIE, 1999. Google Scholar
  22. M. Yim, W. Shen, B. Salemi, D. Rus, M. Moll, H. Lipson, E. Klavins, and G. S. Chirikjian. Modular self-reconfigurable robot systems. IEEE Robotics & Automation Magazine, 14(1):43-52, 2007. Google Scholar
  23. V. Zykov, A. Chan, and H. Lipson. Molecubes: an open-source modular robotic kit. In IROS-2007 Self-Reconfigurable Robotics Workshop, 2007. Google Scholar
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