License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.14
URN: urn:nbn:de:0030-drops-191409
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19140/
Cosson, Romain ;
Massoulié, Laurent ;
Viennot, Laurent
Efficient Collaborative Tree Exploration with Breadth-First Depth-Next
Abstract
We study the problem of collaborative tree exploration introduced by Fraigniaud, Gasieniec, Kowalski, and Pelc [Pierre Fraigniaud et al., 2006] where a team of k agents is tasked to collectively go through all the edges of an unknown tree as fast as possible and return to the root. Denoting by n the total number of nodes and by D the tree depth, the ?(n/log(k)+D) algorithm of [Pierre Fraigniaud et al., 2006] achieves a ?(k/log(k)) competitive ratio with respect to the cost of offline exploration which is at least max{{2n/k,2D}}. Brass, Cabrera-Mora, Gasparri, and Xiao [Peter Brass et al., 2011] study an alternative performance criterion, the competitive overhead with respect to the cost of offline exploration, with their 2n/k+?((D+k)^k) guarantee. In this paper, we introduce "Breadth-First Depth-Next" (BFDN), a novel and simple algorithm that performs collaborative tree exploration in 2n/k+?(D²log(k)) rounds, thus outperforming [Peter Brass et al., 2011] for all values of (n,D,k) and being order-optimal for trees of depth D = o(√n). Our analysis relies on a two-player game reflecting a problem of online resource allocation that could be of independent interest. We extend the guarantees of BFDN to: scenarios with limited memory and communication, adversarial setups where robots can be blocked, and exploration of classes of non-tree graphs. Finally, we provide a recursive version of BFDN with a runtime of ?_?(n/k^{1/?}+log(k) D^{1+1/?}) for parameter ? ≥ 1, thereby improving performance for trees with large depth.
BibTeX - Entry
@InProceedings{cosson_et_al:LIPIcs.DISC.2023.14,
author = {Cosson, Romain and Massouli\'{e}, Laurent and Viennot, Laurent},
title = {{Efficient Collaborative Tree Exploration with Breadth-First Depth-Next}},
booktitle = {37th International Symposium on Distributed Computing (DISC 2023)},
pages = {14:1--14:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-301-0},
ISSN = {1868-8969},
year = {2023},
volume = {281},
editor = {Oshman, Rotem},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19140},
URN = {urn:nbn:de:0030-drops-191409},
doi = {10.4230/LIPIcs.DISC.2023.14},
annote = {Keywords: collaborative exploration, online algorithms, trees, adversarial game, competitive analysis, robot swarms}
}
|
Keywords: |
|
collaborative exploration, online algorithms, trees, adversarial game, competitive analysis, robot swarms |
|
Collection: |
|
37th International Symposium on Distributed Computing (DISC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.10.2023 |
