A Supermodular Optimization Framework for Leader Selection under Link Noise in Linear Multi-Agent Systems

I. INTRODUCTION

• The paper formulates leader selection in linear multi-agent systems to minimize the sum of follower-state mean-square errors from desired steady-state values.Source: §I · p. 3
• The framework proves the error is supermodular by relating each follower’s error to random-walk commute time, which is itself supermodular in the leader set.Source: §I · p. 3
• It addresses fixed-size leader sets and minimum-size sets meeting an error bound across static, failure-prone, switching, and arbitrarily time-varying topologies.Source: §I · p. 3
• Simulations report that the supermodular approach outperforms random and degree-based selection and performs comparably to convex-optimization methods.Source: §I · pp. 3–4

II. RELATED WORK

• The noise-free selection method in finds a minimum leader set for structural controllability, but does not account for link-noise errors.Source: §II · p. 4
• For,, the authors’ semidefinite-programming relaxation gives no guarantees on chosen-set optimality;,, do not study minimum-size leader sets meeting an error bound or leader selection in dynamic networks.Source: §II · p. 5
• For additive link noise, steady-state error was related to leader-follower effective resistance, while transfer-matrix-based metrics were also proposed.Source: §II · p. 5
• Prior work studied decentralized vehicle-network control with state noise and proved that at least one leader is needed for stability, and examined consensus and formation control using the H2-norm.Source: §II · p. 5
• Existing methods can analyze leader-follower systems with given leaders, but do not select leaders in the presence of noise.Source: §II · p. 5
• Random-walk commute time is the expected time to travel between nodes, and effective resistance between two nodes is proportional to that commute time.Source: §II · p. 5
• Commute time from a node u to a set S is supermodular in S, a result the authors say does not appear in existing literature.Prior work established that effective resistance between two nodes is proportional to their random-walk commute time.Source: §II · p. 5

III. PRELIMINARIES AND BACKGROUND

• The preliminaries cover the system model, system error, and supermodularity.Source: §III · p. 6

A. System Model

• The MAS is modeled as a connected, undirected graph whose edges join agents within communication range.Source: A. System Model · p. 6
• Leaders receive state values from the MAS owner and broadcast them to one-hop neighbors, thereby influencing follower dynamics.Source: A. System Model · p. 6
• The control objective is to make neighboring-agent state differences match desired values rij, which are known to the agents and owner.Source: A. System Model · p. 6
• Each communication link adds independent zero-mean white noise with autocorrelation νijδ(τ), and link weights are selected for a best unbiased linear estimate of leader states.Source: A. System Model · pp. 6–7
• The follower update dynamics are expressed using a weighted Laplacian partitioned into follower and leader blocks, with link-noise contributions represented through matrix B.Source: A. System Model · p. 7
• Leaders hold constant states, and the desired follower state is defined from the leader state and noise-free link terms; connectedness ensures Lff exists.Source: A. System Model · p. 8

B. Quantifying System Error

• The steady-state mean-square error in follower states due to link noise is denoted R(S), the system error for leader set S.The section states that an explicit formula for R(S) is given in terms of matrix L.Source: B. Quantifying System Error · p. 8
• For a given leader set S, the system error can be computed in worst-case O(n^3) time.Source: B. Quantifying System Error · p. 9

C. Supermodular Functions

• Supermodularity means adding an element yields a larger incremental decrease in f for a smaller set than for a superset, expressing diminishing returns as the set grows.Source: C. Supermodular Functions · p. 9
• A set function is monotone nondecreasing when S ⊆ T implies f(S) ≤ f(T), and nonincreasing when f(S) ≥ f(T).Source: C. Supermodular Functions · p. 9
• Any nonnegative finite weighted sum of supermodular functions is supermodular; the corresponding result also holds for submodular functions.Source: C. Supermodular Functions · p. 9
• If f is nonincreasing and supermodular and c ≥ 0, then g(S) = max {f(S), c} is also supermodular.Source: C. Supermodular Functions · p. 9

IV. LEADER SELECTION IN STATIC NETWORKS

• The section treats static networks with fixed links and link-error variances, considering both up-to-k error minimization and minimum-leader selection under an error bound α.Source: §IV · pp. 9–10

A. Case I – Choosing up to k Leaders to Minimize System Error

• Each agent’s error is linked to random-walk commute time, which is nonincreasing and supermodular in the leader set; total error inherits these properties.Source: A. Case I – Choosing up to k Leaders… · pp. 10, 12
• Total system error R(S) is nonincreasing and supermodular, making the up-to-k leader-selection problem a supermodular optimization problem.Source: A. Case I – Choosing up to k Leaders… · p. 12
• The polynomial-time static-k greedy algorithm returns a solution with the stated (1−1/e)-factor approximation guarantee.Source: A. Case I – Choosing up to k Leaders… · pp. 12–13
• static-k starts with no leaders and stops when it reaches k leaders or its stated error condition.Source: A. Case I – Choosing up to k Leaders… · p. 12
• The algorithm’s total runtime is O(kn^4).Source: A. Case I – Choosing up to k Leaders… · p. 13
• Whether additional structure can improve the supermodularity-based guarantee remains an open problem.Source: A. Case I – Choosing up to k Leaders… · pp. 13–14

B. Case II – Choosing the Minimum-Size Leader Set to Achieve an Error Bound

• The goal is to find a minimum-size leader set S such that R(S) ≤ α.For any α ≥ 0, S = V is stated to meet the bound.Source: B. Case II – Choosing the Minimum-Size… · p. 14
• Because R(S) is supermodular, the static-α algorithm uses a greedy procedure to approximately solve the minimum-size leader-selection problem.The algorithm terminates when the error bound is met.Source: B. Case II – Choosing the Minimum-Size… · p. 14
• Theorem 5 states that static-α runs in polynomial time and bounds its returned set size k against the optimal size k*.The supplied theorem excerpt does not show the bound expression.Source: B. Case II – Choosing the Minimum-Size… · p. 15
• In the worst case, static-α performs O(n^2) evaluations of R, each requiring O(n^3) computations.This occurs when it does not terminate until S = V, after n iterations.Source: B. Case II – Choosing the Minimum-Size… · p. 15

V. LEADER SELECTION IN DYNAMIC NETWORKS

• When links or devices fail, topologies switch among prescribed alternatives, or agents move, the optimal leaders may differ from those for a static network.Mobility can change both the link set E and link-error variances νij.Source: §V · p. 15

A. Leader Selection Under Random Link Failures

• When the link set is unknown in advance, leaders can be selected to minimize expected system error over a probability distribution of possible weighted Laplacians.One example assigns each link in an underlying set E an independent, equal failure probability p.Source: A. Leader Selection Under Random Link… · p. 16
• Random link failures can create up to 2^|E| possible topologies, making exact expected-error computation difficult and motivating two approximation approaches.Monte Carlo applies to any distribution π; the gradient-based approximation applies when link-failure probability is small.Source: A. Leader Selection Under Random Link… · p. 16
• Monte Carlo estimates of expected system error converge in probability to the true expected error as the number of sampled Laplacians grows.The result holds for any distribution π and every leader set S.Source: A. Leader Selection Under Random Link… · p. 16
• Under independent random link failures with probability p, the perturbation matrix satisfies ||∆||2 ≤ 2pdX, where d is the maximum node degree and X is defined in Lemma 3.This bound supports the gradient-based approximation for expected error.Source: A. Leader Selection Under Random Link… · p. 17
• For random link failures, expected-error leader selection is supermodular, enabling algorithms for both fixed-size and minimum-size leader sets under an error bound.The algorithms are analogous to static-k and static-α and take the Laplacian distribution as an input.Source: A. Leader Selection Under Random Link… · p. 18

B. Leader Selection Under Switching Between Predefined Topologies

• Leaders may be updated after each topology change using static-k or static-α, or one shared leader set may be used across all topologies.The topology-specific strategy selects a separate set for each topology; the shared-set strategy is described in, while updating after each change is described in.Source: B. Leader Selection Under Switching… · pp. 18–19
• Average-case error is supermodular, so minimizing it with up to k leaders or choosing the fewest leaders to meet α uses modified static-k or static-α algorithms.Ravg is a nonnegative weighted sum of supermodular functions, and therefore is supermodular as a function of the leader set.Source: B. Leader Selection Under Switching… · p. 19

1) Choosing k leaders to minimize worst-case error

• Worst-case error is generally not supermodular because it takes a maximum of supermodular functions, motivating an alternate method for selecting k leaders.The proposed switching-k procedure iteratively tests error thresholds using a supermodular approximation and converges as its threshold decreases.Source: B. Leader Selection Under Switching… · pp. 19–20

2) Choosing leaders to achieve an error bound:

• For a fixed error bound α, minimizing the number of leaders is equivalent to enforcing Fα(S) ≤ α, and supermodularity enables an algorithm analogous to static-α.The equivalence follows because Fα(S) ≤ α exactly when R(S|Li) ≤ α for all i.Source: 2) Choosing leaders to achieve an… · p. 21

3) Leader selection for switching topologies under random agent and link failures:

• Random-failure topologies need not be independent; the analysis uses their joint distribution while the expected average-error expression depends on the individual topology distributions.For example, under the stated failure model, an agent failure in any topology implies failure in all topologies.Source: 3) Leader selection for switching… · p. 21
• For switching topologies with random failures, expected average error is supermodular, enabling leader selection under a size limit or error bound with algorithms analogous to static-k and static-α.The algorithms take the topology distributions π1, . . . , πM as additional inputs.Source: 3) Leader selection for switching… · pp. 21–22
• For switching topologies, the expected worst-case error is bounded below by the maximum expected individual-topology error, whose supermodularity supports approximate selection of up to k leaders.The method uses an algorithm similar to switching-k.Source: 3) Leader selection for switching… · p. 22

C. Leader Selection Under Arbitrarily Time-Varying Topologies

• For arbitrary topology changes, the method selects leaders at each step using previously observed topologies, since the current topology is unknown and a fixed leader set may perform poorly.It assumes topology changes slowly enough for agent dynamics to approximate steady state during each step.Source: C. Leader Selection Under Arbitrarily… · pp. 22–23
• Because the exact leader-choice distributions are unknown, online learning estimates them from prior observations and updates node weights according to losses, reducing the next-step selection likelihood of higher-loss nodes.The update uses a tunable parameter β ∈ (0, 1].Source: C. Leader Selection Under Arbitrarily… · p. 23
• K ≤ O(√(Rmax k T log n)) bounds the difference between online-k’s total error and the error achievable when all T topologies are known in advance.Theorem 9 states this bound for online-k executed over T steps.Source: C. Leader Selection Under Arbitrarily… · p. 24

Case 1: MAS with static network topology

• Figure 1(a) compares supermodular optimization with convex optimization; the convex optimization approach in selects leaders with lower error when k = 3, 4.Source: Figure 1 · p. 25, §VI · p. 26
• 40 leaders achieve normalized error 0.7 with supermodular selection, versus 50 for random selection and over 60 for maximum-degree selection.The random heuristic also consistently outperforms both degree-based algorithms; average-degree selection performs better than maximum-degree selection.Source: Figure 1 · p. 25, §VI · p. 26

Case 2: MAS experiencing random link failures

• At constant deployment area, adding agents increases links and reduces overall error; the supermodular approach still outperforms other methods, though its advantage shrinks as node density grows.As failure probability increases, every scheme degrades, but supermodular optimization minimizes that degradation.Source: §VI · pp. 26–27

Case 3: MAS that switch between predefined topologies

• With random link failures, more leaders are needed to meet the error bound, and supermodular selection outperforms the other heuristics in most cases.The comparison considers switching topologies with independent link failures at probability p = 0.05.Source: §VI · pp. 27–28, Figure 3 · p. 27

Case 4: MAS with arbitrarily time-varying topology

• The supermodular optimization approach consistently yields the lowest error, followed by random, average-degree, and maximum-degree heuristics; online-k improves over time by incorporating observed network topology.A new set of 10 leaders is selected every 10 seconds.Source: §VI · p. 28

• The paper formulates selection to minimize follower-state total mean-square error, either with up to k leaders or with the smallest leader set meeting an error upper bound.Source: §VII · p. 28
• The two selection problems are examined for static topologies, random link failures, switching predefined topologies, and topologies varying arbitrarily over time.Source: §VII · p. 29
• Efficient algorithms use supermodular optimization to approximate the optimum within a provable bound for each of the four cases.Source: §VII · p. 29
• Supermodular leader selection significantly outperformed random and degree-based methods in static and dynamic MAS while providing provable performance bounds and performance comparable to convex optimization.Source: §VII · p. 29

APPENDIX A DERIVATION OF AGENT DYNAMICS

• Appendix A derives follower estimation dynamics from noisy relative-state measurements using a covariance-weighted least-squares estimator.The estimator is given in terms of the diagonal covariance matrix of the measurement noise.Source: Appendix A · p. 31
• The appendix characterizes asymptotic follower-state error covariance through the positive definite solution of a Lyapunov equation.Lemma 6 is identified as characterizing the asymptotic error variance of follower states.Source: Appendix A · pp. 31–32

APPENDIX B

• For nonincreasing supermodular f and c ≥ 0, the truncation g(S) = max{f(S), c} is supermodular.The proof checks cases using supermodularity and monotonicity.Source: Appendix B · p. 32

APPENDIX C

• A preceding lemma characterizes v* through a relation involving neighboring nodes and transition probabilities P(i, j).The proof derives the relation from the definition of L and divides by the sum of neighboring weights.Source: Appendix C · p. 33
• Appendix C states that the solution v* of its Laplacian equation equals the probability that a random walk reaches u before any node in S.The probability uses the transition probabilities defined in equation (8).Source: Appendix C · p. 33
• The proof of Theorem 2 reduces to showing that commute time κ(S, u) is proportional to the right-hand side of equation (36).It begins by considering the probability that a walk from u reaches S before returning to u.Source: Appendix C · p. 34

10. Proposition 2.3 of [36] gives Q(u, S) as a function of the commute time,

• Rearranging the expression for Q(u, S) from Proposition 2.3 of [36] and applying Lemma 10 completes the theorem proof.Source: §10 · p. 34

APPENDIX D

• Appendix D offers an alternative graphical proof of Theorem 3 to the indicator-function derivation in Section IV.Source: Appendix D · p. 34
• Theorem 10 states that commute time κ(S, u) is nonincreasing and supermodular as a function of S.Source: Appendix D · p. 34
• If S ⊆ T, a random walk that reaches S and returns to u has also reached T, so κ(T, u) ≤ κ(S, u).Source: Appendix D · p. 34
• For A ⊆ B and j ∉ B, supermodularity follows by comparing hjAu with hjBu and using τj(B) ⊆ τj(A).The event inclusion gives Pr(τj(B)) ≤ Pr(τj(A)).Source: Appendix D · p. 35
• When a walk from j reaches A before any node in B \ A, or reaches B \ A and then A before u, hjAu equals hjBu.Source: Appendix D · pp. 35–36
• When a walk reaches t ∈ B \ A and then u before A, hjAu > hjBu; together, the three path cases establish supermodularity.Source: Appendix D · p. 36