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 ρ. Our method achieves a worst-case post-failure objective within a factor of [max(1−νf(I),h(N,β))]2ρκf1(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.
Figures & tables
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) -vertex-connectivity, ensuring the surviving team remains structurally connected and performant.
Work
k
β
Matroid
Guarantee
Nemhauser [ 10 ]
–
–
yes
1−1/e
Conforti [ 13 ]
–
–
yes
κf1(1−e−κf)
Hochbaum–Rao [ 18 ]
1
–
no
radius-based
Kuo [ 20 ]
≥1
–
no
O(1/k)
Shi [ 7 ]
1
–
no
heuristic
Orlin [ 12 ]
–
≤2α
yes
≈0.29
TABLE I : Positioning relative to prior work. k : connectivity level, β : resilience budget, Matroid: whether the feasible family is a matroid
Fig. 2 : Post-attack topology after removing 3 bait robots from an 8-robot team. (a) Resilient Only [ 8 ] : unconstrained S2 (resilient set) selection leaves survivors fragmented ( κ=0 , 2 components); 36/56 possible 3-robot failures would disconnect them. (b) RES-CON : adding a k -connectivity constraint ( k=4 ) keeps survivors fully connected ( κ=7 ), with 0/56 possible failures.
Fig. 3 : Realized price of connectivity ρ (solid: median; shaded band: interquartile range) and fallback-firing frequency (dashed) versus communication density, for β=N/4 (left) and β=N/2 (right). The dotted verticals mark the (β+1) -connectivity percolation threshold. Above the threshold ρ is a flat 1.0 and the fallback frequency collapses to zero. Below it, ρ degrades as the fallback activates.
Fig. 4 : Margin (realized ratio − squared bound) over the (κ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.
Fig. 5 : Worst-case-survivor disconnection rate versus communication density (normalized to the percolation threshold).
Fig. 6 : Cumulative worst-case tracking below threshold ( rc/rmove=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
Department of Computer Science, University of Illinois Chicago, Chicago, IL 60607, USA · Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC 28223, USA