Steering a Swarm

The result

We compared six ways of choosing the field: two simple baselines, a published algorithm for gathering a swarm with one shared push, and three sequences designed through the simulation. Each was tested on 64 swarms it was never designed on, at three levels of wall friction and under seven changed conditions. The test, its measures and its decision rules were written down before any of these runs.

Designed sequences deliver most of the swarm. At moderate wall friction, the best design puts 95% of the robots in the target outlet, against 82% for a greedy method that picks the best push one move at a time, 61% for the published algorithm translated to these channels, and 16% for pushing along the path to the target. It was found by an evolution strategy, a search that tries random changes to the sequence and keeps what helps, starting from the greedy one. It wins at every friction level tested, by 12 to 16 points over greedy.

Designing for the uncertainty costs nothing. A sequence designed over a range of friction, robot variation and flow did better than one designed for a single condition, even under that single condition (95% against 89%), and better in 16 of the 21 other tests, by up to 17 points with flow on sticky walls (19 with stiffer collisions). It fell behind by about 2 points only on frictionless walls with twice the robots or with stiffer collisions.

Gradients through the simulation didn’t help. The simulation is differentiable, so a sequence can be improved by following the gradient of a smooth score. But collisions make the gradient grow about 20-fold with every move, and capped to stay finite, it didn’t improve on its greedy start (81% against 82%). The search without gradients did, by 13 points.

Sorting by mobility needs a difference of about 1.5×. With identical robots no field separates them, as it must be. At a 1.5× difference in mobility one designed sequence reaches a separation of 0.24 at moderate friction, mostly by delivering the more mobile kind (53% of them, against 5% of the others); at 1.1× it does nothing. A 2× difference separated less than 1.5× at moderate and high friction, which may be the search rather than the physics.

A 2D model with soft collisions, in which robots in a crowd overlap. A check with collisions five times stiffer kept the ranking of the designs but moved the numbers at high friction by up to 16 points, so the main results are quoted at moderate friction. Every comparison is relative: gathering is a hard problem, and nothing here says how close to the best possible any design is.

Loading the results…

Conclusion

One shared push can deliver nearly a whole scattered swarm through a branching network, if the sequence of pushes is designed for it: walls and collisions do the selecting, and a search over sequences in a simulation finds ways to use them that neither a greedy method nor a gathering algorithm made for an idealized grid does. Designing over the conditions one can’t control, friction, robot-to-robot variation and flow, cost nothing and held up better under conditions none of the designs saw. Gradients through the simulation, the obvious tool for a differentiable model, were defeated by collisions; a simple search did better at the same cost. Sorting two kinds of robot with one field works once they differ by about half again in mobility. All of this is in a simplified 2D model; real vessels, real robots and real flow are the test that would settle it.

The science

Magnetic microrobots, from helical swimmers to drug-carrying particles, are driven by fields from coils outside the body. A field is nearly uniform at the scale of a swarm, so every robot gets the same command. Control under a shared input is well studied as a puzzle: in the “tilt” model every particle moves the same way until blocked, and gathering a swarm into one place in a maze-like vessel network is NP-complete. Becker, Fekete and colleagues give algorithms for it; the best of their heuristics, MSTE, repeatedly takes the move that most reduces the total distance to an extreme cell. Their model is a grid of cells; here MSTE’s moves become unit pushes along the axes, each long enough to cross one cell.

Other work uses differences between robots (size, magnetic material) to move two or three independently with one field, wall friction to reshape a swarm, or reinforcement learning to steer a swarm from its observed positions, which needs imaging. This study asks a different question: can a fixed, open-loop sequence, designed through a continuous simulation with walls, friction, collisions and flow, deliver a swarm it has never seen, and does designing over the conditions one can’t control protect it?

The model: a binary tree of channels, three levels deep, each a straight channel with rounded ends. Robots are disks with no inertia; each moves at its mobility times the field, plus the flow, plus a soft push from any robot it overlaps. At a wall the push into the wall is removed and sliding is slowed by Coulomb friction. Every switch in the model is smooth, so it can be differentiated. Flow is parabolic in each channel and halves at each junction.