Map construction of unknown graphs by multiple agents

• DOI: 10.1016/j.tcs.2007.05.011
• Publication Date: 2007-05-19T20:24:31Z
• Authors: Shantanu Das; Paola Flocchini; Shay Kutten; Amiya Nayak; Nicola Santoro
• Keywords: Rendezvous; Traverse

AbstractWe consider a distributed version of the graph exploration and mapping problem where a mobile agent has to traverse the edges of an unlabelled (i.e., anonymous) graph and return to its starting point, building a map of the graph in the process. In our case, instead of a single agent, there are k identical (i.e., mutually indistinguishable) agents initially dispersed among the n nodes of the graph. The agents can communicate by writing to the small public bulletin boards available at each node. The objective is for each agent to build an identically labelled map of the graph; we call this the Labelled Map Construction problem. This problem is much more difficult than exploration by a single agent, because it involves achieving cooperation among multiple agents. In fact, this problem is deterministically unsolvable in some cases. We present deterministic algorithms that successfully and efficiently solve the problem under the condition that the values of n and k are co-prime with each other. We also show how the problem of Labelled Map Construction is related to other problems like leader election and rendezvous of agents.