×

zbMATH — the first resource for mathematics

Distributed reconfiguration of metamorphic robot chains. (English) Zbl 1448.68436
Summary: The problem we address is the distributed reconfiguration of a planar metamorphic robotic system composed of any number of hexagonal modules. After presenting a framework for classifying motion planning algorithms for metamorphic robotic systems, we describe distributed algorithms for reconfiguring a straight chain of hexagonal modules to any intersecting straight chain configuration. We prove our algorithms are correct, and show that they are either optimal or asymptotically optimal in the number of moves and asymptotically optimal in the time required for parallel reconfiguration.
MSC:
68T40 Artificial intelligence for robotics
68W15 Distributed algorithms
Software:
M-TRAN
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bojinov H, Casal A, Hoag T: Emergent structures in modular self-reconfigurable robots. In: Proc. of IEEE Intl. Conf. on Robotics and Automation, vol. 2, pp 1734-1741 (2000)
[2] Bojinov H, Casal A, Hoag T: Multiagent control of self-reconfigurable robots. In: Proc. of Fourth Intl. Conf. on Multiagent Systems, pp 143-150 (2000)
[3] Butler Z, Byrnes S, Rus D: Distributed motion planning for modular robots with unit-compressible modules. In: Proc. of IEEE Intl. Conf. on Intelligent Robots and Systems, pp 790-796 (2001)
[4] Casal A, Yim M: Self-reconfiguration planning for a class of modular robots. In: Proc. of SPIE Symposium on Intelligent Systems and Advanced Manufacturing, vol. 3839, pp 246-256 (1999)
[5] Castano A, Shen W-M, Will P: CONRO: Towards miniature self-sufficient metamorphic robots. Autonomous Robots Journal 8: 309-324 (2000)
[6] Chiang C-J, Chirikjian G: Similarity metrics with applications to modular robot motion planning. Autonomous Robots Journal, special issue on self-reconfiguring robots, 10(1): 91-106 (2001) · Zbl 1030.68622
[7] Chirikjian G: Kinematics of a metamorphic robotic system. In: Proc. of IEEE Intl. Conf. on Robotics and Automation, pp 449-455 (1994)
[8] Chirikjian G, Pamecha, A: Bounds for self-reconfiguration of metamorphic robots. Proc. IEEE International Conference on Robotics and Automation, pp 1452-1457 (1996)
[9] Chirikjian G: Metamorphic hyper-redundant manipulators. In: Proc. of Intl. Conf. on Advanced Mechatronics, pp 467-472 (1993)
[10] Chirikjian G, Pamecha A, Ebert-Uphoff I: Evaluating efficiency of self-reconfiguration in a class of modular robots. Journal of Robotic Systems 13(5): 317-338 (1996) · Zbl 0881.68137
[11] Dumitrescu A, Suzuki I, Yamashita M: High speed formations of reconfigurable modular robotic systems. Proc. IEEE International Conference on Robotics and Automation, pp 123-128 (2002)
[12] Fukuda T, Buss M, Hosokai H, Kawauchi Y: Cell structured robotic system CEBOT (control, planning and communication methods). Intelligent Autonomous Systems 2: 661-671 (1989)
[13] Hamlin GJ, Sanderson AC: Tetrobot: A modular approach to reconfigurable parallel robotics. Kluwer Academic Publishers, Newton, MA (1997) · Zbl 0912.70001
[14] Hosokawa K, Tsujimori T, Fujii T, Kaetsu H, Asama H, Kuroda Y, Endo I: Self-organizing collective robots with morphogenesis in a vertical plane. In: IEEE Intl. Conf. on Robotics and Automation, pp 2858-2863 (1998)
[15] Kotay K, Rus D: Scalable parallel algorithm for configuration planning for self-reconfigurable robots. In: Proc. of the Conf. on Sensor Fusion and Decentralized Control in Robotic Systems III, (SPIE RB06) (2000)
[16] Lee WH, Sanderson AC: Dynamic analysis and distributed control of the tetrobot modular reconfigurable robot system. Autonomous Robots Journal, special issue on self-reconfiguring robots 10(1): 67-82 (2001) · Zbl 1030.68751
[17] Murata S, Kurokawa H, Kokaji S: Self-assembling machine. In: Proc. of IEEE Intl. Conf. on Robotics and Automation, pp 441-448 (1994)
[18] Murata S, Kurokawa H, Tomita K, Kokaji S: Self-assembling method for mechanical structure. In: Artif. Life Robotics 1: 111-115 (1997)
[19] Murata S, Kurokawa H, Yoshida E, Tomita K, Kokaji S: A 3-D self-reconfigurable structure. In: Proc. of IEEE Intl. Conf. on Robotics and Automation, pp 432-439 (1998)
[20] Murata S, Yoshida E, Kamimura A, Kurokawa H, Tomita K, Kokaji S: M-TRAN: Self-reconfigurable modular robotic system. IEEE/ASME Trans. on Mechatronics 7(4): 431-441 (2002)
[21] Nguyen A, Guibas LJ, Yim M: Controlled module density helps reconfiguration planning. New Directions in Algorithmic and Computational Robotics. A.K. Peters, pp 23-36 (2001) · Zbl 0986.68148
[22] Nilsson M: Free climbing snake robot. IEEE Control Systems, pp 21-26 (1998)
[23] Pamecha A, Chirikjian G: A useful metric for modular robot motion planning. In: Proc. of IEEE Intl. Conf. on Robotics and Automation, pp 442-447 (1996)
[24] Pamecha A, Ebert-Uphoff I, Chirikjian G: Useful metrics for modular robot motion planning. IEEE Trans. on Robotics and Automation 13(4): 531-545 (1997) · Zbl 0881.68137
[25] Pamecha A, Chiang C-J, Stein D, Chirikjian G: Design and implementation of metamorphic robots. In: Proc. of ASME Design Engineering Technical Conf. and Computers in Engineering Conf. (1996)
[26] Prevas K, Unsal C, Efe M, Khosla P: A hierarchical motion planning strategy for a uniform self-reconfigurable module robotic system. In: Proc. of IEEE Intl. Conf. on Robotics and Automation, pp 787-792 (2002)
[27] Rus D, Vona M: Physical implementation of the crystalline robot. In: Proc. of IEEE Intl. Conf. on Robotics and Automation, pp 1726-1733 (2000)
[28] Rus D, Vona M: Crystalline robots: Self-reconfiguration with compressible unit modules. Autonomous Robots Journal, special issue on self-reconfigurable robots 10(1): 107-124 (2001) · Zbl 1030.68833
[29] Salemi B, Shen W-M, Will P: Hormone-controlled metamorphic robots. In: Proc. of IEEE Intl. Conf. on Robotics and Automation, pp 4194-4199 (2001)
[30] Suh J, Homans S, 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)
[31] Tomita K, Murata S, Kurokawa H, Toshida E, Kokaji S: Self-assembly and self-repair method for a distributed mechanical system. IEEE Trans. on Robotics and Automation 15(6): 1035-1045 (1999)
[32] Unsal C, Kiliccote H, Khosla P: A modular self-reconfigurable bipartite robotic system: implementation and motion planning. Auton. Robot. 10: 23-40 (2001) · Zbl 1030.68875
[33] Vassilvitskii S, Yim M, Suh J: 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)
[34] Walter J, Tsai B, Amato N: Choosing good paths for fast distributed reconfiguration of hexagonal metamorphic robots. In: Proc. of the IEEE Intl. Conf. on Robotics and Automation, pp 102-109 (2002)
[35] Walter J, Welch J, Amato N: Concurrent metamorphosis of hexagonal robot chains into simple connected configurations. IEEE Trans. on Robotics and Automation (2002,) to appear
[36] Walter J, Welch J, Amato N: Distributed reconfiguration of hexagonal metamorphic robots in two dimensions. In: Sensor Fusion and Decentralized Control in Robotic Systems III, Gerard T. McKee and Paul S. Schenker, eds., Proceedings of SPIE, 4196: 441-453 (2000)
[37] Yim M: A reconfigurable modular robot with many modes of locomotion. In: Proc. of Intl. Conf. on Advanced Mechatronics, pp 283-288 (1993)
[38] Yim M, Duff D, Roufas K: Polybot: a modular reconfigurable robot. In: Proc. of the IEEE Intl. Conf. on Robotics and Automation, pp 514-520 (2000)
[39] Yim M, Lamping J, Mao E, Chase JG: Rhombic dodecahedron shape for self-assembling robots. SPL TechReport P9710777, Xerox PARC (1997)
[40] Yoshida E, Murata S, Tomita K, Kurokawa H, Kokaji S: Distributed formation control of a modular mechanical system. In: Proc. of the Intl. Conf. on Intelligent Robots and Systems, pp 1090-1097 (1997)
[41] Yoshida E, Murata S, Kurokawa H, Tomita K, Kokaji S: A distributed reconfiguration method for 3-D homogeneous structure. In: Proc. of the Intl. Conf. on Intelligent Robots and Systems, pp 852-859 (1998)
[42] Zhang Y,
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.