文章基本信息
- 标题：Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)
- 本地全文：下载
- 作者：Tillmann Miltzow ; Irene Parada ; Willem Sonke 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：164
- 页码：78:1-78:5
- DOI：10.4230/LIPIcs.SoCG.2020.78
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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.
- 关键词：Sliding cubes; Reconfiguration; Modular robots
