Document Open Access Logo

Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares

Authors Hugo A. Akitaya , Erik D. Demaine , Matias Korman, Irina Kostitsyna , Irene Parada , Willem Sonke , Bettina Speckmann , Ryuhei Uehara , Jules Wulms

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.4.pdf
  • Filesize: 1.57 MB
  • 19 pages

Document Identifiers

Author Details

Hugo A. Akitaya
  • University of Massachusetts Lowell, MA, USA
Erik D. Demaine
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Matias Korman
  • Siemens Electronic Design Automation, Wilsonville, OR, USA
Irina Kostitsyna
  • Eindhoven University of Technology, The Netherlands
Irene Parada
  • Technical University of Denmark, Lyngby, Denmark
Willem Sonke
  • Eindhoven University of Technology, The Netherlands
Bettina Speckmann
  • Eindhoven University of Technology, The Netherlands
Ryuhei Uehara
  • Japan Advanced Institute of Science and Technology, Ishikawa, Japan
Jules Wulms
  • Technische Universität Wien, Austria

Funding

Irene Parada was supported by Independent Research Fund Denmark grant 2020-2023 (9131-00044B) "Dynamic Network Analysis" and Jules Wulms was supported partially by the Austrian Science Fund (FWF) under grant P31119 and partially by the Vienna Science and Technology Fund (WWTF) under grant ICT19-035.

Acknowledgements

Parts of this work were initiated at the 5th Workshop on Applied Geometric Algorithms (AGA 2020) and at the 2nd Virtual Workshop on Computational Geometry. We thank all participants for discussions and an inspiring and productive atmosphere. We thank Fabian Klute for discussions on the computational experiments.

Cite As Get BibTex

Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms. Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SWAT.2022.4

Abstract

Edge-connected configurations of square modules, which can reconfigure through so-called sliding moves, are a well-established theoretical model for modular robots in two dimensions. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it is always possible to reconfigure one edge-connected configuration of n squares into any other using at most O(n²) sliding moves, while keeping the configuration connected at all times.
For certain pairs of configurations, reconfiguration may require Ω(n²) sliding moves. However, significantly fewer moves may be sufficient. We prove that it is NP-hard to minimize the number of sliding moves for a given pair of edge-connected configurations. On the positive side we present Gather&Compact, an input-sensitive in-place algorithm that requires only O( ̄P n) sliding moves to transform one configuration into the other, where  ̄P is the maximum perimeter of the two bounding boxes. The squares move within the bounding boxes only, with the exception of at most one square at a time which may move through the positions adjacent to the bounding boxes. The O( ̄P n) bound never exceeds O(n²), and is optimal (up to constant factors) among all bounds parameterized by just n and  ̄P. Our algorithm is built on the basic principle that well-connected components of modular robots can be transformed efficiently. Hence we iteratively increase the connectivity within a configuration, to finally arrive at a single solid xy-monotone component. 
We implemented Gather&Compact and compared it experimentally to the in-place modification by Moreno and Sacristán [EuroCG 2020] of the Dumitrescu and Pach algorithm (MSDP). Our experiments show that Gather&Compact consistently outperforms MSDP by a significant margin, on all types of square configurations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Sliding cubes
  • Reconfiguration
  • Modular robots
  • NP-hardness

Metrics

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

Related Versions

Supplementary Materials

References

  1. Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmović, Robin 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. In Proc. 37th International Symposium on Computational Geometry (SoCG), pages 10:1-10:20, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.10.
  3. Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms. Compacting squares: Input-sensitive in-place reconfiguration of sliding squares. CoRR, abs/2105.07997, 2021. URL: http://arxiv.org/abs/2105.07997.
  4. Greg Aloupis, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Robin Flatland, John Iacono, and Stefanie Wuhrer. Efficient reconfiguration of lattice-based modular robots. Computational Geometry: Theory and Applications, 46(8):917-928, 2013. URL: https://doi.org/10.1016/j.comgeo.2013.03.004.
  5. 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.
  6. Byoung Kwon An. EM-Cube: Cube-shaped, self-reconfigurable robots sliding on structure surfaces. In Proc. 2008 IEEE International Conference on Robotics and Automation (ICRA), pages 3149-3155, 2008. URL: https://doi.org/10.1109/ROBOT.2008.4543690.
  7. 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.
  8. Nadia M. Benbernou. Geometric algorithms for reconfigurable structures. PhD thesis, Massachusetts Institute of Technology, 2011. Google Scholar
  9. Chih-Jung Chiang and Gregory S. Chirikjian. Modular robot motion planning using similarity metrics. Autonomous Robots, 10:91-106, 2001. URL: https://doi.org/10.1023/A:1026552720914.
  10. 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.
  11. 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 System, pages 2460-2467, 2003. URL: https://doi.org/10.1109/IROS.2003.1249239.
  12. Kazuo Hosokawa, Takehito Tsujimori, Teruo Fujii, Hayato Kaetsu, Hajime Asama, Yoji Kuroda, and Isao Endo. Self-organizing collective robots with morphogenesis in a vertical plane. In Proc. 1998 IEEE International Conference on Robotics and Automation (ICRA), pages 2858-2863, 1998. URL: https://doi.org/10.1109/ROBOT.1998.680616.
  13. Othon Michail, George Skretas, and Paul G. Spirakis. On the transformation capability of feasible mechanisms for programmable matter. Journal of Computer and System Sciences, 102:18-39, 2019. URL: https://doi.org/10.1016/j.jcss.2018.12.001.
  14. Joel Moreno. In-place reconfiguration of lattice-based modular robots. Bachelor’s thesis, Universitat Politècnica de Catalunya, 2019. Google Scholar
  15. Joel Moreno and Vera Sacristán. Reconfiguring sliding squares in-place by flooding. In Proc. 36th European Workshop on Computational Geometry (EuroCG), pages 32:1-32:7, 2020. Google Scholar
  16. Irene Parada, Vera Sacristán, and Rodrigo I. Silveira. A new meta-module design for efficient reconfiguration of modular robots. Autonomous Robots, 45(4):457-472, 2021. URL: https://doi.org/10.1007/s10514-021-09977-6.
  17. Daniela Rus and Marsette Vona. A physical implementation of the self-reconfiguring crystalline robot. In Proc. 2000 IEEE International Conference on Robotics and Automation (ICRA), pages 1726-1733, 2000. URL: https://doi.org/10.1109/ROBOT.2000.844845.
  18. John W. Suh, Samuel B. Homans, and Mark Yim. Telecubes: mechanical design of a module for self-reconfigurable robotics. In Proc. 2002 IEEE International Conference on Robotics and Automation (ICRA), pages 4095-4101, 2002. URL: https://doi.org/10.1109/ROBOT.2002.1014385.
  19. 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.
  20. Mark Yim, Wei-Min Shen, Behnam Salemi, Daniela Rus, Mark Moll, Hod Lipson, Eric Klavins, and Gregory S. Chirikjian. Modular self-reconfigurable robot systems. IEEE Robotics & Automation Magazine, 14(1):43-52, 2007. URL: https://doi.org/10.1109/MRA.2007.339623.
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 About DROPS Imprint Privacy Contact