License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.78
URN: urn:nbn:de:0030-drops-122363
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12236/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-SoCG-2020-78.pdf (3 MB)

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.

BibTeX - Entry

@InProceedings{miltzow_et_al:LIPIcs:2020:12236,
  author =	{Tillmann Miltzow and Irene Parada and Willem Sonke and Bettina Speckmann and Jules Wulms},
  title =	{{Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{78:1--78:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12236},
  URN =		{urn:nbn:de:0030-drops-122363},
  doi =		{10.4230/LIPIcs.SoCG.2020.78},
  annote =	{Keywords: Sliding cubes, Reconfiguration, Modular robots}
}

Keywords: Sliding cubes, Reconfiguration, Modular robots
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020
Supplementary Material: The code used, along with a list of coordinates of the cubes in the construction, can be found at https://github.com/tue-aga/cubes-checker.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI