Generic distributed universal constant-force reconfiguration of 2D lattice-based modular robotic systems

Ferran Hurtado, Enrique Molina, Suneeta Ramaswami and Vera Sacristán


initial shape reconfiguring forwards canonical shape reconfiguring backwards final shape
Initial shape Reconfiguring forwards Canonical shape Reconfiguring backwards Final shape


We prove universal reconfiguration (i.e., reconfiguration between any two robot configurations of the same number of modules) of 2-dimensional lattice-based modular robotic systems, by means of a distributed algorithms.

To the best of our knowledge, this is the first known reconfiguration algorithms that applies in a general setting to a wide variety of particular modular robotic systems, and holds both for square and hexagonal lattice-based 2-dimensional systems.

All modules apply the same set of local rules (in a manner similar to cellular automata), and move relative to each other. Reconfiguration is carried out while keeping the robot connected at all times.

If executed synchronously, any reconfiguration of a robotic system of n modules is done in O(n) time steps, with O(n) basic moves per module, using O(1) force per module, O(1) size memory and computation per module (except for one module, which needs O(n) size memory to store the information of the goal shape), and O(n) communication per module.

Acknowledgments

The square version of the algorithm has been implementd by Óscar Rodiguez, on a simulator put up by Reinhard Wallner, under the supervision of Oswin Aichholzer and Thomas Hackl, and extended by himself. The hexagonal version of the algorithm has been implemented by Sergio Ordóñez and Ángel Rodríguez, on a simulator put up by themselves by modifying the previous one by Reinhad Wallner.

Algorithm

You can read how and why the reconfiguration algorithm works in the following documents:

Download the simulations

You can download our simulators for square-lattice robotic systems. They come with all the rules necessary to perform the reconfiguration, and a few pairs of initial and goal shapes. Both the square and the hexagonal simulators only require a JAVA Runtime Environment 1.4 or greater.

SQUARE HEXAGONAL
Download the square simulator:
  1. Download the zipped file anywhere in your computer.
  2. Unzip the file. This will create the required subdirectories.
  3. Run the AgentSystem2D.jar file to start the simulator.
  4. The User Guide contains all the information required to use the simulator.
Download the hexagonal simulator:
  1. Download the zipped file anywhere in your computer.
  2. Unzip the file. This will create the required subdirectories.
  3. Run the AgentSystemHexa.jar file to start the simulator.
  4. The User Guide contains all the information required to use the simulator.
Information about the sets of rules:

We supply a set of 558 rules, which are distributed in the following way:
  1. rules_sq_initial_setting.txt contains the preable, which specifies the use of colors for the visualization.
  2. rules_sq_common_phase.txt contains 129 rules for self-organizing both the initial and the goal shapes (elect a leader, detect all holes, form the scan tree).
  3. rules_sq_DFvalues_forwards.txt contains 105 rules for computing the DF-values of the initial shape.
  4. rules_sq_DFvalues_backwards.txt contains 126 rules for computing the DF-values of the goal shape.
  5. rules_sq_reconfiguring_forwards.txt contains 109 for reconfiguring from the initial shape into the strip.
  6. rules_sq_reconfiguring_backwards.txt contains 89 for reconfiguring from the strip into the goal shape.
  7. rules_sq_all_together.txt contains the colors setting and all 558 rules.
Notice that the rules dealing with computations on the mirror image of the goal shape are an artifact of our simulation: when running this strategy on real robots, the information of the goal shape should be sent to the modules, not necessarily computed by them. In addition, a few rules are devoted to correctly showing the colors in the simulation, and are not really necessary otherwise. Their number is irrelevant, though.
Information about the sets of rules:

We supply a set of 1003 rules, which are distributed in the following way:
  1. rules_hex_initial_setting.txt contains the preable, which specifies the use of colors for the visualization.
  2. rules_hex_common_phase.txt contains 216 rules for self-organizing both the initial and the goal shapes (elect a leader, detect all holes, form the scan tree).
  3. rules_hex_DFvalues_forwards.txt contains 256 rules for computing the DF-values of the initial shape.
  4. rules_hex_DFvalues_backwards.txt contains 296 rules for computing the DF-values of the goal shape.
  5. rules_hex_reconfiguring_forwards.txt contains 166 rules for reconfiguring from the initial shape into the strip.
  6. rules_hex_reconfiguring_backwards.txt contains 70 rules for reconfiguring from the strip into the goal shape.
Notice that the rules dealing with computations on the mirror image of the goal shape are an artifact of our simulation: when running this strategy on real robots, the information of the goal shape should be sent to the modules, not necessarily computed by them. In addition, a few rules are devoted to correctly showing the colors in the simulation, and are not really necessary otherwise. Their number is irrelevant, though.
Legend:

The following document contains the legend for states, counters and message channels used in the rules: Legend_sq.pdf
Legend:

The following document contains the legend for states, counters and message channels used in the rules: Legend_hex.pdf
Information about the supplied configuration examples:

We supply a set of examples showing specific important behaviors of our rules:
  1. agents_sq_activation.txt Small example showing what an activation conflict is, and how we solve it. The activation conflict can be seen in iterations 15-17.
  2. agents_sq_collision-deadlock-jump-and-wait.txt Small example simultaneously showing how we solve a potential collision and deadlock in iterations 76-95, during the reconfiguration from the initial shape into the strip. Later on, in iterations 552-end, it can be seen how our rules keep the ordering (and still avoid deadlocks by jumping) when reconfiguring from the strip into the goal shape.
  3. agents_sq_wait_to_close_hole.txt This small example also shows how deadlocks, collisions and activation conflicts are solved (see iterations 50-87). Iterations 594-end also show that our rules take care of closing the holes at the right time, i.e., only when all modules lie in the appropriate connected component of the boundary of the static structure. In this example, some modules need to exit the hole before it gets closed.
  4. agents_sq_hole_leader_control.txt This small example shows the opposite case, in which modules need to reach the interior of a hole before it gets closed. This is, in general, trivial, since the hole leader normally is sent to its destination after all modules internal to the hole. This file shows the one specific case in which this does not happen if the leader of the hole has been disconnected following the general rule. In this case the leader needs to change its parent in the tree. The file shows two apparently identical examples. In the one above, the hole leader connections in the goal shape (top left) follow the general rule. In the one below, our rules realize the mistake in iteration 74, and the hole leader of the goal shape (bottom left) changes its attachments in iteration 75. This produces a change in the DF-values of the goal shape, which need to be recomputed. Later on, in iterations 569-end, the consequences of these elections are show: in the top right reconfiguring shape, two modules gets trapped in the wrong connected component of the boundary, while in the bottom right reconfiguring shape each module reaches its final destination.
  5. agents_sq_example1.txt, agents_sq_example3.txt and agents_sq_example3.txt These files contain three more examples.
Information about the supplied configuration examples:

We supply a set of examples showing specific important behaviors of our rules:
  1. agents_hex_activation.txt Small example showing what an activation conflict is, and how we solve it. The activation conflict can be seen in iterations 15-17.
  2. agents_hex_collision-deadlock-jump-and-wait.txt Small example simultaneously showing how we solve a potential collision and deadlock in iterations 61-64, during the reconfiguration from the initial shape into the strip. Later on, in iterations 558-end, it can be seen how our rules keep the ordering (and still avoid deadlocks by jumping) when reconfiguring from the strip into the goal shape.
  3. agents_hex_wait_to_close_hole.txt This small example also shows how deadlocks, collisions and activation conflicts are solved (see iterations 50-94). Iterations 749-end also show that our rules take care of closing the holes at the right time, i.e., only when all modules lie in the appropriate connected component of the boundary of the static structure. In this example, some modules need to exit the hole before it gets closed.
  4. agents_hex_hole_leader_control.txt This small example shows the opposite case, in which modules need to reach the interior of a hole before it gets closed. This is, in general, trivial, since the hole leader normally is sent to its destination after all modules internal to the hole. This file shows the one specific case in which this does not happen if the leader of the hole has been disconnected following the general rule. In this case the leader needs to change its parent in the tree. The file shows two apparently identical examples. In the one above, the hole leader connections in the goal shape (top left) follow the general rule. In the one below, our rules realize the mistake in iteration 71, and the hole leader of the goal shape (bottom left) changes its attachments in iteration 72. This produces a change in the DF-values of the goal shape, which need to be recomputed. Later on, in iterations 708-end, the consequences of these elections are show: in the top right reconfiguring shape, one module gets trapped in the wrong connected component of the boundary, while in the bottom right reconfiguring shape each module reaches its final destination.
  5. agents_hex_spiral-1.txt, agents_hex_spiral-2.txt, agents_hex_spiral-3.txt, and agents_hex_spiral-4.txt. These four bigger examples, each made out of 185-223 modules (plus the same number for the mirror image of the goal configuration), show all possible bottleneck topologies and geometric orientations. In all four cases, the robot reconfigures from its initial shape into a strip, and then back to the initial shape (which coincides with the goal shape).

Create your own examples

If you want to create your own examples and see how they reconfigure using our sets of rules, you need to take into account the following conditions. They are due to the fact that we need to also simulate the process of the leader getting the information of the goal shape. This is done in the simulator through what we call the mirror of the goal shape, i.e., a translation of the goal configuration, which gets processed and is used by the modules to "read" the goal information, hence simulating that they got it from their leader.

Source files for the simulators

Our simulators are open source. You are allowed to modify them, as long as the following requirements are fulfilled:
  1. The source code of your modified version of the simulator must be made public.
  2. Acknowledgment to the original version and authors of the simulator must be included.
  3. A notice must be sent by e-mail to the authors of the original simulator, explaining what your modification does and where it is available.
The source files of both simulators can be downloaded here:

Related work


Initial shape Reconfiguring forwards Building the strip Back from the strip Reconfiguring backwards Final shape
initial shape reconfiguring forwards building the strip back from the strip reconfiguring backwrds final shape

Last update of this page: