Power of Communication in Cooperative Exploration of Graphs

Abstract

We consider the task of exploring finite anonymous graphs by teams of mobile agents (modeled as finite automata) that have no a priori knowledge of the topology of the graph or of its size. Each edge has to be traversed by at least one agent. Information exchange between agents is crucial for performing such cooperative exploration. Our goal is to compare the strength of two communication scenarios from the point of view of feasibility of exploration: one is the local model in which agents can exchange information only when they meet at a node of the graph, and the other is the global model in which all agents can exchange all information available to them at each step of the exploration. We show that the global model is strictly stronger than the local model: there exists a family of graphs that cannot be explored by any finite team of agents in the local model but can be explored by just two agents in the global model. We also show that three agents are strictly stronger than two agents in the global model but no team of three agents can explore all graphs.