Abstract
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 cases.

The above reachability algorithm has been implemented in a tool called SPeeDI.

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 controllability kernels.

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.

ASTEC seminar
September 3, 2002

Place: Information technology, Uppsala University
Room: 1113
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.