×

zbMATH — the first resource for mathematics

Universal reconfiguration of facet-connected modular robots by pivots: the \(O(1)\) musketeers. (English) Zbl 07335024
Summary: We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra “helper” modules (“musketeers”) suffice to reconfigure the remaining \(n\) modules between any two given configurations. Our algorithm uses \(O(n^2)\) pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive “sliding” moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.
MSC:
68Wxx Algorithms in computer science
05Cxx Graph theory
PDF BibTeX Cite
Full Text: DOI
References:
[1] Abel, Z., Kominers, S.D.: Pushing hypercubes around. CoRR abs/0802.3414 (2008)
[2] An, B.K.: EM-Cube: cube-shaped, self-reconfigurable robots sliding on structure surfaces. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), pp. 3149-3155 (2008)
[3] Ayanian, N., White, P.J., Hálász, Á., Yim, M., Kumar, V.: Stochastic control for self-assembly of XBots. In: Proceedings of ASME International Design Engineering Technical Conferences and Computers and Information in Engineering Conference (IDETC-CIE) (2008)
[4] Benbernou, N.M.: Geometric algorithms for reconfigurable structures. Ph.D. Thesis, Massachusetts Institute of Technology (2011)
[5] Chennareddy, S.; Agrawal, A.; Karuppiah, A., Modular self-reconfigurable robotic systems: a survey on hardware architectures, J. Robot., 2017, 5013532 (2017)
[6] Chirikjian, G.S.: Kinematics of a metamorphic robotic system. In: Proceedings of IEEE international conference on robotics and automation (ICRA), vol. 1, pp. 449-455 (1994)
[7] Dumitrescu, A.; Pach, J., Pushing squares around, Graphs Comb., 22, 1, 37-50 (2006) · Zbl 1092.68715
[8] Dumitrescu, A.; Suzuki, I.; Yamashita, M., Motion planning for metamorphic systems: feasibility, decidability, and distributed reconfiguration, IEEE Trans. Robot., 20, 3, 409-418 (2004)
[9] Fitch, R., Butler, Z., Rus, D.: Reconfiguration planning for heterogeneous self-reconfiguring robots. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), vol. 3, pp. 2460-2467 (2003)
[10] Hemmerling, A., Labyrinth Problems: Labyrinth-Searching Abilities of Automata, Teubner-Texte zur Mathematik (TTZM) (1989), Berlin: Springer, Berlin · Zbl 0702.68055
[11] Kurokawa, H., Murata, S., Yoshida, E., Tomita, K., Kokaji, S.: A 3-D self-reconfigurable structure and experiments. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), vol. 2, pp. 860-865 (1998)
[12] Larkworthy, T.; Ramamoorthy, S., A characterization of the reconfiguration space of self-reconfiguring robotic systems, Robotica, 29, 1, 73-85 (2011)
[13] Michail, O.; Skretas, G.; Spirakis, PG, On the transformation capability of feasible mechanisms for programmable matter, J. Comput. Syst. Sci., 102, 18-39 (2019) · Zbl 1421.68158
[14] Murata, S., Kurokawa, H., Kokaji, S.: Self-assembling machine. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), vol. 1, pp. 441-448 (1994)
[15] Murata, S.; Yoshida, E.; Kamimura, A.; Kurokawa, H.; Tomita, K.; Kokaji, S., M-TRAN: self-reconfigurable modular robotic system, IEEE/ASME Trans. Mechatron., 7, 4, 431-441 (2002)
[16] Nguyen, A., Guibas, L.J., Yim, M.: Controlled module density helps reconfiguration planning. In: Proceedings of 4th International Workshop on Algorithmic Foundations of Robotics (WAFR), pp. 23-36 (2000) · Zbl 0986.68148
[17] Østergaard, EH; Kassow, K.; Beck, R.; Lund, HH, Design of the ATRON lattice-based self-reconfigurable robot, Auton. Robots, 21, 2, 165-183 (2006)
[18] Rus, D., Vona, M.: A physical implementation of the self-reconfiguring crystalline robot. In: Proceedings of IEEE International Conference on Robotics and Automation (ICRA), vol. 2, pp. 1726-1733 (2000)
[19] Salemi, B., Moll, M., Shen, W.M.: SUPERBOT: a deployable, multi-functional, and modular self-reconfigurable robotic system. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3636-3641 (2006)
[20] Stoy, K.; Brandt, D.; Christensen, DJ, Self-Reconfigurable Robots: An Introduction (2010), Cambridge: MIT Press, Cambridge
[21] Sung, C., Bern, J., Romanishin, J., Rus, D.: Reconfiguration planning for pivoting cube modular robots. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 1933-1940 (2015)
[22] Unsal, C., Kiliccote, H., Khosla, P.: I(CES)-Cubes: a modular self-reconfigurable bipartite robotic system. In: Proceedings of SPIE Conference on Mobile Robots and Autonomous Systems, vol. 3839, pp. 258-269 (1999)
[23] Yim, M.; Shen, W.; Salemi, B.; Rus, D.; Moll, M.; Lipson, H.; Klavins, E.; Chirikjian, GS, Modular self-reconfigurable robot systems, IEEE Robot. Autom. Mag., 14, 1, 43-52 (2007)
[24] Zykov, V., Chan, A., Lipson, H.: Molecubes: an open-source modular robotic kit. In: IROS-2007 Self-Reconfigurable Robotics Workshop (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.