Master Thesis subject 2016-2017 KIT / FEMTO-ST institute German-French partnership Title: Self-Reconfiguration Algorithm for Quasi-Spherical Modular Robots producing Programmable Matter Keywords: computer science, modular robots, programmable matter, self-reconfiguration, distributed computing Advisors (FEMTO-ST & KIT): FEMTO-ST : Dr. Benoît Piranda, Assistant Professor in Computer Science email:
[email protected]
FEMTO-ST – CNRS research institute 15 B avenue des Montboucons 25030 BESANCON cedex, France Tél. +33 (0)3 63 08 24 02 - www.femto-st.fr
Subject description: This internship is proposed in the context of a project called ‘Programmable Matter’ funded by French National Research Agency (ANR) in collaboration with the University of Tokyo and Peugeot Citroen car company. This work could be continued in the framework of a PhD thesis. Programmable matter This work is part of the Claytronics project [1]. Claytronics, which stands for Clay-Electronics is an implementation of programmable matter initiated by Carnegie Mellon University and Intel Corporation, and then joined by FEMTO-ST Institute. On a broad scope, programmable matter is a matter which can change one or several of its physical properties, more likely its shape, according to an internal or an external action. An example of a mug being created by an ensemble of micro-robots is presented in Figure 1. Programmable matter can have different properties depending on the underlying technology chosen: evolutivity, programmability, autonomy, interactivity [2]. Only modular self-reconfigurable robots (MSR) can implement this full set of properties as they can embed computation. MSR are composed of individual modules able to move relatively one to another to create different configurations. In this work, we consider lattice-based modules that are aligned on a Face-Centered Cubic lattice as shown in this video [https://youtu.be/V8JQvfpO-0Q]. The micro-robots we consider in this project are named 3D Figure 1: mug model made of 3D catoms. catoms, their geometry is fully detailed in [3]. To sum up, they are quasi-spherical, able to move from one cell of the lattice to another in rolling around another catom. Each catom therefore embeds a chip for computation and for driving its actuators and communication capabilities. Self-Reconfiguration Considering a set of connected micro-robot forming an initial configuration, self-reconfiguration process consists in making successive small motions in order to reach a goal configuration. Self-reconfiguration algorithms consist in distributed codes, executed in each module and using local knowledge of the environment but producing a global reorganization of the set of robots. Each module can exchange messages with its direct neighbors in order to get more information on its neighborhood, and decide if it has to move or not. Some previous works of the team were about proposing self-reconfiguration algorithms for modules that move in 2D [4][5]. Following videos show examples of self-reconfiguration for these contexts [https://youtu.be/XGnY-oS4Nw0] [https://youtu.be/gAyP4xFb1eU]. This work consists in defining several distributed algorithms allowing that efficiently make the selfreconfiguration of a set of 3D catoms possible. These algorithms will be developed in C++ in order to be integrated to our simulator (called VisibleSim [6]). It allows to simulate programs running on configurations made of tens to many tens of thousands of catoms. We imagine that we obtain asynchronous motions of a large subset of catoms that converge to the goal configuration.
Environment description (team, facilities): Team FEMTO-ST/DISC/OMNI in Montbéliard (close to the German border). The OMNI team is a human scale team made of 9 Professor (Full Professor and Assistant Professor) and 7 Ph.D. Students. The Master student will be welcomed to the team during its internship, he will have at his disposal a desk and a computer.
1
Claytronics Project web page: http://www.cs.cmu.edu/~./claytronics/
2
Julien Bourgeois, Benoit Piranda, André Naz, Hicham Lakhlef, Nicolas Boillot, Hakim Mabed, Dominique Dhoutaut, Thadeu Tucci, "Programmable matter as a cyber-physical conjugation", IEEE International Conference on Systems, Man, and Cybernetics (SMC 2016), Budapest, Hungary, October 9-12, 2016. 3 Benoît Piranda, Julien Bourgeois, "Geometrical study of a quasi-spherical module for building programmable matter”, 13th International Symposium on Distributed Autonomous Robotic Systems (DARS 2016), London, United Kingdom, november 7-9, 2016. 4 André Naz, Benoît Piranda, Seth Copen Goldstein, Julien Bourgeois, “A Distributed Self-Reconfiguration Algorithm for Cylindrical Lattice-Based Modular Robots”, The 15th IEEE International Symposium on Network Computing and Applications (NCA 2016), Cambridge, Massachusetts USA, Oct. 31-Nov. 2, 2016. 5 Benoît Piranda, Guillaume J. Laurent, Julien Bourgeois, Cédric Clévy, Nadine Le Fort-Piat, "A New Concept of Planar SelfReconfigurable Modular Robot for Conveying Microparts", Mechatronics Journal 2013, vol. 23(7), pp. 906-915, ISSN 0957-4158. 6
VisibleSim Project web page: http://projects.femto-st.fr/projet-visiblesim/