MJK
28 October 2009 - 14h00
Reachability Analysis of Hybrid Systems with Linear Continuous Dynamics (Phd Defense)
by Colas Le Guernic from VERIMAG
Abstract: This thesis is devoted to the problem of computing reachable sets of linear and hybrid systems.
In the first part, after exposing existing approaches for reachability analysis of linear systems, we present the main contribution of the thesis: a new algorithmic scheme for linear time-invariant systems that definitely outperforms existing algorithms. As the exact implementation furnishes a representation of the reachable sets that is sometimes hard to manipulate, we propose an approximate version that is not subject to the wrapping effect, an uncontrolled growth of the approximation errors. We also discuss a variant of this algorithm specialized to support functions, a functional representation of convex sets.
In the second part, we extend this work to hybrid systems. We first show how to deal with the constraints on the continuous dynamics imposed by the invariants. Then, we present algorithms for approximating the intersection of the continuous reachable sets with hyperplanar guards.
Jury composé de:
- Nicolas Halbwachs (DR), Président (proposé)
- Bruce Krogh (Pr), Rapporteur
- Manfred Morari (Pr), Rapporteur
- Eugene Asarin (Pr), Examinateur
- Patrick Cousot (Pr), Examinateur
- Oded Maler (DR), Directeur de thèse
- Antoine Girard (MC), Co-directeur de thèse
