PaperlayerView exact revision on arXiv

Source-linked AI summary

Actuator Scheduling for Linear Systems: A Convex Relaxation Approach

Junjie Jiao, Dipankar Maity, John S. Baras, Sandra Hirche

arXiv:2203.02321v2math.OCcs.SYeess.SY

TL;DR

Actuator scheduling among multiple actuators is a combinatorial, generally NP-hard problem, and optimal time-varying schedules remain an open issue in the cited background. This paper uses a convex relaxation as a reference for constructing schedules and reports a faster computation than random trials, while also describing extensions to multiple actuators and actuation costs.

  • Problem

    Optimal time-varying actuator scheduling remains unresolved, and the problem is combinatorial and NP-hard in general.

    Source: §I · p. 1

  • Method

    The paper proposes a convex relaxation and uses its solution as a reference for an algorithm that constructs a schedule for the original problem.

    Source: §I · p. 1, A. Actuator Scheduling Algorithm · p. 4

  • Results

    The proposed approach took 2.5 seconds versus 34.65 seconds for 50,000 random trials; greedy selection had the worst performance.

    Source: §V · p. 7

  • Takeaways & Limitations

    The paper reports that its framework extends to scheduling multiple actuators and incorporating actuation costs.

    Source: §VI · p. 7

    The main analysis restricts scheduling to exactly one actuator at each time with equal actuation costs; the broader cases are discussed separately.

    Source: §I · p. 1

Abstract

from arXiv · show

In this letter, we investigate the problem of actuator scheduling for networked control systems. Given a stochastic linear system with a number of actuators, we consider the case that one actuator is activated at each time. This problem is combinatorial in nature and NP hard to solve. We propose a convex relaxation to the actuator scheduling problem, and use its solution as a reference to design an algorithm for solving the original scheduling problem. Using dynamic programming arguments, we provide a suboptimality bound of our proposed algorithm. Furthermore, we show that our framework can be extended to incorporate multiple actuators scheduling at each time and actuation costs. A simulation example is provided, which shows that our proposed method outperforms a random selection approach and a greedy selection approach.

I. INTRODUCTION

Actuator scheduling in networked control systems remains less studied than sensor scheduling, despite its direct effects on controllability, stability, and control performance. This letter formulates a finite-horizon quadratic-cost scheduling problem and proposes a convex-relaxation-based algorithm, a suboptimality bound, and extensions to multiple actuators and actuation costs.

I. INTRODUCTION

  • Actuator scheduling has received less attention than sensor scheduling, and it affects controllability, stability, and control performance rather than focusing on estimation error.The cited actuator-scheduling work largely studies controllability and stability.Source: §I · p. 1
  • Optimal time-varying actuator scheduling remains unresolved, while prior work often assumes time-invariant schedules that may be suboptimal or restrict controllability in large systems.A round-robin method is discussed as attaining local stability when switching is sufficiently fast.Source: §I · p. 1
  • Earlier LQ actuator-scheduling work considers whether to activate the single available actuator, while the paper studies scheduling among multiple actuators.The paper notes that performance under criteria such as quadratic cost is unknown for controllers focused on controllability and stability.Source: §I · p. 1
  • The scheduling objective is a finite-horizon quadratic cost of system state and control, plus the cost of using each actuator.The actuator cost can represent energy consumption; the general setting allows nonempty actuator subsets at each time.Source: §I · p. 1
  • The paper proposes a convex relaxation whose solution guides an algorithm for the NP-hard scheduling problem, with a suboptimality bound and extensions to multiple actuators and actuation costs.The main setup activates one actuator at each time with equal actuation costs.Source: §I · p. 1

II. PROBLEM FORMULATION

The formulation chooses an actuator schedule for a stochastic linear system to minimize a finite-horizon quadratic control cost. The main analysis restricts the schedule to one actuator per time and equal actuation costs, making the actuation-cost term independent of the schedule.

II. PROBLEM FORMULATION

  • The system model uses Gaussian process noise and an initial Gaussian state, with each actuator entering through its own input matrix.The passage defines the actuator activation indicators as binary-valued.Source: §II · p. 2
  • The general objective minimizes the joint control and actuation cost, with each actuator's use carrying a potentially different time-dependent cost.Actuation cost can reflect differing energy consumption or resource usage across actuators.Source: §II · p. 2
  • The main analysis assumes exactly one actuator is used at each time and equal actuation costs, so minimizing the joint cost is equivalent to minimizing the control cost.The authors defer multiple-actuator scheduling and unequal actuation costs to later discussion.Source: §II · p. 2
  • The system has N actuators, and the schedule specifies which actuator is used at each time to control the system.The setup assumes perfect state measurement and defines the controller's information at time t.Source: §II · p. 2
  • For a fixed schedule, the optimal controller's gain at time t depends on the future actuator schedule through the backward recursion for the cost matrices.The cost for a schedule is expressed as a sum involving those matrices and the noise covariances.Source: §II · p. 2

III. ACTUATOR SCHEDULING WITH SUBOPTIMALITY GUARANTEES

The paper reformulates actuator scheduling as a semidefinite optimization problem and establishes that the stated relaxations preserve the original optimum. It then uses a convex solution as a reference for schedule construction and discusses why choosing the largest relaxed actuator weight at each time need not minimize cost.

III. ACTUATOR SCHEDULING WITH SUBOPTIMALITY GUARANTEES

  • The proposed method uses the convex optimization solution as a reference for a computationally inexpensive suboptimal schedule, with a stated suboptimality bound.The paper says the bound is discussed using dynamic-programming-type arguments.Source: §III · p. 3
  • The LMI-based relaxation in Problem 3 has the same optimal solutions as the original scheduling problem, so these relaxations do not change optimality.The proof constructs an original-problem feasible solution from a relaxed-problem solution with no greater objective value.Source: §III · p. 3
  • Replacing the discrete actuator-matrix constraint by its convex hull yields a convex semidefinite program, while nonbinary relaxed weights require a separate schedule-design algorithm.If the optimal weights are binary-valued, they directly determine the schedule.Source: §III · p. 4
  • Selecting the actuator with the largest relaxed weight at each time is not guaranteed to produce the lowest cost.The paper points to its simulation as an example and motivates a more efficient algorithm with a suboptimality bound.Source: §III · p. 4

A. Actuator Scheduling Algorithm

The algorithm uses the convex-relaxation solution as a reference for constructing a schedule for the original problem. It tracks a trajectory of positive-definite matrices, and its runtime depends linearly on the number of actuators.

A. Actuator Scheduling Algorithm

  • The convex-relaxation solution serves as the reference for an algorithm that constructs a schedule for the original problem, with complexity linear in the actuator count.The algorithm produces a suboptimal solution to the original scheduling problem.Source: A. Actuator Scheduling Algorithm · p. 4
  • The algorithm initializes from the relaxed solution and selects the actuator whose matrix is closest to the reference in Frobenius norm.It starts from the relaxed solution and sets the terminal condition to Q_T.Source: A. Actuator Scheduling Algorithm · p. 4
  • The relaxed matrices form a reference trajectory in the space of positive-definite matrices for the algorithm to track.The sequence K^o_{t|t+1} serves as the reference trajectory.Source: A. Actuator Scheduling Algorithm · p. 4
  • The paper next analyzes the suboptimality guarantee of the algorithm.Source: A. Actuator Scheduling Algorithm · p. 4

B. Dynamic Programming and Suboptimality Guarantees

The analysis uses approximate dynamic programming and the relaxed problem's value function to bound the algorithm's cost relative to the optimal schedule. The bound's error depends on schedule mismatch and vanishes when the relaxation solution is integer-valued.

B. Dynamic Programming and Suboptimality Guarantees

  • The analysis establishes local Lipschitz behavior and an upper bound on the value function, under stated boundedness conditions.The propositions concern positive-definite matrices with bounded Frobenius norms and a positive-definite K with bounded Frobenius norm.Source: B. Dynamic Programming and… · p. 5
  • Algorithm 1 performs approximate dynamic programming by minimizing an upper bound on the value function.Its actuator choice minimizes an upper bound on the cumulative trace objective.Source: B. Dynamic Programming and… · p. 5
  • Theorem 7 denotes by σ the schedule obtained from Algorithm 1, by σ* the true optimal schedule of Problem 1, and by θ* the solution to Problem 4.It defines λₜ ≜ ‖Aₜ₊₁‖₂‖Hₜ(σ*, Kₜ₊₁(θ*))‖₂ and βₜ ≜ ‖gₜ(σ*(t), Kₜ₊₁(θ*)) − Kₜ|ₜ₊₁(θ*)‖F.Source: B. Dynamic Programming and… · p. 5
  • The error term depends on the mismatch between the relaxed and optimal schedules, and is zero when the relaxation solution is integer-valued at every time.In that integer case, each β_t is zero and consequently ε is zero.Source: B. Dynamic Programming and… · p. 6

IV. DISCUSSION ON MULTIPLE ACTUATOR SCHEDULING AND ACTUATION COSTS

This section briefly discusses extensions to multiple-actuator scheduling and actuation costs.

IV. DISCUSSION ON MULTIPLE ACTUATOR SCHEDULING AND ACTUATION COSTS

  • The discussion covers extending the framework to multiple-actuator scheduling.Source: §IV · p. 6
  • The discussion also covers actuation costs.Source: §IV · p. 6
  • Both topics are treated briefly in this section.Source: §IV · p. 6

A. Multiple Actuator Scheduling

For scheduling N_t actuators at a time, the paper describes both virtual-actuator grouping and a less computationally expensive modification of the relaxation and algorithm. The virtual-actuator approach grows factorially in complexity; the alternative adds no complexity to the modified relaxation and only slightly increases algorithm requirements.

A. Multiple Actuator Scheduling

  • Grouping each set of N_t actuators as a virtual actuator makes selecting N_t actuators equivalent to selecting one virtual actuator, but complexity grows factorially.Source: A. Multiple Actuator Scheduling · p. 6
  • A less computationally expensive alternative modifies Problem 4 and Algorithm 1 to select the N_t actuators with the smallest Frobenius distances.The modified Problem 4 sets the selection total to N_t.Source: A. Multiple Actuator Scheduling · p. 6
  • The alternative adds no computational complexity to the modified Problem 4 and only slightly increases Algorithm 1's requirements.The authors describe the increase as practically inconsequential given the algorithm's simplicity.Source: A. Multiple Actuator Scheduling · p. 6

B. Actuation Costs

The main results assume equal actuation costs. Adding actuation costs through a linear term in the optimization objective preserves convexity, and this approach is used in the simulation.

B. Actuation Costs

  • The main results assume equal actuation costs across actuators and time.The assumption is stated as c_t(i) = c for all t and i.Source: B. Actuation Costs · p. 6
  • Actuation costs can be incorporated by adding their sum to the objective, whose linearity in θ_t retains convexity.The simulation adopts this approach.Source: B. Actuation Costs · p. 6
  • The simulation uses the linear-term approach to include actuation costs.Source: B. Actuation Costs · p. 6

V. SIMULATION

In a six-node network with a 30-step horizon, the proposed method obtains cost 101.0006; random schedules have a minimum cost of 102.0693, while greedy selection performs worst. The relaxation also shows that large θ values alone do not identify the best restricted schedule.

V. SIMULATION

  • The simulation uses a six-node network with a 30-step horizon and actuator costs of 1 for nodes 1–4, 1.5 for node 5, and 2 for node 6.The higher costs for nodes 5 and 6 are chosen because the system is fully controllable only with B(5) and B(6).Source: §V · p. 6
  • The six-node system assigns link weights α_ij, with α_ii set so each node’s weights sum to one, and associates an actuator with each node.Source: §V · p. 6
  • The cost function uses Q_t = 1/2 I, R_t(i) = I for all t ≤ T − 1, and Q_T = I.Source: §V · p. 6
  • Cost 101.0006 is the proposed schedule’s result, versus a minimum of 102.0693 across 50,000 random schedules; greedy selection performs worst.The proposed approach took 2.5 seconds, compared with 34.65 seconds for the random trials and less than 1 second for greedy selection.Source: §V · pp. 6–7, Figure 4 · p. 7
  • Actuator 1 has θ values orders of magnitude below the other nodes, yet Algorithm 1 schedules it about 17% of the time.Fig. 3 shows the relaxed θ values, while Fig. 2 shows the resulting schedules.Source: §V · p. 6, Figure 2 · p. 7, Figure 3 · p. 7
  • Fig. 4 plots cost against the percentage of random trials whose cost is at or below that value.The plotted distribution comes from 50,000 randomly selected schedules.Source: Figure 4 · p. 7, §V · p. 7
  • Restricting the schedule to actuators 3 and 4 yields cost 108.5531, higher than the cost found by the proposed method.These actuators have the highest corresponding θ values in Fig. 3.Source: §V · p. 7
  • Greedy selection chooses the minimum-cost actuator at each time stage and is fast, taking less than 1 second, but has the worst performance.Source: §V · p. 7

VI. CONCLUSIONS

The paper studies actuator scheduling for stochastic linear networked control systems, using a convex relaxation as a reference for a suboptimal tracking algorithm. It gives dynamic-programming-based suboptimality guarantees and discusses extensions to multiple actuators and actuation costs.

VI. CONCLUSIONS

  • For stochastic linear networked control systems, the paper uses a convex relaxation as a reference for a suboptimal tracking algorithm, provides dynamic-programming-based suboptimality guarantees, and discusses multiple-actuator and actuation-cost extensions.Source: §VI · p. 7
Loading 2203.02321v2…