Efficient constant-velocity reconfiguration of crystalline robots** - Aloupis, Greg; Collette, S bastien; Damian, Mirela; Demaine, Erik D.; Flatland, Robin; Langerman, Stefan; O'Rourke, Joseph; Pinciu, Val; Ramaswami, Suneeta; Sacrist, Vera; Wuhrer, Stefanie (Robotica, 2011)
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 × 2 × 2 modules. We respect certain physical constraints: each atom reaches at most constant velocity and can displace at most a constant number of other atoms. We assume that one of the atoms has access to the coordinates of atoms in the target configuration. Our algorithms involve a total of O(n2) atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n2) parallel steps or do not respect the constraints mentioned above. In fact, in the settings considered, our algorithms are optimal. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configuration space, and only requires local communication. © 2011 Cambridge University Press.
7 citations (Crossref) [2023-10-31] Citation Key Alias: pop00108 tex.type: [object Object]
Keywords: Algorithms; Atoms; Constant velocities; Control of robotic systems; Local communications; Mobile robots; Modular robots; Motion planning; Novel algorithm; Path planning; Physical constraints; Reconfiguration algorithm; Robot programming; Robotic systems; Robotics; Target configurations; dept.mat

Realistic reconfiguration of crystalline (and telecube) robots - Aloupis, Greg; Collette, Sebastien; Damian, Mirela; Demaine, Erik D; Elkhechen, Dania; Flatland, Robin; Langerman, Stefan; Orourke, Joseph; Pinciu, Val; Ramaswami, Suneeta; Sacristan, Vera; Wuhrer, Stefanie (International Workshop Algorithmic Foundations Robotics, 2009)
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×2×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 configuration. Our algorithms involve a total of O(n 2) such atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n 2) parallel steps [8,10,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. © 2009 Springer-Verlag.
5 citations (Crossref) [2023-10-31] tex.type: Proceedings paper
Keywords: Algorithms; Atoms; Novel algorithm; Physical constraints; Reconfiguration algorithm; Robotics; Robots; Target configurations; dept.mat