Why compute by moving

The four models of the atlas (agents on graphs, robots in the plane, search in geometric domains, programmable matter) were built by different groups for different reasons, and their papers still open with different stories. What they have in common is the decision to abstract from the hardware. Pelc puts it this way for rendezvous: "Since rendezvous algorithms do not depend on the physical nature of the mobile entities executing them, but only on their perception capabilities, memory size, mobility characteristics and on the structure of the environment, we will not distinguish between natural and artificial agents" Pelc 2019. Each model then fixes those four ingredients differently, and the choice is what makes a problem easy or hard in it.

This essay follows the introductions of the founding papers and surveys: what each community wanted when it started, and what it chose to measure. The other perspectives take single threads (meeting, faults, lower bounds) across the same four models.

In the graph model the entity is usually a program. Pelc's survey names "software agents, i.e., mobile pieces of software that navigate in a computer network in order to perform maintenance of its components or to collect data distributed in nodes of the network" Pelc 2019, and later papers keep the same picture of "a software entity endowed with limited memory, capable of traversing a network and visiting nodes" Kaur et al. 2026. The oldest problem of the model is older than computer networks: Shannon built a mouse that explores a \(5\times5\) maze using constant memory per vertex Shannon 1951, as recalled by Disser et al. 2019. Exploration also mattered to complexity theory. Fraigniaud et al. list "robot navigation, network maintenance, resource discovery, and WWW search" as applications and add that a finite set of finite automata exploring all graphs "would have put USTCON in L" Fraigniaud et al. 2006; Disser, Hackfeld and Klimm call exploration "a natural abstraction of a process of computing where nodes correspond to states" Disser et al. 2019.

Later problems kept the network story but added a reason to move. Black hole search starts from security: a host that "disposes of visiting agents upon their arrival, leaving no observable trace", which can be a virus or simply "the undetectable crash failure of a site" Di Luna et al. 2025. Dispersion was introduced with self-driving electric cars looking for free charging stations, and from the start was placed next to scattering, exploration and load balancing Augustine & Moses Jr. 2018. What the model counts follows from the picture of a small program on a large network: rounds or moves, the number of agents, and above all the bits of memory an agent carries.

The plane model starts from the opposite end: the robots are physical, but the question is how weak they can be. "The study of swarms of mobile robots from an algorithmic perspective was initiated by Suzuki and Yamashita, and the simplicity of their model fostered many research results" Bramas et al. 2023, referring to Suzuki & Yamashita 1999. The applied motivation is deployment where no infrastructure exists: "space, deep sea, or after some natural (or unnatural) disaster", so that the group "must self-organize in the absence of any prior infrastructure (e.g., no global positioning)" Clement et al. 2010. The research motivation is stated plainly: "The primary motivation in this field is to find the minimum capability required to achieve certain objectives for a system of robots" Pattanayak et al. 2019.

Hence the questions are of the form "under which conditions this task can be accomplished by the robots?" Prencipe 2007. Robots are anonymous, silent and oblivious; what varies is synchrony, agreement on coordinates, multiplicity detection, visibility and, since lights were added, a constant number of persistent colours Das et al. 2016. Flocchini, Santoro and Wada describe the programme as determining "the impact that internal capabilities (e.g., memory, communication) and external conditions (e.g. synchrony, activation scheduler) have on the solvability of a problem" Flocchini et al. 2019. The primary measure is therefore feasibility; colours come second, and time (in rounds or epochs) is often not analysed at all.

The search model comes from operations research rather than computing. Bellman posed the linear search problem in 1963 and Beck studied it in 1964; Kupavskii and Welzl quote Beck's formulation, "A man in an automobile searches for another man who is located at some point of a certain road" Kupavskii & Welzl 2018 Beck 1964. Computer scientists rediscovered it in the late 1980s as the cow-path problem, with the worst-case (competitive) ratio as the measure, and the doubling strategy with ratio 9 is optimal Kupavskii & Welzl 2018 Baeza-Yates et al. 1993. Brandt et al. state the method directly: "The standard toolkit to analyze this class of problems is competitive analysis" Brandt et al. 2020.

The distributed version adds several robots and a communication model. Czyzowicz et al. describe what is abstracted away: in geometric environments "their performance is measured by the geometric distance travelled, most often disregarding their computing, communicating and environment-perceiving activities" Czyzowicz et al. 2014. Evacuation, which they posed, asks for "a compromise between, on the one hand, spreading sufficiently the robots so that they can find the exit point fast in parallel, and, on the other hand, not to spread them too far" Czyzowicz et al. 2014. The robots know the domain and each other's trajectories; what they lack is the location of the target. The answers are exact constants, and the open problems are gaps between two constants.

Programmable matter begins with a vision rather than an application: "a material that can dynamically alter its physical properties in a programmable fashion, controlled either by user input or its own autonomous sensing of its environment" Daymude et al. 2023. The term is attributed to Toffoli and Margolus by Di Luna et al. 2020 and Dufoulon et al. 2021; Di Luna et al. list smart materials, monitoring and repair, and minimally invasive surgery as envisioned uses Di Luna et al. 2020. The amoebot model, introduced at SPAA 2014 Derakhshandeh et al. 2014, is "motivated by micro- and nano-scale robotic systems with strictly limited computational and locomotive capabilities" Daymude et al. 2023. Dufoulon, Kutten and Moses note that smart particles "need to be small. Thus, they are also weak in their memory size, computational power, communication ability, movement ability" Dufoulon et al. 2021.

The first problems were shape formation and leader election, and their link was there from the beginning: "most shape formation algorithms depend on some seed element", and the founding paper asks "whether shape formation can even be solved in circumstances where leader election is not possible" Derakhshandeh et al. 2015. Later models removed more: SILBOT has no communication and no memory, to find "the minimal settings for PM under which it is possible to accomplish basic global tasks" Navarra & Piselli 2023. The measures are rounds (under an adversarial scheduler) and the total number of moves; a centralised line of work asks what transformations are possible at all under given movement mechanisms Michail et al. 2019.

Three ingredients recur. The first is an adversary: in a deterministic setting "the initial positions of the agents are chosen by an adversary which models the worst-case situation" Pelc 2019, and the adversary also picks the port numbers, the activation schedule, the moving edges of a dynamic graph, or the exit of a disk. The second is locality: an agent sees only its node and its ports, an oblivious robot sees a snapshot but no history, a particle sees its neighbours, and a searcher recognises the target only when it stands on it. The third is symmetry: identical entities in symmetric positions cannot be separated by any deterministic rule. Ta-Shma and Zwick give the standard example, two identical robots in a ring whose ports are all oriented the same way: "they would never meet!" Ta-Shma & Zwick 2014.

What each model counts follows from its origin. Agents on graphs count rounds, moves, team size and memory bits, because the entity is a program in a network. Robots in the plane first ask whether a task is solvable at all, then how many colours it needs. Search counts distance travelled, as a competitive ratio with exact constants. Programmable matter counts rounds and moves of a very large number of constant-memory particles. Bampas et al. make the contrast explicit within one model: in search, cost is "the time when the first searcher arrives at the target", while in rendezvous it is "the time when the last involved robot reaches the meeting point" Bampas et al. 2019. The same task, read with a different measure, becomes a different problem, and that is why the atlas keeps the four models apart while linking their problems.