Efficient Synthesis of Safety Controllers using Symbolic Models and Lazy Algorithms
Synthèse efficace des contrôleurs de sécurité à l'aide de modèles symboliques et d'algorithmes paresseux
Résumé
This thesis focuses on the development of efficient abstraction-based controller synthesis approaches for cyber-physical systems (CPS). While abstraction-based methods for CPS design have been the subject of intensive research over the last decades, the scalability of these techniques remains an issue. This thesis focus on developing lazy synthesis algorithms for safety specifications. Safety specifications consist in maintaining the trajectory of the system inside a given safe set. This specification is of the utmost importance in many engineering problems, often prioritized over other performance requirements. Lazy approaches outperform the classical synthesis algorithm [Tabuada, 2009] by avoiding computations, which are non-essential for synthesis goals. Chapter 1 motivates the thesis and discusses the state of the art. Chapter 2 structures the existing lazy synthesis approaches and emphasizes three sources of efficiency: information about a priori controllable states, priorities on inputs, and non-reachable from initial set states. Chapter 3 proposes an algorithm, which iteratively explores states on the boundary of controllable domain while avoiding exploration of internal states, supposing that they are safely controllable a priory. A closed-loop safety controller for the original problem is then defined as follows: we use the abstract controller to push the system from a boundary state back towards the interior, while for inner states, any admissible input is valid. Chapter 4 presents an algorithm that restricts the controller synthesis computations to reachable states only while prioritizing longer-duration transitions. The original system is abstracted by a symbolic model with an adaptive grid. Moreover, a novel type of time sampling is also considered. Instead of using transitions of predetermined duration, the duration of the transitions is constrained by state intervals that must contain the reachable set. Chapter 5 is dedicated to monotone transition systems. The introduced lazy synthesis approach benefits from a monotone property of transition systems and the ordered structure of the state (input) space, and the fact that directed safety specifications are considered. The considered class of specifications is then enriched by intersections of upper and lower-closed safety requirements. Chapter 6 concludes the discussion and raises new issues for future research.
Cette thèse porte sur le développement d'approches efficaces de synthèse de contrôleurs basées sur l'abstraction pour les systèmes cyber-physiques (CPS). Alors que les méthodes basées sur l'abstraction pour la conception de CPS ont fait l'objet de recherches intensives au cours des dernières décennies, l'évolutivité de ces techniques reste un problème. Cette thèse se concentre sur le développement d'algorithmes de synthèse paresseuse pour les spécifications de sécurité. Les spécifications de sécurité consistent à maintenir la trajectoire du système à l'intérieur d'un ensemble sûr donné. Cette spécification est de la plus haute importance dans de nombreux problèmes d'ingénierie, souvent prioritaires par rapport à d'autres exigences de performance. Les approches paresseuses surpassent l'algorithme de synthèse classique [Tabuada, 2009] en évitant les calculs, qui ne sont pas essentiels pour les objectifs de synthèse. Le chapitre 1 motive la thèse et présente l'état de l'art. Le chapitre 2 structure les approches de synthèse paresseuses existantes et met l'accent sur trois sources d'efficacité : les informations sur les états contrôlables a priori, les priorités sur les entrées et les états non accessibles à partir de l'ensemble initial. Le chapitre 3 propose un algorithme, qui explore itérativement les états à la frontière du domaine contrôlable tout en évitant l'exploration des états internes, en supposant qu'ils sont contrôlables en toute sécurité a priori. Un contrôleur de sécurité en boucle fermée pour le problème d'origine est alors défini comme suit : nous utilisons le contrôleur abstrait pour repousser le système d'un état limite vers l'intérieur, tandis que pour les états internes, toute entrée admissible est valide. Le chapitre 4 présente un algorithme qui restreint les calculs de synthèse du contrôleur aux seuls états atteignables tout en privilégiant les transitions de plus longue durée. Le système original est abstrait par un modèle symbolique avec une grille adaptative. De plus, un nouveau type d'échantillonnage temporel est également envisagé. Au lieu d'utiliser des transitions de durée prédéterminée, la durée des transitions est contrainte par des intervalles d'état qui doivent contenir l'ensemble accessible. Le chapitre 5 est consacré aux systèmes de transition monotones. L'approche de synthèse paresseuse introduite bénéficie d'une propriété monotone des systèmes de transition et de la structure ordonnée de l'espace d'état (d'entrée), et du fait que des spécifications de sécurité dirigées sont prises en compte. La classe de spécifications considérée s'enrichit alors d'intersections d'exigences de sécurité supérieures et inférieures fermées. Le chapitre 6 conclut la discussion et soulève de nouvelles questions pour les recherches futures.
Origine : Version validée par le jury (STAR)