Mobility Matters
Home›Programmable matter›Self-organising particle systems›Scattering of particles

Scattering of particles

Particles must reach a configuration in which no two particles occupy neighbouring nodes.

Problem statement and measurescollapse
Start: a crowded triangle; every particle with a neighbour is activatedActivated particles expand into the middle of their longest run of 3 to 5 empty neighbouring nodes… and contract thereParticles that still have a neighbour are activated againFinal: no two particles are neighbours; none is activated, all stop
Scattering under event-driven activation Navarra et al. 2025: from a configuration of contracted particles, here a triangle of ten, the particles must reach a configuration in which no two occupy neighbouring nodes, and stop. A particle is activated only while it has a neighbour (blue). An activated particle finds its longest run of consecutive empty neighbouring nodes; if the run has 3, 4 or 5 nodes, it makes an expansion into the middle node (outlined: the activated particles that move) and then a contraction there, otherwise it stays. In this run every activated particle acts in each step and all particles break ties the same way; isolated particles (green) are never activated again.

From any initial configuration of \(n\) contracted particles (each occupying one node of the triangular lattice), the particles must reach a configuration in which no two occupy neighbouring nodes (a scattered configuration), and stop.

Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Picture people standing in a crowded square who must spread out until nobody is standing right next to anyone else. The floor is the triangular lattice: the endless graph whose nodes are the corners of a tiling of the plane by equal triangles; each node is joined by an edge to six others, its neighbours. A particle occupies one node and moves in two actions: an expansion into an empty neighbouring node, after which it occupies both, then a contraction into one of the two; so one expansion and one contraction move it by one node. There are \(n\) particles, each occupying one node at the start; the set of occupied nodes is the configuration. The particles are oblivious (they remember nothing from one action to the next) and silent (they send no messages); each decides only from what it sees around it. The goal is to reach a scattered configuration, where no two particles occupy neighbouring nodes, and then stop moving. The basic question is whether this is possible at all, from every starting configuration.

1AlgorithmActivated only when crowded SILBOT with event-driven activation → Navarra et al. 2025

Navarra, Piselli and Prencipe Navarra et al. 2025 let each particle see only its six neighbouring nodes, give the particles no common sense of direction, and use event-driven activation: a contracted particle is activated (it gets a turn to act, an activation) as soon as it has a neighbour, and only then.

  1. A particle with no neighbour is never activated, so it stays put.
  2. An activated particle looks around itself and finds the longest run \(I\) of consecutive empty neighbouring nodes.
  3. If \(I\) has 3, 4 or 5 nodes, the particle makes an expansion into the most central node of \(I\) (in a tie, the one it sees as rightmost), and a contraction into that node once it is free; otherwise it stays.
  4. When no particle has a neighbour, no particle is activated again: the task is done and the particles have stopped.
Why it works and what it costs. Event-driven activation gives stopping for free: a scattered configuration is exactly one in which nobody is ever activated again. The difficulty is choosing the local rule so that crowded particles really do spread out instead of moving back and forth forever. The proof looks at the smallest regular hexagon around a fixed centre that contains all particles: a particle on its border never moves inwards, each particle moves away from the centre at most \(n-1\) times (Lemma 4 of Navarra et al. 2025), so the particles on the outermost hexagon end with no neighbour, and induction on \(n\) handles the rest (Theorem 6). The paper gives no bound on rounds or moves.

Why it matters. It shows how much the choice of scheduler can replace memory: with a 1-hop view and the usual asynchronous scheduler scattering is impossible (Theorem 4 of Navarra et al. 2025), but with event-driven activation particles without memory scatter and stop.

2Lower boundA crowded hexagon must spread over three times its area SILBOT with event-driven activation →

This simple counting argument is ours; the catalogue records no lower bound on time or moves. In the triangular lattice every small triangle of three mutually neighbouring nodes can hold at most one particle of a scattered configuration. Counting triangles, a region with \(N\) nodes can hold at most about \(N/3\) scattered particles. Now start with the \(n\) particles packed into a full hexagon of radius \(r\) (it has about \(3r^2 = n\) nodes). The hexagon of radius \(1.5r\) around the same centre has about \(6.75r^2\) nodes, so it can hold only about \(2.25r^2 = 0.75n\) scattered particles.

Why it holds. So about \(n/4\) particles must end more than \(1.5r\) from the centre, having started within \(r\) of it: each travels at least \(r/2\), which is about \(\sqrt n\) nodes. That is at least about \(n\sqrt n\) moves in total, and, if the scheduler lets each particle act once per round (an interval of time in which every particle is activated at least once), about \(\sqrt n\) rounds. Navarra et al. 2025 give no bound on rounds or moves, so how close their algorithm comes to these numbers is unknown.

Why it matters. It shows that scattering, unlike gathering, forces the occupied region to grow in area, which costs real movement.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Moves
SILBOT
With a 1-hop view and adversarial activation, silent oblivious particles cannot scatter; with the 2-hop view of SILBOT the question is open.
impossible — vs \(\text{impossible}\) symmetry breaking
unknown — vs —
SILBOT with event-driven activation standard
Under event-driven activation, silent oblivious particles with a 1-hop view and no common direction scatter from any configuration without obstacles.
unknown \(\text{finite}\) vs —
unknown — vs —

Open questions 3

SILBOT

  1. Is scattering solvable in SILBOT with its original 2-hop view under adversarial activation? Navarra et al. 2025 leave it open.

SILBOT with event-driven activation

  1. Bound the rounds and moves of scattering under event-driven activation Navarra et al. 2025.
  2. Scattering with obstacles: unsolvable deterministically with a 1-hop view even under a synchronous scheduler (Theorem 7 of Navarra et al. 2025); which extra capability (chirality, a 2-hop view, randomised choices) makes it solvable?

What the community started looking at

Scattering was posed for silent, oblivious particles, where the question is solvability without memory or messages. Navarra, Piselli and Prencipe restrict the 2-hop view of SILBOT to 1 hop; then scattering is unsolvable under the asynchronous scheduler, solvable without obstacles when a particle is activated as soon as it has a neighbour, and unsolvable with obstacles even under a synchronous scheduler Navarra et al. 2025.

Related problems

Scattering: Robots in the plane scatter to distinct points; particles must scatter so that no two are neighbours.

Perspectives

  • From robots to particles Programmable matter re-asks the questions of robots in the plane on a lattice, with particles that touch, remember a little and stay connected; SILBOT takes memory and messages away again, and the stochastic approach replaces algorithms by a biased local rule.

All settings

The assumption tree (2 settings, 0 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Moves); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Memory › Scheduler › Communication › Activation › Orientation › Randomness › Initial shape › Connectivity during execution.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Activation

0adversarial activation1event-driven activation (ED-Async)

Navarra, Piselli and Prencipe introduced event-driven activation for scattering after showing that with a 1-hop view the problem is unsolvable when the adversary controls activations Navarra et al. 2025. Under it "the adversary does not control anymore the activation of contracted particles which becomes an event driven (ED) process"; they read it as sensing that reacts to the stimuli of neighbouring particles. In their words, "this kind of schedule, that we call ED-Async, is less general than the pure asynchronous one, but it is clearly more general than the synchronous case where all particles are always active" Navarra et al. 2025. It is kept as an axis of this problem rather than a value of the model's scheduler axis, because it neither implies nor follows from a sequential scheduler.

Formal definitions
0adversarial activation
The scheduler of the setting decides, fairly, when each particle is activated; an isolated particle may be activated, and a particle with a neighbour may wait any finite time.
1event-driven
A contracted particle is activated as soon as it has, or gains, a neighbour, and a contracted particle with no neighbour is not activated. The adversary still chooses the duration of each activation, the time an expansion or a contraction takes, and the activation of expanded particles; operations stay non-atomic.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.