Academic literature on the topic 'Constrained Zonotopes'

This paper presents a computational procedure to evaluate the fault tolerance of a linear-constrained model predictive control (LCMPC) scheme for a given actuator fault configuration (AFC). Faults in actuators cause changes in the constraints related to control signals (inputs), which in turn modify the set of MPC feasible solutions. This fact may result in an empty set of admissible solutions for a given control objective. Therefore, the admissibility of the control law facing actuator faults can be determined by knowing the set of feasible solutions. One of the aims of this paper is to provide methods to compute this set and to evaluate the admissibility of the control law for a given AFC, once the control objective and the admissibility criteria have been established. In particular, the admissible solution set for the predictive control problem, including the effect of faults (either through reconfiguration or accommodation), is determined using an algorithm that is implemented using set computations based on zonotopes. Finally, the proposed method is tested on a real application consisting of a part of the Barcelona sewer network.

Collision prediction and avoidance are critical for satellite proximity operations, and the key is the treatment of satellites' motion uncertainties and shapes, especially for ultra-close autonomous systems. In this paper, the zonotope-based reachable sets are utilized to propagate the uncertainties. For satellites with slender structures (such as solar panels), their shapes are simplified as cuboids which is a special class of zonotopes, instead of the classical sphere approach. The domains in position subspace influenced by the uncertainties and shapes are determined, and the relative distance is estimated to assess the safety of satellites. Moreover, with the approximation of the domains, the worst-case uncertainties for path constraints are determined, and a robust model predictive control method is proposed to deal with the line of sight and obstacle avoidance constraints. With zonotope representations of satellites, the proposed robust model predictive control is capable of handling the shapes of the satellite and obstacle simultaneously. Numerical simulations demonstrate the effectiveness of the proposed methods with an elliptic reference orbit. 1

For the quasi-linear parameter varying (quasi-LPV) system with bounded disturbance, a synthesis approach of dynamic output feedback robust model predictive control (OFRMPC) is investigated. The estimation error set is represented by a zonotope and refreshed by the zonotopic set-membership estimation method. By properly refreshing the estimation error set online, the bounds of true state at the next sampling time can be obtained. Furthermore, the feasibility of the main optimization problem at the next sampling time can be determined at the current time. A numerical example is given to illustrate the effectiveness of the approach.

Les systèmes dynamiques sont des modèles mathématiques pour décrire l'évolution temporelle de l'état d'un système. Il y a deux classes de systèmes dynamiques pertinentes à cette thèse : les systèmes discrets et les systèmes continus. Dans les systèmes dynamiques discrets (ou les programmes informatiques classiques), l'état évolue avec un pas de temps discrets. Dans les systèmes dynamiques continus, l'état du système est fonction du temps continu, et son évolution caractérisée par des équations différentielles. Étant donné que ces systèmes peuvent prendre des décisions critiques, il est important de pouvoir vérifier des propriétés garantissant leur sûreté. Par exemple, sur un programme, l'absence de débordement arithmétique. Dans cette thèse, nous développons un cadre pour la vérification automatique des propriétés de sûreté des programmes. Un élément clé de cette vérification est la preuve de propriétés invariantes. Nous développons ici un algorithme pour synthétiser des invariants inductifs (des propriétés vraies pour l'état initial, qui sont stables dans l'évolution des états du programme, donc sont toujours vraies par récurrence) pour des programmes numériques. L’interprétation abstraite (IA) est une approche traditionnelle pour la recherche d’invariants inductifs des programmes numériques. L'IA interprète les instructions du programme dans un domaine abstrait (par exemple intervalles, octogones, polyèdres, zonotopes), domaine qui est choisi en fonction des propriétés à prouver. Un invariant inductif peut être calculé comme limite possiblement infinie des itérées d'une fonctionnelle croissante. L'analyse peut recourir aux opérateurs d'élargissement pour forcer la convergence, au détriment de la précision. Si l'invariant n'est pas prouvé, une solution standard est de remplacer le domaine par un nouveau domaine abstrait davantage susceptible de représenter précisément l'invariant.La programmation par contraintes (PPC) est une approche alternative pour synthétiser des invariants, traduisant un programme en contraintes, et les résolvant en utilisant des solveurs de contraintes. Les contraintes peuvent opérer sur des domaines soit discrets, soit continus. La programmation classique par contraintes continues est basée sur un domaine d'intervalle, mais peut approximer une forme invariante complexe par une collection d’éléments abstraits. Une approche existante combine IA et PPC, raffinant de façon itérative, par découpage et contraction, une collection d’éléments abstraits, jusqu'à obtenir un invariant inductif. Celle-ci a été initialement présentée en combinaison avec intervalles et octogones. La nouveauté de notre travail est d'étendre ce cadre au domaine abstrait des zonotopes, un domaine sous-polyédrique qui présente un bon compromis en terme de précision et de coût. Cette extension demande de définir de nouveaux opérateurs sur les zonotopes, pour permettre le découpage et la contraction, ainsi que d'adapter l'algorithme générique. Nous introduisons notamment un nouvel algorithme de découpage de zonotopes basé sur un pavage par sous-zonotopes et parallélotopes. Nous proposons également des alternatives à certains opérateurs existants sur les zonotopes, mieux adaptés que les existants à la méthode. Nous avons implémenté ces opérations dans la bibliothèque APRON et avons testé l'approche sur des programmes présentant des invariants complexes, éventuellement non convexes. Les résultats démontrent un bon compromis par rapport à l'utilisation de domaines simples, comme les intervalles et les octogones, ou d'un domaine plus couteux comme les polyèdres. Enfin, nous discutons de l'extension de l'approche pour trouver des ensembles d'invariants positifs et négatifs pour des systèmes dynamiques continus
Dynamical systems are mathematical models for describing temporal evolution of the state of a system. There are two classes of dynamical systems relevant to this thesis: discrete and continuous. In discrete dynamical systems (or classical computer programs), the state evolves in discrete time steps, as described by difference equations. In continuous dynamical systems, the state of the system is a function of continuous time, characterized by differential equations. When we analyze the behavior of a dynamical system, we usually want to make sure that it satisfies a safety property expressing that nothing bad happens. An example of a safety property of programs is the absence of arithmetic overflows. In this thesis, we design a framework related to the automatic verification of the safety properties of programs. Proving that a program satisfies a safety property of interest involves an invariance argument. We develop an algorithm for inferring invariants more precisely inductive invariants (properties which hold during the initial state, remains stable under the program evolution, and hence hold always due to induction) for numerical programs. A traditional approach for finding inductive invariants in programs is abstract interpretation (AI) that interprets the states of a program in an abstract domain (intervals, polyhedra, octagon, zonotopes) of choice. This choice is made based on the property of interest to be inferred. Using the AI framework, inductive invariant can be computed as limits of iterations of functions. However, for abstract domains which feature infinite increasing chain, for instance, interval, these computations may fail to converge. Then, the classical solution would be to withdraw that particular domain and in its place redesign a new abstract domain which can represent the shape of the invariant. One may also use convergence techniques like widening to enforce convergence, but this may come at the cost of precision. Another approach called constraint programming (CP), can be used to find invariants by translating a program into constraints and solving them by using constraint solvers. Constraints in CP primarily operate on domains that are either discrete or continuous. Classical continuous constraint programming corresponds to interval domain and can approximate a complex shape invariant by a set of boxes, for instance, upto a precision criterion. An existing framework combines AI and continuous CP inspired by iterative refinement, splitting and tightening a collection of abstract elements. This was initially presented in combination with simple underlying abstract elements, boxes and octagons. The novelty of our work is to extend this framework by using zonotopes, a sub-polyhedric domain that shows a good compromise between cost and precision. However, zonotopes are not closed under intersection, and we had to extend the existing framework, in addition to designing new operations on zonotopes. We introduce a novel splitting algorithm based on tiling zonotopes by sub-zonotopes and parallelotopes. We also propose few alternative operators to the existing ones for a better efficiency of the method. We implemented these operations on top of the APRON library, and tested it on programs with non-linear loops that present complex, possibly non-convex, invariants. We present some results demonstrating the interest of this splitting-based algorithm to synthesize invariants on such programs. This algoritm also shows a good compromise by its use in combination with zonotopes with respect to its use with both simpler domains such as boxes and octagons, and more expressive domains like polyhedra. Finally, we discuss the extension of the approach to infer positive and negative invariant sets for dynamical systems