Collective tree exploration

Authors:
Publisher website
Google Scholar
Abstract
Ann‐node tree has to be explored bykmobile agents (robots), starting at its root. Every edge of the tree must be traversed by at least one robot, and exploration must be completed as fast as possible. Even when the tree is known in advance, scheduling optimal collective exploration turns out to be NP‐hard. We investigate the problem of how communication among robots influences the time for exploring unknown trees. To this end, we consider two scenarios. In the first scenario, robots can communicate by writing at the currently visited node previously acquired information, and reading information available at this node. In the second scenario robots are oblivious of one another, and each of them knows only the part of the tree previously explored by itself. We show that this difference of communication capability significantly influences time of collective exploration. Under the first scenario, we construct an exploration algorithm whose running time for any tree is onlyO(k/ logk) larger than the optimal exploration time with full knowledge of the tree, while under the second scenario we prove that every algorithm works in timeΩ(k) larger than optimal, for some trees. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(3), 166–177 2006

This publication has 16 references indexed in Scilit: