Abstract
In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2 ×2 ×2 meta-modules. The reconfiguration involves a total of O(n) atom operations (expand, contract, attach, detach) and is performed in O(n) parallel steps. This improves on previous reconfiguration algorithms [1,2,3], which require O(n 2) parallel steps. Our algorithm is in place; that is, the reconfiguration takes place within the union of the bounding boxes of the source and target robots. We show that the algorithm can also be implemented in a synchronous, distributed fashion.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rus, D., Vona, M.: Crystalline robots: Self-reconfiguration with compressible unit modules. Autonomous Robots 10(1), 107–124 (2001)
Vassilvitskii, S., Suh, Y.M.: A complete, local and parallel reconfiguration algorithm for cube style modular robots. In: Proc. of the IEEE Intl. Conf. on Robotics and Automation, pp. 117–122 (2002)
Butler, Z., Rus, D.: Distributed planning and control for modular robots with unit-compressible modules. The Intl. Journal of Robotics Research 22(9), 699–715 (2003)
Butler, Z., Fitch, R., Rus, D.: Distributed control for unit-compressible robots: Goal-recognition, locomotion and splitting. IEEE/ASME Trans. on Mechatronics 7(4), 418–430 (2002)
Suh, J.W., Homans, S.B., Yim, M.: Telecubes: Mechanical design of a module for self-reconfigurable robotics. In: Proc. of the IEEE Intl. Conf. on Robotics and Automation, pp. 4095–4101 (2002)
Hackl, T.: Personal communication (2007)
Aloupis, G., Collette, S., Damian, M., Demaine, E.D., Flatland, R., Langerman, S., O’Rourke, J., Ramaswami, S., Sacristán, V., Wuhrer, S.: Linear reconfiguration of cube-style modular robots (2007), www.cs.siena.edu/papers/cbots_long.pdf
Arkin, E., Bender, M., Mitchell, J., Polishchuk, V.: The snowblower problem. In: Proc. 7th Intl. Workshop on the Algorithmic Foundations of Robotics (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aloupis, G. et al. (2007). Linear Reconfiguration of Cube-Style Modular Robots. In: Tokuyama, T. (eds) Algorithms and Computation. ISAAC 2007. Lecture Notes in Computer Science, vol 4835. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77120-3_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-77120-3_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77118-0
Online ISBN: 978-3-540-77120-3
eBook Packages: Computer ScienceComputer Science (R0)