News
- The next meeting (box implementation presentation) will take place on Tuesday 10.11.2015, at 3:30pm in the I2 seminar-room.
- The next meetings are:
- Tue, 24.11.2015
- Tue, 08.12.2015
- Tue, 15.12.2015
- Tue, 12.01.2016
- Tue, 26.01.2016
- (Tue, 09.02.2016)
Files
Organization
| Name | File |
| Timetable | timetable |
| Introduction slides | introduction |
| Optimization & Evaluation | optimization |
Tasks
| Task | File |
| Task 0 | task_0 |
| Task 1 | task_1 |
| Task 2 | task_2 |
Additional material
| Name | File |
| Reachability analysis | 07_analysis |
| Polyhedra | 09_polyhedra |
| Exercise Polyhedra | exercise_8, exercise_8_solution |
Contents
Hybrid systems are systems with mixed discrete-continuous behavior. Hybrid automata are a well established modeling language for such hybrid systems. A hybrid automaton is similar to a discrete transition system, having a finite set of locations (control modes) and discrete transitions between them . This discrete model part is extended with a dynamical part by attaching differential equations to the locations; while control stays in a location, time goes by and the values of some (continuous) variables evolve continuously according to the differential equations in that location.
Correspondingly, a state of a hybrid system consists of a discrete and a continuous component, the latter being a point in the n-dimensional real space (specifying the values for n continuous variables), whereas state sets refer to a subset of the n-dimensional real space.
As hybrid automata often model safety-critical systems, their reachability analysis (computing the set of states that are reachable from a given set of initial states) is highly important. A basic prerequisite for the reachability analysis is the efficient over-approximative representation of state sets, i.e., the support of a data type for storing state sets and providing some operations on them, which are used in the reachability analysis. For this purpose, different geometric objects are in use, for example, boxes, convex polytopes or ellipsoids can be used to over-approximate subsets of the n-dimensional real space. The representation of, e.g., a convex polytope can be given by the set of its vertices. To use polytopes for state set representation in the reachability analysis we need, e.g. to compute the union and the intersection of two polytopes.
In the HyPro research project, funded by the German Research Council (DFG), we develop a library of such state set representation techniques. In this practical course we will improve parts of this library. Possible tasks cover:
– reduction techniques (for example, over-approximate a polytope by another polytope whose representation is smaller)
– conversion techniques (for example, over-approximate a polytope by an ellipsoid)
– improve the efficiency of certain operations (possibly on the cost of precision).
The results will be evaluated in the context of some predefined reachability analysis problems.
Organisational issues
This is a practical course classified in Theoretical Computer Science.
There will be weekly meetings. The dates will be fixed at the beginning of the semester.
Contact information
If you have any questions concerning this lab, please contact Stefan Schupp
Evaluation