CS Seminar: Fabio Torrisi, November 18, 2003

Fabio Torrisi,
Automatic Control Laboratory, Swiss Federal Institute of Technology, Zurich, Switzerland.

Date and Time
Tuesday, November 18, 2003 at 14:30
Aula Seminari,
Dipartimento di Matematica, Università di Parma, Via D'Azeglio 85/A, I-43100 Parma

Inner and Outer Approximations of Polytopes Using Boxes

The talk deals with the problem of approximating a convex polytope in any finite dimension by a collection of (hyper)boxes. More exactly, given a polytope P by a system of linear inequalities, we look for two collections I and E of boxes with non-overlapping interiors such that the union of all boxes in I is contained in P and the union of all boxes in E contains P. We propose and test several techniques to construct I and E aimed at getting a good balance between two contrasting objectives: minimize the volume error and minimize the total number of generated boxes. We suggest how to modify the proposed techniques in order to approximate the projection of P onto a given subspace without computing the projection explicitly. The effectiveness of the approach is shown in the context of verification of hybrid and embedded systems, where the aim is to check if an embedded controller satisfies certain specifications. We sketch a methodology for computing an over (under) approximation of the set of states that a discrete-time affine hybrid system can reach by starting from a given set of initial conditions and under the effect of exogenous inputs to the system, such as disturbances, within a prescribed range.


Links to Related Publications

Contact Person
Roberto Bagnara

[Page last updated on November 22, 2003, 10:38:50.]

Page maintained by
Enea Zaffanella

Home | People | Projects | Publications | Seminars | Software | Links