In this thesis, we develop methods leading towards the distributed control of spatio-temporally constrained systems. Overall, we focus on two different approaches: a model predictive control approach and an approach based on ensuring set-invariance via control barrier functions. Developing a distributed control framework for spatio-temporally constrained systems is challenging since multiple subsystems are interconnected via time-varying state constraints. Often, such constraints are only implicitly given as logic formulas, for example in Signal Temporal Logic (STL). Our approach to dealing with spatio-temporal constraints is as follows. We aim at combining the computational efficiency of low-level feedback controllers with planning algorithms. Low-level feedback controllers shall ensure the satisfaction of parts of spatio-temporal constraints such as coupling state constraints or short term time-constraints. In contrast, planning algorithms account for those parts that require computationally intense planning operations. Powerful low-level controllers can simplify the planning task significantly. For this reason, the focus of this thesis is on the development of low level feedback controllers.  In the first part, we focus on handling coupling state constraints using a model predictive control (MPC) approach. Commonly, the distributed handling of coupling state constraints requires a sequential or iterative MPC scheme which however is computationally time-intense. We address this issue by employing consistency constraints to develop a parallelized distributed model predictive controller (DMPC). By using consistency constraints, each subsystem guarantees to its neighbors that its states stay within a particular neighborhood around a reference trajectory. Furthermore, we propose extensions to robust and iterative schemes. Building up on this, also systems with bounded dynamic couplings can be controlled. In the second part, we focus on methods for ensuring set-invariance. In particular, we focus on control barrier functions (CBF). We show how spatio-temporal constraints that comprise disjunctions (logic OR) can be encoded in non-smooth time-varying control barrier functions and how subgradients can be used to synthesize an efficient gradient-based controller. For these results, controllability assumptions must be invoked. To extend the results to systems with weaker controllability properties, we investigate the connection between controllability properties and the construction of CBFs. As a result, we propose a construction method for CBFs based on finite horizon predictions. The constructed CBF exhibits favorable properties for the extension of the previous results on encoding spatio-temporal constraints in CBFs to systems with weaker controllability properties. At last, we investigate with a case study how set-invariance methods can be used to implicitly coordinate systems subject to coupled state constraints. Our proposed method is fully decentralized and subsystems coordinate themselves purely via their actions and the adjustment of their individual constraints. In the end, we draw a conclusion and outline how the presented results contribute to the development of a distributed control framework for spatio-temporally constrained systems. / I den här avhandlingen utvecklar vi metoder som leder till distribuerad styrning av tillstånds-temporalt begränsade system. Vi följer två olika tillvägagångssätt: å ena sidan en modellprediktiv styrning och å andra sidan ett tillvägagångssätt som bygger på att säkerställa invarians i mängden via kontrollbarriärfunktioner. Det är en utmaning att utveckla ett ramverk för distribuerad styrning för tillstånds-temporalt begränsade system, eftersom flera delsystem är sammankopplade via sina tillståndsbegränsningar som varierar över tiden. Ofta ges sådana begränsningar endast implicit som logiska formler, till exempel i Signal Temporal Logic (STL).  Vår metod för att hantera tillstånds- och tidsmässiga begränsningar är följande. Vi strävar efter att kombinera beräkningseffektiviteten hos återkopplingsregulatorer på låg nivå med planeringsalgoritmer. Återkopplingsregulatorer på låg nivå skall säkerställa att delar av de tillstånds- och tidsmässiga begränsningarna uppfylls, t.ex. sammankopplande tillståndsbegränsningar eller kortsiktiga tidsbegränsningar, medan planeringsalgoritmerna tar hänsyn till de delar som kräver beräkningsintensiva planeringsoperationer. Kraftfulla styrsystem på låg nivå kan förenkla planeringsuppgiften avsevärt. Därför fokuserar vi i denna avhandlingen på utvecklingen av återkopplingsregulatorer på låg nivå.  I den första delen fokuserar vi på att hantera sammankopplande tillståndsbegränsningar för distribuerade system med hjälp av en modell prediktiv styrning (MPC). Vanligtvis kräver den distribuerade hanteringen av kopplingsbegränsningar ett sekventiellt eller iterativt MPC-system som dock är tidskrävande. Därför utvecklar vi en parallelliserad distribuerad modell prediktiv styrning (DMPC) baserad på konsistensbegränsningar. Därigenom garanterar ett delsystem till sina grannar att det håller sig inom ett visst område runt en referensbana. Den generiska formuleringen av vårt DMPC-system möjliggör flera realiseringar. En särskild realisering föreslås. Dessutom utvecklas utvidgningar till ett robust och iterativt system samt ett DMPC-system för system med begränsade dynamiska kopplingar. I den andra delen fokuserar vi på metoder för att säkerställa invariansen av mängder. Vi fokuserar särskilt på kontrollbarriärfunktioner (CBF). Vi visar hur tillstånds- och tidsmässiga begränsningar kan inkodas i icke-glatta tidsvarierande kontrollbarriärfunktioner och hur subgradienter kan användas för att konstruera en effektiv gradientbaserad styrning. För dessa resultat måste antaganden om kontrollerbarhet åberopas. För att utvidga detta resultat till system med svagare kontrollerbarhetsegenskaper undersöker vi kopplingen mellan dynamiska systems kontrollerbarhetsegenskaper och konstruktionen av en CBF. Som ett resultat av detta föreslår vi en konstruktionsmetod för CBF:er som bygger på förutsägelser för ändliga horisonter. Den konstruerade CBF:n uppvisar gynnsamma egenskaper för att utvidga det tidigare resultatet om kodning av rums-temporala begränsningar i CBF:er till system med svagare kontrollerbarhetsegenskaper. Slutligen undersöker vi med hjälp av en fallstudie hur metoder för att säkerställa invariansen av mängder kan användas för att implicit samordna system som är kopplade via tillståndsbegränsningar. Vår föreslagna metod är helt decentraliserad och delsystemen samordnar sig själva endast via sina handlingar och justeringen av sina individuella begränsningar. Slutligen drar vi en slutsats och beskriver hur de presenterade resultaten bidrar till utvecklingen av ett ramverk för distribuerad styrning av tillstånds- och tidsmässigt begränsade system. / <p>QC 20230520</p>

Les systèmes Matériels/Logiciels deviennent indispensables dans tous les aspects de la vie quotidienne. La présence croissante de ces systèmes dans les différents produits et services incite à trouver des méthodes pour les développer efficacement. Mais une conception efficace de ces systèmes est limitée par plusieurs facteurs, certains d'entre eux sont: la complexité croissante des applications, une augmentation de la densité d'intégration, la nature hétérogène des produits et services, la diminution de temps d’accès au marché. Une modélisation transactionnelle (TLM) est considérée comme un paradigme prometteur permettant de gérer la complexité de conception et fournissant des moyens d’exploration et de validation d'alternatives de conception à des niveaux d’abstraction élevés. Cette recherche propose une méthodologie d’expression de temps dans TLM basée sur une analyse de contraintes temporelles. Nous proposons d'utiliser une combinaison de deux paradigmes de développement pour accélérer la conception: le TLM d'une part et une méthodologie d’expression de temps entre différentes transactions d’autre part. Cette synergie nous permet de combiner dans un seul environnement des méthodes de simulation performantes et des méthodes analytiques formelles. Nous avons proposé un nouvel algorithme de vérification temporelle basé sur la procédure de linéarisation des contraintes de type min/max et une technique d'optimisation afin d'améliorer l'efficacité de l'algorithme. Nous avons complété la description mathématique de tous les types de contraintes présentées dans la littérature. Nous avons développé des méthodes d'exploration et raffinement de système de communication qui nous a permis d'utiliser les algorithmes de vérification temporelle à différents niveaux TLM. Comme il existe plusieurs définitions du TLM, dans le cadre de notre recherche, nous avons défini une méthodologie de spécification et simulation pour des systèmes Matériel/Logiciel basée sur le paradigme de TLM. Dans cette méthodologie plusieurs concepts de modélisation peuvent être considérés séparément. Basée sur l'utilisation des technologies modernes de génie logiciel telles que XML, XSLT, XSD, la programmation orientée objet et plusieurs autres fournies par l’environnement .Net, la méthodologie proposée présente une approche qui rend possible une réutilisation des modèles intermédiaires afin de faire face à la contrainte de temps d’accès au marché. Elle fournit une approche générale dans la modélisation du système qui sépare les différents aspects de conception tels que des modèles de calculs utilisés pour décrire le système à des niveaux d’abstraction multiples. En conséquence, dans le modèle du système nous pouvons clairement identifier la fonctionnalité du système sans les détails reliés aux plateformes de développement et ceci mènera à améliorer la "portabilité" du modèle d'application. / Hardware/Software (Hw/Sw) systems are likely to become essential in all aspects of everyday life. The increasing penetration of Hw/Sw systems in products and services creates a necessity of their efficient development. However, the productive design of these systems is limited by several factors, some of them being the increasing complexity of applications, the increasing degree of integration, the heterogeneous nature of products and services as well as the shrinking of the time-to-market delay. Transaction Level Modeling (TLM) paradigm is considered as one of the most promising simulation paradigms to break down the design complexity by allowing the exploration and validation of design alternatives at high levels of abstraction. This research proposes a timing expression methodology in TLM based on temporal constraints analysis. We propose to use a combination of two paradigms to accelerate the design process: TLM on one hand and a methodology to express timing between different transactions on the other hand. Using a timing specification model and underlining timing constraints verification algorithms can decrease the time needed for verification by simulation. Combining in one framework the simulation and analytical design exploration methods can improve the analytical power of design verification and validation. We have proposed a new timing verification algorithm based on the linearization procedure and an optimization technique to improve its efficiency. We have completed the mathematical representation of all constraint types discussed in the literature creating in this way a unified timing specification methodology that can be used in the expression of a wider class of applications than previously presented ones. We have developed the methods for communication structure exploration and refinement that permitted us to apply the timing verification algorithms in system exploration at different TLM levels. As there are many definitions of TLM and many development environments proposing TLM in their design cycle with several pro and contra, in the context of our research we define a hardware/software (Hw/Sw) specification and simulation methodology which supports TLM in such a way that several modeling concepts can be seen separately. Relying on the use of modern software engineering technologies such as XML, XSLT, XSD, object oriented programming and others supported by the .Net Framework, an approach that makes an intermediate design model reuse possible in order to cope with time-to-market constraint is presented. The proposed TLM design methodology provides a general approach in system modeling that separates various application modeling aspects from system specification: computational models, used in application modeling, supported by the language used for the functional specification and provided by simulator. As a result, in the system model we can clearly identify system functionality without details related to the development platform thereby leading to a better “portability” of the application model.

Le travail présenté s'inscrit dans le contexte de la théorie des systèmes linéaires dans les dioïdes. La motivation initiale de cette étude a été de contribuer à l'analyse et la commande de systèmes linéaires dans max-plus en utilisant spécifiquement une approche géométrique. La contribution de cette thèse est centrée sur deux problèmes. La première partie est dédiée à l'étude de la relation entre les notions d'invariance contrôlée et d'invariance contrôlée par retour d'état dynamique dans un semi-anneau. Cette relation permet de montrer l'équivalence de ces deux notions. La deuxième partie concerne un problème original dans la théorie des systèmes linéaires dans max-plus, il s'agit de la synthèse d'une loi de commande par retour d'état, qui permette de satisfaire un ensemble de spécifications exprimées sous la forme de restrictions sur l'état du système, avec une approche géométrique. Il s'agit plus précisément de commander des systèmes à événements discrets décrits par un modèle linéaire dans max-plus. Nous définissons et caractérisons l'ensemble des conditions initiales admissibles, lesquelles sont à l'origine de solutions non décroissantes. Les restrictions temporelles imposées à l'espace d'état du système sont décrites par le semi-module défini par l'image de l'étoile de Kleene de la matrice associée aux restrictions temporelles. Les propriétés géométriques de ce semi-module permettant de garantir que l'évolution du système en boucle fermée satisfasse les restrictions sont étudiées. Des conditions suffisantes concernant l'existence d'une loi de commande causale par retour d'état statique sont présentées. Le calcul des lois de commande causales est également présenté. Pour illustrer l'application de cette approche, deux problèmes de commande sont présentés. / This work is in the context of the theory of linear Systems in the dioids. The initial motivation of this study was to contribute to the analysis and control of max-plus linear systems, specifically using a geometric approach. The contribution of this thesis focuses on two issues. The first part is dedicated to study of the relationship between the concepts of controlled invariance and dynamic state feedback controlled invariance in a semi-ring. This relationship allows us to show the equivalence of these two concepts. The second part relates to a new problem in the theory of max-plus linear systems, it is the synthesis, with a geometric approach, of a static state feedback control law, in order to satisfy a set of specifications that apply to the state space of the system. This is specifically to control of discrete event systems described by a linear model in max-plus. We define and characterize the set of admissible initial conditions, which are the cause of non-decreasing solutions. Temporal restrictions on the system state space are described by the semi-module defined by the image of the Kleene star of the matrix associated with time restrictions. The geometric properties of this semi-module are studied. Sufficient conditions for the existence of a causal control law by static feedback are presented. Calculating causal control laws is also presented. To illustrate the application of this approach, two control problems are presented.

Les systèmes Matériels/Logiciels deviennent indispensables dans tous les aspects de la vie quotidienne. La présence croissante de ces systèmes dans les différents produits et services incite à trouver des méthodes pour les développer efficacement. Mais une conception efficace de ces systèmes est limitée par plusieurs facteurs, certains d'entre eux sont: la complexité croissante des applications, une augmentation de la densité d'intégration, la nature hétérogène des produits et services, la diminution de temps d’accès au marché. Une modélisation transactionnelle (TLM) est considérée comme un paradigme prometteur permettant de gérer la complexité de conception et fournissant des moyens d’exploration et de validation d'alternatives de conception à des niveaux d’abstraction élevés. Cette recherche propose une méthodologie d’expression de temps dans TLM basée sur une analyse de contraintes temporelles. Nous proposons d'utiliser une combinaison de deux paradigmes de développement pour accélérer la conception: le TLM d'une part et une méthodologie d’expression de temps entre différentes transactions d’autre part. Cette synergie nous permet de combiner dans un seul environnement des méthodes de simulation performantes et des méthodes analytiques formelles. Nous avons proposé un nouvel algorithme de vérification temporelle basé sur la procédure de linéarisation des contraintes de type min/max et une technique d'optimisation afin d'améliorer l'efficacité de l'algorithme. Nous avons complété la description mathématique de tous les types de contraintes présentées dans la littérature. Nous avons développé des méthodes d'exploration et raffinement de système de communication qui nous a permis d'utiliser les algorithmes de vérification temporelle à différents niveaux TLM. Comme il existe plusieurs définitions du TLM, dans le cadre de notre recherche, nous avons défini une méthodologie de spécification et simulation pour des systèmes Matériel/Logiciel basée sur le paradigme de TLM. Dans cette méthodologie plusieurs concepts de modélisation peuvent être considérés séparément. Basée sur l'utilisation des technologies modernes de génie logiciel telles que XML, XSLT, XSD, la programmation orientée objet et plusieurs autres fournies par l’environnement .Net, la méthodologie proposée présente une approche qui rend possible une réutilisation des modèles intermédiaires afin de faire face à la contrainte de temps d’accès au marché. Elle fournit une approche générale dans la modélisation du système qui sépare les différents aspects de conception tels que des modèles de calculs utilisés pour décrire le système à des niveaux d’abstraction multiples. En conséquence, dans le modèle du système nous pouvons clairement identifier la fonctionnalité du système sans les détails reliés aux plateformes de développement et ceci mènera à améliorer la "portabilité" du modèle d'application. / Hardware/Software (Hw/Sw) systems are likely to become essential in all aspects of everyday life. The increasing penetration of Hw/Sw systems in products and services creates a necessity of their efficient development. However, the productive design of these systems is limited by several factors, some of them being the increasing complexity of applications, the increasing degree of integration, the heterogeneous nature of products and services as well as the shrinking of the time-to-market delay. Transaction Level Modeling (TLM) paradigm is considered as one of the most promising simulation paradigms to break down the design complexity by allowing the exploration and validation of design alternatives at high levels of abstraction. This research proposes a timing expression methodology in TLM based on temporal constraints analysis. We propose to use a combination of two paradigms to accelerate the design process: TLM on one hand and a methodology to express timing between different transactions on the other hand. Using a timing specification model and underlining timing constraints verification algorithms can decrease the time needed for verification by simulation. Combining in one framework the simulation and analytical design exploration methods can improve the analytical power of design verification and validation. We have proposed a new timing verification algorithm based on the linearization procedure and an optimization technique to improve its efficiency. We have completed the mathematical representation of all constraint types discussed in the literature creating in this way a unified timing specification methodology that can be used in the expression of a wider class of applications than previously presented ones. We have developed the methods for communication structure exploration and refinement that permitted us to apply the timing verification algorithms in system exploration at different TLM levels. As there are many definitions of TLM and many development environments proposing TLM in their design cycle with several pro and contra, in the context of our research we define a hardware/software (Hw/Sw) specification and simulation methodology which supports TLM in such a way that several modeling concepts can be seen separately. Relying on the use of modern software engineering technologies such as XML, XSLT, XSD, object oriented programming and others supported by the .Net Framework, an approach that makes an intermediate design model reuse possible in order to cope with time-to-market constraint is presented. The proposed TLM design methodology provides a general approach in system modeling that separates various application modeling aspects from system specification: computational models, used in application modeling, supported by the language used for the functional specification and provided by simulator. As a result, in the system model we can clearly identify system functionality without details related to the development platform thereby leading to a better “portability” of the application model.