PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimal Actuator Placement with Bounds on Control Effort

V. Tzoumas, M. A. Rahimian, G. J. Pappas, A. Jadbabaie

arXiv:1409.3289v5math.OCcs.MAeess.SYmath.DS

TL;DR

The paper addresses how to place a small number of actuators in linear systems while meeting control-energy requirements over the state space. It uses a perturbed energy metric and supermodularity to design efficient approximation algorithms for two NP-hard placement problems, including a worst-case O(log n) approximation for the minimal-placement problem.

  • Problem

    The central problem is selecting few actuated states that ensure controllability while bounding control effort, rather than ensuring controllability alone.

  • Method

    The paper relaxes controllability using an ǫ-close energy objective, proves the generalized metric is supermodular, and applies efficient approximation algorithms, including bisection to search for ǫ.

  • Results

    The minimal actuator-placement problem is NP-hard, while the proposed algorithm achieves an O(log n) multiplicative approximation over a specified parameter range and also approximates the cardinality-constrained minimum-effort problem.

  • Takeaways & Limitations

    The framework provides computationally efficient actuator selection for both prescribed reachable-volume guarantees and maximum reachable volume under a cardinality constraint.

Abstract

from arXiv · show

We address the problem of minimal actuator placement in linear systems so that the volume of the set of states reachable with one unit or less of input energy is lower bounded by a desired value. First, following the recent work of Olshevsky, we prove that this is NP-hard. Then, we provide an efficient algorithm which, for a given range of problem parameters, approximates up to a multiplicative factor of O(logn), n being the network size, any optimal actuator set that meets the same energy criteria; this is the best approximation factor one can achieve in polynomial time, in the worst case. Moreover, the algorithm uses a perturbed version of the involved control energy metric, which we prove to be supermodular. Next, we focus on the related problem of cardinality-constrained actuator placement for minimum control effort, where the optimal actuator set is selected to maximize the volume of the set of states reachable with one unit or less of input energy. While this is also an NP-hard problem, we use our proposed algorithm to efficiently approximate its solutions as well.

I. INTRODUCTION

The paper frames actuator placement as selecting a small set of states that enables controllability while controlling the energy required to steer the system across its state space. It develops approximation algorithms for energy-constrained and cardinality-constrained placement problems.

  • Motivation: Large-scale systems require actuating a small fraction of states to steer the system throughout its state space at low control cost.Controllability alone may be insufficient when the controllability matrix is close to singularity, because desired transfers can require excessive input energy.
  • Actuator placement problems: The first problem selects the fewest actuators whose reachable-state volume meets a prescribed energy criterion, extending controllability-only placement with an energy requirement.The problem is computationally challenging because it combines actuator selection with controllability and energy performance.
  • Actuator placement problems: A related problem selects a cardinality-constrained actuator set that maximizes the volume of states reachable with one unit or less of input energy.The proposed approach selects all actuated states jointly, avoiding the sub-optimality of first ensuring controllability and then adding actuators for energy optimization.
  • Computational challenges: Both actuator placement problems are NP-hard, motivating efficient approximation algorithms based on supermodular control-energy metrics.The paper presents these results alongside its model of diagonal zero-one input placement for linear systems.
  • Energy metric: The paper measures reachable-state volume through log det(W^-1), which is minimized to maximize the states reachable with one unit or less of input energy.The objective can either satisfy a specified upper bound or be minimized while using as few actuators as possible.

C. Actuator Placement Problems

The paper formulates actuator-placement problems that minimize actuator count while enforcing control-energy performance, rather than controllability alone. Both the energy-constrained and cardinality-constrained formulations are NP-hard, motivating approximation algorithms that do not require pre-existing controllability.

  • C. Actuator Placement Problems: The paper minimizes actuator count subject to an upper bound on log det(W^-1), thereby strengthening actuator-placement goals beyond controllability alone.For E →∞, the formulation recovers the minimal controllability problem of.
  • C. Actuator Placement Problems: Unlike related methods, the paper seeks energy-aware actuator placement without assuming a pre-existing controllable actuator set.Related works optimize extra actuators after controllability has already been ensured.
  • C. Actuator Placement Problems: Problem (I) is defined over actuator sets that make the system controllable because the controllability Gramian must be invertible.The paper proves this problem is NP-hard.
  • C. Actuator Placement Problems: Problem (II) selects at most r actuated states to maximize the volume reachable with one unit or less of input energy.This cardinality-constrained problem is also NP-hard.
  • C. Actuator Placement Problems: The proposed approach relaxes Problem (I)'s controllability constraint using an auxiliary program whose solutions can still be controllable and satisfy an ǫ-close energy bound.The paper applies a parallel strategy to Problem (II).

D. Supermodular Functions

The paper uses supermodular-function optimization to construct approximation algorithms for actuator placement. Its perturbed energy metric enables selecting all actuators for the energy objective without assuming controllability beforehand.

  • D. Supermodular Functions: A supermodular function is one whose negation is submodular.Submodularity is characterized by diminishing returns of adding an element to larger sets.
  • D. Supermodular Functions: The relevant auxiliary optimization program uses a non-decreasing supermodular set function and admits a greedy approximate solution.Fact 1 characterizes the performance of the greedy sequence relative to an optimal solution.
  • D. Supermodular Functions: Algorithm 1 takes h and E as input and returns an approximate solution to Problem (O).The associated greedy sequence stops at the first set whose function value is at most E.
  • D. Supermodular Functions: The paper applies this framework to a perturbed energy objective that is supermodular, enabling efficient approximation of Problem (I).The same approach is used for cardinality-constrained Problem (II).
  • D. Supermodular Functions: The resulting algorithms select all actuators toward the energy objective, unlike related work that assumes a controllable initial actuator set.The paper reports worst-case performance guarantees for both problems.

III. MINIMAL ACTUATOR SETS WITH CONSTRAINED CONTROL EFFORT

For minimal actuator placement with constrained control effort, the paper replaces the original energy metric with an ǫ-close metric and relaxes the controllability constraint. Supermodularity and controllability guarantees then support an efficient approximation algorithm.

  • III. MINIMAL ACTUATOR SETS WITH CONSTRAINED CONTROL EFFORT: The paper defines an ǫ-close energy metric that remains well-defined when the controllability matrix is non-invertible.It then introduces an auxiliary problem that avoids the original controllability constraint.
  • III. MINIMAL ACTUATOR SETS WITH CONSTRAINED CONTROL EFFORT: For certain ǫ values, every solution of the auxiliary problem renders the system controllable despite the relaxed constraint.The generalized metric is also proved supermodular with respect to actuator-set choice.
  • III. MINIMAL ACTUATOR SETS WITH CONSTRAINED CONTROL EFFORT: These properties lead to an efficient approximation algorithm for Problem (I).The paper concludes the section by analyzing the algorithm's efficiency.

A. An ǫ-close Auxiliary Problem

The paper introduces an ǫ-close auxiliary problem whose regularized Gramian is always invertible and whose objective approaches the original energy constraint as ǫ tends to zero.

  • A. An ǫ-close Auxiliary Problem: The auxiliary problem replaces W_∆ with a normalized Gramian and adds ǫI to make the matrix invertible for every actuator set.The normalization uses 2λ_max(W_V), while ǫ is positive.
  • A. An ǫ-close Auxiliary Problem: As ǫ →0, the auxiliary energy inequality becomes the original constraint log det(W_∆^-1) ≤ E for controllable actuator sets.The perturbed formulation is therefore ǫ-close to Problem (I).
  • A. An ǫ-close Auxiliary Problem: The auxiliary problem ranges over all subsets of V because its regularized matrix is always invertible.All eigenvalues of the normalized Gramian are at most 1/2.
  • A. An ǫ-close Auxiliary Problem: The paper seeks an approximation algorithm for the ǫ-close NP-hard auxiliary problem corresponding to Problem (I).This auxiliary formulation is the basis for the subsequent algorithmic analysis.

B. Approximation Algorithm for Problem (I′)

The auxiliary problem replaces the restrictive controllability constraint with an ǫ-close energy metric that is supermodular and non-increasing. A greedy algorithm therefore obtains controllable actuator sets satisfying the energy bound, with provable approximation and O(n^5) complexity.

  • Auxiliary problem: The ǫ-close energy metric remains usable without an invertible controllability matrix and supports an auxiliary problem over all actuator subsets.The regularization makes ˜W(∆)+ǫI always invertible.
  • Controllability guarantee: For 0 < ǫ ≤ min{1/2, e^-˜E}, every auxiliary-problem solution satisfying the energy threshold renders the system controllable.The controllability constraint is omitted explicitly but recovered under the stated ǫ condition.
  • Metric structure: The function log det(˜W∆+ǫI)^-1 is supermodular and non-increasing in the actuator set.Its diminishing marginal changes follow from the submodularity argument for log det(˜W∆+ǫI).
  • Greedy algorithm: The greedy algorithm repeatedly adds the actuator producing the largest decrease in the generalized energy objective until the threshold is met.This is Algorithm 2 for the auxiliary problem (I′).
  • Guarantees: O(n^5) is the computational complexity of Algorithm 2, while its actuator-set cardinality is within factor F of the minimum meeting the same energy bound.The determinant and matrix-inversion evaluations dominate the implementation.
  • Design dependence: Increasing n, decreasing ǫ, or decreasing the required energy bound E can increase the selected actuator-set cardinality.The paper identifies log log(ǫ^-1) as the design cost of avoiding pre-existing controllability actuators.

C. Approximation Algorithm for Problem (I)

Algorithm 3 searches for a sufficiently small regularization parameter using bisection and invokes the auxiliary greedy algorithm. It provides a controllable actuator set whose cardinality is within O(log n) of optimal under stated parameter conditions.

  • Bisection search: Algorithm 3 uses bisection to find a sufficiently small ǫ because the required ǫ(c) is not known beforehand.The search interval is bounded by 0 and min{1/2, e^-˜E}.
  • Algorithm: The algorithm invokes Algorithm 2 with the selected ǫ and terminates when the approximation-error condition is satisfied.The procedure adjusts ǫ through inner and outer loops until the required inequality holds.
  • Complexity: The computational complexity is O(n^5 log^2(1/a0)) when the final accuracy is a0, or O(n^5 log^2(1/a) log^2(a0/a)) otherwise.The two forms reflect whether the outer bisection loop executes once or repeatedly.
  • Approximation efficiency: Under the stated parameter-growth conditions, F = O(log n), so the selected cardinality is within a multiplicative O(log n) factor of the optimum.The paper identifies this as the best polynomial-time worst-case bound for the corresponding set-covering class.

IV. MINIMUM ENERGY CONTROL BY A CARDINALITY-CONSTRAINED ACTUATOR SET

For cardinality-constrained minimum-energy control, the paper adapts the regularized metric and Algorithm 3 to approximate actuator sets without assuming initial controllability. The associated auxiliary problem remains NP-hard because its objective is supermodular.

  • Problem formulation: Problem (II) selects at most a prescribed number of actuators to maximize the volume reachable with one unit or less of input energy.The paper formulates this as cardinality-constrained actuator placement for minimum control effort.
  • Regularization: The method removes the restrictive controllability constraint using the ǫ-close generalized energy metric.The regularized objective is defined for every actuator subset.
  • Approximation method: An efficient approximation algorithm for Problem (II) is built from Algorithm 3 and guarantees controllability while approaching the optimal objective value.The construction first solves the regularized auxiliary problem and then transfers the guarantee to the original problem.
  • Complexity: The ǫ-close Problem (II) remains NP-hard because its objective log det(˜W∆+ǫI)^-1 is supermodular.The paper relates this hardness to general supermodular-function minimization.

B. Approximation Algorithm for Problem (II)

Algorithm 4 applies a bisection search over the energy bound and repeatedly calls Algorithm 3 to satisfy an actuator-cardinality limit. It yields controllable sets with approximation guarantees for Problem (II), and runs in polynomial time for a broad parameter class.

  • Bisection framework: Algorithm 4 searches over the energy bound ˜E while requiring Algorithm 3 to return at most r actuators.The search uses lower and upper bounds on the value of Problem (II).
  • Initialization: The algorithm obtains an upper bound from a small controllable actuator set ∆C and exploits monotonicity of the generalized energy objective.The initial controllable set can be found using Algorithm 3 for large E or an earlier procedure.
  • Search target: The least searched bound is defined as the smallest ˜E for which Algorithm 3 returns an actuator set of cardinality at most r.Bisection converges toward this threshold up to its specified accuracy.
  • Guarantees: The returned set satisfies |∆| ≤ r, renders the system controllable, and obeys the stated energy approximation guarantee.These properties follow from the final bisection adjustment and Theorem 2.
  • Complexity: For a wide class of systems with logarithmically bounded accuracy parameters, Algorithm 4 runs in polynomial time.Its complexity inherits Algorithm 3’s dependence on the searched parameters.

V. CONCLUDING REMARKS

The paper addresses two NP-hard actuator-placement problems based on reachable-state volume and provides approximation algorithms for both. It identifies topology effects and distributed implementations as future directions.

  • Both actuator-placement problems are NP-hard: minimum placement for a volume lower bound and cardinality-constrained placement for maximum reachable volume.
  • For the minimum-placement problem, the paper provides a best approximation algorithm for a given range of problem parameters.
  • For cardinality-constrained minimum control effort, the paper proposes an efficient approximation algorithm.
  • Future work examines how network topology affects these problems and how to implement the corresponding algorithms distributively.

APPENDIX

The appendix establishes NP-hardness for both actuator-placement problems through a reduction from controllability and the r-hitting set problem. The reduction uses a polynomially describable energy threshold to make the first problem equivalent to an NP-hard controllability instance.

  • The construction uses an r-hitting set instance, where a size-at-most-r subset must intersect every non-empty set in the collection.
  • Problem (I) is NP-hard by reduction to the controllability problem for a zero-one diagonal actuator matrix.
  • The reduction sets n = m+p+1 and constructs A = V −1DV with D = diag(1, 2, . . ., n).
  • The constructed matrix V has bounded integer entries, while scaled entries of V −1 remain integer and bounded in absolute value by n2.
  • Problem (II) is also NP-hard.

B. The Greedy Algorithm used in the Supermodular Minimization Literature is Inefficient for solving Problem (II′)

The standard greedy algorithm for supermodular minimization is inefficient for Problem (II′) because its approximation error depends on n log(ǫ−1) and it may return an uncontrollable actuator set. Its performance guarantee follows from the submodularity of the perturbed objective.

  • Algorithm 5 greedily selects actuators using the change in log det(W∆ + ǫI)−1.
  • For any positive integer l, Algorithm 5 guarantees log det(W∆l + ǫI)−1 ≤ (1 −e−l/r)v⋆+ n log(ǫ−1)e−l/r.
  • The guarantee follows because the shifted negative log-determinant objective is non-negative, non-decreasing, and submodular.
  • Algorithm 5 has an error term proportional to n log(ǫ−1) and may return an actuator set that does not render the system controllable.
Loading 1409.3289v5…