This project develops a novel approach for heterogeneous self-reconfiguration of a modular robot comprised of heterogeneous cubic modules. We allow an arbitrary number of modules and module classes and show that the proposed self-reconfiguration algorithm can guarantee completion of heterogeneous self-reconfiguration sequences by avoiding so-called hole obstructions. We introduce a hole-detection algorithm to avoid creating holes in connected sets of modules (furthermore called configuration) and an assignment resolution algorithm that prevents deadlocks. Using these algorithms, we show that this approach yields provably successful reconfiguration sequences from any heterogeneous initial configuration to any heterogeneous target configuration as long as the initial and the target configuration are hole and enclosure-free.
The Self-Reconfiguration Problem
Heterogeneous robots are comprised of modules with different capabilities and potentially shape and size. Heterogeneous self-reconfiguration solves the problem of reconfiguring a given initial configuration into a desired target configuration. As opposed to the homogeneous case, not all modules are interchangeable anymore. The loss of interchangeability in heterogeneous systems introduces additional complications such as the potential for creating deadlocks. In the presented algorithm, the avoidance of deadlocks translates into the avoidance of holes (positions in the target configuration that cannot be reached) and enclosures (positions in the current configuration that cannot be reached) during the reconfiguration process. Additionally, we have to ensure the existence of valid assignments of modules to their respective target positions.
System Representation
We employ a model commonly referred to as sliding cube model that employs cubic modules embedded in a discrete three-dimensional unit lattice. The instantiation of the sliding cube model in this paper uses cubes of unit dimensions that move through a cubic lattice in discrete steps of size one. These cubes are capable of two basic motions – corner and sliding motions. We furthermore impose a feasibility constraint on a motion meaning that a motion requires a connected substrate of other cubes (also called a configuration) and has to obey connectivity constraints as well as collision constraints.
Reconfiguration Planning
Accomplishing a heterogeneous reconfiguration requires to move all cubes in the initial configuration to matching positions in the target configuration. A matching position must have the same properties as the cube that will occupy it.
The self-reconfiguration planning algorithm we developed repeats the following steps until the reconfiguration sequence has been completed.
- Compute the movable set M (see figure below)
- Compute the reachable set R (see figure below)
- Compute a valid assignment that avoids holes and deadlocks (see next section)
- Compute the planning space (this can be thought of as the hull around the current configuration)
- Plan a path from the location of the movable cube to the reachable target position
- Execute the planned path
Assignment Resolution
By construction M and R are nonempty sets unless the target configuration has been assembled. For homogeneous reconfiguration, there exists a module that can be moved from its initial to its target position at any time. For heterogeneous self-reconfiguration, this is not generally true even for nonempty sets M and R. If no cube m in M matches the properties of a position r in R then no valid assignment can be found (see for example the figure below). To avoid deadlocks created by a lack of valid assignments we employ the assignment resolution algorithm. This algorithm essentially moves a movable cube to a random position in the hull (or planning space) such that no holes are created.
Hole Detection and Avoidance
The heterogeneous self-reconfiguration algorithm potentially creates holes in the target configuration. A hole is a target position that can not be reached by any cube. Holes obstruct the completion of a reconfiguration because they create permanent deadlocks and must therefore be avoided at all cost. Our hole-detection algorithm provably detects holes and can invalidate assignments that would create them.
The example below shows a two-dimensional case where the move of one cube creates a hole (indicated by H) and the boundary of a whole (shown as green nodes). Note that the existence of a hole implies that the planning space becomes disconnected and contains the hole and the planning space outside the boundary of the hole.
The main result in our self-reconfiguration studies states: Using the assignment resolution algorithm, the absence of holes guarantees a successful reconfiguration.
Results
In our simulations, we have found that the number of assignment resolution steps is generally low. Also the number of assignment resolution steps is larger for small configurations and decreases as the size of the configuration increases. This can be attributed to the larger number of movable and reachable cubes in larger configurations, which makes it very likely that a valid assignment can be found.
In our experiments reconfiguring random initial configurations into box-shaped configurations, not a single holes occurred. The complete absence of holes might be an artifact of this specific set of randomly generated problem instances. Note, however, that the occurrence of holes is very unlikely in general and requires multiple consecutive assignment or assignment resolution steps to arrange cubes in specific shapes.
An example reconfiguration sequence is furthermore shown below.
A video showing the above sequence can be viewed at the following link Heterogeneous Self-Reconfiguration.
Related Publications
- D. Pickem, M. Egerstedt, J. S. Shamma, “Complete Heterogeneous Self-Reconfiguration: Deadlock Avoidance Using Hole-Free Assemblies,” 4th IFAC Workshop on Distributed Estimation and Control in Networked Systems 2013 (NecSys)
- D. Pickem and M. Egerstedt, “Self-reconfiguration using graph grammars for modular robotics,” 4th IFAC Conference on Analysis and Design of Hybrid Systems 2012 (ADHS)
- D. Pickem, “3D Reconfiguration Using Graph Grammars for Modular Robotics,” Master Thesis, 2011
