Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/9774

Realistic reconfiguration of crystalline (and telecube) robots
Wuhrer, Stefanie; Sacristán Adinolfi, Vera; Ramaswami, Suneeta; Pinciu, Val; Aloupis, Greg; Collette, Sébastien; Damian, Mirela; Demaine, Erik D.; El-Khechen, Dania; Flatland, Robin; Langerman, Stefan; O'Rourke, Joseph
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
In this paper we propose novel algorithms for reconfiguring modular robots that are composed of n atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2 x 2 x 2 modules. We respect certain physical constraints: each atom reaches at most unit velocity and (via expansion) can displace at most one other atom. We require that one of the atoms can store a map of the target con guration. Our algorithms involve a total of O(n²) such atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n²) parallel steps [7, 9, 4] or do not respect the constraints mentioned above [1]. In fact, in the setting considered, our algorithms are optimal, in the sense that certain reconfigurations require Ω(n) parallel steps. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configurations.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional
Algorithms
Atoms
Robotics
Computational geometry
Algorismes
Àtoms
Robòtica
Geometria computacional
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/conferenceObject
CIMAT
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Aloupis, Greg; Collette, Sébastien; Demaine, Erik D.; Langerman, Stefan; Sacristán Adinolfi, Vera; Wuhrer, Stefanie
Wuhrer, S.; Sacristán Adinolfi, Vera; Ramaswami, Suneeta; Pinciu, Val; Aloupis, G.; Collette, S.; Damian, M.; Demaine, E. D.; El-Khechen, Dania; Flatland, R.; Langerman, S.; O'Rourke, J.
Taslakian, Perouz; Seara Ojea, Carlos; Saumell Mendiola, Maria; Langerman, Stefan; Hurtado Díaz, Fernando Alfredo; Aloupis, Greg; Cardinal, Jean; Collette, Sébastien; Demaine, Erik D.; Demaine, Martin L.; Dulieu, Muriel; Fabila Monroy, Ruy; Hart, Vi
Bose, Prosenjit; Collette, Sébastien; Hurtado Díaz, Fernando Alfredo; Korman, Matias; Langerman, Stefan; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
Wood, David; Por, Attila; Abel, Zachary; Ballinger, Brad; Bose, Prosenjit; Collette, Sébastien; Dujmovic, Vida; Hurtado Díaz, Fernando Alfredo; Kominers, Scott Duke; Langerman, Stefan