Mobility Matters: A Living Survey of Open Problems on Autonomous Agents, Robots and Particles
Debasish Pattanayak · living survey, version 2026-10-14 · 51 problems, 282 settings, 389 papers
Open the atlasPDFSourceContribute
Abstract
Mobility Matters is a living survey of open problems in distributed computing by mobile entities: agents moving on graphs, robots in the plane, robots searching geometric domains, and programmable matter. Each problem is organised as a tree of settings: its root assumes nothing, and each edge adds one assumption (timing, faults, communication, symmetry breaking, knowledge, and so on), so that algorithms carry over to stronger assumptions and lower bounds to weaker ones. For every setting the survey records the proven lower bounds and what forces them, the paper that introduced the setting, the current best result, the gap between them, and the open questions, each checked against the cited papers. Every assumption comes with its origin and formal definition, every problem with a plain-language first look, and essays connect the problems across models. The survey is maintained as a website and regenerated as a book from the same data.
Contents
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.
Exploration
- Graph exploration by a single agent: One agent starts at a node of an unknown anonymous graph and must visit every node; how much memory does it need, which pebbles or knowledge make it possible, and how fast can it be?
- Collaborative exploration: k agents start together at the root of an unknown graph and must visit all its nodes; how much faster than one agent can a team be?
- Dispersion: Spread k \le n agents over the nodes of an n-node anonymous graph so that no node hosts more than one agent, as fast as possible and with as little memory per agent as possible.
- Treasure hunt: One agent must find a static treasure at an unknown node; the cost should depend on how far the treasure is, not on the size of the graph.
- Rendezvous: Two agents start at different nodes of an unknown graph and must meet; how long does it take, and how much memory or symmetry breaking does it need?
- Black hole search: A black hole destroys every agent that enters it, without trace; a team must locate it, losing as few agents as possible.
- Gathering in graphs: Several agents must all meet at one node of an unknown graph, possibly despite faulty agents.
- Map construction: Agents must not only visit every node but output a map of the anonymous graph, up to isomorphism.
- Exploration of dynamic graphs by teams: An adversary changes the graph over time; how many agents are needed to explore it?
- Exploration by oblivious robots: Oblivious Look–Compute–Move robots with vision must visit every node of a ring or grid and stop; how many robots are needed?
- Exploration by luminous robots: Myopic Look–Compute–Move robots with a light of a few colours must visit every node of a ring, grid or torus, and stop or keep visiting; how many robots and colours are needed?
- Exploration of recolourable graphs: A single agent with little or no memory must visit every node of an anonymous graph whose nodes carry colours it can read and rewrite; how many colours are needed, and how much does it help to recolour, to see neighbours or to have port numbers?
- Network decontamination: A team of agents must clean a contaminated network, or equivalently capture an invisible, arbitrarily fast intruder, using as few agents as possible.
Computing with agents
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.
Formation problems
- Pattern formation: Robots start at distinct points and must form a given geometric pattern, up to similarity; which patterns are formable, and from which initial configurations?
- Gathering: Robots must meet at a single point that is not fixed in advance, and stay there.
- Circle formation: Robots must reach positions on a common circle.
- Uniform circle formation: Robots must form a regular n-gon: a circle with equal spacing.
- Universal pattern formation: Robots must be able to form any pattern from any initial configuration, not only the ones symmetry allows.
- Pattern sequences: Robots must form a given sequence of patterns, one after the other, forever.
- Mutual visibility: Opaque robots must reach positions where no three are collinear, so that every robot sees every other.
- k-grouping: Robots must form k distinct groups, each group at its own point.
- Near-gathering: Robots must get within a small distance of each other without ever colliding.
- Convergence: Robots must get arbitrarily close to a common point; they need not ever meet.
- Partitioning: Robots must partition themselves into k groups of exactly n/k robots each, each group at its own point.
Symmetry breaking and spreading
- Leader election in the plane: Anonymous robots must agree on one of them, using only their positions.
- Scattering: Robots that may start at shared points must move to pairwise distinct points.
- Separation: Robots of different (hidden) colours must separate so that each colour class occupies its own region.
- Uniform deployment on a ring: Robots on a circle must spread out to equal spacing.
- Flocking: Robots must move together as a group, following a leader while roughly keeping a formation.
Robots with unit speed move continuously in a known domain (a line, rays, a disk, a polygon) to find a target or an exit whose position is unknown.
Search, evacuation and patrolling
- Linear search (cow path): A robot on a line (or on m rays from a point) must find a target at unknown distance; how small can the competitive ratio be?
- Evacuation: Robots start at the centre of a disk (or a polygon) and must all leave through an exit at an unknown point of the boundary, as fast as possible.
- Chauffeuring a crashed robot: An active robot must find a crashed robot inside a disk and carry it, at reduced speed, to one of e exits on the boundary.
- Patrolling: Robots move forever so that no point of a fence (a segment, a circle, or the edges of a graph) stays unvisited for long.
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.
Self-organising particle systems
- Leader election in programmable matter: Anonymous constant-memory particles must elect exactly one leader, which most shape-formation algorithms need first.
- Shape formation in programmable matter: Particles must rearrange into a target shape (a line, a triangle, any shape built from triangles).
- Coating: Particles must cover a fixed object as uniformly as possible: in layers, each filled before the next.
- Compression: Particles following a local stochastic rule must gather into a configuration with small perimeter.
- Convex hull formation: Particles must enclose an object in its convex hull, sensing only locally.
- Scattering of particles: Particles must reach a configuration in which no two particles occupy neighbouring nodes.
- Separation of coloured particles: Particles of two colours, following a local stochastic rule, must cluster by colour (or mix).
- Alignment: Oriented particles, following a local stochastic rule, must align their orientations.
- Bridging: Particles moving between two sites must build a bridge across a gap that balances path length against bridge cost.
- Energy distribution: Only some particles reach the energy source; particles must share energy so that every action is paid for.
- Shape formation by hybrid programmable matter: One finite-automaton agent rearranges passive tiles into a target shape.
- Centralised transformations of modular robots: A centralised algorithm must transform one connected shape of n modules on the square grid into another using local moves.
How to cite
Debasish Pattanayak. Mobility Matters: A Living Survey of Open Problems on Autonomous Agents, Robots and Particles. Living survey, version 2026-10-14. https://drdebmath.github.io/mobility-matters/
@misc{Pattanayak2026Mobility,
author = {Debasish Pattanayak},
title = {{Mobility Matters: A Living Survey of Open Problems on Autonomous Agents, Robots and Particles}},
year = {2026},
howpublished = {\url{https://drdebmath.github.io/mobility-matters/}},
note = {Living survey, version 2026-10-14}
}
Licence
Text and data: CC BY 4.0 · code: MIT. AI use: Claude (Anthropic) was used in cataloguing the problems.