Programmable matter can change its physical properties according to user input or autonomous sensing. Researchers are using amoebots to understand programmable matter. Dr Giovanni Viglietta, Assistant Professor at the Japan Advanced Institute of Science and Technology, has developed a mathematical technique for the self-organisation of individual particles to achieve a complex task. He demonstrates that, when properly programmed, amoebots perform tasks such as solving the fundamental shape-formation problem. Dr Viglietta is also exploring innovative approaches based on machine learning and discusses his plans to apply reinforcement learning techniques to create a more efficient and reliable algorithm.
Programmable matter can be envisaged as a myriad of nanoscale robots, known as particles, working together as a team to perform a task. A large group of these particles forms a material that can be programmed to dynamically change its physical properties (shape, density, conductivity, colour, etc). Applications of programmable matter include smart materials, autonomous monitoring and repair, and minimally invasive surgery.
The science surrounding programmable matter is still in its infancy. Practical and theoretical research are advancing in parallel, inspiring and guiding each other. Engineers are developing smaller and more efficient prototypes of programmable particles. These are often inspired by biological systems, such as amoeba, cells, or unicellular organisms that can change shape and act collectively to surround a target object. At the same time, theoretical computer scientists are studying abstract models, including amoebots, to understand programmable matter and design efficient algorithms for typical tasks. Dr Giovanni Viglietta, Assistant Professor at the Japan Advanced Institute of Science and Technology, has developed a mathematical technique for the self-organisation of individual particles to achieve a complex task.
Amoebots
Inspired by the behaviour of amoeba, the geometric amoebot model of programmable matter provides an adaptable framework for modelling self-organising particles. It also facilitates algorithmic research into programmable matter. In this model, programmable matter is depicted as a swarm of decentralised autonomous self-organising particles that operate on a grid of equilateral triangles, made up of nodes, or vertices, and edges.
“Particle hardware can be tailored to suit specific tasks, and whatever is redundant can be discarded.”
The amoebot particles are subject to several constraints. They are finite-state machines with simple computational capabilities. A finite-state machine stores a sequence of different unique states that it transitions between, depending on the values of the inputs and its current state. The particles’ interactions and their communication capabilities are strictly local and are limited to particles located in the neighbouring nodes of the triangular grid. The particles have limited motorial capabilities in that they can only move to an empty neighbouring grid node. In addition, their activation is controlled by an adversarial but fair scheduler. Particles can be in one of two modes: contracted and expanded. When a particle is contracted, it occupies only one node; alternatively, when a particle is expanded, it occupies two neighbouring nodes. It is the particles’ ability to expand and contract that enables them to move around the grid.
The amoebot model is of particular interest from a distributed computing perspective. It is used to help understand the computational power of these simple entities, with applications such as the uniformed coating of shapes, gathering particles, and shape formation. Viglietta examines the latter as a case study to showcase a general problem-solving technique.
Figure 1.
A swarm of unorganised particles spontaneously elects a leader. The leader recruits a small group of particles to form a ‘brain’ with greater computational power. The brain’s computational power comes not from extra hardware, but from the complex interaction of simple particles.
Determining particle capabilities
Viglietta describes a particular goal for theorists: to determine which elementary capabilities (eg, the amount of internal memory, the ability to sense a neighbouring particle and communicate or connect with it, etc.) are required by individual particles to make a large particle system capable of self-organising and achieving a complex task. Engineers can use this knowledge to design more compact and less expensive particles. Particle hardware can be tailored to suit specific tasks, and whatever is redundant can be discarded. This efficiency is crucial to ensure that the programmable particles are very small and aid in their mass production.
Shape-formation problem
The shape-formation problem, also known as the pattern-formation problem, involves a team of particles, initially arranged in an arbitrary connected shape, that has to form a given target shape. Each particle starts with a concise description, a ‘blueprint’ of the target shape in its memory, and coordinates with the other particles. Thereby, the team self-organises, without any external supervision, and forms a suitably scaled-up version of the shape that includes all particles in the system. Successful completion of the task may mean that some particles must be in their expanded state to form the final shape. Usually, the total number of particles is not known; besides, the constant-size memory of a single particle cannot store the total number of particles. Furthermore, as soon as the given blueprint changes, all particles must react and form the new shape. A particular challenge with this task is that the particles are all identical and appear to have no way to coordinate.
Figure 2.
The brain visits each region of the swarm, instructing all the particles on where to move to form the desired shape. The same technique applies not only to shape formation but to any complex task the swarm must perform as a team.
A universal shape-formation algorithm
Viglietta has developed a mathematical technique which demonstrates that, provided amoebots are properly programmed, they can solve the fundamental shape-formation problem. The first stage of his universal shape-formation algorithm involves the election of a leader from among all the particles. This is not a trivial task as an amoebot cannot ‘flip a coin’ or make random choices. Amoebots all behave identically, so everything they do must be deterministic. This novel algorithm contains a deterministic leader-election algorithm as a subroutine to elect a leader. A set of at most three leaders might be required if the initial configuration has unbreakable symmetry. A configuration of particles is said to have unbreakable symmetry if it has a centre of rotational symmetry, of order 2 or more, that does not coincide with any node in the grid of regular triangles.
Electing a leader
The leader-election subroutine comprises four steps. Initially, all particles are eligible to be leaders. Each particle must communicate with its neighbours to ensure that its elimination from the leader election will not disconnect the set of eligible particles. Depending on the eligibility of its neighbours, a particle can decide to remain eligible or remove itself from the election. At the end of this ‘lattice consumption phase’, there can be at most three eligible particles that remain simply connected and become candidate leaders.
In the ‘spanning forest construction phase’, each candidate leader starts constructing a tree (an undirected graph in which any two vertices are connected by exactly one path), with itself as the root (a special node that is a point of reference for other nodes in the tree). In each tree, the particles (or nodes) try to extend the tree in all directions by sending merge requests to their neighbours. Once a particle has accepted a merge request it becomes part of that tree and refuses any further requests. The process continues until all particles are part of a tree, so the tree(s) form a spanning forest.
Figure 3.
Electing a leader, or ‘lattice consumption phase’: a particle can decide to remain eligible or remove itself from the leader election, depending on whether its elimination will disconnect any other eligible particles. At most three particles can become candidate leaders.
Particles can be left- or right-handed. In the ‘handedness agreement phase’, all particles assume the same handedness as their candidate leaders. Some candidate leaders may be eliminated during this process. Finally, the candidate leaders attempt to break symmetries and elect a unique leader in the ‘leader election phase’. If the initial shape has unbreakable symmetry, all candidates become leaders. In this case, each leader supervises the formation of an equal portion of the target shape.
Once elected, the leader recruits a small group of particles and uses their internal storage and relative positions to simulate a Turing machine (ie, a regular computer). This is necessary, as the internal storage of the leader alone is largely insufficient for the task. This enables the leader to become a ‘smarter’ entity that can direct each particle to take up its position within the target shape.
Unfortunately, as Viglietta explains, this technique has two disadvantages. Firstly, it does not cope well with malfunctioning particles. Secondly, simulating a Turing machine introduces a bottleneck that slows down the process.
“The functioning particles can therefore self-organise into a new linear formation, devoid of faulty particles, and continue with their normal tasks.”
Malfunctioning particles
In his preliminary research into the issue of malfunctioning particles, Viglietta has created a set of rules to solve the problem for particles that are initially positioned in a line formation. It is assumed that the particles can communicate with neighbouring particles and move from node to neighbouring node. However, an arbitrary number of particles is faulty and unable to move or communicate. This becomes a reconfiguration problem. First, the system has to self-repair, so the non-faulty particles must reconfigure themselves into a new linear formation that does not include any faulty particles. Then, the system is faced with the problem of coordinated moving, or flocking, where the particles move away, keeping the linear arrangement. The set of local rules for the particles solves the reconfiguration problem regardless of the initial distribution, the number of faulty particles, and the local orientations of the non-faulty particles. This solution enables the particles to reconfigure. Whenever possible a single linear arrangement is created. Alternatively, when symmetries prevent the creation of a single line, the particles form two lines of equal size. The functioning particles can therefore self-organise into a new linear formation, devoid of faulty particles, and continue with their normal tasks.
A reinforcement learning solution
Viglietta is exploring some alternative approaches based on machine learning to mitigate the bottleneck issue. He plans to use the classic coating problem for programmable matter, where a system of programmable particles has to form a thin layer around a two-dimensional object as a case study. The first objective is to apply reinforcement learning techniques to a new, more efficient, and more reliable algorithm for the coating problem. Reinforcement learning involves training machine-learning models to make a sequence of decisions to achieve a goal in an uncertain and potentially complex environment. Possible applications for this innovative technique include autonomous painting of complex structures, monitoring, and repairing.
The design and implementation of an open-source, cross-platform software simulator for programmable matter is also planned. This can be employed to compare the new algorithm with traditional coating algorithms from the literature and will be made available to other researchers in the field. Viglietta hopes to extend this approach to more challenging problems, including universal shape formation, obstacle avoidance, and three-dimensional applications.
What inspired you to include the deterministic leader election algorithm as a subroutine in the Universal Shape Formation Algorithm?
I needed a way to coordinate a chaotic swarm of particles, and making them follow a leader’s orders seemed like a natural strategy. Initially, every particle is in an ‘eligible’ state. Next, a process similar to ‘erosion’ starts from the boundary of the swarm and propagates toward the interior. The particles in the ‘eroded’ regions become ineligible, until only one particle somewhere in the interior remains eligible: this will be the leader. It’s remarkable that this algorithm works in spite of an asynchronous scheduler and regardless of the initial (connected) shape of the swarm, as it only depends on the initial geometry of the swarm, and it doesn’t require any particle to move during the process.
References
- Di Luna, GA, Flocchini, P, Santoro, N, Viglietta, G, Yamauchi, Y, (2020) Shape formation by programmable particles. Distributed Computing, 33, 69–101.
doi.org/10.1007/s00446-019-00350-6 - Di Luna, GA, Flocchini P, Santoro N, Viglietta G, Yamauchi Y, (2020) Mobile RAM and Shape Formation by Programmable Particles. In: Malawski M., Rzadca K. (eds) Euro-Par 2020: Parallel Processing. Euro-Par 2020. Lecture Notes in Computer Science, vol 12247. Springer, Cham.
doi.org/10.1007/978-3-030-57675-2_22 - Di Luna, GA, Flocchini, P, Prencipe, G, Santoro, N, Viglietta, G, (Submitted) Self-Repairing Line of Mobile Finite-State Robots.
10.26904/RF-139-2054748742
Research Objectives
Dr Viglietta has developed a mathematical technique on how individual particles can self-organise to achieve a complex task.
Funding
Japan Advanced Institute of Science and Technology (JAIST)
Collaborators
- Giuseppe Di Luna
- Yukiko Yamauchi
Bio
After obtaining his PhD in computer science in Italy, Giovanni Viglietta worked as a postdoctoral researcher in Canada and Switzerland. In 2018, Dr Viglietta joined the faculty of the Japan Advanced Institute of Science and Technology (JAIST). His research interests include distributed computing, computational geometry, and combinatorial game theory.
Contact
1-50 Asahidai, Faculty Residence D-21
Nomi City, Ishikawa 923–1211, Japan
E: johnny@jaist.ac.jp
T: +81 80 8691 6839 T: +81 0761 51 1207
W: giovanniviglietta.com
