Paper deep dive
Failure-Resilient Multi-Robot Coordination with $k$-Connectivity Constrained Submodular Maximization
Yoonjae Hwang, Hojune Kim, Ellen Novoseller, Guangyao Shi, Gaurav S. Sukhatme
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/12/2026, 5:42:13 AM
Summary
This paper introduces Resilient k-Connected Submodular Maximization, a framework for multi-robot coordination that jointly optimizes task performance (submodular maximization) and communication network connectivity under adversarial robot failures. The authors demonstrate that the feasible solution space is not a matroid, preventing the use of classical greedy guarantees. They propose the RES-CON algorithm, which uses a Menger-based connectivity reduction and a connectivity-aware greedy strategy with a fallback mechanism. Theoretical analysis provides a worst-case approximation bound involving curvature and connectivity factors, validated through experiments on multi-robot target tracking.
Entities (10)
Relation Signals (6)
Yoonjae Hwang → affiliatedwith → University of Southern California
confidence 99% · Y. Hwang... are with the School of Computer Science, University of Southern California
Resilient k-Connected Submodular Maximization → solvedby → RES-CON
confidence 95% · Algorithm 1 (RES-CON) states the procedure precisely... We overcome this challenge through a Menger-based connectivity reduction, a connectivity-aware greedy algorithm...
Resilient k-Connected Submodular Maximization → optimizes → Submodular Maximization
confidence 93% · Submodular maximization provides an effective framework for such coordination... we introduce Resilient k-Connected Submodular Maximization
RES-CON → appliedto → Target Tracking
confidence 92% · Experiments on multi-robot target tracking validate the proposed method
RES-CON → uses → Menger's Theorem
confidence 90% · We overcome this challenge through a Menger-based connectivity reduction... By Menger’s theorem, kappa(G) is the largest k...
Resilient k-Connected Submodular Maximization → hasconstraint → Matroid
confidence 85% · The resulting feasible family is not a matroid, preventing the direct application of classical curvature-greedy guarantees.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-robot coordination is essential in applications such as coverage, target tracking, and information gathering, where robots must jointly select actions to maximize team performance. Submodular maximization provides an effective framework for such coordination, and resilient variants further account for robot failures or adversarial removals. However, existing methods typically overlook the impact of robot loss on the communication network, which may disconnect the surviving team and prevent continued coordination. To address this issue, we introduce Resilient $k$-Connected Submodular Maximization, which jointly considers task performance, resilience, and communication connectivity. The resulting feasible family is not a matroid, preventing the direct application of classical curvature-greedy guarantees. We overcome this challenge through a Menger-based connectivity reduction, a connectivity-aware greedy algorithm with a feasibility-preserving fallback, and a new curvature-based analysis that captures the cost of enforcing connectivity through a single factor $\rho$. Our method achieves a worst-case post-failure objective within a factor of $[\max(1-\nu_f(\mathcal{I}),h(N,\beta))]^2 \rho \frac{1}{\kappa_f}(1-e^{-\kappa_f})$ of the optimal connectivity-respecting resilient assignment, while recovering the classical unconstrained guarantee in the appropriate limits. Experiments on multi-robot target tracking validate the proposed method and characterize the practical impact of connectivity constraints.
Tags
Links
- Source: https://arxiv.org/abs/2610.13049v1
- Canonical: https://arxiv.org/abs/2610.13049v1
Trouble viewing inline? Open PDF directly →
Full Text
48,098 characters extracted from source content.
Expand or collapse full text
Failure-Resilient Multi-Robot Coordination with k-Connectivity Constrained Submodular Maximization Yoonjae Hwang Affiliation: Y. Hwang, G. Shi, H. Kim, and G. S. Sukhatme are with the School of Computer Science, University of Southern California, Los Angeles, CA, USA yoonjae, shig, hojuneki, gaurav@usc.edu Hojune Kim Affiliation: Y. Hwang, G. Shi, H. Kim, and G. S. Sukhatme are with the School of Computer Science, University of Southern California, Los Angeles, CA, USA yoonjae, shig, hojuneki, gaurav@usc.edu Ellen Novoseller Affiliation: E. Novoseller is with the U.S. Army DEVCOM Army Research Laboratory, ellen.r.novoseller.civ@army.mil Guangyao Shi Affiliation: Y. Hwang, G. Shi, H. Kim, and G. S. Sukhatme are with the School of Computer Science, University of Southern California, Los Angeles, CA, USA yoonjae, shig, hojuneki, gaurav@usc.edu and Gaurav S. Sukhatme Affiliation: Y. Hwang, G. Shi, H. Kim, and G. S. Sukhatme are with the School of Computer Science, University of Southern California, Los Angeles, CA, USA yoonjae, shig, hojuneki, gaurav@usc.edu Abstract Multi-robot coordination is essential in applications such as coverage, target tracking, and information gathering, where robots must jointly select actions to maximize team performance. Submodular maximization provides an effective framework for such coordination, and resilient variants further account for robot failures or adversarial removals. However, existing methods typically overlook the impact of robot loss on the communication network, which may disconnect the surviving team and prevent continued coordination. To address this issue, we introduce Resilient k-Connected Submodular Maximization, which jointly considers task performance, resilience, and communication connectivity. The resulting feasible family is not a matroid, preventing a direct application of classical curvature-greedy guarantees. We overcome this challenge through a Menger-based connectivity reduction, a connectivity-aware greedy algorithm with a feasibility-preserving fallback, and a new curvature-based analysis that captures the cost of enforcing connectivity through a single factor ρ. Our method achieves a worst-case post-failure objective within a factor [max(1−νf(ℐ),h(N,β))]2ρ1κf(1−e−κf)[ (1- _f(I),h(N,β))]^2ρ 1 _f(1-e^- _f) of the optimal connectivity-respecting resilient assignment, while recovering the classical unconstrained guarantee in the appropriate limits. Experiments on multi-robot target tracking validate the proposed method and characterize the practical impact of connectivity constraints. I Introduction Multi-robot systems provide scalable solutions to applications such as environmental monitoring, target tracking, search and rescue, and collaborative exploration [1, 2, 3, 4]. In many of these settings, the robots must coordinate their sensing or motion decisions to maximize a common team objective [5]. Submodular set functions provide a natural mathematical framework for such coordination by capturing the principle of diminishing returns: the marginal benefit of adding an additional robot decreases as more robots are already selected. Many commonly used objectives, including mutual information [6], area coverage [7], number of observed targets [8], and sensor-measurement entropy [9] are monotone submodular [10]. This structure enables computationally efficient greedy algorithms with well-established constant-factor performance guarantees, as reviewed in Section I. Fig. 1: The core structural conflict in multi-robot deployments. (Left) Aerial teams face adversarial attacks or failures removing up to β nodes. (Middle) Existing frameworks treat requirements in isolation, in which standard resilient maximization risks post-attack fragmentation, while standard connectivity assumes a failure-free environment. (Right) Our framework resolves this by achieving simultaneous adversarial resilience and (β+1)(β+1)-vertex-connectivity, ensuring the surviving team remains structurally connected and performant. Classical submodular maximization, however, typically assumes that the selected robots remain available throughout execution. In practice, robots may be lost due to hardware failures, communication interference, denial-of-service attacks, or other adverse events. This has motivated resilient submodular maximization, where the team is selected so that the objective remains large even after a bounded number of robots are removed [8, 11, 12]. Existing resilient formulations primarily focus on preserving submodular objective performance after such removals. Yet, critically, robot loss can disrupt the communication network among surviving robots. A team might therefore retain high sensing or coverage capacity after failures while becoming disconnected and rendered unable to continue coordinated operation. Communication connectivity and resilience have both been studied extensively, but largely as separate requirements. In this work, we consider them jointly and ask how to select robot actions so that the team achieves a high submodular objective while remaining connected even after adversarial robot removals. We refer to this problem as Resilient k-Connected Submodular Maximization (see Fig. 1). The joint treatment is substantially more challenging than simply combining two existing constraints. Resilience requires accounting for the worst-case subset of removed robots, while connectivity is a global property whose feasibility depends on which robots survive. This interaction also breaks key structures used in existing approximation analysis. In the resilient maximization framework of Tzoumas et al. [11], robustness is achieved by constructing a sacrificial “bait” set of β high-value robots together with a greedily selected remainder. Under a connectivity requirement, however, the adversary determines which robots are removed, and the worst-case removal need not coincide with the bait set. Consequently, enforcing connectivity only on the non-bait robots does not guarantee that the surviving team remains connected. Moreover, the constraint of selecting one trajectory per robot together with a global vertex-connectivity requirement does not form a matroid. As a result, classical curvature-based greedy guarantees cannot be applied directly and must be re-established for the connectivity-constrained resilient setting. We make the following contributions: • We formulate resilient submodular maximization under a (β+1)(β+1)-vertex-connectivity constraint and show that the family of partial, connectivity-feasible selections is not a matroid (Proposition 1), identifying precisely why the classical greedy analysis fails to transfer. • We introduce a connectivity filter with a rigid-shift fallback across both bait and greedy stages, show it guarantees a feasible, (β+1)(β+1)-connected output that survives any removal of size at most β regardless of composition (Proposition 2), and re-derive the curvature-greedy bound against a connectivity-respecting benchmark (Lemma 1), isolating the filter’s entire cost into a single interpretable constant ρ∈[0,1]ρ∈[0,1]. • We prove a resilient, connectivity-preserving approximation guarantee (Theorem 1) and empirically corroborate the algorithm’s feasibility, the price of connectivity, and the squared resilience factor (Section V). I Related Work Our problem sits at the intersection of three literatures, summarized in Table I. Submodular maximization and curvature. The classical greedy (1−1/e)(1-1/e) guarantee [10] was sharpened via curvature [13, 14] and extended to matroid and knapsack constraints [15, 16]. None impose a structural k-connectivity requirement on the selected elements. Connected submodular maximization. Connected maximum coverage was introduced by Vandin et al. [17] and improved by Hochbaum and Rao [18], with follow-up work giving a 1/21/2-approximation in the geometric setting [19], an O(1/k)O( 1/k) bound [20], and a two-stage heuristic for 11-connectivity [7]. None provide a provable guarantee for k≥2k≥ 2, with or without an adversary. Resilient submodular maximization. Maximizing f(A∖B)f(A B) against an adversary removing β elements was introduced and shown NP-hard by Orlin et al. [12] (≈29%≈ 29\% guarantee, β≤2αβ≤ 2α). Tzoumas et al. [11] remove this restriction for any β≤αβ≤α, and Zhou et al. [8] extend it to the matroid-constrained multi-robot setting [6]. None impose a structural requirement on the surviving graph. No prior work imposes k-connectivity as a constraint that holds simultaneously with adversarial resilience, and this is the gap we address. TABLE I: Positioning relative to prior work. k: connectivity level, β: resilience budget, Matroid: whether the feasible family is a matroid Work k β Matroid Guarantee Nemhauser [10] – – yes 1−1/e1-1/e Conforti [13] – – yes 1κf(1−e−κf) 1 _f(1-e^- _f) Hochbaum–Rao [18] 11 – no radius-based Kuo [20] ≥1≥ 1 – no O(1/k)O( 1/k) Shi [7] 11 – no heuristic Orlin [12] – ≤2α≤ 2α yes ≈0.29≈ 0.29 Tzoumas [11] – ≤α≤α yes max(1−κf,1β+1)1κf(1−e−κf) (1- _f, 1β+1) 1 _f(1-e^- _f) Zhou [8] – ≤α≤α yes [⋅]2[·]^2 (matroid) This work β+1β+1 ≤α≤α no [max1−νf(ℐ),h(N,β)]2ρ1κf(1−e−κf) [ \1- _f(I),\,h(N,β) \ ]^2ρ\, 1 _f (1-e^- _f ) (Thm. 1) I Problem Formulation I-A Trajectory Model and Submodular Objective Let ℛ=r1,…,rNR=\r_1,…,r_N\ be a team of N robots. Each robot r has a finite set of candidate trajectories, which we tag with the robot’s identity, r=(r,τ):τ∈rT_r=\(r,τ):τ _r\, with |r|=D|T_r|=D. Because the robot identity r is part of each element, the sets rT_r are pairwise disjoint by construction, and we write ℛ=⋃r∈ℛrT_R= _r T_r for their (disjoint) union. A selection assigns each robot exactly one trajectory. We identify it with the set S⊆ℛS _R of chosen (robot, trajectory) pairs. The team objective is a normalized, monotone nondecreasing, submodular set function f:2ℛ→ℝ≥0f:2^T_R _≥ 0, with f(∅)=0f( )=0. Thus, adding a trajectory never decreases the objective, and its marginal benefit exhibits diminishing returns. We write f(s∣X):=f(X∪s)−f(X)f(s X):=f(X∪\s\)-f(X) for the marginal gain of trajectory s relative to X. One example of such an objective is the number of distinct targets covered by the selected trajectories, as discussed in Section V. I-B Communication and Failure Model Let P(s)P(s) denote the endpoint of trajectory s, and for a selection S let P(S)=P(s):s∈SP(S)=\P(s):s∈ S\ be the joint configuration. Two robots communicate when their endpoints lie within range rcr_c. We define the proximity graph G(P(S))=(ℛ,E)G(P(S))=(R,E), where (i,j)∈E⇔‖P(si)−P(sj)‖≤rc(i,j)∈ E \|P(s_i)-P(s_j)\|≤ r_c. Recall that the vertex connectivity κ(G)κ(G) of a graph G is the size of the smallest set of vertices whose removal disconnects G. By Menger’s theorem [22], κ(G)κ(G) is the largest k such that every pair of vertices is joined by k internally vertex-disjoint paths. In our setting, each vertex is a robot, so κ(G)κ(G) is exactly the minimum number of robot failures that can disconnect the network. We assume that in any deployment, at most β robots may fail or be attacked [11, 8]. As in prior work, the identities of the failed robots are unknown at the time of trajectory selection, and a failure removes the affected robot’s trajectory contribution. It also removes the corresponding vertex of our communication graph G. Because every robot acts, the number of selected trajectories α:=|S|=Nα:=|S|=N, and the number of greedily selected “resilient” robots is at least α−β=N−βα-β=N-β. I-C Assumptions Assumption 1 (Initial connectivity). At the start of each planning cycle, the current configuration induces a (β+1)(β+1)-vertex-connected graph representing a multi-robot team with a prescribed k-vertex-connected topology as in Shi et al. [21]. Assumption 2 (Endpoint connectivity). Connectivity is required only of the committed endpoint configuration P(S)P(S). In other words, robots may temporarily disconnect mid-trajectory. Assumption 3 (Non-degeneracy). Every singleton trajectory satisfies f(s)≠0f(s)≠ 0, so that νf(ℐ) _f(I) and κf _f are well defined and the resilient optimum is nonzero, i.e., fℐ⋆>0f _I>0. Section V shows the excluded degenerate instances (post-attack objective collapsing to zero) are a negligible fraction of scenarios. I-D Formal Problem Statement We synthesize the individual components of robot assignment, communication connectivity, and adversarial resilience into a single robust optimization problem. Problem 1 (Resilient Connectivity-Constrained Maximization). Given a team of robots ℛR, candidate trajectories rT_r for each r∈ℛr , communication radius rcr_c, and an attack budget β, find a joint trajectory selection S⋆⊆ℛS _R that solves: maxS⊆ℛ _S _R minB⊆S|B|≤βf(S∖B) _ subarraycB S\\ |B|≤β subarrayf(S B) (1) s.t. |S∩r|=1,∀r∈ℛ |S _r|=1, ∀ r (2) κ(G(P(S)))≥β+1 κ (G(P(S)) )≥β+1 (3) We assign each robot one trajectory so that the pre-attack graph is (β+1)(β+1)-vertex-connected, ensuring the surviving graph stays connected after at most β removals. The goals pull in opposite directions: coverage rewards spreading robots out to reduce overlap, while resilient connectivity rewards keeping them close with redundant links. This tension, against a worst-case adversary, breaks the matroid structure the classical greedy analysis relies on, as we show next. I-E Resilient Objective and Theoretical Baseline For a selection S, a worst-case removal is B⋆(S)∈argminB⊆S,|B|≤βf(S∖B)B (S)∈ _B S,|B|≤βf(S B). We compare algorithm performance against the best connectivity-respecting resilient assignment, fℐ⋆=maxS∈ℐminB⊆S,|B|≤βf(S∖B),f _I= _S _B S,|B|≤βf(S B), (4) while the unconstrained optimum is f⋆=max|S∩r|=1min|B|≤βf(S∖B)f = _|S _r|=1 _|B|≤βf(S B). Since (4) ranges over a subset of the selections feasible for f⋆f , we have fℐ⋆≤f⋆f _I≤ f . Comparing against the constrained optimal solution fℐ⋆f _I is theoretically necessary, as standard greedy approximation proofs require the elements of the optimal set to be feasible additions to the algorithm’s intermediate solutions. I-F The Feasible Family and the Failure of Matroid Structure The central object is the intersection of the partition matroid (one trajectory per robot) with the connectivity constraint: ℐ=S⊆ℛ: = \\,S _R: |S∩r|=1∀r∈ℛ, |S _r|=1 ∀ r , (5) and κ(G(P(S)))≥β+1. κ (G(P(S)) )≥β+1 \. The one-trajectory-per-robot condition is a partition matroid. Intersecting it with a k-connectivity requirement, however, destroys the matroid structure. To make this precise, extend ℐI to a family of independent sets ℐindI_ind: S∈ℐindS _ind iff S selects at most one trajectory per robot and the induced endpoint graph G(P(S))G(P(S)) is (β+1)(β+1)-vertex-connected. This is the object relevant to Algorithm 1’s correctness, since the stages of the proposed algorithm (Algorithm 1, introduced in Sec. IV) build the final trajectory selection ARESA_RES one trajectory at a time, and it is exactly the family of partial selections encountered along this process that the classical curvature-greedy guarantee requires to form a matroid. We show it does not. Proposition 1 (ℐindI_ind is not a matroid). There exist a communication radius rcr_c and a robot set such that ℐindI_ind violates the hereditary property, and is therefore not the independent-set family of any matroid. Algorithm 1 constructs solutions through partial selections in ℐindI_ind. Its failure to form a matroid is therefore what prevents direct use of the classical curvature-greedy analysis. Proof. Take β=1β=1, so that feasibility requires 22-vertex connectivity, and set rc=1r_c=1. Consider four robots r1,r2,r3,r4\r_1,r_2,r_3,r_4\ and let X=(r1,τ1),(r2,τ2),(r3,τ3),(r4,τ4)X=\(r_1, _1),(r_2, _2),(r_3, _3),(r_4, _4)\ be the selection whose endpoints P(ri,τi)P(r_i, _i) form a 22-connected unit square, so X∈ℐindX _ind. Let Y=X∖(r4,τ4)=(r1,τ1),(r2,τ2),(r3,τ3)Y=X \(r_4, _4)\=\(r_1, _1),(r_2, _2),(r_3, _3)\. Removing one vertex from a 44-cycle leaves a path on three vertices. Thus, Y∉ℐindY _ind, violating the axiom that every subset of an independent set must itself be independent, so ℐindI_ind fails to be a matroid. ∎ IV Methodology and Theoretical Analysis Our algorithm mirrors the bait-plus-greedy structure of Tzoumas et al. [11] and Zhou et al. [8], augmented with a connectivity filter and a rigid-shift fallback in both stages. The analysis is in two parts. First, connectivity and survivability (Section IV-B) follow essentially by construction and are dealt with in Proposition 2. Second, the substance of the analysis is the performance bound (Sections IV-D–IV-E), which quantifies the effect of the connectivity constraint on the usual resilient greedy choices, and how this constraint impacts the approximation guarantee. IV-A The Algorithm Algorithm 1 (RES-CON) states the procedure precisely. Algorithm 1 RES-CON 1: Robots ℛR, trajectory sets Trr∈ℛ\T_r\_r , budget β, initial (β+1)(β+1)-connected configuration P0P_0 (Assumption 1) 2: Feasible, (β+1)(β+1)-connected selection ARES∈ℐA_RES 3: Stage S1 — bait 4: A1←∅A_1← ; P←P0P← P_0 ⊳ shadow configuration 5: Sort ℛR by non-increasing single-trajectory coverage 6: while |A1|<β|A_1|<β do 7: r←r← next robot in sorted order 8: s←s← highest-coverage trajectory of r 9: s.t. G(P[r:=P(s)])G (P[r:=P(s)] ) is (β+1)(β+1)-connected 10: if no such s exists then 11: s←τ0(r)s← _0(r) ⊳ stay at P0(r)P_0(r); Prop. 2 12: end if 13: A1←A1∪sA_1← A_1∪\s\; P[r]←P(s)P[r]← P(s) ⊳ update shadow 14: end while 15: Stage S2 — resilient greedy 16: A2←∅A_2← 17: for k=1k=1 to α−βα-β do 18: s⋆←argmaxsf(s∣A1∪A2)s ← _s\ f(s A_1∪ A_2) 19: subject to G(P[rs:=P(s)])G (P[r_s:=P(s)] ) (β+1)(β+1)-connected 20: if no feasible s⋆s exists then 21: s⋆←τ0(rs)s ← _0(r_s) ⊳ stay at P0(rs)P_0(r_s) 22: end if 23: A2←A2∪s⋆A_2← A_2∪\s \; P[rs⋆]←P(s⋆)P[r_s ]← P(s ) 24: end for 25: return ARES←A1∪A2A_RES← A_1∪ A_2 Stage S1 (bait A1A_1) The robots are sorted in non-increasing order of their maximum single-trajectory coverage. The top β robots are then processed, each assigned its highest-coverage trajectory subject to keeping the running shadow configuration (β+1)(β+1)-connected (line 5), with the stay-in-place fallback (i.e., returning the robot to its Assumption 1 initial endpoint P0(r)P_0(r)) invoked when no such trajectory exists (line 7; see Proposition 2). Ordering by standalone rather than marginal value may assign overlapping bait trajectories, but this affects neither feasibility nor Theorem 1 as the redundancy is priced into the guarantee through νf(ℐ)→1 _f(I)→ 1. Because the fallback leaves the shadow configuration unchanged at that robot’s coordinate, it trivially preserves whatever connectivity level the configuration held prior to the attempted commit. Stage S2 (resilient set A2A_2) Each of the remaining α−βα-β robots greedily selects the connectivity-feasible trajectory of maximal marginal gain (line 13), executing the rigid fallback when no feasible candidate exists (line 15). Output ARES=A1∪A2A_RES=A_1∪ A_2 (line 19). Complexity Each commit evaluates at most D candidate trajectories, and for each it tests whether κ(G)≥β+1κ(G)≥β+1 on an N-vertex graph. This test runs in O((β+1)|E|N)O ((β+1)\,|E|\, N ) time, with |E|=O(N2)|E|=O(N^2) in the worst case. Over the N commits, RES-CON therefore runs in low-order polynomial time, O(ND(β+1)|E|N)O (N\,D\,(β+1)\,|E|\, N ), matching the connectivity-blind resilient greedy up to the per-step connectivity factor. IV-B Connectivity and Survivability Every commitment in Algorithm 1 preserves (β+1)(β+1)-connectivity (or falls back to a move that trivially does), so output connectivity and survivability under attack follow directly from the construction. Proposition 2 (Connectivity and survivability). Algorithm 1 always outputs some ARES∈ℐA_RES . Moreover, for every removal B⊆ℛB with |B|≤β|B|≤β (whether B consists of bait robots, greedy robots, or any mixture of the two), the induced subgraph G(P(ARES))∖BG(P(A_RES)) B is connected. Proof. Feasibility. Let P(0)=P0P^(0)=P_0 denote the shadow configuration prior to any commits, and let P(i)P^(i) denote the shadow configuration after the i-th commit (previously committed robots at their chosen endpoints, not-yet-committed robots still at their P0P_0 position). We show by induction on i that P(i)P^(i) is (β+1)(β+1)-connected for every i. The base case P(0)=P0P^(0)=P_0 holds by Assumption 1. For the inductive step, suppose P(i−1)P^(i-1) is (β+1)(β+1)-connected and consider the i-th commit, for robot r. If a trajectory s exists such that G(P(i−1)[r:=P(s)])G (P^(i-1)[r:=P(s)] ) is (β+1)(β+1)-connected, the algorithm selects it directly, and P(i)=P(i−1)[r:=P(s)]P^(i)=P^(i-1)[r:=P(s)] is (β+1)(β+1)-connected by construction. Otherwise, the algorithm falls back to τ0(r) _0(r), i.e., r remains at P0(r)P_0(r), so P(i)=P(i−1)P^(i)=P^(i-1) is unchanged and remains (β+1)(β+1)-connected by the inductive hypothesis. Every commit in both Stage S1 and Stage S2 falls into one of these two cases, so by induction over the full commit sequence the final shadow configuration P(N)=P(ARES)P^(N)=P(A_RES) is (β+1)(β+1)-connected, so ARES∈ℐA_RES . Survivability. A graph with κ(G)≥kκ(G)≥ k remains connected after deleting any set of fewer than k vertices, equivalently (by Menger’s theorem) every pair of vertices is joined by k internally vertex-disjoint paths [22]. Taking k=β+1k=β+1 and |B|≤β|B|≤β yields connectivity of G(P(ARES))∖BG(P(A_RES)) B for any B of size at most β, regardless of its composition. ∎ Proposition 2 collapses a requirement over all (Nβ) Nβ possible removals, ∀B∀ B with |B|≤β|B|≤β, G(P(ARES))∖BG(P(A_RES)) B connected, into a single scalar test, κ(G)≥β+1κ(G)≥β+1, checked by the connectivity filter once per commit rather than enumerated per attack. IV-C Curvature We use the constrained curvature of Zhou et al. [8] to quantify the worst-case informational overlap between selected trajectories. For a feasible family ℐI and a monotone submodular f with f(s)≠0f(s)≠ 0 for every singleton trajectory, νf(ℐ)=1−minS∈ℐmins∈Sf(S)−f(S∖s)f(s)∈[0,1]. _f(I)=1- _S _s∈ S f(S)-f(S \s\)f(s)∈[0,1]. (6) Here νf=0 _f=0 means the trajectories provide independent information, while νf→1 _f→ 1 indicates severe diminishing returns. We also define the global curvature, κf=1−minvf(ℛ)−f(ℛ∖v)f(v) _f=1- _v f(T_R)-f(T_R \v\)f(v) [13, 14], which similarly bounds overlap across the entire ground set, for the greedy recursion. IV-D A Greedy Bound under the Connectivity Constraint Because ℐI is not a matroid, the Conforti–Cornuéjols curvature-greedy guarantee does not immediately transfer. We re-derive it with respect to the constrained optimum, isolating the cost of the connectivity filter into a single interpretable constant. Definition 1 (Price of connectivity per step). At greedy step k, let gkuncg^unc_k be the largest marginal gain over all remaining single-robot trajectories, and let gkcong^con_k be the largest marginal gain over those trajectories that keep the committed graph (β+1)(β+1)-connected. Define: ρ=mink:gkunc>0gkcongkunc∈[0,1].ρ= _k:\,g^unc_k>0 g^con_kg^unc_k∈[0,1]. (7) A feasible candidate always exists at every step (Proposition 2), so gkcong^con_k is well defined; ρ is the worst-case fraction of greedy marginal value retained under the constraint, with ρ=1ρ=1 when connectivity never throttles the greedy choice and ρ→0ρ→ 0 when it does so severely. Let Aℐ,2⋆∈argmaxA:A1∪A∈ℐ,|A|≤α−βf(A)A _I,2∈ _A:\,A_1∪ A ,|A|≤α-βf(A) be the best feasible completion of the bait, where recall that A1A_1 and A2A_2 denote the S1 and S2 outputs, respectively. Lemma 1 (Constrained curvature-greedy bound). Under Assumptions 1–3, f(A2)≥ρ⋅1κf(1−e−κf)f(Aℐ,2⋆).f(A_2)\;≥\;ρ· 1 _f (1-e^- _f )\,f(A _I,2). (8) Proof. Index the greedy steps k=1,…,α−βk=1,…,α-β, and write A2(k)A_2^(k) for the partial greedy set after k commits. Let O:=Aℐ,2⋆O:=A _I,2, with |O|≤α−β|O|≤α-β. Step (i): submodular decomposition relative to the feasible optimum. By monotonicity and submodularity, at each step k, f(O)−f(A2(k)) f(O)-f(A_2^(k)) ≤f(O∪A2(k))−f(A2(k)) ≤ f(O∪ A_2^(k))-f(A_2^(k)) ≤∑s∈O∖A2(k)f(s∣A2(k)). ≤ _s∈ O A_2^(k)f(s A_2^(k)). Every s∈Os∈ O is, by definition of O as a feasible completion of the bait, a candidate the greedy step could have considered, so it lies in the feasible pool whose best element defines gk+1uncg^unc_k+1. This decomposition is exactly why the bound is stated against the constrained optimum fℐ⋆f _I: elements of an unconstrained optimum could be infeasible to add and would break it. Step (i): curvature relates the marginal sum to a single greedy step. Applying the curvature definition to the marginals bounded in Step (i) and telescoping via the standard Conforti–Cornuéjols recursion [13] yields f(A2′)≥1κf(1−e−κf)f(O)f(A_2 )≥ 1 _f(1-e^- _f)f(O) for the hypothetical greedy A2′A_2 that at each step takes the unconstrained best feasible marginal gkuncg^unc_k. Crucially, this recursion remains valid because submodularity and curvature are properties of f alone; they do not require the optimal set O to be drawn from a strict matroid structure. Step (i): discount by ρ. The actual algorithm commits the connectivity-feasible best, achieving marginal gkcon≥ρgkuncg^con_k≥ρ g^unc_k at every step by (7). Replacing each step’s progress by its ρ-fraction and re-telescoping yields f(A2)≥ρf(A2′)f(A_2)≥ρ f(A_2 ). This scales the bound in (i) uniformly by ρ, giving (8). ∎ IV-E Main Theorem To bound Algorithm 1’s performance, we first use Lemma 1 to bound f(A2)f(A_2) in terms of its constrained optimum f(Aℐ,2⋆)f(A _I,2) and then apply Lemma 2 (proven below) to bound f(Aℐ,2⋆)f(A _I,2) in terms of the true worst-case optimum fℐ⋆f _I. Theorem 1 (Resilient, connectivity-preserving approximation). Under Assumptions 1–3, the output ARESA_RES of Algorithm 1 satisfies, f(ARES∖B⋆(ARES)) f (A_RES B (A_RES) ) ≥[max(1−νf(ℐ),h(N,β))]2⋅ρ ≥ [ (1- _f(I),h(N,β)) ]^2·ρ ⋅1κf(1−e−κf)fℐ⋆, · 1 _f (1-e^- _f )\,f _I, (9) where h(N,β)=max(11+β,1N−β)h(N,β)= \! ( 11+β, 1N-β ). Proof. We follow the bait/greedy case split over ℐI. Write B⋆=B⋆(ARES)B =B (A_RES), B1⋆=B⋆∩A1B _1=B ∩ A_1, and B2⋆=B⋆∩A2B _2=B ∩ A_2. Case A: B2⋆=∅B _2= . Then ARES∖B⋆=A2A_RES B =A_2, so by Lemma 1 and Lemma 2, f(ARES∖B⋆)=f(A2)≥ρ1κf(1−e−κf)max(1−νf(ℐ),h(N,β))fℐ⋆f(A_RES B )=f(A_2)≥ρ 1 _f(1-e^- _f) (1- _f(I),h(N,β))f _I. Since max(1−νf(ℐ),h(N,β))≤1 (1- _f(I),h(N,β))≤ 1, the squared bound in (9) holds. Case B: B2⋆≠∅B _2≠ . Because |B⋆|=|A1|=β|B |=|A_1|=β and at least one greedy element is removed, at least one bait element survives. The bait robots are those of largest single-trajectory coverage, each assigned its highest-coverage connectivity-feasible trajectory. Since the greedy elements are drawn from the same connectivity-feasible universe, each surviving bait element dominates each removed greedy element in absolute single-trajectory coverage. Applying the constrained-curvature counterpart of Tzoumas et al.’s Lemma 1 (using νf(ℐ) _f(I) in place of the global curvature) and value-domination gives the modularity-side bound f(ARES∖B⋆)≥(1−νf(ℐ))f(A2)f(A_RES B )≥(1- _f(I))f(A_2). Independently, the resilience accounting of Zhou et al. [8] yields the cardinality-side bound f(ARES∖B⋆)≥h(N,β)f(A2)f(A_RES B )≥ h(N,β)f(A_2). Taking the larger of the two gives f(ARES∖B⋆)≥max(1−νf(ℐ),h(N,β))f(A2)f(A_RES B )≥ (1- _f(I),h(N,β))f(A_2). Substituting f(A2)f(A_2) using Lemma 1, and then substituting f(Aℐ,2⋆)f(A _I,2) using Lemma 2, yields the desired squared bound in (9). Because the max factor is ≤1≤ 1, this squared bound is the worst-case minimum, ensuring (9) holds in all cases. ∎ We now formally bound the constrained optimum f(Aℐ,2⋆)f(A _I,2) against the worst-case optimum fℐ⋆f _I. Lemma 2 (Second resilience factor). f(Aℐ,2⋆)≥max(1−νf(ℐ),h(N,β))⋅fℐ⋆.f(A _I,2)≥ (1- _f(I),h(N,β))· f _I. Proof. Let S⋆∈ℐS attain fℐ⋆f _I, with worst-case removal B⋆(S⋆)B (S ), and split it into the β highest-singleton-value elements (the virtual bait A~1 A_1) and the remainder A~2:=S⋆∖A~1 A_2:=S A_1. Since A~2 A_2 is a feasible completion of a size-β bait, it competes in the maximization defining Aℐ,2⋆A _I,2, so f(Aℐ,2⋆)≥f(A~2)f(A _I,2)≥ f( A_2). Removing the β highest-value elements extracts the maximum possible value under the curvature bound defined by Zhou et al. [8], guaranteeing that the remainder retains at least f(A~2)≥(1−νf(ℐ))fℐ⋆f( A_2)≥(1- _f(I))f _I. The survivor-count accounting of Zhou et al. [8] gives the cardinality bound f(A~2)≥h(N,β)fℐ⋆f( A_2)≥ h(N,β)f _I. Taking the larger yields the claim. ∎ We formally justify multiplying the bounds from Lemmas 1 and 2 by ensuring the connectivity penalty ρ is conditionally independent of the Stage S1 trajectory selections: Proposition 3 (Stage independence under intra-stage filtering). Suppose the connectivity filter is intra-stage: the feasible S2 completions of the bait depend on S1 only through the fixed endpoint set P(A1)P(A_1), and the retention ratios gkcon/gkuncg^con_k/g^unc_k defining ρ are evaluated against that same configuration. Then the loss from the S1 bait commitment (Lemma 2) and the S2 loss (Lemma 1) compose multiplicatively, yielding the squared factor in (9). Proof. The bounds from Lemma 1 and Lemma 2 chain through the common term f(Aℐ,2⋆)f(A _I,2). The intra-stage hypothesis confines the influence of the S1 choice to the endpoints P(A1)P(A_1); freezing these renders ρ conditionally independent of the specific S1 trajectories, so the two worst-case fractions multiply. Combining with the Case B inequality f(ARES∖B⋆)≥max(1−νf(ℐ),h(N,β))f(A2)f(A_RES B )≥ (1- _f(I),h(N,β))f(A_2) yields the squared bound in Theorem 1. ∎ Remark 1 (Scope of the square). The squared factor holds under Assumptions 1–3 and the intra-stage hypothesis of Proposition 3 on every non-degenerate instance. When fℐ⋆=0f _I=0, (9) is vacuously true but the ratio is the indeterminate 0/00/0; Assumption 3 excludes exactly this floor-collapse set. Section V confirms that the ≈0.7%≈ 0.7\% of swept instances violating the squared bound are precisely these degenerate cases, independent of the connectivity regime. Corollary 1 (Bridge to the unconstrained optimum). Suppose there is γ∈(0,1]γ∈(0,1] with fℐ⋆≥γf⋆f _I≥γ f (γ=1γ=1 whenever some unconstrained resilient optimum is already (β+1)(β+1)-connected). Then f(ARES∖B⋆(ARES))≥[max(1−νf(ℐ),h(N,β))]2ρ1κf(1−e−κf)γf⋆f(A_RES B (A_RES))≥[ (1- _f(I),h(N,β))]^2ρ 1 _f(1-e^- _f)γ f . V Experiments Our experiment objectives are (i) to characterize the connectivity penalty ρ across communication densities and team sizes, establishing that it remains bounded away from zero in realistic instances, (i) to validate the feasibility of Algorithm 1’s outputs (Proposition 2), (i) to test the squared resilience factor derived in (9), and (iv) to evaluate the algorithm’s operational resilience and connectivity maintenance over multi-planning cycle deployments. V-A System Model We instantiate a multi-robot active target tracking formulation, following Shi et al. [7]. A team of N aerial robots flies at fixed altitude in a bounded arena W=[0,L]2W=[0,L]^2. Robot i occupies position xi∈Wx_i∈ W with a downward camera of sensing radius rsr_s under a condition where two robots communicate if and only if ‖xi−xj‖≤rc\|x_i-x_j\|≤ r_c. During each planning cycle, robot i may move within a disc of radius rmover_move, discretized into D candidate trajectories, while M ground targets move by a single-integrator model with reflecting boundaries. The objective is the number of distinct targets observed by at least one robot, f(A)=|⋃i∈AT(xi)|,T(xi)=j:‖pj−xi‖≤rs,f(A)= | _i∈ AT(x_i) |, T(x_i)=\j:\|p^j-x_i\|≤ r_s\, (10) a monotone submodular coverage function with total curvature κf=1−1/M _f=1-1/M. This closed form gives direct control over curvature. After the team commits A, a rational β-adversary removes B⋆(A)=argmin|B|≤βf(A∖B)B (A)= _|B|≤βf(A B), which may be computed exactly for small teams. Fig. 2: Post-attack topology after removing 3 bait robots from an 8-robot team. (a) Resilient Only [8]: unconstrained S2S_2 (resilient set) selection leaves survivors fragmented (κ=0κ=0, 2 components); 36/56 possible 3-robot failures would disconnect them. (b) RES-CON: adding a k-connectivity constraint (k=4k=4) keeps survivors fully connected (κ=7κ=7), with 0/56 possible failures. We compare against baselines spanning the connectivity/resilience design space: Pure Greedy (no constraints), Resilient-Only (Tzoumas et al. [11], no connectivity), 11-Connected-Only (Hochbaum–Rao [18], CSM from Shi et al. [7]), (β+1)(β+1)-Connected-Only (connectivity, no adversary), and Fallback-ablated (ours without the rigid-shift fallback). We denote our method RES-CON. Figure 2 visualizes a post-attack comparison between RES-CON and the Resilient-Only baseline. V-B Measuring the Price of Connectivity ρ At each greedy step, we record the marginal gains gkuncg^unc_k and gkcong^con_k and the running minimum of their ratio, i.e., the realized ρ (7). We sweep density rc/rmover_c/r_move across sparse-to-dense regimes and use N∈6,10,20,40N∈\6,10,20,40\ and β∈N/4,N/2β∈\N/4,N/2\, over 100100 random initializations per parameter set. Fig. 3: Realized price of connectivity ρ (solid: median; shaded band: interquartile range) and fallback-firing frequency (dashed) versus communication density, for β=N/4β=N/4 (left) and β=N/2β=N/2 (right). The dotted verticals mark the (β+1)(β+1)-connectivity percolation threshold. Above the threshold ρ is a flat 1.01.0 and the fallback frequency collapses to zero. Below it, ρ degrades as the fallback activates. Above the connectivity percolation threshold, the realized ρ is a flat median of 1.01.0 in every (N,β)(N,β) cell (Fig. 3), with fallback frequency collapsing to approximately zero. Meanwhile, below the threshold, it degrades sharply (median →0→ 0, with the fallback invoked up to 44%44\% of steps). This empirical result demonstrates that (9) is non-vacuous in the operating regime: when Assumption 1 is satisfied, the connectivity filter imposes no significant penalty to the objective score (i.e., ρ≈1ρ≈ 1). To distinguish whether ρ=1ρ\!=\!1 reflects a filter that is inexpensive to satisfy or one that is invoked only rarely, we measure the per-step candidate-rejection rate. Above threshold, the filter rejects at least one candidate on only 1.67%1.67\% of steps. Below threshold, by contrast, the filter rejects at least one selection on 32%32\% of steps. Thus, we conclude that the connectivity constraint is essentially inactive above the percolation threshold and becomes binding precisely in the sparse regime where connectivity is genuinely at risk. V-C Feasibility Validation (Proposition 2) Across 3,6193,619 instances, the committed team is (β+1)(β+1)-connected on 100%100\% of outputs, confirming Proposition 2. For comparison, an ablation without the Stage S1 connectivity filter fails to maintain connectivity on ≈29%≈ 29\% of instances below threshold. The S1 filter repairs this at negligible cost without measurably affecting the post-attack objective (93.5%93.5\% of instances identical to the unfiltered variant), confirming that guaranteed connectivity does not trade away resilience. V-D Testing the Squared Resilience Factor For small teams (N≤12N≤ 12) where fℐ⋆f _I is computable by brute force, we measure the empirical ratio f(ARES∖B⋆)/fℐ⋆f(A_RES B )/f _I and compare against the squared bound of (9). Fig. 4: Margin (realized ratio −- squared bound) over the (κf,β)( _f,β) plane, where the non-negativity certifies the squared factor. Every cell is positive, indicating the squared bound holds across the entire swept plane on non-degenerate instances. The squared bound is respected on ≈99.3%≈ 99.3\% of instances, with margin uniformly positive across the (κf,β)( _f,β) plane, from +0.18+0.18 to +0.87+0.87 (Fig. 4). The ≈0.7%≈ 0.7\% exceptions are exactly the degenerate fℐ⋆=0f _I=0 instances of Remark 1, independent of the connectivity regime. V-E The Connectivity-Resilience Trade-off Our central claim is that RES-CON preserves connectivity under repeated adversarial attack where connectivity-blind methods fragment. We test this over a T-planning cycle horizon with moving targets, sweeping rcr_c relative to the percolation threshold and measuring both the worst-case-survivor disconnection rate and cumulative target tracking. Fig. 5: Worst-case-survivor disconnection rate versus communication density (normalized to the percolation threshold). Connectivity: Below the percolation threshold, RES-CON disconnects on 12.5%12.5\% of planning cycles at the sparsest density versus 24.7%24.7\% for Resilient-Only and 27%27\% for Pure Greedy (Fig. 5). At and above threshold every method disconnects at near-zero rate. Fig. 6: Cumulative worst-case tracking below threshold (rc/rmove=5.2r_c/r_move=5.2). Resilient-Only accrues the most tracking value by ignoring connectivity, while RES-CON accepts a modest tracking reduction in exchange for roughly halved disconnection Trade-off: Below threshold, Resilient-Only secures the highest cumulative tracking by disregarding the communication graph, but since a fragmented team cannot coordinate under our assumptions, that advantage is misleading. RES-CON instead accepts a modest tracking reduction for the roughly halved disconnection rate as shown in Fig. 5 and in Fig. 6, delivering connectivity-guaranteed tracking at a small coverage cost. At and above threshold, the tracking curves of all methods coincide, consistent with the connectivity constraint being inactive there (Section V-B). VI Conclusion and Future Work We introduced resilient submodular maximization under a (β+1)(β+1)-vertex-connectivity constraint, jointly capturing adversarial robustness and communication network integrity for multi-robot teams. Several directions remain open. First, the squared resilience factor is established under the intra-stage hypothesis of Proposition 3 and corroborated empirically. A proof that this hypothesis holds unconditionally for disk-graph geometries under bounded motion would bolster the idea. Second, deriving a geometric lower bound for ρ would convert the penalty into a computable quantity, making (9) a fully unconditional guarantee on non-degenerate instances. Finally, a hardware demonstration on an aerial or ground fleet would validate the connectivity guarantee under real communication models. Acknowledgments This work was sponsored in part by the U.S. Army DEVCOM Army Research Laboratory under Cooperative Agreement Number W911NF-17-2-0181. References [1] M. Dunbabin and L. Marques, “Robots for environmental monitoring: Significant advancements and applications,” IEEE Robotics & Automation Magazine, vol. 19, no. 1, p. 24–39, 2015. [2] C. Robin and S. Lacroix, “Multi-robot target detection and tracking: Taxonomy and survey,” Autonomous Robots, vol. 40, no. 4, p. 729–760, 2016. [3] J. Peña Queralta, J. Taipalmaa, B. Can Pullinen, V. K. Sarker, T. Nguyen Gia, H. Tenhunen, M. Gabbouj, J. Raitoharju, and T. Westerlund, “Collaborative multi-robot search and rescue: Planning, coordination, perception, and active vision,” IEEE Access, vol. 8, p. 191617–191643, 2020. [4] W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider, “Coordinated multi-robot exploration,” IEEE Transactions on Robotics, vol. 21, no. 3, p. 376–386, 2005. [5] A. Krause and D. Golovin, “Submodular function maximization,” in Tractability: Practical Approaches to Hard Problems, Cambridge University Press, p. 71–104, 2014. [6] A. Krause, H. B. McMahan, C. Guestrin, and A. Gupta, “Robust submodular observation selection,” Journal of Machine Learning Research, vol. 9, no. 12, 2008. [7] G. Shi, I. E. Rabban, L. Zhou, and P. Tokekar, “Communication-aware multi-robot coordination with submodular maximization,” in Proc. IEEE International Conference on Robotics and Automation (ICRA), p. 8955–8961, 2021. [8] L. Zhou, V. Tzoumas, G. J. Pappas, and P. Tokekar, “Resilient active target tracking with multiple robots,” IEEE Robotics and Automation Letters, vol. 4, no. 1, p. 129–136, 2019. [9] P. Dames, P. Tokekar, and V. Kumar, “Detecting, localizing, and tracking an unknown number of moving targets using a team of mobile robots,” The International Journal of Robotics Research, vol. 36, no. 13-14, p. 1540–1553, 2017. [10] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions—I,” Mathematical Programming, vol. 14, no. 1, p. 265–294, 1978. [11] V. Tzoumas, K. Gatsis, A. Jadbabaie, and G. J. Pappas, “Resilient monotone submodular function maximization,” in Proc. IEEE Conference on Decision and Control (CDC), p. 1362–1367, 2017. [12] J. B. Orlin, A. S. Schulz, and R. Udwani, “Robust monotone submodular function maximization,” Mathematical Programming, vol. 172, no. 1, p. 505–537, 2018. [13] M. Conforti and G. Cornuéjols, “Submodular set functions, matroids and the greedy algorithm,” Discrete Applied Mathematics, vol. 7, no. 3, p. 251–274, 1984. [14] R. K. Iyer, S. Jegelka, and J. A. Bilmes, “Curvature and optimal algorithms for learning and minimizing submodular functions,” in Advances in Neural Information Processing Systems, vol. 26, 2013. [15] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, “Maximizing a monotone submodular function subject to a matroid constraint,” SIAM Journal on Computing, vol. 40, no. 6, p. 1740–1766, 2011. [16] C. Chekuri, J. Vondrák, and R. Zenklusen, “Submodular function maximization via the multilinear relaxation and contention resolution schemes,” in Proc. 43rd ACM Symposium on Theory of Computing (STOC), p. 783–792, 2011. [17] F. Vandin, E. Upfal, and B. J. Raphael, “Algorithms for detecting significantly mutated pathways in cancer,” Journal of Computational Biology, vol. 18, no. 3, p. 507–522, 2011. [18] D. S. Hochbaum and X. Rao, “Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer,” Information Processing Letters, vol. 158, art. 105940, 2020. [19] C.-C. Huang, M. Mari, C. Mathieu, J. S. B. Mitchell, and N. H. Mustafa, “Maximizing covered area in the Euclidean plane with connectivity constraint,” in APPROX/RANDOM, p. 32:1–32:21, 2019. [20] T.-W. Kuo, K. C.-J. Lin, and M.-J. Tsai, “Maximizing submodular set function with connectivity constraint: Theory and application to networks,” IEEE/ACM Transactions on Networking, vol. 23, no. 2, p. 533–546, 2014. [21] G. Shi, M. Ishat-E-Rabban, G. Bonner, and P. Tokekar, “Fast k-connectivity restoration in multi-robot systems for robust communication maintenance: Algorithmic and learning-based solutions,” Autonomous Robots, vol. 49, Art. no. 34, 2025. [22] K. Menger, “Zur allgemeinen Kurventheorie,” Fundamenta Mathematicae, vol. 10, no. 1, p. 96–115, 1927.