Fast in-place reconfiguration of expand-contract modular robots
Manuel Perera and Vera Sacristán
Goal
We prove universal in-place reconfiguration (i.e., in-place reconfiguration between any two robot configurations of the same number of 2x2 meta-modules) of 2- and 3-dimensional Crystalline or Telecube modular robotic systems, by means of a distributed algorithm. All meta-modules apply the same set of local rules (in a manner similar to cellular automata), and move relative to each other.
The algorithm relays on the expand-contract capability of the Crystal and Telecube atoms. When organized into 2x2 meta-modules this allows two meta-modules to occupy one single grid position. Reconfiguration is carried out while keeping the robot connected at all times, and uses exactly the union of the positions of the intial and the goal shapes.
If executed synchronously, any reconfiguration of a connected system of n modules is carried out in O(n) time steps, with O(n) basic moves per module, using O(1) force per module, and O(n) communication per module.
References
You can read how and why the reconfiguration algorithm works in the following documents:
Centralized version of the algorithm:
G. Aloupis, S. Collette, M. Damian, E. D. Demaine, R. Flatland, S. Langerman, J. O'Rourke, V. Pinciu, S. Ramaswami, V. Sacristán, S Wuhrer.
Efficient Constant-Velocity Reconfiguration of Crystalline Robots.
Robotica, Vol. 29, N. 1, pp. 59-71, 2011. PDF
Preliminary version: Realistic Reconfiguration of Crystalline (and Telecube) Robots, in Proc. 8th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2008), 2008. PDF
Distributed versions of the algorithm:
M. Perera.
Reconfiguración distribuida de robots cristalinos (in Spanish).
Degree thesis under the supervision of V. Sacristán, Facultat d'Informàtica de Barcelona, Universitat Politècnica de Catalunya, 2015. PDF.
J. Soler.
Reconfiguració de robots cristal·lins (in Catalan).
Degree thesis under the supervision of V. Sacristán, Facultat de Matemàtiques i Estadística, Universitat Politècnica de Catalunya, 2013. PDF
The simulator and the simulations
You can download our simulator for square-lattice robotic systems.
It comes with all the rules necessary to perform the reconfiguration, and initial initial and goal shapes.
The program only requires a JAVA Runtime Environment 1.4 or greater.
Unzip the file. This will create the required subdirectories.
Run the CrystalSimulator.jar file to start the simulator.
The simulator comes with the set of rules (rules.txt) to perform the reconfiguration, together with an example of sets of modules (agents.txt) to try them on. More examples can be found in the "files\Exp_Agents" folder. In addition, other versions of the distributed algorithm, not as efficient as the current one can be found in the "files\Other algorithms" folder. See Manuel Perera's degree thesis for details.
The User Guide contains all the information required to use the simulator.
Experimentation
All examples, programs and scripts used in the experimentation phase of our project can be found here:
Tests cases:
Can be found in the "files\Exp_Agents" folder of the simulator.
Parser:
A parser for the action.log file generated by the execution of a rules set on the simulator. You can find the Parser.jar file here and the instruction manual at chapter 8 of Manuel Perera's degree thesis.
Windows Powershell script:
This is a Windows Powershell script used on the experimentation phase of Manuel Perera's degree thesis. If you wish to create your own set of rules and test cases, you may find this useful. You can download the script from here.
Experimentation phase results & logs:
This compressed folder contains, all "actions.log" files generated while executing all test cases, the result of analysing these logs with the parser, the parser's actions file used to analyse them and the numbered rules used for the execution of the test cases, for each algorithm studied in Manuel Perera's degree thesis.
Create your own examples
If you want to create your own examples and see how they reconfigure using our set 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 modules 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 somehow.
The initial and the mirror of the goal configurations must have the same number of modules (>1)
All connections among modules within each configuration need to be present when the process starts.
Each grid cell must contain at most one module (no initial compression is allowed).
The initial configuration must lie to the left of the mirror of the goal configuration.
The leaders of both configurations (i.e., the topmost among the leftmost modules of both configurations) need to be horizontally aligned.
The state of all modules of the initial configuration must be Start, and the state of all modules in the mirror of the goal configuration must be Final.
Source files for the simulator
Our simulator is open source. You are allowed to modify it, as long as the following requirements are fulfilled:
The source code of your modified version of the simulator must be made public.
Acknowledgment to the original version and authors of the simulator must be included.
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.
Generic distributed universal constant-force reconfiguration of 2D lattice-based modular robotic systems, by Ferran Hurtado, Enrique Molina, Suneeta Ramaswami and Vera Sacristán. Link.
Simulating Distributed Algorithms for Lattice Agents, by Oswin Aichholzer, Thomas Hackl, Vera Sacristán, Birgit Vogtenhuber, and Reinhard Wallner. Link.