A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2008
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910366127095808 |
|---|---|
| author | Abel, Zachary Akitaya, Hugo A. Kominers, Scott Duke Korman, Matias Stock, Frederick |
| author_facet | Abel, Zachary Akitaya, Hugo A. Kominers, Scott Duke Korman, Matias Stock, Frederick |
| contents | 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^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 the start and end configuration. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_0802_3414 |
| institution | arXiv |
| publishDate | 2008 |
| record_format | arxiv |
| spellingShingle | A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves Abel, Zachary Akitaya, Hugo A. Kominers, Scott Duke Korman, Matias Stock, Frederick Computational Geometry Multiagent Systems Robotics 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^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 the start and end configuration. |
| title | A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves |
| topic | Computational Geometry Multiagent Systems Robotics |
| url | https://arxiv.org/abs/0802.3414 |