3.4 HSD-based Algorithms
We now present two self-reconfiguration algorithms. As a first step, both perform a decomposition step where I and G arehierarchically organized as a tree of substructures, as discussed in Section 3.3.2. As an illustration, consider I and G in Figure5a and 5b, and their corresponding decompositions. We will use these example configurations throughout the section toillustrate the algorithms.

1) Substructure selection.
The module-to-module connectivity of the configuration is traversed. A module is called a “vertex” module if it isconnected to more than two neighbor modules (is at a branch-out point) or to only one neighbor (is at a free end). All othermodules have two neighbors and lie between vertex modules.

A substructure is the shortest list of distinct modules lying between two vertex modules. If the two vertex modules are thesame, the substructure is of type loop. Conversely, if the vertices are distinct the type is chain. The special case of a singlecycle (with no vertex modules) is handled explicitly. A second step further creates loops by searching for cycles among theexisting chains. If there are any, all the chains involved in the cycle are now grouped together as a single loop substructureand no longer considered as a number individual chains.

Each substructure has an associated data structure containing the following information: size (number of modules in thesubstructure), type of substructure (chain or loop), pointers to neighbor substructures (other substructures connected at itsvertex modules).

2) Hierarchy creation
A substructure is selected as the root node (heuristics for this choice are discussed in Section 3.5). All neighborsubstructures become a child node of the root, and the root their parent node. The children’s children are recursivelysearched to create the corresponding parent/child relationships until childless nodes are reached.

Each node in the tree has an associated data structure that inherits the information of a substructure and the following: levelin the tree, pointer to its parent, pointers to all its children, and list of “attachment points”. We define attachment points asthe relative locations (vertex modules) on a substructure where its children nodes are attached.

Once hierarchically decomposed, I and G can be compared for equivalence, as defined in Section 3.2. Specifically, I and Gare equivalent if their trees are identical. That is, they have the same: 1) number of levels, 2) number of substructures perlevel, 3) type of substructures per level, 4) size of the substructures and 5) “attachment points” on each substructure.Conveniently, the difference between two configurations can also be quantified in terms of their respective trees, that is interms of the difference in the number of levels, number of substructures per level, etc. This measure of difference is used togenerate the sequence of precomputed substructure operations in the reconfiguration stage of the algorithms as explained inthe next section.

3.4.1 Canonical Form Algorithm
A very simple algorithm results in overall reconfiguration by first transforming into a simple intermediate configuration. It isbased on two observations: 1) the symmetry of reconfiguration sequences, that is, a sequence of rmoves that takes I to G canbe obtained by reversing the order of the sequence that transforms G to I; 2) “destructive” sequences that reconfigure acomplex configuration into a simpler one are easier to devise than vice versa.

Based on these observations, we find the sequence of rmoves to reconfigure both I and G into an intermediate simpleconfiguration, C. The reconfiguration from I to G is then:

The hierarchical decomposition is used to guide the sequence of operations needed to reconfigure I and G into C. If we selectC as a single chain then the reconfiguration stage is simply a concatenation of merge operations (retrieved from a lookuptable) resulting in ever decreasing number of levels and substructures.

This algorithm is, in general, sub-optimal as there may be redundant operations involved in going through the intermediateconfiguration. It is however, a very simple way to obtain otherwise difficult sequences of moves. It is an efficient heuristicsolution for cases where the I, G pair are close to the intermediate configuration. The Canonical Form algorithm is also likelyto perform better than the Matching algorithm presented below in cases where the latter requires many relocation operations,which may be more costly than the other substructure operations (see Section 3.3.1).

3.4.2 Matching Algorithm
This algorithm works by progressively matching the 5 equivalence conditions in Section 3.2. As a first step, the algorithmmatches the number of levels. In this case, G has a smaller number of levels than I. In order to reduce the number of levelsin I to match G’s, the algorithm invokes merge operations between the leaf nodes and their parent (lI - lG) times, where lGand lI are the number of levels in G and I respectively. Figure 7 shows the process.

Once the number of levels has been matched, the algorithm proceeds to match the number of modules at each level. Aseries of merge and split operations is invoked that effectively redistributes modules between levels. One pertinentobservation is that the number of modules per level need not be matched exactly. As long as the relative sizes are fairly close(90% was used in our implementation), the functionality will be the same and we can save extra reconfiguration operations.In this particular I, G pair, once I has reconfigured to have only two levels like G, the number of modules per level is deemedclose to the goal’s and no matching is

needed.

The type of substructures at every level is matched by invoking transformation operations to change a loop into a chain orvice versa. In the example shown, the types at every level already match those of the goal G and don’t require anytransformation operations.

As a last step, relocation operations attach the substructures at their goal attachment points on their parent. The relocationoperations involve, in general, the moving of a branch of the tree relative to the parent substructure. If the branch is severallevels deep and/or if the move is over a large distance, motion planning techniques must be brought to bear (see Section 2.4).This may result in these operations being costly or even unrealizable. However, if the relocation operations are simple, thisalgorithm will in general be more efficient than the Canonical Form algorithm, as it compares I and G for differences andseeks to make only those changes necessary to remove them.

3.5 Choices of Decomposition and Correspondence
It has been previously pointed out that following the definitions of s, chain and loop above, there are many different ways inwhich to group modules into substructures. An example is shown in the Figure 9. The number of different ways of selectingsubstructures is proportional to the number of ways of partitioning the associated module graph. This number increases withthe total number of modules.

This initial choice of substructures determines to a large extent the ensuing hierarchical decomposition. This means that for agiven I and G pair, there may be nI*nG different ways to partition both configurations into substructures, where nI and nG arethe number of different ways to select substructures in I and G respectively. There is, in addition, a choice involved in thecreation of the tree, as a particular substructure must be distinguished to be the root.

The simplicity of the reconfiguration sequence depends to a large extent on these choices. We can make use of a concept of“correspondence” (closeness) between I and G to result in a simpler reconfiguration. In particular, we wish to selectdecompositions that result in I and G having trees as similar as possible. For instance, for the Matching algorithm we wouldlike I and G to have:

• an equal (or as similar as possible) number of levels
• an equal (or as similar as possible) number of modules per level
• the same (or as similar as possible) number of substructures per level

We can use heuristics to guide the selection of the root. For example, we may select the largest substructure (largest numberof modules) to become the root in both I and G. This partly satisfies one of the correspondence rules above, and is resonantwith the macro-mini concept of complex hierarchical systems. Or alternatively, we could balance both trees to try to satisfythe first rule.

Although these criteria do not necessarily yield an optimal solution, they help to guide the decomposition towards choiceswith good correspondence between I and G, and so result in simpler reconfigurations. However, searching for the best I andG pair can be costly, since it implies creating all possible decompositions for both I and G and then searching for the bestpair among all (nI*nG ) choices. It is also possible to simply pick a choice “blindly” for both I and G and continue with thedecomposition, saving the cost of searching for the best correspondence.

3.6 Extensions
HSD analyses a network of substructures as a tree, which is an acyclic graph. By grouping modules in a cycle as a single loopsubstructure that becomes a node in the tree, we are effectively removing cycles from the graph. However, there are stillcases where cycles remain. These include cases when a substructure (loop or chain) connects to more than one point onanother substructure, or when it connects two substructures that belong to different levels. For example, this happens whenloops share common edges, or when there are cycles of substructures, as illustrated in Figure 10.

We call such substructures overconstrained, as an excess of connections causes the problem. The solution involvesselectively disconnecting one of the attachment points of the overconstrained substructure so that the cycle is effectivelyremoved and the tree can be constructed. Reverting to a module graph representation of a configuration (Section 3.2),overconstrained cases occur whenever the graph contains 3-connected minors, i.e. there exist pairs of vertex modules withthree or more distinct paths connecting them [26].

A clever choice of s may in some cases partly, or even entirely, avoid the problem. For example, we may select s to containa substructure equal to the first configuration shown in Figure 10. By encapsulating this particular topological grouping ofmodules as a single substructure with its associated operations, we effectively remove any such overconstrained substructuresfrom a global configuration.

One way to handle overconstrained I or G configurations in the planning is to form a virtual break in the overconstrainedsubstructures as they are discovered in the decomposition. This will produce I’ or G’, which are free of overconstrainedsubstructures. Planning can then happen normally between two non-overconstrained configurations. A step is added in thebeginning of the reconfiguration plan to transform I to I’ and a step at the end to transform G’ to G, as needed. This processis sub-optimal since it introduces additional rmoves and removes overconstrained configurations from the reconfigurationspace that may be indeed part of an optimal sequence.

3.7 Experimental Results
A computer simulation was run to test the HSD method. Several I,G pairs were used, the most complex configurationshaving up to four levels and twelve substructures. The desired goal configuration is achieved in all cases. One of the I,G pairstested is the example pair used to illustrate the method in Section 3. The sequence of rmoves output by the method leads tothe same changes shown in Figures 5-8, and these figures serve as illustration of the simulation results. Decompositions withoverconstrained substructures, and subsequently needing treatment as described in Section 3.6, were also tested.

4. CONCLUSIONS

This paper introduces a taxonomy of reconfiguration classes for modular, self-reconfigurable robots and defines theircharacteristics. A study of the closed-chain reconfiguration class, its topological space and suitable reconfigurationalgorithms are also presented. To the authors’ knowledge, this is the first time a reconfiguration approach has been publishedfor this class.

This paper introduces a heuristic approach called Hierarchical Substructure Decomposition (HSD). It centers on thepartitioning of a robot configuration into small components, called substructures, and their subsequent ordering as ahierarchy. Reconfiguration of the entire system is thus divided into a series of simple, precomputed reconfigurationsubsequences happening among the substructures.

Two algorithms based on HSD are described and simulation results discussed. The method presented outputs a sequence ofconnectivity changes to reconfigure between two arbitrary configurations. For the closed-chain class this sequence ofconnectivity changes must be accompanied by physically realizable trajectories for the moving kinematic chains. We do notaddress these considerations in the paper. As a next step, we intend to add a path planning stage to the method to producefeasible trajectories.

Page 1, Page 2

Tech Materials

Modular Robots Self-Reconfiguration Planning Of Identical Modules
Robot Assistive Tasks User-Guided Reinforcement Learning for an Intelligent Environment
Wireless Systems Learn The Science And Engineering Of Mobile And Wireless Communicaitons
Digital Signal Processing How can digital systems be designed to replace existing analog systems
Automatic Control Systems The best general book about control engineering
Dark Side Robots 30 Cool LEGO Mindstorms Projects Kit
Robotics Experimental Circuit Blocks Provides Instruction On Creating Moving Robotic Parts
Machine Design Master Machine Design With The High Performance Study Guide
Microsensor Signal Conditioning A Large Number Of Applications Are Supplied For Each Type Of Sensor Described
Control Systems A complete tutorial on using MATLAB

More...