{'fraction_non_alphanumeric': 0.05255127987794542, 'fraction_numerical': 0.021981126744645984, 'mean_word_length': 4.141778036025567, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Set-based state estimation and fault diagnosis of linear discrete-time descriptor systems using constrained zonotopes

This paper presents new methods for set-valued state estimation and active fault diagnosis of linear descriptor systems. The algorithms are based on constrained zonotopes, a generalization of zonotopes capable of describing strongly asymmetric convex sets, while retaining the computational advantages of zonotopes. Additionally, unlike other set representations like intervals, zonotopes, ellipsoids, paralletopes, among others, linear static constraints on the state variables, typical of descriptor systems, can be directly incorporated in the mathematical description of constrained zonotopes. Therefore, the proposed methods lead to more accurate results in state estimation in comparison to existing methods based on the previous sets without requiring rank assumptions on the structure of the descriptor system and with a fair trade-off between accuracy and efficiency. These advantages are highlighted in two numerical examples.


INTRODUCTION
Many physical processes such as battery packs, robotic systems with holonomic and nonholonomic constraints, and socioeconomic systems (Janschek, 2011;Yang et al., 2019), exhibit static relations between their internal variables. These processes are known as descriptor systems (or implicit systems), which have generalized dynamic and static behaviors described through differential and algebraic equations, respectively (Wang et al., 2018a). Descriptor systems appear in several contexts, such as linear control (Bender and Laub, 1987), fault-tolerant control (Shi and Patton, 2014), and fault diagnosis . However, few strategies can deal effectively with state estimation and fault diagnosis of descriptor systems when uncertainties with unknown probability distribution are present (Hamdi et al., 2012).
Set-based strategies for state estimation of discrete-time descriptor systems with unknown-but-bounded uncertainties is a recent subject, often addressed using intervals, zonotopes and ellipsoids (Efimov et al., 2015;Wang et al., 2018a,b;Merhy et al., 2019). Interval methods are used in Efimov et al. (2015) to design a state estimator for time-delay descriptor systems based on linear matrix inequalities and the Luenberger structure. However, interval arithmetics can lead to conservative enclosures due to the wrapping effect. A few methods are proposed in Wang et al. (2018a) for set-valued state estimation of linear descriptor systems by enclosing the intersection of two consistent sets with a zonotope bound. Nevertheless, since the intersection cannot be computed exactly, the resulting bound can be conservative. These strategies are extended in Wang et al. (2018b) for linear parametervarying descriptor systems, but conservative enclosures are still present since the intersection method is maintained. Ellipsoids are used in Merhy et al. (2019) for state estimation of linear descriptor systems based on Luenberger type observers. Despite being able to provide stable bounds, the ellipsoidal estimation can be conservative since the complexity of the set is fixed and static relations are not directly incorporated. In addition, as in Wang et al. (2018a), restrictive assumptions on the rank of the system matrices are required to be able to design the proposed estimator. Moreover, due to the static constraints, the reachable sets of models of a descriptor system may be asymmetric even if the initial set is symmetric, and therefore methods based on the sets above can provide conservative enclosures.
Fault diagnosis aims to determine exactly which fault a process is subject to. For the case of descriptor systems, this problem has been considered in recent works using zonotopes (Yang et al., 2019;Wang et al., 2019). While Wang et al. (2019) explores the use of unknown input observers for robust passive fault diagnosis limited to ad-ditive faults, Yang et al. (2019) proposes a zonotope-based method for active fault diagnosis (AFD) of descriptor systems. The latter is based on the design of an input sequence for separation of the reachable sets. Unfortunately, the generator representation of zonotopes cannot incorporate exactly static relations between the state variables in general linear descriptor systems. Consequently, in practice, this may lead to a more difficult diagnosis.
This manuscript proposes strategies for set-based state estimation and AFD of linear descriptor systems based on constrained zonotopes (CZs), aiming to reduce the conservativeness described above through this asymmetric set representation. In contrast to the aforementioned sets, it is worth noting that linear static constraints, typical of descriptor systems, can be directly incorporated in the mathematical description of CZs. Thanks to this feature, set-valued methods based on CZs can provide less conservative enclosures. The proposed methods extensively explore the basic properties of CZs . In addition, efficient complexity reduction methods for CZs, available in the literature Yang and Scott, 2018), are used in the proposed strategies allowing a direct trade-off between accuracy and computational efficiency. The superiority of the proposed approaches with respect to zonotope-based methods is highlighted in numerical examples.

Problem formulation and preliminaries
Consider a linear discrete-time descriptor system with time k, state x k ∈ R n , input u k ∈ R nu , process uncertainty w k ∈ R nw , measured output y k ∈ R ny , and measurement uncertainty v k ∈ R nv . In each time interval [k − 1, k], k = 1, 2, . . ., the system evolves according to the model with E ∈ R n×n , A ∈ R n×n , B ∈ R n×nu , B w ∈ R n×nw , C ∈ R ny×n , D ∈ R ny×nu , and D v ∈ R ny×nv . In the following, it is assumed that rank(E) ≤ n. Note that when E is singular, one has n − rank(E) purely static constraints. It is assumed that the initial state x 0 ∈ X 0 and (w k , v k ) ∈ W × V for all k ≥ 0, where X 0 , W and V are known polytopic sets. Moreover, the initial condition (x 0 , u 0 , w 0 , v 0 ) is assumed to be feasible, i.e., consistent with the static relations in (1), and the output y 0 is computed as Constrained zonotopes are an extension of zonotopes, proposed in Scott et al. (2016), capable of describing also asymmetric convex polytopes, while maintaining the wellknown computational benefits of zonotopes.
Equation (2) is referred as constrained generator representation (CG-rep). Each column of G z is a generator, c z is the center, and A z ξ = b z are the constraints. Differently from zonotopes, the linear equality constraints in (2) permit a CZ to describe general convex polytopes . In the following, we use the shorthand notation Z = {G z , c z , A z , b z } for CZs, Z = {G z , c z } for zonotopes. In ng ∞ = {ξ ∈ R ng : ξ ∞ ≤ 1} denote, respectively, the n g -dimensional constrained unitary hypercube and the unitary hypercube 1 . A few common set operations can be computed using CZs in a trivial manner. Let Z, W ⊂ R n , R ∈ R m×n , and Y ⊂ R m . Define the linear mapping, Minkowski sum, and generalized intersection as With zonotopes, (3) and (4) are computed efficiently, but (5) is conservative and difficult to compute in the general case (Bravo et al., 2006). Operations (3) and (4) are computed trivially with polytopes in vertex representation, and (5) is computed efficiently in half-space representation, but conversions between representations are extremely expensive (Hagemann, 2015). On the other hand, operations (3)-(5) are computed trivially with CZs by (6)-(8) resulting only in a mild increase in the complexity of the CG-rep (2). Efficient methods for complexity reduction (to enclose a CZ with another one with fewer generators and constraints) are available, see Scott et al. (2016).

STATE ESTIMATION OF DESCRIPTOR SYSTEMS
This section presents a new method for set-based state estimation of system (1). For the sake of clarity, the prediction-update algorithm for standard discrete-time systems is first recalled. Consider (1) with E = I. Given an initial condition X 0 and an input u k with k ≥ 0, let Then, for k ≥ 1 the prediction-update algorithm consists in computing setsX k andX k satisfying   (10) is referred to as the prediction step, and (11) as the update step. The prediction step (10) must be reformulated when E is not invertible. We first consider the following assumption. Assumption 1. There exists a known CZ X a = {G a , c a , A a , b a } ⊂ R n such that x k ∈ X a for all k ≥ 0. Remark 1. Even though X a can be arbitrarily large, Assumption 1 is restrictive in the sense that the descriptor system (1) must be stable. Unstable systems are out of the scope of this paper and will be considered in future work.
The set estimation in Scott et al. (2016) relied on (6)-(8) to compute the steps (10)-(11). In order to extend this method to the case of descriptor systems, when computingX k it is necessary to take into account the static constraints arising from the possible singularity of E. The proposed method is based on singular value decomposition (SVD). Let E = UΣV T , where U and V are invertible by construction. Since E is square, then Σ is also square. Without loss of generality, let Σ be arranged as Σ = blkdiag(Σ, 0), whereΣ ∈ R nz×nz is diagonal with all the n z = rank(E) nonzero singular values of E. Moreover, let (1) can be rewritten with decoupled dynamics given by (Jonchkeere, 1988) (9). From (13b), the state z 0 must satisfyǍz 0 +Bu 0 +B w w 0 = 0. This constraint can be incorporated in the CG-rep of the initial setẐ 0 as follows.
Note that the extra columns inĜ 0 andÂ 0 come from w 0 ∈ W . Having definedẐ 0 , for the purpose of state estimation the static relation (13b) can be shifted forward to time k without loss of information. By doing so, from (13), the variablesz k are fully determined by (13a), whilě z k are obtained a posteriori byǍz k +Bu k +B w w k = 0.
T . An effective enclosure of the prediction step for the descriptor system (13) can be obtained in CG-rep as follows.
Moreover, Assumption 1 implies that z k ∈ Z a . Thus there must exist ξ a ∈ B ∞ (A a , b a ) such thatž k =č a +Ǧ a ξ a . Therefore, substituting these equalities in (13a) leads to From the constraint (13b) shifted to time k, we have thať Rearranging (14) and (15), grouping (ξ k−1 , δ k−1 , ξ a , δ k ), and writing in the CG-rep (2) proves the lemma. 2 Lemma 1 provides a predicted enclosure of the state z k in which the equality constraints (13b), shifted to time k, are directly taken into account. This is possible thanks to the fact that CZs incorporate equality constraints (see (2)). Finally, the prediction-update algorithm proposed for descriptor systems consists in the computation of CZsZ k , Z k , andX k , such that For this algorithm, the initial set isẐ 0 . The algorithm (16)-(18) operates recursively withZ k andẐ k for k ≥ 1 in the transformed state-space (13), while the estimated enclosure in the original state-space (1) is given byX k . Remark 2. The set Z a is used only to predict an enclosure for the componentsž k . This way, the static relation (13b) is incorporated as constraints to the variables ξ a in Z a . Remark 3. By construction, the CG-rep (16) corresponds to the exact feasible state set of (13) at k for the known state and uncertainty bounds. In addition, (17)-(18) can be computed exactly. However, in practice, in order to limit the complexity of the resulting sets these are outer approximated by using order reduction algorithms. In this case, equalities (16)-(18) are replaced by the relation ⊃.

ACTIVE FAULT DIAGNOSIS
The previous section presented a method to address the problem of the set-based estimation of descriptor systems. In the following, this tool is used in the design of an AFD method accounting for a finite number of possible abrupt faults. Consider a linear discrete-time descriptor system whose dynamics obeys one of possible n m known models 0 ∈ X 0 , (w k , v k ) ∈ W × V , and u k ∈ U , with X 0 , W , V and U being known polytopic sets.
The goal of AFD is to find which model describes the process behaviour. In the following, the dynamics are assumed to not change during the diagnosis procedure, i.e. the AFD is fast enough to avoid the switching between models. In this sense, a sequence (u 0 , u 1 , ..., u N ) of minimal length N is designed such that any output y [i] N is consistent with only one i ∈ I. If feasible, this problem may admit multiple solutions. For this reason, we introduce a cost function and select among the feasible input sequences the optimal one. Let → u = (u 0 , ..., u N ) ∈ R (N +1)nu , → w = (w 0 , . . ., w N ) ∈ R (N +1)nw , and → W = W × . . . × W . Consider a variable transformation similar to the one used in the previous section. With a slight abuse of notation, let z Then,(19) can be rewritten as with Note that the(·) anď (·) variables are defined according to (12) for each i, and equation (20b) has been already shifted to time k.

For each model i, consider the CZ Z
In addition, define the solution mappings (φ are the state and output of (20) at k, respectively. Then, for each i ∈ I, define state and output reachable sets at time k as Using (6)-(7), and taking note that by assumption z for k = 1, 2, . . . , N . Note that the third constraint in A , comes from the fact that (20b) must hold. Using the initial values (21), the variables c where α  (6) and (7), Consider an input sequence → u ∈ → U to be injected into the set of models (20), and let y [i] N denote the observed output. We are interested in the design of an input sequence such that the relation y Definition 2. An input sequence → u is said to be a separating input on k ∈ [0, N ] if, for every i, j ∈ I, i = j, Clearly, if (25) holds for all i, j ∈ I, i = j, then y N ( → u) must hold only for one i. In the case that this is not valid for any i ∈ I, one concludes that the real dynamics does not belong to the set of models (20). The following theorem is based on the computation of Y , where → 0 denotes the zero input sequence.
Proof. The relations below follow from (22)-(24a), (24c): According to (27) and Ω(i, j) defined as in the statement of the theorem. Then, (25) which in turn holds iff (26) is satisfied, with G Y N (i, j) and A Y N (i, j) defined as in the statement of the theorem. 2 Let n q denote the number of all possible combinations of i, j ∈ I, i = j, and define N Y } being the right hand side of (26). As it can be noticed, Y [q] is a zonotope. Then, the relation can be verified by solving a linear program (LP) similar to what proposed in Scott et al. (2014). In this sense, the following lemma provides an effective way to verify if a given input sequence is a separating input according to Theorem 1, consequently satisfying (25).
For the AFD of the n m models in (20) of the descriptor system, we consider the design of a separating input of minimum length according to the optimization problem with J( → u) chosen to minimize any harmful effects caused by injecting → u into (20). For simplicity we may choose J( where R is a weighting matrix. As in Scott et al. (2014), this is a bilevel optimization problem and can be rewritten as a mixed-integer quadratic program by defining a minimum separation threshold ε > 0 such that ε ≤δ [q] ( → u), for all q = 1, 2, . . . , n q .

NUMERICAL EXAMPLES
This section first evaluates the accuracy of the state estimation method proposed in Section 2 for descriptor and the uncertainties are random uniform noises bounded by w k ∞ ≤ 1, v k ∞ ≤ 1. The CZ in Assumption 1 is X a = {50·I 3 , 0}. The simulation is conducted for x 0 = [0.5 0.5 0.25] T , and the complexity of the CZs is limited to 15 generators and 5 constraints using the constraint elimination algorithm in Scott et al. (2016) and Method 4 in Yang and Scott (2018). Fig. 1 shows the volumes of the CZsX k for k ∈ [0, 100] obtained using the algorithm (16)-(18). Results obtained using the zonotope method in Wang et al. (2018a) are presented for comparison 2 . Note that the computation of the volumes was possible because this example has few states, otherwise the radii (half the length of the longest edge of the interval hull) can be used instead. The complexity of the zonotopes is limited to 15 generators using Method 4 in Yang and Scott (2018). Fig. 1 shows also the projections of X k onto x 3 . As it can be noticed, CZs provide substantially sharper bounds in comparison to zonotopes. This is possible since the enclosure in Lemma 1 takes into account the static constraints explicitly, while zonotopes provide only a conservative bound of the corresponding feasible region. However, this improved accuracy comes with an increase in computational time due to the higher set complexity (see Scott et al. (2016) for a discussion). This experiment was run 500 times consecutively on a laptop with an Intel Core i7-9750H processor, resulting in an average execution time of 3.34 ms for CZs, and of 0.33 ms for zonotopes.
We now evaluate the effectiveness of the AFD method proposed in Section 3. Consider the set of models (19) with model i = 1 described in the previous example, and  (30), the uncertainties are bounded by w k ∞ ≤ 0.1, v k ∞ ≤ 0.1, and the input is limited by u k ∞ ≤ 1. Let X a = {50·I 3 , 0} and ε = 0.01. All the models i ∈ I are considered to be faulty and must be separated. The number of generators of Y(i, j) was limited to two times its dimension using Method 4 in Yang and Scott (2018). The minimum length optimal input sequence that solves (29) was obtained using CPLEX 12.8 and MATLAB 9.1, with J(  for i = 1, 2, 3, 4, resulting by the injection of the designed