Referent: Dipl.-Inform. Ibtissem Ben Makhlouf
Titel: Comparative Evaluation and Improvement of Computational Approaches to Reachability Analysis of Linear Hybrid Systems
Abstract:
Hybrid systems combine discrete events and continuous behaviors in the same framework. The discrete part is represented as transitions between locations, in which the continuous part is described as a differential equation and that generally in a confined invariant domain. The transitions are commonly triggered if the corresponding guard conditions are fulfilled. After an eventually reset condition, the hybrid automaton springs to the next location if its invariant condition is also met. The reachability analysis consists in computing all states reached by a hybrid automaton starting with an initial set. We focused in this work on techniques combining set mapping theory and geometric set approximations to compute an over-approximation of the reachable sets. Our work began with an exhaustive evaluation and comparison of already available tools. For this purpose a suite of benchmarks has been collected. Based on the results of this study, we decided to implement first the technique using zonotopes as approximating sets. Diverse techniques for handling guard conditions described as hyperplanes, halfspaces and polyhedra were considered. We therefore performed a performance comparison of different intersection methods. In addition, we compared them in combination with many clustering approaches for dealing with the bundle of intersecting sets in transitions. In a further step, we implemented the support function based techniques in a toolbox allowing users the choice between different approximation methods for the initial set, the input contribution, optimization solvers as well as different algorithms for computing intersections between reachable sets, guards and invariants. This toolbox allows users to configure the reachability analysis by combining different available options. In particular, it offers the possibility to compare their performance and to change the choice if the already chosen method or optimization solver fails. We finally demonstrated potential applications of the reachability analysis using a networked platoon of vehicles as case study. We first carried out a reachability analysis to determine the shortest safe gaps between vehicles in a platoon controlled using Linear Matrix Inequalities. We showed then how reachability can help by the choice of the best performing platoon controller. The controllers were computed using H2 or H∞ optimal control design. Afterwards, we considered a platoon approaching an intersection as application to demonstrate how time and state critical conditions can be determined using reachability analysis. These conditions are decisive for a safe and reliable management of the intersection.
Es laden ein: Die Dozenten der Informatik