PaperlayerView exact revision on arXiv

Source-linked AI summary

Pointwise-Sparse Actuator Scheduling for Linear Systems with Controllability Guarantee

Luca Ballotta, Geethu Joseph, Irawati Rahul Thete

arXiv:2407.12125v3math.OCcs.SYeess.SY

TL;DR

The paper studies how to schedule control inputs under a hard per-time sparsity limit while preserving controllability. It characterizes feasible schedules, develops a guaranteed greedy method, and enhances it with MCMC-based optimization. Numerical tests report that the proposed methods work when naive greedy selection fails, while MCMC generally achieves lower costs than greedy selection.

Abstract

from arXiv · show

This paper considers the design of sparse actuator schedules for linear time-invariant systems. An actuator schedule selects, for each time instant, which control inputs act on the system in that instant. We address the optimal scheduling of control inputs under a hard constraint on the number of inputs that can be used at each time. For a sparsely controllable system, we characterize sparse actuator schedules that make the system controllable, and then devise a greedy selection algorithm that guarantees controllability while heuristically providing low control effort. We further show how to enhance our greedy algorithm via Markov chain Monte Carlo-based randomized optimization

I. INTRODUCTION

The paper addresses sparse actuator design, where prior work studied controllability conditions but sparse input design remained underdeveloped. It defines pointwise-sparse schedules and proposes a controllability-guaranteeing greedy approach with an MCMC-based enhancement.

I. INTRODUCTION

  • Sparse input design remained under-studied despite established controllability theory, and naive greedy selection does not guarantee controllability for every sparsity-controllable system.The paper addresses this gap with algorithms that formally guarantee controllability.Source: §I · p. 1

Contribution:

  • The paper characterizes controllability-enabling schedules, develops an improved greedy algorithm with a formal guarantee, and proposes MCMC-based optimization at increased computational complexity.The guarantee applies when the system is controllable under the sparsity constraint.Source: Contribution · p. 1

II. SPARSE ACTUATOR SCHEDULING PROBLEM

  • An s-sparse controllable system can be driven between any initial and desired states while at most s control inputs are nonzero at each time.The bound applies at every time instant, not merely on average over the horizon.Source: §II · p. 2

A. Preliminaries on Sparse Controllability

  • An actuator schedule is an ordered sequence of active-channel sets, with each set containing no more than s inputs for an s-sparse schedule.Channel i is active at time k only when i belongs to S_k.Source: A. Preliminaries on Sparse… · p. 2

B. Sparse Control Design Problem Formulation

The design problem selects a pointwise-sparse actuator schedule that ensures controllability while minimizing a control-effort metric. Its constraints are combinatorial, and feasibility depends on controllability, sparsity, and horizon conditions.

B. Sparse Control Design Problem Formulation

  • A feasible schedule determines the support of the control input independently of the initial and final states, after which the control inputs can be designed by least squares.This support-selection approach removes the sparsity constraint from the subsequent input-design step.Source: B. Sparse Control Design Problem… · p. 2
  • The control-effort metric is based on the schedule's controllability Gramian, which quantifies the energy required to reach a target state in h steps.The passage points to common energy-aware performance metrics but does not supply their values.Source: B. Sparse Control Design Problem… · p. 2, Table I · p. 2
  • The schedule must respect a per-time input budget and a rank constraint that ensures sparse controllability, while minimizing the chosen cost function.The authors note that exhaustive search is possible, but describe the problem as combinatorial and report that its NP-hardness has been suggested without proof.Source: B. Sparse Control Design Problem… · p. 2
  • Feasibility requires a controllable system, s ≥ max{n − rk{A}, 1}, and a horizon h ≥ h∗.The proposed algorithms assume these conditions and are described as having polynomial complexity.Source: B. Sparse Control Design Problem… · p. 2

III. DESIGN ALGORITHMS

The section shows why naive greedy selection can fail under pointwise sparsity, then develops feasible-schedule conditions and a greedy design algorithm with a formal controllability guarantee. It also proposes stochastic optimization to improve performance.

III. DESIGN ALGORITHMS

  • A stochastic optimization approach is proposed to improve the design algorithm's performance.The section introduces this approach after the improved greedy algorithm.Source: §III · p. 3

A. Drawback of the Naive Greedy Algorithm

  • Under pointwise s-sparsity, greedy column selection may yield an uncontrollable system, despite its use to reduce cost under an input budget.In the example, the selected columns leave the last reachability row zero, so the resulting system is uncontrollable.Source: A. Drawback of the Naive Greedy… · p. 3

B. Characterizing Feasible Actuator Schedules

  • The analysis develops sufficient conditions for controllability by extending a necessary-condition argument.Lemma 2 supplies index sets under its stated assumptions, and Theorem 1 guarantees a feasible schedule satisfying the derived structural condition for every k in [R].Source: B. Characterizing Feasible Actuator… · pp. 3–4
  • The sparse controllability index gives a lower bound of R on schedule length, and Theorem 1 establishes structure for schedules at times h−R through h−1.The improved greedy algorithm searches among schedules with this structure to guarantee controllability.Source: B. Characterizing Feasible Actuator… · p. 4

C. Improved s-Sparse Greedy Algorithm

The improved greedy algorithm first schedules channels needed to span key subspaces, then adds channels while checking controllability and reducing cost. Its rank checks ensure a controllable schedule when one exists under the sparsity constraint.

C. Improved s-Sparse Greedy Algorithm

  • The algorithm initializes the schedule with all channels, then selects channels to span the subspaces required for controllability.At each time step, it computes K_k and selects channels until the spanning condition is met.Source: C. Improved s-Sparse Greedy Algorithm · p. 4
  • For each selected channel, its contribution to the controllability Gramian is computed, and dependent candidates are removed so the schedule spans K_k.A positive slack is needed when K_k has dimension greater than one to avoid a singular matrix in the cost function.Source: C. Improved s-Sparse Greedy Algorithm · p. 4
  • After scheduling channels needed to span the kernels of A, A^2, …, A^R, rank-checked greedy selection makes the S-controllability Gramian full rank.The rank check removes candidates that cannot increase the Gramian's rank.Source: C. Improved s-Sparse Greedy Algorithm · p. 4
  • A final loop adds channels until cost cannot be further reduced or the schedule reaches the s-sparsity limit.For this last selection, the cost can be computed exactly by setting ϵ = 0.Source: C. Improved s-Sparse Greedy Algorithm · pp. 4–5

Computational complexity:

The improved greedy algorithm has polynomial computational complexity, with the rank-checking loop dominating its total cost. Its overall order matches that of the naive greedy algorithm under pointwise sparsity.

Computational complexity:

  • The first loop costs O(hms max{n^β, n^3}), including greedy selection and subspace computation.Powers of A and their null spaces can be computed once before the algorithm runs.Source: Computational complexity · p. 5
  • The rank-checking loop runs for at most n iterations and costs O(hm max{n^β+1, n^4}) overall.Its channel-selection and rank-check steps cost O(hmn^β) and O(hmn^3), respectively, per iteration.Source: Computational complexity · p. 5
  • The improved algorithm's total complexity is O(hm max{n^(β+1), n^4}), the same order as the naive pointwise-sparse greedy algorithm.The second for-loop dominates the total complexity.Source: Computational complexity · p. 5

D. s-Sparse Markov Chain Monte Carlo

The s-sparse MCMC method explores schedules through one-channel, one-time-step changes and can improve on a greedy initialization. Its randomized search does not itself guarantee controllability, and can be slow for large systems.

D. s-Sparse Markov Chain Monte Carlo

  • The paper leaves unexplored the option of randomly dropping channels across multiple iterations when greedy selection cannot lower cost in one iteration.The authors identify this as a direction for future numerical evaluation.Source: D. s-Sparse Markov Chain Monte Carlo · p. 5
  • MCMC proposes schedules that differ from the current schedule by one channel at one time step, preserving s-sparsity.The method uses the output of Algorithm 1 as its warm start and accepts a sample with probability that decreases exponentially with the cost gap.Source: D. s-Sparse Markov Chain Monte Carlo · p. 5
  • A rank check can prevent candidate schedules from decreasing the controllability Gramian's rank, but may significantly slow the algorithm.If the initial schedule is not controllable, formal controllability of the output cannot be ensured.Source: D. s-Sparse Markov Chain Monte Carlo · pp. 5–6
  • MCMC generally converges slowly in practice and may require many samples to find good solutions for large systems.With finite samples and a positive minimum temperature, the method has approximation error and a suboptimality gap.Source: D. s-Sparse Markov Chain Monte Carlo · p. 5

IV. NUMERICAL EXPERIMENTS

The numerical evaluation tests the proposed algorithms on two problem instances.

IV. NUMERICAL EXPERIMENTS

  • The numerical experiments test the algorithms on two problem instances.Source: §IV · p. 6

A. Revisited Example 1

In Example 1, the s-sparse greedy algorithm selects input channel 4 at every time step, guaranteeing controllability through its preselection strategy.

A. Revisited Example 1

  • Input channel 4 is selected at all four time steps, satisfying the stated necessary condition for controllability.The authors attribute this choice to the algorithm's preselection at Lines 8 and 9.Source: A. Revisited Example 1 · p. 6
  • Table II reports the proposed schedule and cost alongside the naive greedy schedule and the fully actuated system's cost.The passage provides no numerical cost values.Source: A. Revisited Example 1 · p. 6

B. Experiment with Large-Scale Network

On the tested large-scale networks, the s-sparse greedy algorithm achieved controllability where naive greedy failed, including after s-sparse MCMC refinement. The experiments also compare control costs as sparsity varies, and the conclusion identifies stricter sparsity constraints as future work.

B. Experiment with Large-Scale Network

  • The benchmark models a network with n=m=50, using a scaled random-geometric-graph adjacency matrix A and identity input matrix B.Each node is directly controlled through the corresponding column of B.Source: B. Experiment with Large-Scale Network · p. 6
  • The s-sparse greedy algorithm yielded controllable systems on all tried instances, while naive greedy failed even after s-sparse MCMC refinement.The benchmark used n=m=50 and sparsity s=n−rk{A}.Source: B. Experiment with Large-Scale Network · p. 6
  • As sparsity s increases from 20 to 28, both methods' costs decrease; MCMC costs are smaller, while greedy costs are only slightly larger in most cases, especially with ρ(·) = −log det(·).The comparison uses a system with n−rk{A}=20; the passage attributes MCMC's lower costs to its exploratory approach.Source: B. Experiment with Large-Scale Network · p. 6

V. CONCLUSION

  • The conclusion proposes exploring stricter sparsity constraints, including slowly varying active input sets, as future work.Source: §V · p. 6

APPENDIX A PROOF OF LEMMA 2

The proof uses projection onto the orthogonal complement of the columns of powers of A, then constructs sparse input contributions recursively to establish the lemma's result.

APPENDIX A PROOF OF LEMMA 2

  • K(k)=I−Ak(Ak)† projects onto ker{(Ak)⊤}, the subspace orthogonal to Col{Ak}.Source: Appendix A · p. 6
  • For each relevant k, the proof selects s columns of K(k)Ak−1B to satisfy the stated condition.It uses the Sylvester rank inequality to establish the existence of these columns.Source: Appendix A · p. 6
  • The proof recursively constructs sparse input vectors and uses K(R) to establish the desired result.Source: Appendix A · pp. 6–7

APPENDIX B PROOF OF THEOREM 1

The proof decomposes the state space into zero- and nonzero-eigenvalue components, then applies sparse controllability to the invertible component. The condition h≥n ensures enough time steps for the constructed schedule.

APPENDIX B PROOF OF THEOREM 1

  • The proof decomposes A into Jordan blocks for its nonzero and zero eigenvalues, with the nilpotent zero-eigenvalue component vanishing for k≥R.The nonzero-eigenvalue component has rank J≤n−R.Source: Appendix B · p. 7
  • Because the nonzero-eigenvalue component is invertible, sparse controllability yields sets S0 through SJ−1 with at most s inputs each.The proof applies Proposition 2 to the system (J, B̄).Source: Appendix B · p. 7
  • When h≥n, h−R≥n−R≥J implies R+J≤h, which establishes the required schedule condition.Source: Appendix B · p. 7
Loading 2407.12125v3…