Sage Journals: Discover world-class research

Abstract

Configuration of a reconfigurable modular system is a tough issue because the possible configurations or structures grow exponentially with the number of modules. A library of the non-isomorphic configurations should be set up as a database for configuration design and control. In this paper, we propose a matrix-based enumerating approach for the non-isomorphic configurations of a reconfigurable modular robot system with square-cubic-cell(SCC) modules. Each SCC module considered in this study includes a cubic module body and four connectors on its lateral surfaces. Since it has a square lattice like 2D projection, configuration matrices are proposed to represent the topological information of the modular robot. Thus reconfiguration and enumeration can be programmed by matrix computation in simulation. According to combinational principle, recursive algorithms are used to find out all non-isomorphic configurations. Enumerating result for a multi-module SCC system is provided as an example. Potential applications of this approach to other reconfigurable systems with lattice-form or cubic-form modules are discussed as well. As an application, enumeration of the multi-module CONRO robot also proves the validity of this method.

Keywords

reconfigurable modular robot non-isomorphic configuration lattice cubic configuration matrix 2D projection

1. Introduction

The reconfigurable modular robot is a kind of biologically inspired robot that can be reconfigured and reassembled to fulfil various natural environmental tasks, which has been widely studied for many applications in areas of deep sea exploration, space exploration, urban search and rescue, and many other situations (e.g., Fukuda and Nakagawa, 1988, 1990; Groß et al., 2006; Liu et al., 2004, 2005, 2008; Rus and Chirikjian, 2001; Shen et al., 2006; Yim et al., 2000a, 2003; Zykov et al., 2005). The reconfigurable modular robot is usually composed of a large number of homologous modules or heterologous modules. It is a challenging and tough issue to develop and construct a reconfigurable modular robot system, since the possible configurations of the reconfigurable modular robot grow exponentially with the number of modules (Butler et al., 2004; Chen, 1994; Duff et al., 2001; Yim, 1994; Yoshida et al., 2002). Configuration analysis is considered to be the first step to design a reconfigurable modular robot since configuration not only reflects the topology of the system but also has close relationship with the robotic flexibility and controllability. How to find out all the possible configurations and then choose the best assembled structure or configuration is difficult but crucial for development and control of a reconfigurable modular robot system.

Configuration representation or modeling is a foundation for configuration enumeration. This work is to extact the module's topological information and its physical information as effectively as possible. Optimal modeling of the representation is required. The paradox is that if too much information is included, the computational complexity will increase, while if the key information is lost, reasonable representation is impossible. Since the reconfigurable modular robot with multi-modules is similar to a connected graph, researchers have successfully modeled the modular robot via graph and matrix in its configuration representation and enumeration. When the configuration enumeration is needed, graph theory (such as Pólya theory) and combinatorial mathematics can be used for the modular robots with regular structures. Kinematic graph and Assembly Incidence Matrix (AIM) were proposed by Chen et al. to model and optimize the modular manipulator. Joint module and link module have been selected to enumerate the tree type modular manipulator effectively (Chen and Burdick, 1993, 1995; Yang and Chen, 2000). Atom Connectivity Graph for Crystal C denoted by ACG(C) was also proposed to represent the crystalline robots in reconfiguration space analysis (Rus and Vona, 2001). Node and line were used to represent and find the configuration of robot “CONRO” (Castano and Will, 2001). Graph representation and wireframe depiction were used in analyzing the configurations of Polypod (Casal and Yim, 1999). Group and matrix were proposed theoretically to discuss configuration space of metamorphic robots (Chiang and Chirikjian, 2001). There are also other representing techniques. The connection types of a 3-D unit were classified and each unit was described by a sphere with connection arms (Yoshida, 1998). In such representation, each connection type was expressed by its valence. For instance, the type with valence 3 and type 0 is written as “C30”, where “C” denotes “connection”. The binary string was widely used to represent the module manipulator in genetic design and optimization techniques (e.g., Chocron and Bidaud, 1997; Bi and Zhang, 2001). However, there hardly exists an universal technique for configuration representation and enumeration.

In the literatures, reconfigurable modular robots can be mainly divided into chain-type reconfigurable systems (e.g., CEBOT (Fukuda and Nakagawa, 1990), CONRO (Castano and Will, 2001), SuperBot (Shen et al., 2006), Polypod (Casal and Yim, 1999), PolyBot (Yim et al., 2000b), AMOEBA-I (Liu et al., 2008)) and lattice-type ones (e.g., Telecube (Vassilvitskii et al., 2002), I-Cube (Ünsal and Khosla, 2000), Metamorphic (Chirikjian, 1994), Molecule (Kotay, 1998), Crystalline (Rus and Vona, 2001), Fracta (Murata, 1994), Gear-Type Unit (Tokashiki et al., 2003), ATRON (Ostergaard et al., 2006), Riken Vertical (Hosokawa et al., 1998)). There are also some hybrid systems such as M-TRAN (Murata et al., 2002), Tetrobot (Lee and Sanderson, 2001), RMPRS (Wang et al., 2006), and Swarm-Bot (Groß et al., 2006). After extensive observation on the geometrical figurations of existing modular systems, we find out an interesting thing that their modules usually have regular shapes. Most geometrical shapes for their modules in the 3D structures are cube, tetrahedron, sphere or dodecahedron, while their 2D projections are square, hexagon, or circle. Since some of them can be projected onto a 2D plane like a rectangle or a square lattice, we propose a technique by using configuration matrices to represent the non-isomorphic configurations of a reconfigurable modular robot with square-cubic-cell(SCC) modules. Being discrete and distinctive, each non-isomorphic configuration denotes an unique assembled structure. This idea is inspired by the similarity between the SCC modules and the matrix for their regular figuration. A single SCC module includes a cubic module body and four connectors (two male connectors and two female ones). Since the module is represented by a physical configuration matrix, all the different parts are displayed in the matrix as various sub-matrices accordingly. The modular robot's restructuring or reconfiguration can be turned into configuration matrix's computation. Therefore, configuration enumeration is carried out by configuration matrix's enumeration. This technique can also be applied to other reconfigurable modular robot system with lattice-form or cubic-form modules. An example applied on the famous reconfigurable modular robot system, CONRO, is provided for proving its validity.

The rest of the paper is organized as follows. After the SCC modular system is briefly introduced, configuration matrices and related definitions are proposed to describe the modular robot in Section 2. Enumerating algorithm of the non-isomorphic configuration for the multi-module SCC robot system is provided in Section 3. Extended application of this approach to other lattice or cubic module based system is discussed in Section 4. Section 5 concludes the paper with current contributions and future extensions.

2. Representation and definition

2.1. A single SCC module description

As mentioned above, there are various kinds of modules in the chain-type or lattice-type reconfigurable modular robot. In this paper, we propose a square-cubic-cell (SCC) module which can be assembled into both chain-type structure and lattice type structure. A conceptual level of such kind of module is provided in Fig.1.

Fig. 1.

A single square-cubic-cell(SCC) module

In a SCC module, it mainly includes the cubic module body and four connectors in its lateral sides. The module body with free top/bottom faces can be a basic platform for equipment in terms of wheels or tracks, power, actuators, sensors, controllers, and manipulators. The connectors are the main mechanisms for system restructuring from connection and disconnection of the adjacent modules. Moreover, the links between adjacent modules can also possess some degrees of freedom for relative motion. Fig. 2 shows several locomotion capabilities envisioned for the reconfigurable modular robots. They can be a chain-type structure, a lattice-type or a hybrid one upon requirement. The chain-type structure is analogous to a snake. It can pass the narrow space and overcome the obstacle in line. There are also other modes of locomotion with various structures like insects, for example the biped structure, the three-legged structure, and the quadruped structure.

Fig. 2.

Several possible locomotion modes for the reconfigurable modular robots with several SCC modules. (a). The chain-type linear structure locked into a line for crossing ditches. (b). The chain-type linear structure passes through the pipeline in line. (c). The chain-type linear structure lifts the former units to overcome the stairs. (d). The chain-type biped structure overcomes obstacle. (e). The chain-type three-legged structure moves forwards. (f). The chain-type quadruped structure turns around. (g). The lattice-type quadruped structure turns around.

2.2. Representation of a single SCC module

As mentioned above, configuration representation is the basic step for the configuration studies. Representation should be possible to extract the actual physical information uniquely. It can save the key information of the modular robots in a compact form. Representing schemes are also useful for locomotion control or reconfiguration planning in which a description of the initial and target configuration is specified.

In this study, configuration matrices are proposed to represent the non-isomorphic configurations for the reconfigurable modular robot system with SCC modules. The original idea comes from the similarity between the modules' 2D projection and the matrix for their regular appearance. This representing technique for the modular robots can accurately represent the heterogeneous or different kinds of modules and the interconnections between them. In this approach, a singe module is represented by a configuration matrix, while its different parts are denoted by various sub-matrices respectively. Therefore, the multi-module robot's configuration enumeration can be turned into physical configuration matrix's computation which can be programmed in computer simulation.

According to the geometrical information of the 2D projection in Fig.3 (a), a single SCC module is represented by a 3times3 matrix. We call it physical matrix because the dimensions of the matrix and the values of the matrix are decided by the physical information of the module. The module body, the male connectors, and the female connectors, are represented by the sub-matrices, “6”, “1”, and “2” respectively as shown in Fig.3 (b). The dimensions of the configuration matrix are decided by the geometrical character of the module. The values of the configuration matrix are decided by the physical character of the module. Generally, the dimensions, the values of the single module's configuration matrix are in scale with the module's physical structure. The configuration matrix is changeable according to the actual modular robot platform. To visualize the configuration matrix, we use symbols to represent the configuration matrix during computer simulation. The physical configuration matrix can be equivalently displayed in Fig.3(c). The module body, the male connectors, and the female connectors, are displayed by square, circle, and diamond respectively. The x-coordinate denotes the column of the configuration matrix and the y-coordinate denotes the row of the configuration matrix.

Fig. 3.

Representation of a SCC module. (a).2D projection. (b). Represented by a 3times3 matrix. (c). Displayed in simulation.

2.3. Representation of two connected SCC modules

In the reconfigurable SCC modular robot system, reconfiguration mainly comes from disconnection or connection of the adjacent modules. Fig.4 gives the expression of the connection of two SCC modules. The link of connectors is represented by “3” in the matrices and hexagram in simulation. It can be seen that for two SCC modules, they have only one non-isomorphic configuration as shown in Fig.4(a) but four available configurations as shown in Fig.4(c). In these configuration matrices or configurations, three of them are repeated ones. On the other hand, we can know that the available connections of two adjacent modules are usually limited. When adding another new module in the existing modular robot system, the first step is to find the free male connectors and free female connectors, then add the new module to the existing system. For instance, Fig.4(c) displays the four available kinds of connections of the two-module system.

Fig. 4.

Representing the connection of two connected SCC modules. (a) Two SCC modules in connection. (b) Two-module robot's available configuration matrices. (c) Two-module robot's available configuration matrices in simulation.

2.4. Definition of the configuration matrices

It can be seen from Fig.4 that there are isomorphic or repeated configurations in the possible configurations. The repeated configurations will increase with the number of modules for system's symmetry. To find out the non-isomorphic configurations and delete them, we should find out the isomorphic configuration matrices. In Fig.4 (b), there are four isomorphic configuration matrices to represent one non-isomorphic configuration in Fig.4 (a). For a non-symmetry matrix, there would be many other isomorphic matrices which come from horizontal flip, vertical flip, transpose, and the combinatorial transformations. For instance, M₁(2) is a 3times5 matrix. M₂(2) is the vertical flip of M₁(2). M₃(2) is the transpose flip of M₁(2). M₄(2) is the transpose flip of M₂(2). In the same manner, M₅(2), M₆(2), M₇(2), and M₈(2) are the horizontal flip of M₁(2), M₂(2), M₃(2), and M₄(2). According to Fig.4 (b), the rest four isomorphic matrices are given below.

\begin{aligned} M_{5} (2) & = [\begin{matrix} 0 & 1 & 0 & 2 & 0 \\ 2 & 6 & 3 & 6 & 1 \\ 0 & 1 & 0 & 2 & 0 \end{matrix}] M_{6} (2) = [\begin{matrix} 0 & 2 & 0 & 1 & 0 \\ 1 & 6 & 3 & 6 & 2 \\ 0 & 2 & 0 & 1 & 0 \end{matrix}] \\ M_{7} (2) = [\begin{matrix} 0 & 1 & 0 \\ 2 & 6 & 2 \\ 0 & 3 & 0 \\ 1 & 6 & 1 \\ 0 & 2 & 0 \end{matrix}] M_{8} (2) = [\begin{matrix} 0 & 2 & 0 \\ 1 & 6 & 1 \\ 0 & 3 & 0 \\ 2 & 6 & 2 \\ 0 & 1 & 0 \end{matrix}] \end{aligned}

It is clear that M₅(2), M₆(2), M₇(2), and M₈(2) have the same structures as that of M₁(2), M₂(2), M₃(2), and M₄(2) respectively. There are totally eight isomorphic matrices in which four are repeated and there is only one non-isomorphic physical structure. Therefore, for any two configuration matrices, if one of them can be rotated or overturned to get the other, they are considered to be isomorphic configuration matrices. Otherwise, they are non-isomorphic configuration matrices. To distinguish the non-isomorphic configuration matrices and the non-isomorphic configurations, we define configuration matrix, configuration matrix group, non-isomorphic configuration matrix, and configuration matrix library to represent the multi-module robot's configuration topological information as follows.

Available configuration matrix Mi(j)

Available configuration matrix is the matrix which equivalently represents the modular robot's physical configuration. M_i(j) is the ith configuration matrix for the j-module robot system. For instance, M₄(2) in Fig.4 (b) is the fourth configuration matrix for the 2-module robot system.

Available configuration matrix group Cg(j)

Available configuration matrix group is defined as a set of the available configuration matrices. For instance, there are eight configuration matrices in the two-module robot's configuration matrix group. C_g(2)={M₁(2), M₂(2), M₃(2), M₄(2), M₅(2), M₆(2), M₇(2), M₈(2)}.

Non-isomorphic configuration matrix Ni(j)

Non-isomorphic configuration matrix is the unique matrix to represent the corresponding non-isomorphic configuration. N_i(j) is the ith non-isomorphic configuration matrix for the j-module robot system. The non-isomorphic configurations can be found from the front part to the end part of the available configuration matrix group. In C_g(2), there is only one non-isomorphic configuration matrix, that is, N₁(2) = M₁(2).

Non-isomorphic configuration matrix group Ng(j)

All the non-isomorphic configuration matrices are defined as a non-isomorphic configuration matrix group. In this matrix group, there is no matrix which can come from another configuration matrix's rotation or transformation. For instance, N_g(2) = {N₁(2)}.

Symmetrical non-isomorphic configuration matrix group Sg(j)

All the symmetrical non-isomorphic configuration matrices are defined to be in a symmetrical non-isomorphic configuration matrix group. In this matrix group, we only take the horizontal symmetry and the vertical symmetry into consideration. For instance, S_g(2)= {N₁(2)}.

3. Enumerating algorithm of the non-isomorphic configuration for a multi-module SCC system

The enumerating algorithm of the modular robot's non-isomorphic configurations is a typical combinatorial problem. During the enumerating process, repeating and omitting should be prohibited. The way to avoid repeat ones is to check and delete them. A complete and strict algorithm is needed to avoid missing. When it comes to add a new module, firstly we find out the free male or female connectors. Secondly, we select the connections in Fig.4 to add the next modules. Then, we delete the interfered ones and the repeated ones. The steps and pseudo-code of the algorithm have been provided as follows.

Step 1: Pre-processor

Represent existing n-module robot's non-isomorphic configurations by configuration matrices. All the non-isomorphic available configuration matrices are stored in the matrix group N_g(n).

Step 2: Operation and solution

Decide the size of matrix group N_g(n). N_g(n)={N₁(n), N₂(n),…, N_k(n)}.

For i=1: k

(a)
Find out the free male connectors and female connectors, that is, “1” and “2” in the matrix.
(b)
Then add the next module's configuration matrix at the location of “2” and “1” respectively.
(c)
If there is no physical interference in above addition, we get the available configuration matrix M_i(n+1). Store all these available configuration matrix into C_g(n+1);
(d)
Judge the isomorphic configurations in C_g(n+1) and delete them to get the non-isomorphic configuration matrix group N_g(n+1).

Step 3: Post-processor
(e)
Post-processor of the non-isomorphic configuration matrix group depends on the actual requirement.
(f)
Judge the symmetrical configurations and store them in S_g(n+1);
(g)
Select the configuration according to the requirement. For instance, judge the largest/smallest/longest/shortest/widest/ narrowest configuration matrix in the non-isomorphic configuration matrix group and seek it out.
(h)
Store or display the needed configurations in matrix or simulation status for reference.
(i)
If we need a robot system with more modules, go to Step 2(n=n+1), else end.

It is known that the single module robot has only one non-isomorphic configuration matrix. For instance, to get a two-module non-isomorphic configuration group, the first step is to find out the two free male connectors and the two female connectors in the single module's non-isomorphic configuration matrix. During the second step, the second module is connected to the previous module at the free connectors. After the matrices' addition, we get four available configuration matrices in an available configuration matrix group C_g(2). Then, we delete repeated ones to get a two-module non-isomorphic configuration group N_g(2). This recursive algorithm is also suitable for a modular robot with more than two modules.

The enumerating program is written by C language. We have implemented this program successfully on a Microsoft Windows 2000 computer operation system. The computer has a hardware configuration of Intel 2.00 GHz Pentium 4 CPU with 256MB RAM. The enumerating process includes a great amount of matrix computation. The CPU time consumed in the enumerating process has been recorded. It can be seen from Table 1 that this process is really time consumable. The complexity and optimization of the algorithm will be studied in the future works.

Table 1.
Enumerating results of the available configurations, the non-isomorphic configurations, and the symmetrical non-isomorphic configurations for SCC robot.

Number of modules (j) Number of non-isomorphic configurations in N_g(j) Number of symmetrical non-isomorphic configurations in S_g(j) Number of available configurations in C_g(j) CPU time(s)

1 1 1 1 0

2 1 1 4 0.078

3 3 2 6 0.125

4 7 3 24 0.563

5 21 7 68 2.828

6 60 10 248 28.938

7 208 24 814 273.547

8 704 36 3216 3969.403

9 2542 86 12164 56943.825

Since the enumerating process can be carried out off-line, the enumerating results can be stored as a database for sequent research. For instance, when a five-module SCC system is designed, it can be seen from Table 1 that the reconfigurable modular robots with five SCC modules have 21 kinds of non-isomorphic configurations and 7 of them are symmetrical ones. All these configurations' 2D projections are displayed in Fig.5 according to the simulation results. Thus, we can select the suitable configuration upon requirement. Several examples are provided in Fig.2.

Fig. 5.
All these non-isomorphic configurations of a reconfigurable modular robot with five SCC modules. Seven symmetrical non-isomorphic configurations are in (b), (h), (i), (j), (l), (r), and (s). Most of them are chain-type structures except that (d) and (f) are lattice-type structures.
4. Enumerating approach applied to the other reconfigurable modular robot with lattice-form module

The enumerating algorithm presented above can effectively deal with 2D square or rectangle reconfigurable system because the configuration matrices are in 2D configuration. However, in all the lattice-form modular robot systems, there are both 2D reconfigurable modular robot and 3D reconfigurable modular robot. Generally, there are two possible solutions to deal with the 3D structure. One solution is to redefine the configuration matrices extended in 3D space. The 3D matrix can be used to represent the cubic topology of the robot module in the same manner as that for the 2D lattice-form modules. However, such representation may be too complex to operate in algorithms. The other way is to simplify the 3D structure into 2D system according the 2D projection of the reconfigurable modular robot. Then the non-isomorphic configuration enumeration can be carried out in 2D space which is available to matrix representation and computation. For instance, the SCC system enumerated above, it is a 3D structure in locomotion modes (as shown in Fig.2). On the other hand, we can make use of the enumerating result of the 2D lattice-form modules with suitable modifications to get 3D structures. For example, according to the enumerating result in Fig.5, we can add the degrees of freedom to the lattice-form module (on the module body or the connectors) to get various 3D robots to meet the requirements.

Table 2 has listed most of the reconfigurable modular robots with lattice-form modules. These modular robot systems may be in chain-type, lattice-type or hybrid types. The modules are also in various lattice-form shapes. The matrix representation technique is limited by the matrix's character that it has parallel lines and parallel rows while the lines are perpendicular to the rows. Therefore, the hexagonal type is unable to be represented by matrix. Both the square type and the rectangle type can be represented by 2D matrix, while the cubic type can be represented by 3D matrix. Therefore, the rules to apply the configuration matrix based enumerating approach to the other reconfigurable modular robot with lattice-form module can be summarized as follows.

Table 2.
Potential application of the enumerating approach to other reconfigurable modular robot with lattice-form modules. The SCC system is included for comparison. (This table is partially reorganized from research results in the literatures (Ostergaard et al., 2006; Stoy, 2004)).

System Dimension Connectors 2D Projection Simplified Lattice Type Matrix Representation

MEL, Fracta (Murata et al., 1994) 2D 6 Hexagon Unable

U. Ryukyus, Gear-Type Unit (Tokashiki et al., 2003) 2D 6 Hexagon Unable

JHU, Metamorphic (Chirikjian, 1994) 2D 6 Hexagon Unable

Dartmouth, Crystalline (Rus and Vona, 2001) 2D 4 Square 2D matrix

MEL, Micro-unit (Yoshida et al., 2000) 2D 4 Square 2D matrix

TIT, Chobie (Inou et al., 2003) 2D 4 Square 2D matrix

RIKEN, Vertical (Hosokawa et al., 1998) 2D 1 Square 2D matrix

SIA, SCC 3D 4 Square 2D matrix

USC/ISI, CONRO (Castano and Will, 2001) 3D 4 Rectangle 2D matrix

Dartmouth, Molecule (Kotay et al., 1998) 3D 10 Hybrid Rectangles 2D matrices

SIA, AMOEBA-I (Liu et al., 2008) 3D 2 Hybrid Rectangles 2D matrices

SIA, RMPRS (Wang et al., 2006) 3D 2 Hybrid Rectangles 2D matrices

CMU, I-Cubes (Ünsal et al., 2001) 3D 2 Hybrid Cubes 3D matrices

Xerox PARC, Polybot (Yim et al., 2001a) 3D 2 Hybrid Cubes 3D matrices

MEL, M-TRAN (Murata et al., 2002) 3D 6 Cube 3D matrix

USC/ISI, SuperBot (Shen et al., 2006) 3D 6 Cube 3D matrix

Xerox PARC, Telecube (Vassilvitskii et al., 2002) 3D 6 Cube 3D matrix

MEL, 3D-Unit (Murata et al., 1998) 3D 6 Cube 3D matrix

TIT, Pneumatic (Inou et al., 2002) 3D 4 Cube 3D matrix

Maersk Institute, ATRON (Ostergaard et al., 2006) 3D 8 Cube 3D matrix

System	Dimension	Connectors	Simplified Lattice Type	Matrix Representation
MEL, Fracta (Murata et al., 1994)	2D	6	Hexagon	Unable
U. Ryukyus, Gear-Type Unit (Tokashiki et al., 2003)	2D	6	Hexagon	Unable
JHU, Metamorphic (Chirikjian, 1994)	2D	6	Hexagon	Unable
Dartmouth, Crystalline (Rus and Vona, 2001)	2D	4	Square	2D matrix
MEL, Micro-unit (Yoshida et al., 2000)	2D	4	Square	2D matrix
TIT, Chobie (Inou et al., 2003)	2D	4	Square	2D matrix
RIKEN, Vertical (Hosokawa et al., 1998)	2D	1	Square	2D matrix
SIA, SCC	3D	4	Square	2D matrix
USC/ISI, CONRO (Castano and Will, 2001)	3D	4	Rectangle	2D matrix
Dartmouth, Molecule (Kotay et al., 1998)	3D	10	Hybrid Rectangles	2D matrices
SIA, AMOEBA-I (Liu et al., 2008)	3D	2	Hybrid Rectangles	2D matrices
SIA, RMPRS (Wang et al., 2006)	3D	2	Hybrid Rectangles	2D matrices
CMU, I-Cubes (Ünsal et al., 2001)	3D	2	Hybrid Cubes	3D matrices
Xerox PARC, Polybot (Yim et al., 2001a)	3D	2	Hybrid Cubes	3D matrices
MEL, M-TRAN (Murata et al., 2002)	3D	6	Cube	3D matrix
USC/ISI, SuperBot (Shen et al., 2006)	3D	6	Cube	3D matrix
Xerox PARC, Telecube (Vassilvitskii et al., 2002)	3D	6	Cube	3D matrix
MEL, 3D-Unit (Murata et al., 1998)	3D	6	Cube	3D matrix
TIT, Pneumatic (Inou et al., 2002)	3D	4	Cube	3D matrix
Maersk Institute, ATRON (Ostergaard et al., 2006)	3D	8	Cube	3D matrix

: Male connector; : Female connector; : Unisex or hermaphroditic connector.

The lattice-form module has a 2D projection like a square or a rectangle grid.

The 2D lattice usually has four sides with connectors or ports while the 3D lattice has six faces with connectors or ports.

The types of lattice module are changeable. In the reconfigurable modular robot system with hybrid modules, there may be more than one kind of configuration matrix.

The dimensions of the configuration matrix for a lattice-form module are decided by the physical size of the module. Moreover, the matrix dimensions are set to be as small as possible to reduce the computational complexity.

According to above rules, we can take the CONRO robot as an example for the enumerating approach's application. Fig.6 (a) provides a simple CONRO module with three male connectors and one female connector. It can be represented by a 5times3 matrix as shown in Fig.6(b). Based on this matrix, the enumerating process following the steps in Section 3 can be successfully carried out. Enumerating results of the available configurations, the non-isomorphic configurations, and the symmetrical non-isomorphic configurations for the reconfigurable modular robots with one module to six CONRO modules are provided in Table 3. All the symmetrical non-isomorphic configurations of a reconfigurable modular robot with five CONRO modules are displayed in Fig.7.

Fig. 6.

Representation of a single CONRO module. (a). A simple CONRO module includes a module body, three male connectors and one female connector (Støy et al., 2002). (b). Represented by a 5times3 matrix. (c). Displayed in computer simulation.

Fig. 7.

All the symmetrical non-isomorphic configurations of a reconfigurable modular robot with five CONRO modules.

Table 3.

Enumerating results of the reconfigurable modular robots with one to six CONRO modules.

Number of modules (j)	Non-isomorphic configurations N_g(j)	Symmetrical non-isomorphic configurations S_g(j)	Number of available configurations in C_g(j)	CPU time (s)
1	1	1	1	0
2	2	1	3	0.1400
3	7	2	10	0.3900
4	29	3	49	4.2970
5	133	7	260	109.83
6	653	12	1433	3505.3

According to the enumerating results in Table 1 and those in Table 3, there are many factors deciding the numbers of non-isomorphic configurations. These factors include the number of connectors or ports per module, the number of ways that two ports can be attached, symmetries in the module, the physical structure of the module, the dimension or size proportionality of the connectors, and the types of modules. In summary, physical information about the modules is crucial to represent and enumerate the non-isomorphic configurations. When we use the enumerating algorithms, the factors mentioned above should be highly noticed.

5. Conclusion

In this paper, we have proposed a matrix-based enumerating approach for the non-isomorphic configurations of a reconfigurable modular robot system with square-cubic-cell (SCC) modules. Since the SCC module has a lattice-like 2D projection, configuration matrices have been proposed to represent the topological information of the modular robot. Configuration enumeration has also been transformed into matrix computation. Therefore, recursive algorithms have been successfully used to find out all these non-isomorphic configurations for a multi-module SCC system. Potential applications and limitations of this approach to other reconfigurable systems with lattice-form modules have also been discussed.

This paper has also presented the 2D configuration matrix based enumerating result for the reconfigurable modular robot with small number of lattice-form modules. We will investigate the optimization of the algorithms and the possibilities of 3D matrix based enumerating technique in our future study.

Footnotes

6. Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant No. 60705029), the National High-Technology 863 Program (Grant No. 2007AA041502-5), and the Foundation of the State Key Laboratory of Robotics at SIA (Grant No. RLO201003).

References

Z. M.

and Zhang

W. J.

(2001). Concurrent optimal design of modular robotic configuration. J. of Robot Syst., 18 (2):77–87.

Butler

Kotay

Rus

, and Tomita

(2004). Generic decentralized locomotion control for lattice-based self-reconfigurable robots. Intl. J. Robot. Res., 23(9):919–938.

Casal

and Yim

(1999). Self-reconfiguration planning for a class of modular robots. In Proc. of SPIE Symp. on Intell. Sys. and Adv. Manu., pp. 246–257

Castano

and Will

(2001). Representing and discovering the configuration of CONRO Robots. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp.3503–3509.

Chen

I.-M.

(1994). Theory and application of modular reconfigurable robot systems. Ph.D. Dissertation, Dept. of Mech. Eng., California Institute of Technology.

Chen

I.-M.

and Burdick

J. W.

(1993). Enumerating the non-isomorphic assembly configuration of modular robot systems. In Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp.1985–1992.

Chen

I.-M.

and Burdick

J. W.

(1995). Determining task optimal modular robot assembly configurations. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp.21–27.

Chiang

C.-J.

and Chirikjian

(2001). Modular robot motion planning using similarity metrics. Auton. Robots, 10 (1):91–106.

Chirikjian

(1994). Kinematics of a metamorphic robot system. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp.449–455.

10.

Chocron

and Bidaud

(1997). Genetic design of 3D modular manipulators. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp.223–228.

11.

Duff

Yim

, and Roufas

(2001). Evolution of PolyBot: a modular reconfigurable robot. In Proc. of COE/Super-Mechano-Systems Workshop, 2001.

12.

Fukuda

and Nakagawa

(1988). Dynamically reconfigurable robot system. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp.1581–1586.

13.

Fukuda

and Nakagawa

(1990). Method of autonomous approach, docking and detaching between cells for dynamically reconfigurable robot system CEBOT. JSME Int. J., 33(2):263–268.

14.

Groß

Bonani

Mondada

, and Dorigo

(2006). Autonomous self-assembly in swarm-bots. IEEE Trans. Robot., 22(6):1115–1130.

15.

Hosokawa

Tsujimori

Fujii

Kaetsu

Asama

Kuroda

, and Endo

(1998). Self-organizing collective robots with morphogenesis in a vertical plane. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp.2858–2863.

16.

Inou

Kobayashi

, and Koseki

(2002). Development of pneumatic cellular robots forming a mechanical structure. In Proc. of the Seventh Int. Conf. on Control, Automation, Robotics and Vision, pp. 63–68.

17.

Inou

Minami

, and Koseki

(2003). Group robots forming a mechanical structure—Development of slide motion mechanism and estimation of energy consumption of the structural formation. In Proc. IEEE Int. Symp. on Comput. Intelli. in Robotics and Automation, pp.874–879.

18.

Kotay

Rus

Vona

, and McGray

(1998). The selfreconfiguring robotic molecule. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp.424–431.

19.

Lee

W.H.

, and Sanderson

2001. Dynamic analysis and distributed control of the tetrobot modular reconfigurable robot system. Auton. Robots, 10(1):67–82

20.

Liu

Wang

, and Wang

(2005). Design and experiment of a novel link-type shape shifting modular robot series. In Proc. of IEEE Int. Conf. Robotics and Biomimetics, pp.318–323.

21.

Liu

Wang

, and Ma

(2004). Link-type shape shifting modular robot for search and rescue. High Tech. Lett., 10(Sup):179–183.

22.

Liu

Wang

, and Li

(2008). Network-based reconfiguration routes for a self-reconfigurable robot. Science in China Series F-Information Sciences, 51(10): 1532–1546

23.

Murata

Kurokawa

, and Kokaji

(1994). Self-assembling machine. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp.441–448.

24.

Murata

Kurokawa

Yoshida

Tomita

, and Kokaji

(1998). A 3-D Self-reconfigurable structure. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp. 432–439.

25.

Murata

Yoshida

Kamimura

Kurokawa

Tomita

, and Kokaji

(2002). M-TRAN: Self-reconfigurable modular robot system. IEEE/ASME Trans. on Mech., 7(4):431–441.

26.

Ostergaard

E. H.

Kassow

Beck

, and Lund

H. H.

(2006). Design of the ATRON lattice-based self-reconfigurable robot. Auton. Robots, 21(2):165–183.

27.

Rus

and Chirikjian

G.S.

(2001). Guest editorial: self-reconfigurable robots. Auton. Robots, 10(1): 5–5.

28.

Rus

and Vona

(2001). Crystalline Robots: Self-reconfiguration with compressible unit modules. Auton. Robots, 10(1):107–124.

29.

Shen

W.-M.

Krivokon

Chiu

Everist

Rubenstein

, and Venkatesh

(2006). Multimode locomotion via SuperBot reconfigurable robots. Auton. Robots, 20(2): 165–177.

30.

Støy

(2004). Emergent control of self-reconfigurable robots. Ph.D. Dissertation, The Maersk Mc-Kinney Møller Institute for Production Technology, University of Southern Denmark.

31.

Støy

Shen

W. M.

, and Will

(2002). Using role based control to produce locomotion in chain-type self-reconfigurable robot. IEEE/ASME Trans. on Mech., 7(4):410–417.

32.

Tokashiki

Amagai

Endo

Yamada

, and Kelly

(2003). Development of a transformable mobile robot composed of homogenous gear-type units. In Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 1602–1607.

33.

Ünsal

and Khosla

(2000). Mechatronic design of a modular self-reconfiguring robot system. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp. 1742–1747.

34.

Ünsal

Kiliççöte

, and Khosla

(2001). A modular self-reconfigurable bipartite robot system: implementation and motion planning. Auton. Robots, 10(1): 23–40.

35.

Vassilvitskii

Yim

, and Suh

(2002). Acomplete, local and parallel reconfiguration algorithm for cube style modular robots. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp. 117–122.

36.

Wang

, and Wang

(2006). Configuration analysis for reconfigurable modular planetary robots based on MSV and CSM. In Proc. IEEE/RSJ of the Intl. Conf. on Intelligent Robots and Systems, pp.3191–3196.

37.

Yang

and Chen

I.-M.

(2000). Task-based optimization of modular robot configuration: minimized degree-of-freedom approach. Mech. Mach. Theory, 35(4):517–540.

38.

Yim

(1994). Locomotion with a unit modular reconfigurable robot. Ph.D. Dissertation, Dept. of Mech. Engg., Stanford University.

39.

Yim

Duff

, and Roufas

(2000a). Modular reconfigurable robots, an approach to urban search and rescue. In Proc. of 1st Intl. WorkShop on Human-friendly welfare Robot systems, pp.69–76.

40.

Yim

Duff

, and Roufas

(2000b). Polybot: a modular reconfigurable robot. In Proc. of IEEE Int. Conf. on Robotics and Automation, pp.514–520.

41.

Yim

Roufas

Duff

Zhang

Eldershaw

, and Homans

(2003). Modular reconfigurable robots in space applications, Auton. Robots, 14 (2–3): 225–237.

42.

Yoshida

Murata

Kamimura

Tomita

Kurokawa

, and Kokaji

(2002). A self-reconfigurable modular robot: reconfiguration planning and experiments. Intl. J. Robot. Res., 21(10):903–916.

43.

Yoshida

Murata

Kokaji

Tomita

, and Kurokawa

(2000). Micro self-reconfigurable robotic system using shape memory alloy. In Distributed Autonomous Robotic Systems 4, pp.145–154.

44.

Yoshida

Murata

Kurokawa

Tomita

, and Kokaji

(1998). A distributed reconfiguration method for 3-D homogeneous structure. In Proc. IEEE/RSJ of the Intl. Conf. on Intelligent Robots and Systems, pp. 852–859.

45.

Zykov

Mytilinaios

Adams

(2005). Self-reproducing machines. Nature, 435(7038):163–164.

Number of modules (j)	Number of non-isomorphic configurations in N_g(j)	Number of symmetrical non-isomorphic configurations in S_g(j)	Number of available configurations in C_g(j)	CPU time(s)
1	1	1	1	0
2	1	1	4	0.078
3	3	2	6	0.125
4	7	3	24	0.563
5	21	7	68	2.828
6	60	10	248	28.938
7	208	24	814	273.547
8	704	36	3216	3969.403
9	2542	86	12164	56943.825

Enumeration of the Non-Isomorphic Configurations for a Reconfigurable Modular Robot with Square-Cubic-Cell Modules

Abstract

Keywords

1. Introduction

2. Representation and definition

2.1. A single SCC module description

Available configuration matrix Mi(j)

Available configuration matrix group Cg(j)

Non-isomorphic configuration matrix Ni(j)

Non-isomorphic configuration matrix group Ng(j)

Symmetrical non-isomorphic configuration matrix group Sg(j)

3. Enumerating algorithm of the non-isomorphic configuration for a multi-module SCC system

Step 1: Pre-processor

Step 2: Operation and solution

Step 3: Post-processor

Footnotes

6. Acknowledgments

References