Academic literature on the topic 'Zonotopic analysis'

We present Pasado, a technique for synthesizing precise static analyzers for Automatic Differentiation. Our technique allows one to automatically construct a static analyzer specialized for the Chain Rule, Product Rule, and Quotient Rule computations for Automatic Differentiation in a way that abstracts all of the nonlinear operations of each respective rule simultaneously. By directly synthesizing an abstract transformer for the composite expressions of these 3 most common rules of AD, we are able to obtain significant precision improvement compared to prior works which compose standard abstract transformers together suboptimally. We prove our synthesized static analyzers sound and additionally demonstrate the generality of our approach by instantiating these AD static analyzers with different nonlinear functions, different abstract domains (both intervals and zonotopes) and both forward-mode and reverse-mode AD. We evaluate Pasado on multiple case studies, namely soundly computing bounds on a neural network’s local Lipschitz constant, soundly bounding the sensitivities of financial models, certifying monotonicity, and lastly, bounding sensitivities of the solutions of differential equations from climate science and chemistry for verified ranges of initial conditions and parameters. The local Lipschitz constants computed by Pasado on our largest CNN are up to 2750× more precise compared to the existing state-of-the-art zonotope analysis. The bounds obtained on the sensitivities of the climate, chemical, and financial differential equation solutions are between 1.31 − 2.81× more precise (on average) compared to a state-of-the-art zonotope analysis.

Kinematic efficiency of robot limbs can be analyzed by means of the manipulability concept defined by Yoshikawa. However, when it is applied to redundant serial chains, that are the most common case in humanoid robotics, Yoshikawa's manipulability measure is not able to take into account the joint velocity range of each robot joint. In order to overcome this difficulty we propose to substitute in the place of the manipulability ellipsoid a manipulability zonotope resulting from the robot Jacobian transform of the joint velocities parallelotope. The proposed manipulability zonotope notion is similar to the well-known manipulability polytope notion, but its associated volume measure can take benefit of the so-called zonotope theory. By means of a famous and powerful theorem about the cubical dissection of any zonotope, an original formula of manipulability measure is proposed from which is also derived a mean manipulability estimate associated to a given joint space working. The proposed tools are applied to a kinematic analysis of a 4R-regional structure model of the upper limb.

For solving the advanced manufacturing fault diagnosis issue, a novel zonotopes estimation-based fault diagnosis algorithm is proposed in this paper. By using the intersection of the convex polytope and the tight strip, the fault diagnosis problem is changed into the analysis of the set membership outer bound computation. If the feasible set is detected empty, the set membership filters are designed. The minimal volume is also calculated and the selected zonotopes can be viewed as the approximate boundary. The simulation results show the effectiveness and practicability of the presented fault diagnosis algorithm.

In this work, we describe the new command zonotope, which, by resorting to a geometry-based approach, provides a measure of productivity that fully accounts for the existing heterogeneity across firms within the same industry. The method we propose also enables assessment of the extent of multidimensional heterogeneity with applications to fields beyond that of production analysis. Finally, we detail the functioning of the software to perform the related empirical analysis, and we discuss the main computational issues encountered in its development.

Cette thèse s’intéresse à l’estimation d’état et à la détection de défauts de systèmes linéaires à commutations. Deux approches d’estimation par intervalles sont développées. La première consiste à proposer une estimation d’état pour des systèmes linéaires à commutations à paramètres variants en temps continu et en temps discret. La deuxième approche consiste à proposer une nouvelle logique d’estimation du signal de commutations d’un système linéaire à commutations à entrée inconnue en combinant la technique par modes glissants et l’approche par intervalles. Le problème d’estimation d’état constitue une des étapes fondamentales pour traiter le problème de détection de défauts. Par conséquent, des solutions robustes pour la détection de défauts sont développées en utilisant la théorie des ensembles. Deux méthodologies ont été employées pour détecter les défauts : un observateur classique par intervalle et une nouvelle structure TNL d’observateur par intervalle. Les performances de détection de défauts sont améliorées en se basant sur un critère L∞. De plus, une stratégie robuste de détection de défauts est introduite en utilisant des techniques zonotopiques et ellipsoïdales. En se basant sur des critères d’optimisation, ces techniques sont utilisées pour fournir des seuils dynamiques pour l’évaluation du résidu et pour améliorer la précision des résultats de détection de défauts sans tenir compte de l’hypothèse de coopérativité. Les méthodes développées dans cette thèse sont illustrées par des exemples académiques et les résultats obtenus montrent leur efficacité
This thesis deals with state estimation and fault detection for a class of switched linear systems. Two interval state estimation approaches are proposed. The first one is investigated for both continuous and discrete-time linear parameter varying switched systems subject to measured polytopic parameters. The second approach is concerned with a new switching signal observer, combining sliding mode and interval techniques, for a class of switched linear systems with unknown input. State estimation remains one of the fundamental steps to deal with fault detection. Hence, robust solutions for fault detection are considered using set-membership theory. Two interval techniques are achieved to deal with fault detection for discrete-time switched systems. First, a commonly used interval observer is designed based on an L∞ criterion to obtain accurate fault detection results. Second, a new interval observer structure (TNL structure) is investigated to relax the cooperativity constraint. In addition, a robust fault detection strategy is considered using zonotopic and ellipsoidal analysis. Based on optimization criteria, the zonotopic and ellipsoidal techniques are used to provide a systematic and effective way to improve the accuracy of the residual boundaries without considering the nonnegativity assumption. The developed techniques in this thesis are illustrated using academic examples and the results show their effectiveness

Le diagnostic consiste à détecter, localiser et éventuellement identifier les défauts au sein d’un système. Un modèle ne représentant qu’imparfaitement la réalité, une prise en compte explicite des incertitudes est nécessaire pour mettre en oeuvre des techniques de redondance analytique conduisant à un diagnostic garanti. En s’appuyant sur une représentation déterministe des incertitudes (par des intervalles et, plus particulièrement, des zonotopes, une classe particulière de polytopes), l’objet de ce travail est double : proposer une spécification des modes de fonctionnement aussi proche que possible de la connaissance disponible, d’une part, assurer la correction logique entre la spécification des modes de fonctionnement et la décision fournie, d’autre part. En s’appuyant sur des algorithmes de calcul d’atteignabilité à base de zonotopes pour limiter les problèmes de dépendance et l’effet d’enveloppement, d’une part, sur des algorithmes de détection de collision, d’autre part, l’intérêt d’une re-formulation ensembliste de plusieurs techniques de génération de résidus (indicateurs de défauts) est mise en évidence non seulement pour la synthèse de tests implantés en ligne, mais aussi pour l’aide à la conception d’un système de diagnostic (choix de seuils, analyses de sensibilité). Les approches ensemblistes permettent d’introduire la notion de découplage dans les limites fixées par les bornes. Un nombre arbitrairement grand de perturbations peut ainsi être découplé parfaitement sans contrainte de rang. Les domaines calculés permettent de borner les incertitudes dans toutes les directions de l’espace et d’obtenir des sensibilités meilleures que celles résultant de techniques projectives ou d’élimination. Le travail effectué sur les calculs d’atteignabilité débouche quant à lui sur une ouverture vers la vérification de propriétés de sûreté dans les systèmes dynamiques hybrides
Fault diagnosis consists in detecting, isolating and possibly identifying the faults occurring in a system. As a model never perfectly represent the reality, the uncertainties have to be explicitly formalized in order to implement analytical redundancy approaches providing a guaranteed diagnosis. Based on a deterministic representation of uncertainties (by intervals and, more precisely, by zonotopes, a particular class of polytopes), this work follows two main objectives: proposing a specification of operating modes which is as close as possible to the available knowledge, and ensuring the logical soundness between the specification of the operating modes and the diagnosis decision. Using reachability algorithms based on zonotopes to control the dependency problem and the wrapping effect, on the one hand, using collision detection algorithms, on the other hand, the interest in a setmembership re-formulation of several residual generation methods is put into evidence not only to design on-line tests, but also to design and analyse the properties of a fault diagnosis system (adjustment of thresholds, sensitivity analysis). Set-membership approaches allow to introduce the notion of decoupling in the limits fixed by some bounds An arbitrary number of perturbations can then be perfectly decoupled without any rank constraint. The computed domains allow to bound the uncertainties in all the space directions and so obtain better sensitivities than those resulting from projective or elimination approaches. The work about reachability computations has lead to developments that are expected to be useful for the verification of safety properties of hybrid dynamical systems

La maggior parte dei robot industriali può essere caratterizzata da una larghezza di banda di impedenza molto stretta, capacità di carico elevata, attuatori precisi e vasto spazio di lavoro. Al contrario, l’operatore umano presenta un’ampia larghezza di banda di impedenza, flessibilità e destrezza, ma capacità di carico basse. La possibilità di combinare i vantaggi di entrambi può portare alla realizzazione di sistemi robotici molto efficaci. Pertanto, se l’impedenza apparente di un manipolatore può essere minimizzata, l’operatore può sviluppare la propria impedenza, consentendo una collaborazione altamente intuitiva. Ciò è importante nelle operazioni di assemblaggio, dove l’accoppiamento delle parti richiede un’interazione a bassa impedenza, che sia anche efficace ed intuitiva. Il progetto prevede la sintesi e la progettazione di manipolatori ridondanti nell’ambito dell’interazione fisica uomo-robot. In particolare, si studiano diverse architetture della piattaforma di Gough-Stewart a 6 gradi di libertà e, tra queste, si sceglie quella che garantisce il miglior comportamento isotropo, oltre ad altri vantaggi costruttivi, quali ad esempio la capacità di misurarne facilmente i parametri di controllo. Impiegando il software Creo, si propone un modello CAD del meccanismo scelto e, grazie alla tecnologia di prototipazione rapida, si riesce a verificare la bontà della progettazione.

Nous nous plaçons dans le cadre de l'analyse statique de programmes, et nous nous intéressons aux propriétés numériques, c'est a dire celles qui concernent les valeurs numériques des variables de programmes. Nous essayons en particulier de déterminer une sur-approximation garantie de l'ensemble de valeurs possibles pour chaque variable numérique utilisée dans le programme à analyser. Cette analyse statique est faite dans le cadre de la théorie de l'interprétation abstraite, théorie présentant un compromis entre les limites théoriques d'indécidabilite et de calculabilite et la précision des résultats obtenus. Nous sommes partis des travaux d'Eric Goubault et Sylvie Putot, que nous avons étendus et généralisés. Notre nouveau domaine abstrait, appelé ensembles affines contraints, combine à la fois l'efficacite de calcul des domaines à base de formes affines et le pouvoir ex- pressif des domaines relationnels classiques tels que les octogones ou les polyèdres. Le nouveau domaine a été implémenté pour mettre en évidence l'intérêt de cette combinaison, ses avantages, ses performances et ses limites par rapport aux autres domaines numériques déjà existants. Le formalisme ainsi que les résultats pra- tiques ont fait l'objet de plusieurs publications [CAV 2009, CAV 2010].

Cette thèse se compose de plusieurs travaux portant sur l'énumération et le comportement asymptotique de structures combinatoires apparentées aux partitions d'entiers. Un premier travail s'intéresse aux partitions d'entiers bipartites, qui constituent une généralisation bidimensionnelle des partitions d'entiers. Des équivalents du nombre de partitions sont obtenus dans le régime critique où l'un des entiers est de l'ordre du carré de l'autre entier et au delà de ce régime critique. Ceci complète les résultats établis dans les années cinquante par Auluck, Nanda et Wright. Le deuxième travail traite des chaînes polygonales à sommets entiers dans le plan. Pour un modèle statistique introduit par Sinaï, une représentation intégrale exacte de la fonction de partition est donnée. Ceci conduit à un équivalent du nombre de chaînes joignant deux points distants qui fait intervenir les zéros non triviaux de la fonction zêta de Riemann. Une analyse combinatoire détaillée des chaînes convexes est présentée. Elle permet de montrer l'existence d'une forme limite pour les chaînes convexes aléatoires ayant peu de sommets, répondant ainsi à une question ouverte de Vershik. Un troisième travail porte sur les zonotopes à sommets entiers en dimension supérieure. Un équivalent simple est donné pour le logarithme du nombre de zonotopes contenus dans un cône convexe et dont les extrémités sont fixées. Une loi des grands nombres est établie et la forme limite est caractérisée par la transformée de Laplace du cône
This thesis consists of several works dealing with the enumeration and the asymptotic behaviour of combinatorial structures related to integer partitions. A first work concerns partitions of large bipartite integers, which are a bidimensional generalization of integer partitions. Asymptotic formulæ are obtained in the critical regime where one of the numbers is of the order of magnitude of the square of the other number, and beyond this critical regime. This completes the results established in the fifties by Auluck, Nanda, and Wright. The second work deals with lattice convex chains in the plane. In a statistical model introduced by Sinaï, an exact integral representation of the partition function is given. This leads to an asymptotic formula for the number of chains joining two distant points, which involves the non trivial zeros of the Riemann zeta function. A detailed combinatorial analysis of convex chains is presented. It makes it possible to prove the existence of a limit shape for random convex chains with few vertices, answering an open question of Vershik. A third work focuses on lattice zonotopes in higher dimensions. An asymptotic equality is given for the logarithm of the number of zonotopes contained in a convex cone and such that the endings of the zonotope are fixed. A law of large numbers is established and the limit shape is characterized by the Laplace transform of the cone

Model-based Fault Detection and Isolation (FDI) is a major theoretical topic that is becoming increasingly to one of the most significant key features to increase safety and reliability of complex automatic control systems. Basically, model-based FDI relies on the use of a mathematical model to describe the system behavior. However, uncertainty remains always present when modelling a system since its effect is non-negligible even if there are no process faults. One way to deal with uncertainty is to assume its unknown-but-bounded description. Generally speaking, the uncertainty in so-called \emph{set-based approaches} is represented by a set that is unknown-but-bounded at each time instant. Set-based approaches can be classified into three main paradigms: interval observer approach, set-membership approach and set-invariance approach. In this thesis, the influence of the uncertainty is addressed using the set-based approaches considering a zonotopic representation. Moreover, this thesis presents both analysis and comparison of the set-based approaches for the state estimation and FDI frameworks with the goal of establishing the advantages and disadvantages of each approach, and also, to find out their relationship in a formal mathematical framework. However, the mentioned set-based approaches implicitly assume time-varying uncertainty. In the set-based approach, the propagation of the state set is affected by several problems such as the wrapping effect, temporal variance on uncertain parameters (or uncertain parameter time dependency) and range evaluation of an interval function, especially in the case of using the interval hull of the set at each iteration. Therefore, conservative and unstable results may be obtained (for even a stable system) when using the set-based approach in the simulation of the system with parametric time-invariant uncertainties. On the other hand, the approximated state set can be computed based on a set of point-wise trajectories. This type of approach is called \emph{trajectory-based approach}. Therefore, the uncertain parameter time dependency is preserved if the set of point-wise trajectories is generated using the mentioned trajectory-based approach.
La detección y el aislamiento de fallos (DAF) basado en modelos es un problema teórico importante que se está convirtiendo cada vez m ás en una de las características clave para aumentar la seguridad y abilidad de los sistemas de control autom ático complejos. Básicamente, la DAF basada en modelos utiliza un modelo m atem ático para describir el comportamiento del sistem a. Sin embargo, la incertidumbre permanece siempre presente cuando se modela un sistema, ya que su efecto no es despreciable, incluso si no hay fallos que afecten al sistema. Una form a de tener en cuenta la incertidumbre es asumir una descripción desconocida pero acotada. En términos generales, la incertidumbre en los llamados enfoques basados en conjuntos se representa mediante un conjunto que es desconocido pero acotado en cada instante de tiempo. Los enfoques basados en conjuntos se pueden clasicar en tres paradigmas principales: enfoque basado en observadores intervalares, enfoque de pertenencia al conjunto y enfoque basados en conjuntos invariante. En esta tesis, la inuencia de la incertidumbre se aborda utilizando los enfoques basados en conjuntos y representaciones zonotópicas de los mismos. Adem ás, esta tesis presenta tanto el análisis como la comparación de los enfoques basados en conjuntos para la estimación de estado con el objetivo de establecer las ventajas y desventajas de cada enfoque, y también, para descubrir su relación en un m arco matemático formal. Sin embargo, los mencionados enfoques basados en conjuntos suponen implícitamente una incertidumbre variante en el tiempo. En el enfoque basado en pertenencia a conjuntos, la propagación del conjunto de estados se ve afectada por varios problemas, como el efecto de del aum ento de incertidumbre, la varianza temporal de los parámetros inciertos (o la dependencia temporal de los parámetros inciertos) y la evaluación de rango de una función de intervalo, especialm ente cundo se usa el "lnterval Hull" en cada iteración. Por lo tanto, se pueden obtener resultados conservadores (incluso para un sistema estable) en la simulación del sistema con incertidumbres param étricas invariantes en el tiempo con el uso del enfoque basado en pertenencia a conjuntos. Por otro lado, el conjunto de estados aproximados se puede calcular con base en un conjunto de trayectorias puntuales. Este tipo de enfoque se denomina enfoque basado en trayectorias. Por lo tanto, la dependencia temporal del parámetro incierto se conserva si el conjunto de trayectorias puntuales se genera utilizando el mencionado enfoque basado en trayectorias
La detecció i aïllament de fallades basada en models (DAF) és un problema teòric important que està esdevenint cada cop més una de les característiques clau per augmentar la seguretat i la fiabilitat dels sistemes de control automàtic complexos. Bàsicament, la DAF basada en models es basa en l’ús d'un model matemàtic per descriure el comportament del sistema. Tanmateix, la incertesa roman sempre present quan es modelitza un sistema ja que el seu efecte no és insignificant, fins i tot si no hi ha fallades en el procés. Una forma de fer front a la incertesa és assumir una descripció desconeguda però acotada. En termes generals, la incertesa en els anomenats enfocaments basats en conjunts està representada per un conjunt desconegut però acotat en cada instant. Els enfocaments basats en conjunts es poden classificar en tres paradigmes principals: l'enfocament d'observadors d'intervals, l'enfocament de pertinença a conjunts i l'enfocament d’invariància. En aquesta tesi, s'aborda la influència de la incertesa mitjançant els enfocaments basats en conjunts fent servir una representació zonotòpica. A més, aquesta tesi presenta tant l’anàlisi com la comparació dels enfocaments basats en conjunts per a l’estimació de l'estat i la seva aplicació a DAF amb l'objectiu d'establir els avantatges i desavantatges de cada enfocament i, a més, conèixer la seva relació en un marc matemàtic formal. Tanmateix, els esmentats enfocaments basats en conjunts assumeixen implícitament una incertesa variable en el temps. En l'enfocament basat en conjunts, la propagació del conjunt d'estats es veu afectada per diversos problemes com l'efecte d'embolcall, la variació temporal dels paràmetres incerts (o la dependència en el temps dels paràmetres incerts) i l’avaluació del rang d'una funció intervalar, especialment en el cas d'utilitzar el "Interval Hull" del conjunt a cada iteració. Per tant, es poden obtenir resultats conservadors i inestables (fins i tot per a un sistema estable) en la simulació del sistema amb incerteses temporals invariants paramètriques amb l’ús del mètode basat en conjunts. D'altra banda, el conjunt d'estats aproximat es pot calcular a partir d'un conjunt de trajectòries puntuals. Aquest tipus d'enfocament s'anomena enfocament basat en trajectòries. Per tant, la dependència en el temps del paràmetres es conserva si el conjunt de trajectòries puntuals es generen utilitzant l'enfocament basat en trajectòries esmentat. Aquesta tesi inclou sis parts. La primera part, presenta l'estat de la tècnica i fa una introducció de les eines de recerca. La segona part proposa la relació matemàtica entre l'observador intervalar i els enfocaments de pertinença. La tercera part se centra en la integració dels enfocaments basats en observadors i d’invariància de conjunts en la seva aplicació a DAF caracteritzant la mínima fallada detectable i aïllable. La quarta part presenta el disseny d'un observador intervalar que millora la sensibilitat a les fallades respecte les pertorbacions. La cinquena part proposa el disseny robust d'observadors d'intervals per a sistemes incerts, subjectes a incerteses tant temporals com variables es el temps. L'última part presenta algunes conclusions, resumeix la investigació realitzada i estableix les bases per al treball futur

AbstractKoopman operator linearization approximates nonlinear systems of differential equations with higher-dimensional linear systems. For formal verification using reachability analysis, this is an attractive conversion, as highly scalable methods exist to compute reachable sets for linear systems. However, two main challenges are present with this approach, both of which are addressed in this work. First, the approximation must be sufficiently accurate for the result to be meaningful, which is controlled by the choice of observable functions during Koopman operator linearization. By using random Fourier features as observable functions, the process becomes more systematic than earlier work, while providing a higher-accuracy approximation. Second, although the higher-dimensional system is linear, simple convex initial sets in the original space can become complex non-convex initial sets in the linear system. We overcome this using a combination of Taylor model arithmetic and polynomial zonotope refinement. Compared with prior work, the result is more efficient, more systematic and more accurate.