Introduction
Self-reconfiguration is a very slow process and its distributed planning exceedingly hard due to constraints and the assembly order of the goal shape, and the risks of collisions between modules. This is even more so when considering this problem in a Face-Centered Cubic (FCC) lattice with 3D Catom modules, as the FCC lattice produces a very tight arrangement of modules with 12 neighbors, exacerbating the risks of one module hampering on the movement of another. Furthermore, 3D Catoms cannot enter or leave a lattice position that is surrounded by at least two opposing modules (see Figure 1 below), which greatly constrains the possible assembly order of a shape, forcing a sort of diagonal progression of the construction.
Traditional distributed reconfiguration algorithms [2] are slow due to the reconfiguration time of existing algorithms being at best linear in the number of modules in the system. In the context of swarms of thousands of modules, this is still too long. This stems from the fact that coordinating the motion of large ensembles of modules concurrently is excruciatingly hard.
To remediate this, we have proposed to alter the parameters of self-reconfiguration, so that it can be achieve to levels of speed, but only if the self-reconfiguration occurs in an environment specifically engineered for that purpose.
Our Method
Sandboxing
The first addition required by our method is what we name a sandbox. This is a reserve of modules that lies underneath the reconfiguration scene and share the same internal structure as our goal objects while holding extra modules that can be supplied at various regularly defined ground locations of the scene. The sandbox enables new ways to reconfigure, by supplying modules from the system or discarding modules from it and renders the maximum distance that a module has to cover on horizontal ground displacement constant. See Figure 2.a below.
Scaffolding
Then, we propose to use scaffolding, which engineers the goal shape so that it is made porous, thus reducing the total number of modules required to form a shape, and leaving holes inside the structure through which modules can flow faster than on the surface of the object. Scaffolding had been previously introduced and used successfully in the context of cubic-lattice-based modules, but not within a face-centered cubic lattice. This scaffold is made from an arrangement of regular multi-module groups named tiles. These tiles assemble by connecting the tip of their branches to the root of neighbor tiles. See Figure 2.b for an example of a scaffold for a pyramid shape. Furthermore, the regular nature of the scaffold creates a number of predictable paths throughout the structure, through which modules can flow in parallel without ever crossing each others' paths, as long as modules always navigate the structure from the sandbox through the structure in a strictly vertical manner, following the vertical branches of the tiles above its insertion point. By forming trains of modules from the sandbox to available positions in the goal shape, this allows for a massively parallel reconfiguration.
Scaffold Construction
Results
We have shown that our reconfiguration method had a reconfiguration time that is in $O(N1/3), with N the number of modules in the goal object, for all shapes that do not have vertical concavities or holes between the sandbox and the scaffold. Not only is this sublinear, but the number of modules N is much lower than for the dense version of the object, thus producing unseen before reconfiguration speeds.
The videos below highlight some principles behind our distributed method, and show simulations of self-reconfigurations using our method on the VisibleSim simulator. All modules execute the same distributed program, have IDs, communicate through a message-passing scheme, and are able to navigate the scaffold thanks to a set of local navigation rules stored in memory.
Please refer to [2] and [3] for details on the reconfiguration algorithm itself.
References
[1] P. Thalamy, B. Piranda, et J. Bourgeois, « A survey of autonomous self-reconfiguration methods for robot-based programmable matter », Robotics and Autonomous Systems, vol. 120, p. 103242, oct. 2019, doi: 10.1016/j.robot.2019.07.012.
[2] P. Thalamy, B. Piranda, et J. Bourgeois, « Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure », in Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, Montreal QC, Canada, 2019, p. 140‑148, doi: 10.5555/3306127.3331685.
[3] P. Thalamy, B. Piranda, F. Lassabe, et J. Bourgeois, « Scaffold-Based Asynchronous Distributed Self-Reconfiguration By Continuous Module Flow », in 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2019, p. 4840‑4846, doi: 10.1109/IROS40897.2019.8967775.