Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy

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

doi:10.4230/LIPICS.SOCG.2020.78

Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	36th International Symposium on Computational Geometry (SoCG 2020)
Editors	Sergio Cabello, Danny Z. Chen
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	78:1-78:5
ISBN (Electronic)	9783959771436
DOIs	https://doi.org/10.4230/LIPICS.SOCG.2020.78
Publication status	Published - 8 Jun 2020

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	164
ISSN (Print)	1868-8969

Bibliographical note

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

Keywords

Modular robots
Reconfiguration
Sliding cubes

Access to Document

10.4230/LIPICS.SOCG.2020.78Licence: CC BY

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy'. Together they form a unique fingerprint.

Cite this

Miltzow, T., Parada, I., Sonke, W., Speckmann, B., & Wulms, J. (2020). Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy. In S. Cabello, & D. Z. Chen (Eds.), 36th International Symposium on Computational Geometry (SoCG 2020) (pp. 78:1-78:5). [LIPIcs-SoCG-2020-78] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 164). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2020.78

Miltzow, Tillmann ; Parada, Irene ; Sonke, Willem ; Speckmann, Bettina ; Wulms, Jules. / Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy. 36th International Symposium on Computational Geometry (SoCG 2020). editor / Sergio Cabello ; Danny Z. Chen. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. pp. 78:1-78:5 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{144e1b597d104143ae8acc611f3cfa9d,

title = "Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy",

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 2) sliding moves are necessary. In contrast, the best current upper bound is O(n 3). 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 2) 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 2) reconfiguration algorithm for face-connected cubes is blocked. ",

keywords = "Modular robots, Reconfiguration, Sliding cubes",

author = "Tillmann Miltzow and Irene Parada and Willem Sonke and Bettina Speckmann and Jules Wulms",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2020",

month = jun,

day = "8",

doi = "10.4230/LIPICS.SOCG.2020.78",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "78:1--78:5",

editor = "Sergio Cabello and Chen, {Danny Z.}",

booktitle = "36th International Symposium on Computational Geometry (SoCG 2020)",

}

Miltzow, T, Parada, I , Sonke, W , Speckmann, B & Wulms, J 2020, Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy. in S Cabello & DZ Chen (eds), 36th International Symposium on Computational Geometry (SoCG 2020)., LIPIcs-SoCG-2020-78, Leibniz International Proceedings in Informatics, LIPIcs, vol. 164, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 78:1-78:5. https://doi.org/10.4230/LIPICS.SOCG.2020.78

Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy. / Miltzow, Tillmann; Parada, Irene ; Sonke, Willem ; Speckmann, Bettina ; Wulms, Jules.

36th International Symposium on Computational Geometry (SoCG 2020). ed. / Sergio Cabello; Danny Z. Chen. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. p. 78:1-78:5 LIPIcs-SoCG-2020-78 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 164).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy

AU - Miltzow, Tillmann

AU - Parada, Irene

AU - Sonke, Willem

AU - Speckmann, Bettina

AU - Wulms, Jules

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2020/6/8

Y1 - 2020/6/8

N2 - 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 2) sliding moves are necessary. In contrast, the best current upper bound is O(n 3). 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 2) 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 2) reconfiguration algorithm for face-connected cubes is blocked.

AB - 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 2) sliding moves are necessary. In contrast, the best current upper bound is O(n 3). 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 2) 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 2) reconfiguration algorithm for face-connected cubes is blocked.

KW - Modular robots

KW - Reconfiguration

KW - Sliding cubes

UR - http://www.scopus.com/inward/record.url?scp=85086501576&partnerID=8YFLogxK

U2 - 10.4230/LIPICS.SOCG.2020.78

DO - 10.4230/LIPICS.SOCG.2020.78

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 78:1-78:5

BT - 36th International Symposium on Computational Geometry (SoCG 2020)

A2 - Cabello, Sergio

A2 - Chen, Danny Z.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

ER -

Miltzow T, Parada I , Sonke W , Speckmann B , Wulms J. Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy. In Cabello S, Chen DZ, editors, 36th International Symposium on Computational Geometry (SoCG 2020). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2020. p. 78:1-78:5. LIPIcs-SoCG-2020-78. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPICS.SOCG.2020.78