Publications
Publications
- 2024
- Proceedings of the International Symposium on Computational Geometry (SoCG)
A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in Quadratic Time
By: Zachary Abel, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman and Frederick Stock
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 Omega(n^2) 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^2) 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 each configuration.
For many years it has been known that certain module configurations in this model require at least Omega(n^2) 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^2) 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 each configuration.
Keywords
Citation
Abel, Zachary, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman, and Frederick Stock. "A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in Quadratic Time." Proceedings of the International Symposium on Computational Geometry (SoCG) 40th (2024): 1:1–1:14.