Mobility Matters: A Living Survey of Open Problems on Autonomous Agents, Robots and Particles
Debasish Pattanayak · living survey, version 2026-11-11 · 60 problems, 419 settings, 757 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. The settings of each problem form a directed acyclic graph: a setting is a set of assumptions (timing, faults, communication, symmetry breaking, knowledge, and so on), the setting that assumes nothing comes first, and each edge leads to a setting that assumes more, so that algorithms carry over to stronger settings 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?
- Collision-free exploration: Agents start at distinct nodes of a graph and must explore it so that no two agents are ever at the same node; how long does it take, and what must the agents sense of each other?
- 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.
- Uniform deployment on graphs: Spread k \le n agents that start on distinct nodes of an n-node graph so that they end evenly spread, on a ring every two consecutive agents at distance \lfloor n/k\rfloor or \lceil n/k\rceil, and stop.
- 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.
- Gathering by oblivious robots on graphs: Oblivious Look–Compute–Move robots must all reach one node of a graph and stay there; which starts can be gathered depends on the symmetries of the graph, on multiplicity detection and on the scheduler.
- 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?
- Broadcast by agents in dynamic graphs: One agent holds a message; an adversary changes the graph every round, keeping it connected. How many agents are needed so that the message always reaches every agent?
- Delivery by energy-constrained agents: Agents with energy budgets, placed in a weighted graph, must carry a message from a source node to a target node, handing it over when they meet: when can a planner find a schedule quickly, and by how much must the budgets grow?
- Exploration by oblivious robots: Oblivious Look–Compute–Move robots that see all robots must visit every node of a ring or grid and stop, or keep visiting every node forever without two robots ever meeting; 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.
- Online exploration of weighted graphs: One agent must visit every node of an unknown weighted graph and return to its start node, learning the edges at each node only when it gets there; how close to a shortest tour can its cost be?
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?
- Search for a moving target: A target starts at unknown distance d from the origin of a line (or of m rays) and moves at constant speed u; how fast can robots capture it, depending on what they know about d and u?
- 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.
- Search with segment visibility: Robots search the plane for a point that they see when it lies on the segment joining two of them.
- 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-11-11. https://debasishpattanayak.com/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://debasishpattanayak.com/mobility-matters/}},
note = {Living survey, version 2026-11-11}
}
Licence
Text and data: CC BY 4.0 · code: MIT. AI use: Claude (Anthropic) was used in cataloguing the problems.