A Recursive Approach to Multi-robot Exploration of Trees

The multi-robot exploration problem is to explore an unknown graph of size n and depth d with k robots starting from the same node. For known graphs a traversal of all nodes takes at most O(d + n/k) steps. The ratio between the time until cooperating robots explore an unknown graph and the optimal traversal of a known graph is called the competitive exploration time ratio. It is known that for any algorithm this ratio is at least Omega ((log k)/log log k). For k <= n robots the best algorithm known so far achieves a competitive time ratio of O(k/log k). Here, we improve this bound for trees with bounded depth or a minimum number of robots. Starting from a simple O(d)-competitive algorithm, called Yo-yo, we recursively improve it by the Yo-star algorithm, which for any 0 < alpha < 1 transforms a g(d, k)-competitive algorithm into a O((g(d(alpha), k) log k + d(1-alpha))(log k + log n))-competitive algorithm. So, we achieve a competitive bound of O (2(O(root(log d)(log log k)))(log k)(log k + log n)). This improves the best known bounds for trees of depth d, whenever the number of robots is at least k = 2(omega(root(log d)(log log d))) and n = 2(O(2 root log d)).