DIPARTIMENTO DIELETTRONICA, INFORMAZIONE E BIOINGEGNERIA
DOCTORALPROGRAMME IN INFORMATIONTECHNOLOGY
A
UTOMATIC VERIFICATION AND INPUT DESIGN
FOR DYNAMICAL SYSTEMS
:
AN
OPTIMIZATION
-
BASED APPROACH TO THE
DETECTION OF NON
-
INFLUENTIAL INPUTS
Doctoral Dissertation of:
Riccardo Maria Vignali
Supervisor:
Prof. Maria Prandini
As the complexity of control systems grows, the verification of their correct functioning assumes a more important role. In the testing phase, when the system is checked against possible misbehaviors, the verification task con-sists in computing the input sequence to be injected in the system so as to generate that undesired behavior. When such an inputs sequence is found, the cause of the malfunctioning can be understood and the design of the control system improved accordingly. Nonetheless, it may happen that the detected input sequence is too complicated to interpret, since, for example, it requires to simultaneously set too many inputs. This prompts the need for novel verification methods, that provide "minimal" inputs sequences that satisfy a given specification (i.e., the misbehavior in the considered testing framework). In this work we address this need and develop techniques for the maximization of the number of non-influential inputs, i.e., those inputs that can take an arbitrary value in their range without compromising the satisfaction of the specification. We address this problem for the class of discrete time linear systems and discrete time Piecewise Affine (PWA) sys-tems, in the case of reachability and safety specifications.
For linear systems we develop two different techniques. In the first tech-nique we rely on an input parametrization that treats the inputs as set valued signals and formulate a linear optimization problem with the objective of maximizing the range on where each input can vary, with the constraint on the satisfaction of the specification. In the second technique, we rely on a parametrization that allows the influential inputs to depend on the non-influential ones and formulate a Mixed Integer Linear Programming
As for the PWA case, we start by showing that an approach based on the extension of the first technique developed for the linear case leads to too conservative results. Prompted by the analysis of conservativeness, we rein-terpret the problem from a geometrical perspective and formulate an exact approach to its solution, that, however, turns out to be intractable. On the base of this, we then construct an approximation of the exact problem that, despite being still conservative, leads to better results than the approach in-spired by the linear case. As the approaches formulated for the PWA case can be computationally demanding, we also show, in the last part of this work, how to reduce their complexity via suitable techniques. In one of these techniques we show how to construct a reduced order PWA that pre-serves the input/output behavior of the original system by performing an extension of the classical observability analysis of linear systems.
1 Introduction 1
2 Linear case 5
2.1 Non-influential inputs detection for linear systems: an open
loop scheme . . . 6
2.1.1 Problem formulation and resolution . . . 6
2.1.2 Numerical Examples . . . 12
2.2 Non-influential inputs detection for linear systems: a com-pensation scheme . . . 14
2.2.1 Problem formulation and resolution . . . 16
2.2.2 Comparison with the open loop approach . . . 22
2.2.3 Application to networked control system . . . 23
2.2.4 Numerical example . . . 24
3 Piecewise Affine case 29 3.1 Modelling context . . . 30
3.1.1 Piecewise Affine systems . . . 30
3.1.2 Mixed Logical Dynamical systems . . . 31
3.2 Problem formulation . . . 31
3.3 Satisfying the specification in minimum time . . . 33
3.4 Computing non-influential inputs for a PWA system . . . 35
3.4.1 Extension of the approach proposed for the linear case 35 3.4.2 An exact approach . . . 49
4 Reducing computational complexity 61
4.1 Iterative procedure for cascading systems . . . 61
4.2 Redundancies removal . . . 63
4.2.1 Removal of redundant binary variables . . . 63
4.2.2 Removal of redundant modes . . . 63
4.3 Structural reduction . . . 65
4.3.1 Linear systems . . . 66
4.3.2 Mixed Logical Dynamical systems . . . 67
5 Numerical examples 73 5.1 Non-influential inputs detection in PWA case . . . 73
5.2 Structural reduction . . . 81
5.2.1 Modes merging . . . 82
5.2.2 Structural reduction . . . 84
6 Conclusions 87
CHAPTER
1
Introduction
The aim of this thesis is to develop novel methods for verifying the correct functioning of a system, which possibly involves interacting continuous and discrete dynamical components. In general terms, the goal of system verification is to evaluate if a system behaves as desired. Commonly, the desired behavior is referred to as a specification and is associated to the evolution in time of some variables of the system (state or output). In par-ticular, reachability and safety specifications have been extensively studied in the literature and deal with checking if the state reaches a desired target set and if it remains within some given safe set, respectively.
In this work, we address verification problems where the inputs have to be designed so as to make the system satisfy either a reachability or a safety specification. Among the possible solutions to the problem, we look for the one that minimizes the time to satisfy the specification and that corresponds to the maximal number of non-influential inputs, i.e., inputs that can take an arbitrary value in their range without compromising the satisfaction of the specification. Because of the latter requirement, the resulting verifica-tion problem is non standard and, hence, novel verificaverifica-tion techniques are needed to tackle it.
Motivation
Detecting non-influential inputs can be particularly useful in testing com-plex control systems. In this context, it is common to model an undesired behavior of the control system in terms of a specification and then to detect the inputs sequence that originates that behavior. Once such a sequence has been identified, appropriate countermeasures can be taken to improve the control system design. For complex systems with many inputs, it may be the case that the identified sequence is not easy to interpret, so that it is dif-ficult to understand the cause of the undesired behavior and to improve the control system design. To ease the diagnosis of the system misbehavior, it can then be useful to identify the inputs that are actually influential and the input sequence with minimum length, since shorter sequences are usually simpler to interpret.
Resolution approaches
The problem of designing the inputs of a dynamical system so as to make its evolution satisfy a specification has been extensively treated in litera-ture, and effective solutions have been developed for a variety of classes of systems. Many of these techniques are simple derivation of the ones de-veloped in the model checking context, where the aim is typically to check if a system satisfies a certain specification, without input design. For dis-crete systems, it has been shown that checking if a disdis-crete system S sat-isfies a specification can be done by means of a reachability test on the enlarged system obtained by making S interact with the test automaton (see [1], [6], [21]) that translates the specification. The resulting reacha-bility test can then be tackled by means of efficient model checkers, like SPIN [27], UPPAAL [33], NuSMV [18], to name a few.
For continuous state systems, these model checking techniques are not di-rectly applicable, since they would require to analyze an infinite number of possible evolutions of the system. For this reason, alternative methods have been proposed in literature. Some of them rely on the computation (either exact or approximated) of the reachable set of the system under test, so as to consider in a compact way all its infinite possible evolutions (see [5], [10], [23], [32], [36], [42]). Other common approaches are based on abstracting the continuous system to a discrete one (by means, for exam-ple, of a bisimulation [4]), and then analyzing the latter via model checking techniques (see [24], [29], [31], [40]). Many of these methods can be ex-tended to the class of hybrid systems, i.e., systems with interacting discrete and continuous dynamics (see [2], [10], [22], [35]).
specifically rely on any of the methods that can be found in literature but has been strongly influenced by other works on related topics like [10], [42]. In particular, the techniques that we develop are based on optimization, that appears to be the most suitable approach to address the requirement of max-imizing the number of non-influential inputs.
Contributions and structure of the thesis
The thesis is organized as follows:
• In Chapter 2 we focus on the class of linear systems and formulate an approach for the detection of non-influential inputs. In particular, we introduce an appropriate parametrization of the inputs so that some of them are treated as actual control variables and the others as distur-bances taking an arbitrary value in their range (non-influential inputs). We then enforce the specification while maximizing the number of in-puts that are treated as disturbances. Two approaches are developed: one based on an open loop scheme and one based on a compensation scheme. In the latter, we introduce a parametrization that allows the influential inputs to depend on the non-influential ones. Interestingly enough, this approach finds application in the security of networked control systems, and, in particular, in the detection of the minimum number of inputs that need to be protected in case of attack for guar-anteeing the satisfaction of a safety/reachability specification. In the same chapter, a comparison between the two approaches developed for the linear case is also carried out.
• In Chapter 3 we consider the class of Piecewise Affine (PWA) sys-tems. For these systems, we first show how to compute a minimum length inputs sequence that enforces the specification, and then de-velop an approach for the maximization of non-influential inputs. As for the latter, we start by showing that extending the method devel-oped for linear systems to PWA systems leads to too conservative re-sults and we then propose a new method that arises from a geometrical reinterpretation of the problem.
• In Chapter 4 some techniques to reduce the computational complex-ity of the methods proposed in Chapter 3 are presented. In the same chapter we also describe a technique to perform model order reduc-tion of a PWA system, that is based on an observability-like analysis. The developed technique is such that the input/output behavior of the
system is preserved and appears less involved than the ones already present in the literature for continuous time PWA.
• In Chapter 5 we show the effectiveness of the methods discussed in Chapter 3 and Chapter 4 on some numerical examples, taken from the real case study of an avionic computer testing.
CHAPTER
2
Linear case
In this chapter we address the problem of designing the control input for a discrete time linear dynamical system so as to make its state reach a target set in some finite time with an additional requirement: we look for a solu-tion where only few input variables need to be set to some specific value (influential inputs), whereas the others can take an arbitrary value within their admissible range without compromising the desired reachability con-dition (non-influential inputs). The non-influential input variables remain free to be set and can eventually be used to satisfy further objectives be-sides reachability (multi-objective optimization). Note that the described input design problem is not standard and cannot be expressed easily as an optimization problem. In this chapter we propose two different approaches for the detection of non-influential inputs. The first one, based on an open loop control scheme, is presented in Section 2.1 whereas the second one, based on a compensation scheme, is presented in Section 2.2.
2.1
Non-influential inputs detection for linear systems: an open loop schemeIn this section, we propose a solution to the considered input design prob-lem that rests on an appropriate parametrization of the input variables as set-valued signals, and show that this parametrization allows to reformulate the problem as a robust optimization program. In turn, if the target set is a polytope, the robust optimization program reduces to a Linear Program-ming (LP) problem for linear systems, hence solutions can be effectively computed with LP solvers, like CPLEX [20].
The rest of the section unfolds as follows. In Section 2.1.1, we formulate the problem as a robust optimization problem. A resolution methodology is then proposed that finally leads to reformulate it as an LP problem to be solved. Section 2.1.2 presents some numerical examples.
2.1.1 Problem formulation and resolution Consider a discrete time linear system
x(k + 1) = Ax(k) + B1u1(k) + · · · + Bmum(k), (2.1)
where the evolution of the state x ∈ Rn is affected by m scalar control inputs ui, i = 1, . . . , m, taking values within the intervals [ui, ui], i =
1, . . . , m.
Our goal is to design the inputs ui, i = 1, . . . , m so as to steer the state
x of the system to some convex set Xf ⊂ Rnat a certain time T , starting
from a given initial condition x(0) = x0. We look for a solution where only
a limited number p ≤ m of inputs have to be set to some specific value in order to reach the target set Xf at time T (influential inputs), whilst the
other m − p inputs can take arbitrarily values within their whole admissible range (non-influential inputs).
To this purpose, we treat each input ui as a set-valued signal whose range
has to be maximized while satisfying the reachability specification. More precisely, for each i = 1, ..., m, we parameterize uias follows
ui(k) = (1 − βi)˜ui(k) +
ui+ ui
2 βi+
ui− ui
2 βiwi(k), (2.2) k = 0, ..., T − 1, where wi is a set-valued auxiliary signal taking values in
[−1, 1], whereas βiand ˜uiare optimization variables to be set. In particular,
βi ∈ [0, 1] is a scalar parameter and ˜ui is a single-valued signal taking
scheme Note that the range Ri(k) ⊆ [ui, ui] for ui(k) is jointly determined by βi
and ˜ui(k) as follows
Ri(k) = [˜ui(k) + βi(ui− ˜ui(k)), ˜ui(k) + βi(ui− ˜ui(k))],
and collapses to the singleton [˜ui(k), ˜ui(k)] when βi = 0, whereas it
coin-cides with the whole interval [ui, ui] when βi = 1. Figure 2.1 depicts the
case when βi = 0.5.
Figure 2.1: Range Ri(k) for ui(k) for a given ˜ui(k) when βi= 0.5.
The goal of identifying the minimum number of influential inputs, while setting an appropriate value for them at the same time, can be pursued by solving the following robust optimization problem:
max {βi∈[0,1],˜ui(k)∈[ui,ui],k=0,...,T −1}mi=1 |{i : βi = 1}| (2.3) x(T ) ∈ Xf x(k + 1) = Ax(k) + B1u1(k) + · · · + Bmum(k) ui(k) = (1 − βi)˜ui(k) + ui+ ui 2 βi+ ui− ui 2 βiwi(k) ∀wi(k) ∈ [−1, 1], i = 1, . . . m, k = 0, . . . , T − 1
where |C| denotes the cardinality of set C and we are actually maximizing the number of βi’s that are equal to 1, subject to the reachability condition,
the system dynamics and the input parametrization.
Due to the non-convex nature of the cost function and the bilinear term appearing in the parametrization of the input ui (see (2.2)), computing a
solution to the robust optimization problem (2.3) is difficult, in general. We next propose an approach to reduce (2.3) to a robust convex optimiza-tion problem that can be solved efficiently if Xf is a polytope described by
a set of linear inequalities:
Xf = {x ∈ Rn: Hax ≤ Hb}. (2.4)
The same approach can be applied if an inner approximation of Xf via a
We first reparameterize ui in (2.2) by replacing the bilinear term (1 −
βi)˜ui(k) with uβ,i(k) taking values in [(1 − βi)ui, (1 − βi)ui], thus
ob-taining ui(k) = uβ,i(k) + ui+ ui 2 βi+ ui− ui 2 βiwi(k). (2.5) Accordingly, the range Ri(k) of ui(k) can be expressed as
Ri(k) = [uβ,i(k) + βiui, uβ,i(k) + βiui], (2.6)
and ˜ui(k) can be recovered through:
˜ ui(k) =
(uβ,i(k)
1−βi if βi ∈ [0, 1)
0 if βi = 1.
As for the cost function, maximizing |{i : βi = 1}| is equivalent to
enhanc-ing the sparsity of vector γ = [γ1γ2. . . γm]0with γi = 1−βiby minimizing
its `0-norm, i.e., the number of its non-zero elements. Since the `0-norm is
non-convex, we shall replace it with the `1-norm kγk1 =Pmi=1|1 − βi|, as
suggested in [16] where a discussion on possible variants with a reweight-ing of the `1-norm to better approximate the `0-norm is also provided.
Given that βi ∈ [0, 1], then, kγk1 = m −Pmi=1βi, and minimizing kγk1 is
equivalent to maximizing the functionPm
i=1βi, which is convex.
This leads to the robust optimization program
max
{βi∈[0,1],uβ,i(k),k=0,...,T −1}mi=1
m X i=1 βi (2.7) x(T ) ∈ Xf x(k + 1) = Ax(k) + B1u1(k) + · · · + Bmum(k) ui(k) = uβ,i(k) + ui+ ui 2 βi+ ui− ui 2 βiwi(k) (1 − βi)ui ≤ uβ,i(k) ≤ (1 − βi)ui ∀wi(k) ∈ [−1, 1], i = 1, . . . m, k = 0, . . . , T − 1,
which is convex since x(T ) is a linear function of the optimization variables βi and uβ,i, i = 1, . . . , m, and Xf is a convex set.
We next show how (2.7) can be solved efficiently when Xf is a polytope
scheme Let us define vectors
u(k) = [u1(k), u2(k), . . . , um(k)]0, uβ(k) = [uβ,1(k), uβ,2(k), . . . , uβ,m(k)]0, w(k) = [w1(k), w2(k), . . . , wm(k)]0, β = [β1, β2, . . . , βm]0, and U = u(0) u(1) .. . u(T − 1) , Uβ = uβ(0) uβ(1) .. . uβ(T − 1) , W = w(0) w(1) .. . w(T − 1) .
Then, the state at time T can be expressed as
x(T ) = ATx0+ BTU, (2.8)
where BT is the matrix obtained by extracting the last n rows of matrix B
defined as B = B 0 0 0 AB B 0 0 .. . ... ... ... AT −1B AT −2B . . . B , (2.9)
with B = [B1 B2 . . . Bm]. Also, equation (2.5) can be written in the
following compact form:
U = Uβ + (DW + M )β, (2.10) where we set DW = diag([a1w1(0), . . . , amwm(0)]) .. . diag([a1w1(T − 1), . . . , amwm(T − 1)]) , M = diag([µ1, . . . , µm]) .. . diag([µ1, . . . , µm]) ,
with ai = ui−ui
2 and µi = ui+ui
2 , i = 1, . . . , m.
By plugging (2.10) into (2.8), we finally get
x(T ) = ATx0+ BTUβ + BT(DW + M )β. (2.11)
As a result, the constraint x(T ) ∈ Xf with Xf given in (2.4) becomes:
HaBT HaBT(DW + M )
Uβ β
≤ Hb − HaATx0 (2.12)
and the optimization problem (2.7) rewrites as max {U(1−β)≤Uβ≤U(1−β), β∈[0,1]m} 10mβ (2.13) HaBT HaBT(DW + M ) Uβ β ≤ Hb− HaATx0, ∀W ∈ [−1, 1]mT where U = diag([u1, . . . , um]) .. . diag([u1, . . . , um]) , U = diag([u1, . . . , um]) .. . diag([u1, . . . , um]) , and 1mis a column vector of m ones.
Note that the optimization problem (2.13) is linear but semi-infinite since the number of optimization variables is finite but the number of con-straints is infinite given that constraint (2.12) has to be satisfied for any realization of the set-valued signal W . Finding a solution to a semi-infinite optimization problem is difficult in general, see e.g. [11], [12], [13], [14]. However, we can find the exact optimal solution of (2.13) with a limited computational effort thanks to its particular structure. This is explained in the following proposition.
Proposition 1. The solution to the robust optimization program (2.13) can be obtained by solving the following LP program
max {U(1−β)≤Uβ≤U(1−β), β∈[0,1]m} 10mβ (2.14) HaBT HaBTM + Ξ Uβ β ≤ Hb− HaATx0, where (Ξ)ij = kdj[(HaBT)ij, (HaBT)i j+m, . . . , (HaBT)i j+m(T −1)]0k1.
scheme Proof. Consider the i-th row of constraint (2.12) given by
(HaBT)iUβ + (HaBTDW)iβ + (HaBTM )iβ ≤ (Hb− HaATx0)i.
Note that the set-valued signal W enters only the left-hand-side of this in-equality through the term (HaBTDW)i β. The worst case is then achieved
for those values of W that maximize the term (HaBTDW)iβ. Observe
also that β is non-negative, and that each entry (HaBTDW)ij depends on
wj(0), wj(1), . . . , wj(T − 1) only, i.e., each j-th entry of the same row i
depends only on the values within [0, T − 1] of the j-th component of w. Exploiting these two facts, we can just focus on independently maximiz-ing each j-th entry of (HaBTDW)i. In turn, since (HaBTDW)ij depends
linearly on wj(0), wj(1), . . . , wj(T − 1), we can write
(HaBTDW)ij = ξij0 wj(0) .. . wj(T − 1)] , where ξij = aj[(HaBT)ij, (HaBT)i j+m, . . . , (HaBT)i j+m(T −1)]0.
Recalling that wj(k) ∈ [−1, 1], ∀k = 0, . . . , T − 1, we finally have
max
W ∈[−1,1]mT(HaBTDW)ij = kξijk1,
which concludes the proof.
Problem (2.14) is a finite LP program with a finite number of constraints, and, hence, can be easily solved by means of standard LP solvers like CPLEX [20].
Remark 1 (time-varying case). The approach would still apply with slight modifications if the system in (2.21) were time-varying. In particular, the termAT andBT in(2.14) would become:
AT 7→ T −1 Y k=0 A(k) BT 7→ "T −1 Y k=1 A(k)B(0) T −1 Y k=2 A(k)B(1) . . . B(T −1) #
whereA(i) andB(i) denote the matrices of the time varying system at time i.
2.1.2 Numerical Examples
Consider the following linear system:
x(k + 1) = 0.7 0.9 0.5 −0.2 0.8 −0.1 0 0.2 0.1 x(k) + 5 1 0.1 u1(k) + 1 2 0 u2(k) (2.15) where x ∈ R3, u1 ∈ [0.5, 1.5], and u2 ∈ [−1, 1].
Suppose that we want to steer the state x so as to reach the target set Xf
at time T = 5 starting from x(0) = [1 1 1]0.
The target set Xf is defined by the linear inequalities:
I3 −I3
x ≤30 0 1 −5 7 00. (2.16) In order to solve problem (2.14) we use YALMIP [34] with CPLEX [20] as LP solver, and obtain the following results:
β1∗ = 1, β2∗ = 0.042 u∗β,1(k) = 0, k = 0, . . . , 4 u∗β,2(k) =(−0.957, k = 0, 4
0.957 k = 1, 2, 3.
We obtain that the first input is non influential (β1∗ = 1) while the second in-put is influential and can vary in a quite small range being its corresponding β2∗ close to 0 (β2∗ = 0.042).
Figure 2.2 (a) shows the target set Xf together with an approximation
of the set that can be reach at time T by applying all input sequences in the set UT starting from x(0) = [1 1 1]0 (maximal reachable set). The approximation is computed by gridding UT and computing x(T ) for each point of the grid. Note that just a small portion of the reachable set is contained in the target set, and thus it is necessary to limit the admissible range of at least one of the inputs, as highlighted by the achieved solution. Indeed, we can compute the admissible ranges for the inputs
u1(k) ∈ [0.5, 1.5] ∀k = 0, . . . , 4,
u2(k) ∈
[−1, −0.915] k = 0, 4 [0.915, 1] k = 1, 2, 3 ,
using (2.6) with β1 = β1∗, β2 = β2∗, uβ,1= u∗β,1, and uβ,2= u∗β,2, and verify
that the set of values for x(T ) reached from x(0) = [1 1 1]0when applying all input sequences in these ranges is contained within Xf.
scheme
(a)
(b)
Figure 2.2: Maximal reachable set (green), target set Xf(red), reachable set
correspond-ing to the designed input ranges (blue).
The more the constraints defining the target set become tighter, the more the inputs become influential. This is shown in Figure 2.2 (b), which refers to a smaller target set described by:
I3 −I3
x ≤20 −4 1 −5 7 00. (2.17)
In this case, by solving problem (2.13) we get β1∗ = 0.441 and β2∗ = 0, so that both the inputs are influential.
We consider now a different linear system, described by: x(k + 1) = 0.2 0.9 0.5 −0.2 0.6 −0.1 0.8 −0.2 0.7 x(k) + 0.7 0.1 −0.7 u1(k) + −0.1 0.4 −0.9 u2(k) (2.18) where x ∈ R3, u1 ∈ [0.5, 1.5], and u2 ∈ [−1, 1], and the goal is reaching
some target set Xf at T = 4 from x0 = [0 0 0]0. In this second example we
show that each input can be non-influential, depending on Xf. As a matter
of fact, if we choose Xf as
I3 −I3
x ≤1.5 2 3.5 −0.5 1.5 50 (2.19) we obtain β1∗ = 0.08 and β2∗ = 1 so that input u2 is non influential
(Fig-ure 2.3 (a)), while, if we choose Xf as
I3
−I3
x ≤0.8 1.2 −2 0.2 −0.8 40 (2.20) we obtain β1∗ = 1 and β2∗ = 0.097 so that it is now the first input to be non influential (Figure 2.3 (b)).
2.2
Non-influential inputs detection for linear systems: acom-pensation scheme
In Section 2.1 we presented a technique based on the optimization of an open loop control input for the detection of non-influential inputs; here we present an alternative approach, where we allow the influential inputs to depend on the non-influential ones. The resulting scheme resembles the disturbance compensation scheme introduced in [25] with the difference that here the disturbance is not an exogenous signal, but it is a subset of the control inputs whose cardinality has to be maximized. In turn, we show that the problem of maximizing the number of non-influential inputs while satisfying a reachability specification can be solved by means of robust op-timization, that, in the case of polytopic target sets, reduces to a Mixed In-teger Linear Programming (MILP) problem. The obtained non-influential inputs are free to be set so as to satisfy a further objective besides reachabil-ity. This way, one obtains a multi-objective control scheme with prioritized goals: reachability first, then performance (see Figure 2.4).
Notably, the methodology proposed in this section can be used to deal with the problem of security of networked control systems. Indeed, when
scheme
(a)
(b)
Figure 2.3: Maximal reachable set (green), target set Xf(red), reachable set
correspond-ing to the designed input ranges (blue).
Figure 2.4: Control scheme with prioritized goals: reachability first (through controller Creach), then performance (through controllerCopt)
an attacker has the possibility to inject false data in the communication net-work that links the controller to the plant, one should detect the minimum number of inputs that need to be encrypted so as to guarantee a safe opera-tion of the system for any possible attack.
The section is organized as follows. In Section 2.2.1 we formulate the problem for a discrete time linear system and show how to rephrase it as a MILP problem. In Section 2.2.3 we illustrate how the proposed method-ology can be applied to the case of networked control systems security. In
the same section we also show the applicability of the approach by means of a numerical example, and present a comparative analysis with the open loop with no compensation scheme proposed in Section 2.1.
2.2.1 Problem formulation and resolution Consider a discrete time linear system
x(k + 1) = Ax(k) +
m
X
i=1
Biui(k) (2.21)
where x ∈ Rnis the state vector and u
i ∈ R, i = 1, . . . , m, are m scalar
control inputs taking values in a bounded set: ui ∈ [ui, ui] ⊂ R, i =
1, . . . , m.
By collecting all inputs in vector u(k) = [u1(k), . . . , um(k)] 0
and intro-ducing U = [u, u] where u and u are defined similarly to vector u(k), we have that u(k) ∈ U ⊂ Rm, k = 0, . . . , T − 1, and system (2.21) can be rewritten in the compact form:
x(k + 1) = Ax(k) + Bu(k) (2.22)
where B = [B1, . . . , Bm] is assumed to be full rank.
Our goal is to design a controller that is able to steer the state of the system into a target set Xf ⊂ Rn, in some finite time T . The controller
has to be designed so as to maximize the number of inputs that can take an arbitrary value in their range while guaranteeing that the reachability spec-ification is satisfied.
The controller will have then to set only the value of the influential in-puts, and the target set will be reached for any possible behavior of the influential inputs. Influential inputs are allowed to depend on non-influential inputs, which entails that the former can (partially) compensate for the latter inputs.
The problem can be formally stated as follows: max N ∈2M, g |N | (2.23) x(T ) ∈ Xf, x(k + 1) = Ax(k) + Bu(k), ui(k) = g(uj1(0), . . . , uj|N |(0), . . . , uj1(k − 1), . . . , uj|N |(k − 1)), i ∈ I, ∀ujh ∈ujh, ujh , jh ∈ N , h = 1, 2, . . . |N |, k = 0, . . . , T − 1,
scheme where M = {1, . . . , m} is the set of all input indexes, N is the set of non-influential input indexes, I = M \ N is the set of non-influential input indexes, |C| and 2C denote respectively the cardinality and the power set of set C.
Note that, in the general case, problem (2.23) is intractable because the optimization has to be performed over the space of all the possible functions g and subsets of M. Moreover, problem (2.23) is also semi-infinite, since the constraint on reaching the target set has to be satisfied for any possible realization of the non-influential inputs. For these reasons, we shall illus-trate hereafter how problem (2.23) can be rewritten in a tractable form by choosing an appropriate parametrization of g and then tackled via standard robust optimization techniques.
Input parametrization
The need of partitioning the inputs into two sets – one grouping together the influential inputs, and the other the non-influential inputs – leads to the idea of introducing m boolean variables βi (one for each input) that
identify the set to which the i-th input belongs. In particular, we propose a parametrization where βiis set equal to 1 if the corresponding i-th input is
non-influential and it is set equal to 0 otherwise. Let β = [β1, . . . , βm] 0
∈ {0, 1}m.
The i-th input is parameterized as follows:
ui(k) = γk,i(β) + k X t=0 m X j=0 θk,it,j(β) uj(t), (2.24)
where γk,i ∈ R is the open loop component and θ t,j
k,i(β) ∈ R for t =
0, . . . , k, j = 1, . . . , m are the scalar coefficients that define the depen-dency of ui(k) on the sequence of inputs uj(t). The input parametrization
in (2.24) recalls the one proposed in [25] with a main difference: here the disturbance signal on which the feedback is constructed is not an actual exogenous signal acting on the system; instead it is a subset of the whole inputs – the non-influential ones – which are not known a priori and whose number has to be maximized. Note that in (2.24) both the compensation and the open loop coefficients depend on β; this is needed to force each j-th input to be either in feedback on the other inputs (if βj = 0) or not (if
βj = 1).
depen-dency on β of θk,it,j: • k > t (βi− 1)V ≤ θ t,j k,i ≤ (1 − βi)V −βjV ≤ θk,it,j ≤ βjV ) if i 6= j, (2.25) θt,jk,i= 0 if i = j • k = t θt,jk,i= βi if i = j, (2.26) θt,jk,i= 0 if i 6= j
and the following constraint that states the dependency on β of γk,i:
(βi− 1)V ≤ γk,i≤ (1 − βi)V ∀ i, k (2.27)
where V is a large enough constant (see [7]). It is easy to verify that con-straints (2.25), (2.26) and (2.27) jointly guarantee the following facts:
1. If an input is non-influential, the feedback term and the open loop term in (2.24) vanish
2. If an input is influential, its value is determined by a linear combina-tion of the past values of the non-influential inputs and an open loop term. None of the influential input depends on other influential in-puts (including itself) or on a synchronous value of the non-influential inputs
3. If all the inputs are influential, i.e. βi = 0, i = 1, . . . , m, the
compen-sation scheme degenerates in an open loop control law.
Finally, additional constraints are introduced to enforce the parameterized inputs to belong to their corresponding bounded interval:
ui ≤ γk,i(β) + k X t=0 m X j=0 θt,jk,i(β)uj(t) ≤ ui, (2.28) k = 0, . . . , T − 1, i = 1, . . . , m.
Note that all the constraints introduced so far are linear in the design pa-rameters β, θk,it,j, and γk,i.
scheme
Reformulation as a MILP problem
In this section, we show how to reformulate problem (2.23) as a robust optimization problem and how to efficiently solve it by MILP.
If we consider a polytopic target set Xf (or an inner approximation of
the actual target set by a polytope), the reachability constraint in (2.23) can be rewritten as:
Hax(T ) ≤ Hb (2.29)
where Ha ∈ RrH×n and Hb ∈ RrH are the matrices defining the
poly-tope Xf. Exploiting (2.29) and the input parametrization in (2.24), problem
(2.23) can be formulated as:
max βi, γk,i, θk,it,j i, j = 1, . . . , m k, t = 0, . . . , T − 1 m X i=0 βi Hax(T ) ≤ Hb x(k + 1) = Ax(k) + Bu(k) (2.30) ui(k) = γk,i(β) + k X t=0 m X j=0 θk,it,j(β) uj(t) Constraints (2.25), (2.26), (2.27), (2.28) ∀u(k) ∈ U , k = 0, . . . , T − 1
Note that the optimization problem (2.30) is a robust MILP problem, since x(T ) and the constraints (2.25), (2.26), (2.27), (2.28) are linear as a func-tion of the optimizafunc-tion variables. Moreover, imposing the satisfacfunc-tion of the constraints for any possible value in time of all the inputs (both the influ-ential and the non-influinflu-ential ones) is still consistent with problem (2.23), because the parametrization is constructed so that only the non-influential inputs appear in the definition of the robust constraints.
Due to the fact that some constraints must hold irrespectively of the value taken by the non-influential inputs, problem (2.30) is a semi-infinite problem and hence it is in general not easy to solve, see e.g. [11], [12], [13], [14]. However, we can exploit the particular structure of (2.30) to find its solution with a limited computational effort. To this end, we first introduce
the following compact notations: U = [u0(0), . . . , u0(T − 1)]0, U = [u0, . . . , u0]0, U = [u¯ 0, . . . , u0]0, M = ¯ U + U 2 , F = ¯ U − U 2 , Γ = [γ 0 (0), . . . , γ0(T − 1)]0, θtk = θt,1k,1 . . . 0 .. . . . . ... θk,mt,1 . . . θt,mk,m , Θ = θ00 0 . . . 0 .. . . .. ... ... .. . . .. 0 θ0 T −1 . . . θ T −1 T −1 .
Based on these notations, the input parametrization in (2.24) simplifies to
U = ΘU + Γ (2.31)
where matrix Θ has a lower triangular structure. Similarly, constraints in (2.28) are rewritten as:
U ≤ ΘU + Γ ≤ ¯U . (2.32)
The state at time T can be expressed as:
x(T ) = ATx0+ BTU, (2.33)
where BT has been defined in (2.9).
By plugging (2.31) in (2.33) we obtain:
x(T ) = ATx0+ BT(ΘU + Γ). (2.34)
As a result, by properly rearranging terms, constraint (2.29) becomes: HaBTΘU ≤ Hb− HaATx0 − HaBTΓ (2.35)
Finally, problem (2.30) can be rewritten as follows: max β, Θ, Γ c 0 β ZaU ≤ Zb ∀U ∈ [U , ¯U ] (2.36) Constraints (2.25), (2.26), (2.27)
where c = [1, . . . , 1]0 and Za, Zbhave the following form:
Za = HaBTΘ Θ −Θ , Zb = Hb− HaATx0− HaBTΓ ¯ U − Γ −U + Γ . (2.37)
scheme Note that, as for the approach described in Section 2.1, the same formula-tion can be adopted for linear time-varying system, with slight modifica-tions (see Remark 1).
We can now prove the following proposition:
Proposition 2. The robust MILP problem (2.36) is equivalent to the stan-dard MILP problem:
max β, Θ, Γ 1 0 mβ Ψ + ZaM ≤ Zb (2.38) Constraints (2.25), (2.26), (2.27)
where each i-th element ofΨ ∈ RrH+2mT is theF -weighted `
1-norm of the
i-th row of Za, that is:
Ψi = mT X j=1 Zai,jFj
Proof. By introducing an auxiliary variable W ∈ W = [−F, F ] and set-ting U = M + W , the robust constraint on the inputs in (2.36) can be equivalently rewritten as:
max
W ∈WZaW ≤ Zb− ZaM. (2.39)
The worst-case value of the left-hand side in (2.39) is found on a vertex of W and, since each element of F is positive, its value is given row-by-row by:
max
W ∈W[Za]iW = k [Za]i ∗ F k1 = k[Za]ik1,F = Ψi (2.40)
where [P ]idenotes the i-th row of matrix P and * denotes the element-wise
product.
Let β∗, Θ∗, and Γ∗denote the solution to problem (2.38).
Note that the input parametrization presented in this paper can be recast as a state feedback policy, by reconstructing the past values of the non-influential inputs as the difference between the predicted and actual state at each time step, i.e.:
un−in(k) = B †
n−in(x(k + 1) − Ax(k) − Binuin(k)), (2.41)
where un−inand uinare the vectors of non-influential and influential inputs,
Bn−in and Bin are the corresponding sub-matrices of the full rank matrix
marked as influential, the feedback scheme degenerates in the open loop control law Γ∗.
Remark 2. The techniques described in the current section and in Section 2.1 can be easily extended to other specifications besides reachability. In particular, the same methodology can be used in the case of safety specifi-cations where the aim is to check if the entire state evolution of the system belongs to a safe set, i.e., ifHa,kx(k) ≤ Hb,k,k = 1, . . . , T . In this case it
is enough to do the following replacement in(2.30) and (2.14): BT 7→ B
AT 7→ [A0, . . . , AT0]0
Ha 7→ diag([Ha,1, . . . , Ha,T]).
and the proved results remain valid. Clearly, analogous slight modifica-tions can be used if the specification involves the output or a linear combi-nation of state and output. Moreover, it is possible to extend the approach to any specification expressible as a propositional logic formula composed by linear clauses on the state or the output (like, for example, a reachability specification with two distinct target sets); in order to do so, it is enough to translate the formula as a set of mixed integer inequalities (see [7]), and then apply the techniques discussed above.
Note that with respect to the approach described in Section 2.1, here we lose the additional information on the size of the range on which an input is influential. Indeed, the parametrization (2.24) determine an unique value for the influential inputs, that can not be interpreted anymore as set-valued signals as we did in Section 2.1 (see Figure 2.1). Nonetheless, we will show in the next section that this approach is able to detect more non-influential inputs than that without the compensation term. In Section 2.2.3 we show how the methodology proposed can be used to deal with security issues in networked control systems.
2.2.2 Comparison with the open loop approach
We now show that the technique proposed in this Section leads to better results, in terms of number of non-influential inputs, with respect to the one proposed in Section 2.1. Given the same specification, denote with J2∗ the optimal solution of (2.38), and with J1∗ the optimal solution of (2.14) ob-tained by restricting the β variables to be binary. Then, J2∗ and J1∗represent the number of non-influential inputs detected by the compensation scheme approach, and the open loop scheme approach, respectively.
scheme Proposition 3. J2∗ ≥ J∗
1
Proof. If we restrict the β variables in (2.14) to be binary, then problem (2.38) and problem (2.14) share the same constraints and cost functions, and differ just in terms of the input parametrization adopted. The proposi-tion is then easily proved by noticing that the input parametrizaproposi-tion adopted in problem (2.38) is richer than the one adopted in problem (2.14), so that the optimal solution of the latter is always feasible for the former.
2.2.3 Application to networked control system
In a typical networked control system the plant is connected to the con-troller through a communication network, that carries the input signal u(k) and the output signal y(k) (see Figure 2.5). Because the data channels are usually unprotected, the control system is vulnerable to threats (see [17]); in particular, its safe operation can be jeopardized by the malicious intrusion of an attacker, that may inject false data in the communication network, causing a discrepancy between the expected input/output signals and the actual ones.
Figure 2.5: Schematic view of a networked control system. The plant and the controller are connected through a communication network that can be attacked.
Here we consider the case of an attacker whose intent is steering the state of the system out of a safe set by injecting false data in the input data channel. One way of modeling the attacker intrusion is via a disturbance ∆u(k) that enters additively on the output u(k) of the controller so that the actual input entering the system is ˜u(k) = u(k) + ∆u(k) (see [41]). We can
Figure 2.6: Control scheme in the case of attack: the data injected by the attacker is reconstructed on the base of the measured state and used to calculate the influential inputs value. The satisfaction of the reachability specification is guaranteed for any possible attack, since the adversary has access only to the non-influential inputs data channels
equivalently assume that the attacker is the one who determines the input ˜
u(k) to be injected in the system.
A typical approach to minimize the risk is to protect the actuators data channels via encryption (see [41]), so that the attacker can no longer have access to the communication channel. Since carrying out the encryption of many data channels can be expensive, one would like to minimize the num-ber of signals that need to be encrypted. This can be done by applying the methodology explained in Section 2.2.1 as an offline procedure to identify the minimum number of inputs that need to be protected so as to guarantee the safe operation of the controlled system. Once the non-influential inputs have been detected and the influential ones have been encrypted, the con-trol scheme in Figure 2.4 becomes the one in Figure 2.6 where R stands for the reconstruction procedure in (2.41). Note that even though it is not possible anymore to choose an optimal value for the non-influential inputs, it is still guaranteed that the closed loop system will satisfy the reachability specification for any possible action of the attacker.
2.2.4 Numerical example
We consider the benchmark example in [28] and apply the methodology developed in this section. The system is composed of four tanks, whose levels are controlled by means of two pumps. The non-linear fourth order model of the quadruple tank system with state h = [h1 h2h3 h4]0 and input
scheme v = [v1 v2]0 has the following form:
˙h1(t) = − a1 A1 p 2gh1(t) + a3 A1 p 2gh3(t) + γ1k1 A1 v1(t), ˙h2(t) = − a2 A2 p 2gh2(t) + a4 A2 p 2gh4(t) + γ2k2 A2 v2(t), ˙h3(t) = − a3 A3 p 2gh3(t) + (1 − γ2)k2 A3 v2(t), (2.42) ˙h4(t) = − a4 A4 p 2gh4(t) + (1 − γ1)k1 A4 v1(t).
The model is linearized in correspondence of two operating points P− and
P+ obtained by feeding the non-linear system (2.42) with the constant
in-puts ¯v− = [3, 3]0 and ¯v+ = [3.15, 3.15]0 respectively. The linearized
dy-namics is: ˙x(t) = − 1 T1 0 A3 A1T3 0 0 −1 T2 0 A4 A2T4 0 0 −1 T3 0 0 0 0 − 1 T4 x(t) + γ1k1 A1 0 0 γ2k2 A2 0 (1−γ2)k2 A3 (1−γ1)k1 A4 0 u1(t) u2(t) (2.43) where x and u are the state and input variables of the linearized system representing the difference between h, v and their corresponding equilibria. The value of each coefficient in (2.43) is reported in Table 2.1 for both the operating points P− and P+. In order to apply our method we first
T1 T2 T3 T4 A1,3 A2,4 γ1 γ2 k1 k2
P− 62 90 23 30 28 32 0.7 0.6 3.33 3.35
P+ 63 91 39 56 28 32 0.43 0.34 3.14 3.29
Table 2.1: Coefficients of the linearized models
discretize system (2.43) by applying a constant input in the interval [t, t + Ts), where Ts = 4 is the sample time. As for the time horizon and the
safe set, we respectively choose T = 50 discrete time steps and Xf :=
{x ∈ R4 : kxk
∞≤ 5}. The safety specification is then given by x(k) ∈ Xf,
k = 0, . . . , T . Both the inputs of the linearized system are bounded in the interval [−1.5, 1.5].
Figure 2.7: Operating point P−: inputu2compensates for inputu1, which is set to a bad
realization able to steer the system outside of the target set if not properly counteracted.
Solving problem (2.38) leads to β∗ = [1, 0] for both the linearized mod-els, meaning that if we set u2to the value given by the optimal
parametriza-tion Θ∗and Γ∗, u1is non-influential. This is shown in Figure 2.7 and Figure
2.8 where, in both cases, we set input u1to a specific realization that would
steer the state of the system outside the safe set if Θ were set to zero instead of Θ∗. This is shown in Figure 2.9 for the operating point P−. The
com-putation was performed on a laptop computer running CPLEX [20] over YALMIP [34].
For comparison, we apply the technique for non-influential inputs de-tection described in Section 2.1 to the quadruple tank problem: we obtain in both P−and P+cases β∗ = [0, 0], meaning that u1 and u2are marked as
influential. This is due to the fact that there exists no open loop sequence for u1that keeps the state in the safe set Xf for any possible behavior of u2,
scheme
Figure 2.8: Operating point P+: inputu2compensates for inputu1, which is set to a bad
realization able to steer the system outside of the target set if not properly counteracted.
Figure 2.9: Operating point P−: inputu1is able to steer the state of the system outside
of the safe set when inputu2 is set equal to 0. Similar results can be obtained for
CHAPTER
3
Piecewise Affine case
In this chapter we deal with the class of PieceWise Affine (PWA) systems. The problem that we address is the detection of non-influential inputs to-gether with the additional requirement of satisfying a reachability specifi-cation in the minimum number of time steps. In order to deal with both the requirements, we split the problem in two steps: first we compute the mini-mum number of steps needed to satisfy the specification, and then we solve the problem of detecting the non-influential inputs with the fixed time hori-zon computed in the previous step. As for the latter, we show that extending the methods described in Chapter 2 provides too conservative results, and we therefore develop a novel approach to tackle the hybrid nature of the considered class of systems.
The chapter is organized as follows: in Section 3.1, we introduce the class of PWA systems and we recall their equivalence with the class of Mixed Logical Dynamical (MLD) systems. In Section 3.2 we discuss the problem of detecting the non-influential inputs while satisfying a specification in the minimum number of steps, and we propose a two steps approach to solve it. In Section 3.3 the first step of the approach is presented, whereas in Section 3.4 we deal with the problem of detecting the non-influential inputs for a PWA system with a fixed time horizon specification.
3.1
Modelling context3.1.1 Piecewise Affine systems
A Piecewise Affine (PWA) system is described by the following state-space equations: x(k + 1) = Aix(k) + Biu(k) + fi y(k) = Cix(k) + Diu(k) + gi forx(k) u(k) ∈ Ai, (3.1)
where x ∈ X ⊆ Rnis the state, u ∈ U =
×
mi=1[ui, ui] is the input, y ∈ Rpis the output and fi, gi are constant vectors. Note that we assume that the
input is bounded.
System (3.1) is said to be well posed if the collection of sets {A}si=1forms a polyhedral subdivision of the space X × U , that is if ∪si=1Ai = X × U ,
each Aiis of dimension n + m, and the intersection Ai∩ Aj, i 6= j, is either
empty or a common proper face of both polyhedra.
The well posedness assumption guarantees that the evolution of system (3.1) is always well-defined. The single polyhedron Ai is of the form:
Ai = (x, u) :LiaxLiaux u ≤ Li b . (3.2)
Throughout the dissertation we will implicitly assume that the systems we deal with are all well posed. Even though this is not a strong assumption – especially in the case of PWA models that derive from real systems –, a numerical test for checking if a system is well posed can be found in [8]. We will refer to each polyhedron Aias a mode of the PWA system, and we will
say that the j-th mode is active at time k if [Lj
axLjau]x0(k) u0(k)
0 ≤ Ljb. Note that, since the modes define a partition of the state-input space, there is one and only one active mode at a time. We can now give the following definition.
Definition 3.1.1 (Switching sequence). The state evolution of (3.1) is given by: x(k) = k−1 Y j=0 Aijx(0) + k−1 X j=0 k−1 Y h=j+1 Ai(h) !
Bi(j)u(j) + fi(j)
!
, (3.3) wherei(t) ∈ {1, . . . , s} is the index of the active mode at time t, and, hence, the pairx(t), u(t) satisfies [Li(t)ax Li(t)au ] [x(t)0, u(t)0]0 ≤ Li(t)b . The ordered
collection of modesI = {i(0), i(1), . . . , i(k − 1)} ∈ {1, . . . , s}k is called switching sequence.
3.1.2 Mixed Logical Dynamical systems
A Mixed Logical Dynamical (MLD) system has the following form: x(k + 1) = Ax(k) + Buu(k) + Bδδ(k) + Bzz(k) + Baf f
y(k) = Cx(k) + Duu(k) + Dδδ(k) + Dzz(k) + Daf f (3.4)
Exx(k) + Euu(k) + Eδδ(k) + Ezz(k) ≤ Eaf f
where x ∈ Rnc× {0, 1}nlis the hybrid state composed of both continuous
and binary variables, y ∈ Rp is the output, and u = [u1, u2, . . . , um]0 is
the input vector, which comprises m scalar control inputs ui ∈ [ui, ui],
i = 1, . . . , m. As for δ and z, they are respectively binary and continuous auxiliary variables: δ ∈ {0, 1}rl and z ∈ Rrc. For MLD systems, the
assumption of well-posedness translates into the uniqueness of the solution of the inequalities in (3.4), i.e., given a state-input pair it is always possible to find a unique corresponding value for the auxiliary variables δ and z. Under the well posedness assumption it is always possible to convert a MLD system in an equivalent PWA system. This is stated in the following theorem.
Theorem 1 (MLD and PWA are equivalent). Consider generic state, in-put and outin-put trajectoriesx(k), u(k), y(k) of a MLD system (3.4). Then there exists a polyhedral subdivision{A}s
i=1of the state-input space
X U = {(x, u) ∈ Rn× Rm : ∃δ ∈ {0, 1}rl, z ∈ Rrc :
Exx(k) + Euu(k) + Eδδ(k) + Ezz(k) ≤ Eaf f},
and 6-tuples(Ai, Bi, Ci, Di, fi, gi), i = 1, . . . , s such that x(k), u(k),
y(k) satisfy (3.1).
The proof of Theorem 1 is based on the equivalence between proposi-tional logic formulas and linear inequalities and can be found in [7]. The idea behind the translation from the PWA form to the MLD form is to in-troduce auxiliary variables δ and z that respectively capture which of the original PWA mode is active, and the dynamics associated to that mode. This is done by means of big-M techniques that lead to the linear inequali-ties in (3.4) (see [7]).
3.2
Problem formulationConsider a PWA system of the form in (3.1) and a reachability specification that requires the state at time T to belong to a polytopic target set Xf:
where Ha and Hb denote the matrices of the H-representation of Xf. The
problem that we will address in this Chapter is the following: max N ∈2M |N | x(T∗) ∈ Xf, x(k + 1) = Aix(k) + Biu(k) + fi, for x(k) u(k) ∈ Ai (3.6) ∀ujh ∈ujh, ujh , jh ∈ N , h = 1, 2, . . . |N |, k = 0, . . . , T∗− 1, where
T∗ = infT ∈ N+ : ∃ {u(0), u(1), . . . u(T − 1)} : x(T ) ∈ Xf , (3.7)
and |C| denotes the cardinality of set C. Problem (3.6) aims at identifying the non-influential inputs for a PWA system, while satisfying the specifica-tion in the minimum number of time steps. As discussed in Chapter 1, the latter is an important additional requirement in the testing of avionic con-trol systems and, in general, in all verification contexts; indeed, when an undesired behavior of the system is formulated as a specification, it is valu-able to find the shortest input sequence that generates that behavior, because shorter sequences are usually easier to interpret (see [38]). Then, once that the cause of the undesired behavior has been understood, appropriate coun-termeasures can be then taken to improve the design of the tested system. Our approach to solve problem (3.6) is based on two steps: we first identify the minimum number of time steps needed to satisfy the specification and then we compute the number of non-influential inputs in that time horizon. Note that finding the minimum length feasible time horizon would not lead to identify the maximum number of non-influential inputs. This is formally proved in Proposition 4.
Proposition 4. The number of non-influential inputs may increase with the time horizon length.
Proof. By contradiction, assume that the number of non-influential inputs is decreasing with the length of the time horizon. We denote with QT the
number of non-influential inputs detected when the problem is defined on a time horizon [0, T ]. The aim is to show that it maybe the case that QT <
QT +l, l ∈ N+. To this end we consider the linear system described by the
following dynamics:
starting from the initial condition x(0) = x0. The scalar inputs u1 and
u2 are bounded in the intervals [−u1, u1] and [−u2, u2], respectively. We
assume that u1 > 3u2. Consider the following specification: x(T ) ≥ x0+
u1+u2. When T = 1 the only way to satisfy the specification is to apply the
input sequence u(0) = [u1, u2] 0
= [u1, u2] 0
so that Q1 = 0. On the other
hand when T = 2, by choosing u1(0) = u1and u1(1) = u1we obtain:
x(2) = x0+u1(0)+u2(0)+u1(1)+u2(1) = x0+2u1+u2(0)+u2(1). (3.8)
so that the specification is satisfied if:
x0+ 2u1 + u2(0) + u2(1) > x0 + u1+ u2,
that becomes
u1 > u2− u2(0) − u2(1),
which is satisfied for any value of u2(0) and u2(1), given that u1 > 3u2;
hence we have that Q2 = 1 > Q1, which concludes the proof.
In the next section we show how to deal with the computation of the minimum time needed for satisfying the specification, whereas in Section 3.4 we extensively deal with the detection of non-influential inputs.
3.3
Satisfying the specification in minimum timeIn this section we look for T∗ satisfying
T∗ = infT ∈ N+ : ∃ {u(0), u(1), . . . u(T − 1)} : x(T ) ∈ Xf , (3.9)
Given that we work in a discrete time framework, T∗ can be computed via an iterative procedure that at each iteration increases the time horizon by 1 and checks whether there exists an input sequence that allows to reach the target set Xf in that time horizon. To this purpose, we use the MLD
formulation of the original PWA system.
We express the state of system (3.4) at time T as:
x(T ) = ATx0+ BuTU + BδT∆ + BzTZ (3.10)
where
U = [u0(0), u0(1), . . . , u0(T )]0, ∆ = [δ0(0), δ0(1), . . . , δ0(T )]0, Z = [z0(0), z0(1), . . . , z0(T )]0,
The inequality in (3.4) can then be expressed as: Ex(Ax0+ BuU + Bδ∆ + BzZ) + EuU + Eδ∆ + EzZ ≤ Eaf f, (3.11) where A = I A A2 .. . AT −1 , Bi = 0 . . . 0 Bi 0 ABi Bi ... .. . . .. AT −2B i . . . Bi 0 i = u, δ, z, Ei = diag([Ei, . . . , Ei]), i = x, u, δ, z, and Eaf f = [E 0 af f, . . . , E 0 af f] 0. By plugging (3.10) in (3.5) we get: Ha(BuTU + BδT∆ + BzTZ) ≤ Hb− ATx0. (3.12)
An input sequence that drives the state in the specification at time T can be then computed by means of the following Mixed Integer Feasibility Test (MIFT): min U ∈UT, ∆∈{0,1}T , Z∈RnT 0 (3.13) H aBuT HaBδT HaBzT Eu+ ExBu Eδ+ ExBδ Ez+ ExBz U ∆ Z ≤ H b− ATx0 Eaf f − ExAx0 .
Finally, the procedure that computes the minimum number of time steps needed to satisfy the specification is summarized in Algorithm 1.
Algorithm 1 Minimum time for satisfying the specification
Input: System in MLD formulation, target set Xf, initial condition x(0) = x0
1: initialize T = 0
2: repeat
3: T ← T + 1
4: Solve the mixed integer feasibility test (3.13)
5: until Problem (3.13) is feasible
6: T∗← T
Output: Minimum time for reaching the specification T∗
Note that, in the general case, if the specification is satisfied at some time T1 then it is not guaranteed to be satisfied at time T > T1, so that a
3.4
Computing non-influential inputs for a PWA systemOnce that the minimum number of time steps needed to satisfy the specifi-cation has been computed, we can deal with the detection of non-influential inputs. This section is organized as follows: in Section 3.4.1 we show that extending the methodology proposed in Chapter 2 to the PWA case leads to conservative results. Prompted by this consideration, in Section 3.4.2 we exploit duality theory to formulate a new approach, that, despite exact, turns out to be intractable from a computational point of view. Finally, in Section 3.4.3 we propose a relaxation of the exact approach that, although still conservative, leads to better result than the approach described in Sec-tion 3.4.1. Throughout the secSec-tion some numerical examples are given to clarify the explanation.
3.4.1 Extension of the approach proposed for the linear case
The approach proposed in this section aims at extending to the PWA case the approach discussed in Section 2.1 for linear systems. We consider a PWA of the form (3.1) and a specification defined by
Hax(T∗) ≤ HB, (3.14)
where T∗ satisfies (3.9); our goal is identifying the non-influential inputs that lead the state to satisfy (3.14).
Problem formulation on a fixed switching sequence
For a fixed switching sequence the dynamics of the PWA is linear, although time-varying, hence, the technique in Section 2.1 can be applied (see Re-mark 1).
Let us consider a fixed switching sequence ¯I = {i0, i1, . . . , iT∗−1}. The
state of system (3.1) on the time interval [0, T∗] with initial condition x(0) = x0, can be written as:
where X = x(0) x(1) x(2) .. . x(T∗) , U = u(0) u(1) u(2) .. . u(T∗− 1) , F( ¯I) = fi0 fi1 fi2 .. . fiT ∗−1 , A( ¯I) = I Ai0 Ai1Ai0 .. . QT∗−1 j=0 Aij , B( ¯I) = 0 0 0 0 0 Bi0 0 0 0 0 Ai1Bi0 Bi1 0 0 0 Ai2Ai1Bi0 Ai2Bi1 Bi2 0 0 .. . ... ... . .. ... QT∗−1 j=1 AijBi0 QT∗−1 j=2 AijBi1 QT∗−1 j=3 AijBi2 . . . BiT ∗−1 , G( ¯I) = 0 0 0 0 0 I 0 0 0 0 Ai1 I 0 0 0 Ai2Ai1 Ai2 I 0 0 .. . ... ... . .. ... QT∗−1 j=1 Aij QT∗−1 j=2 Aij QT∗−1 j=3 Aij . . . I .
The constraints on the state-input pairs to the modes activation in the switch-ing sequence can be written in the followswitch-ing compact form:
L( ¯axI)X + L( ¯auI)U ≤ L( ¯bI), (3.16) where L( ¯axI) = Li0 ax Li1 ax . .. LiT ∗−1 ax , L( ¯auI) = Li0 au Li1 au . .. LiT ∗−1 au ,
L( ¯bI) = Li0 b Li1 b .. . LiT ∗−1 b . By plugging (3.15) in (3.16) we get: L( ¯axI)(A( ¯I)x0+ B( ¯I)U + G( ¯I)F( ¯I)) + L( ¯auI)U ≤ L ( ¯I) b , which becomes: M( ¯aI)U ≤ M( ¯bI), (3.17) where M( ¯aI) = L( ¯axI)B( ¯I)+ L( ¯auI), M( ¯bI) = L( ¯bI)− L( ¯I) axA ( ¯I)x 0− L( ¯axI)G ( ¯I)F( ¯I).
From now on, we will say that system (3.1) evolves in the switching se-quence ¯I if equation (3.17) is satisfied.
We also define the set A AAi = n U ∈ UT∗ : M(Ii) a ≤ M (Ii) b o . (3.18)
Equation (3.14) can be rewritten as: Ha(A ( ¯I) T∗x0+ B ( ¯I) T∗U + G ( ¯I) T∗F( ¯I)) ≤ Hb, (3.19) where A( ¯TI)∗, B ( ¯I) T∗ and G ( ¯I)
T∗ are obtained by extracting the last n rows of
matrices A( ¯I),B( ¯I) and G( ¯I), respectively. We can rewrite equation (3.19) in the compact form:
S( ¯aI)U ≤ S( ¯bI), (3.20) where: S( ¯aI) = HaB ( ¯I) T∗, S( ¯bI) = Hb− HaA ( ¯I) T∗x0 − HaG ( ¯I) T∗F( ¯I).
We also define the set Sp SpSpi = {U ∈ UT ∗ : S(Ii) a U ≤ S (Ii) b }. (3.21)
We now consider the following linear feasibility test: min U ∈ [U , ¯U ] 0 S( ¯aI)U ≤ S( ¯bI) (3.22) M( ¯aI)U ≤ M( ¯bI)
where U = [u0, . . . , u0]0 and ¯U = [u0, . . . , u0]0. A solution of (3.22) is an in-put sequence {u(0), u(1), . . . u(T∗− 1)} that drives the state of the system into the target set Xf by keeping its evolution in the switching sequence ¯I.
Note that, depending on the switching sequence, problem (3.22) may be unfeasible. We will say that the switching sequence ¯I is unfeasible (feasi-ble) if problem (3.22) is unfeasible (feasi(feasi-ble).
We now introduce a parametrization of the input that resembles the one adopted in Section 2.1, with the difference that we allow the βi variables
in (2.5) to depend on time. More precisely, the i-th input at time k is parametrized as: ui(k) = uβ,i(k) + ui+ ui 2 βi(k) + ui− ui 2 , βi(k)wi(k). (3.23) where uβ,i(k), wi(k) and βi(k) denote the i-th element of the column vector
uβ(k), w(k) and β(k), respectively. Regarding the role of uβ,i(k), wi(k)
and βi(k) the reader is referred to Section 2.1 since parametrization (3.23)
is essentially the same as (2.5) with an extra degree of freedom given by the dependency of β on time. Again we can express the range Ri ⊆ [ui, ui] of
the i-th input at time k as
Ri(k) = [uβ,i(k) + βi(k)ui, uβ,i(k) + βi(k)ui] . (3.24)
Considering a different value of β for each time step is needed to avoid that the overall solution is conditioned by a single time step. In fact, if we had a constant βi, the i-th input range Ri in (3.24) would be limited by the
smallest interval to which the i-th input has to belong in order to make the system evolve in the considered switching sequence. This is not an issue in the case of the linear system addressed in Section 2.1 since there are no further possible evolutions (associated with other switching sequences) to explore.
Parametrization (3.23) is rewritten in a compact form as:
where: Uβ = uβ(0) uβ(1) .. . uβ(T∗− 1) , W = w(0) w(1) .. . w(T∗− 1) , βββ = β(0) β(1) .. . β(T∗− 1) , (3.26) D = diag u−u2 . .. diag u−u2 , M = diag u+u2 . .. diag u+u2 . (3.27) By plugging (3.25) in the constraints (3.17) and (3.20) we get:
M( ¯aI)Uβ+ M( ¯aI)(D diag(W ) + M )βββ ≤ M ( ¯I) b S( ¯aI)Uβ+ S( ¯aI)(D diag(W ) + M )βββ ≤ S ( ¯I) b
so that the constraint that forces the evolution in the switching sequence ¯I becomes: h M( ¯aI) M( ¯aI)(D diag(W ) + M )iUβ βββ ≤ M( ¯bI), (3.28) and the corresponding specification constraint becomes:
h S( ¯aI) S( ¯aI)(D diag(W ) + M )iUβ β ββ ≤ S( ¯bI). (3.29) Finally, following the developments in Section 2.1 we formulate the robust linear optimization problem for the switching sequence ¯I:
max
{(1−diag(βββ))U ≤Uβ≤(1−diag(βββ)) ¯U , βββ∈[0,1]mT ∗}
10mT∗βββ " M( ¯aI) M( ¯aI)(D diag(W ) + M ) S( ¯aI) S( ¯aI)(D diag(W ) + M ) # Uβ β β β ≤ " M( ¯bI) S( ¯bI) # (3.30) ∀W ∈ [−1, 1]mT∗.
Proposition 5. The solution to the robust linear optimization problem (3.30) can be obtained by solving the following LP:
max
{(1−diag(βββ))U ≤Uβ≤(1−diag(βββ)) ¯U , βββ∈[0,1]mT ∗}
10mT∗βββ " M( ¯aI) M( ¯aI)M + Ω S( ¯aI) S( ¯aI)M + Υ # Uβ βββ ≤ " M( ¯bI) S( ¯bI) # , (3.31)
where each element of Ω and Υ is given by (Ω)i,j = |(M( ¯aI))i,j|Di,j,
(Υ)i,j = |(S( ¯aI))i,j|Di,j.
Proof. The proposition can be proved by following the same argument of Proposition 1 and noticing that M( ¯aI)and D are both diagonal matrices.
We denote with Uβ∗ and βββ∗ the optimal solution to problem (3.31). We can construct the corresponding multi-dimensional range for U :
R( ¯I) =U∗ β + diag(βββ ∗)U , U∗ β + diag(βββ ∗)U (3.32) where in (3.32) we stress the dependency of the range on the switching sequence I. The set R( ¯I) ⊆ UT∗is a mT∗-dimensional box in the enlarged
input space UT∗and can be interpreted as the maximum-perimeter box that can be inscribed in the set AAAI¯∩ SpSpSpI¯(see Figure 3.1).
Figure 3.1: R( ¯I)is the maximum-perimeter box that can be inscribed inAAA ¯ I∩ SpSpSpI¯
The j-th input is non-influential if all the corresponding optimal βj∗(k), k = 0, . . . , T∗− 1 are equal to 1, or, equivalently, if
P{j}(RI¯) =uj, uj
T∗
where PJ(Z) ⊆ RT∗
denotes the projection of the set Z ⊆ RmT∗ on the subspace defined by the inputs uj, j ∈ J . Equation (3.33) shows that, in
general, considering only one switching sequence is restrictive, since the size of R( ¯I) is limited by constraint (3.17) that guarantees that the system
evolves in the switching sequence ¯I. In order to overcome this issue, we need to explore all the feasible switching sequences, and solve the LP prob-lem (3.31) for each one of them. The obtained ranges can then be patched together so as to satisfy condition (3.33) for as many inputs as possible.
Iterative exploration of the switching sequences
In the iterative exploration of the switching sequences we make use of the MLD form of the PWA system.
Solving the mixed integer feasibility test (3.13) with T = T∗ provides a feasible value for the binary vector ∆ that define a switching sequence I. The corresponding switching sequence can be obtained by looking at the MLD inequalities in (3.4) that define the binary auxiliary variable δ. We denote with ∆∗1 the solution of the first run of the MIFT (3.13). In order to find a new feasible switching sequence ∆∗2, we rerun the MIFT (3.13) with an added constraint on ∆ that forces the optimizer to find a solution different from ∆∗1, i.e.:
(2∆∗1 − 1rlT∗)
0
∆ ≤ ||∆∗1||1− 0.5. (3.34)
Constraint (3.34) is satisfied for all the possible combinations of binary vector in the ∆ space, except ∆∗1. Indeed, constraint (3.34) defines an hy-perplane that cuts the ∆ space in two regions, one of which containing only the point ∆∗1 (see Figure 3.2 for a two dimensional example). Once that the new value for the binary vector, ∆∗2, has been computed, the procedure goes on iteratively, as it is summarized in Algorithm 2.
Given the set of all feasible ∆’s, ∆feasible, we determine the collection of
all the feasible switching sequences SS = I1, . . . , I|∆feasible| , by
translat-ing each ∆j ∈ ∆feasible, j = 1, . . . , |∆feasible| in the corresponding Ij. For
each feasible switching sequence we then solve the LP problem (3.31) and obtain a collection of ranges R = R(I1), . . . , R(Is) where each R(Ij) is
defined according to (3.32) and, for ease of notation, we denote with s the total number of feasible switching sequences.
Patching the ranges
It may exist a subset of feasible switching sequences Q ⊆ SS such that condition (3.33) on the j-th input is satisfied by considering the setS
Ii∈QR
Figure 3.2: Graphical representation of the hyperplane that cuts the ∆ space when ∆∗1= [1, 1]0. The cutting plane is defined by[1 1]∆ ≤ 1.5
and applying the projector operator, i.e.:
P{j} [ Ii∈Q R(Ii) ! =uj, uj T∗ . (3.36)
Note that condition (3.36) is necessary but not sufficient to guarantee that uj is non-influential: indeed, it may be the case that the other inputs
share no common value on the subset of switching sequences Q, so that they can not be set to a value that makes uj vary on its entire feasible range.
We in fact need the following further condition to hold: \
Ii∈Q
PM\{j} R(Ii) 6= ∅, (3.37)
i.e., there is an admissible value for the other inputs, which is the same for all the switching sequences in Q, to have input uj non-influential. In Figure
3.4 is depicted the case of condition (3.36) and condition (3.37) satisfied at the same time, whereas in Figure 3.3 is depicted the case of (3.36) satisfied and (3.37) not satisfied.
Conditions (3.36) and (3.37) can be extended to all the inputs in (i.e., "whose index is in") a subset J ⊆ M, so that they are jointly non-influential
