logo

SCIENTIA SINICA Informationis, Volume 48, Issue 2: 143-176(2018) https://doi.org/10.1360/N112017-00154

Path planning for self-reconfigurable modular robots: a survey

More info
  • ReceivedJul 12, 2017
  • AcceptedSep 25, 2017
  • PublishedJan 24, 2018

Abstract

Self-reconfigurable modular robots (SRMRs) are a special type of robots that can change their shapes and functions according to different tasks and environments. Such a robot is usually constructed using connected modules, each of which can encapsulate a simple function independently and also communicate with each other. Complex tasks can be completed by those connected modules collaboratively. In recent years, SRMRs have attracted considerable attention from both the academia and industry because of their versatility and flexibility. The path planning problem for the transformation of an SRMR is an important but not a well-solved problem, which can be considered as finding an optimal path in the configuration space where every point represents a feasible configuration of the SRMR. To provide a systematic overview of this research, we review the existing approaches considering five different aspects of SRMRs, including the type of motion on a single module, hardware for different motions, connectivity between modules, representation of a configuration space, and path planning algorithms. Aiming at motivating more research into SRMRs, the problems in existing approaches are analyzed and challenges in future work are summarized at the end of this paper.


Funded by

国家重点研发计划(2016YFB1001200)

国家自然科学基金创新研究群体项目(61521002)


Acknowledgment

感谢Swiss Federal Institute of Technology in Lausanne生物机器人实验室提供本文中使用的Roombots 图片, 美国Massachusetts Institute of Technology计算机科学与人工智能实验室Daniela Rus 教授和John Romanishin博士提供了M-Blocks和Crystalline图片, 美国University of Southern California Polymorphic机器人实验室Wei-Min Shen教授提供了SuperBot图片, 美国University of Pennsylvania GRASP实验室Mark Yim教授提供了SMORES和Telecubes图片, 日本产业技术综合研究所的Haruhisa Kurokawa 教授提供了M-TRAN III图片, 以及Technical University of Denmark Henrik Hautop Lund 教授提供了ATRON 图片.


References

[1] Østergaard E H, Christensen D J, Eggenberger P, et al. Hydra: from cellular biology to shape-changing artefacts. In: Proceedings of the 15th International Conference on Artificial Neural Networks, Poland, 2005. 275--281. Google Scholar

[2] Kurokawa H, Tomita K, Kamimura A, et al. Distributed self-reconfiguration of M-TRAN III modular robotic system. Int J Robot Res, 2008, 27: 373--386. Google Scholar

[3] Ryland G G, Cheng H H. Design of iMobot, an intelligent reconfigurable mobile robot with novel locomotion. In: Proceedings of IEEE International Conference on Robotics and Automation, Anchorage, 2010. 60--65. Google Scholar

[4] Murata S, Yoshida E, Kamimura A, et al. M-TRAN: self-reconfigurable modular robotic system. IEEE/ASME Trans Mech, 2002, 7: 431--441. Google Scholar

[5] Kurokawa H, Kamimura A, Yoshida E, et al. M-TRAN II: metamorphosis from a four-legged walker to a caterpillar. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Las Vegas, 2003. 2454--2459. Google Scholar

[6] 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, Beijing, 2006. 3636--3641. Google Scholar

[7] Romanishin J W, Gilpin K, Rus D. M-blocks: momentum-driven, magnetic modular robots. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Tokyo, 2013. 4288--4295. Google Scholar

[8] Rus D, Vona M. Crystalline robots: self-reconfiguration with compressible unit modules. Auton Robot, 2001, 10: 107--124. Google Scholar

[9] Rus D, Vona M. A physical implementation of the self-reconfiguring crystalline robot. In: Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, 2000. 1726--1733. Google Scholar

[10] Jorgensen M W, Ostergaard E H, Lund H H. Modular ATRON: modules for a self-reconfigurable robot. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, 2004. 2068--2073. Google Scholar

[11] Zykov V, Chan A, Lipson H. Molecubes: an open-source modular robotics kit. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems Workshop, Self-Reconfigurable Robotics, San Diego, 2007. 3--6. Google Scholar

[12] Sproewitz A, Billard A, Dillenbourg P, et al. Roombots-mechanical design of self-reconfiguring modular robots for adaptive furniture. In: Proceedings of IEEE International Conference on Robotics and Automation, Kobe, 2009. 4259--4264. Google Scholar

[13] Sprowitz A, Moeckel R, Vespignani M, et al. Roombots: a hardware perspective on 3D self-reconfiguration and locomotion with a homogeneous modular robot. Robot Auton Syst, 2014, 62: 1016--1033. Google Scholar

[14] Davey J, Kwok N, Yim M. Emulating self-reconfigurable robots-design of the SMORES system. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Vilamoura, 2012. 4464--4469. Google Scholar

[15] Romanishin J W, Gilpin K, Claici S, et al. 3D M-Blocks: self-reconfiguring robots capable of locomotion via pivoting in three dimensions. In: Proceedings of IEEE International Conference on Robotics and Automation, Seattle, 2015. 1925--1932. Google Scholar

[16] Suh J W, Homans S B, Yim M. Telecubes: mechanical design of a module for self-reconfigurable robotics. In: Proceedings of the IEEE International Conference on Robotics and Automation, Washington, 2002. 4095--4101. Google Scholar

[17] Ikuta K. Micro/miniature shape memory alloy actuator. In: Proceedings of the IEEE International Conference on Robotics and Automation, Cincinnati, 1990. 2156--2161. Google Scholar

[18] Yoshida E, Kokaji S, Murata S, et al. Miniaturization of self-reconfigurable robotic system using shape memory alloy actuator. J Robotic Mech, 2000, 12: 96--102. Google Scholar

[19] Yoshida E, Murata S, Kokaji S, et al. Micro self-reconfigurable modular robot using shape memory alloy. J Robotic Mech, 2001, 13: 212--218. Google Scholar

[20] Stoy K, Brandt D, Christensen D J, et al. Self-Reconfigurable Robots: an Introduction. Cambridge: MIT Press, 2010. 63--91. Google Scholar

[21] Yim M, Zhang Y, Roufas K, et al. Connecting and disconnecting for chain self-reconfiguration with PolyBot. IEEE/ASME Trans Mech, 2002, 7: 442--451. Google Scholar

[22] Yim M, Eldershaw C, Zhang Y, et al. Self-reconfigurable robot systems: PolyBot. J Robotic Soc Jpn, 2003, 21: 851--854. Google Scholar

[23] Shen W M, Kovac R, Rubenstein M. SINGO: a single-end-operative and genderless connector for self-reconfiguration, self-assembly and self-healing. In: Proceedings of IEEE International Conference on Robotics and Automation, Kobe, 2009. 4253--4258. Google Scholar

[24] Tosun T, Davey J, Liu C, et al. Design and characterization of the EP-Face connector. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Deajeon, 2016. 45--51. Google Scholar

[25] Karagozler M E, Campbell J D, Fedder G K, et al. Electrostatic latching for inter-module adhesion, power transfer, and communication in modular robots. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, San Diego, 2007. 2779--2786. Google Scholar

[26] Moeckel R, Jaquier C, Drapel K, et al. Exploring adaptive locomotion with YaMoR, a novel autonomous modular robot with Bluetooth interface. Ind Robot, 2006, 33: 285--290. Google Scholar

[27] Castano A, Shen W M, Will P. CONRO: towards deployable robots with inter-robots metamorphic capabilities. Auton Robot, 2000, 8: 309--324. Google Scholar

[28] Murata S, Kurokawa H, Kokaji S. Self-assembling machine. In: Proceedings of the IEEE International Conference on Robotics and Automation, San Diego, 1994. 441--448. Google Scholar

[29] Tomita K, Murata S, Kurokawa H, et al. Self-assembly and self-repair method for a distributed mechanical system. IEEE Trans Robotic Autom, 1999, 15: 1035--1045. Google Scholar

[30] Yim M. New locomotion gaits. In: Proceedings of the IEEE International Conference on Robotics and Automation, San Diego, 1994. 2508--2514. Google Scholar

[31] Zhao J, Cui X D, Zhu Y H, et al. A new self-reconfigurable modular robotic system UBot: multi-mode locomotion and self-reconfiguration. In: Proceedings of IEEE International Conference on Robotics and Automation, Shanghai, 2011. 1020--1025. Google Scholar

[32] Zhao J, Tang S F, Zhu Y H, et al. A modular self-reconfigurable robot based on universal joint. Robot, 2010, 32: 608--613. Google Scholar

[33] Jing G Y, Tosun T, Yim M, et al. An end-to-end system for accomplishing tasks with modular robots. In: Proceedings of Robotics Science and Systems, Michigan, 2016. Google Scholar

[34] Mondada F, Pettinaro G C, Guignard A, et al. SWARM-BOT: a new distributed robotic concept. Auton Robot, 2004, 17: 193--221. Google Scholar

[35] Rubenstein M, Cornejo A, Nagpal R. Programmable self-assembly in a thousand-robot swarm. Science, 2014, 345: 795--799. Google Scholar

[36] Rybski P E, Larson A, Veeraraghavan H, et al. Performance evaluation of a multi-robot search $\&$ retrieval system: experiences with MinDART. J Intell Robot Syst, 2008, 52: 363--387. Google Scholar

[37] Sastra J, Bernal-Heredia W G, Clark J, et al. A biologically-inspired dynamic legged locomotion with a modular reconfigurable robot. In: Proceedings of ASME Dynamic Systems and Control Conference, Michigan, 2008. 1467--1474. Google Scholar

[38] Østergaard E H, Kassow K, Beck R, et al. Design of the ATRON lattice-based self-reconfigurable robot. Auton Robot, 2006, 21: 165--183. Google Scholar

[39] Wei H X, Wang T M. Configuration analysis and self-assembly control for modular swarm robots. J Mech Eng, 2010, 46: 100--108. Google Scholar

[40] Rubenstein M, Nagpal R. Kilobot: a robotic module for demonstrating behaviors in a large scale ($2^{10}$ units) collective. In: Proceedings of the IEEE International Conference on Robotics and Automation Workshop, Modular Robotics: State of the Art, Anchorage, 2010. 47--51. Google Scholar

[41] Stoy K. The deformatron robot: a biologically inspired homogeneous modular robot. In: Proceedings of the IEEE International Conference on Robotics and Automation, Orlando, 2006. 2527--2531. Google Scholar

[42] Zhang Y H, Zhao J, Zhang L, et al. Novel modular self-reconfigurable robot system. J Mech Eng, 2006, 42: 175--178. Google Scholar

[43] Chirikjian G S. Kinematics of a metamorphic robotic system. In: Proceedings of the IEEE International Conference on Robotics and Automation, San Diego, 1994. 449--455. Google Scholar

[44] Pamecha A, Chiang C J, Stein D, et al. Design and implementation of metamorphic robots. In: Proceedings of the ASME Design Engineering Technical Conference and Computers in Engineering Conference, Irvine, 1996. Google Scholar

[45] Mondada F, Pettinaro G C, Guignard A, et al. SWARM-BOT: a new distributed robotic concept. Auton Robot, 2004, 17: 193--221. Google Scholar

[46] Kotay K, Rus D, Vona M, et al. The self-reconfiguring robotic molecule. In: Proceedings of the IEEE International Conference on Robotics and Automation, Leuven, 1998. 424--431. Google Scholar

[47] Yim M, Duff D G, Roufas K D. PolyBot: a modular reconfigurable robot. In: Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, 2000. 514--520. Google Scholar

[48] Gilpin K, Kotay K, Rus D, et al. Miche: modular shape formation by self-disassembly. Int J Robot Res, 2008, 27: 345--372. Google Scholar

[49] Stoy K, Brandt D. Efficient enumeration of modular robot configurations and shapes. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Tokyo, 2013. 4296--4301. Google Scholar

[50] Harary F. Unsolved problems in the enumeration of graphs. Publ Math Inst Hungar Acad Sci, 1960, 5: 63--95. Google Scholar

[51] Eden M. A two-dimensional growth process. In: Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics, and Probability. Berkeley: University of California Press, 1961. 223--239. Google Scholar

[52] Klarner D A, Rivest R L. A procedure for improving the upper bound for the number of n-ominoes. Canad J Math, 1973, 25: 585--602. Google Scholar

[53] Cormen T, Leiserson C, Rivest R. Introduction to algorithms. Cambridge: MIT Press, 1990. 527--531. Google Scholar

[54] Hou F, Shen W M. On the complexity of optimal reconfiguration planning for modular reconfigurable robots. In: Proceedings of IEEE International Conference on Robotics and Automation, Anchorage, 2010. 2791--2796. Google Scholar

[55] Michael R G, David S J. Computers and intractability: a guide to the theory of NP-completeness. B Am Math Soc, 1980, 3: 898--904. Google Scholar

[56] Russell S, Norvig P. Artificial Intelligence: a Modern Approach. Egnlewood Cliffs: Prentice-Hall, 1995. 25--27. Google Scholar

[57] Pamecha A, Ebert-Uphoff I, Chirikjian G S. Useful metrics for modular robot motion planning. IEEE Trans Robotic Autom, 1997, 13: 531--545. Google Scholar

[58] Papadimitriou C H, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. Mineola: Dover Publications, 1998. 248--255. Google Scholar

[59] Butler Z, Byrnes S, Rus D. Distributed motion planning for modular robots with unit-compressible modules. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Maui, 2001. 790--796. Google Scholar

[60] An B K. Em-cube: cube-shaped, self-reconfigurable robots sliding on structure surfaces. In: Proceedings of IEEE International Conference on Robotics and Automation, Pasadena, 2008. 3149--3155. Google Scholar

[61] Kawano H. Full-resolution reconfiguration planning for heterogeneous cube-shaped modular robots with only sliding motion primitive. In: Proceedings of IEEE International Conference on Robotics and Automation, Stockholm, 2016. 5222--5229. Google Scholar

[62] Parada I, Sacristan V, Silveira R I. A new meta-module for efficient reconfiguration of hinged-units modular robots. In: Proceedings of IEEE International Conference on Robotics and Automation, Stockholm, 2016. 5197--5202. Google Scholar

[63] Burkard R E, Deineko V G, van Dal R, et al. Well-solvable special cases of the traveling salesman problem: a survey. SIAM Rev, 1998, 40: 496--546. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1