Distributed Algorithms and Advanced Modeling Approaches for Fast and Efficient Object Construction Using a Modular Self-reconfigurable Robotic System
Ph.D. Thesis - University of Bourgogne Franche-Comté, FEMTO-ST Institute, CNRS (2020)
Defended in Montbéliard, France on October, 9th 2020.
Jury Members:
| Nicolas ANDREFF | Professor | University of Franche-Comté | President |
| Heiko HAMANN | Professor | University of Lübeck | Rapporteur |
| Kasper STØY | Professor | IT University of Copenhagen | Rapporteur |
| Alcherio MARTINOLI | Associate Professor | École Polytechnique Fédérale de Lausanne (EPFL) | Examiner |
| Julien BOURGEOIS | Professor | University of Franche-Comté | Thesis director |
| Benoît PIRANDA | Associate Professor | University of Franche-Comté | Thesis codirector |
Humans have always been on a quest to master their environment. But with the arrival of our digital age, an emerging technology now stands as the ultimate tool for that purpose: Programmable Matter. While any form of matter that can be programmed to autonomously react to a stimulus would fit that label, its most promising substrate resides in modular robotic systems. Such robotic systems are composed of interconnected, autonomous, and computationally simple modules that must coordinate through their motions and communications to achieve a complex common goal.
Such programmable matter technology could be used to realize tangible and interactive 3D display systems that could revolutionize the ways in which we interact with the virtual world. Large-scale modular robotic systems with up to hundreds of thousands of modules can be used to form tangible shapes that can be rearranged at will. From an algorithmic point of view, however, this self-reconfiguration process is a formidable challenge due to the kinematic, communication, control, and time constraints imposed on the modules during this process.
We argue in this thesis that there exist ways to accelerate the self-reconfiguration of programmable matter systems, and that a new class of reconfiguration methods with increased speed and specifically tailored to tangible display systems must emerge. We contend that such methods can be achieved by proposing a novel way of representing programmable matter objects, and by using a dedicated reconfiguration platform supporting self-reconfiguration.
Therefore, we propose a framework to apply this novel approach on quasi-spherical modules arranged in a face-centered cubic lattice, and present algorithms to implement self-reconfiguration in this context. We analyze these algorithms and evaluate them on classes of shapes with increasing complexity, to show that our method enables previously unattainable reconfiguration times.
3D Coating Self-Assembly for Modular Robotic Scaffolds
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2020)
This paper addresses the self-reconfiguration problem in large-scale modular robots for the purpose of shape formation for object representation. It aims to show that this process can be accelerated without compromising on the visual aspect of the final object, by creating an internal skeleton of the shape using the previously introduced sandboxing and scaffolding techniques, and then coating this skeleton with a layer of modules for higher visual fidelity.
We discuss the challenges of the coating problem, introduce a basic method for constructing the coating of a scaffold layer by layer, and show that even with a straightforward algorithm, our scaffolding and coating combo uses much fewer modules than dense shapes and offers attractive reconfiguration times. Finally, we show that it could be a strong alternative to the construction of dense shapes using traditional self-reconfiguration algorithms.
Deterministic Scaffold Assembly By Self-Reconfiguring Micro-Robotic Swarms
Swarm and Evolutionary Computation — Special Issue on: “Parallel/Distributed Combinatorics and Optimization” (2020)
The self-reconfiguration of large swarms of modular robotic units from one object into another is an intricate problem whose critical parameter that must be optimized is the time required to perform a transformation. Various optimizations methods have been proposed to accelerate transformations, as well as techniques to engineer the shape itself, such as scaffolding which creates an internal object structure filled with holes for easing the motion of modules. In this paper, we propose a novel deterministic and distributed method for rapidly constructing the scaffold of an object from an organized reserve of modules placed underneath the reconfiguration scene. This innovative scaffold design is parameterizable and has a face-centered-cubic lattice structure made from our rotating-only micro-modules. Our method operates at two levels of planning, scheduling the construction of components of the scaffold to avoid deadlocks at one level, and handling the navigation of modules and their coordination to avoid collisions in the other. We provide an analysis of the method and perform simulations on shapes with an increasing level of intricacy to show that our method has a reconfiguration time complexity of $O(\sqrt[3]{N})$ time steps for a subclass of convex shapes, with $N$ the number of modules in the shape. We then proceed to explain how our solution can be further extended to any shape.
Scaffold-Based Asynchronous Distributed Self-Reconfiguration By Continuous Module Flow
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2019)
Distributed self-reconfiguration in large-scale modular robots is a slow process and increasing its speed a major challenge. In this article, we propose an improved and asynchronous version of a previously proposed distributed self-reconfiguration algorithm to build a parametric scaffolding structure. This scaffold can then be coated to form the desired final object. The scaffolding is built through a continuous feeding of modules into the growing shape from an underneath reserve of modules which shows a reconfiguration time improved by a factor of √[3](N) compared to the previous and synchronous version of the algorithm, therefore attaining an O(N^(1/3)) reconfiguration time, with N the number of modules in the system. Our algorithm uses a local motion coordination algorithm and pipelining techniques to ensure that modules can traverse the structure without collisions or creating deadlocks. Last but not least, our algorithm manages uncertainty in the motion duration of modules without negatively impacting reconfiguration time.
A Survey of Autonomous Self-reconfiguration Methods for Robot-based Programmable Matter
Robotics and Autonomous Systems (2019)
While researchers envision exciting applications for metamorphic systems like programmable matter, current solutions to the shape formation problem are still a long way from meeting their requirements. To dive deeper into this issue, we propose an extensive survey of the current state of the art of self-reconfiguration algorithms and underlying models in modular robotic and self-organizing particle systems. We identify three approaches for solving this problem and we compare the different solutions using a synoptic graphical representation. We then close this survey by confronting existing methods to our vision of programmable matter, and by discussing a number of future research directions that would bring us closer to making it a reality.
Scaffold-Based Asynchronous Distributed Self-Reconfiguration By Continuous Module Flow
Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (2019)
In the context of large distributed modular robots, self-reconfiguration is the process of having modules, seen as autonomous agents, acting together and moving to transform the morphology of their physical arrangement to produce a desired shape. However, due to motion constraints, the number of modules that can move concurrently is greatly limited, thus making self-reconfiguration a very slow process.
In this paper, we propose an approach for accelerating self-reconfi--guration to build a porous version of the desired shape, using scaffolding. We expand this idea and propose a method for constructing a parametric scaffolding model that increases the parallelism of the reconfiguration, supports its mechanical stability, and simplifies planning and coordination between agents. Each agent has a set of basic rules using only four states which guarantees that module movements and the construction of the scaffold are deterministic.
Coupled with an underneath reserve of modules that allows the introduction of rotating quasi-spherical modules at various ground locations of the growing porous structure, our method is able to build the scaffolding structure in O(N^(2/3)) time with N the number of modules composing the structure. Furthermore, we provide simulation results showing that our method uses O(N^(4/3)) messages with no congestion.