(246s) Constrained Zonotopes: A New Tool for Set-Based Computations

Many modern control and optimization algorithms make use of sets (e.g., intervals, ellipsoids, polytopes) as basic computational objects, with the aim of characterizing some sets of interest. Sets of interest may include the range of a given function, reachable or invariant sets of dynamical systems, or sets of states or parameters consistent with a bounded-error model [1,2,3]. Since the true set of interest is often impossible to represent exactly with finite data, an enclosure of this set by an element of some class of simpler sets is typically sought instead. The choice of a set class for a given application is critical and is based on a trade-off between (i) the accuracy with which a member of the class can represent the set of interest, and (ii) the complexity of the required computations.  An important consideration in (ii) is the convenience of the approximating set for its end use, which may involve checking for the inclusion of given points, as in model invalidation and fault diagnosis [2], checking for intersection with another set, as in system verification and safety analysis [1], or using the set as a constraint in an optimization problem, as in robust optimization and control [3].

This presentation introduces a new class of sets called constrained zonotopes and demonstrates that they provide a better trade-off between accuracy and efficiency than existing classes for some representative problems. While we believe that these sets will find application in a variety of optimization and control algorithms, their performance will be demonstrated here through the classical set-based state estimation problem for discrete-time linear systems with bounded noise [4], and its application to set-based fault diagnosis [5].

As with many problems in linear control and estimation, the essential set-operations required by these applications are Minkowski sums, linear mappings, and intersections. Before describing constrained zonotopes, it is informative to take stock of the capabilities of commonly used set classes with regard to these operations. The class of convex polytopes is closed under all three operations (i.e., performing any of them on members of the class results in another member of the class). Moreover, using the typical halfspace representation (H-rep), both intersections and invertible linear mappings can be computed efficiently.  However, the complexity of the Minkowski sum is exponential in the dimension of the set, as is the worst-case number of halfspaces describing the result [6]. The same is true of non-invertible linear mappings (e.g., polytope projections) [7]. In contrast, if the polytope is stored as a set of vertices (V-rep), then linear mappings and Minkowski sums are much simpler, but intersection becomes NP-hard [6]. Consequently, working with convex polytopes is very costly and numerically unstable when the dimension exceeds about five, or the number of halfspaces or vertices is large.

At the other extreme, intervals, parallelotopes, and ellipsoids all provide low-complexity set representations and relatively low-cost set operations. However, intervals are not closed under linear mappings, and parallelotopes and ellipsoids are not closed under Minkowski sums or intersections. Instead, the results of these operations must be conservatively enclosed. Optimal interval enclosures are easily computed, but are often very weak. For ellipsoids, cheap heuristic enclosures are given in [4] and optimal enclosures in [8], but the intersection requires the solution of a convex optimization problem. Cheap heuristic enclosures for parallelotopes are given in [9], but optimal enclosures are not available.

Recently, zonotopes have received much attention within the control community, particularly because linear mappings and Minkowski sums can be computed exactly and efficiently [10].  Zonotopes are convex polytopes that are centrally symmetric, which makes it possible to store them in terms of their center and a set of vectors called generators. This generator representation (G-rep) is often more compact than the equivalent H- or V-rep. Moreover, linear mappings and Minkowski sums of zonotopes in G-rep can be computed through trivial identities; the first requires a single matrix-matrix product, and the second requires only memory moves.  Both operations can increase the complexity of the set representation. However, in contrast to the worst-case exponential increase of the H-rep, the increase in the number of generators under these operations is only linear in the input data. Moreover, conservative order reduction techniques are available that enclose a given zonotope within another with fewer generators [11,1], providing a tunable mechanism for balancing accuracy and complexity. The main disadvantage of zonotopes is that they are not closed under intersection, and tight enclosures are difficult to compute. This leads to serious complications in, e.g., state estimation and hybrid systems verification [12].

Motivated by this discussion, the constrained zonotopes are defined by generalizing the following equivalent definition of the zonotopes: every zonotope is the image of the unit hypercube in some higher-dimensional space under an affine mapping. The constant part of this mapping is the center of the zonotope, while the linear term is comprised of its generators. To generalize this definition, we impose linear equality constraints on the unit hypercube, and define the constrained zonotopes as the affine images of these constrained hypercubes. These sets are fully described by the storing the constraint matrix and right-hand side vector in addition to the center and generator matrix. This is called the constrained generator representation (CG-rep).

With this definition, it will be shown that the constrained zonotopes are closed under Minkowsi sums and linear mappings, and that both operations can be implemented via simple identities that are hardly more complex than the corresponding identities for zonotopes. Further, we show that the constrained zonotopes are also closed under intersections, and these can be trivially computed with only memory moves. At the same time, the constrained zonotopes are also considerably more flexible than zonotopes. A simplex, for example, is a constrained zonotope that is not a zonotope (it is clearly not centrally symmetric). Remarkably, it turns out that every convex polytope is a constrained zonotope, and vice-versa. Thus, the novelty of the constrained zonotopes can be stated in two ways:

(1) When the numbers of generators and constraints are not limited, the CG-rep provides a new representation of convex polytopes that confers some significant computational advantages of zonotopes to this larger class of sets.

(2) When the numbers of generators and constraints are limited, the CG-rep describes a new class of sets that significantly extends the zonotopes while maintaining computational efficiency.

As with zonotopes, set operations on constrained zonotopes can increase the complexity of the CG-rep. This is more serious than with zonotopes because the number of generators and constraints may increase, but is considerably less serious than the growth of the H-rep discussed above.  Nonetheless, accurate and efficient methods for conservatively reducing the complexity of the CG-rep are essential to computing with constrained zonotopes. Thus, a comprehensive set of generator and constraint reduction techniques are proposed and demonstrated in this work.

Finally, the advantages of constrained zonotopes are demonstrated through extensive numerical case studies. First, comparisons with several existing approaches [9,11,12] for linear discrete-time estimation are presented, showing that constrained zonotopic estimators can provide estimates with substantially smaller volumes at only modest additional cost. These estimators are further shown to scale well to high-dimensional systems.  Next, these estimators are evaluated in the context of set-based fault diagnosis, where estimation accuracy is critical. Our results show that constrained zonotopic estimators are capable of reducing the time required for diagnosis by nearly half as compared to existing estimators applied to randomized examples.

References Cited

1. Althoff, M.; Stursberg, O. & Buss, M.
   Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes
   Nonlinear Analysis-Hybrid Systems, 2010, 4, 233-249
2. Rosa, P.; Silvestre, C.; Shamma, J. & Athans, M.
   Fault Detection and Isolation of LTV systems using Set-Valued Observers
   Proc. of the 49th IEEE Conference on Decision and Control, 2010, 768-773
3. Mayne, D.; Rakovic, S.; Findeisen, R. & Allgower, F.
   Robust output feedback model predictive control of constrained linear systems
   Automatica , 2006, 42, 1217-1222
4. Schweppe, F.
   Recursive state estimation: Unknown but bounded errors and system inputs
   IEEE Trans. Automat. Contr., 1968, 13, 22-28
5. Scott, J. K.; Findeisen, R.; Braatz, R. D. & Raimondo, D. M.
   Input design for guaranteed fault diagnosis using zonotopes
   Automatica , 2014, 50, 1580-1589
6. Tiwary, H. R.
   On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes
   Discrete & Computational Geometry, Springer-Verlag, 2008, 40, 469-479
7. Jones, C.; Kerrigan, E. & Maciejowski, J.
   On Polyhedral Projection and Parametric Programming
   J. Optim. Theor. Appl., Springer US, 2008, 138, 207-220
8. Chernousko, F.
   Optimal Guaranteed Estimates of Indeterminacies with the Aid of Ellipsoids. Parts I-II
   Engineering Cybernetics, 1980, 18, 1-9
9. Chisci, L.; Garulli, A. & Zappa, G.
   Recursive state bounding by parallelotopes
   Automatica , 1996, 32, 1049-1055

10. Kuhn, W.
Rigorously computed orbits of dynamical systems without the wrapping effect
Computing, 1998, 61, 47-67

11. Combastel, C.
A state bounding observer based on zonotopes
European Control Conference, 2003

12. Bravo, J.; Alamo, T. & Camacho, E.
Bounded error identification of systems with time-varying parameters
IEEE Trans. Automat. Contr., 2006, 51, 1144-1150