Abstract
The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. As is common in the literature, we focus on reconfiguration via an intermediate canonical shape. Specifically, we present an in-place algorithm that reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. This result is asymptotically optimal and strictly improves on all prior work. Furthermore, our algorithm directly extends to dimensions higher than three.
| Original language | English |
|---|---|
| Title of host publication | 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024 |
| Editors | Hans L. Bodlaender |
| Publisher | Dagstuhl Publishing |
| Number of pages | 14 |
| ISBN (Electronic) | 9783959773188 |
| DOIs | |
| Publication status | Published - Jun 2024 |
| Event | 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024 - Helsinki, Finland Duration: 12 Jun 2024 → 14 Jun 2024 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 294 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024 |
|---|---|
| Country/Territory | Finland |
| City | Helsinki |
| Period | 12/06/24 → 14/06/24 |
Bibliographical note
Publisher Copyright:© Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann; licensed under Creative Commons License CC-BY 4.0.
Keywords
- Modular robots
- Reconfiguration algorithm
- Sliding cubes