Analyse algorithmique de systèmes hybrides polygonaux

A polygonal differential inclusion system (SPDI) is a non-deterministic planar hybrid system which can be represented by piecewise constant differential inclusions. In this thesis we are concerned with several theoretical and practical questions related to SPDIs such as reachability analysis and phase portrait construction. First we show that the reachability question for SPDIs is indeed decidable. Our procedure is not based on the computation of the reach-set but rather on the computation of the limit of individual trajectories. A key idea is the use of edge-to-edge one-dimensional affine Poincaré maps, the fix-points of which are easily computed. By taking advantage of this information, cycles can be accelerated in most cases. The above reachability algorithm has been implemented in a tool called SPeeDI. We next build the phase portrait of such systems. In particular, we identify the viability kernels of simple cycles. Such kernels are the set of starting points of trajectories that can keep rotating in the cycles forever. We also introduce the notion of controllability kernel of simple cycles as the set of points such that any two points of the set are reachable from each other via trajectories that remain on the set. We give non-iterative algorithms to compute both kernels. We obtain the SPDI phase portrait computing all the viability and controllability kernels. We finally study the decidability of the reachability problem for other 2-dimensional hybrid systems. We introduce hierarchical piecewise constant derivative systems (HPCDs) and 2-dimensional manifolds with piecewise constant derivative systems. We show that the reachability problem for the above two classes of systems is as hard as the reachability problem for piecewise affine maps that is known to be an open problem. We also show that the reachability question for slight extensions of HPCDs are undecidable.Les systèmes polygonaux à inclusions différentielles (SPDIs) sont des systèmes planaires non déterministes qui peuvent être représentés par des inclusions différentielles constantes par morceaux. Cette thèse porte sur les aspects théoriques et pratiques des SPDIs tels que le problème de l'atteignabilité et de la construction du portrait de phase. Nous montrons que le problème de l'atteignabilité est décidable pour les SPDIs. Notre procédure est basée sur le calcul des limites des trajectoires individuelles : l'idée sous-jacente est l'utilisation de fonctions de Poincaré unidimensionelles, pour lequelles on peut facilement calculer les points fixes et qui permettent dans la plupart des cas d'accélérer les cycles. Nous avons implanté cet algorithme d'atteignabilité dans l'outil SPeeDI. Ensuite, nous construisons le portrait de phase des SPDIs. Nous savons identifier les noyaux de viabilité des boucles simples. Il s'agit des ensembles de points initiaux de trajectoires restant dans la boucle. Nous introduisons la notion de noyau de controlabilité de boucles simples comme l'ensemble des points atteignables les uns à partir des autres par des trajectoires qui restent dans le noyau. Nous proposons un algorithme non itératif pour calculer ces deux noyaux, qui nous permet ensuite de construire le portrait de phase des SPDIs. Enfin, nous étudions la décidabilité du problème de l'atteignabilité pour d'autres classes de systèmes hybrides à deux dimensions : les systèmes hiérarchiques constants par morceaux (HPCDs) et les systèmes constants par morceaux, définis sur les surfaces. Nous montrons que le problème de l'atteignabilité pour ces deux classes de systèmes est équivalent à l'atteignabilité pour des systèmes affines par morceaux, dont la décidabilité est un problème ouvert. Nous montrons enfin que le problème de l'atteignabilité pour quelques extensions de HPCDs est indécidable