Reachability Computation and Parameter Synthesis for Polynomial Dynamical Systems
Calcul d'atteignabilité et synthèse de paramètres pour systèmes dynamiques polynomiaux
Résumé
Dynamical systems are important mathematical models used to describe the temporal evolution of systems.Often dynamical systems are equipped with parameters that allow the models to better capture the characteristicsof the abstracted phenomena. An important question around dynamical systems isto formally determine whether a model (biased by its parameters) behaves well.In this thesis we deal with two main questions concerning discrete-time polynomial dynamical systems:1) the reachability computation problem, i.e, given a set of initial conditions and a set ofparameters, compute the set of states reachable by the system in a bounded time horizon;2) the parameter synthesis problem, i.e., given a set of initial conditions,a set of parameters, and a specification, find the largestset of parameters such that all the behaviors of the system staring from the set ofinitial conditions satisfy the specification.The reachability computation problem for nonlinear dynamical systems is well known for being nontrivial.Difficulties arise in handling and representing sets generated by nonlinear transformations.In this thesis we adopt a common technique that consistsin over-approximating the complex reachable sets with sets that are easy to manipulate.The challenge is to determine accurate over-approximations.We propose methods to finely over-approximate the images of sets using boxes,parallelotopes, and a new data structure called parallelotope bundles (that are collections of parallelotopeswhose intersections symbolically represent polytopes). These approximation techniquesare the basic steps of our reachability algorithm.The synthesis of parameters aims at determining the valuesof the parameters such that the system behaves as expected. This feature can beused, for instance, to tune a model so that it imitates the modeledphenomenon with a sufficient level of precision. The contributions of thisthesis concerning the parameter synthesis problem are twofold. Firstly,we define a new semantics for the Signal Temporal Logic (STL) that allows oneto formalize a specification and reason on sets of parameters and flows of behaviors.Secondly, we define an algorithm to compute the synthesis semanticsof a formula against a discrete-time dynamical system. The result of the algorithmconstitutes a conservative solution of the parameter synthesis problem.The developed methods for both reachability computation and parameter synthesisexploit and improve Bernstein coefficients computation.The techniques defined in this thesis have been implemented ina tool called Sapo. The effectiveness of our methods is validatedby the application of our tool to several polynomial dynamical systems.
Les systèmes dynamiques sont des importants modèles mathématiques utilisés pour décrire l'évolution temporelle des systèmes.Souvent, les systèmes dynamiques sont équipées avec des paramètres qui permettent les modèles de mieux saisir les caractéristiques des phénomènes abstraits. Une question importante autour des systèmes dynamiques est de déterminer formellement si un modèle (sollicité par ses paramètres) se comporte bien.Dans cette thèse, nous traitons deux questions principales concernant les systèmes dynamiques polynomiaux en temps discret:1) problème de calcul de la d'atteignabilité, i.e., étant donné un ensemble de conditions initiales et un ensemble deparamètres, calculer l'ensemble des états atteignable par le système dans un horizon de temps borné;2) le problème de la synthèse de paramètre, i.e., étant donné un ensemble de conditions initiales,un ensemble de paramètres, et une spécification, trouver l'ensemble de paramètres le plus grandtels que tous les comportements du système fixes de l'ensemble de conditions initiales satisfont la spécification.Le problème de calcul d'atteignabilité pour les systèmes dynamiques non linéaires est bien connu pour être non triviale.Des difficultés surgissent dans le traitement et la représentation des ensembles générés par les transformations non linéaires.Dans cette thèse, nous adoptons une technique courante qui consistede rapprocher les ensembles atteignable avec des ensembles complexes qui sont faciles à manipuler.Le défi est de déterminer précis sur-approximations.Nous proposons des méthodes pour rapprocher finement les images des ensembles utilisant des boîtes,parallelotopes, et une nouvelle structure appelé parallelotope bundle (ce sont des collections de parallelotopes dont les intersections représentent symboliquement polytopes). Ces techniques d'approximation sont les étapes de base de notre algorithme d'accessibilité.La synthèse des paramètres vise à déterminer les valeursdes paramètres tels que le système se comporte comme prévu. Cette fonctionnalité peut êtreutilisé, par exemple, pour régler un modèle qu'il imite la modéliséphénomène avec un niveau suffisant de précision. Les contributions de cettethèse sur le problème de synthèse de paramètres sont de deux ordres. Premièrement,nous définissons une nouvelle sémantique pour le signal logique temporelle (STL) que nous permetde formaliser une spécification et de raisonner sur des ensembles de paramètres et des flux de comportements.Deuxièmement, nous définissons un algorithme pour calculer la sémantique de synthèsed'une formule à l'encontre d'un système dynamique à temps discret. Le résultat de l'algorithmeconstitue une solution conservatrice du problème de la synthèse de paramètre.Les méthodes développées exploitent et améliorent le calcul des coefficients de Bernstein.Les techniques définies dans cette thèse ont été mises en œuvreun tool appelé Sapo. L'efficacité de notre méthode est validéepar l'application de notre tool pour plusieurs systèmes dynamiques polynomiaux.
Origine : Version validée par le jury (STAR)