PaperlayerView exact revision on arXiv

Source-linked AI summary

Failure-Resilient Multi-Robot Coordination with $k$-Connectivity Constrained Submodular Maximization

Yoonjae Hwang, Hojune Kim, Ellen Novoseller, Guangyao Shi, Gaurav S. Sukhatme

arXiv:2610.13049v1cs.ROcs.MA

TL;DR

Robot failures can disrupt communication among surviving robots, a concern not captured by resilient submodular maximization alone. The paper formulates a joint connectivity-and-resilience problem and develops a connectivity-filtered greedy approach with a feasibility-preserving fallback. It proves a connectivity-preserving approximation guarantee and reports that its analysis and experiments characterize the cost of connectivity and resilience.

  • Problem

    Resilient submodular methods preserve objective performance after robot removals but do not account for whether the surviving robots remain connected.

    Source: §I · p. 1

  • Method

    A connectivity filter with rigid-shift fallback is applied across the bait and greedy stages, with a curvature-based analysis that isolates the filter cost in ρ.

    Source: §I · p. 2

  • Results

    The method provides a feasible, (β+1)-connected output surviving any removal of at most β robots and a resilient connectivity-preserving approximation guarantee.

    Source: §I · p. 2

  • Takeaways & Limitations

    The framework jointly captures adversarial robustness and communication-network integrity for multi-robot teams.

    Source: §I · p. 2

    The squared resilience factor is established under the intra-stage hypothesis of Proposition 3; proving that hypothesis unconditionally for diskgraph geometries under bounded motion remains open.

    Source: §VI · p. 8

Abstract

from arXiv · show

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(\mathcal{I}),h(N,β))]^2 ρ\frac{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 teams use submodular objectives to coordinate actions, but robot failures can leave high-performing survivors disconnected. This paper jointly addresses resilience and connectivity, developing a connectivity-aware method and guarantee for the resulting non-matroid feasible family.

I. INTRODUCTION

  • Monotone submodular objectives model coordination through diminishing returns and support computationally efficient greedy algorithms with established constant-factor guarantees.Examples include mutual information, area coverage, observed-target count, and sensor-measurement entropy.Source: §I · p. 1
  • Robot loss can leave a team with high sensing or coverage capacity but a disconnected network that cannot continue coordinated operation.Existing resilient formulations focus primarily on preserving objective performance after removals.Source: §I · p. 1
  • The worst-case removed robots need not be the designated bait set, and the connectivity-constrained feasible family is not a matroid.These properties prevent direct transfer of classical curvature-based greedy guarantees.Source: §I · p. 2
  • The method combines a connectivity filter with a rigid-shift fallback across bait and greedy stages to preserve feasibility after any removal of at most β robots.Its curvature-greedy bound isolates the filter’s cost in a single factor ρ.Source: §I · p. 2
  • The paper proves a resilient, connectivity-preserving approximation guarantee and empirically examines feasibility, the price of connectivity, and the squared resilience factor.The guarantee is evaluated against a connectivity-respecting benchmark.Source: §I · p. 2

II. RELATED WORK

  • Prior work treated connectivity and resilience separately, leaving their simultaneous enforcement against adversarial removals unaddressed.The related-work discussion states that prior work does not impose k-connectivity together with adversarial resilience.Source: §I · p. 1, §II · p. 2

III. PROBLEM FORMULATION

The formulation assigns one candidate trajectory to each robot, evaluates the resulting team with a monotone submodular objective, and constrains endpoint connectivity to withstand up to β removals. It also specifies operational assumptions and highlights the tension between spreading robots for coverage and keeping redundant communication links.

A. Trajectory Model and Submodular Objective

  • Each robot has a finite set of identity-tagged candidate trajectories, and a selection consists of chosen robot–trajectory pairs.The trajectory sets are disjoint because each element includes the robot identity.Source: A. Trajectory Model and Submodular… · p. 2
  • The team objective is normalized, monotone nondecreasing, and submodular, so added trajectories have diminishing marginal benefit.Distinct-target coverage is one example given in the paper.Source: A. Trajectory Model and Submodular… · p. 2

B. Communication and Failure Model

  • The communication graph connects robots whose trajectory endpoints lie within range r_c, and its vertex connectivity equals the minimum robot failures that can disconnect it.By Menger’s theorem, this is also the largest number of internally vertex-disjoint paths joining every pair of vertices.Source: B. Communication and Failure Model · p. 2
  • The failure model allows at most β unknown robot failures or attacks, each removing that robot’s trajectory contribution and graph vertex.With one trajectory per robot, the number of selected trajectories is N and at least N−β are greedily selected as resilient robots.Source: B. Communication and Failure Model · p. 2

C. Assumptions

  • The initial configuration is assumed (β+1)-vertex-connected, and connectivity is required only at committed endpoints, not during trajectories.The endpoint assumption permits temporary disconnection midtrajectory.Source: C. Assumptions · p. 2
  • The analysis assumes every singleton trajectory has nonzero objective value, making the curvature quantities well-defined and the resilient optimum nonzero.The paper reports that excluded instances with zero post-attack objective are a negligible fraction of scenarios.Source: C. Assumptions · p. 2

D. Formal Problem Statement

  • The optimization assigns one trajectory per robot while seeking high team value under a (β+1)-connected endpoint graph.Coverage favors spreading robots to reduce overlap, whereas resilient connectivity favors close placement with redundant links; their intersection destroys the matroid structure.Source: D. Formal Problem Statement · p. 3

E. Resilient Objective and Theoretical Baseline

The resilient benchmark compares assignments that respect connectivity with the best feasible completion of the bait set, rather than with an unconstrained optimum. The connectivity requirement also changes the feasible family in a way that prevents direct use of classical matroid-based greedy analysis.

E. Resilient Objective and Theoretical Baseline

  • The analysis benchmarks performance against the best feasible completion of the bait, since unconstrained-optimum elements may not be feasible additions.The connectivity-respecting optimum is no greater than the unconstrained resilient optimum.Source: E. Resilient Objective and Theoretical… · p. 3

F. The Feasible Family and the Failure of Matroid Structure

  • The one-trajectory-per-robot condition is a partition matroid, but intersecting it with endpoint connectivity yields a partial-selection family that is not a matroid.A four-robot 2-connected square provides a counterexample: removing one selected robot leaves a path that is no longer 2-connected.Source: F. The Feasible Family and the Failure… · p. 3

IV. METHODOLOGY AND THEORETICAL ANALYSIS

  • The algorithm extends a bait-plus-greedy approach with connectivity checks and fallbacks, while the analysis quantifies how connectivity affects the usual resilient greedy choices.The bound addresses the connectivity constraint's impact on the approximation guarantee.Source: §IV · pp. 3–4

A. The Algorithm

RES-CON builds a resilient assignment in bait and greedy stages while preserving connectivity through candidate checks and stay-in-place fallbacks. Its runtime is described as low-order polynomial, with connectivity testing adding a per-step factor.

A. The Algorithm

  • The bait stage orders robots by maximum single-trajectory coverage and assigns each processed robot its highest-coverage trajectory that preserves connectivity.If no such trajectory exists, the robot stays at its Assumption 1 initial endpoint.Source: A. The Algorithm · p. 4
  • The greedy stage assigns each remaining robot the connectivity-feasible trajectory with the greatest marginal gain, falling back to its initial endpoint when none is feasible.The bait and greedy selections together form the output assignment.Source: A. The Algorithm · p. 4
  • RES-CON runs in low-order polynomial time, matching connectivity-blind resilient greedy up to the per-step connectivity factor.Each commit tests at most D candidate trajectories for connectivity on an N-vertex graph.Source: A. The Algorithm · p. 4

B. Connectivity and Survivability

The algorithm maintains a (β+1)-connected endpoint configuration, which guarantees connectivity after any removal of at most β robots. The section also introduces curvature measures for quantifying overlap among trajectories.

B. Connectivity and Survivability

  • Every algorithm output is feasible and remains connected after removal of any at most β robots, regardless of whether removals affect bait robots, greedy robots, or both.The construction preserves (β+1)-connectivity at every commitment, and Menger’s theorem links this threshold to survivability.Source: B. Connectivity and Survivability · p. 4
  • The requirement to survive all removals of at most β robots is reduced to checking whether the endpoint graph has vertex connectivity at least β+1.The connectivity filter performs this scalar test once per commit rather than enumerating attacks.Source: B. Connectivity and Survivability · p. 4

C. Curvature

  • Constrained curvature quantifies worst-case informational overlap among selected trajectories, while global curvature bounds overlap across the ground set for the greedy recursion.The passage associates ν_f near zero with independent information and values approaching one with severe diminishing returns.Source: C. Curvature · pp. 4–5

D. A Greedy Bound under the Connectivity Constraint

The greedy analysis is re-established against a connectivity-respecting optimum because the feasible family is not a matroid. It accounts for connectivity's effect on greedy progress through a single factor, ρ.

D. A Greedy Bound under the Connectivity Constraint

  • The curvature-greedy analysis is re-derived against the constrained optimum, with the connectivity filter’s cost isolated in a single constant.The bound is stated against a connectivity-respecting benchmark because unconstrained-optimum elements may be infeasible additions.Source: D. A Greedy Bound under the… · p. 5
  • At each greedy step, ρ measures the worst-case fraction of marginal value retained when connectivity restricts the candidate set.ρ equals 1 when connectivity never throttles the greedy choice and approaches 0 when it throttles it severely.Source: D. A Greedy Bound under the… · p. 5
  • The hypothetical best-feasible-marginal greedy recursion yields a curvature-based bound, and discounting each step by ρ scales that bound for the actual algorithm.The recursion uses submodularity and curvature of the objective and does not require the optimal set to belong to a matroid.Source: D. A Greedy Bound under the… · p. 5

E. Main Theorem

The theorem’s squared resilience factor results from composing the bait-stage and greedy-stage bounds under an intra-stage filtering condition. Its scope is limited to the stated assumptions and non-degenerate instances.

E. Main Theorem

  • The adversarial-removal bound takes the larger of the curvature-based factor 1 − ν_f(I) and the cardinality-based factor h(N, β).The proof then combines this bound with the greedy-stage and bait-stage bounds.Source: E. Main Theorem · pp. 5–6
  • The multiplicative composition requires intra-stage filtering, where feasible S2 completions depend on S1 through the fixed endpoint set P(A1).The retention ratios defining ρ must be evaluated against that same configuration.Source: E. Main Theorem · p. 6
  • The worst-case guarantee combines the squared resilience factor with the connectivity penalty ρ under the intra-stage hypothesis.The proof makes the two losses multiply by conditioning ρ on the fixed endpoint set P(A1).Source: E. Main Theorem · p. 6
  • The squared factor holds under Assumptions 1–3 and the intra-stage hypothesis; when the post-attack optimum is zero, the ratio is indeterminate.Assumption 3 excludes the floor-collapse cases, which the experiments identify as the approximately 0.7% of swept instances violating the squared bound.Source: E. Main Theorem · p. 6

V. EXPERIMENTS

The experiments assess connectivity cost, output feasibility, the squared resilience factor, and operational behavior over multiple planning cycles.

V. EXPERIMENTS

  • The experiments characterize the connectivity penalty ρ across communication densities and team sizes, including whether it remains bounded away from zero in realistic instances.They also assess output feasibility, the squared resilience factor, and connectivity maintenance over multi-cycle deployments.Source: §V · p. 6
  • The evaluation tests whether Algorithm 1’s outputs satisfy the feasibility guarantee in Proposition 2.Feasibility is one of four stated experiment objectives.Source: §V · p. 6
  • The experiments test the squared resilience factor derived in (9) and assess operational resilience and connectivity maintenance over multi-planning-cycle deployments.The stated objectives also include characterizing ρ across communication densities and team sizes.Source: §V · p. 6

A. System Model

The system model instantiates active target tracking with a coverage objective and compares methods spanning the connectivity–resilience design space. Experiments report how communication density relates to the realized connectivity penalty and filter activity.

A. System Model

  • The target-tracking objective counts distinct targets observed by at least one robot, and the comparison includes RES-CON and baselines with different connectivity or resilience constraints.Robots choose among discretized trajectories while targets move in the arena; the listed baselines include Pure Greedy, Resilient-Only, and connectivity-only methods.Source: A. System Model · p. 6
  • Above the connectivity percolation threshold, realized ρ has median 1.0 and fallback frequency is approximately zero; below it, ρ approaches zero and fallback fires up to 44% of steps.The sweep covers N ∈ {6, 10, 20, 40} and β ∈ {N/4, N/2}.Source: A. System Model · p. 6
  • Above threshold, the filter rejects at least one candidate on 1.67% of steps, versus 32% of steps below threshold.The passage characterizes the constraint as essentially inactive above threshold and binding in the sparse regime.Source: A. System Model · p. 6

C. Feasibility Validation (Proposition 2)

The committed team satisfies the stated (β+1)-connectivity condition across all tested instances. The comparison and objective results characterize the observed tradeoff against the resilience-only selection.

C. Feasibility Validation (Proposition 2)

  • Across 3,619 instances, committed teams are (β+1)-connected on 100% of outputs.This confirms Proposition 2.Source: C. Feasibility Validation (Proposition… · p. 6
  • Without the Stage S1 connectivity filter, connectivity fails on approximately 29% of instances below the percolation threshold.The passage attributes repair of these cases to the S1 filter.Source: C. Feasibility Validation (Proposition… · p. 6
  • In the illustrated 8-robot case after removing three bait robots, RES-CON leaves survivors connected, while Resilient Only yields two components and 36/56 possible failures disconnect them.The caption reports 0/56 such failures for RES-CON.Source: Figure 2 · p. 7
  • The post-attack objective is identical to the unfiltered variant in 93.5% of instances after the S1 filter repairs connectivity.The passage reports negligible cost without measurable effect on the post-attack objective.Source: C. Feasibility Validation (Proposition… · p. 7

D. Testing the Squared Resilience Factor

Experiments show that RES-CON reduces worst-case-survivor disconnection below the percolation threshold while accepting a modest tracking reduction, and that the squared bound is respected on nearly all instances. The conclusion identifies open proof, computability, and hardware-validation questions.

D. Testing the Squared Resilience Factor

E. The Connectivity-Resilience Trade-off

VI. CONCLUSION AND FUTURE WORK

  • The squared resilience factor remains conditional on Proposition 3’s intra-stage hypothesis; unconditional proof for bounded-motion diskgraphs, a geometric lower bound for ρ, and hardware validation remain open.The conclusion identifies these as directions for future work.Source: §VI · p. 8
Loading 2610.13049v1…