From robots to particles

Programmable matter, a term that Di Luna et al. trace to Toffoli and Margolus, is matter that can change its physical properties "in a programmable fashion, based upon user input or autonomous sensing", usually imagined as many small, locally interacting computational particles; the intended uses include smart materials, autonomous monitoring and repair, and minimally invasive surgery Di Luna et al. 2020. Navarra and Piselli add that ideas that were "mostly theoretical" in the early 1990s have become realistic as nano-technology advanced Navarra & Piselli 2023.

The amoebot model, introduced at SPAA 2014 Derakhshandeh et al. 2014, is "motivated by micro- and nano-scale robotic systems with strictly limited computational and locomotive capabilities" Daymude et al. 2023. Particles occupy nodes of the triangular lattice, have constant memory, and move by expanding into an empty neighbouring node and contracting again, like an amoeba Emek et al. 2019. The system must stay connected, "to prevent the particles from drifting apart in an uncontrolled manner like in fluids and because in our case particles communicate only via bonds" Derakhshandeh et al. 2015. As results accumulated, the model's assumptions diverged; Daymude, Richa and Scheideler proposed the canonical amoebot model to separate core features from assumption variants and to treat concurrency explicitly, since much earlier work "implicitly assumes amoebot actions are isolated and reliable" Daymude et al. 2023.

Di Luna, Flocchini, Santoro, Viglietta and Yamauchi say it directly: shape formation is the problem "called pattern formation in swarm robotics", and it has been "intensively studied" for autonomous mobile robots Di Luna et al. 2020. Derakhshandeh et al. posed shape formation together with leader election, because "most shape formation algorithms depend on some seed element", and asked whether shape formation can be solved when leader election cannot Derakhshandeh et al. 2015. With chirality, a sequential scheduler and randomization, any shape made of a constant number of triangles can be formed from a well-initialised start Derakhshandeh et al. 2016.

The deterministic answer echoes Suzuki and Yamashita. Di Luna et al. characterise the shapes that can be formed from any simply connected start: as in the plane, feasibility depends on the symmetry of the start; chirality turns out to be "computationally irrelevant"; randomization lets any shape be formed once there are enough particles; and \(O(n^2)\) moves suffice for \(n\) particles, which is optimal Di Luna et al. 2020. The comparison with the plane is the one in Flocchini et al. 2017: there the symmetricity of the start decides which patterns are formable.

Leader election is the primitive behind most amoebot algorithms: a unique leader "breaks symmetry and coordinates the remaining amoebots", and Emek et al. set the goal of an algorithm that "requires as few assumptions as possible" Emek et al. 2019. Dufoulon, Kutten and Moses recount the history: early deterministic algorithms assumed that the system has no holes, or elected up to six leaders; using movement removed the restriction on the shape but cost at least quadratic time Dufoulon et al. 2021. Emek et al. elect a unique leader deterministically without chirality, and the particles also agree on a chirality Emek et al. 2019; with chirality and a strong scheduler, Dufoulon et al. do it in linear time, as fast as the randomized algorithms Dufoulon et al. 2021 Daymude et al. 2017.

The contrast with robots in the plane is instructive. Robots that only see can elect a leader only from configurations that are not symmetric Dieudonné et al. 2013. Particles have constant memory, read their neighbours and stay connected, and these powers break symmetries that positions alone cannot. Particles that do not move form a separate line of work: with chirality on hole-free systems Gastineau et al. 2019, with holes but up to six leaders Bazzi & Briones 2019, under an asynchronous adversary Briones et al. 2023, and self-stabilising Chalopin et al. 2025.

SILBOT takes the extra powers away. Navarra and Piselli describe it as "one of the weakest models" for programmable matter: it "includes concurrency and eliminates direct communication among particles as well as local and shared memory", and in exchange particles see two hops instead of one Navarra & Piselli 2023. Its aim, introduced by D'Angelo et al. D'Angelo et al. 2020, is the minimal setting in which basic tasks remain solvable, which is the question Suzuki and Yamashita asked of robots.

The limits of oblivious robots return. In SILBOT up to three leaders are elected on hole-free configurations D'Angelo et al. 2020. A line cannot be formed with chirality alone; with a full common orientation it takes \(O(n^2)\) moves for \(n\) particles, which is optimal Navarra & Piselli 2023. With chirality, particles coat a convex object with one layer in \(O(n^2)\) rounds Navarra & Piselli 2023, and particles can scatter so that no two are neighbours Navarra et al. 2025, a lattice counterpart of scattering in the plane Dieudonné & Petit 2009.

A second approach drops coordination altogether. Cannon, Daymude, Randall and Richa define an energy function whose minima are the desired configurations, design a Markov chain whose stationary distribution favours them, and make each transition probability computable from a particle's neighbourhood, so that the chain becomes a local, asynchronous algorithm; being a Markov chain, it is "inherently robust and oblivious" Cannon et al. 2016. The motivation is natural systems such as fire ants forming rafts, where each individual "can take cues from its immediate neighbors" without seeing the group Cannon et al. 2016. For compression, a bias \(\lambda > 2+\sqrt2\) towards having more neighbours makes the system compress, while \(\lambda < 2.17\) makes it expand Cannon et al. 2016.

The same recipe was extended one ingredient at a time. With two colours and a second bias, one algorithm separates or integrates the colour classes, a behaviour seen in bacteria, social insects and human groups Cannon et al. 2019. With orientations, particles align or do not for every number \(q \ge 2\) of orientations, a variant of the Potts model Kedia et al. 2022. With terrain, particles build shortcut bridges across a gap, inspired by army ants that balance "the benefit of increased foraging trail efficiency" against the cost of the workers in the bridge Arroyo et al. 2018. For fire-ant bridges, Oh et al. show that a single bridge forms for large biases, and argue that this "follows from a statistical inevitability, and not from the sophistication of the individuals" Oh et al. 2024.

The stochastic results describe the stationary distribution, not when it is reached: no catalogued paper bounds the mixing time, and for compression the behaviour for \(2.17 \le \lambda \le 2+\sqrt2\) is not determined Cannon et al. 2016. For SILBOT, Navarra and Piselli ask whether one common direction suffices for line formation, whether 1-hop visibility suffices, and which other shapes can be formed Navarra & Piselli 2023; coating without chirality is open Navarra & Piselli 2023. For leader election, linear-time deterministic election without chirality, and under schedulers weaker than the strong one, are open Dufoulon et al. 2021.