Mobility Matters
What is known, what is tight, and what is open, under which assumptions.
AI use Claude (Anthropic) was used in cataloguing the problems.
How the problems evolved
Each year lists the problems first posed then (highlighted) and the papers that introduced a setting, gave the current best result, or proved a lower bound, dated by their first appearance in any form (conference, journal or arXiv preprint). The logical view arranges the same problems by reduction; the two orders can disagree, and where a derived problem was posed before its logical parent the entry says so.
1950s
1951
Mobile agents on graphs · Exploration
Graph exploration by a single agent is posed in Shannon 1951
Shannon's maze-solving mouse Theseus (first prototype 1950) explored a \(5\times5\) grid with constant memory per cell Disser et al. 2019; the first impossibility theorem for finite automata is Budach's Budach 1978.
1960s
1964
Search in geometric domains · Search, evacuation and patrolling
Linear search (cow path) is posed in Beck 1964
Bellman posed the problem in 1963 and Beck analysed it in 1964; computer scientists rediscovered it in the late 1980s as the cow-path problem Kupavskii & Welzl 2021.
1970s
1979
1990s
1990
1991
Mobile agents on graphs · Exploration
Map construction is posed in Dudek et al. 1991
Dudek, Jenkin, Milios and Wilkes framed robotic exploration as graph construction.
In the logical view: strengthening of Graph exploration by a single agent, which was posed earlier (1951).
- Dudek et al. 1991 — Map construction: One agent with a marker current best
1993
Mobile agents on graphs · Exploration
Online exploration of weighted graphs is posed in Kalyanasundaram & Pruhs 1993
Posed by Kalyanasundaram and Pruhs at ICALP 1993 (journal version 1994), who asked whether a constant competitive ratio is possible and gave one for planar graphs, as reported by Baligács 2026 and Baligács et al. 2026a; the paper itself was not read.
In the logical view: variant of Graph exploration by a single agent, which was posed earlier (1951).
- Baeza-Yates et al. 1993 — Linear search (cow path): One robot on a line current best, One robot on a line lower bound, One robot on \(m\) rays current best, One robot on \(m\) rays lower bound
- Kao et al. 1993 — Linear search (cow path): One randomized robot on a line current best, One randomized robot on a line lower bound, One randomized robot on \(m\) rays current best
- Kalyanasundaram & Pruhs 1993 — Online exploration of weighted graphs: Planar graphs current best
1995
- Baeza-Yates & Schott 1995 — Evacuation: Line, any number of face-to-face robots introduced, Line, any number of wireless robots introduced
1998
1999
Mobile robots in the plane · Formation problems
Pattern formation is posed in Suzuki & Yamashita 1999
Suzuki and Yamashita characterised the patterns that anonymous robots can form in terms of their initial configuration.
Mobile robots in the plane · Formation problems
Gathering is posed in Suzuki & Yamashita 1999
Suzuki and Yamashita gave an algorithm "moving the robots to a single point in finite steps" and showed that two oblivious robots cannot meet in SSYNC.
In the logical view: special case of k-grouping, but was posed before it (2007).
Mobile robots in the plane · Formation problems
Convergence is posed in Suzuki & Yamashita 1999
Suzuki and Yamashita gave algorithms for converging to a point and for reaching a point; Ando et al. treated limited visibility the same year Ando et al. 1999.
2000s
2001
Mobile agents on graphs · Exploration
Black hole search is posed in Dobrev et al. 2001
Dobrev, Flocchini, Prencipe and Santoro introduced black hole search in rings (DISC 2001) and in arbitrary networks (PODC 2002) Dobrev et al. 2006.
In the logical view: variant of Collaborative exploration, but was posed before it (2004).
- Flocchini et al. 2001 — Gathering: Limited visibility with a compass, ASYNC current best, Limited visibility with a compass, ASYNC lower bound
- Dobrev et al. 2001 — Black hole search: Asynchronous agents with whiteboards in a ring current best, Asynchronous agents with whiteboards in a ring lower bound
2002
Mobile robots in the plane · Formation problems
Circle formation is posed in Défago & Konagaya 2002
In the logical view: special case of Pattern formation, which was posed earlier (1999).
Mobile agents on graphs · Exploration
Network decontamination is posed in Barrière et al. 2002
Capture of an intruder by mobile agents (SPAA 2002).
- Diks et al. 2002 — Graph exploration by a single agent: Trees, perpetual exploration current best, Trees, perpetual exploration lower bound, Trees, exploration with stop lower bound, Trees, exploration with return introduced, Trees, exploration with return lower bound
- Défago & Konagaya 2002 — Circle formation: Circle formation, SSYNC introduced
- Dobrev et al. 2002 — Black hole search: Asynchronous agents with whiteboards current best, Asynchronous agents with whiteboards lower bound, Whiteboards and sense of direction current best, Whiteboards and sense of direction lower bound, Whiteboards and a map current best, Whiteboards and a map lower bound, Tokens and a map lower bound
- Barrière et al. 2002 — Network decontamination: Trees current best
2003
Mobile agents on graphs · Exploration
Rendezvous is posed in Dessmark et al. 2003
Deterministic rendezvous of labelled agents in arbitrary graphs was posed by Dessmark, Fraigniaud and Pelc at ESA 2003. Rendezvous itself is older (randomized search games); the catalogue covers the deterministic line Pelc 2019.
In the logical view: subproblem of Graph exploration by a single agent, which was posed earlier (1951).
Search in geometric domains · Search, evacuation and patrolling
Search for a moving target is posed in Alpern & Gal 2003
An early treatment, as reported by Coleman et al. 2022: Alpern and Gal give an optimal algorithm for one robot and a target moving away from the origin at a known speed. Coleman et al. write that the case of a moving target "appears to have been first considered by McCabe" (1974), for a target performing a random walk on the integers; that paper is not in the bibliography.
In the logical view: generalisation of Linear search (cow path), which was posed earlier (1964).
- Dessmark et al. 2003 — Rendezvous: Labelled agents, arbitrary finite graphs introduced, Labelled agents, arbitrary finite graphs lower bound, Labelled agents in trees current best, Labelled agents in trees lower bound, Labelled agents in rings, simultaneous start current best, Labelled agents in rings, simultaneous start lower bound
- Cieliebak et al. 2003 — Gathering: ASYNC with weak multiplicity detection current best
- Yanovski et al. 2003 — Exploration of recolourable graphs: Rotor-router: a pointer in every node current best
- Alpern & Gal 2003 — Search for a moving target: One robot, line, target moving away, speed known current best, One robot, line, target moving away, speed known lower bound, One robot, line, target moving away, nothing known lower bound
2004
Mobile agents on graphs · Exploration
Collaborative exploration is posed in Fraigniaud et al. 2004b
Collective tree exploration was posed at LATIN 2004 (journal version 2006).
Mobile robots in the plane · Symmetry breaking and spreading
Flocking is posed in Gervasi & Prencipe 2004
Coordination without communication: the flocking problem.
- Fraigniaud et al. 2004a — Graph exploration by a single agent: Arbitrary graphs, perpetual exploration current best, Arbitrary graphs, perpetual exploration lower bound
- Fraigniaud & Ilcinkas 2004 — Graph exploration by a single agent: Directed graphs, one pebble current best, Directed graphs, one pebble lower bound
- Fraigniaud et al. 2004b — Collaborative exploration: Trees, complete communication introduced, Trees, communication by whiteboards only current best, Trees, no communication current best, Trees, no communication lower bound
- Cohen & Peleg 2004 — Convergence: ASYNC, unlimited visibility current best
- Gervasi & Prencipe 2004 — Flocking: Oblivious robots following a leader current best
2005
- Reingold 2005 — Graph exploration by a single agent: Exploration with stop when \(n\) is known current best
- Fraigniaud et al. 2005a — Graph exploration by a single agent: Exploration with stop and one pebble current best
- Fraigniaud et al. 2005b — Graph exploration by a single agent: Exploration with stop and one pebble lower bound
- Cohen et al. 2005 — Graph exploration by a single agent: Node labels chosen by the designer current best; Exploration of recolourable graphs: Label-guided: colours fixed by a designer current best, Label-guided: colours fixed by a designer lower bound, Label-guided, oblivious agent lower bound
- Fleischer & Trippen 2005 — Graph exploration by a single agent: Directed graphs with labelled nodes current best
- De Marco et al. 2005 — Rendezvous: Asynchronous labelled agents introduced
- Prencipe 2005 — Gathering: No multiplicity detection, SSYNC lower bound, Gathering, full lights, SSYNC, no multiplicity detection lower bound, Gathering, full lights, ASYNC, no multiplicity detection lower bound
- Klasing et al. 2005 — Black hole search: Synchronous agents with a map current best, Synchronous agents with a map lower bound
- Flocchini et al. 2005 — Network decontamination: Hypercubes current best, Hypercubes lower bound
2006
Mobile robots in the plane · Formation problems
Uniform circle formation is posed in Dieudonné et al. 2006
The first deterministic solution (SSS 2006); circle formation with convergence towards uniformity predates it Défago & Konagaya 2002.
In the logical view: special case of Pattern formation, which was posed earlier (1999).
Mobile robots in the plane · Symmetry breaking and spreading
Uniform deployment on a ring is posed in Flocchini et al. 2006
Self-deployment of mobile sensors on a ring (ALGOSENSORS 2006).
Mobile agents on graphs · Exploration
Gathering by oblivious robots on graphs is posed in Klasing et al. 2006
Gathering of asynchronous oblivious robots on a ring (ISAAC 2006).
In the logical view: variant of Gathering in graphs, but was posed before it (2012).
- Ilcinkas 2006 — Graph exploration by a single agent: Port numbers chosen by the designer (periodic exploration) introduced
- Agmon & Peleg 2006 — Gathering: Crash faults, SSYNC introduced, Byzantine faults, SSYNC lower bound, Byzantine faults, FSYNC current best
- Czyzowicz et al. 2006b — Gathering: Fat robots, few robots, no common orientation current best
- Dieudonné et al. 2006 — Uniform circle formation: SSYNC, oblivious introduced
- Dobrev et al. 2006 — Black hole search: Tokens, no map introduced
- Czyzowicz et al. 2006a — Black hole search: Synchronous agents with a map introduced
- Flocchini et al. 2006 — Uniform deployment on a ring: Oriented ring, asynchronous, oblivious current best, Oriented ring, asynchronous, oblivious lower bound
- Klasing et al. 2006 — Gathering by oblivious robots on graphs: Rings, SSYNC, no multiplicity detection lower bound, Rings, ASYNC, weak multiplicity detection introduced, Rings, ASYNC, weak multiplicity detection lower bound
2007
Mobile agents on graphs · Exploration
Treasure hunt is posed in Ta-Shma & Zwick 2007
Ta-Shma and Zwick introduced the deterministic treasure hunt problem at SODA 2007, as a variant of rendezvous in which one agent never moves.
In the logical view: subproblem of Graph exploration by a single agent, which was posed earlier (1951).
Mobile robots in the plane · Symmetry breaking and spreading
Leader election in the plane is posed in Dieudonné et al. 2012a
Posed for disoriented robots at OPODIS 2007 (Dieudonné and Petit); characterised in Dieudonné et al. 2013.
Mobile robots in the plane · Formation problems
k-grouping is posed in Efrima & Peleg 2007b
Splitting a swarm into a given number of groups was introduced at SIROCCO 2007, under the name partitioning. No paper titled "k-grouping" was found.
In the logical view: special case of Pattern formation, which was posed earlier (1999).
Mobile agents on graphs · Exploration
Exploration by oblivious robots is posed in Flocchini et al. 2007
Ring exploration by asynchronous oblivious robots (OPODIS 2007).
In the logical view: variant of Graph exploration by a single agent, which was posed earlier (1951).
- Ambühl et al. 2007 — Graph exploration by a single agent: Trees, exploration with stop current best, Trees, exploration with return current best
- Ta-Shma & Zwick 2007 — Treasure hunt: Anonymous finite graphs introduced; Rendezvous: Labelled agents, arbitrary finite graphs current best
- Das et al. 2007 — Map construction: Identical agents with whiteboards introduced, Identical agents with whiteboards current best, Identical agents with whiteboards lower bound
- Dieudonné & Petit 2007 — Scattering: Randomized, SSYNC, strong multiplicity detection introduced, Randomized, SSYNC, strong multiplicity detection lower bound
- Efrima & Peleg 2007b — k-grouping: \(k\) groups of equal size current best, \(k\) equal groups, no common orientation, deterministic lower bound, \(k\) equal groups, randomized, SSYNC current best
- Ilcinkas et al. 2007 — Network decontamination: Unknown graphs, monotone strategies current best, Unknown graphs, monotone strategies lower bound
- Flocchini et al. 2007 — Exploration by oblivious robots: Rings, ASYNC, terminating introduced, Rings, ASYNC, terminating lower bound, Rings, SSYNC, terminating lower bound
2008
- Fraigniaud & Pelc 2008 — Rendezvous: Anonymous agents in trees, simultaneous start current best, Anonymous agents in trees, simultaneous start lower bound
- Flocchini et al. 2008a — Pattern formation: ASYNC, no agreement on coordinates introduced, ASYNC, no agreement on coordinates lower bound, ASYNC with one common axis current best, ASYNC with one common axis lower bound, ASYNC with a common compass current best
- Défago & Souissi 2008 — Circle formation: Circle formation, SSYNC current best
- Flocchini et al. 2008c — Black hole search: Tokens and a map current best
- Clement et al. 2008 — Scattering: Randomized, SSYNC, strong multiplicity detection current best
2009
Mobile robots in the plane · Symmetry breaking and spreading
Scattering is posed in Dieudonné & Petit 2007
Dieudonné and Petit showed scattering is deterministically impossible and gave a randomized solution (preprint 2007).
- Czyzowicz et al. 2009b — Graph exploration by a single agent: Port numbers chosen by the designer (periodic exploration) current best, Port numbers chosen by the designer (periodic exploration) lower bound
- Lamani et al. 2009 — Exploration by oblivious robots: Rings, ASYNC, terminating current best, Rings, ASYNC, terminating lower bound, Rings, SSYNC, terminating current best, Rings, SSYNC, terminating lower bound
- Devismes et al. 2009 — Exploration by oblivious robots: Rings, ASYNC, terminating lower bound, Rings, SSYNC, terminating lower bound, Rings, probabilistic, SSYNC, terminating current best, Rings, probabilistic, SSYNC, terminating lower bound
- Bampas et al. 2009 — Exploration of recolourable graphs: Rotor-router with pointers set by a designer current best
- Miyazaki et al. 2009 — Online exploration of weighted graphs: Weighted cycles current best, Weighted cycles lower bound
2010s
2010
Mobile robots in the plane · Formation problems
Pattern sequences is posed in Das et al. 2010
Introduced at PODC 2010.
In the logical view: generalisation of Pattern formation, which was posed earlier (1999).
Mobile agents on graphs · Computing with agents
Deciding graph properties by mobile agents is posed in Fraigniaud & Pelc 2010
Fraigniaud and Pelc introduced decision problems for mobile agents and the classes \(\mathsf{MAD}\) and \(\mathsf{MAV}\), as Bampas & Ilcinkas 2018 reports (arXiv 2010; LATIN 2012; Journal of Parallel and Distributed Computing 2017).
- Czyzowicz et al. 2010b — Rendezvous: Anonymous agents: memory current best, Anonymous agents: memory lower bound
- Chaudhuri & Mukhopadhyaya 2010 — Gathering: Transparent fat robots, no chirality introduced
- Chalopin et al. 2010a — Map construction: One agent, no marking current best
- Izumi et al. 2010 — Scattering: Limited visibility, connectivity preserving current best, Limited visibility, connectivity preserving lower bound
- Das et al. 2010 — Pattern sequences: Oblivious, SSYNC, chirality current best
- Blin et al. 2010 — Exploration by oblivious robots: Rings, ASYNC, exclusive perpetual introduced, Rings, ASYNC, exclusive perpetual lower bound
- Fraigniaud & Pelc 2010 — Deciding graph properties by mobile agents: Any number of agents lower bound, Two or more agents that know their number current best, One agent lower bound, One agent that knows \(n\) lower bound, One agent with a map current best
2011
Search in geometric domains · Search, evacuation and patrolling
Patrolling is posed in Czyzowicz et al. 2011
Boundary patrolling by agents with distinct speeds (ESA 2011).
- Guilbault & Pelc 2011 — Rendezvous: Asynchronous anonymous agents current best
- Degener et al. 2011 — Gathering: Limited visibility, FSYNC, disoriented introduced
- Katreniak 2011 — Convergence: Limited visibility, asynchronous introduced
- Dieudonné & Pelc 2011 — Gathering in graphs: Anonymous agents current best, Anonymous agents lower bound
- Czyzowicz et al. 2011 — Patrolling: Open fence, distinct speeds introduced, Closed fence, one-way, distinct speeds introduced, Closed fence, one-way, distinct speeds lower bound, Closed fence, two-way, distinct speeds introduced
- Devismes et al. 2011 — Exploration by oblivious robots: Grids, ASYNC, terminating current best, Grids, ASYNC, terminating lower bound
2012
Mobile agents on graphs · Exploration
Gathering in graphs is posed in Dieudonné et al. 2012b
Gathering many agents in arbitrary graphs grew out of two-agent rendezvous; the Byzantine version was posed at SODA 2012.
In the logical view: generalisation of Rendezvous, which was posed earlier (2003).
Mobile robots in the plane · Formation problems
Near-gathering is posed in Pagli et al. 2012
Introduced at SIROCCO 2012.
In the logical view: relaxation of Gathering, which was posed earlier (1999).
Mobile agents on graphs · Exploration
Collision-free exploration is posed in Czyzowicz et al. 2012b
Formalised by Czyzowicz, Dereniowski, Gąsieniec, Klasing, Kosowski and Pająk for agents on graphs with labelled nodes (a 2012 report; LATIN 2014; Journal of Computer and System Sciences 2017); Papin 2026 calls this the first formalisation. Bhagat and Pelc posed it for anonymous graphs Bhagat & Pelc 2025.
In the logical view: variant of Graph exploration by a single agent, which was posed earlier (1951).
- Dieudonné & Pelc 2012 — Graph exploration by a single agent: Exploration with stop, nothing known lower bound
- Das et al. 2012 — Gathering: Rendezvous, full lights (LUMI), ASYNC, non-rigid introduced
- Viglietta 2012 — Gathering: Rendezvous, full lights (LUMI), ASYNC, non-rigid lower bound
- Agathangelou et al. 2012 — Gathering: Fat robots, chirality, any number current best
- Chaudhuri & Mukhopadhyaya 2012 — Gathering: Transparent fat robots, no chirality current best; Leader election in the plane: Transparent fat robots, no chirality current best, Transparent fat robots, no chirality lower bound
- Balamohan et al. 2012 — Black hole search: Tokens, no map current best, Tokens, no map lower bound
- Dieudonné et al. 2012b — Gathering in graphs: Weakly Byzantine agents current best, Weakly Byzantine agents lower bound, Byzantine agents introduced, Byzantine agents lower bound
- Dieudonné et al. 2012a — Leader election in the plane: Disoriented robots, with or without chirality current best, Disoriented robots, with or without chirality lower bound
- Pagli et al. 2012 — Near-gathering: ASYNC, limited visibility, one common axis current best
- Kawamura & Kobayashi 2012 — Patrolling: Open fence, distinct speeds lower bound
- Datta et al. 2012 — Exploration by luminous robots: Rings, FSYNC, terminating, \(\varphi = 1\) lower bound, Rings, oblivious, FSYNC, terminating, \(\varphi = 1\) current best, Rings, oblivious, FSYNC, terminating, \(\varphi = 1\) lower bound, Rings, oblivious, ASYNC, terminating, \(\varphi = 1\) lower bound
- D'Angelo et al. 2012 — Gathering by oblivious robots on graphs: Finite grids, ASYNC, no multiplicity detection current best, Finite grids, ASYNC, no multiplicity detection lower bound, Trees, ASYNC, no multiplicity detection current best, Trees, ASYNC, no multiplicity detection lower bound
- Czyzowicz et al. 2012b — Collision-free exploration: Labelled trees, with a map, any number of agents current best, Labelled trees, with a map, any number of agents lower bound, Labelled graphs, with a map, any number of agents current best, Labelled graphs, with a map, any number of agents lower bound, Labelled trees, no knowledge, any number of agents current best, Labelled trees, no knowledge, any number of agents lower bound, Labelled graphs, no knowledge, any number of agents current best, Labelled graphs, no knowledge, any number of agents lower bound
- Anaya et al. 2012 — Delivery by energy-constrained agents: Paths, equal budgets current best
2013
Mobile agents on graphs · Exploration
Delivery by energy-constrained agents is posed in Chalopin et al. 2013
Chalopin, Das, Mihalák, Penna and Widmayer first studied collaborative delivery, as Chalopin et al. 2021 reports (ALGOSENSORS 2013). Anaya et al. had treated the transfer between two points of a path as part of convergecast with equal budgets (DISC 2012) Anaya et al. 2016.
- Ilcinkas & Wade 2013 — Graph exploration by a single agent: Dynamic rings current best, Dynamic rings lower bound
- Dereniowski et al. 2013 — Collaborative exploration: Large teams, complete communication current best, Large teams, complete communication lower bound, Large teams, local communication current best, Large teams, local communication lower bound
- Dieudonné et al. 2013 — Rendezvous: Asynchronous labelled agents current best
- Flocchini et al. 2013 — Gathering: Two robots, SSYNC lower bound, Rendezvous, external light (FCOM), SSYNC current best, Rendezvous, external light (FCOM), ASYNC, non-rigid current best, Rendezvous, external light (FCOM), ASYNC, rigid introduced, Rendezvous, internal light (FSTA), SSYNC, non-rigid current best, Rendezvous, internal light (FSTA), SSYNC, rigid introduced
- Bramas & Tixeuil 2013 — Scattering: Randomized, SSYNC, weak multiplicity detection current best, Randomized, SSYNC, weak multiplicity detection lower bound
- Chalopin et al. 2013 — Delivery by energy-constrained agents: Arbitrary graphs current best, Arbitrary graphs lower bound, Arbitrary graphs, equal budgets current best, Arbitrary graphs, equal budgets lower bound
2014
Search in geometric domains · Search, evacuation and patrolling
Evacuation is posed in Czyzowicz et al. 2014
Czyzowicz et al. posed evacuation of \(k\) robots from a disk through an unknown exit on its boundary at DISC 2014.
In the logical view: generalisation of Linear search (cow path), which was posed earlier (1964).
Mobile robots in the plane · Formation problems
Mutual visibility is posed in Di Luna et al. 2015a
Introduced at CCCG 2014 for oblivious robots and at SSS 2014 for robots with lights Di Luna et al. 2014; journal version Di Luna et al. 2017.
In the logical view: special case of Pattern formation, which was posed earlier (1999).
Programmable matter · Self-organising particle systems
Coating is posed in Derakhshandeh et al. 2016b
Infinite object coating appeared as an arXiv preprint in 2014; universal coating in Derakhshandeh et al. 2017.
- Miller & Pelc 2014c — Treasure hunt: Treasure hunt with advice current best, Treasure hunt with advice lower bound
- Yamauchi & Yamashita 2014 — Pattern formation: Randomized, ASYNC, chirality introduced
- Flocchini et al. 2014 — Circle formation: Circle formation current best; Uniform circle formation: ASYNC, oblivious, disoriented current best, ASYNC, oblivious, disoriented lower bound
- Czyzowicz et al. 2014 — Evacuation: Two wireless robots, disk current best, Two wireless robots, disk lower bound, Two face-to-face robots, disk introduced, Three wireless robots, disk current best, Three wireless robots, disk lower bound, Three face-to-face robots, disk current best, Three face-to-face robots, disk lower bound, Many wireless robots, disk current best, Many wireless robots, disk lower bound, Many face-to-face robots, disk current best, Many face-to-face robots, disk lower bound, Disk, \(k\) wireless robots, \(f\) Byzantine lower bound, Disk, \(k\) face-to-face robots, \(f\) Byzantine lower bound, Disk, \(k\) face-to-face robots, \(f\) crash faults lower bound
- Das et al. 2014b — Pattern sequences: Luminous robots, ASYNC, non-rigid, chirality current best, Luminous robots, ASYNC, non-rigid, chirality lower bound
- Dumitrescu et al. 2014 — Patrolling: Closed fence, two-way, distinct speeds current best
- Chalopin et al. 2014a — Delivery by energy-constrained agents: Paths current best, Paths lower bound
2015
Programmable matter · Self-organising particle systems
Leader election in programmable matter is posed in Derakhshandeh et al. 2015b
Introduced with shape formation at DNA 21 (2015).
Programmable matter · Self-organising particle systems
Shape formation in programmable matter is posed in Derakhshandeh et al. 2015b
Introduced with leader election at DNA 21 (2015).
- Erlebach et al. 2015 — Graph exploration by a single agent: Temporal graphs, schedule known current best, Temporal graphs, schedule known lower bound
- Bhagat et al. 2015 — Gathering: Crash faults, one common axis, opaque robots current best
- Chrobak et al. 2015 — Linear search (cow path): Two robots of different speeds, both must reach the target introduced; Evacuation: Line, any number of face-to-face robots current best, Line, any number of face-to-face robots lower bound
- Czyzowicz et al. 2015d — Evacuation: Two face-to-face robots, disk lower bound
- Czyzowicz et al. 2015a — Evacuation: Triangle, two wireless robots starting on the boundary introduced, Triangle, two wireless robots at the centroid current best, Triangle, two wireless robots at the centroid lower bound, Triangle, any number of wireless robots at the centroid introduced, Triangle, any number of wireless robots at the centroid lower bound, Triangle, any number of wireless robots starting on the boundary current best, Triangle, any number of wireless robots starting on the boundary lower bound, Square, any number of wireless robots at the centre current best, Square, any number of wireless robots at the centre lower bound, Square, two wireless robots starting on the boundary current best, Square, two wireless robots starting on the boundary lower bound
- Bouchard et al. 2015 — Gathering in graphs: Byzantine agents current best
- Di Luna et al. 2015b — Exploration of dynamic graphs by teams: 1-interval-connected rings introduced, 1-interval-connected rings lower bound
- Di Luna et al. 2015a — Mutual visibility: Lights, SSYNC, rigid current best, Lights, SSYNC, rigid lower bound, Lights, SSYNC, non-rigid introduced, Lights, SSYNC, non-rigid lower bound, Finite state, SSYNC, non-rigid lower bound, Lights, ASYNC, rigid introduced, Lights, ASYNC, rigid lower bound, Lights, ASYNC, non-rigid, one axis introduced, Lights, ASYNC, non-rigid, one axis lower bound, Lights, crash faults, ASYNC, one axis lower bound, Lights, mobility faults, SSYNC, non-rigid lower bound
- Sharma et al. 2015b — Mutual visibility: Lights, SSYNC, non-rigid current best, Lights, ASYNC, non-rigid, one axis current best
- Vaidyanathan et al. 2015 — Mutual visibility: Lights, FSYNC, rigid, chirality current best
- Derakhshandeh et al. 2015b — Leader election in programmable matter: Randomized, with chirality introduced; Shape formation in programmable matter: SILBOT, full orientation lower bound
- Czyzowicz et al. 2015c — Patrolling: Graphs with faulty patrollers current best, Graphs with faulty patrollers lower bound
- Menc et al. 2015b — Exploration of recolourable graphs: Rotor-router: a pointer in every node lower bound
- D'Emidio et al. 2015b — Gathering by oblivious robots on graphs: Rings, ASYNC, weak multiplicity detection lower bound
- Bampas & Ilcinkas 2015 — Deciding graph properties by mobile agents: Any number of agents, with certificates lower bound
2016
Mobile agents on graphs · Exploration
Uniform deployment on graphs is posed in Shibata et al. 2016
Agents that have memory but see only the node they are on, in asynchronous unidirectional rings (PODC 2016), as reported by Shibata et al. 2022a; not read. Look–Compute–Move robots that see several nodes had been deployed on rings and grids before, as listed in Shibata et al. 2022a.
Mobile agents on graphs · Exploration
Exploration of dynamic graphs by teams is posed in Di Luna et al. 2015b
Live exploration of dynamic rings was posed at ICDCS 2016.
In the logical view: variant of Collaborative exploration, which was posed earlier (2004).
Programmable matter · Self-organising particle systems
Compression is posed in Cannon et al. 2016
PODC 2016.
- Disser et al. 2016a — Graph exploration by a single agent: Exploration with stop when \(n\) is known lower bound, Exploration with return and pebbles current best, Exploration with return and pebbles lower bound; Collaborative exploration: Anonymous graphs, a team of constant-memory agents current best, Anonymous graphs, a team of constant-memory agents lower bound
- Disser et al. 2016b — Collaborative exploration: Trees, complete communication lower bound, Trees with \(k = n\) agents current best, Trees with \(k = n\) agents lower bound; Dispersion: Trees lower bound, Rooted trees lower bound
- Shibata et al. 2016 — Uniform deployment on graphs: Asynchronous unidirectional rings current best, Asynchronous unidirectional rings lower bound
- Pattanayak et al. 2016b — Gathering: Crash faults, SSYNC current best, Crash faults, SSYNC lower bound, Crash faults, ASYNC, restricted start current best
- Balabonski et al. 2016 — Gathering: FSYNC, no multiplicity detection current best
- Czyzowicz et al. 2016b — Linear search (cow path): \(k\) robots on a line, \(f\) crash faults current best
- Czyzowicz et al. 2016c — Linear search (cow path): \(k\) robots on a line, Byzantine faults current best
- Bampas et al. 2016 — Linear search (cow path): Two robots of different speeds, both must reach the target current best, Two robots of different speeds, both must reach the target lower bound; Evacuation: Line, any number of face-to-face robots lower bound, Line, any number of wireless robots current best, Line, any number of wireless robots lower bound, Line, two face-to-face robots of different speeds current best, Line, two face-to-face robots of different speeds lower bound, Line, two wireless robots of different speeds current best, Line, two wireless robots of different speeds lower bound
- Lamprou et al. 2016 — Evacuation: Disk, two wireless robots of different speeds current best, Disk, two wireless robots of different speeds lower bound
- Georgiou et al. 2016b — Evacuation: Disk, search-and-fetch, two wireless robots current best, Disk, search-and-fetch, two face-to-face robots current best, Disk, search-and-fetch, two face-to-face robots lower bound
- Derakhshandeh et al. 2016a — Shape formation in programmable matter: Universal shapes, sequential, randomized current best, Universal shapes, sequential, randomized lower bound
- Derakhshandeh et al. 2016b — Coating: Universal coating introduced, Universal coating lower bound
- Daymude et al. 2016 — Coating: Universal coating current best, Universal coating lower bound
- Cannon et al. 2016 — Compression: Markov chain, sequential current best
- Bérard et al. 2016 — Exploration by oblivious robots: Rings, ASYNC, exclusive perpetual current best
- Bärtschi et al. 2016b — Delivery by energy-constrained agents: Arbitrary graphs current best, Arbitrary graphs lower bound, Planar graphs, equal budgets lower bound
2017
Programmable matter · Self-organising particle systems
Bridging is posed in Arroyo et al. 2017
arXiv 2017; Natural Computing 2018.
In the logical view: generalisation of Compression, which was posed earlier (2016).
Programmable matter · Self-organising particle systems
Shape formation by hybrid programmable matter is posed in Gmyr et al. 2017
First presented at EuroCG 2017 (non-archival); DNA 24 (2018); Natural Computing 2020. The work began at a Dagstuhl seminar in 2016.
Programmable matter · Self-organising particle systems
Centralised transformations of modular robots is posed in Michail et al. 2017
arXiv 2017; JCSS 2019.
- Augustine & Moses Jr. 2017 — Collaborative exploration: Anonymous graphs with \(k = n\) agents introduced; Dispersion: Arbitrary graph, arbitrary initial configuration introduced, Arbitrary graph, arbitrary initial configuration lower bound, Rooted initial configuration introduced, Rooted initial configuration lower bound, Asynchronous agents lower bound, Rings and paths introduced, Rings and paths lower bound, Trees introduced, Trees lower bound, Rooted trees current best, Rooted trees lower bound, Crash faults lower bound, Weak Byzantine agents lower bound, Weak Byzantine agents on rings lower bound, Weak Byzantine agents on oriented grids lower bound
- Agarwalla et al. 2017 — Dispersion: Dynamic rings current best
- Cicerone et al. 2017 — Pattern formation: ASYNC, no agreement on coordinates current best
- Poudel & Sharma 2017 — Gathering: Limited visibility with a compass, rigid, ASYNC current best, Limited visibility with a compass, rigid, ASYNC lower bound, Limited visibility, one common axis, rigid, ASYNC current best, Limited visibility, one common axis, rigid, ASYNC lower bound
- Heriban et al. 2017 — Gathering: Rendezvous, full lights (LUMI), ASYNC, non-rigid current best
- Mondal & Chaudhuri 2017 — Uniform circle formation: Transparent fat robots, SSYNC current best
- Kupavskii & Welzl 2017 — Linear search (cow path): \(k\) robots on a line, \(f\) crash faults lower bound, \(k\) robots on a line, Byzantine faults lower bound; Evacuation: Line, \(2f+1\) wireless robots, \(f\) crash faults lower bound
- Czyzowicz et al. 2017b — Evacuation: Three wireless robots, one crash fault current best, Three wireless robots, one crash fault lower bound, Three wireless robots, one Byzantine current best, Three wireless robots, one Byzantine lower bound
- Chuangpishit et al. 2017c — Evacuation: Two face-to-face robots, equilateral triangle current best, Two face-to-face robots, equilateral triangle lower bound, Two face-to-face robots, square current best, Two face-to-face robots, square lower bound, Triangle, any number of face-to-face robots current best, Triangle, any number of face-to-face robots lower bound
- Pattanayak et al. 2017 — Evacuation: Two robots, two exits, face-to-face current best, Two robots, two exits, face-to-face lower bound, Two robots, two exits, wireless current best, Two robots, two exits, wireless lower bound
- Brandt et al. 2017b — Evacuation: \(m\) rays, \(k = m\) wireless robots at the junction current best, \(m\) rays, \(k = m\) wireless robots at the junction lower bound
- Bhagat & Mukhopadhyaya 2017 — Mutual visibility: Finite state, SSYNC, non-rigid current best
- Sharma et al. 2017b — Mutual visibility: Lights, ASYNC, rigid current best, Lights, ASYNC, rigid lower bound
- Aljohani & Sharma 2017 — Mutual visibility: Lights, one crash, SSYNC, rigid, compass current best, Lights, one Byzantine robot lower bound
- Daymude et al. 2017 — Leader election in programmable matter: Randomized, with chirality current best
- Di Luna et al. 2017d — Shape formation in programmable matter: Deterministic, simply connected start, no chirality current best, Deterministic, simply connected start, no chirality lower bound
- Arroyo et al. 2017 — Bridging: Markov chain, sequential current best
- Gmyr et al. 2017 — Shape formation by hybrid programmable matter: Planar current best, Planar lower bound
- Michail et al. 2017 — Centralised transformations of modular robots: Rotation only current best, Rotation and sliding current best, Rotation and sliding lower bound
2018
Mobile agents on graphs · Exploration
Dispersion is posed in Augustine & Moses Jr. 2017
Posed at ICDCN 2018, fourteen years after collaborative exploration; the introductory paper already relates dispersion to \(n\)-robot collaborative exploration and takes its tree lower bound from it.
In the logical view: derived from Collaborative exploration, which was posed earlier (2004).
Programmable matter · Self-organising particle systems
Convex hull formation is posed in Daymude et al. 2018
arXiv 2018; ICDCN 2020.
Mobile agents on graphs · Exploration
Exploration by luminous robots is posed in Ooshita & Tixeuil 2018
Ring exploration by myopic robots with a two-colour light (SSS 2018).
In the logical view: variant of Exploration by oblivious robots, which was posed earlier (2007).
Programmable matter · Self-organising particle systems
Separation of coloured particles is posed in Cannon et al. 2018
arXiv 2018; APPROX/RANDOM 2019.
In the logical view: generalisation of Compression, which was posed earlier (2016).
- Kshemkalyani & Ali 2018 — Collaborative exploration: Anonymous graphs with \(k = n\) agents lower bound; Dispersion: Arbitrary graph, arbitrary initial configuration lower bound, Rooted initial configuration lower bound, Asynchronous agents introduced, Asynchronous agents lower bound, Rings and paths lower bound, Anonymous agents with randomness lower bound, Crash faults lower bound, Weak Byzantine agents lower bound, Strong Byzantine agents lower bound
- Kshemkalyani et al. 2018b — Dispersion: Unoriented grids current best, Unoriented grids lower bound, Oriented grids lower bound, Crash faults on unoriented grids lower bound, Crash faults on oriented grids lower bound, Weak Byzantine agents on oriented grids lower bound
- Pelc & Yadav 2018a — Rendezvous: Anonymous agents: memory current best, Anonymous agents: memory lower bound
- Okumura et al. 2018 — Gathering: Rendezvous, external light (FCOM), SSYNC lower bound
- Terai et al. 2018 — Gathering: Gathering, full lights, SSYNC, no multiplicity detection current best, Gathering, full lights, ASYNC, no multiplicity detection introduced, Gathering, external light (FCOM), SSYNC, rigid current best, Gathering, internal light (FSTA), SSYNC, non-rigid introduced, Gathering, external light, sequential scheduler current best, Gathering, external light, sequential scheduler lower bound
- Feletti et al. 2018 — Uniform circle formation: Opaque robots with lights, FSYNC introduced
- Czyzowicz et al. 2018b — Evacuation: Priority evacuation (queen and servants), disk current best, Priority evacuation (queen and servants), disk lower bound
- Czyzowicz et al. 2018a — Evacuation: Disk, priority evacuation, queen and one servant introduced, Disk, priority evacuation, queen and two servants current best, Disk, priority evacuation, queen and two servants lower bound
- Sharma et al. 2018 — Mutual visibility: Fat robots, FSYNC, rigid introduced
- Poudel et al. 2018 — Mutual visibility: Lights, crash faults, ASYNC, one axis current best
- Gastineau et al. 2018 — Leader election in programmable matter: Stationary, chirality, no holes current best
- Bazzi & Briones 2018 — Leader election in programmable matter: Stationary, chirality, weak scheduler current best, Stationary, chirality, weak scheduler lower bound
- Daymude et al. 2018 — Convex hull formation: No orientation current best
- Haeupler et al. 2018 — Patrolling: Open fence, distinct speeds current best, Open fence, distinct speeds lower bound, Closed fence, one-way, distinct speeds current best
- Ooshita & Tixeuil 2018 — Exploration by luminous robots: Rings, FSYNC, perpetual, \(\varphi = 1\) current best, Rings, FSYNC, perpetual, \(\varphi = 1\) lower bound, Rings, FSYNC, terminating, \(\varphi = 1\) current best, Rings, FSYNC, terminating, \(\varphi = 1\) lower bound, Rings, ASYNC, perpetual, \(\varphi = 1\) current best, Rings, ASYNC, perpetual, \(\varphi = 1\) lower bound, Rings, ASYNC, terminating, \(\varphi = 1\) current best, Rings, ASYNC, terminating, \(\varphi = 1\) lower bound
- Cannon et al. 2018 — Separation of coloured particles: Markov chain, sequential current best
2019
Search in geometric domains · Search, evacuation and patrolling
Chauffeuring a crashed robot is posed in Pattanayak et al. 2019a
ALGOSENSORS 2019.
In the logical view: variant of Evacuation, which was posed earlier (2014).
- Molla & Moses Jr. 2019 — Dispersion: More agents than nodes current best, More agents than nodes lower bound, Anonymous agents with randomness introduced, Anonymous agents with randomness lower bound
- Bose et al. 2019c — Pattern formation: Opaque robots with lights, ASYNC, one axis, rigid current best, Opaque robots with lights, ASYNC, compass, rigid current best, Opaque oblivious robots, ASYNC, compass lower bound
- Bose et al. 2019b — Pattern formation: Opaque fat robots with lights, ASYNC, one axis current best
- Disser & Schmitt 2019 — Evacuation: Two face-to-face robots, disk current best
- Georgiou et al. 2019 — Evacuation: Disk, \(k\) wireless robots, \(f\) Byzantine lower bound, Disk, \(k\) face-to-face robots, \(f\) Byzantine lower bound, Disk, \(k\) face-to-face robots, \(f\) crash faults lower bound, Disk search, \(k\) wireless robots, \(f\) crash faults current best, Disk search, \(k\) wireless robots, \(f\) crash faults lower bound, Disk search, \(k\) wireless robots, one Byzantine current best, Disk search, \(k\) wireless robots, one Byzantine lower bound
- Bagheri et al. 2019 — Evacuation: Triangle, any number of wireless robots at the centroid current best
- Gotoh et al. 2019b — Exploration of dynamic graphs by teams: Temporally connected graphs, arbitrary topology current best, Temporally connected graphs, arbitrary topology lower bound
- Léchine & Tixeuil 2019 — Scattering: Randomized, ASYNC, weak multiplicity detection current best, Randomized, ASYNC, rigid, weak multiplicity detection, no vision needed current best
- Emek et al. 2019 — Leader election in programmable matter: Deterministic, no orientation current best
- Ilcinkas 2019 — Exploration by oblivious robots: Rings, ASYNC, exclusive perpetual lower bound
- Nagahama et al. 2019 — Exploration by luminous robots: Rings, ASYNC, perpetual, \(\varphi \ge 2\) current best, Rings, ASYNC, perpetual, \(\varphi \ge 2\) lower bound, Rings, ASYNC, terminating, \(\varphi \ge 2\) current best, Rings, ASYNC, terminating, \(\varphi \ge 2\) lower bound
- Pattanayak et al. 2019a — Chauffeuring a crashed robot: \(e\) exits current best, One exit current best, Two exits current best
- Cicerone et al. 2019 — Gathering by oblivious robots on graphs: Complete graphs, FSYNC, strong multiplicity detection current best, Complete graphs, FSYNC, strong multiplicity detection lower bound
2020s
2020
Programmable matter · Self-organising particle systems
Energy distribution is posed in Daymude et al. 2020
arXiv 2020; ICDCN 2021.
Mobile agents on graphs · Exploration
Broadcast by agents in dynamic graphs is posed in Das et al. 2020b
Posed at OPODIS 2020; the journal version appeared in Discrete Applied Mathematics (2026).
- Kshemkalyani et al. 2020 — Dispersion: Dynamic graphs (1-interval connected) lower bound, Dynamic graphs with global communication current best, Dynamic graphs with global communication lower bound
- Das et al. 2020a — Dispersion: Anonymous agents with randomness current best
- Molla et al. 2020 — Dispersion: Weak Byzantine agents on rings current best, Weak Byzantine agents on rings lower bound
- Shibata et al. 2020 — Uniform deployment on graphs: Dynamic rings, all agents lower bound, Dynamic rings, all agents but one current best, Dynamic rings, all agents but one lower bound
- Bouchard et al. 2020 — Treasure hunt: Labelled nodes, locally finite graphs current best, Labelled nodes, locally finite graphs lower bound
- Mondal et al. 2020 — Uniform circle formation: Opaque fat robots, ASYNC, limited visibility, compass current best
- Georgiou & Lucier 2020 — Evacuation: Line, weighted evacuation of two wireless robots current best, Line, weighted evacuation of two wireless robots lower bound, Line, weighted evacuation of two face-to-face robots current best, Line, weighted evacuation of two face-to-face robots lower bound, Line, priority evacuation, queen and one wireless servant current best, Line, priority evacuation, queen and one face-to-face servant current best
- Di Luna et al. 2020b — Black hole search: Dynamic rings current best, Dynamic rings lower bound
- Dobrev et al. 2020a — Exploration of dynamic graphs by teams: Connected at every step, any graph current best, Connected at every step, any graph lower bound
- D'Angelo et al. 2020 — Leader election in programmable matter: Silent oblivious particles (SILBOT) current best, SILBOT with holes current best, SILBOT with holes lower bound
- Daymude et al. 2020 — Energy distribution: Unfair adversary current best, Unfair adversary lower bound
- Das et al. 2020b — Broadcast by agents in dynamic graphs: Static graph current best, Dynamic graph, any topology current best, Dynamic graph, any topology lower bound, Dynamic rings current best, Dynamic rings lower bound, Dynamic complete graphs current best, Dynamic complete graphs lower bound, Dynamic bipartite graphs current best, Dynamic bipartite graphs lower bound, Dynamic hypercubes current best, Dynamic hypercubes lower bound, Dynamic grids current best, Dynamic grids lower bound
2021
Mobile robots in the plane · Formation problems
Partitioning is posed in Bhagat et al. 2021
The fixed-point version (\(k\)-EPF) was posed with \(k\)-circle formation in 2021; the earlier partitioning of Efrima and Peleg fixes the number of groups instead and is recorded under \(k\)-grouping.
In the logical view: special case of Pattern formation, which was posed earlier (1999).
- Pattanayak et al. 2021 — Dispersion: Crash faults introduced
- Molla et al. 2021 — Dispersion: Weak Byzantine agents current best, Weak Byzantine agents lower bound, Strong Byzantine agents introduced
- Gorain et al. 2021 — Treasure hunt: Treasure hunt guided by pebbles current best, Treasure hunt guided by pebbles lower bound
- Cicerone et al. 2021 — Pattern formation: ASYNC with common chirality current best
- Bramas et al. 2021c — Gathering: Rendezvous, full lights, a crash, SSYNC lower bound
- Nakai et al. 2021 — Gathering: Gathering, full lights, ASYNC, no multiplicity detection current best
- Kirkpatrick et al. 2021 — Convergence: Limited visibility, asynchronous current best
- Czyzowicz et al. 2021c — Evacuation: Line, any number of wireless robots lower bound, Line, a sender and a receiver current best, Line, a sender and a receiver lower bound; Search for a moving target: Line, a sender and a receiver, away, \(u\) known lower bound
- Czyzowicz et al. 2021d — Evacuation: Line, \(2f+1\) wireless robots, \(f\) crash faults current best
- Leonardos et al. 2021 — Evacuation: Disk, \(k\) wireless robots, \(f\) Byzantine introduced, Disk, \(k\) face-to-face robots, \(f\) Byzantine introduced, Disk, \(k\) face-to-face robots, \(f\) crash faults current best
- Dufoulon et al. 2021 — Leader election in programmable matter: Deterministic, with chirality current best
- Feldmann et al. 2021 — Leader election in programmable matter: Stationary, reconfigurable circuits, synchronous, randomized current best
- Bramas et al. 2021b — Exploration by luminous robots: Grids, FSYNC, perpetual, chirality, \(\varphi = 1\) current best, Grids, FSYNC, perpetual, chirality, \(\varphi = 1\) lower bound, Grids, FSYNC, perpetual, chirality, \(\varphi = 2\) current best, Grids, FSYNC, perpetual, chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, perpetual, chirality, \(\varphi = 2\) current best, Grids, ASYNC, perpetual, chirality, \(\varphi = 2\) lower bound, Grids, FSYNC, terminating, chirality, \(\varphi = 1\) lower bound, Grids, FSYNC, terminating, no chirality, \(\varphi = 1\) lower bound, Grids, FSYNC, terminating, chirality, \(\varphi = 2\) lower bound, Grids, FSYNC, terminating, no chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, terminating, chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, terminating, no chirality, \(\varphi = 2\) lower bound
- Rauch et al. 2021 — Exploration by luminous robots: Grids, FSYNC, perpetual, no chirality, \(\varphi = 1\) current best, Grids, FSYNC, perpetual, no chirality, \(\varphi = 1\) lower bound, Grids, ASYNC, perpetual, no chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, perpetual, no chirality, \(\varphi = 3\) lower bound
- Nagahama et al. 2021 — Exploration by luminous robots: Grids, FSYNC, terminating, chirality, \(\varphi = 1\) current best, Grids, FSYNC, terminating, no chirality, \(\varphi = 1\) current best, Grids, FSYNC, terminating, chirality, \(\varphi = 2\) current best, Grids, FSYNC, terminating, no chirality, \(\varphi = 2\) current best, Grids, ASYNC, terminating, chirality, \(\varphi = 1\) current best, Grids, ASYNC, terminating, chirality, \(\varphi = 1\) lower bound, Grids, ASYNC, terminating, no chirality, \(\varphi = 1\) current best, Grids, ASYNC, terminating, no chirality, \(\varphi = 1\) lower bound, Grids, ASYNC, terminating, chirality, \(\varphi = 2\) current best, Grids, ASYNC, terminating, no chirality, \(\varphi = 2\) current best
- Bojko et al. 2021 — Exploration of recolourable graphs: Recolourable nodes, oblivious agent, any graph lower bound, Recolourable nodes on cacti lower bound, Recolourable nodes on trees lower bound, Label-guided: colours fixed by a designer lower bound
- Bhagat et al. 2021 — Partitioning: Exactly \(n/k\) robots at each fixed point current best
2022
Programmable matter · Self-organising particle systems
Alignment is posed in Kedia et al. 2022
APPROX/RANDOM 2022.
In the logical view: generalisation of Compression, which was posed earlier (2016).
- Kshemkalyani et al. 2022 — Dispersion: Global communication introduced, Global communication lower bound
- Italiano et al. 2022 — Dispersion: Directed graphs current best, Directed graphs lower bound, Directed graphs, 1-hop communication current best, Directed graphs, 1-hop communication lower bound
- Gorain et al. 2022 — Dispersion: Silent agents (no communication) current best, Silent agents (no communication) lower bound, Silent agents on rings lower bound
- Bhagat & Pelc 2022b — Rendezvous: Labelled agents in infinite trees current best, Labelled agents in infinite trees lower bound, Labelled agents in infinite trees, simultaneous start current best, Labelled agents in infinite trees, simultaneous start lower bound
- Castenow et al. 2022 — Gathering: Limited visibility, FSYNC, disoriented current best, Limited visibility, FSYNC, disoriented lower bound; Near-gathering: SSYNC, limited visibility, disoriented current best, SSYNC, limited visibility, disoriented lower bound
- Feletti et al. 2022 — Uniform circle formation: Opaque robots with lights, ASYNC introduced, Opaque robots with lights, FSYNC current best
- Georgiou et al. 2022 — Evacuation: Two robots with asymmetric communication, disk current best, Two robots with asymmetric communication, disk lower bound
- Georgiou & Jang 2022 — Evacuation: Triangle, two wireless robots starting on the boundary current best, Triangle, two wireless robots starting on the boundary lower bound
- Alsaedi et al. 2022 — Mutual visibility: Fat robots, FSYNC, rigid current best, Fat robots, FSYNC, rigid lower bound
- Briones et al. 2022 — Leader election in programmable matter: Stationary, asynchronous, no orientation, no holes current best, Stationary, sequential, no orientation, no holes current best
- Darwich et al. 2022 — Exploration by luminous robots: Tori, FSYNC, perpetual, chirality, \(\varphi = 1\) current best, Tori, FSYNC, perpetual, chirality, \(\varphi = 1\) lower bound, Tori, FSYNC, perpetual, no chirality, \(\varphi = 1\) current best, Tori, FSYNC, perpetual, no chirality, \(\varphi = 1\) lower bound, Tori, FSYNC, perpetual, chirality, \(\varphi = 2\) current best, Tori, FSYNC, perpetual, chirality, \(\varphi = 2\) lower bound, Tori, FSYNC, perpetual, no chirality, \(\varphi = 2\) current best, Tori, FSYNC, perpetual, no chirality, \(\varphi = 2\) lower bound
- Kedia et al. 2022 — Alignment: Markov chain, sequential current best
- Coleman et al. 2022a — Search for a moving target: One robot, line, target moving away, \(d\) and \(u\) known current best, One robot, line, target moving away, \(d\) and \(u\) known lower bound, One robot, line, target moving toward the origin, \(d\) and \(u\) known current best, One robot, line, target moving toward the origin, \(d\) and \(u\) known lower bound, One robot, line, target moving toward the origin, speed known current best, One robot, line, target moving toward the origin, speed known lower bound, One robot, line, target moving away, \(d\) known introduced, One robot, line, target moving away, \(d\) known lower bound, One robot, line, target moving toward the origin, \(d\) known current best, One robot, line, target moving toward the origin, \(d\) known lower bound, One robot, line, target moving away, nothing known introduced, One robot, line, target moving away, nothing known lower bound, One robot, line, target moving toward the origin, nothing known current best, One robot, line, target moving toward the origin, nothing known lower bound
- Izumi et al. 2022 — Deciding graph properties by mobile agents: One agent with whiteboards and little memory current best, One agent with whiteboards and little memory lower bound
2023
Mobile agents on graphs · Computing with agents
Minimal dominating set by agents is posed in Chand et al. 2023
Introduced at ALGOSENSORS 2023.
Mobile robots in the plane · Symmetry breaking and spreading
Separation is posed in Seike & Yamauchi 2023
Introduced at SSS 2023.
Mobile agents on graphs · Exploration
Exploration of recolourable graphs is posed in Böckenhauer et al. 2023
Böckenhauer, Frei, Unger and Wehner posed exploration by an oblivious agent without port numbers that colours nodes and sees its neighbours' colours (SIROCCO 2023; arXiv January 2023), first with each node coloured once and, in a last section, with recolouring. Fixed colours chosen by a designer (2005) and the rotor-router pointer (1996, 2003) are earlier node-side precursors.
In the logical view: variant of Graph exploration by a single agent, which was posed earlier (1951).
Programmable matter · Self-organising particle systems
Scattering of particles is posed in Navarra et al. 2023
Scattering in SILBOT first appeared at AINA 2023 (Navarra, Prencipe, Bonini, Tracolli, "Scattering with programmable matter", pp. 236–247), as the journal version states; that paper was not read and its DOI was not verified, so the journal version (Navarra, Piselli, Prencipe) is cited.
- Cosson et al. 2023 — Collaborative exploration: Trees, asynchronous, complete communication introduced, Arbitrary graphs, complete communication current best
- Pattanayak et al. 2023 — Dispersion: Crash faults current best
- Moses Jr. & Redlich 2023 — Dispersion: Strong Byzantine agents current best
- Pattanayak & Pelc 2023b — Treasure hunt: Anonymous graphs with possibly infinite degrees current best, Anonymous graphs with possibly infinite degrees lower bound; Rendezvous: Labelled agents, graphs with infinite degrees current best, Labelled agents, graphs with infinite degrees lower bound
- Miller & Pelc 2023 — Rendezvous: Anonymous agents on paths and rings with labelled nodes introduced, Anonymous agents on paths and rings with labelled nodes lower bound
- Alsaedi et al. 2023c — Pattern formation: Fat robots with lights, FSYNC, randomized, no agreement current best
- Asahiro & Yamashita 2023b — Gathering: Homonymous robots, SSYNC current best, Homonymous robots, SSYNC lower bound
- Behrouz et al. 2023 — Evacuation: Disk, \(k\) wireless robots, \(f\) Byzantine current best, Disk, \(k\) face-to-face robots, \(f\) Byzantine current best
- Molla et al. 2023 — Gathering in graphs: Labelled agents current best
- Chand et al. 2023 — Minimal dominating set by agents: No knowledge introduced
- Seike & Yamauchi 2023 — Separation: ASYNC, one common axis introduced
- Navarra & Piselli 2023b — Shape formation in programmable matter: SILBOT, chirality lower bound, SILBOT, full orientation current best
- Navarra & Piselli 2023a — Coating: SILBOT, chirality, deterministic current best, SILBOT, chirality, deterministic lower bound
- Böckenhauer et al. 2023 — Exploration of recolourable graphs: Recolourable nodes, oblivious agent, any graph introduced, Once-colourable nodes, any graph current best, Once-colourable nodes, any graph lower bound, Once-colourable nodes, \(n\) known current best, Once-colourable nodes, \(n\) known lower bound, Once-colourable nodes on trees current best, Once-colourable nodes on trees lower bound
- Navarra et al. 2023 — Scattering of particles: SILBOT lower bound, SILBOT with event-driven activation current best
- Baligács et al. 2023 — Online exploration of weighted graphs: Arbitrary weighted graphs current best, Graphs excluding a fixed minor current best
2024
Mobile agents on graphs · Computing with agents
Leader election by agents is posed in Kshemkalyani et al. 2024a
Leader election in the agent-based model, with MST as an application (DISC 2024).
Mobile agents on graphs · Computing with agents
Maximal independent set by agents is posed in Pattanayak et al. 2024
Introduced at ICDCN 2024.
Mobile agents on graphs · Computing with agents
Triangle and butterfly counting by agents is posed in Chand et al. 2024
Agent-based triangle counting (arXiv 2024; IEEE Transactions on Networking 2026).
Mobile agents on graphs · Computing with agents
Minimum spanning tree by agents is posed in Kshemkalyani et al. 2024a
MST in the agent-based model appeared together with leader election (DISC 2024).
- Pattanayak & Pelc 2024 — Graph exploration by a single agent: Memoryless automaton with pebbles current best, Memoryless automaton with pebbles lower bound
- Mondal et al. 2024b — Dispersion: Dynamic rings lower bound
- Banerjee et al. 2024a — Dispersion: Crash faults on unoriented grids current best, Crash faults on oriented grids introduced
- Banerjee et al. 2024b — Dispersion: Crash faults on oriented grids current best, Weak Byzantine agents on oriented grids current best
- Das et al. 2024b — Dispersion: Silent agents (no communication) lower bound, Silent agents on rings current best, Silent agents on rings lower bound
- Hahn et al. 2024 — Pattern formation: Limited visibility current best
- Otaka et al. 2024 — Gathering: Rendezvous, external light (FCOM), SSYNC lower bound, Rendezvous, external light (FCOM), ASYNC, non-rigid lower bound, Rendezvous, external light (FCOM), ASYNC, rigid lower bound, Rendezvous, internal light (FSTA), SSYNC, non-rigid lower bound, Rendezvous, internal light (FSTA), SSYNC, rigid lower bound, Rendezvous, internal light (FSTA), ASYNC lower bound, Gathering, external light (FCOM), SSYNC, rigid lower bound, Gathering, internal light (FSTA), SSYNC, non-rigid current best, Gathering, internal light (FSTA), SSYNC, non-rigid lower bound
- Feletti et al. 2024a — Uniform circle formation: Opaque robots with lights, ASYNC current best, Opaque robots with lights, ASYNC lower bound
- Georgiou & Wang 2024 — Evacuation: Disk, priority evacuation, queen and one servant current best, Disk, priority evacuation, queen and one servant lower bound, Disk, weighted evacuation of two wireless robots current best, Disk, weighted evacuation of two wireless robots lower bound
- Kaur et al. 2024a — Black hole search: Dynamic graphs with whiteboards current best, Dynamic graphs with whiteboards lower bound
- Kshemkalyani et al. 2024a — Leader election by agents: No knowledge introduced; Maximal independent set by agents: No knowledge introduced; Minimum spanning tree by agents: Dispersed start introduced, Arbitrary start introduced
- Pattanayak et al. 2024 — Maximal independent set by agents: Knowing \(n\) and \(\Delta\) introduced, Rooted start, no knowledge current best
- Kaur et al. 2024b — Maximal independent set by agents: No knowledge current best
- Flocchini et al. 2024b — Universal pattern formation: Sequential schedulers current best, Sequential schedulers lower bound
- Bhagat et al. 2024 — Mutual visibility: Fat robots, ASYNC, rigid, one axis current best
- Flocchini et al. 2024a — Separation: ASYNC, one common axis current best, ASYNC, one common axis lower bound
- Chand et al. 2024 — Triangle and butterfly counting by agents: Triangle counting current best
- Chalopin et al. 2024b — Leader election in programmable matter: Stationary, common direction, no chirality current best, Stationary, common direction, no chirality lower bound
- Chalopin et al. 2024a — Leader election in programmable matter: Stationary, fair scheduler, no orientation, no holes current best
- Ooshita et al. 2024 — Exploration by luminous robots: Rings, FSYNC, perpetual, up to \(f\) crashes current best, Rings, FSYNC, perpetual, up to \(f\) crashes lower bound, Rings, ASYNC, perpetual, up to \(f\) crashes, \(\varphi = 1\) current best, Rings, ASYNC, perpetual, up to \(f\) crashes, \(\varphi = 1\) lower bound, Rings, ASYNC, perpetual, up to \(f\) crashes, \(\varphi \ge 2\) current best, Rings, ASYNC, perpetual, up to \(f\) crashes, \(\varphi \ge 2\) lower bound
- Bramas et al. 2024 — Exploration by luminous robots: Grids, ASYNC, perpetual, chirality, \(\varphi = 1\) (exclusive) lower bound, Grids, ASYNC, perpetual, chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, perpetual, no chirality, \(\varphi = 2\) current best, Grids, ASYNC, perpetual, no chirality, \(\varphi = 2\) lower bound, Grids, ASYNC, perpetual, no chirality, \(\varphi = 3\) current best
- Hinnenthal et al. 2024 — Shape formation by hybrid programmable matter: Three-dimensional current best
- Coleman et al. 2024 — Search for a moving target: One robot, line, target moving away, \(d\) known current best, One robot, line, target moving away, \(d\) known lower bound, One robot, line, target moving away, nothing known current best, One robot, line, target moving away, nothing known lower bound
- Bhagat & Pelc 2024 — Collision-free exploration: Anonymous graphs, nothing known lower bound, Two agents, anonymous graphs, vision of radius 2 introduced, Two agents, anonymous graphs, vision of radius 1 lower bound
- Das et al. 2024a — Collision-free exploration: Two agents sensing presence, no pebbles lower bound, Two agents sensing presence, with coloured pebbles current best, Two agents sensing presence, with coloured pebbles lower bound, Two agents sensing presence, with coloured pebbles, bipartite graphs current best, Two agents sensing presence, with coloured pebbles, bipartite graphs lower bound
2025
Mobile robots in the plane · Formation problems
Universal pattern formation is posed in Flocchini et al. 2024b
Introduced at SIROCCO 2025.
In the logical view: strengthening of Pattern formation, which was posed earlier (1999).
Mobile agents on graphs · Computing with agents
BFS tree by agents is posed in Chand et al. 2025b
BFS without root knowledge in the agent-based model (SSS 2025).
- Cosson & Massoulié 2025 — Collaborative exploration: Trees, asynchronous, complete communication lower bound, Trees, asynchronous, whiteboards only current best
- Kshemkalyani et al. 2025a — Collaborative exploration: Anonymous graphs with \(k = n\) agents current best; Dispersion: Arbitrary graph, arbitrary initial configuration current best, Rooted initial configuration current best, Global communication current best, Rings and paths current best, Trees current best
- Pattanayak et al. 2025 — Dispersion: Asynchronous agents current best
- Bourreau et al. 2025 — Rendezvous: Anonymous agents on paths and rings with labelled nodes current best
- Bonnet et al. 2025a — Gathering: Self-stabilizing gathering, full lights, SSYNC, strong multiplicity detection current best
- Di Luna et al. 2025 — Black hole search: Byzantine companions, with a map current best, Byzantine companions, whiteboards, no map current best
- Bonnet et al. 2025b — Black hole search: Eventually emerging black hole, synchronous agents, oriented ring current best, Eventually emerging black hole, synchronous agents, oriented ring lower bound, Eventually emerging black hole, asynchronous agents, oriented ring current best, Eventually emerging black hole, asynchronous agents, oriented ring lower bound, Eventually emerging black hole, synchronous agents, arbitrary graphs lower bound
- Kaur et al. 2025b — Black hole search: Eventually emerging black hole, synchronous agents, arbitrary graphs current best
- Devismes et al. 2025 — Gathering in graphs: Homonymous agents current best
- Hirose et al. 2025 — Gathering in graphs: Weakly Byzantine agents lower bound
- Chand & Molla 2025 — Leader election by agents: No knowledge current best; Minimal dominating set by agents: No knowledge current best
- Kshemkalyani et al. 2025c — Leader election by agents: Knowing \(n\) and \(\Delta\) current best; Maximal independent set by agents: Knowing \(n\) and \(\Delta\) current best
- Feletti et al. 2025 — Pattern sequences: Luminous robots, sequential scheduler (universal dancing) current best, Luminous robots, sequential scheduler (universal dancing) lower bound
- Pyati et al. 2025 — Separation: Opaque robots, SSYNC current best
- Chand et al. 2025a — Triangle and butterfly counting by agents: Butterfly counting in bipartite graphs current best
- Chand et al. 2025b — Minimum spanning tree by agents: Dispersed start current best; BFS tree by agents: Dispersed start, root unknown current best
- Kshemkalyani et al. 2025b — Minimum spanning tree by agents: Arbitrary start current best
- Chalopin et al. 2025 — Leader election in programmable matter: Oblivious, common compass, holes allowed current best
- Bar et al. 2025 — Network decontamination: Dynamic graphs, monotone strategies current best, Dynamic graphs, monotone strategies lower bound
- Das et al. 2025 — Exploration by luminous robots: Triangular grids, FSYNC, perpetual, no chirality, \(\varphi = 1\) current best, Triangular grids, FSYNC, perpetual, no chirality, \(\varphi = 1\) lower bound, Triangular grids, FSYNC, perpetual, chirality, \(\varphi = 2\) current best, Triangular grids, FSYNC, perpetual, chirality, \(\varphi = 2\) lower bound
- Takahashi et al. 2025 — Exploration of recolourable graphs: Recolourable nodes, oblivious agent, any graph current best
- Gehnen et al. 2025 — Online exploration of weighted graphs: Known graph, weight estimates current best, Known graph, weight estimates lower bound, Complete graphs, uniform weight estimates current best, Complete graphs, uniform weight estimates lower bound
- Navarra & Piselli 2025 — Gathering by oblivious robots on graphs: Rings, round robin, no multiplicity detection current best, Rings, round robin, no multiplicity detection lower bound, Rings, round robin, one robot per node at the start current best, Rings, round robin, one robot per node at the start lower bound, Rings, sequential scheduler, no multiplicity detection lower bound
- Cicerone et al. 2025c — Gathering by oblivious robots on graphs: Graphs that are not vertex-transitive, round robin current best, Graphs that are not vertex-transitive, round robin lower bound
- Cicerone et al. 2025a — Gathering by oblivious robots on graphs: Hypercubes, round robin current best, Hypercubes, round robin lower bound, Infinite grid, round robin current best, Infinite grid, round robin lower bound, Complete graphs, round robin lower bound
- Moses Jr. et al. 2025 — Broadcast by agents in dynamic graphs: Dynamic graph, any topology lower bound
- Jawhar & Kranakis 2025b — Search for a moving target: Line, two face-to-face robots, away, \(d\) and \(u\) known current best, Line, two face-to-face robots, away, \(d\) and \(u\) known lower bound, Line, two face-to-face robots, toward, \(d\) and \(u\) known current best, Line, two face-to-face robots, toward, \(d\) and \(u\) known lower bound, Line, two face-to-face robots, away, \(u\) known current best, Line, two face-to-face robots, away, \(u\) known lower bound, Line, two face-to-face robots, toward, \(u\) known current best, Line, two face-to-face robots, toward, \(u\) known lower bound, Line, two face-to-face robots, away, \(d\) known current best, Line, two face-to-face robots, away, \(d\) known lower bound, Line, two face-to-face robots, toward, \(d\) known current best, Line, two face-to-face robots, toward, \(d\) known lower bound, Line, two face-to-face robots, away, nothing known current best, Line, two face-to-face robots, toward, nothing known current best, Line, two face-to-face robots, toward, nothing known lower bound
- Jawhar & Kranakis 2025a — Search for a moving target: Line, a sender and a receiver, away, \(u\) known current best, Line, a sender and a receiver, toward, \(u\) known current best, Line, a sender and a receiver, away, \(d\) known current best, Line, a sender and a receiver, away, \(d\) known lower bound, Line, a sender and a receiver, toward, \(d\) known current best, Line, a sender and a receiver, toward, \(d\) known lower bound, Line, a sender and a receiver, away, nothing known current best, Line, a sender and a receiver, toward, nothing known current best, Line, a sender and a receiver, toward, nothing known lower bound
2026
Search in geometric domains · Search, evacuation and patrolling
Search with segment visibility is posed in Kranakis 2026
Kranakis introduced segment visibility in a preprint of November 2026 Kranakis 2026; the earlier uses this note rests on are the author's own account.
- Carnevale 2026 — Graph exploration by a single agent: Temporal graphs, schedule known lower bound
- Sudo et al. 2026 — Graph exploration by a single agent: \(T\)-interval-connected graphs, labelled nodes current best, \(T\)-interval-connected graphs, labelled nodes lower bound
- Cosson & Massoulié 2026 — Collaborative exploration: Trees, complete communication current best, Trees, asynchronous, complete communication current best
- Mutzari et al. 2026 — Collaborative exploration: Connected team, labelled graphs, shared knowledge current best
- Kumar et al. 2026a — Dispersion: Oriented grids current best
- Xin 2026 — Treasure hunt: Anonymous finite graphs current best
- Ayoubi et al. 2026 — Treasure hunt: Dynamic graphs, connected at every step lower bound
- Wada et al. 2026 — Gathering: Rendezvous, external light (FCOM), ASYNC, rigid current best, Rendezvous, internal light (FSTA), SSYNC, rigid current best
- Ma & Yin 2026 — Linear search (cow path): One randomized robot on \(m\) rays lower bound
- Shukla et al. 2026a — Mutual visibility: Lights, mobility faults, SSYNC, non-rigid current best
- Warner & Scheideler 2026a — Leader election in programmable matter: Stationary, randomized, sequential, holes allowed current best
- Hiraoka et al. 2026 — Exploration of recolourable graphs: Recolourable nodes, oblivious agent, any graph lower bound, Recolourable nodes on cacti current best, Recolourable nodes on cacti lower bound, Recolourable nodes on trees current best, Recolourable nodes on trees lower bound
- Kranakis 2026 — Search with segment visibility: Two robots, unknown distance current best, Two robots, unknown distance lower bound, Two robots, known distance current best, Two robots, known distance lower bound, \(k \ge 3\) robots, unknown distance current best, \(k \ge 3\) robots, unknown distance lower bound, \(k \ge 3\) robots, known distance current best, \(k \ge 3\) robots, known distance lower bound
- Baligács 2026 — Online exploration of weighted graphs: Arbitrary weighted graphs lower bound, Graphs excluding a fixed minor lower bound, Planar graphs lower bound
- Baligács et al. 2026 — Online exploration of weighted graphs: Weighted cycles, randomized agent current best, Weighted cycles, randomized agent lower bound
- Moses Jr. et al. 2026 — Broadcast by agents in dynamic graphs: Static graph lower bound, Dynamic graph, any topology lower bound
- Jawhar & Kranakis 2026 — Search for a moving target: \(m\) rays, two face-to-face robots, away, \(u\) known current best, \(m\) rays, two face-to-face robots, away, \(d\) known current best, \(m\) rays, two face-to-face robots, away, nothing known current best, \(m\) rays, a sender and a receiver, away, \(u\) known current best, \(m\) rays, a sender and a receiver, away, \(u\) known lower bound, \(m\) rays, a sender and a receiver, away, \(d\) known current best, \(m\) rays, a sender and a receiver, away, \(d\) known lower bound, \(m\) rays, a sender and a receiver, away, nothing known current best
- Papin 2026 — Collision-free exploration: Two agents, anonymous graphs, vision of radius 2 current best