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

  • Figure 1

    (Color online) The M-TRAN III modular robot in national institute of advanced industrial science and technology (AIST), Japan [2]. (a) A single M-TRAN III module; (b) the reconfiguration from a quadruped robot to snake robot. Both robots are made up of the same number of modules. Photos are courtesy of professor Haruhisa Kurokawa

  • Figure 2

    (Color online) Double-unit modules. (a) M-TRAN III module [2] is an edge-hinged double-unit module (Subsection 2.3). It consists of two (i.e., female and male) semi-cylindrical cubes. Two cubes are connected by a linker. Each cube can independently rotate with respect to the linker and the rotation angle is ranged from $-90^{\circ}$ to $90^{\circ}$; (b) the CellRobot in KEYi technology incorporated consists of two symmetrically hemispherical units. By rotating around the center of the module, each unit can relatively move with respect to each other (Subsection 2.2)

  • Figure 3

    (Color online) Single-unit modules. (a) M-Blocks [4] modules locomote by pivoting about edges, and the movements are driven by a torque generated by rapidly decelerating an internal flywheel. The permanent magnets embedded in edges are free to rotate to allow 2–4 modules to form structural magnetic bonds. (b) crystalline [5] modules move by expanding and contracting and the length of the side when expanded is two times that of contraction. Photos are courtesy of professor Daniela Rus and doctor John Romanishin

  • Figure 4

    (Color online) Central-point-hinged type I. (a) The rotate axis is the line connecting the centers of two faces opposite with each other; (b) Atron [10] proposed by University of Southern Denmark modules are in this type. Photos are courtesy of professor Henrik Hautop Lund

  • Figure 5

    (Color online) Central-point-hinged type II. (a) The rotation axis is the diagonal of bounding box. (b) Molecube modules [9]proposed by Cornell University cannot move relative to each other. (b) Roombots [10,11]modules proposed by Swiss Federal Institute of Technology in Lausanne (EPFL) are able to move relative to each other. Photos are courtesy of BioRob, EPFL

  • Figure 6

    (Color online) Possible grid-reconfigurations with two Roombots because of the different relationship between rotate axes [10]. (a) Skew: 5 options; (b) parallel, 4 options; (c) orthogonal, 4 options

  • Figure 7

    (Color online) The edge-hinged type. (a) The sub-modules of SuperBot [6]can rotate around the link (DoF 1 and 2) and with each other (DoF 3); (b) the sub-modules of iMobot [3]can rotate around the link (DoF 2 and 3), and the modules can rotate with each other (DoF 1 and 4). Photos are courtesy of professor Wei-Min Shen

  • Figure 8

    (Color online) (a) SMORES modules and (b) their motion modes [14]. Each module has two wheels (DoF 1 and 2), and the connected face is a rotatable disk. Once the connection of two modules is made, there are DoF 3 and 4. Photos are courtesy of professor Mark Yim

  • Figure 9

    (Color online) Pivoting modules. (a) The modules move by pivoting about edges. (b) Modules in this type cannot control the angle of rotation accurately because of lacking in connector. They cannot stop at the position showed in red cross and the only way to stop pivoting is other modules block the way, as show in green circle

  • Figure 10

    (Color online) A sketch map of reconfiguration by expanding and contracting. Modules 1, 2, 3, 4 of (a) were contracted, and the configuration is transformed into (b). Then modules 3 and 4 were expanded, transformed into (c). Then modules 1 and 2 were expanded, transformed into (d). Because the modules are all the same, the reconfiguration between (a) to (d) can be regarded as that module 4 moved to the position of module 5

  • Figure 11

    (Color online) The 3D expand and contract operation of Telecubes [16]. (a) CAD model of Telecubes module; (b) the physical prototype of Telecubes module expanded; (c) the physical prototype of Telecubes module contracted. Photos are courtesy of professor Mark Yim

  • Figure 12

    (Color online) The (a) four-legged walkers and (b) snake forms assembled by four M-TRAN modules [2]. Each module should bend or rotate by the rules to walk or crawl. (c) The automatic metamorphosis between configurations. Photos are courtesy of professor Haruhisa Kurokawa

  • Figure 13

    (Color online) (a) The rolling Roombots modules can be used to moving furniture; (b) a Roombots [10,11]chair. The rolling bottom modules enable the chair to move. Photos are courtesy of BioRob, EPFL

  • Figure 14

    (Color online) The chain-typed self-reconfiguration. (a) Modules 9–16 are regarded as a chain, and it can be fold through the cooperation among modules; (b) module 16 moves to connect module 5, then module 11 disconnects module 12; (c) modules 12–16 are regarded as a new chain

  • Figure 15

    (Color online) The one-by-one-type self-reconfiguration. Only one module moves in each step

  • Figure 16

    (Color online) Two configurations composed by two M-TRAN modules. A M-TRAN module consists of female cube (white) and male cube (black). (+,$-$) represents that the hook in male cube is inserted into the slit in female cube of another module. The male and female cube without +,$-$ is free to rotate. Configurations (a) and (b) are different because their connection methods are different

  • Figure 17

    (Color online) (a) The configuration 1 is composed of three M-TRAN modules; (b) the configuration 2 is composed of three M-TRAN modules; (c) graph representation for the configuration. Each module is regarded as a node. There is an edge between two nodes if two modules are connected; (d) weighted digraph representations for two configurations. This method separates configurations 1 and 2 easily

  • Figure 18

    (Color online) (a) Each face is uniquely identified with an ID; (b) a configuration of three M-TRAN modules; (c) the weighted graph representation of configuration in (b); (d) the matrix representation of configuration in (b). Two columns of the matrix correspond to the two joint faces in (b). Three rows of the matrix correspond to three modules. Two non-zero units in each column correspond to the id of the faces which are connected to other modules. For example, column $C$1 means the face 6 of module 1 and the face 2 of module 2 are connected

  • Figure 20

    (Color online) Three graphs above are isomorphic

  • Figure 21

    (Color online) The relationship between number of configurations and number of modules. The horizontal axis is the number of modules, and the vertical axis is the logarithm of the configuration number. The result is approximately a straight line. The expression of the fitting function is $f(n)={\rm~e}^{1.62n-3.7}$, which indicates that the number of configuration increases exponentially with the increase of module number

  • Figure 22

    The overlap metric. Modules 1, 2, 3 are overlapped in (a), (b) and (a), (c), so both the overlap metrics are 1. However, transformation from (a) to (b) needs only one step while (a) to (c) needs two steps

  • Figure 23

    (Color online) The principle of expanded-and-extracted modules. Module 1, 2, 3, 4 of (a) were contracted, and the configuration is transformed into (b). Then modules 3 and 4 were expanded, transformed into (c). Then modules 1 and 2 were expanded, transformed into (d). Because the modules are all the same, the reconfiguration between (a) to (d) can be regarded as that module 4 moved to the position of module 5

  • Figure 24

    (Color online) An example of “melt-grow algorithm. The original shape are reconfigured to a linear form, then reconfigured to the target shape

  • Figure 25

    (Color online) (a) The sliding module is allowed only sliding movement across other modules surfaces; (b) the sliding module is not allowed rotate around other modules

  • Figure 26

    (Color online) The seed modules (red) help work module (yellow) move to another surface [62]. (a) Initial state. Seed module 1 is on the target surface while seed module 2 and work module are on the original surface; (b) seed module 1 slides on the target surface to connect the seed module 2; (c) work module slides from seed module 2 to 1; (d) seed module 1protectłinebreak and work module slide together to target surface

  • Figure 27

    (Color online) The meta-module composed of M-TRAN modules [62]. (a) The expanding state of meta-module, which includes six arms assembled by 12 M-TRAN modules; (b) central blocks; (c) the contracting state of meta-module

  • Figure 28

    (Color online) An example of self-reconfiguration of 4 M-TRAN modules. Upper-left is original shape and lower-left is the target shape. The difference between them is shown by orange arrow. It needs 9 moves to change only one modules position [61]

  • Table 1   Comparison of different actuators used in reconfigurable modular robots
    Type Torque Size Control complexity Cost
    Brushless DC motor Large Medium Complex High
    Brush DC motor Medium Large Easy High
    DC stepping motor Medium Large Moderate Moderate
    Shape memory alloy Small Small Complex Low

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

京ICP备18024590号-1