Algorithmic Analysis of Polygonal Hybrid Systems
Gerardo will join informationtechnology
this autumn for one year as a post-doc.
A polygonal differential inclusion system (SPDI) is a non-deterministic
planar hybrid system which can be represented by piecewise constant
differential inclusions. In this work we are concerned with several
theoretical and practical questions related to SPDIs such as
reachability analysis and phase portrait construction.
First we show that the reachability question for SPDIs is indeed
decidable. Our procedure is not based on the computation of the reach-
set but rather on the computation of the limit of individual
trajectories. A key idea is the use of edge-to-edge one-dimensional
affine Poincaré maps, the fix-points of which are easily computed. By
taking advantage of this information, cycles can be accelerated in most
The above reachability algorithm has been implemented in a tool called
We next build the phase portrait of such systems. In particular, we
identify the viability kernels of simple cycles. Such kernels are the
set of starting points of trajectories that can keep rotating in the
cycles forever. We also introduce the notion of controllability kernel
of simple cycles as the set of points such that any two points of the
set are reachable from each other via trajectories that remain on the
set. We give non-iterative algorithms to compute both kernels. We
obtain the SPDI phase portrait computing all the viability and
We finally study the decidability of the reachability problem for other
2-dimensional hybrid systems. We introduce hierarchical piecewise
constant derivative systems (HPCDs) and 2-dimensional manifolds with
piecewise constant derivative systems. We show that the reachability
problem for the above two classes of systems is as hard as the
reachability problem for piecewise affine maps that is known to be an
open problem. We also show that the reachability question for slight
extensions of HPCDs are undecidable.
Place: Information technology, Uppsala University
Time: 15.15-16.00 (+ discussions)
Room 1113 is in building 1, floor 1, room 13
(in the southern part of the building).
Help on how to find ASTEC Seminars.
There will be an extended period for discussions after the seminar.
Speakers are encouraged to give an short (5 min) introduction to the subject at the begining of the talk.
Listeners are excused if they have to leave after 16.00.
Everyone is welcome !
Updated 29-Aug-2002 09:19 by Roland Grönroos
e-mail: info -at- astec.uu.se