Spelling suggestions: "subject:"theoretical methods""
1 |
Number theoretic methods and their significance in computer science, information theory, combinatorics, and geometryBibak, Khodakhast 13 April 2017 (has links)
In this dissertation, I introduce some number theoretic methods and discuss their intriguing applications to a variety of problems in computer science, information theory, combinatorics, and geometry. First, using properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions, we give an explicit formula for the number of solutions of restricted linear congruences in their `most general case'. As a consequence, we derive necessary and su cient conditions under which these congruences have no solutions. The number of solutions of this kind of congruence was rst considered by Rademacher in 1925 and Brauer in 1926, in a special case. Since then, this problem has been studied, in several other special cases, in many papers. The problem is very well-motivated and has found intriguing applications in several areas of mathematics, computer science, and physics, and there is promise for more applications/implications in these or other directions.
Universal hash functions, discovered by Carter and Wegman in 1979, have many important applications in computer science. Applying our results we construct an almost-universal hash function family which is used to give a generalization of a recent authentication code with secrecy scheme.
As another application of our results, we prove an explicit and practical formula for the number of surface-kernel epimorphisms from a co-compact Fuchsian group to iv a cyclic group. This problem has important applications in combinatorics, geometry, string theory, and quantum eld theory (QFT). As a consequence, we obtain an
`equivalent' form of Harvey's famous theorem on the cyclic groups of automorphisms of compact Riemann surfaces.
We also consider the number of solutions of linear congruences with distinct coordinates, and using a graph theoretic method, generalize a result of Sch onemann from 1839. Also, we give explicit formulas for the number of solutions of unweighted linear congruences with distinct coordinates. Our main tools are properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions. Then, as an application, we derive an explicit formula for the number of codewords in the Varshamov{Tenengolts code V Tb(n) with Hamming weight k, that is, with exactly k 1's. The Varshamov{Tenengolts codes are an important class of codes that are capable of correcting asymmetric errors on a Z-channel. As another application, we derive Ginzburg's formula for the number of codewords in V Tb(n), that is, jV Tb(n)j. We even go further and discuss applications to several other combinatorial problems, some of which have appeared in seemingly unrelated contexts. This provides a general
framework and gives new insight into these problems which might lead to further work.
Finally, we bring a very deep result of Pierre Deligne into the area of coding theory we connect Lee codes to Ramanujan graphs by showing that the Cayley graphs associated with some quasi-perfect Lee codes are Ramanujan graphs (this solves a recent conjecture). Our main tools are Deligne's bound from 1977 for estimating a
particular kind of trigonometric sum and a result of Lov asz from 1975 (or of Babai from 1979) which gives the eigenvalues of Cayley graphs of nite Abelian groups. Our proof techniques may motivate more work in the interactions between spectral graph theory, character theory, and coding theory, and may provide new ideas towards the long-standing Golomb{Welch conjecture. / Graduate / 0984
|
2 |
Network-centric methods for heterogeneous multiagent systemsAbbas, Waseem 13 January 2014 (has links)
We present tools for a network topology based characterization of heterogeneity in multiagent systems, thereby providing a framework for the analysis and design of heterogeneous multiagent networks from a network structure view-point. In heterogeneous networks, agents with a diverse set of resources coordinate with each other. Coordination among different
agents and the structure of the underlying network topology have significant impacts on the overall behavior and functionality of the system. Using constructs from graph theory, a qualitative as well as a quantitative analysis is performed to examine an inter-relationship between the network topology and the distribution of agents with various capabilities in heterogeneous networks. Our goal is to allow agents maximally exploit heterogeneous resources available within the network through local interactions, thus exploring a promise heterogeneous networks hold to accomplish complicated tasks by leveraging upon the assorted capabilities of agents. For a reliable operations of such systems, the issue of security against intrusions and malicious agents is also addressed. We provide a scheme to secure a network against a sequence of intruder attacks through a set of heterogeneous guards. Moreover, robustness of networked systems against noise corruption and structural changes in the underlying network topology is also examined.
|
3 |
Sheaf theoretic methods in modular representation theoryMautner, Carl Irving 05 October 2010 (has links)
This thesis concerns the use of perverse sheaves with coefficients in commutative rings and in particular, fields of positive characteristic, in the study of modular representation theory. We begin by giving a new geometric interpretation of classical connections between the representation theory of the general linear groups and symmetric groups. We then survey work, joint with D. Juteau and G. Williamson, in which we construct a class of objects, called parity sheaves. These objects share many properties with the intersection cohomology complexes in characteristic zero, including a decomposition theorem and a close relation to representation theory. The final part of this document consists of two computations of IC stalks in the nilpotent cones of sl₃and sl₄. These computations build upon our calculations in sections 3.5 and 3.6 of (31), but utilize slightly more sophisticated techniques and allow us to compute the stalks in the remaining characteristics. / text
|
4 |
Fault tolerant control based on set-theoretic methods. / Commande tolérante aux défauts fondée sur des méthodes ensemblistesStoican, Florin 06 October 2011 (has links)
La thèse est dédiée à l'analyse et à la conception de la commande tolérante aux défauts (fault tolerant control - FTC) en se fondant sur des méthodes ensemblistes. Nous étudions l'apparition des défauts pour les systèmes multi-capteurs, et les modes de détection, ainsi que la conception de lois de commande qui assurent la stabilité en boucle fermée. L'utilisation des ensembles invariants/contractifs permet la caractérisation des signaux résiduels, qui sont utilisés par la suite dans le processus de détection et d'isolement des défauts. La décision est fondée sur le positionnement par rapport à des hyperplans de séparation avec des importantes réductions de temps de calcul. Un mécanisme dual mis en œuvre par un bloc de récupération, permet la certification de la récupération des capteurs précédemment affectés par ces défauts.Dans une perspective théorique, nous soulignons les conditions qui permettent l'inclusion du bloc FDI (fault detection and isolation) et sa raison d'être dans la conception des lois de commande. Cela conduit par exemple à la synthèse des gains de retour d'état statique, par résolution de problèmes d'optimisation efficace (linéaire/convexe).Selon les paramètres choisis pour le réglage, la conception de la FTC peut être complétée par un superviseur de référence ou d'une loi de commande prédictive, qui adapte la trajectoire d'état et l'action de commande par retour d'état, afin d'assurer l'identification et la détection des défauts. Les questions spécifiques à l'utilisation de méthodes ensemblistes sont détaillées et des améliorations diverses sont proposées, par exemple : la construction des ensembles invariants, des formulations moins complexes des problèmes de type Mixed Integer Programming (MIP), l'analyse de la stabilité des systèmes commutés (notion de ``dwell-time''). / The scope of the thesis is the analysis and design of fault tolerant control (FTC) schemes through the use of set-theoretic methods. In the framework of multisensor schemes, the faults appearance and the modalities to accurately detect them are investigated as well as the design of control laws which assure the closed-loop stability. By using invariant/contractive sets to describe the residual signals, a fault detection and isolation (FDI) mechanism with reduced computational demands is implemented based on set-separation. A dual mechanism, implemented by a recovery block, which certificates previously fault-affected sensors is also studied. From a broader theoretical perspective, we point to the conditions which allow the inclusion of {FDI} objectives in the control law design. This leads to static feedback gains synthesis by means of numerically attractive optimization problems. Depending on the parameters selected for tuning, is shown that the FTC design can be completed by a reference governor or a predictive control scheme which adapts the state trajectory and the feedback control action in order to assure {FDI}. When necessary, the specific issues originated by the use of set-theoretic methods are detailed and various improvements are proposed towards: invariant set construction, mixed integer programming (MIP), stability for switched systems (dwell-time notions).
|
5 |
Control of Multi-Agent Dynamical Systems in the Presence of Constraints / Commande sous contraintes de systèmes dynamiques multi-agentsProdan, Ionela 03 December 2012 (has links)
L'objectif de cette thèse est de proposer des solutions aux problèmes liés à la commande optimale de systèmes dynamiques multi-agents en présence de contraintes. Des éléments de la théorie de commande et d'optimisation sont appliqués à différents problèmes impliquant des formations de systèmes multi-agents. La thèse examine le cas d'agents soumis à des contraintes dynamiques. Pour faire face à ces problèmes, les concepts bien établis tels que la théorie des ensembles, la platitude différentielle, la commande prédictive (Model Predictive Control - MPC), la programmation mixte en nombres entiers (Mixed-Integer Programming - MIP) sont adaptés et améliorés. En utilisant ces notions théoriques, ce travail de thèse a porté sur les propriétés géométriques de la formation d'un groupe multi-agents et propose un cadre de synthèse original qui exploite cette structure. En particulier, le problème de conception de formation et les conditions d'évitement des collisions sont formulés comme des problèmes géométriques et d'optimisation pour lesquels il existe des procédures de résolution. En outre, des progrès considérables dans ce sens ont été obtenus en utilisant de façon efficace les techniques MIP (dans le but d'en déduire une description efficace des propriétés de non convexité et de non connexion d'une région de faisabilité résultant d'une collision de type multi-agents avec des contraintes d'évitement d'obstacles) et des propriétés de stabilité (afin d'analyser l'unicité et l'existence de configurations de formation de systèmes multi-agents). Enfin, certains résultats théoriques obtenus ont été appliqués dans un cas pratique très intéressant. On utilise une nouvelle combinaison de la commande prédictive et de platitude différentielle (pour la génération de référence) dans la commande et la navigation de véhicules aériens sans pilote (UAVs). / The goal of this thesis is to propose solutions for the optimal control of multi-agent dynamical systems under constraints. Elements from control theory and optimization are merged together in order to provide useful tools which are further applied to different problems involving multi-agent formations. The thesis considers the challenging case of agents subject to dynamical constraints. To deal with these issues, well established concepts like set-theory, differential flatness, Model Predictive Control (MPC), Mixed-Integer Programming (MIP) are adapted and enhanced. Using these theoretical notions, the thesis concentrates on understanding the geometrical properties of the multi-agent group formation and on providing a novel synthesis framework which exploits the group structure. In particular, the formation design and the collision avoidance conditions are casted as geometrical problems and optimization-based procedures are developed to solve them. Moreover, considerable advances in this direction are obtained by efficiently using MIP techniques (in order to derive an efficient description of the non-convex, non-connected feasible region which results from multi-agent collision and obstacle avoidance constraints) and stability properties (in order to analyze the uniqueness and existence of formation configurations). Lastly, some of the obtained theoretical results are applied on a challenging practical application. A novel combination of MPC and differential flatness (for reference generation) is used for the flight control of Unmanned Aerial Vehicles (UAVs).
|
6 |
Théorie des ensembles pour le contrôle robuste des systèmes non linéaires : Application à la chimiothérapie et les thérapies anti-angiogéniques / Set-theoretic methods for robust control of nonlinear systems : Application to chemotherapy and anti-angiogenic therapiesRiah, Rachid 25 November 2016 (has links)
Cette thèse vise à utiliser la modélisation mathématique avec les outils du contrôle avancé, afin de guider les thérapies pour assurer la contraction de la tumeur. Les buts de cette thèse sont la contribution au développement des méthodes de la théorie des ensembles pour le contrôle robuste des systèmes non linéaires et le développement d’outils numériques pour l’analyse et le contrôle de la croissance tumorale en présence de chimiothérapie et=ou de traitement anti-angiogénique. Génériquement, dans le contexte de la théorie du contrôle, les techniques qui sont théoriquement basées sur certaines propriétés des sous-ensembles de l’espace d’état du système pourraient être désignées comme des méthodes de la théorie des ensembles. Dans la première partie, nous passons en revue les définitions, concepts et outils de la théorie des ensembles existants dans la littérature pour réponde efficacement à des problématiques de contrôle des systèmes linéaires et non linéaires avec contraintes dures et incertitudes. Dans ce cadre, nous nous intéressons à deux propriétés des ensembles qui sont l’invariance et la contraction. Les problèmes liés à la stabilité des systèmes peuvent être formulés en termes de calcul de leurs domaines d’attraction. Pour des fins de développement, nous rappelons les méthodes de la littérature pour la caractérisation de ces domaines d’attraction pour les systèmes linéaires et non linéaires. Une application importante de ces méthodes est le contrôle de la croissance tumorale en présence de différents traitements. Car dans cette application, plusieurs contraintes peuvent être posées pour éviter l’intoxication des patients pendant les traitements et les méthodes de la théorie des ensembles peuvent les prendre en compte facilement. Pour cette application, nous proposons une méthodologie pour déterminer les domaines d’attraction pour les modèles mathématiques choisis pour simuler la croissance tumorale. Dans la deuxième partie, nous proposons des méthodes de la théorie des ensemble pour la caractérisation des domaines d’attraction pour les systèmes non linéaires incertains. Au début, nous développons des conditions suffisantes pour l’invariance et la contraction d’un ellipsoïde pour des systèmes saturés. Ces conditions permettent de déterminer implicitement une fonction de Lyapunov quadratique locale. Nous montrerons que l’approche proposée est moins conservatrice que celles de la littérature, et donnerons un algorithme pour la caractérisation de l’ellipsoïde invariant et contractif. Pour les systèmes non linéaires incertains, nous développons une condition suffisante pour l’invariance contrôlable robuste pour le cas des incertitudes paramétriques. Une méthode basée sur cette condition est développée pour la caractérisation des domaines d’attraction des systèmes avec ces incertitudes. Ensuite, nous nous concentrons sur l’étude des systèmes non linéaires avec incertitudes additives, et nous donnons également une autre méthode pour la caractérisation de leurs domaines d’attraction. Ces méthodes sont des méthodes facilement traitables en utilisant les outils de l’optimisation convexe. Dans la troisième partie, nous développons des outils numériques pour la caractérisation des domaines d’attraction pour les modèles de la croissance tumorale en présence de traitements, en particulier la chimiothérapie et le traitement anti-angiogénique. Ces domaines contiennent tous les états des patients pour lesquels ils existent des protocoles de traitement efficaces. Dans ce cadre, nous considérons que les modèles sont incertains car les paramètres exactes qui les définissent sont en pratique inconnus. Ces outils sont basés sur les méthodes rappelées et développées dans cette thèse. Plusieurs informations utiles pour une thérapie tumorale efficace peuvent être extraites de ces domaines. / This thesis aims at using the mathematical modeling with advanced control tools to guide therapies for the contraction of the tumor. The aims of this thesis are the contribution to the development of the set-theoretic methods for robust control of nonlinear systems and the development of analytical tools for the analysis and control of tumor growth in presence of chemotherapy and/oranti-angiogenic therapy. Generically, in the context of control theory, techniques that are theoretically based on some properties of subsets of the system state space could be referred as set-theoretic methods.In the first part, we review the definitions, concepts and tools of the existing set-theoretic methods in the literature to respond effectively to the control issues of linear and nonlinear systems with hard constraints and uncertainties. In this context, we are interested in two properties of sets that are invariance and contractiveness. The problems associated with the stability of the systems may be formulated in terms of calculation of their domain of attraction. For development purposes, we recall methods from the literature for characterizing these domains of attraction for linear and nonlinear systems. An important application of these methods is the control of tumor growth in the presence of different treatments. For this application, several constraints can be imposed in order to avoid the patient intoxications during the treatments and the set-theoretic methods can consider easily these constraints. For this latter application, we propose a methodology to estimate the domains of attraction for the mathematical models chosen to simulate the tumor growth.In the second part, we propose set-theoretic methods for the characterization of the domains ofattraction for linear and nonlinear uncertain systems. At the beginning, we develop sufficient conditions for the invariance and contractiveness of an ellipsoid for saturated systems. These conditions allow implicitly determining a local Lyapunov function. We will show that the proposed approach is less conservative than those in the literature, and we give an algorithm for characterizing the invariant ellipsoids. For uncertain nonlinear systems, we develop a sufficient condition for the robust controlled invariance in the case of parametric uncertainties. A method based on this condition is developed for characterizing the domains of attraction for nonlinear systems with these uncertainties. Then we focus on the study of nonlinear systems with additive uncertainties, and we also give a method for the characterization of their domains of attraction. These methods are easily treatable using convex optimization tools.In the third part, we develop numerical tools for characterizing the domains of attraction for themodels of tumor growth in the presence of treatments, particularly chemotherapy and anti-angiogenictreatment. These domains contain all the states of the patients for whom effective treatment protocols exist. In this context, we consider that the models are uncertain and in particular the parameters that are unknown in practice. These tools are based on the methods developed in this thesis. Several useful informations for effective tumor therapy can be extracted from these domains.
|
7 |
Commande prédictive sous contraintes de sécurité pour des systèmes dynamiques Multi-Agents / Safe predictive control for Multi-Agent dynamical systemsNguyen, Minh Tri 10 October 2016 (has links)
Cette thèse porte sur des techniques de commande à base d’optimisation dans le cadre des systèmes dynamiques Multi-Agents sous contraintes, plus particulièrement liées à l’évitement des collisions. Dans un contexte ensembliste, l’évitement des collisions au sein de la formation se traduit par des conditions de non intersection des régions de sécurité caractéristiques à chaque agent/obstacle. Grace à sa capacité à gérer les contraintes, la commande prédictive a été choisie parmi les méthodes de synthèse fondées sur des techniques d’optimisation. Tout d’abord, une structure de type leader-suiveur est considérée comme une architecture décentralisée élémentaire. La zone de fonctionnement de chaque suiveur est décidée par le leader et puis une loi de commande locale est calculée afin de garantir que les suiveurs restent à l’intérieur de la zone autorisée, permettant d’éviter les collisions. Ensuite, un déploiement des agents fondé sur l’approche de commande prédictive décentralisée, utilisant des partitions dynamiques de Voronoi, est proposé, permettant de ramener chaque agent vers l’intérieur de sa cellule Voronoi. Une des contributions a été de considérer le centre de Chebyshev comme cible à l’intérieur de chaque cellule. D’autres solutions proposent l’utilisation du centre de masse ou du centre obtenu par l’interpolation des sommets. Finalement, des méthodes ensemblistes sont utilisées pour construire un niveau supplémentaire de détection de défauts dans le cadre du système Multi-Agents. Cela permet l’exclusion des agents défectueux ainsi que l’intégration des agents extérieurs certifiés sans défauts dans la formation en utilisant des techniques de commande prédictive centralisée. / This thesis presents optimizationbased control techniques for dynamical Multi-Agent systems (MAS) subject to collision avoidance constraints. From the set-theoretic point of view, collision avoidance objective can be translated into non-overlapping conditions for the safety regions characterizing each agent/obstacle while maintaining the convergence towards a specified formation. Among the successful optimizationbased control methods, Model Predictive Control (MPC) is used for constraints handling. First, a leader-follower structure is considered as a basic decentralized architecture. The followers functioning zone assignment is decided by the leader and then the local linear feedback control is computed such that the follower operates strictly inside its authorized zone, offering anti-collision guarantees. Second, a dynamic Voronoi partition based deployment of the agents using an inner target driver is developed. The main novelty is to consider the Chebyshev center as the inner target for each agent, leading to an optimization-based decentralized predictive control design. In the same topic, other inner targets are considered such as the center of mass or vertex interpolated center. Third, set-theoretic tools are used to design a centralized FDI layer for dynamical MAS, leading to the exclusion of a faulty agent from the MAS formation and the integration of an external healthy/recovered agent in the current formation. The set-based FDI allows detecting and isolating these faulty agents to protect the current formation using centralized predictive control techniques.
|
8 |
The Index Bundle for Gap-Continuous Families, Morse-Type Index Theorems and Bifurcation / Das Indexbündel für Graphenstetige Familien, Morseartige Indexsätze und BifurkationWaterstraat, Nils 31 October 2011 (has links)
No description available.
|
9 |
Ανάλυση και έλεγχος γραμμικών και μη γραμμικών συστημάτων με περιορισμούς μέσω πολυεδρικών συναρτήσεων LyapunovΑθανασόπουλος, Νικόλαος 05 January 2011 (has links)
Το αντικείμενο της διατριβής αφορά την ανάλυση και τον έλεγχο δυναμικών συστημάτων με περιορισμούς στο διάνυσμα της εισόδου ή/ και στις μεταβλητές κατάστασης. Τα θεωρητικά εργαλεία που χρησιμοποιήθηκαν για την εξαγωγή των αποτελεσμάτων προέρχονται από τη θεωρία ευστάθειας Lyapunov, την αρχή σύγκρισης συστημάτων και τη θεωρία συνόλων, και οδήγησαν στην εδραίωση συνθηκών ευστάθειας και την ανάπτυξη συστηματικών μεθόδων εύρεσης λύσης στο πρόβλημα ελέγχου συγκεκριμένων κατηγοριών δυναμικών συστημάτων με περιορισμούς.
Πιο συγκεκριμένα, για την κατηγορία των γραμμικών συστημάτων συνεχούς και διακριτού χρόνου, προτάθηκε μια νέα μέθοδος επίλυσης του προβλήματος ευσταθειοποίησης συνόλου αρχικών συνθηκών και του υπολογισμού του μέγιστου θετικά αμετάβλητου ή αμετάβλητου με έλεγχο συνόλου παρουσία περιορισμών στις εισόδους ή/και στις καταστάσεις. Τα αποτελέσματα επεκτάθηκαν και στην κατηγορία των γραμμικών συστημάτων με πολυτοπικη αβεβαιότητα.
Επίσης, μελετήθηκε η κατηγορία των αυτοανάδρομων μοντέλων κινούμενου μέσου όρου (ARMA models). Αρχικά εδραιώθηκαν συνθήκες που εγγυώνται ευστάθεια για ένα συγκεκριμένο σύνολο αρχικών συνθηκών παρουσία περιορισμών. Τα αποτελέσματα αυτά εφαρμόστηκαν στην κατηγορία των δικτυωμένων συστημάτων ελέγχου (NCS), όπου υπολογίστηκε ένας κοινός γραμμικός νόμος ελέγχου ανατροφοδότησης κατάστασης για όλο το εύρος της καθυστέρησης της εισόδου.
Τέλος, μελετήθηκε η κατηγορία των διγραμμικών συστημάτων συνεχούς και διακριτού χρόνου. Αρχικά διατυπώθηκαν ικανές συνθήκες ύπαρξης πολυεδρικών συναρτήσεων Lyapunov για αυτήν την κατηγορία συστημάτων. Το πρόβλημα που μελετήθηκε είναι η ευσταθειοποίηση μιας συγκεκριμένης περιοχής του χώρου κατάστασης παρουσία περιορισμών στις εισόδους και τις καταστάσεις και προτάθηκε μια υποβέλτιστη λύση που οδηγεί στον υπολογισμό γραμμικού νόμου ελέγχου ανατροφοδότησης κατάστασης.
Όλα τα αποτελέσματα προκύπτουν από την επιλογή πολυεδρικών συναρτήσεων Lyapunov οι οποίες οδηγούν στο χαρακτηρισμό πολυεδρικών εκτιμήσεων της περιοχής ελκτικότητας και θετικά αμετάβλητων συνόλων. Τα κυριότερα οφέλη της επιλογής τέτοιων συναρτήσεων είναι η μη συντηρητική εκτίμησης της περιοχή ευστάθειας και η εδράιωση συνθηκών που οδηγούν σε συστηματικές μεθόδους επίλυσης των προβλημάτων ανάλυσης και ελέγχου, η λύση των οποίων προκύπτει από τη λύση γραμμικών προβλημάτων βελτιστοποίησης. / This dissertation considers the problem of stability analysis and control of dynamical systems under constraints in the input and/or state vector. The theoretical tools used arise from Lyapunov stability theory, comparison systems theory and set theoretic methods and lead to the determination of stability conditions and development of systematic methods that solve the control problem of constrained systems of particular type.
In specific, for linear discrete or continuous time systems, a novel method that leads to the solution of the initial condition set stabilization problem as well as the maximal controlled invariant set computation problem is presented. These results have been extended for the case of linear systems with polytopic uncertainty.
Also, the category of auto regressive moving average (ARMA) models is investigated. First, conditions that guarantee stability for a preassigned initial conditions set for constrained ARMA models are established. These results are applied to the category of networked control systems (NCS), were a single linear state feedback control law is computed for the whole range of the input delay.
Finally, the category of bilinear discrete-time or continuous-time systems is investigated. Initially, sufficient conditions which guarantee existence of polyhedral Lyapunov functions are presented. The problem studied here is the stabilization of an initial condition set in the presence of input and state constraints. The solution proposed is suboptimal and leads to the determination of a linear state feedback control law.
The choice of Lyapunov functions leads to the determination of a polyhedral approximation of the domain of attraction as well as polyhedral positively invariant sets. The main benefits of choosing this type of functions is the nonconservative estimation of the domain of attraction and the establishment of stability conditions that lead to systematic control design methods through the solution of linear programming problems.
|
10 |
Hybrid Zonotopes: A Mixed-Integer Set Representation for the Analysis of Hybrid SystemsTrevor John Bird (13877174) 29 September 2022 (has links)
<p>Set-based methods have been leveraged in many engineering applications from robust control and global optimization, to probabilistic planning and estimation. While useful, these methods have most widely been applied to analysis over sets that are convex, due to their ease in both representation and calculation. The representation and analysis of nonconvex sets is inherently complex. When nonconvexity arises in design and control applications, the nonconvex set is often over-approximated by a convex set to provide conservative results. However, the level of conservatism may be large and difficult to quantify, often leading to trivial results and requiring repetitive analysis by the engineer. Nonconvexity is inherent and unavoidable in many applications, such as the analysis of hybrid systems and robust safety constraints. </p>
<p>In this dissertation, I present a new nonconvex set representation named the hybrid zonotope. The hybrid zonotope builds upon a combination of recent advances in the compact representation of convex sets in the controls literature with methods leveraged in solving mixed-integer programming problems. It is shown that the hybrid zonotope is equivalent to the union of an exponential number of convex sets while using a linear number of continuous and binary variables in the set’s representation. I provide identities for, and derivations of, the set operations of hybrid zonotopes for linear mappings, Minkowski sums, generalized intersections, halfspace intersections, Cartesian products, unions, complements, point containment, set containment, support functions, and convex enclosures. I also provide methods for redundancy removal and order reduction to improve the compactness and computational efficiency of the represented sets. Therefore proving the hybrid zonotopes expressive power and applicability to many nonconvex set-theoretic methods. Beyond basic set operations, I specifically show how the exact forward and backward reachable sets of linear hybrid systems may be found using identities that are calculated algebraically and scale linearly. Numerical examples show the scalability of the proposed methods and how they may be used to verify the safety and performance of complex systems. These exact methods may also be used to evaluate the level of conservatism of the existing approximate methods provided in the literature. </p>
|
Page generated in 0.0515 seconds