Competitive Connected Multi-robot Exploration of Unknown Graphs

1 Introduction

Multi-robot exploration and coverage are central problems in robotics, planning, and multi-agent systems. In applications such as search-and-rescue, environmental monitoring, and infrastructure inspection, a team of robots must visit every location in an environment, naturally modeled as a graph whose vertices correspond to locations and edges to traversable paths. When the graph is known in advance, the goal is to schedule robot motion so as to minimize the number of rounds needed to visit all vertices. This problem is called multi-robot, or collective, graph coverage. Notably, the problem is NP-hard even for trees [Fraigniaud et al., 2006].

In many settings, however, the graph is unknown, so robots must discover and cover it online. Upon first visiting a vertex, its incident edges are revealed. This is Collective Graph Exploration (CGE) [Fraigniaud et al., 2006]. In this setting, the central question is: what is the additional cost of online discovery, beyond pure coverage? This is captured by the competitive ratio, also known as overhead tween online exploration performance and an optimal offline coverage [Dessmark and Pelc, 2004; Fraigniaud et al., 2006]. Existing competitive strategies for CGE crucially rely on the ability of robots to disperse arbitrarily throughout the graph. The best existing algorithm for this problem achieves a competitive ratio of O(k/exp(√log2 logk)) [Cosson, 2024], improving on the previous best algorithm of O(k/ logk). In contrast, the best known lower bound on the competitive ratio is Ω(log k/ log log k) [Disser et al., 2020; Dynia et al., 2007].

ConnectedCollectiveGraphExploration (CCGE). Standard graph coverage and exploration models allow arbitrary dispersion, usually assuming global communication: robots share information regardless of their positions. In many applications, however, robots must remain in close proximity for communication, safety, supervision, or cooperative operation. Examples include rescue teams, swarms relying on multi-hop connectivity, or equipment transport teams. Such requirements significantly complicate parallel exploration, as robots cannot independently explore distant regions.

We therefore study Connected Collective Graph Exploration (CCGE), a constrained variant of CGE in which occupied vertices must induce a connected subgraph at all times. Connectivity constraints significantly restrict robot mobility and coordination, making the exploration task qualitatively more challenging. Such constraints appear in related settings, e.g. multi-robot connected graph coverage (MRCGC) [Sinay et al., 2017; Mutzari et al., 2024], tethered robot Coverage Path Planning (CPP) [Mechsy et al., 2017], and Multi-Agent Path Finding (MAPF) under continuous connectivity [Dutta et al., 2019]. However, to the best of our knowledge, connectivity constraints have not been studied in the context of competitive online graph exploration.

Unlike standard CGE with global communication, connectivity allows us to replace the long-distance communication with local message passing through the connected robot team. Since the robots remain connected, even a communication radius of k ≪ n suffices, and in fact even a sublinear radius suffices in our proposed algorithm. Moreover, within O(k) communication rounds, or the diameter of the occupied subgraph, all robots can communicate by forwarding messages between neighboring robots. Moreover, although we present centralized algorithms, they can be implemented distributively: robots may exchange information when gathering at a node, and can use local randomness to distribute among unexplored regions.

Our Contributions. We introduce CCGE, a new exploration model in which robots explore an unknown graph while remaining connected. Unlike prior work on collective exploration, our model prohibits arbitrary dispersion of robots and rules out most existing competitive strategies. We then present DFS-BGS, and analyze it theoretically and experimentally. For k ≥ n, it achieves competitive ratio O(min(√D, k1/3 ) log(k)), where D is the radius of the graph. Experimentally, we compare the online DFS-BGS to COCTA [Sinay et al., 2017], the state-of-the-art offline algorithm. On random graphs and over a wide range of parameters, as well as real hotel floor plans from [Mutzari et al., 2024], DFS-BGS exhibits only a small slowdown relative to COCTA, even for large values of k and n.

This shows that sublinear-overhead exploration is possible under connectivity constraints, narrowing the gap between theoretical exploration models and practical deployments.

Organization. In Section 3 we present our problem CCGE. We then gradually motivate our exploration algorithm as follows. In Section 4.1 we derive Picaboo, an exploration algorithm for bounded radius, in Section 4.2 we derive BGS, an exploration algorithm under bounded graph size and in Section 5 we derive DFS-BGS, an exploration algorithm for CCGE under no restrictions. Finally, Section 6 exhibits our experimental comparison with COCTA on a wide parameter range and families of trees.

2 RelatedWork

Multi-robot exploration and coverage have been studied extensively in robotics and multi-agent systems. We review the most relevant lines of work and clarify how they differ from our setting.

The study of online multi-robot graph exploration was initiated by [Fraigniaud et al., 2006], who introduced Collective Tree Exploration (CTE), later generalized to graphs (CGE) [Dereniowski et al., 2015]. In this model, robots explore an initially unknown graph under synchronous rounds and global communication. The objective is to minimize exploration time, typically analyzed via overhead, the ratio between the online algorithm and an optimal offline traversal. Even without connectivity constraints, minimizing exploration time is NP-hard, and much of the literature focuses on competitive guarantees and approximation algorithms. The work of [Cabrera-Mora and Xiao, 2012] studied variants with additional traversal restrictions and decentralized coordination using landmarks, but without explicit proximity constraints between robots. Subsequent works studied exploration in the regime of many robots, including the case k ≥ n [Dereniowski et al., 2015].

However, these works allow robots to disperse arbitrarily in the graph, without connectivity or proximity constraints. Connectivity-constrained multi-robot coverage was introduced by [Sinay et al., 2017] for offline coverage of trees; due to NP-hardness, they analyzed speedup relative to a single robot. This work is limited to trees, does not compare against optimal multi-robot solutions, and does not address online exploration. [Charrier et al., 2020] studied coverage and multi-agent path finding with separate movement and communication edges, requiring connectivity to a base station, but focused on PSPACE-completeness results without algorithmic guarantees. More recently, [Mutzari et al., 2024] generalized this framework to heterogeneous robots under broad proximity and movement constraints, providing FPT and PTAS offline algorithms for bounded-treewidth graphs. Overall, these works assume a known environment and focus on offline planning rather than online exploration.

In robotics, multi-robot exploration is often studied in the context of mapping and model reconstruction, see the survey by [Almadhoun et al., 2019]. [Brass et al., 2011] studied exploration of unknown graphs by multiple robots, but without connectivity constraints. [Banfi et al., 2016] allowed robots to disconnect from the base station for arbitrarily long periods, reconnecting only to transmit information.

Another related line of work is Multi-Robot Coverage Path Planning (mCPP), which studies coverage of continuous environments. Works such as [Tang et al., 2021; Lu et al., 2023] consider physical constraints but do not enforce connectivity between robots. [Jensen and Gini, 2018] compared coverage algorithms under varying communication assumptions, while [Mechsy et al., 2017] studied tethered robots with bounded cable length. Connectivity constraints are also central in swarm robotics. [Panerati et al., 2018] and [Siligardi et al., 2019] studied maintaining swarm connectivity during area coverage. More recent work considers UAV swarms with limited perception or repeated coverage in dynamic environments. However, swarmmodels typically rely on local rules, limited communication, and asynchronous operation, and do not allow centralized coordination or global planning.

To the best of our knowledge, no prior work provides competitive-overhead guarantees for online multi-robot exploration of unknown graphs under strict connectivity constraints. Our work fills this gap by providing the first sublinear-overhead exploration algorithms in this setting.

3 Model and ProblemDefinition

Consider a rooted, connected, undirected graph ⟨G, r⟩ where r ∈ V (G), parameterized by its radius Dr(G) = maxv∈V (G) d(r, v) < ∞, where d(u, v) is the shortest path length between u, v ∈ V (G). An edge e = {u, v} ∈ E(G) exists if a robot can move directly from u to v.

A configuration of robots x ∶ V (G) → N specifies how many robots occupy each vertex. In a connected configuration, the set of occupied vertices Occupied(x) ∶= {v ∈ V (G) ∶ x(v) > 0} forms a connected induced subgraph of G. A simple interpretation is line-of-sight. A transition is a pair of connected configurations (x,x′ ), where x′ can be reached from x by moving each robot along at most one incident edge. In particular, multiple robots are allowed to occupy a vertex simultaneously or pass through a common edge.

A t-traversal of G is a sequence of t +1 connected configurations X = (x0 , . . . ,xt ), which form t sequential transitions, where each vertex v ∈ V (G) is visited at least once by at least one robot. In addition, in x0 all robots are at the root r.

In CGE, a team of k robots is initially located at the root r of an unknown graph G with edges of unit length. When a robot visits a node v ∈ V (G) for the first time, the whole team becomes aware of its degree and of all unexplored edges adjacent to v, called dangling edges. When there are no more dangling edges, the entire team knows that all edges have been explored, and meets at the root to declare termination of exploration. The runtime of an exploration algorithm E is defined on a graph G as the number of rounds before termination and is denoted by Runtime(E, k,G). By extension, for any two integers n ≥ D, Runtime(E, k,n,D) is the maximum number of rounds required before termination on any graph with n nodes and radius D. We refer to [Cosson et al., 2023] for more details. Additionally, we define Runtime∗ (k,G) as the minimal number of rounds required before termination if G is known in advance. The overhead of an exploration algorithm E is then defined as Q(E, k) ∶= supG Runtime(E,k,G) Runtime∗ (k,G) . With slight abuse of notation, Q(E, k,D) can be defined by taking the supremum over graphs of radius D, and by definition, Q(E, k) = supD Q(E , k, D).

The Connected Collective Graph Exploration (CCGE) Problem is defined similarly. Given a rooted graph ⟨G, r⟩, a number of robots k ∈ N initially located at r ∈ V , find an exploration algorithm E with minimal overhead. The difference is that throughout the exploration, all configurations must be connected, and Runtime∗ (k, G) is the minimal number of rounds required before termination if G is known in advance and robots must stay connected.

Notably, our approach is limited to undirected graphs, allowing robots to go back, regroup, and redistribute. Additionally, a connected team of robots is less effective in the case of sparse and deep graphs, as the connectivity constraint hinders effective coverage of the graph, even if the graph is known in advance.

4 CCGE with k ≥ n Robots

For the case of k ≥ n, there are enough robots to occupy the entire graph simultaneously, and therefore an optimal vertex traversal will take precisely D = radius⟨G, r⟩ rounds. As for edge traversal, it would still take at least D rounds as all vertices will be visited.

However, in the exploration setting, D is unknown. To address this, we derive an exploration algorithm for the case k ≥ n in two steps. In Section 4.1 we derive Picaboo, an exploration algorithm parameterized by a bound ∆ on the radius of the unknown graph, with an overhead ∆ in case ∆ > D. In the following Section 4.2, we derive Baby-Giant Step, which uses Picaboo as a subroutine, and applies to any graph of size n ≤ k. It achieves an overhead of ˜O(√D), which can be ˜O(√k) for graphs of radius O(k). We then utilize an early stopping technique to get the overhead complexity down to ˜O(k1/3 ).

Algorithm 1 Picaboo(r, k, ∆)

Input: A starting node r ∈ V (G) of an unknown graph; k ∈ N the number of robots;

∆ ∈ N an upper bound on radius(G);

Output: A connected partial traversal X of the graph with k robots; Initialize X with a single configuration with all robots at r;

for i = 1, . . . ,∆ do

Let Gi be the subgraph of size ni = ∣V (Gi)∣ discovered so far;

Let Ti be a spanning tree of Gi of depth i;

Pica: Send to each vertex in v ∈ V (Ti) kv robots, the number of vertices in the subtree of Ti rooted at v. If there are any robots remaining, divide them equally among the leaves of ⟨Ti, r⟩, and update X ;

Boo: Return with all robots back to the root r, and update X; return X; // Either T is traversed or max depth ∆ is reached

4.1 Bounded Radius

Essentially, the idea behind Picaboo (Algorithm 1) is to explore the graph in BFS, keeping connectivity by occupying vertices from previous layers with single robots. The problem is that since the graph is unknown, robots cannot know how to distribute the ith layer in order to effectively continue to the i + 1th layer. The algorithm therefore works iteratively, where in the ith iteration the subgraph of radius i - 1 from r is visited, and so the subgraph of radius i is known. To this end, the algorithm chooses a spanning tree for the subgraph of radius i of depth i, and sends to each discovered vertex the size of its discovered subtree number of robots. When the robots reach radius i, they all go back to the root r in i more rounds. At the end of the ith iteration, which therefore takes exactly 2i rounds, all vertices in the subgraph of radius i are visited, and the subgraph of radius i +1 is observed, allowing advancement to the next iteration.

Figure 1 demonstrates Picaboo on a toy graph. k = 30 robots start at the root r marked in red in 1a, where dangling edges are colored green, and their incident unvisited vertices are colored in gray. In the first pica step, the robots are divided equally among the gray vertices 1b, after which the subgraph of radius two is observed. Then comes boo, where robots then gather back at the root 1c. We mark edges that are not part of the spanning tree in dashed gray, and Picaboo ignores them throughout the exploration. Then in the next two rounds 1d,1e, pica is used to occupy the layer at radius two from r. Exploration ends after reaching D(G) = 4 in 1j and gathering at r. Overall, the exploration time of this algorithm is therefore quadratic in the graph radius, and so its overhead is Θ(D). This can be a prohibitive Θ(k) overhead in case D = Θ(k). To bound the overhead, we parameterize the algorithm with a parameter ∆ and let it stop if it reaches a radius of ∆ from r. The first termination condition ensures the algorithm has an overhead at most ∆, and the second ensures there are enough robots to cover the tree in a single connected configuration. As a result, the algorithm may fail to explore the tree, but if successful, the overhead is bounded by ∆. This parameterized algorithm will serve as a subroutine for the unbounded-radius case.

Lemma 1. Let n, k,∆ ∈ N and let ⟨G, r⟩ be a tree of radius

(f) Gather in 2 rounds.

(g) Spread to layer #3. (h) Reach radius 3 from r. (i) Gather in 3 rounds.

(j) Reach radius 4 from r.

Figure 1: A demonstration of Picaboo with k = 30 robots on a toy graph with n = 26 vertices and 33 edges.

Algorithm 2 BabyGiantStep (BGS)(r, k, ∆)

Input: The root r ∈ V (G) of a graph of size n = ∣V (G)∣ ≤ k; k ∈ N the number of robots; ∆ ∈ N a parameter for baby-steps; Output: A connected traversal X of G with k robots; for j = 0, . . . , 4⌈k/∆⌉ + log4/3 (k) + 1 do Let Gj be the subgraph of size nj = ∣V (Gj)∣ discovered so far; Let Tj be a spanning tree of Gj; Let Lj = L(Tj) be its set of ∣Lj∣ = ℓj leaves; repeat ⌈log2 (k)⌉ times: Giant-step: Group all robots at r, and then send one robot to every interior vertex of Tj , and divide the rest of the k-nj + ℓj robots equally among the leaves Lj (in Round-Robin), and update X ; Baby-step: Call Picaboo(v, ⋅,∆) in parallel on all leaves v ∈ Lj , ignoring backward edges to V (Gj) ∖ {v}, and update X ; return X;

group. This results with complete exploration of the shallow subtree. Then in 2e a second giant step moves all robots to the chain side of the graph, where in 2f a final Picaboo is executed to fully explore the tree, and gather at the root 2g.

In what follows, we formally analyze the overhead of the BabyGiantStep (BGS) algorithm (Algorithm 2).

Proof. Consider some iteration j, that starts with a discovered subgraph Gj . The first baby-step on each leaf v ∈ L(Gj) may result in three potential outcomes:

1. Picaboo succeeds, and so the connected component of v in G∖Gj is fully explored.
2. Picaboo fails, and so the subgraph of radius ∆ from v contains more vertices than the number of assigned robots. In this case, a subgraph of size equal to the number of assigned robots, of the connected component of v in G∖Gj, is discovered.
3. Picaboo terminates, and the subgraph of radius ∆ from v is discovered.

D and size n ≥ k. Algorithm Picaboo(r, k,∆) maintains a connected configuration at all times. Moreover, after the ith iteration, all vertices at a distance of at most i from r are visited. If ∆ ≥ D, the algorithm explores G completely in Θ(D2 ) rounds; otherwise, it terminates after Θ(∆2 ) rounds having explored the subgraph of radius ∆.

4.2 Unbounded Radius

Next, we extend Picaboo and derive an algorithm that traverses any graph of size n ≤ k and depth ≤ D, with overhead O((∆ + D∆ ) log(k)). The algorithm starts by calling Picaboo(r, k,∆). In case the traversal is done or a graph of size > n is discovered, it returns. Otherwise, the entire subgraph of G of radius ∆ has been traversed, its size is smaller than n, and we must continue exploration until either we discover more than k vertices, or the subgraph of depth D is successfully explored. However, we cannot continue with Picaboo using a larger ∆, as this would result in an overhead potentially greater than ∆ and proportional to the actual radius of G. There are two reasons why, intuitively, it is possible to maintain the overhead of ∆. The first one is that the size of the graph G remains bounded, and the second is that we can exploit the information gained by discovering the subgraph of radius ∆. One may think of it as a baby-step giant-step algorithm, where in each baby step we discover more nodes in the graph and increase the observed radius by at most ∆ using Picaboo, and each giant step redistributes the robots equally among the unexplored vertices with dangling edges. Intuitively, the giant steps therefore take ∆(1+. . .+(D/∆)) = O(D2 /∆) rounds, or a D/∆ overhead as getting to radius ∆j takes at least ∆j rounds. The baby steps contribute to the established ∆ overhead.

Figure 2 demonstrates BGS (Algorithm 2) on a toy graph, using Picaboo as a subroutine. k = 35 robots start at the root r marked in red in 2a. In the first picaboo step 2b, the subgraph of radius ∆ = 5 is visited, and all vertices in radius 6 are discovered, and marked in gray. Then, in the first giant step 2c, all robots gather at the root and then spread equally among the unvisited vertices, marked in green, except for robots needed to maintain connectivity at the internal vertices marked in gray. Next, Picaboo is executed in parallel in 2d from both green vertices, using 13 robots in each However, after applying a second giant step, the leaves with small connected components will not be traversed again. Let ℓ1j + ℓ2j + ℓ3j be the number of picaboo calls in Cases 1, 2 and 3. If ℓ1j ≥ ℓ2j + ℓ3j , the number of leaves is reduced by a factor of two in each such repetition, and so after ⌈log2(k)⌉ repetitions, ℓ1j = 0. Otherwise, ℓ2j + ℓ3j > ℓj/2. We again divide this case into two cases. If ℓ2j > ℓ3j , then ℓ2j > ℓj/4. Let kj = ∣V (Tj)∣ be the number of robots occupying Tj for connectivity. Since all the rest of the k - kj robots are allocated to leaves, in this case, at least (k - kj)/4 vertices are discovered. In particular, in every iteration j that this case happens, we have kj+1 > kj + (k - kj)/4 = 3kj/4 + k/4. This is a linear recurrence, solving it with k1 = 1 yields kj = k - (k - 1)(3/4)j-1 , and therefore this can also happen at most 1 + log4/3(k - 1) iterations. Finally, we are left with the case where ℓ3j > ℓ2j and therefore ℓ3j > ℓj/4. In this case, a quarter of the leaves discover the radius ∆ subgraph of their connected component in G∖Gj. Therefore, this happens at most 4D/∆ times. As D ≤ n ≤ k, this concludes the correctness of the algorithm.

It remains to bound the algorithm's overhead relative to the optimal traversal. Since the tree is of size n ≤ k, the optimal traversal time equals D, the radius of the graph. The analysis above shows that the number of iterations is bounded by O(D/∆+ log(k)). In each iteration, O(log(k)) repetitions, and in each repetition, we make one baby step and one giant step. As for the giant step, the radius of the discovered subgraph Gj increases by at most ∆ in each iteration (we can avoid the log(k) repetitions for leaves of Case 3), and therefore the radius radius(Gj) ≤ δj. In particular, the j th giant step takes at most 2δj log(k) rounds, and summing over j from 1 to O(D/∆+ log(k)) gives overall O(D2 /∆ log(k) + log2 (k)) rounds. As for baby steps, each one takes at most ∆2 rounds by construction, and therefore the overall number of rounds for baby steps is O((D/∆+log(k))⋅ log(k)⋅∆2 ) = O(Dδ log(k) + log(k)2∆2 ). To conclude, the number of rounds is bounded by O((D2 /∆ + (D + log(k))∆) log(k). Since any traversal of the graph takes at least the radius D, the overhead is bounded by Q(k,D) = O((D/∆ + (1 + log(k) D ∆) log(k)), or ˜Q(k,D) = ˜O(D/∆ + ∆) up to logarithmic factors in k.

Corollary 3. There exists an exploration algorithm with overhead Q(k,D) = O(max(√D, log(k)) log(k)) = ˜O(√D), for k ≥ n.

Intuitively, this directly follows from Lemma 2 by setting ∆ = √D. However, D is not known to the exploration algorithm in advance. This can be tackled by running BGS(r, k,∆i = 2i ) for increasing powers of two, until ∆i > √D, which would take at most ⌈log2(D)⌉ BGS calls. Importantly, each such call will do ∆i iterations, and not run up to k/∆i, effectively "guessing" that the radius of the graph is ≤ ∆2i . In particular, the number of rounds may double each BGS call, and so the geometric sum over the rounds in each call converges to a constant factor.

Theorem4. There exists an exploration algorithmwith overhead Q(k) = O(k1/3 log(k)).

Notably, plugging in D = Θ(k) as the worst case bound in Corollary 3 yields an overhead of Q(k) = O(k1/2 log(k)). However, one can improve by noticing that for such deep graphs, of depth D = Ω(k2/3 ), an optimal algorithm that knows the graph in advance still takes Θ(D) = Ω(k2/3 ) rounds, which is what a DFS exploration with a single robot would take, and therefore the overhead compared to having all robots as one unit traverse the tree is only O(k1/3 ). We can therefore plug in D = k2/3 and ∆ = k1/3 and run BGS, and if the graph is not fully explored, simply traverse it with all robots as one unit in DFS. This yields an overhead of ˜Q(k) = ˜O(k1/3 ).

5 CCGE Under Unbounded Graph Size

The key idea is that under connectivity constraints, the exploration overhead should not depend on the graph size n for a fixed number of robots k ≪ n. For instance, reaching distance 2k from r requires all robots to be at distance > k, so the

Algorithm 3 GraphCover

Input: A rooted graph ⟨G, r⟩; Parameter 0 < ε < 1; Output: The induced subgraph Gτ remained to be covered, of size ∣V (Gτ)∣ < 1ε ; A family V of induced subgraphs of G, with ∣V∣ ≤ nε, where the size of each subgraph Gτ is in ∣V (Gτ )∣ ∈ [ 1ε , 2ε ], and P(V∪{τ}) is an ε-tree-cover of T ; if r has no neighbors then return (({r}, ∅), r), ∅; for u ∈ neighbors(r) do Gu, Vu ← GraphCover((G ∖ {r}, u), ε); Remove Vu and Gu from G; // avoid double coverage Sort neighbors(r) by radius(Gu, u); Initialize size ← 1; for u ∈ neighbors(r) do size += ∣V (Gu)∣; Gr.add subgraph.(Gu); Vr.add(Vu); if size > 1ε then size ← 1; Vr .add(Gr , r); Gr ← ({r}, ∅); return Gr,V;

radius-k neighborhood of r may effectively be traversed by the robots acting as a single unit. Accordingly, our algorithm partitions the discovered graph into subgraphs of size Θ(k), which are explored independently. Fully explored subgraphs are never revisited, while subgraphs found to be larger than expected are recursively partitioned. Each subgraph is explored using the BGS algorithm, which also detects whether its size exceeds k.

5.1 Graph Cover

First, we formalize the notion of covering the currently discovered subgraph with a collection of smaller subgraphs.

Definition 5. A graph-cover P = (T , V) of G is a tree T and a family V = ((Gτ ,u))τ∈V (T ) of induced rooted subgraphs of G such that:

1. Coverage: It covers V , that is, ⋃τ∈V (T ) V (Gτ) = V (T ).
2. Connectivity: For any τ ≠ τ ′ ∈ V (T ), {τ, τ ′ } ∈ E(T ) iff V (Gτ ) ∩ V (Gτ ′ ) ≠ ∅.

Notably, V uniquely identifies the graph-cover. Therefore, we can denote it by P(V). Next, we parameterize a graphcover with the maximal size of a subgraph in the coverage. This is because we essentially want to divide the graph into Θ(n/k) subgraphs of size Θ(k):

Definition 6. Let ⟨G, r⟩ be a rooted graph and ε > 0. An ε-graph-cover P = (T , V) is a graph-cover where each subgraph Gτ ∈ V satisfies ∣V (Gτ )∣ ≤ 2ε , and ∣V∣ ≤ nε + 1.

GraphCover (Algorithm 3) efficiently computes an εgraph-cover. In particular, an ε-graph-cover always exists:

Lemma 7. GraphCover runs in time O(nlog(1/ε)), and if G is connected, returns a graph-cover P(V ⊍ {Gr}) of G.

Proof. As for complexity, GraphCover is a DFS search over G starting from the root r. After each visit, basic operations such as adding (a pointer to) a subgraph, adding (pointers/indices) of subgraph to the cover, and adding up / comparing O(log( 1ε ))-bit numbers.

Coverage. SinceDFSwill scan thewhole graph, eventually all vertices will appear in a subgraph in V ∪ {τ}.

Connectivity. Each subgraph Gu ∈ V ⊍ {Gr} is associated with a root u ∈ V (G) ∩ V (Gu). A path between Gu and Gr is ensured by induction, as each component Gu is connected, and the root u of Gu belongs to V (Gu′ ) of the caller GraphCover(G′ ,u′ ). Furthermore, T is a tree, because we remove Vu and Gu from the graph before going to the next neighbor of r.

In addition, GraphCover outputs an ε-graph-cover:

Lemma 8. If G is connected, GraphCover returns an εgraph-cover P(V ⊍ {τ }) of G.

Proof. By Lemma 7, P is a graph-cover. The size of each added subgraph always coincides with size by induction. It is initialized as 1 to account for the current root r of Gr, and then as long as it doesn't pass 1ε , it is updated by adding the sizes of the subgraphs of each neighbor of u, which are correct by induction. It is important to avoid double-counting by removing Vu and Gu from the graph before partitioning and covering the remaining of the graph. Once a graph is added to V, all vertices except the root are forgotten and the size of the tree is reset to 1.

Therefore, since subgraphs are added to Vr only after checking their size is greater than 1ε , we have that ∣τ∣ < 1ε , as otherwise it would have been added to V. Now, suppose in contradiction that there is a subgraph Gu ∈ P rooted at u of size greater than 2ε . Then there must be a neighbor of u for which GraphCover returned a tree of size ≥ 1ε . But this is a contradiction, since we proved that the size of Gu is always strictly less than 1ε . Finally, denote by P ∶= ∣Vr∣. Then ∣V ∣ = n = ∣V (Gr)∣ +∑τ∈V ∣V (Gτ)∣ ≥ 0 + P ⋅ 1ε . Therefore, P ≤ nε.

5.2 The Algorithm

We are now ready to formally specify our heuristic for graphs of unbounded size n, potentially n ≫ k. Intuitively, GraphCover is used to divide the currently discovered graph into small graphs of (discovered) size Θ(k) ∈ [k/4, k/2]. On each such subgraph, we call BGS to uncover Θ(k) new nodes (or to complete the exploration of the induced subgraph), and then recursively call the exploration algorithm to ensure the subgraph is explored completely.

DFS-BGS (Algorithm 4) is a recursive algorithm that first applies a BGS to uncover a subgraph of size ≥ k, and then computes a graph cover of it, and recursively explores each subgraph in the graph cover in a similar fashion. Intuitively, this recursive behavior ensures the robots never traverse the same area of the graph G twice, and since each subtree in the tree cover is explored with overhead Q(k) independent of n, and since they are of size Θ(k) which prevents exploring

Algorithm 4 DFS-BGS(r, k)

Input: A starting node r ∈ T of an unknown rooted graph G; k ∈ N the number of robots;

Output: A connected traversal X of the graph with k robots; Call BGS(r, k, ∆ = k1/3 ) and initialize X .

Let G be the subgraph discovered so far;

Let P be an 4k graph-cover of G;

Traverse the tree induced by the roots {rτ}τ∈T (P) in DFS, and update X .

Whenever the robots reach rτ where τ is a leaf in T , call DFS-BGS(rτ , k, ∆ = k1/3 ), removing all edges between Gτ and G, and update X;

Return with all robots back to rτ and update X, and continue following the DFS, while updating X ;

Return with all robots back to r, and update X;

return X;

more than O(1) of them in parallel under connectivity, the overall overhead of the algorithm is expected to be Q(k) as well. Unfortunately, since an optimal traversal that is given the tree in advance could explore the graph in a completely different way, this is left as a heuristic that we analyze with experiments in Section 6. From our observations, the decompositions strategy is most effective when the tree has shallow and dense components, as BGS detects them effectively with a relatively low overhead, and GraphCover effectively partitions and focuses on those components one at a time, exploiting the connected team of robots.

6 Experiments

We compare our algorithm to COCTA [Sinay et al., 2017], the current state-of-the-art for online tree coverage. We use it as a lower bound on the overhead of our algorithm. Experiments are conducted on an Apple M2 Pro, 16GB RAM, single 3.5GHz CPU thread. Source code, datasets, synthetic graphs and raw experimental results are all available in the MRFGC GitHub repo.

We deploy two optimizations in our experiments: (i) In Picaboo, if robots can advance to the next level, we do so before gathering at the root; and (ii) when applying a BGS on a subtree from a tree cover, we exploit the fact that part of this subtree is already discovered, and we start with a giant step that deploys all robots to the leaves right away.

We consider two families of random trees: (i) Preferential Attachment Trees (PATS) [Albert and Barab´asi, 2002], where a leaf is added to a node with probability proportional to its degree. This results in relatively dense trees of low depth with a power-law distribution on the degrees of the nodes, where connected collective robot coverage can be most effective; and (ii) Rapidly-exploring random trees (RRTs) [LaValle and Kuffner, 2001], commonly used in robotics for motion planning and path finding, which grow by randomly sampling points in space and connecting them to the nearest node, producing low-degree low-depth trees.

We tested the algorithms for varying numbers of robots, k = 50, 300 and 500, and varying numbers of nodes 50 ≤ n ≤ 5, 000, thus examining the performance of the algorithm both for k > n and k < n. The results are depicted in Figure 3 (note that the x axis is in logarithmic scale). Within the range we tested, the observed overhead was 2-6. Notably, the competitive ratio does not behave as √k, and indeed, it is not even clear if it is monotone in k, even for k ≥ n. Empirically, the overhead exhibits two regimes with a transition around n ≈ k. (i) When n ≤ k, BGS is applied without graph decomposition. In this regime, COCTA incurs an additive overhead that BGS does not have, that was also observed in [Mutzari et al., 2024]. As n grows, this additive cost becomes relatively smaller, leading to a mild increase in the measured overhead. (ii) When n > k, a phase transition occurs: BGS alone no longer suffices and the graph must be decomposed into subgraphs. For n ∼ k, the initial BGS phase often terminates early due to the detection of a subtree of size k. Together with the optimization that increases the search radius without regrouping when possible, this reduces the number of costly iterations, resulting in a decrease in overhead. As n grows much larger than k, this advantage diminishes. The algorithm repeatedly applies the same BGS and GraphCover subroutines, and the relative overhead stabilizes.

We additionally tested our algorithm on the Jaxonville hotel floor plan studied in [Mutzari et al., 2024], where the overhead seems to be within 2-10. The overhead for this graph is expected to be larger, as its tree is highly imbalanced: along each hall many rooms come out as single leaf nodes. This means an offline coverage algorithm can send there single robots and continue exploring the hall, whereas an exploration algorithm cannot distinguish in advance an edge leading to a room from the continuation of the main hall. In our case, the optimized Picaboo will divide the robots equally between the continuation of the hall and the room edges, and so the number of available robots after each edge along a hall decreases exponentially, compared to linearly for COCTA.

Notably, the observed variance decreases with n. For n > k the standard deviation of the overhead is typically between 0.3 and 0.5. For smaller n's, the variance is larger due to the variance of a single BGS run on small, dense and shallow trees. However, 100 samples for each data point are sufficient to obtain a strong statistical confidence. Accordingly, Table 1 reports a 95% CI of mean overhead per data point.

7 The Visibility and Proximity Spectrum

In this paper, we study multi-robot collective connected graph exploration (CCGE), generalizing multi-robot graph coverage (MRGC) along two axes: visibility and proximity. Visibility captures far ahead robots observe: in MRGC the entire graph is known in advance (visibility D(G)), whereas in collective graph exploration (CGE) robots observe only dangling edges. Proximity captures how far robots may separate: in MRGC robots may disperse arbitrarily (proximity D(G)), while in multi-robot connected graph coverage (MRCGC) they must remain connected. CCGE combines the constraints of CGE and MRCGC, setting both visibility and proximity to one. Figure 4 summarizes the relationships among these variants.

In general, one may define CCGE(δ, ε) with parameterized visibility and proximity constraints: robots observe vertices within distance δ and may separate up to distance ε. For δ = D(G) and variable ε, this yields a special case of multirobot formation graph coverage (MRFGC) [Mutzari et al., 2024]. Notably, our DFS-BGS algorithm naturally extends to arbitrary (δ, ε): in Picaboo, visibility δ allows increasing the explored radius by δ in each iteration, while proximity ε implies that only every ε-th layer must remain occupied, freeing additional robots for exploration.

8 Summary

We prove that multi-robot connected exploration has sublinear overhead over offline connected coverage for n ≤ k. Empirically, we observe that overhead might be a small factor in practice, even for n > k. However, we stress that our experiments compare against an algorithm with no theoretical upper bound. One potential explanation could be that connectivity restricts both online and offline coverage and reduces the gap between the two. However, this proposition requires further investigation. Following this line, we believe that getting a theoretical upper bound for CCGE under n ≫ k is an important milestone left for future work.

Acknowledgments

This research has been partly supported by the Israel Science Foundation (ISF) under grants 3007/24 and 2544/24.