Notation and assumptions
Each model uses the symbols of its own literature, so that a bound reads the same here as in the papers it comes from. Inside one model a symbol has exactly one meaning. The same letter may mean different things in different models (for example \(n\) counts nodes on graphs and robots in the plane); essays that cross models say which model a symbol belongs to. Where a paper writes a different symbol for the same quantity, the table says so under papers write. Symbols that a single paper defines for its own result are defined where they are used and listed under that problem.
General conventions · Mobile agents on graphs · Mobile robots in the plane · Search in geometric domains · Programmable matter · Index of assumptions
General conventions
| Symbol | Meaning | Papers write |
|---|---|---|
| \(O, \Omega, \Theta, o, \omega\) | asymptotic notation, as \(n\) (or the stated parameter) grows; \(\tilde O\) hides polylogarithmic factors | |
| \(\log\) | logarithm to base 2 unless stated | |
| \(\varepsilon\) | an arbitrarily small positive real (a constant unless stated) | |
| \(\kappa\) | a positive constant whose value does not matter for the statement | |
| \(t\) | time: a round, or a point of time in an asynchronous execution | |
| \(\text{round}\) | in synchronous settings (FSYNC, SSYNC, synchronous agents), one step in which every activated entity performs one full cycle | |
| \(\text{epoch}\) | in asynchronous settings, an interval of time in which every entity completes at least one full cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. Programmable matter calls the same notion an asynchronous round |
Symbols: Mobile agents on graphs
| Symbol | Meaning | Papers write | Used in |
|---|---|---|---|
| \(G=(V,E)\) | the graph; for a directed graph \(E\) is a set of arcs, written \(G=(V,A)\) where both appear | whole model | |
| \(n\) | number of nodes, \(n = |V|\) | whole model | |
| \(m\) | number of edges (arcs) | whole model | |
| \(\Delta\) | maximum degree | whole model | |
| \(\Delta_{out}\) | maximum out-degree of a directed graph | \(d\) in some exploration papers | whole model |
| \(\deg(v),\ \deg_{out}(v)\) | degree and out-degree of node \(v\) | \(\delta(v)\), \(\delta_{out}(v)\) | whole model |
| \(D\) | diameter of the graph (for a tree explored from a root: its height) | whole model | |
| \(\mathrm{tw}\) | treewidth of the graph (of the underlying graph of a temporal graph) | \(k\) Adamson & Spirakis 2026, \(w\) Carnevale 2026 | Graph exploration by a single agent, Exploration of dynamic graphs by teams |
| \(u, v, w\) | nodes (local names) | whole model | |
| \(s\) | the starting node of a single agent, the root of a rooted team, or the home base of black hole search and decontamination | \(h\) (home base), \(r\) (root) | whole model |
| \(k\) | number of agents | \(n\) for robots on graphs Maiti et al. 2026e Maiti et al. 2026d; \(k\) for the ignorant agents only, the source agent not counted, so their \(k\) is \(k - 1\) here Das et al. 2026b Moses Jr. et al. 2025 | whole model |
| \(\ell\) | number of initially occupied nodes; \(\ell=1\) is a rooted start, \(\ell=k\) a dispersed start | Dispersion, Gathering by oblivious robots on graphs | |
| \(f\) | maximum number of faulty agents (crashed or Byzantine) | whole model | |
| \(N\) | a known upper bound on \(n\) | \(\hat n\) | whole model |
| \(\mathcal L\) | the set of agent labels in use; \(|\mathcal L|\) distinct labels, \(|\mathcal L|=1\) anonymous, \(|\mathcal L|=k\) distinct identifiers | \(\ell\) (homonyms) | whole model |
| \(L\) | the largest possible label: labels are integers in \(\{1,\dots,L\}\) | \(\lambda\) (largest identifier), \(\mu\) (largest label) | whole model |
| \(\lambda\) | the smallest label among the agents (for two agents: the smaller label) | \(l\) Pelc 2019 | whole model |
| \(\tau\) | delay between the starting times of two agents | whole model | |
| \(d\) | distance from the starting node to the target (the treasure); otherwise the largest distance between two starting nodes (of the two agents in rendezvous, of two initially occupied nodes in gathering) | \(D\) for the distance between starting positions Pelc 2019; \(\Delta(C)\) Cicerone et al. 2025d Cicerone et al. 2025b | whole model |
| \(v^*\) | the node of the treasure | \(t\) | whole model |
| \(e(d)\) | number of edges with an endpoint at distance less than \(d\) from the start | Treasure hunt | |
| \(w(\cdot),\ W\) | weight of the cheapest path type to the treasure (treasure hunt); \(W\) its maximum over the two directions (rendezvous) | Treasure hunt, Rendezvous | |
| \(h\) | communication range in hops (\(h\)-hop communication) | \(\ell\) Saxena et al. 2026a | whole model |
| \(T\) | window length in \(T\)-interval and \(T\)-path connectivity of dynamic graphs | whole model | |
| \(\mu\) | maximum number of edges missing in a round (\(\mu\)-bounded 1-interval connected graphs) | \(\ell\)-bounded Saxena et al. 2026a; \(k\) (\(k\)-edge-deficient temporal graphs) Lahtin & Zamaraev 2027; \(f\) Kaur et al. 2026b | whole model |
| \(\eta\) | number of transient edges of a temporally connected graph | Exploration of dynamic graphs by teams | |
| \(\delta\) | longest time an edge of a dynamic graph may stay missing | Graph exploration by a single agent, Network decontamination | |
| \(p\) | number of pebbles | whole model | |
| \(b\) | number of bits of an agent's memory, when it is a parameter | whole model | |
| \(\beta\) | number of bits of a label written at a node in advance | Graph exploration by a single agent | |
| \(\phi\) | deficiency of a directed graph: the number of arcs whose addition makes it Eulerian | \(d\) Italiano et al. 2025 | Dispersion, Graph exploration by a single agent |
| \(\nu\) | number of leaves of a tree | \(\lambda\) | Rendezvous |
| \(\mathrm{CR}(k)\) | competitive ratio of a collaborative exploration algorithm with \(k\) agents | Collaborative exploration | |
| \(X(n)\) | time to explore any \(n\)-node graph | \(R(n)\) Bhagat & Pelc 2025, \(R(N)\) Papin 2026 | Dispersion, Collision-free exploration, Gathering in graphs |
| \(\mathrm{port}_v\) | port numbering at node \(v\) | \(\lambda_v\) | Graph exploration by a single agent |
| \(R\) | running time, in rounds, of a message-passing algorithm simulated by agents | Leader election by agents, Maximal independent set by agents, Minimal dominating set by agents, Minimum spanning tree by agents, BFS tree by agents, Triangle and butterfly counting by agents | |
| \(K\) | number of states of a finite-automaton agent | Graph exploration by a single agent, Exploration of recolourable graphs | |
| \(\gamma\) | exponent of the team size in large-team collaborative exploration, \(k = Dn^{\gamma}\) | Collaborative exploration | |
| \(\theta\) | the exponent of Reingold's universal exploration sequences | Treasure hunt | |
| \((q,\rho)\) | type of a path: its largest port \(q\) and its length \(\rho\) | Treasure hunt | |
| \(z\) | number of nodes of non-zero capacity | Dispersion | |
| \(r\) | radius of a ball of the grid | Dispersion | |
| \(c\) | number of colours (of a robot's light, or of the colours a node can hold) | \(\kappa\), \(\ell\) | Exploration by luminous robots, Exploration of recolourable graphs |
| \(\varphi\) | visibility range of a myopic robot, in hops | Exploration by luminous robots | |
| \(a\times b\) | size of a grid or torus with \(a\) rows and \(b\) columns | Exploration by luminous robots, Broadcast by agents in dynamic graphs, Gathering by oblivious robots on graphs | |
| \(\psi(v)\) | current colour of node \(v\) | \(c(v)\) | Exploration of recolourable graphs |
| \(c_0\) | initial colour of the nodes | Exploration of recolourable graphs | |
| \(\pi_v\) | rotor pointer at node \(v\): the port the next departing agent takes | Exploration of recolourable graphs | |
| \(N(v)\) | the neighbours of node \(v\) | Exploration of recolourable graphs | |
| \(\mathrm{circ}(G)\) | circumference of \(G\): the length of its longest cycle | \(k\) | Exploration of recolourable graphs |
| \(g\) | a known upper bound on the circumference | Exploration of recolourable graphs | |
| \(\mathrm{wt}(e)\) | weight (length) of edge \(e\) of a weighted graph | \(w(e)\) | Online exploration of weighted graphs, Delivery by energy-constrained agents |
| \(\mathrm{OPT}\) | cost of a shortest closed walk through all nodes (an optimal travelling-salesperson tour) | \(\mathrm{Opt}(G)\) | Online exploration of weighted graphs |
| \(\vartheta\) | largest ratio \(\mathrm{wt}^+(e)/\mathrm{wt}^-(e)\) between the ends of the announced interval of an edge weight | \(\alpha\) Gehnen et al. 2025 | Online exploration of weighted graphs |
| \(\Pi\) | a decision problem: a set of configurations (graph, start nodes and inputs of the agents) | Deciding graph properties by mobile agents | |
| \(B,\ B_i\) | energy budget: the largest total distance an agent may travel (\(B_i\) for agent \(i\), \(B\) when all budgets are equal) | \(R_i\) (range) Chalopin et al. 2013 Chalopin et al. 2014; \(P\) (power) Anaya et al. 2016 | Delivery by energy-constrained agents |
| \(v_s,\ v_t\) | source and target node of the message in delivery | \(s\), \(t\) | Delivery by energy-constrained agents |
Symbols: Mobile robots in the plane
| Symbol | Meaning | Papers write | Used in |
|---|---|---|---|
| \(n\) | number of robots | \(N\) in some mutual visibility papers | whole model |
| \(f\) | maximum number of faulty robots (crashed or Byzantine) | whole model | |
| \(\ell\) | number of distinct labels of homonymous robots; \(\ell=1\) anonymous, \(\ell=n\) distinct identifiers | \(h\) | whole model |
| \(c\) | number of colours of a light | whole model | |
| \(V\) | visibility radius (limited visibility) | whole model | |
| \(\delta\) | minimum distance a robot travels in a non-rigid move before the adversary may stop it | whole model | |
| \(\Delta_0\) | diameter of the initial configuration | \(D_E\) | whole model |
| \(k\) | number of groups (\(k\)-grouping; in partitioning the number of fixed points, each receiving \(n/k\) robots) | Bhagat et al. 2021 write \(k\) for the group size of partitioning, which is \(n/k\) here | k-grouping, Partitioning, Separation |
| \(L\) | length (circumference) of the ring or circle | \(\ell\) | Uniform deployment on a ring |
| \(d\) | the target spacing \(L/n\) in uniform deployment | Uniform deployment on a ring | |
| \(m\) | number of patterns in a sequence | Pattern sequences | |
| \(\lambda\) | contraction factor of a \(\lambda\)-contracting gathering protocol | Gathering, Near-gathering | |
| \(r, s\) | robots (local names) | whole model | |
| \(g\) | hop diameter of the initial visibility graph | \(D_G\), \(D\) | Gathering, Scattering |
| \(\phi\) | expected running time function of scattering algorithm \(SA_\phi\) | \(f\) | Scattering |
Symbols: Search in geometric domains
| Symbol | Meaning | Papers write | Used in |
|---|---|---|---|
| \(k\) | number of robots | \(n\) | whole model |
| \(f\) | maximum number of faulty robots (crash or Byzantine) | whole model | |
| \(m\) | number of rays sharing an endpoint | whole model | |
| \(e\) | number of exits on the boundary | Chauffeuring a crashed robot | |
| \(d\) | distance from the origin to the target (on a line, on rays or in the plane) | whole model | |
| \(x\) | position of the target on the line | whole model | |
| \(R\) | radius of the disk (results are usually stated for \(R=1\)) | whole model | |
| \(v,\ v_i\) | speeds of robots (robot \(i\) moves at speed at most \(v_i\)) | \(s\), \(s_i\) | whole model |
| \(\alpha\) | known arc distance along the boundary (between two exits, or between the treasure and the exit) | \(d\) | whole model |
| \(r\) | communication range of wireless robots | whole model | |
| \(\ell\) | length of the fence (segment or circle) | Patrolling | |
| \(L\) | known distance between the starting points of two robots | Evacuation | |
| \(p\) | index of an \(\ell_p\) norm | Evacuation | |
| \(w\) | weight of the second robot's arrival time in weighted group search | Evacuation | |
| \(\sigma\) | number of servants in priority evacuation (the queen and \(\sigma\) servants, \(k=\sigma+1\) robots) | \(n\) | Evacuation |
| \(u\) | speed of a moving target, which moves at constant speed toward or away from the origin | \(v\); Coleman et al. 2026a write \(u\) for the evasiveness \(1/(1-u)\) | Linear search (cow path), Search for a moving target |
Symbols: Programmable matter
| Symbol | Meaning | Papers write | Used in |
|---|---|---|---|
| \(n\) | number of particles (modules, tiles) | whole model | |
| \(D\) | diameter of the configuration (largest lattice distance between two particles) | whole model | |
| \(L_{out},\ L_{max}\) | length of the outer boundary and of the longest boundary of the configuration | Leader election in programmable matter | |
| \(\lambda\) | bias towards having more neighbours (stochastic approach) | whole model | |
| \(\gamma\) | bias towards neighbours of the same colour (separation) | Separation of coloured particles | |
| \(\alpha\) | compression factor: perimeter at most \(\alpha\) times the minimum | Compression | |
| \(q\) | number of orientations (alignment) | Alignment | |
| \(s\) | number of energy sources | Energy distribution | |
| \(k\) | symmetricity of a configuration (a \(k\)-symmetric configuration admits up to \(k\) leaders) | Leader election in programmable matter |
Index of assumptions
Every assumption the atlas uses, with its formal definition: the axes of each model, then the assumptions specific to single problems. Level 0 assumes nothing; each higher level is a stronger assumption. Where the assumptions come from is told on each model page.
Mobile agents on graphs
Graph dynamics Mobile agents on graphs
- 0any dynamics
- A temporal graph is a sequence \(\mathcal G=(G_t)_{t\ge 0}\) with \(G_t=(V,E_t)\) on a fixed node set. It is temporally connected if for all \(u,v\in V\) and every time \(t\) there is a journey (a path whose edges appear at non-decreasing times \(\ge t\)) from \(u\) to \(v\). No \(G_t\) need be connected.
- 1connected every round explore →
- \(\mathcal G=(G_t)_{t\ge0}\) is 1-interval connected if every snapshot \(G_t=(V,E_t)\) is connected. More generally it is \(T\)-interval connected if for every \(t\) the graph \(\bigl(V,\bigcap_{i=t}^{t+T-1}E_i\bigr)\) is connected.
- 2static graph explore →
- \(G_t=G\) for all \(t\): the edge set never changes.
Edge direction Mobile agents on graphs
- 0directed
- \(G=(V,A)\) with \(A\subseteq V\times V\); an agent at \(u\) may move along \((u,v)\in A\) only, never back along it unless \((v,u)\in A\). \(G\) is strongly connected.
- 1undirected explore →
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
Number of agents Mobile agents on graphs
- 0any \(k\)
- The number of agents \(k\ge1\) is arbitrary; \(k>n\) is allowed.
- 1\(k \le n\) explore →
- The number of agents satisfies \(1\le k\le n\).
Identifiers Mobile agents on graphs
- 0anonymous
- All agents run the same deterministic algorithm on the same input; no agent has a label. Formally the label function is constant: \(\mathrm{id}(a)=\mathrm{id}(b)\) for all agents \(a,b\).
- 1homonymous explore →
- Each agent \(a\) has a label \(\mathrm{id}(a)\in\mathcal L\) known to itself (and revealed on meeting), but the labelling need not be injective: \(1\le|\{\mathrm{id}(a)\}|\le k\). With \(|\mathcal L|\) distinct labels, \(|\mathcal L|=1\) is the anonymous case and \(|\mathcal L|=k\) the eponymous one Delporte-Gallet et al. 2013.
- 2distinct IDs (eponymous) explore →
- Distinct identifiers (eponymous agents): the label function \(\mathrm{id}:\{1,\dots,k\}\to\{1,\dots,L\}\) is injective; usually \(L=k^{O(1)}\), so a label takes \(O(\log k)\) bits.
Randomness Mobile agents on graphs
- 0deterministic
- The next state and move of an agent are a function of its current state and what it observes.
- 1private coins explore →
- Each agent additionally has access to independent fair coin flips; guarantees hold with probability 1, in expectation, or with high probability, as stated per result.
Faults Mobile agents on graphs
- 0any faults
- Up to \(f\) agents behave arbitrarily (adversarially) and may forge identifiers, i.e. report any label in \(\mathcal L\).
- 1at most weak Byzantine faults explore →
- Up to \(f\) agents behave arbitrarily but always report their own true identifier.
- 2at most crash faults explore →
- Up to \(f\) agents may stop forever at an adversarially chosen time; a crashed agent stays at its node (or vanishes, as stated per result) and never acts again.
- 3no faults explore →
- All agents follow the algorithm forever.
Communication Mobile agents on graphs
- 0no communication
- Agents exchange no messages; an agent at \(v\) observes only the number of agents at \(v\) (and, where stated, whether that number changed).
- 1local communication explore →
- Agents at the same node at the same time can read each other's entire memory (face-to-face communication). Agents crossing on an edge do not meet.
- 2\(h\)-hop communication explore →
- For a fixed \(h \ge 1\), stated with each result: at every round an agent at \(v\) can read the memory of every agent at a node \(u\) with \(\mathrm{dist}(v,u) \le h\) (in the current snapshot \(G_t\) for a dynamic graph), in addition to the co-located agents. \(h = 1\) is 1-hop communication (agents at neighbouring nodes communicate); local communication is the case \(h = 0\), and global communication the case \(h \ge D\). Reading another agent's memory does not tell an agent which port leads to it.
- 3global communication explore →
- At every round every agent can read the memory of every other agent, wherever it is.
Timing Mobile agents on graphs
- 0asynchronous
- Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
- 1synchronous explore →
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
Node memory Mobile agents on graphs
- 0no whiteboards
- Nodes have no storage: no information can be left at a node except by an agent staying there.
- 1whiteboards explore →
- Each node \(v\) has a whiteboard of bounded size that agents at \(v\) can read and write, with mutual exclusion.
Node identifiers Mobile agents on graphs
- 0anonymous nodes
- Nodes have no identifiers; an agent at \(v\) sees only \(\deg(v)\) and the port numbers \(1,\dots,\deg(v)\), which are assigned locally and independently at each endpoint of an edge.
- 1labelled nodes explore →
- Each node \(v\) carries a distinct identifier that agents at \(v\) can read; hence an agent can recognise a node it has visited.
Topology Mobile agents on graphs
- 0any topology
- \(G\) is any connected graph in the class allowed by the other axes.
- 1ring explore →
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
- 1tree explore →
- \(G\) is connected and acyclic: \(|E|=n-1\).
- 1grid explore →
- \(G\) is a \(\sqrt n\times\sqrt n\) grid graph; whether ports are globally consistent (oriented) is stated per result.
- 1complete graph explore →
- \(G=K_n\): every pair of nodes is adjacent.
- 1hypercube explore →
- \(G=Q_j\): nodes are the \(n=2^j\) binary strings of length \(j\), adjacent when they differ in one bit.
- 1bipartite explore →
- \(V = V_1 \cup V_2\) with \(V_1 \cap V_2 = \emptyset\) and every edge joining \(V_1\) to \(V_2\); trees are a special case.
Initial configuration Mobile agents on graphs
- 0any start
- Agents start at arbitrary nodes; \(\ell\le k\) nodes are initially occupied, possibly with several agents each.
- 1rooted start explore →
- All \(k\) agents start at the same node (\(\ell=1\)). Also called co-located (black hole search: all agents at the home base) or a rooted graph Molla & Moses Jr. 2019.
- 1dispersed start explore →
- Every initially occupied node holds exactly one agent (\(\ell=k\)). Also called a scattered start, notably in black hole search.
Specific to Graph exploration by a single agent
Knowledge Graph exploration by a single agent
- 0nothing known
- The agent knows nothing about \(G\): not \(n\), \(m\), \(\Delta\) or \(D\).
- 1knows a bound on \(n\) explore →
- The agent is given an integer \(N\ge n\) (an upper bound on the number of nodes) as input.
- 2knows the map explore →
- The agent is given a graph isomorphic to \(G\), with port numbers, and (where stated) its own position on it; for a dynamic graph, the whole sequence \((G_t)\).
Markers Graph exploration by a single agent
- 0no markers
- The agent cannot mark nodes.
- 1one pebble explore →
- The agent carries one pebble that it can drop at its current node and later pick up; it sees whether a pebble is at its node.
- 2pebbles explore →
- The agent carries \(p\) pebbles (identical or distinguishable, as stated); \(p\) is a resource reported with the memory.
Preprocessing Graph exploration by a single agent
- 0adversarial ports
- Port numbers (and any node labels) are chosen by an adversary.
- 1designer ports explore →
- Before the agent starts, the designer may choose the port numbering \(\mathrm{port}_v:\{\text{edges at }v\}\to\{1,\dots,\deg(v)\}\) at every node. Ilcinkas calls a designer's port numbering a local orientation Ilcinkas 2008.
- 1designer labels explore →
- Before the agent starts, the designer may write a label of \(b\) bits (a constant) at every node, which the agent reads on arrival.
Termination requirement Graph exploration by a single agent
- 0with return
- The agent visits every node and then halts at its start node \(s\).
- 1with stop explore →
- The agent visits every node and then halts, at any node. Also called terminating exploration.
- 2perpetual explore →
- Every node is visited at least once (and, for periodic exploration, infinitely often); the agent never needs to halt.
Specific to Collaborative exploration
Team size Collaborative exploration
Connectivity of the team Collaborative exploration
- 0connected team
- In every round the nodes occupied by the agents induce a connected subgraph. An algorithm is then compared with the best traversal of the known graph by a team that obeys the same rule Mutzari et al. 2026.
- 1free team explore →
- Agents may be anywhere in the graph.
Specific to Dispersion
Grid orientation Dispersion
- 0unoriented
- Port labels carry no global meaning: at every node \(v\) the \(\delta_v\) incident edges get the labels \(1,\dots,\delta_v\) in an arbitrary order, chosen independently at each node, so an agent that enters \(v\) cannot tell from the labels which port continues in the same row or column. This is the default on every graph; on a grid it is called an unoriented grid.
- 1oriented explore →
- The graph is a grid with nodes \((x,y)\), and every node labels its ports North, East, South and West consistently: the port North of \((x,y)\) leads to \((x,y+1)\), East to \((x+1,y)\), South to \((x,y-1)\) and West to \((x-1,y)\), whenever that neighbour exists. The same direction carries the same label at every node, so an agent can keep moving along a row or column; a boundary node is recognised by its missing ports.
Specific to Uniform deployment on graphs
Goal Uniform deployment on graphs
- 0all agents
- Every agent ends evenly spread and stops.
- 1all but one explore →
- All agents but one end evenly spread and stop; the remaining agent may stop on any node.
Specific to Treasure hunt
Graph size Treasure hunt
External help Treasure hunt
- 0no help
- No information beyond the agent's own observations.
- 1advice explore →
- An oracle that knows the whole instance gives the agent a binary string before it starts; its length (in bits) is the measure.
- 1oracle pebbles explore →
- An oracle that knows the instance places pebbles on nodes (at most one per node) before the agent starts; their number is the measure.
Specific to Rendezvous
Graph size Rendezvous
Start Rendezvous
- 0any delay
- An adversary wakes the agents at times \(t_1\) and \(t_2\); the delay \(\tau=|t_1-t_2|\) is unknown.
- 1simultaneous start explore →
- Both agents start in the same round (\(\tau=0\)).
Specific to Black hole search
Knowledge of the graph Black hole search
- 0topology unknown
- Agents know \(n\) but not the topology of \(G\).
- 1sense of direction explore →
- Agents have a consistent sense of direction: a globally consistent labelling of edges from which they can tell whether two walks lead to the same node.
- 2map explore →
- Agents have a map of \(G\) and know their starting position on it.
Marking nodes Black hole search
Black hole appearance Black hole search
- 0eventually emerging
- There is a time \(t \ge 0\) and a node \(u\) such that from time \(t\) on \(u\) destroys every agent on it or entering it, and stays a black hole. If \(t = 0\) then \(u \ne s\); the home base may become the black hole after the first round (after one epoch for asynchronous agents). Time is counted from \(t\) Bonnet et al. 2026b.
- 1present from the start explore →
- The black hole is present at time 0, and the home base \(s\) is safe throughout.
Specific to Map construction
Agents Map construction
- 0one agent
- A single agent.
- 1several agents explore →
- \(k\ge2\) identical agents.
Knowledge Map construction
- 0nothing known
- Nothing is known about \(G\).
- 1bound on \(n\) explore →
- An upper bound \(N\ge n\) is known.
Markers Map construction
- 0no markers
- No markers.
- 1markers explore →
- The agent carries markers it can drop and pick up.
Whiteboards Map construction
- 0no whiteboards
- No whiteboards.
- 1whiteboards explore →
- Each node has a whiteboard.
Specific to Leader election by agents
Knowledge Leader election by agents
- 0no knowledge
- Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
- 1knows \(n\), \(\Delta\) explore →
- Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).
Specific to Maximal independent set by agents
Knowledge Maximal independent set by agents
- 0no knowledge
- Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
- 1knows \(n\), \(\Delta\) explore →
- Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).
Specific to Minimal dominating set by agents
Knowledge Minimal dominating set by agents
- 0no knowledge
- Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
- 1knows \(n\), \(\Delta\) explore →
- Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).
Specific to Triangle and butterfly counting by agents
Knowledge Triangle and butterfly counting by agents
- 0no knowledge
- Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
- 1knows \(n\), \(\Delta\) explore →
- Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).
Specific to Minimum spanning tree by agents
Knowledge Minimum spanning tree by agents
- 0no knowledge
- Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
- 1knows \(n\), \(\Delta\) explore →
- Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).
Specific to BFS tree by agents
Knowledge BFS tree by agents
- 0no knowledge
- Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
- 1knows \(n\), \(\Delta\) explore →
- Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).
Specific to Network decontamination
Knowledge Network decontamination
- 0unknown graph
- Agents know nothing about \(G\).
- 1known graph explore →
- The topology is known to the agents (or to a coordinator).
Specific to Exploration by oblivious robots
Scheduler Exploration by oblivious robots
- 0ASYNC
- ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may Look while others are between phases, so it may move on an outdated snapshot. A robot is always seen on a node (moves are instantaneous). The scheduler is fair: every robot is activated infinitely often. Called CORDA (with instantaneous moves) in Lamani et al. 2010 and Blin et al. 2010.
- 1SSYNC explore →
- SSYNC: time is divided into rounds; in each round a fair adversary chooses a non-empty subset of robots, which execute one atomic Look–Compute–Move cycle together. Called ATOM in Lamani et al. 2010.
- 2FSYNC explore →
- FSYNC: in every round every robot executes one atomic Look–Compute–Move cycle.
Exploration goal Exploration by oblivious robots
- 0both goals
- Solve both terminating and exclusive perpetual exploration with the stated resources (possibly with two algorithms). A lower bound for either goal holds here, and a result here gives both. No variant is catalogued here; the value exists because the two goals do not imply each other.
- 1terminating explore →
- From every allowed initial configuration, every node is visited by at least one robot and the robots reach a configuration in which no robot ever moves again. With coin flips, this must happen with probability 1.
- 1exclusive perpetual explore →
- Every robot visits every node infinitely often, no two robots are ever on the same node, and no two robots ever cross the same edge in opposite directions.
Specific to Exploration by luminous robots
Scheduler Exploration by luminous robots
- 0ASYNC
- ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may Look while others are between phases, so it may move on an outdated snapshot. A robot is always seen on a node (an edge traversal is instantaneous), and its new colour is visible from the end of its Compute phase. The scheduler is fair: every robot is activated infinitely often. Called CORDA in Datta et al. 2013.
- 1SSYNC explore →
- SSYNC: time is divided into rounds; in each round a fair adversary chooses a non-empty subset of robots, which execute one atomic Look–Compute–Move cycle together. Called ATOM in Datta et al. 2013.
- 2FSYNC explore →
- FSYNC: in every round every robot executes one atomic Look–Compute–Move cycle.
Lights (memory and messages) Exploration by luminous robots
- 0oblivious
- OBLOT: a robot's Compute phase depends only on the current snapshot; nothing persists across cycles and robots communicate only by moving. Equivalent to a light with \(c = 1\) colour.
- 1FSTA explore →
- FSTA (finite-state): each robot has a light with \(c\) colours that only it can see. The colour is set at the end of Compute and persists until the robot changes it: \(\log_2 c\) bits of persistent memory, no communication Flocchini et al. 2016a.
- 1FCOM explore →
- FCOM (finite-communication): each robot has a light with \(c\) colours that the other robots within distance \(\varphi\) can see but the robot itself cannot; the robot stays oblivious, but every robot that looks reads its last colour: \(\log_2 c\) bits broadcast to the neighbourhood, no memory Flocchini et al. 2016a.
- 2luminous explore →
- LUMI (luminous robots): each robot has a light with \(c\) colours, set at the end of Compute, persistent across cycles, and visible to the robot itself and to every robot within distance \(\varphi\) Das et al. 2016. It is both memory and message. A Look returns, for every node within distance \(\varphi\), the multiset of colours of the robots on it.
Visibility range Exploration by luminous robots
- 0\(\varphi=1\)
- In a Look phase a robot at node \(v\) sees every node at distance at most \(\varphi = 1\) from \(v\) (in the graph metric), with the robots on it, their colours, and how many robots each node holds. It sees no node identifiers and, without chirality, no orientation.
- 1\(\varphi=2\) explore →
- As for \(\varphi = 1\), but the robot sees every node at distance at most \(\varphi = 2\). An algorithm for \(\varphi = 2\) works for every larger \(\varphi\), since a robot can ignore what lies further away.
- 2\(\varphi=3\) explore →
- As for \(\varphi = 1\), but the robot sees every node at distance at most \(\varphi = 3\).
Chirality Exploration by luminous robots
- 0no chirality
- Robots share no orientation: on a ring a robot cannot tell its two directions apart; on a grid or torus its snapshot is known only up to rotation and reflection, and the adversary may choose a different transformation in every cycle (self-inconsistent robots, as in Darwich et al. 2023 and Bramas et al. 2026a).
- 1chirality explore →
- All robots agree on the clockwise direction: a snapshot is known up to rotation only (no reflection), so a robot on an axis of symmetry of its view can still tell its two sides apart. Robots still share no North.
Exploration goal Exploration by luminous robots
- 0both goals
- Solve both terminating and perpetual exploration with the stated resources (possibly with two algorithms). A lower bound for either goal holds here, and a result here gives both. No variant is catalogued here; the value exists because the two goals do not imply each other.
- 1terminating explore →
- Every node is visited by at least one robot, and from some time on no robot is enabled (no robot changes its position or colour again).
- 1perpetual explore →
- Every node is visited by at least one robot infinitely often; robots never stop.
Network Exploration by luminous robots
- 0any graph
- A finite, connected, anonymous graph \(G=(V,E)\) with \(n\) nodes and no port numbers visible to the robots.
- 1ring explore →
- An anonymous, unoriented ring of \(n\) nodes; \(n\) is unknown to the robots.
- 1grid explore →
- An \(a \times b\) grid (\(n = ab\) nodes; nodes \((i,j)\), edges between nodes at Manhattan distance one); anonymous, with \(a\) and \(b\) unknown. A robot sees the border of the grid when it is within range, since nodes beyond the border are missing from its snapshot.
- 1torus explore →
- An \(a \times b\) torus: the grid with wrap-around edges in both dimensions, so every node has degree four and there is no border.
- 1triangular grid explore →
- The subgraph of the infinite triangular grid (every node of degree six, every face an equilateral triangle of unit side) induced by the nodes on or inside a rectangle, one pair of whose sides is parallel to a family of grid lines; the lines parallel to those sides are its columns. It is anonymous and its dimensions are unknown. Corner nodes have degree two or three and other border nodes degree three, four or five, so the border is seen from within range as on a square grid, but with more cases.
Specific to Exploration of recolourable graphs
Port numbers Exploration of recolourable graphs
- 0no ports
- Edges carry no port numbers. To move, the agent at \(v\) names a colour \(x\); the adversary moves it to any neighbour \(u\) of \(v\) with \(\psi(u) = x\) (if the agent sees no neighbour colours, to any neighbour). The agent never learns by which edge it arrived.
- 1ports, no entry port explore →
- The edges at \(v\) carry port numbers \(1,\dots,\deg(v)\), assigned by an adversary independently at each endpoint (\(\mathrm{port}_v\)). The agent chooses the port by which it leaves, but on arrival it is not told the port by which it entered (unknown inport).
- 2ports + entry port explore →
- As for port numbers, and on arrival at \(v\) the agent also reads the port \(\mathrm{port}_v(e)\) of the edge \(e\) by which it entered. This is the standard convention of single-agent exploration.
View Exploration of recolourable graphs
- 0own node
- At node \(v\) the agent observes \(\psi(v)\), \(\deg(v)\) and nothing about its neighbours (and, where ports exist, what the port axis grants).
- 1neighbour colours explore →
- At node \(v\) the agent observes \(\psi(v)\) and the multiset \(\{\!\{\psi(u) : u \in N(v)\}\!\}\) of its neighbours' colours (hence also \(\deg(v)\)), without knowing which edge leads to which colour unless ports say so.
Agent memory Exploration of recolourable graphs
- 0oblivious
- The agent has no internal state: its action (new colour of \(v\), then a move, stay or stop) is a function of its current observation only. Called zero-memory, memoryless or a 1-state robot.
- 1finite automaton explore →
- The agent is a deterministic automaton with \(K\) states, \(K\) independent of the graph; its action and next state depend on its state and its observation.
- 2\(O(\log n)\) bits explore →
- The agent has \(b = O(\log n)\) bits of memory, enough to hold a counter up to a polynomial in \(n\). No variant is catalogued here yet.
Recolouring Exploration of recolourable graphs
- 0fixed colours
- The colouring \(\psi : V \to \{1,\dots,c\}\) never changes; the agent reads \(\psi(v)\) (and, with neighbour view, its neighbours' colours) but cannot write.
- 1colour once explore →
- Every node starts with the initial colour \(c_0\). The agent at \(v\) may change \(\psi(v)\) only while \(\psi(v) = c_0\); once \(v\) has a colour other than \(c_0\) it keeps it forever. This is the main model of Böckenhauer et al. 2023.
- 2recolourable explore →
- At every step the agent at \(v\) may set \(\psi(v)\) to any colour of the palette, including back to \(c_0\), any number of times (the convention of Takahashi et al. 2025 and Hiraoka et al. 2026).
Initial colouring Exploration of recolourable graphs
- 0arbitrary colours
- The initial colouring \(\psi_0 : V \to \{1,\dots,c\}\) is chosen by the adversary; an algorithm must work from every \(\psi_0\) (as with a rotor-router whose pointers are set arbitrarily).
- 1uniform \(c_0\) explore →
- Initially \(\psi(v) = c_0\) for every node \(v\) (clean node memory). The colour \(c_0\) counts as one of the \(c\) colours.
- 2designer's colours explore →
- Before the agent starts, a designer who knows \(G\) (and the start node) chooses \(\psi_0\). Used with fixed colours this is label-guided exploration Cohen et al. 2008.
Knowledge Exploration of recolourable graphs
- 0nothing known
- The algorithm is the same for all graphs: it knows neither \(n\) nor \(\Delta\) nor any other parameter (a uniform algorithm in Böckenhauer et al. 2023).
- 1\(n\) known explore →
- The algorithm may depend on \(n\): it must explore every graph with exactly \(n\) nodes (a non-uniform algorithm).
Termination requirement Exploration of recolourable graphs
Network Exploration of recolourable graphs
Specific to Online exploration of weighted graphs
Knowledge of the graph Online exploration of weighted graphs
- 0nothing known
- The agent knows nothing about \(G\) before it starts; the edges at a node and their weights are revealed when the agent first visits the node.
- 1weight estimates explore →
- The agent is given \(G\) and, for every edge \(e\), an interval \([\mathrm{wt}^-(e), \mathrm{wt}^+(e)]\) that contains \(\mathrm{wt}(e)\), with \(\mathrm{wt}^+(e) \le \vartheta\,\mathrm{wt}^-(e)\) for a factor \(\vartheta \ge 1\) (their \(\alpha\)); the exact weight of \(e\) is revealed when the agent visits an end of \(e\) Gehnen et al. 2025.
Excluded minors Online exploration of weighted graphs
- 0any graph
- \(G\) is any connected graph.
- 1\(H\)-minor-free explore →
- For a fixed graph \(H\), no graph obtained from \(G\) by deleting nodes and edges and contracting edges is isomorphic to \(H\). Graphs of bounded genus and of bounded treewidth are such classes; bounds may depend on \(H\).
- 2planar explore →
- \(G\) can be drawn in the plane without crossing edges; equivalently it has neither \(K_5\) nor \(K_{3,3}\) as a minor.
Specific to Gathering by oblivious robots on graphs
Scheduler Gathering by oblivious robots on graphs
- 0ASYNC
- ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may Look while others are between phases, so it may move on an outdated snapshot. A robot is always seen on a node (moves are instantaneous). The scheduler is fair: every robot is activated infinitely often.
- 1SSYNC explore →
- SSYNC: time is divided into rounds; in each round a fair adversary chooses a non-empty subset of robots, which execute one atomic Look–Compute–Move cycle together.
- 2sequential explore →
- Sequential: an SSYNC scheduler that activates exactly one robot per round, fairly; which robot is the adversary's choice unless the activation order is fixed (see the order axis).
- 2FSYNC explore →
- FSYNC: in every round every robot executes one atomic Look–Compute–Move cycle.
Activation order Gathering by oblivious robots on graphs
- 0any order
- The adversary chooses which robots to activate, subject only to the scheduler's fairness.
- 1round robin explore →
- With the sequential scheduler: the robots are activated one per round in a cyclic order that the adversary fixes at the start, that the robots do not know, and that repeats forever; an epoch is \(k\) consecutive rounds, one activation per robot.
Multiplicity detection Gathering by oblivious robots on graphs
Network Gathering by oblivious robots on graphs
- 0any graph
- Any connected anonymous graph, finite unless stated; robots see it whole but share no orientation.
- 1ring explore →
- An anonymous, unoriented ring of \(n\) nodes.
- 1complete graph explore →
- \(K_n\): every two nodes are neighbours.
- 1hypercube explore →
- The hypercube of dimension \(\log n\): nodes are the \(n\) binary strings of length \(\log n\), neighbours when they differ in one bit. Its diameter is \(D = \log n\).
- 1infinite grid explore →
- The infinite square grid: nodes are the points of \(\mathbb Z^2\), neighbours at Manhattan distance one; finitely many robots.
- 1finite grid explore →
- An anonymous \(a \times b\) grid without orientation: nodes are the points \((i, j)\) with \(1 \le i \le a\) and \(1 \le j \le b\), neighbours at distance one.
- 1tree explore →
- An anonymous tree of \(n\) nodes without orientation.
- 1not vertex-transitive explore →
- A finite connected graph whose nodes fall into at least two orbits, an orbit being a class of nodes that automorphisms of \(G\) map onto each other.
Specific to Collision-free exploration
Number of agents Collision-free exploration
- 0any \(k\)
- Any number \(k\) of agents, \(2 \le k \le n\), which they do not know.
- 1two agents explore →
- Exactly two agents.
What must be visited Collision-free exploration
- 0every agent
- Every agent must visit every node and stop (in Czyzowicz et al. 2017a also return to its start node).
- 1the team explore →
- Every node must be visited by at least one agent, and all agents stop.
Knowledge of the graph Collision-free exploration
- 0nothing known
- The agents know nothing about \(G\), not even \(n\).
- 1bound on \(n\) explore →
- The agents know an upper bound on \(n\) (Das et al. 2025a give them \(n\) itself).
- 2map explore →
- Every agent knows \(G\) and its own start node in it, but not the number or the start nodes of the other agents.
Vision of the other agents Collision-free exploration
- 0no vision
- An agent never perceives another agent.
- 1presence explore →
- An agent notices that the other agent is on a neighbouring node, but not on which one Das et al. 2025a.
- 2radius 1 explore →
- An agent sees the subgraph induced by the nodes at distance at most 1, with its port numbers and the agents on these nodes.
- 3radius 2 explore →
- An agent sees the subgraph induced by the nodes at distance at most 2, with its port numbers and the agents on these nodes Bhagat & Pelc 2025.
Help from an oracle Collision-free exploration
- 0no help
- Nothing is placed on the nodes.
- 1pebbles explore →
- Before the start an oracle that knows \(G\), the start nodes and the wake-up rounds places at most one pebble on each node; pebbles have colours, and an agent sees the pebble of the node it is at Das et al. 2025a.
Start Collision-free exploration
- 0adversarial wake-up
- Each agent starts in a round chosen by the adversary; until then it stays at its start node, where no other agent may enter.
- 1simultaneous start explore →
- All agents start in the same round.
Specific to Deciding graph properties by mobile agents
Number of agents Deciding graph properties by mobile agents
Certificates Deciding graph properties by mobile agents
- 0decide
- The agents receive only their identifiers and inputs.
- 1verify explore →
- Each agent also receives a certificate string. For every configuration in \(\Pi\) some certificate makes all agents output yes; for every other configuration, whatever the certificate, some agent outputs no.
Knowledge of the graph Deciding graph properties by mobile agents
- 0no knowledge
- The agents know nothing about \(G\).
- 1knows \(n\) explore →
- The agents know \(n\) (an oracle for the number of nodes in Fraigniaud & Pelc 2017).
- 2map explore →
- The agents have a copy of \(G\) with its ports, without their start nodes marked on it.
Specific to Delivery by energy-constrained agents
Graph class Delivery by energy-constrained agents
Budgets Delivery by energy-constrained agents
- 0any budgets
- Each agent \(i\) has its own budget \(B_i\).
- 1equal budgets explore →
- All agents have the same budget \(B\).
Mobile robots in the plane
Body Mobile robots in the plane
- 0fat
- Each robot is a closed disc of radius 1 (unit disc). Discs may not overlap, so robots cannot share a point and must avoid collisions; a disc hides what lies behind it from other robots. Gathering then asks for a configuration whose union of discs is connected and in which every robot sees all others Czyzowicz et al. 2009b.
- 1point explore →
- Each robot is a point of the plane: several robots may share a point (multiplicity), and a robot hides only what lies exactly behind it on a line of sight.
Scheduler Mobile robots in the plane
- 0ASYNC
- ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may look while others move, and compute on an outdated snapshot. Time is counted in epochs: an epoch is an interval of time in which every robot completes at least one full Look–Compute–Move cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. In FSYNC and SSYNC time is counted in rounds. Called Corda by Prencipe Prencipe 2007. Intermediate variants restrict interleavings: LC-atomic (no Look by another robot between a robot's Look and its Compute), Move-atomic (no Look during another robot's Move) and CM-atomic Flocchini et al. 2023.
- 1SSYNC explore →
- SSYNC: time is divided into rounds; in each round a non-empty subset of robots, chosen by a fair adversary, executes one atomic Look–Compute–Move cycle. Called Atom by Prencipe Prencipe 2007.
- 2sequential explore →
- Sequential: an SSYNC scheduler that activates exactly one robot per round (fairly). Also called a centralized scheduler Terai et al. 2023; a round-robin scheduler is a fair special case.
- 2FSYNC explore →
- FSYNC: every robot executes one atomic cycle in every round.
Lights (persistent memory) Mobile robots in the plane
- 0oblivious
- OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
- 1internal light (FSTA) explore →
- FSTA: each robot has a light with \(c\) colours that only it can see; it persists between cycles (constant persistent memory, no communication). Also called an internal light.
- 1external light (FCOM) explore →
- FCOM: each robot has a light with \(c\) colours that only the others can see (constant communication, no persistent memory of its own). Also called an external light.
- 2lights (LUMI) explore →
- LUMI: each robot has a light with \(c\) colours, set at the end of Compute, visible to all robots including itself; it is both memory and communication. Also called luminous robots, or a full light.
Agreement on coordinates Mobile robots in the plane
- 0disoriented
- Each robot \(r\) observes in its own coordinate system, obtained from the global one by an unknown similarity (translation, rotation, uniform scaling, and possibly reflection); systems may differ between robots and, in some models, between cycles. Papers that call robots disoriented do not always mean this: Défago and Souissi use the word while assuming chirality Défago & Souissi 2008. Some papers also let the adversary change a robot's rotation, reflection and unit at every Look (variable disorientation) Flocchini et al. 2023 Wada et al. 2026.
- 1chirality explore →
- All local coordinate systems have the same handedness (clockwise orientation): no reflection. Also called handedness. Prencipe uses chirality for agreement on North and East, i.e. a compass Prencipe 2007.
- 1one axis explore →
- All robots agree on the direction and orientation of one axis (e.g. North), but not necessarily on handedness: two robots may disagree on which side is East. This is how the papers use one axis agreement (e.g. robots "agree on only 'left' and 'right'" Bose et al. 2021a; robots "do not necessarily have the same handedness" Pagli et al. 2015). One axis and chirality are alternatives on this axis; together they amount to a common compass.
- 2compass explore →
- All robots agree on the directions and orientations of both axes (a common compass); they may still disagree on origin and unit. Called full compass by Efrima and Peleg, who also use half compass (both axis directions, the positive sense of one axis, no chirality), direction-only and axes-only Efrima & Peleg 2009. Agreement on one axis together with common chirality is equivalent: the orientation of the second axis then follows from handedness.
Movement Mobile robots in the plane
- 0non-rigid
- In a Move phase the adversary may stop a robot before its destination, but only after it has travelled at least \(\delta>0\) (a constant unknown to the robots) or reached the destination.
- 1rigid explore →
- Every Move phase ends at the computed destination.
Multiplicity detection Mobile robots in the plane
- 0no multiplicity detection
- A snapshot is a set of points: a point occupied by several robots looks like a single robot.
- 1weak multiplicity explore →
- A snapshot marks each occupied point as holding one robot or more than one.
- 2strong multiplicity explore →
- A snapshot is a multiset: each occupied point comes with the exact number of robots on it.
Visibility Mobile robots in the plane
- 0limited visibility
- A robot sees exactly the robots within Euclidean distance \(V\) of its position, for a fixed radius \(V>0\).
- 1unlimited visibility explore →
- A robot sees all robots (subject to opacity).
Opacity Mobile robots in the plane
- 0opaque
- Robots are points that obstruct sight: \(r\) sees \(s\) iff no third robot lies on the open segment \(\overline{rs}\).
- 1transparent explore →
- Robots do not obstruct each other's view.
Faults Mobile robots in the plane
Randomness Mobile robots in the plane
- 0deterministic
- The destination computed in a cycle is a function of the snapshot (and the light, if any).
- 1randomized explore →
- Robots may use random bits in Compute; guarantees hold with probability 1 or in expectation, as stated per result.
Identifiers Mobile robots in the plane
- 0anonymous
- Robots are indistinguishable and run the same algorithm.
- 1homonymous explore →
- Robots carry labels from a set of size \(\ell\), \(1\le\ell\le n\), which may repeat; equivalently, robots may run one of \(\ell\) algorithms. The minimum \(\ell\) that solves a problem is its minimum algorithm size Asahiro & Yamashita 2025.
- 2distinct IDs (eponymous) explore →
- Distinct identifiers (eponymous robots): labels are pairwise distinct (\(\ell=n\)); whether others can see a robot's label is stated per result.
Specific to Gathering
Number of robots Gathering
Initial configurations Gathering
- 0any start
- The algorithm must gather from every initial configuration from which gathering is possible at all in the setting; configurations proved unsolvable there (for example bivalent ones, or several multiplicities with weak detection and crashes) are excluded by the problem, not by the algorithm.
- 1restricted start explore →
- The algorithm gathers only from a stated family of initial configurations that leaves out some solvable ones, typically symmetric configurations; the family is named on each result.
Search in geometric domains
Communication Search in geometric domains
- 0face-to-face
- Face-to-face: two robots exchange information only when they are at the same point at the same time.
- 1sender/receiver explore →
- Sender/receiver: one robot can only transmit and the other only receive, instantly at any distance.
- 2wireless explore →
- Wireless: every robot can send messages to every other robot instantly at any distance.
Faults Search in geometric domains
Speeds Search in geometric domains
- 0distinct speeds
- Each robot \(i\) has its own maximum speed \(v_i\), known to all.
- 1equal speeds explore →
- All robots move at most at unit speed.
Randomness Search in geometric domains
- 0deterministic
- Trajectories are fixed functions of the information received.
- 1randomized explore →
- Trajectories may depend on random choices; the measure is the expected competitive ratio against an oblivious adversary.
Specific to Linear search (cow path)
Domain Linear search (cow path)
- 0\(m\) rays
- \(m\ge2\) half-lines sharing their endpoint, the origin, where the robots start.
- 1line explore →
- The real line, robots start at \(0\); the target is at an unknown \(x\) with \(|x|\ge1\).
Number of robots Linear search (cow path)
Goal Linear search (cow path)
- 0evacuation
- The task ends when every robot has reached the target.
- 1search explore →
- The task ends when the first robot reaches the target (and, with faults, the others can be sure of it).
Specific to Evacuation
Domain Evacuation
- 0any domain
- A bounded convex domain; the robots start together at a given point of it, in its interior or on its boundary.
- 1disk explore →
- The unit disk; robots start at its centre; the exit is a point of the boundary circle.
- 1triangle explore →
- The equilateral triangle of unit side; robots start at its centroid; the exit is a point of the boundary.
- 1square explore →
- The unit square; robots start at its centroid; the exit is a point of the boundary.
- 1triangle, boundary start explore →
- A triangle (the equilateral triangle of unit side unless the setting names another family); the robots start together at a point of its boundary, either given (at distance \(y\) from the nearest midpoint of a side) or chosen by the algorithm, as the setting says; the exit is a point of the boundary.
- 1square, boundary start explore →
- The unit square; the robots start together at a given point of its boundary, at distance \(x \le 1/2\) from the nearest corner; the exit is a point of the boundary.
- 1line explore →
- The robots start at the origin of the real line; the exit is at an unknown point at distance at least \(1\); the measure is the competitive ratio, the evacuation time divided by that distance.
- 1rays explore →
- \(m \ge 2\) half-lines share an endpoint, the junction; the exit lies on one ray at distance at least \(1\) from the start; the measure is the competitive ratio.
Number of robots Evacuation
Goal Evacuation
- 0all robots
- The task ends when the last robot reaches the exit.
- 1priority (queen) explore →
- One designated robot (the queen) must reach the exit; the others (servants) only help; the task ends when the queen exits.
- 1search-and-fetch explore →
- A treasure lies at an unknown point of the boundary, and the exit at a known arc distance \(\alpha\) from it; the task ends when some robot has carried the treasure to the exit.
- 1weighted explore →
- Two robots, a light one and a heavy one of known weight \(w \ge 1\), both must reach the exit and stay there; with arrival times \(t_1\) (light) and \(t_2\) (heavy), the cost is \((t_1 + w\,t_2)/(1+w)\).
- 1search explore →
- The task ends as soon as a non-faulty robot has reached the exit and every non-faulty robot knows its position for certain; the robots need not go to the exit.
Exits Evacuation
- 0one exit
- One exit, at an unknown point of the boundary.
- 1two exits explore →
- Two exits at unknown points of the boundary; the task ends when every robot has reached one of them.
Specific to Patrolling
Fence Patrolling
Direction of movement Patrolling
- 0one-way
- On a closed fence every robot moves only counterclockwise, at any speed between \(0\) and its maximum speed \(v_i\); it never reverses. Czyzowicz et al. require strictly positive speeds, while Dumitrescu, Ghosh and Tóth and Kawamura and Soejima allow robots to stop; the counterexample of Dumitrescu et al. holds under both conventions (Remark after Theorem 1 of Dumitrescu et al. 2014). Schedules are a subset of the two-way schedules, so this is the harder level for the robots.
- 1two-way explore →
- Every robot moves along the fence in either direction at any speed between \(0\) and \(v_i\), and may reverse at any point and any time. On a segment and on a graph this is the only meaningful choice.
Specific to Chauffeuring a crashed robot
Exits Chauffeuring a crashed robot
Specific to Search with segment visibility
Number of robots Search with segment visibility
- 0any \(k\)
- \(k \ge 2\) robots; bounds are stated as functions of \(k\).
- 1two robots explore →
- Two robots; the visible set at each time is the one segment between them.
Knowledge of the distance Search with segment visibility
- 0\(d\) unknown
- The trajectories do not depend on \(d\); the ratio is the supremum over all targets \(x \ne O\) of \(T(x)/\|x\|\).
- 1\(d\) known explore →
- The robots know \(d\) (not the direction of the target); the trajectories may depend on \(d\), and the ratio is the supremum over targets with \(\|x\| = d\) of \(T(x)/d\).
Specific to Search for a moving target
Domain Search for a moving target
- 0\(m\) rays
- \(m \ge 2\) half-lines sharing their endpoint, the origin; the target moves along one of them.
- 1line explore →
- The real line; the target moves along one side of the origin.
Number of robots Search for a moving target
Direction of the target Search for a moving target
- 0direction unknown
- The target moves toward or away from the origin, and the robots do not know which.
- 1away explore →
- The target moves away from the origin at constant speed \(u < 1\), and the robots know it.
- 1toward explore →
- The target moves toward the origin at constant speed \(u \ge 0\), and the robots know it.
Knowledge of the target Search for a moving target
- 0nothing known
- The robots know neither the initial distance \(d\) nor the speed \(u\).
- 1speed known explore →
- The robots know \(u\) but not \(d\).
- 1distance known explore →
- The robots know \(d\) but not \(u\).
- 2both known explore →
- The robots know \(d\) and \(u\); only the side (ray) of the target is unknown.
Programmable matter
Orientation Programmable matter
- 0no orientation
- Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
- 1chirality explore →
- All particles agree on clockwise order, not on a common direction.
- 1common direction explore →
- All particles agree on one lattice direction, not on handedness. Chalopin, Das and Kokkou call this a common direction Chalopin et al. 2026b, but the same words mean agreement on all six directions in other papers Chalopin et al. 2026a Navarra & Piselli 2023b.
- 2common compass explore →
- All particles agree on all six directions.
Scheduler Programmable matter
- 0weak scheduler
- An activation's look, compute and move need not be atomic; concurrent activations may interfere. The scheduler of Bazzi and Briones is described as weak sequential, as non-atomic, and as fair asynchronous by different later papers Briones et al. 2023 Dufoulon et al. 2021 Chalopin et al. 2026b.
- 1strong scheduler explore →
- Each activation is executed atomically; the adversary chooses the order, fairly.
- 2sequential explore →
- At most one particle is active at any time.
- 2synchronous explore →
- Time proceeds in rounds; in every round every particle executes one look–compute–act cycle, and what a particle sends in a round is received in the next Feldmann et al. 2022. It is an alternative to the sequential scheduler: one activates every particle at once, the other one at a time.
Communication Programmable matter
- 0local communication
- A particle exchanges constant-size information only with the particles on adjacent nodes, by messages or by reading and writing their memory, so information travels at most one particle per activation.
- 1circuits explore →
- Each particle has a constant number of pins on every incident edge, shared with the neighbour across that edge, and in every round it links its pins into groups. A circuit is a connected component of the resulting graph on pins. A particle may send a beep on any of its circuits; every particle on the circuit receives it in the next round, without learning who sent it or how many did Feldmann et al. 2022. Local communication remains available.
Memory Programmable matter
- 0oblivious
- No persistent state and no messages; a particle decides from its view only.
- 1constant memory explore →
- Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.
Randomness Programmable matter
- 0deterministic
- No random choices.
- 1randomized explore →
- Particles flip fair coins; guarantees hold with high probability or in expectation.
Initial shape Programmable matter
- 0holes allowed
- The initial set of occupied nodes induces a connected subgraph; it may enclose empty regions.
- 1no holes explore →
- The initial configuration is connected and encloses no empty node. Also called contractible Briones et al. 2023 or hole-free Gastineau et al. 2018.
Connectivity during execution Programmable matter
- 0stays connected
- At every time the occupied nodes induce a connected subgraph.
- 1may disconnect explore →
- Connectivity is required only initially and at the end.
Specific to Leader election in programmable matter
Movement Leader election in programmable matter
- 0stationary
- No particle ever expands or contracts; the configuration is fixed and only states change.
- 1may move explore →
- Particles may expand and contract during the election.
Specific to Scattering of particles
Activation Scattering of particles
- 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 explore →
- 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.
Specific to Shape formation by hybrid programmable matter
Space Shape formation by hybrid programmable matter
- 03D
- Tiles occupy nodes of the face-centred cubic lattice; planar structures are a special case.
- 12D explore →
- Tiles occupy nodes of the triangular lattice.
Specific to Centralised transformations of modular robots
Mechanism Centralised transformations of modular robots
- 0rotation
- A module may rotate \(90°\) around an adjacent module, if the cells it sweeps are empty.
- 1rotation + sliding explore →
- In addition, a module may slide one cell along a line of modules.