Mobility Matters

Mobility Matters

A Living Survey of Open Problems on Autonomous Agents, Robots and Particles

What is known, what is tight, and what is open, under which assumptions.

Last updated · what changed

AI use Claude (Anthropic) was used in cataloguing the problems.

The problem space is a directed acyclic graph. Independent assumptions, one per axis (the graph or domain, the scheduler, what the entities see, remember and share, the faults), come together to define a problem, and each particular setting appears as a leaf of the graph: a problem solved under one set of assumptions. Results move along the edges: an algorithm for weaker assumptions works under stronger ones, and a lower bound for stronger assumptions holds under weaker ones. Assumption sets also change over time: later work minimises the set a result needs, a stronger assumption subsumes weaker ones, and some assumptions become irrelevant in the presence of better ones. Every setting records the proven lower bounds and what forces them, the paper that introduced it, the current best result, and the gap between them.

Explore by assumptionsOpen questionsTimelineReferencesPDF

Four models

Model 1

Mobile agents on graphs

Memory-bounded agents move along the edges of a port-labelled graph, by default with anonymous nodes; what they can see, remember, say and rely on is fixed by its assumption axes.

19 problems136 settings101 open questions

Exploration

Graph exploration by a single agentTreasure huntRendezvousGathering in graphsMap constructionExploration by oblivious robotsExploration by luminous robotsExploration of recolourable graphsCollaborative explorationDispersionBlack hole searchExploration of dynamic graphs by teamsNetwork decontamination

Computing with agents

Leader election by agentsMaximal independent set by agentsMinimal dominating set by agentsTriangle and butterfly counting by agentsMinimum spanning tree by agentsBFS tree by agents
Axes, definitions and problem trees →
Model 2

Mobile robots in the plane

Anonymous point robots in the Euclidean plane repeat Look–Compute–Move cycles; what they agree on, remember, see and rely on is fixed by its assumption axes.

16 problems77 settings39 open questions

Formation problems

Pattern formationCircle formationUniform circle formationUniversal pattern formationPattern sequencesMutual visibilityk-groupingGatheringNear-gatheringPartitioningConvergence

Symmetry breaking and spreading

Leader election in the planeScatteringSeparationUniform deployment on a ringFlocking
Axes, definitions and problem trees →
Model 4

Programmable matter

Many tiny particles with constant memory occupy nodes of the triangular lattice, move by expanding and contracting, and must self-organise into a shape or elect a leader.

12 problems29 settings15 open questions

Self-organising particle systems

Leader election in programmable matterShape formation in programmable matterCoatingCompressionSeparation of coloured particlesAlignmentBridgingConvex hull formationScattering of particlesEnergy distributionShape formation by hybrid programmable matterCentralised transformations of modular robots
Axes, definitions and problem trees →

Perspectives

Essays that connect problems across models, in reading order

Why compute by moving

The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.

Symmetry is the adversary

Identical agents running the same deterministic program can be kept in lockstep forever. Across graphs, the plane and programmable matter, the papers break this symmetry with identifiers, with randomness, with asymmetric starts, or with the scheduler, and leader election keeps reappearing as the common core.

Finding your way

A single agent in an anonymous graph: how much memory it needs, what a pebble, an advice string or knowledge of n buys, why stopping is harder than exploring, and how treasure hunt asks for exploration only as far as the target. Each line of papers, in its own words, on why the question matters.

From exploration to dispersion, and beyond

How collaborative exploration asks how much a team speeds up a search, how dispersion arose as the case k = n under weaker assumptions, what dispersion gives back to exploration, and why dispersing first has become the standard opening move for computing graph structures with agents.

Meeting at one place

Rendezvous and gathering on graphs, gathering and convergence in the plane, and evacuation through an unknown exit all ask entities to end at one point. The papers give the same reasons for meeting, but each model makes a different part of it hard: symmetry and exploration on graphs, capability in the plane, information in continuous search.

Weak robots in the plane

Why the theory of robots in the plane starts from oblivious, anonymous, disoriented points; how formation problems became its testbed and the scheduler its adversary; and how a light with a few colours turned into memory, communication and a measure.

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.

From the cow path to evacuation

The line of work from Bellman's and Beck's linear search problem to group search with faulty robots, evacuation of disks and polygons, priority evacuation, and patrolling by robots with distinct speeds.

When agents fail

A node that destroys visitors, a robot that stops, an agent that lies, a searcher that misses the target: the papers motivate each fault by the hardware or the network, and each kind of fault changes a different measure, from team size to feasibility to an exact constant.

What forces the bounds

Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.

The most consequential open problems

Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.