DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.1

A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves

Authors: Zachary Abel, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman, and Frederick Stock

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

In the modular robot reconfiguration problem, we are given n cube-shaped modules (or robots) as well as two configurations, i.e., placements of the n modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves," in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times. For many years it has been known that certain module configurations in this model require at least Ω(n²) moves to reconfigure between them. In this paper, we introduce the first universal reconfiguration algorithm - i.e., we show that any n-module configuration can reconfigure itself into any specified n-module configuration using just sliding moves. Our algorithm achieves reconfiguration in O(n²) moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration.

Cite as

Zachary Abel, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman, and Frederick Stock. A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.SoCG.2024.1,
  author =	{Abel, Zachary and A. Akitaya, Hugo and Kominers, Scott Duke and Korman, Matias and Stock, Frederick},
  title =	{{A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.1},
  URN =		{urn:nbn:de:0030-drops-199468},
  doi =		{10.4230/LIPIcs.SoCG.2024.1},
  annote =	{Keywords: modular reconfigurable robots, sliding cube model, reconfiguration}
}

Search Results

Documents authored by Stock, Frederick

A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves

Abstract

Cite as

Thanks for your feedback!

Could not send message