Hiding Sliding Cubes - Why Reconfiguring Modular Robots Is Not Easy

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 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.

Original languageEnglish
Title of host publication36th International Symposium on Computational Geometry (SoCG 2020)
EditorsSergio Cabello, Danny Z. Chen
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages78:1-78:5
ISBN (Electronic)9783959771436
DOIs
Publication statusPublished - 8 Jun 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume164
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

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