Map construction

Map construction began as a single-robot problem: Dudek, Jenkin, Milios and Wilkes framed robotic exploration as building a graph, with a robot carrying one or more markers Dudek et al. 1991. Das, Flocchini, Kutten, Nayak and Santoro posed the distributed version: \(k\) identical agents, initially dispersed among the nodes and communicating through whiteboards, must each build an identically labelled map Das et al. 2007 (abstract read). They note that it "is much more difficult than exploration by a single agent, because it involves achieving cooperation among multiple agents", and that it is deterministically unsolvable in some cases Das et al. 2007. The axis separates the single agent, whose difficulty is recognising nodes it has already seen, from the team, which must in addition break the symmetry between identical agents.

In an anonymous graph an agent that cannot mark nodes cannot tell a revisited node from a new one by looking at it, so it needs information from outside before it can commit to a map. The standard information is an upper bound on \(n\), which fixes how long a universal sequence must be followed; Chalopin, Das and Kosowski state the trade-off exactly: "in the model where no vertices of the graph are marked, for the task of map construction to be feasible, the agents must know some bound \(n\) on the number of nodes of the graph and some bound \(d\le n\) on its degree", and with these bounds they build the map by following universal exploration sequences; without any knowledge they instead assume that the starting node is marked, and then build the map in \(O(n^3\Delta)\) moves with \(O(n\Delta\log n)\) bits of memory Chalopin et al. 2010. The clearest measurement of what the bound is worth comes from directed graphs: Bender et al. map any strongly connected digraph with one pebble when an upper bound on \(n\) is known, while without it \(\Theta(\log\log n)\) pebbles are necessary and sufficient Bender et al. 2002.

A marker lets a robot recognise one chosen node, which is exactly what an anonymous graph withholds. Dudek, Jenkin, Milios and Wilkes introduced the robot that carries \(k\ge1\) distinct markers and builds the graph as it explores; they show that without markers the task is unsolvable in general (regular graphs of the same degree look alike everywhere) and that their algorithm makes at most \((5+2/k)mn-3n^2\) plus lower-order moves, that is \(O(mn)\subseteq O(n^2\Delta)\) Dudek et al. 1991. Bender, Fernández, Ron, Sahai and Vadhan showed in "The power of a pebble" that one pebble also suffices to map a directed graph in polynomial time when an upper bound on \(n\) is known Bender et al. 2002. The axis keeps carried markers apart from whiteboards because a marker is a single movable bit, while a whiteboard stores information permanently at every node.

Whiteboards, a small memory at every node that visiting agents read and write in mutual exclusion, are the standard communication device in the work of Flocchini, Santoro and coauthors on asynchronous agents Dobrev et al. 2006 Flocchini et al. 2012. Das, Flocchini, Kutten, Nayak and Santoro used them for map construction by \(k\) identical agents, which communicate only through these "small public bulletin boards available at each node" Das et al. 2007 (abstract read). Flocchini, Ilcinkas and Santoro note that whiteboards also "allow to break symmetry among identical agents" Flocchini et al. 2012, which is what a team of identical agents needs in order to agree on one labelled map.