Practical course: State set representation techniques for hybrid systems


  • 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)



Name File
Timetable timetable
Introduction slides introduction
Optimization & Evaluation optimization


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_8exercise_8_solution


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 WS1516