|
CS Seminar: Fabio Torrisi, November 18, 2003
- Speaker
-
Fabio Torrisi,
Automatic Control Laboratory,
Swiss Federal Institute of Technology,
Zurich, Switzerland.
- Date and Time
-
Tuesday, November 18, 2003 at 14:30
- Place
-
Aula Seminari,
Dipartimento di Matematica,
Università di Parma,
Via D'Azeglio 85/A,
I-43100 Parma
- Title
-
Inner and Outer Approximations of Polytopes Using Boxes
- Abstract
-
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.
- Slides
- Links to Related Publications
- Contact Person
-
Roberto Bagnara
[Page last updated on November 22, 2003, 10:38:50.]
|