Document Open Access Logo

Characterizing Universal Reconfigurability of Modular Pivoting Robots

Authors Hugo A. Akitaya , Erik D. Demaine , Andrei Gonczi , Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch , Irene Parada , Vera Sacristán

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.10.pdf
  • Filesize: 1.43 MB
  • 20 pages

Document Identifiers

Author Details

Hugo A. Akitaya
  • University of Massachusetts Lowell, MA, USA
Erik D. Demaine
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Andrei Gonczi
  • Tufts University, Medford, MA, USA
Dylan H. Hendrickson
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Adam Hesterberg
  • Harvard University, Cambridge, MA, USA
Matias Korman
  • Siemens Electronic Design Automation, Portland, OR, USA
Oliver Korten
  • Columbia University, New York, NY, USA
Jayson Lynch
  • University of Waterloo, ON, Canada
Irene Parada
  • TU Eindhoven, The Netherlands
Vera Sacristán
  • Universitat Politècnica de Catalunya, Barcelona, Spain

Funding

  • Lynch, Jayson: Supported by NSERC.
  • Sacristán, Vera: Partially supported by MTM2015-63791-R (MINECO/FEDER) and Gen. Cat. DGR 2017SGR1640.

Acknowledgements

This research started at the 34th Bellairs Winter Workshop on Computational Geometry in 2019. We want to thank all participants for the fruitful discussions and a stimulating environment. We would also like to thank a SoCG reviewer for their many contributions that helped improve the presentation of the paper.

Cite AsGet BibTex

Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán. Characterizing Universal Reconfigurability of Modular Pivoting Robots. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.10

Abstract

We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using O(n³) monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN'18] that we consider of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • reconfiguration
  • geometric algorithm
  • PSPACE-hardness
  • pivoting hexagons
  • pivoting squares
  • modular robots

Metrics

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

Related Versions

References

  1. Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, and Vera Sacristán. Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers. Algorithmica, 83(5):1316-1351, 2021. URL: https://doi.org/10.1007/s00453-020-00784-6.
  2. Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán. Characterizing universal reconfigurability of modular pivoting robots. CoRR, abs/2012.07556, 2020. URL: http://arxiv.org/abs/2012.07556.
  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. Joshua Ani, Erik D. Demaine, Dylan H. Hendrickson, and Jayson Lynch. Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets. CoRR, abs/2005.03192, 2020. URL: http://arxiv.org/abs/2005.03192.
  5. Nora Ayanian, Paul J. White, Ádám Hálász, Mark Yim, and Vijay Kumar. Stochastic control for self-assembly of XBots. In Proc. ASME International Design Engineering Technical Conferences and Computers and Information in Engineering Conference (IDETC-CIE), pages 1169-1176, 2008. URL: https://doi.org/10.1115/DETC2008-49535.
  6. Jose Balanza-Martinez, Austin Luchsinger, David Caballero, Rene Reyes, Angel A Cantu, Robert Schweller, Luis Angel Garcia, and Tim Wylie. Full tilt: Universal constructors for general shapes with uniform external forces. In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2689-2708, 2019. Google Scholar
  7. Nadia M. Benbernou. Geometric Algorithms for Reconfigurable Structures. PhD thesis, Massachusetts Institute of Technology, 2011. Google Scholar
  8. David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie. Relocating units in robot swarms with uniform control signals is PSPACE-complete. In Proc. 32th Canadian Conference on Computational Geometry, 2020. Google Scholar
  9. Erik D. Demaine, Dylan H. Hendrickson, and Jayson Lynch. Toward a general complexity theory of motion planning: Characterizing which gadgets make games hard. In Proc. 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151, pages 62:1-62:42, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.62.
  10. Adrian Dumitrescu and János Pach. Pushing squares around. Graphs and Combinatorics, 22(1):37-50, 2006. URL: https://doi.org/10.1007/s00373-005-0640-1.
  11. Adrian Dumitrescu, Ichiro Suzuki, and Masafumi Yamashita. Motion planning for metamorphic systems: feasibility, decidability, and distributed reconfiguration. IEEE Transactions on Robotics, 20(3):409-418, 2004. URL: https://doi.org/10.1109/TRA.2004.824936.
  12. Robert Fitch, Zack Butler, and Daniela Rus. Reconfiguration planning for heterogeneous self-reconfiguring robots. In Proc. 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), volume 3, pages 2460-2467, 2003. URL: https://doi.org/10.1109/IROS.2003.1249239.
  13. Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, and Jules Wulms. Compacting squares. Manuscript, 2020. Google Scholar
  14. Tom Larkworthy and Subramanian Ramamoorthy. A characterization of the reconfiguration space of self-reconfiguring robotic systems. Robotica, 29(1):73-85, 2011. URL: https://doi.org/10.1017/S0263574710000718.
  15. An Nguyen, Leonidas J. Guibas, and Mark Yim. Controlled module density helps reconfiguration planning. In Algorithmic and Computational Robotics: New Dimensions (2000 WAFR), pages 23-36. A. K. Peters, 2001. Google Scholar
  16. Cynthia Sung, James Bern, John Romanishin, and Daniela Rus. Reconfiguration planning for pivoting cube modular robots. In Proc. 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 1933-1940, 2015. URL: https://doi.org/10.1109/ICRA.2015.7139451.
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