×

Collective tree exploration. (English) Zbl 1196.68171

Farach-Colton, Martin (ed.), LATIN 2004: Theoretical informatics. 6th Latin American symposium, Buenos Aires, Argentina, April 5–8, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21258-2/pbk). Lecture Notes in Computer Science 2976, 141-151 (2004).
Summary: An \(n\)-node tree has to be explored by \(k\) mobile agents (robots), starting in 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 distributed collective exploration of unknown trees. Not surprisingly, communication between robots influences the time of exploration. Our main communication scenario is the following: robots can communicate by writing at the currently visited node previously acquired information, and reading information available at this node. We construct an exploration algorithm whose running time for any tree is only \(O(k/\log k)\) larger than optimal exploration time with full knowledge of the tree. (We say that the algorithm has overhead \(O(k/\log k)\)). On the other hand we show that, in order to get overhead sublinear in the number of robots, some communication is necessary. Indeed, we prove that if robots cannot communicate at all, then every distributed exploration algorithm works in time \(\Omega (k)\) larger than optimal exploration time with full knowledge, for some trees.
For the entire collection see [Zbl 1048.68003].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T40 Artificial intelligence for robotics
68W15 Distributed algorithms
PDFBibTeX XMLCite
Full Text: DOI