A novel distributed meta-module motion design for modular robotic systems based on grid partition method

Abstract

This article studies a meta-module motion design approach for homogenous modular robotic systems in self-configuration. By utilizing configuration diversity, scalability and unit-substitutability, homogenous modular robotic systems can be a promising approach to life detection and space exploration in the future. Based on the requirements of the potential applications, self-configuration can be considered as the precondition. As similar to swarm robotic systems, the distributed control strategy in which the modular robots are operated in a sequence of motion circles consist of ‘detection’– ‘decision’– ‘execution’ is of great significance. However, there is a limitation to the applicability of previously proposed work on the self-configuration topic, due to the fact that the self-configuration strategy execution suffers from the motion constraints of modular robots. In order to solve the problem, we propose a grid partition method that removes the gap between the locomotion of a single modular robot and the reconfiguration of the whole system. Under the analysis of the grid partition, the meta-module motion design is proposed to realize the distributed self-configuration strategy. We simulated the self-configuration in M-Lattice, a two-dimensional homogenous modular robotic system.

Keywords

Homogenous modular robotic system self-configuration grid partition meta-module motion design

Introduction

Homogenous modular robotic systems (H-MRSs) are formed by lots of interconnected isomorphic modular robots(modules). Most research on H-MRS has focused on module design and self-reconfiguration control strategies.^1–3 Self-configuration can be considered as the precondition for the engineering applications in H-MRS, and it is a subset of the self-reconfiguration issue, which was first proposed by Terada and Murata⁴ by using a heterogeneous modular robotic system. Unlike during self-reconfiguration, where all of the modules maintain connection throughout a whole period, the system scale is increased by importing new modules from a certain supply area. Generally, the distributed control strategy in which the robots are operated in a sequence of motion circles consist of ‘detection’ – ‘decision’ – ‘execution’ is efficient for swarm robotic systems with huge system scales. However, in H-MRS, the instantiation of the distributed control strategy suffers from the module's motion constraints. In this work, we attempt to solve this problem and realize the self-configuration in H-MRS.

In the field of module design, H-MRS modules belong to a lattice-type^5,6 or chain-type geometry.^7–9 Generally, the reconfiguration modes of these two types of H-MRSs are different. In a chain H-MRS, the connection between adjacent modules does not change, and the reconfiguration which equals to locomotion in most cases is realized by the combination of modules’ shape changes. In a lattice H-MRS, the modules can change their positions by connecting with different modules and that leads to the shape change of the system which does not only mean locomotion. Meanwhile, there are also H-MRSs,^10,11 known as hybrid-type, which can realize both lattice and chain reconfigurations. From the viewpoint of the module's shape change, most H-MRS modules are rigid. That means the size of the module is certain and the modules are close-packed in the system. Thus the module's locomotion only happens along the system boundary. However, some H-MRSs^12,13 can be unit-compressible. This makes it possible to realize module locomotion within the system.

The self-configuration task with a changeable system scale can be treated as a sequence of self-reconfiguration tasks with an unchangeable system scale. The previous self-reconfiguration strategies have a reference significance in the theoretical design.¹⁴ Among the self-reconfiguration strategies, the centralized strategies^15,16 calculate the configuration distance come from the comparison between the target configuration and the current configuration, and then drive the locomotion of certain modules to minimize the configuration distance. In the distributed strategies, such as the gradient-based method,¹⁷ k-BFS sum-sweep algorithm,¹⁸ artificial neural networks with pruning technology¹⁹ and the unique one-dimensional (ID) assignment method based on the energy and time complexity optimization,²⁰ it is generally assumed that only local communication is valid between connecting modules. That means the components of control strategies for self-configuration such as detection for potential target positions, decision from path planning, and execution for the module's locomotion, need to be designed carefully to meet the module's ability both in sensing, communication, and movability.

To evaluate the performance of self-reconfiguration strategies, such as reconfiguration rate or efficiency, graph theory is an effective theoretical approach to establish a mathematical model between the local deformations caused by the change in a single module's shape or the connectivity relationships among module groups and the system reconfigurations. A common usage is to define individual modules as nodes and modules’ connectivity relationships with each other as edges.²¹ The position of the node can be represented by a Cartesian coordinate system and the change in connectivity can be represented by a change in the state of the edge. Then the reconfiguration strategies can be designed under the system graph. In chain H-MRSs, Liu et al.²² focused on geometry reconfiguration actions, and presented the fast configuration algorithm for H-MRSs. By utilizing the kinematics graph,²³ the motion planning and constrains coming from environment obstacles can be treated as a linearly constrained quadratic program which can be solved efficiently. In lattice H-MRSs. based on the distributed density-cut graph algorithm, Bassil et al.²⁴ divided modules into different clusters, and the proposed self-reconfiguration strategy reduced the time complexity. In the design of self-reconfiguration strategies, it is also possible to consider current system configurations as nodes and deformation actions as edges. In two facet-connected square-grid configurations, Akitaya et al.²⁵ proposed the reconfiguration analysis under the reconfiguration graph in which vertices represented facet-connected configurations and edges represented valid pivot moves. Inspired by previous works, graph theory is used to describe the system configuration. By utilizing the structural characterization of the modular robots, the structural features of the system and the positional representation laws of the nodes can be obtained.

The module's limited movability is the major factor of locomotion failure. To enhance the movability, certain connecting modules can be treated as one special module, called a meta-module. Several studies on meta-module motion have been published in the literature. One primary motion mode for meta-modules is crawling along the system boundary.²⁶ Parada et al.²⁷ gave a meta-module design to realize expand and contract motions with rigid modules and showed the criterion of minimum scale of the meta-module in tunneling algorithms for reconfiguration. The max-flow algorithm^28,29 is designed for porous meta-module motion under the purely geometric model. With the centralized global planner, the reconfiguration process can be realized efficiently. In this work, we presented a novel distributed meta-module motion design under the structural features of the system.

In our previous work,³⁰ we introduced a unit-compressible modular robot named M-Lattice. Inspired by previous studies, the meta-module motion mode was designed and a self-configuration strategy was presented. As the module design of H-MRS is different, it is meaningful to find a general analysis method to guarantee the self-configuration accessibility during the module design process. That will also provide solutions to designing the meta-module motion and realizing the self-configuration strategy in a distributed mode.

The main contributions of this work can be presented with reference to two aspects:

Self-configuration accessibility analysis based on grid partition method: The grid partition method is proposed for the self-configuration accessibility analysis, inspired by the grid partition in navigation for mobile robots. We improve the grid partition method by utilizing the features of H-MRSs and graph theory. Based on the geometric symmetry of modules in an H-MRS, there exists a regular grid unit in which one module takes the position of one vertex and the edge means the connection of adjacent modules. The shape of this grid unit depends on geometric factors, such as the module's degree of freedom and the connection of adjacent modules. It can be found that the system configuration can be described as the distribution of modules within grid units. Then the system reconfiguration can be turned into a sequence of grid transformations which means the redistribution of modules in each grid unit. Under the grid partition, the self-configuration accessibility can be evaluated according to the accessibility of the grid transformation.

Meta-module motion planning for self-configuration: To realize the grid transformation, the requirements of the distributed self-configuration strategy design can be obtained, such as the minimum detection range, the target decision principle, and the movability. In this work, the meta-module motion is designed to meet these requirements. Then the self-configuration task can be accomplished by meta-modules operating the same control program in a distributed manner.

The organization of the work is as follows: the “Self-configuration completeness criterion” section describes the grid partition method and self-configuration accessibility analysis. The “Meta-module motion design for self-configuration” section shows the meta-module motion design and realization of the distributed self-configuration strategy. The “Simulations” section presents the simulation results. The “Results and discussion” section discusses the disadvantages and potential further research. The conclusions are given in the “Conclusions” section.

Self-configuration completeness criterion

One challenge for self-reconfiguration in H-MRSs is how to deal with the motion constraints during the modules’ locomotion. The motion constraints can be divided into two kinds: local constraint and global constraint.

As shown in Figure 1, in local constraint, if module C wants to move to E by rotating with B, Position D needs to be empty. And in global constraint, if module A is chosen to be moved, the system will be split. It can be concluded that local constraint is generally determined by a module's motion mode, and global constraint is caused by the structural characteristics of the H-MRS and the module selection which comes from the reconfiguration strategy. The motion constraints are the preconditions of the self-configuration strategy design.

Figure 1.

Motion constraints in homogenous modular robotic system (H-MRS).

Grid partition method

During navigation for mobile robots, the workspace can be described as a combination of regular grids. If one grid contains boundaries of the workspace or unexpected obstacles, it will be marked as closed. Regarding self-configuration, the grid partition method is improved as a bridge between system configuration, structural features, and the motion range of a single module. In the H-MRS configuration space, the regular grid is also homogenous, and is marked as a grid unit. The grid unit is a regular convex polygon with the following properties:

The vertex of the grid unit represents the potential position for a single module.

The edge of the grid unit represents the potential connection of adjacent modules.

The same vertex or edge can be shared by adjacent grid units, but there is no overlapping area within adjacent grid units.

An example of square modules with four arms is shown in Figure 2. As a single module has four arms and the angle between adjacent arms is 90°, the shape of the grid unit is also square. One gird unit can hold a maximum of four modules. If two modules in one grid unit can keep a connection, then an edge between two vertices exists. Like the workspace of mobile robots, the grid units containing boundaries or unknown obstacles cannot rearrange the modules at vertices, but these modules can be rearranged within adjacent normal grid units. The grid units can be classified into three types: occupied, connected half-occupied, and disconnected half-occupied. The difference between connected half-occupied and disconnected half-occupied is the existence of more than one connective module chain in the grid unit.

Figure 2.

Grid partition in homogenous modular robotic system (H-MRS).

First, some definitions are given in order to analyze the reconfiguration description.

Definition 1:

The target configuration of the H-MRS is represented as a relative vertex index map, designated RI . The form of the map RI is shown as follows:

R I = [\begin{matrix} s_{11} & \dots & s_{1 n} \\ ⋮ & ⋱ & ⋮ \\ s_{m 1} & \dots & s_{m n} \end{matrix}]

where each element in RI represents a 2D or 3D position that can be occupied by one module. If the H-MRS is a 2D system, s_ij represents the state of the current vertex. A 0 means the position is open, 1 means it is occupied by a module, and −1 means the position is closed. This can be caused by obstacles or be preordered for special configurations.

Definition 2:

The connection states of adjacent modules are represented by the adjacent edge map, designated AE .

A E = [\begin{matrix} \begin{matrix} s_{11} & \dots & s_{1 j} & \begin{matrix} \dots & s_{1 k} \end{matrix} \end{matrix} \\ \begin{matrix} ⋮ & \begin{matrix}  \end{matrix} & ⋮ & \begin{matrix} \begin{matrix}  \end{matrix} & ⋮ \end{matrix} \end{matrix} \\ \begin{matrix} s_{i 1} & \dots & s_{i j} & \begin{matrix} \dots & s_{i k} \end{matrix} \end{matrix} \\ \begin{matrix} ⋮ & \begin{matrix}  \end{matrix} & ⋮ & \begin{matrix} \begin{matrix}  \end{matrix} & ⋮ \end{matrix} \end{matrix} \\ \begin{matrix} s_{h 1} & \dots & s_{h j} & \begin{matrix} \dots & s_{h k} \end{matrix} \end{matrix} \end{matrix}]

(1)

As shown in formula (1), there are h modules in the system, and one module has k connectors. s_ij represents the j-th adjacent position state of i-th module. A 0 means the position is open, 1 means it is occupied by a module, and −1 means the position is closed.

Based on Definitions 1 and 2, the configuration of the H-MRS can be represented as an undirected graph G = ( RI , AE ), where RI is a map that shows the current system configuration, and AE is the adjacent edge map representing the connection status of modules. If the target configuration is defined, the target G is certain. The reconfiguration process is then transformed into a process to convert the current G to the target G . As the selection accuracy of the potential target open vertex may suffer from the local optimization and unexpected obstacles, we attempt to turn the current G to the final G which has the minimum error to the target G . In a distributed control manner, only local communication is available. Then the connection state of a single module that has k connectors can be represented as

A d j P = [\begin{matrix} A_{1} \\ ⋮ \\ A_{i} \\ \begin{matrix} ⋮ \\ A_{k} \end{matrix} \end{matrix} \begin{matrix} S_{1} \\ ⋮ \\ S_{i} \\ \begin{matrix} ⋮ \\ S_{k} \end{matrix} \end{matrix}]

(2)

where A_i represents the vertex position belonging to the i-th connector of the module. For a 2D system, it can be ( x , y ), and for a 3D system, it can be ( x , y , z ). s_i represents the state of the i-th adjacent position. A 0 means the position is open, 1 means it is occupied by a module, and −1 means the position is closed.

Self-reconfiguration accessibility analysis

The requirement of self-reconfiguration is that modules can be relocated to the target positions in the system by themselves. The morphological change in the recon-figuration can be described by:

G (n + 1) = T r a n s (G (n), G^{'} (n))

(3)

where G(n) is the current system configuration, G(n + 1) is the next system configuration, and Trans() is the transform function which checks whether the reconfiguration is valid. Gʹ(n) is the transformation strategy for the reconfiguration.³⁰ In a distributed control manner, the valid transformation strategy means that the next target configuration is reachable when the local constraint, the global constraint, and the limited range of sensing and motion are satisfied.

Under the grid partition in H-MRS, if the configuration space can be divided into m grid units, the system configuration can be described as

G (n) = ⋃_{i = 1}^{m} g_{i} (n)

Formula (3) can be rewritten as formula (4), utilizing grid transformation.

G (n + 1) = \sum_{i = 1}^{m} T r a n s (g_{i} (n), g_{i}^{'} (n))

(4)

where g_i(n) is the current configuration of the i-th grid unit, and gʹ_i (n) is the transformation strategy for the i-th grid unit.³⁰

If the transformation in each grid unit is valid, the next target configuration is reachable. As shown in Figure 3, the grid transformation caused by single-module loco-motion can be divided into two kinds:

Stable transformation. This means that, during the grid transformation, the number of the containing modules does not change. In G 2, although the red module changes its position, the number of G 2 is 3.

Unstable transformation. This means that, during the grid transformation, the number of the containing modules changes. In G 1, the number of modules changes from 2 to 1. The number of modules changes from 3 to 4 in G 3, and from 2 to 3 in G 4.

Figure 3.

Two types of grid transformation.

Unstable transformation within adjacent grids can be considered the marginal effect of one stable transformation. If all of the stable transformations are valid, the target system reconfiguration will be reachable. If there are j grids with stable transformation among m grids in formula (4), it can be rewritten as formula (5):

G (n + 1) = \sum_{i = 1}^{j} T r a n s (g s_{i} (n), g s_{i}^{'} (n))

(5)

where gs_i(n) is the current configuration of the i-th stable transformation grid, and gsʹ_i (n) is the transformation strategy for the i-th stable reconfiguration grid.

It can be concluded that under the motion constraints, under the motion constraints, the self-reconfiguration accessibility criterion for H-MRS can then be concluded as follows: If an arbitrary detectable open vertex is accessible in one grid unit for a single moveable module, the arbitrary detectable open vertex in the current configuration is accessible for a single moveable module, and the reconfiguration containing this module's locomotion is accessible.

Firstly, if the number of moveable modules is one, the varying scale of the reconfiguration is one. Using formula (5), the continuous process of arbitrary varying scale reconfiguration can be described as a discrete series that consists of reconfigurations of adjacent grid units, marked as

G (n + N) = Π_{k = 1}^{N} (\sum_{i = 1}^{j} T r a n s (g s_{i + k} (n + k), g s_{i + k}^{'} (n + k)))

(6)

As the varying scale is one, formula (6) can be rewritten as formula (7):

G (n + N) = \prod_{k = 1}^{N} T r a n s (g s_{i} (n + k), g s_{i}^{'} (n + k))

(7)

If arbitrary

T r a n s (g s_{i} (n), g s_{i}^{'} (n))

is valid, then formula (7) is valid and reconfiguration is accessible.

On the contrary, the locomotion of a single module is a sequence of grid transformations containing stable transformations and unstable transformations. As previously mentioned, the locomotion can be marked by stable transformations as

\prod_{k = 1}^{N} T r a n s (g s_{i + k} (n + k), g s_{i + k}^{'} (n + k))

From the definition of a grid unit, an arbitrary open vertex in a grid unit belongs to the system. If an arbitrary open vertex in the system is accessible for a single module, then the arbitrary open vertex in a certain grid unit is accessible for the same module. This means there exists a valid strategy for the stable transformation.

Meta-module motion design for self-configuration

If we ignore the efficiency issue, the self-configuration of an H-MRS can be simplified to a sequence of motions containing two parts. One is the system scale change caused by importing new modules in the supply area. The other one is the self-reconfiguration within a fixed-scale system. That requires the module motion to satisfy the self-reconfiguration accessibility criterion under the motion constraints. If a single module cannot meet the requirements for self-configuration, the meta-module can be an efficient solution. The meta-module is a special kind of ‘module’, which consists of several modules maintaining a connection. In this work, we introduce how the meta-module motion works in a distributed self-configuration strategy design in an H-MRS. Our previous work, M-Lattice³¹ is chosen to explain this process.

M-Lattice system introduction

As shown in Figure 4, M-Lattice is a unit-compressible module. Each module consists of one center prism frame and three mechanical arms containing two DOF and one connector. Under the pin-slot mechanism design, the reliable connection of adjacent modules can be guaranteed by rotation of the pin-slot pair. The topological structure of M-Lattice is a 2D plane and its grid unit is a regular hexagon. Inspired by the Dijkstra method,³² we use the relative integer-valued number to describe the distance between adjacent modules. Then the grid vertex means the potential position of a single module can be represented by an ordered pair of integers ( x , y ), where x represents the row of the module's location and y represents the column of the module's location.

Figure 4.

M-Lattice system and single-base and multi-assistant (SBMA) motion.

The locomotion of the M-Lattice module is realized by the attach/detach operations and the rotations of mechanical arms, which belong to a sequence of connecting modules. The scale of the module sequence is pertinent to the initial position and the target position. This motion is known as single-base and multi-assistant (SBMA) locomotion, as one module, called the ‘Base’, remains connected with the system, while the other modules, called ‘Assistants’, realize the module's relocation.

Distributed self-reconfiguration strategy execution

There are two kinds of modules in the self-reconfiguration task. One is called the system module which has existed as part of the system already. The other one is the moving module which means the meta-module in this work. Then the self-reconfiguration needs to be realized by a sequence of modules’ motion circles, containing ‘detection’ – ‘decision’ – ‘execution’. The distributed self-reconfiguration strategy needs to be executed by meta-modules, as shown in Figure 5.

Figure 5.

Distributed motion circle.

Detection

The goal of the detection is to find all of the potential vertices within a certain local range. In an H-MRS, local messages can be transmitted through connecting modules in a serial mode. It is assumed that an open vertex can only be detected by its adjacent module, the potential transformed grid unit should at least contain one meta-module member and one system module. Thus, the detection depth is at least N−2, where N is the number of the grid vertices. In the M-Lattice system, the search depth is 4.

During the detection, a search message that has a limited transmitting range is generated by meta-module members and sent to their adjacent system modules. If one open vertex is detected, this probe module will generate a feedback message and send it to its adjacent system modules. If one feedback message reaches one meta-module member, this open vertex is added into Path, defined as:

P a t h = [\begin{matrix} T g_{1} \\ T g_{2} \\ ⋮ \\ T g_{n} \end{matrix} \begin{matrix} S y s_{1} \\ S y s_{2} \\ ⋮ \\ S y s_{n} \end{matrix} \begin{matrix} M e t a_{1} \\ M e t a_{2} \\ ⋮ \\ M e t a_{n} \end{matrix}]

where Tg_i represents the i-th open vertex; Sys_i is the system module, which is adjacent to the i-th open vertex; and Meta_i is the meta-module member receiving the responding message for the i-th open vertex.

Decision

Each open vertex Tg_i is checked for a grid unit containing Tg_i, Sys_i, and Meta_i. Then, the optimal open vertex is chosen as the target vertex. The gradient method is used to make sure the target vertex is as far as possible from the supply area.

The meta-module member which is nearest to the entrance is chosen as the reference point. The vector from the reference point to each open vertex and the vector from the reference point to the far-end boundary of the target configuration can be found. Then, the gradient of each open vertex can be calculated, and the target vertex can be chosen out of some vertices with the same gradient according to Boltzmann's law.

Execution

The goal of the execution is to drive one meta-module member into the chosen vertex comes from the decision section. In this part, we focus on the meta-module motion design to realize this execution.

Meta-module's scale: Under local communication, the open vertex can be detected only if there exists one module in its adjacent vertex. The transformed grid unit can be confirmed when it contains a target vertex, the moveable module, and the probe vertex adjacent to this target vertex. If the number of grid vertices is N, the minimum scale of the meta-module should be N−2, which means one of the meta-module members can reach an arbitrary open vertex within one grid unit without moving the existing system modules. Thus the meta-module scale is 4 in M-Lattice.

Meta-module's locomotion: The locomotion of the meta-module can be described as a sequence of stable grid transformations. Some definitions are given firstly:

Target grid: This contains at least one meta-module member, the target vertex, and the probe module which does not belong to the meta-module. There is also a module chain within this grid between the meta-module member and the probe module.

Tail module: This module is a meta-module member within the target grid. One of its adjacent vertices within the target grid is open.

Head module: This module is a meta-module member within the target grid. One of its adjacent vertices within the target grid is a system module.

Transitional grid: This is confirmed by the tail module vertex, the open vertex adjacent to the tail module vertex within the target grid, and the vertex adjacent to the tail module vertex outside of the target grid.

As shown in Figure 6, the target grid and transitional grid are adjacent. By driving meta-module members into the target grid, the member chain can make the target vertex occupied by one member. As there may be fewer current open vertices in the target grid than the number of meta-module members outside of the target grid, we firstly drive the members which do not belong to the target grid into the transitional grid, then lead the proper members moving into the target grid. The motion pattern consists of two parts: transitional grid combination and transitional grid separation. The pseudo-code is shown as follows:

Figure 6.

Combination and separation of meta-module motion.

-------------------------------------------------------------------------------------------------------

Combine Progress ( Target-Grid , Transitional-Grid, Grid Search, SBMA Movement)

-------------------------------------------------------------------------------------------------------

CombineCheck ← 1

CombineFail ← 0

for i = 1: metaNum

Test meta(i) from Head module to Tail module

if meta(i) is not in Target-Grid and meta(i) is not in Transitional-Grid

CombineCheck ← 0

end if

end for

while (CombineCheck = 0) and (CombineFail = 0 )

Find tempGrid by Grid Search

Execute the movement in tempGrid by SBMA Movement

if the movement fails

CombineFail ← 1

else

CombineCheck ← 1

for i = 1: metaNum

if meta(i) is not in TargetGrid and meta(i) is not in Transitional-Grid

CombineCheck ← 0

end if

end for

end if

end while

-------------------------------------------------------------------------------------------------------

Seperate Progress (Target-Grid, Transitional-Grid, Grid Search, SBMA Movement)

-------------------------------------------------------------------------------------------------------

SeperateFail ← 0

Find TargetMetaNum from Target-Grid

tempMetaNum ← 0

for i = 1: metaNum

if meta(i) is in TargetGrid

tempMetaNum ←tempMetaNum + 1

end if

end for

while (tempMetaNum < TargetMetaNum) and (SeperateFail = 0 )

Find tempMetaUnit from Transitional-Grid

while tempMetaUnit is not in Target-Grid

Find tempGrid by Grid Search

Execute the movement in tempGrid by SBMA Movement

if the movement is fail

SeperateFail ← 1

end if

end while

tempMetaNum ← 0

for i = 1: metaNum

if meta(i) is in TargetGrid

tempMetaNum ← tempMetaNum + 1

end if

end for

end while

(3) Meta-module's termination: If a meta-module can’t move any further which may be caused by an unexpected obstacle or failure in detecting target vertices, it will come into the termination stage. The termination means the redistribution of meta-module members within adjacent grid units. That makes the movable modules into system modules which also means the scene of self-reconfiguration with the current system scale is finished. In the M-Lattice system, the termination of the meta-module follows three rules:

Using the traversal method, find the optimal member as the termination seed. This means this member is connecting with a system module, and it occupies an optimal vertex which is determined by the decision strategy.

Check all the vertices within the adjacent grids containing the termination seed, and generate the TargetList which keeps all the open vertices in the configuration gradient order. Drive outside members into these grids and generate the OrgList which contains all the members in the configuration gradient order.

Compare TargetList and OrgList. If there exists a better open vertex, choose this open vertex as the target and drive one member into this vertex. If this process is valid, turn this member into a system module, and refresh TargetList and OrgList. If there is no target, turn all the members into system modules.

The completeness of the meta-module motion

As mentioned previously, motion constraints including local constraint and global constraint are the prerequisite for the study of self-reconfiguration. Local constraint mainly depends on the motion capability of a single module. When the motion capability is not enough to realize the target motion which drives the module from the current vertex to the target vertex, it can be improved by using meta-module motion. Meanwhile, the selection of the target position is also a key factor in determining whether the motion is reachable or not. In the self-reconfiguration task, if the system modules are required to participate in the locomotion of movable modules which may lead to the connection changes of system modules, it may trigger the global constraint, such as the system breakage. When the system scale is small, the system breakage can be avoided by the central controller. However, in distributed control strategies operating in large systems, it is difficult to accurately determine whether a change in the connectivity of system modules will trigger a global constraint.

In this work, we analyze the self-configuration by grid partition to solve the motion constraint problems by meta-module motion. Through the grid partition, we transform the system reconfiguration into a finite number of stable grid transformations. From the viewpoint of the grid unit level, for a single module to be able to reach arbitrary vertex within a grid unit under a distributed control strategy, it needs to be able to detect arbitrary detectable empty vertex within the grid unit, as well as to be able to reach this vertex through motion planning. In the detection part by means of distributed message exchange, the range of the delivery message can be determined by the maximum length of the module chain within the grid unit. In the motion planning part, in order to satisfy the global constraint, the ideal situation is that the system modules are not involved in the module's locomotion. That means the current system module connectivity is unchanged, and it is clear that a break in the system is not possible. And the lack of motion capability of a single module can to be filled by means of a meta-module in which a chain of meta-module members ensures that one of the meta-module members is able to move to the target vertex.

Simulations

A simulation for evaluating the self-configuration was built on MATLAB. The workspace was set as a rectangle. The supply area was in the left bottom corner. The meta-module consists of four modules, which were taken into the working space from the module supply area. After one meta-module was terminated, the next meta-module started to move. If the entrance was blocked by system modules, one simulation round was finished.

Under the grid partition, the self-reconfiguration can be realized by a sequence of stable grid transformations, the scale of stable grid transformations was chosen to reflect the self-reconfiguration process. From the SBMA motion in M-Lattice, one stable grid transformation requires morphologic changes of meta-module members including rotation and extension, and one pair of connection and disconnection. In a distributed control strategy, these motions are driven by messages transmitted between connection modules.

Inspired by the Digital Hormone Model (DHM),³³ the message is transmitted between connecting modules by serial communications in the frame of Msg(motion, life, dir, data, event), where motion means the specific task driven by the message, life is the life of the message which is decreased by one when this message passes through one module and if life is decreased to zero, the message will drive the module to the event , event may be the generation of one new message or the execution of meta-module motions, dir means the direction which the message is transmitted to. Three kinds of DHM messages are used and counted in the simulations.

The message Move drives the rotation and extension of modules, marked as Msg(move, life, dir, data, event). As mentioned in the “Distributed self-reconfiguration strategy execution” section, move means combination or separation. life is determined by the number of meta-module members within the current SBMA motion. dir is determined by the adjacent meta-module member within the tempGrid. data contains the rotation angle determined by the SBMA motion. event is to generate a message Connect in combination or drive the meta-module to the next detection round in separation.

The message Connect drives the connection or the disconnection between connecting meta-module members, marked as Msg(connect/disconnect, life, dir, data, event). life is determined by the number of meta-module members between the message generator with the connection or the disconnection position. dir is determined by connection or disconnection direction. data is null. event is to generate a disconnect message in a connect message or a message Connect for separation in a disconnect message.

The message Search reflects the detection process, marked as Msg(search/return, life, dir, data, event). search means this message is searching for the open vertex. return means this message contains one open vertex. life means the depth of the search range, and it can be set as 4 in M-Lattice. dir is chosen as all of the connecting directions. data contains the positions of the open vertex in a return message and null in a search message. event is to generate a return message in a search message or make the data to be recorded if the current module is one meta-module member.

Accessibility evaluating without obstacles

In order to test the self-configuration accessibility, we selected three target configurations. The motion constraints were monitored by the simulator. If a collision happened, the current locomotion would be shut down and the configuration task was considered as a failure. The black modules show the distribution of the first meta-module to the thirty meta-module. The blue modules show the distribution of the 31 meta-modules to the 60 meta-modules. The red modules show the distribution of the rest meta-modules. As shown in Figure 7, the self-configuration accessibility with smoothing edges can be guaranteed.

Figure 7.

Simulation to evaluate accessibility: (1) rectangle configuration; (2) Type-1 configuration, and (3) Type-2 configuration.

To evaluate the scalability of self-configuration, the target configuration was set as a rectangle with different scales from 100 to 3600 modules. The simulations were repeated 20 times for each system scale. As shown in Figure 8, the scale of stable grid transformations involved in self-configuration grows approximately exponentially with the scale of modules. By analyzing the stable grid transformations, the meta-module behavior in self-configuration can be approximated. Additionally, this can be considered as a characterization factor for the system's scalability.

Figure 8.

Scalability of self-configuration analysis.

The proportional distribution of each type of motion message can be obtained, as shown in Figure 8. The simulation results show that Move messages occupy the largest proportion. We believe that in the distributed control strategy, due to the lack of a central controller, even if the module moves in the form of a small meta-module, a large number of messages need to be exchanged to drive the morphological changes. Therefore, if the self-configuration efficiency of the system needs to be improved, the manner of message exchange should be more effective. Search messages make up the second largest proportion. This is because the system module only transmits the search message to the adjacent modules within the search depth and does not check whether its adjacent open vertex is reachable to the meta-module. As it is unreasonable to let one system module check the existence of a grid unit containing one meta-module member and this open vertex, the self-configuration efficiency suffers from the search motion.

Robustness evaluating

In order to test the robustness of the self-configuration process, obstacles which were chosen as a rectangle occupying the space from 2 × 2 to 5 × 5 modules were randomly located in the configuration space. The target system scale was 20 × 20. The self-configuration rate is defined by the percentage between the amount of modules in the final configuration and the required amount of modules in the target configuration.

The self-configuration processes with obstacles are shown in Figure 9. The black modules show the distribution of the first meta-module to the 25th meta-module. The blue modules show the distribution of the 26th meta-module to the fiftieth meta-module. The red modules show the distribution of the rest meta-modules. As the obstacle may lead to failure of the finite motion for the meta-module, this will drive the meta-module into the termination process. After the termination, meta-module members become system modules surrounding the obstacle as a scaffold for the following meta-modules. When the distance between two obstacles was more than one grid unit, the self-configuration rate was higher than 96%.

Figure 9.

Self-configurations with obstacles: (1) one 5 × 5 obstacle with 98.9%; (2) two obstacles 2 × 2, 4 × 4 with 99.7%; (3) three obstacles 2 × 2, 4 × 4, 5 × 5 with 96.1%; and (4) four 5 × 5 obstacles with 97.7%.

As shown in Figure 10, when the distance between the obstacle and the boundary or between two adjacent obstacles is too small, the self-configuration rate appears to be reduced. This distance can be typically found as one grid unit. The influence of obstacles distributed along the Y-axis is greater than the X-axis on the self-configuration rate. As shown in Figure 11, this influence presents a more obvious effect as the scale of the obstacles becomes larger. From the meta-module movement point, the locomotion of the meta-module needs to be accomplished by SBMA motions with the help of system modules. If the space is not sufficiently caused by the obstacles, the locomotion will fail for some target vertices. From the path planning point, the gradient method drives the meta-module far from the entrance which leads to the vertices close to the obstacles will not be selected as the target, resulting in a decrease in the self-configuration rate. We attempt to solve this path planning issue by the optimization of meta-module termination strategy which is discussed in the results and discussion.

Figure 10.

Self-configurations with two 3 × 3 obstacles: (1) distribution along the Y-axis with 90.8% and (2) distribution along the X-axis with 97.6%.

Figure 11.

Self-configurations rate from 2 × 2 to 5 × 5 obstacles.

Results and discussion

From the simulations, it can be found that the self-configuration under meta-module motion has good scalability for the regular targets, with nearly the same rate for Move, Search, and Connect messages at 43.0%, 39.7%, and 17.3%. Without the obstacles, the self-configuration rate is 100% with different scales from 100 to 3600 modules. When the obstacles exist in the configuration space, the meta-modules can form a scaffold surrounding the obstacles. Then the following meta-module locomotion will not be affected and the configuration rate with the sparse distribution of obstacles is higher than 96% which means the self-configuration has good robustness.

The proposed meta-module termination strategy chooses the meta-module member on the optimal vertex as the termination seed and arranges the other meta-module members within the grid units which contain the termination seed in order of gradient priority. As global constraints are not effectively perceived in distributed control mode, the current termination strategy can minimize the global constraints triggered by the system modules participating in SBMA motion which only involves meta-modules in general grid transformation. In addition, it is important for meta-module termination to facilitate the subsequent meta-module motion. This increases the probability of finding a valid transformation strategy and means that disconnected half-occupied grid units need to be avoided. This issue is key to the optimization of the meta-module termination strategy in further research.

In the current self-configuration process, it is assumed that the target configuration is rectangular. Thus, a gradient approach can be used to evaluate the potential open vertices leading to meta-modules far from the supply area. However, in cases where the target configuration is irregular or changes dynamically, the fixed gradient approach may not work. In such cases, the heuristic algorithms such as reinforcement learning algorithms should be considered to evaluate the potential open vertices, local constraints, and global constraints in a multi-parameter conditional optimization. In addition, if a heuristic algorithm is used, a distributed asynchronous location–state information update method needs to be designed to achieve the state update with a single module's limited communication ability.

Although the current work is not focused on purely geometric models only, it does not consider the influence of dynamics in the self-configuration strategy. The influence is mainly reflected in the effect of gravity on the module's actuators during SBMA motion. This may also effect the evaluation of the potential open vertices, as the distribution of modules can change the mass distribution of the current system and the load capacity of a single module is limited. We attempt to optimize the path planning to decrease this influence in future work.

Conclusions

In this article, we proposed a general analysis method for self-configuration accessibility in H-MRSs. In order to reduce conflict from local and global constraints, the grid partition method is introduced to turn the self-configuration process into a sequence of stable grid transformations. The proposed method consists of two parts: the self-reconfiguration accessibility criterion, which evaluates the system reconfiguration completeness according to the accessibility of stable grid transformation, and the meta-module motion design, which guarantees that the stable grid transformation can be realized by the H-MRS in a distributed manner. We examined the proposed method in the M-Lattice system. In the simulations, we used the amount of the stable grid transformations and local communication messages to describe the ‘detection’ – ‘decision’ – ‘execution’ motion circles. The scalability and robustness of the self-configuration strategy were also tested.

Footnotes

Acknowledgements

This research was funded by the National Natural Science Foundation of China, grant numbers 52105267 and 61806124.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (grant numbers 52105267 and 61806124).

ORCID iDs

Enguang Guan

Yao Wang

Author biographies

Enguang Guan received his bachelor's degree in Automation (2006) and master's degree in Detection Technology and Automatic Equipment (2009) from Harbin Engineering University. He received his PhD degree in Mechanical Engineering (2016) from Shanghai Jiao Tong University. He is currently working at Shanghai Maritime University. His research interests include modular robotic system control, swarm intelligence theory and climbing robot design.

Yao Wang is currently a faculty of the Logistics Engineering College at Shanghai Maritime University (SMU) in China. He did his postdoc at the State Key Laboratory of Mechanical System and Vibration at Shanghai Jiao Tong University (SJTU) in China with Professor Zhuang Fu (from 2018 to 2020). He has been a visiting scholar at Auburn University (AU) in the USA for one year. He graduated in 2018 from Taiyuan University of Science and Technology (TYUST), and received his PhD degree in Mechanical Engineering. He also gained his BS and MS degrees from TYUST in 2011 and 2014, respectively.

Yulong Zhang received an MSc degree in Instrument and Meter Engineering from Beihang University. He is currently pursuing his PhD degree in Mechanical Engineering from the University of Shanghai Jiao Tong, Shanghai, China. His current research interests include climbing robot, robot perception and control.

Yanzheng Zhao received his PhD degree in Mechanical and Electronic Engineering from the Harbin Institute of Technology, Harbin, China. He is currently a research professorship and a PhD supervisor with the School of Mechanical Engineering, Shanghai Jiao Tong University. He has long-term engagement in climbing robot, service robot, special robot, and microrobot research. As the person in charge and main participants, He has completed several national natural science funds, national science and technology support plan project. He has published more than 40 academic papers in domestic and foreign journals and conferences. As a major participant, he received the third award of national science and technology progress and the first prize of science and technology progress of Heilongjiang Province, etc.

References

Ahmadzadeh

Masehian

. Modular robotic systems: methods and algorithms for abstraction, planning, control, and synchronization. Artif Intell 2015; 223: 27–64.

Zhang

Zhu

Lin

, et al. Modular soft robotics: modular units, connection mechanisms, and applications. Adv Intell Syst 2020; 2: 1900166.

Liu

Yim

. Configuration recognition with distributed information for modular robots. Springer Proc Adv Robot 2020; 10: 967–983.

Terada

Murata

. Automatic modular assembly system and its distributed control. Int J Robot Res 2008; 27: 445–462.

Odem

Medina

. A self-reconfiguration algorithm for sliding triangular modular robots. IEEE Robot Autom Lett 2024; 9: 2216–2223.

Gilpin

Kotay

Rus

, et al. Miche: modular shape formation by self-disassembly. Int J Robot Res 2008; 27: 345–372.

Liu

Tong

Liu

. Review of snake robots in constrained environments. Robot Auton Syst 2021; 141: 103785.

Ozkan-Aydin

Goldman

. Self-reconfigurable multilegged robot swarms collectively accomplish challenging terradynamic tasks. Sci Rob 2021; 6: eabf1628.

Yang

Lai

, et al. Reorientation and obstacle avoidance control of free-floating modular robots using sinusoidal oscillator. Chin J Aeronaut 2024. https://doi.org/10.1016/j.cja.2024.03.005

10.

Hauser

Mutlu

Léziart

, et al. Roombots extended: challenges in the next generation of self-reconfigurable modular robots and their application in adaptive and assistive furniture. Robot Auton Syst 2020; 127: 103467.

11.

Parrott

Dodd

Groß

. Hymod: a 3-DOF hybrid mobile and self-reconfigurable modular robot and its extensions. In: Distributed autonomous robotic systems. Cham.: Springer, 2018, pp.401–414.

12.

Butler

Rus

. Distributed planning and control for modular robots with unit-compressible modules. Int J Robot Res 2003; 22: 699–715.

13.

Robertson

Kara

Paik

. Soft pneumatic actuator-driven origami-inspired modular robotic “pneumagami”. Int J Robot Res 2021; 40: 72–85.

14.

Dai

Nei

, et al. Research on reconfiguration strategies for self-reconfiguring modular robots: a review. J Intell Robot Syst 2024; 110: 47.

15.

Golestan

Asadpour

Moradi

. A new graph signature calculation method based on power centrality for modular robots. Springer Tracts Adv Robot: Distrib Auton Robot Syst 2013; 83: 505–516.

16.

Larkworthy

Ramamoorthy

. An Efficient Algorithm for Self-Reconfiguration Planning in a Modular Robot. In: Proceedings of IEEE International Conference on Robotics and Automation, Anchorage, USA, 07 May 2010.

17.

Le Van

Ngo

. Gradient-based routing protocol for modular robotic systems. In: Proceedings of IEEE/SICE International Symposium on System Integration, Honolulu, USA, 15 January 2020.

18.

Naz

Piranda

Bourgeois

, et al. Electing an Approximate Center in a Huge Modular Robot with the k-BFS SumSweep Algorithm. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Madrid, Spain, 05 October 2018.

19.

Nadizar

Medvet

Ramstad H

, et al. Merging pruning and neuroevolution: towards robust and efficient controllers for modular soft robots. Knowl Eng Rev 2022; 37: e3.

20.

Assaker

Makhoul

Bourgeois

, et al. A unique identifier assignment method for distributed modular robots. In: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, USA, 24 October 2020.

21.

Whitman

Travers

Choset

. Learning modular robot control policies. IEEE Trans Robot 2023; 39: 4095–4113.

22.

Liu

Yim

. A fast configuration space algorithm for variable topology truss modular robots. In: 2020 IEEE International Conference on Robotics and Automation (ICRA), Paris, France, 31 May 2020.

23.

Liu

Yim

. A quadratic programming approach to modular robot control and motion planning. In: 2020 Fourth IEEE International Conference on Robotic Computing (IRC), Taichung, China, 09 November 2020.

24.

Bassil

Moussa

Makhoul

, et al. Linear distributed clustering algorithm for modular robots based programmable matter. In: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, USA, 24 October 2020.

25.

Akitaya

Arkin

Damian

, et al. Universal reconfiguration of facet-connected modular robots by pivots: the O (1) musketeers. Algorithmica 2021; 83: 1316–1351.

26.

Christensen

Stoy

. Selecting a meta-module to shape-change the ATRON self-reconfigurable robot. In: Proceedings of IEEE International Conference on Robotics and Automation, Orlando, USA, 19 May 2006.

27.

Parada

Sacristán

Silveira

. A new meta-module design for efficient reconfiguration of modular robots. Auton Robot 2021; 45: 457–472.

28.

Lengiewicz

Hołobut

. Efficient collective shape shifting and locomotion of massively-modular robotic structures. Auton Robot 2019; 43: 97–122.

29.

Bassil

Piranda

Makhoul

, et al. ASAPs: asynchronous hybrid self-reconfiguration algorithm for porous modular robotic structures. Res Sq 2023. https://doi.org/10.21203/rs.3.rs-2700143/v1

30.

Guan

Liu

Zhao

. Self-configuration strategy design for unit-compressible modular robotic system. In: Proceedings of CSAA/IET International Conference on Aircraft Utility Systems, Tianjin, China, 18 September 2020.

31.

Guan

Fei

, et al. M-Lattice: a self-configurable modular robotic system for composing space solar panels. Proc Inst Mech Eng Part I 2015; 229: 406–418.

32.

Dijkstra

. A note to two problems in connection with graphs. Numer Math 1959; 1: 269–271.

33.

Schmickl

Hamann

Crailsheim

. Modelling a hormone-inspired controller for individual-and multi-modular robotic systems. Math Comput Model Dyn Syst 2011; 17: 221–242.