*banner
 

Reachability of Hybrid Systems in Space-Time
Goran Frehse

Citation
Goran Frehse. "Reachability of Hybrid Systems in Space-Time". Talk or presentation, 7, May, 2013.

Abstract
Computing the reachable states of a hybrid system is hard, in part because efficient algorithms are available mainly for convex sets, while the states reachable by time elapse, so-called flowpipes, are generally nonconvex. When the dynamics are piecewise affine, the nonconvexity takes a particular form: when drawn along a time axis, the flowpipe is convex at any point in time. We exploit this property to lift efficient approximation techniques from convex sets to flowpipes. The approximation consists of a set of piecewise linear scalar functions over continuous time, which define at each time point a polyhedral inner- and outer approximation. Reachability operations that are difficult to carry out on nonconvex sets correspond to simple operations on these scalar functions. The resulting reachability algorithm is precise, scalable, and provides good error measurements. We present an implementation in the SpaceEx verification platform and showcase the performance on several examples.

Electronic downloads

Citation formats  
  • HTML
    Goran Frehse. <a
    href="http://chess.eecs.berkeley.edu/pubs/991.html"
    ><i>Reachability of Hybrid Systems in
    Space-Time</i></a>, Talk or presentation,  7,
    May, 2013.
  • Plain text
    Goran Frehse. "Reachability of Hybrid Systems in
    Space-Time". Talk or presentation,  7, May, 2013.
  • BibTeX
    @presentation{Frehse13_ReachabilityOfHybridSystemsInSpaceTime,
        author = {Goran Frehse},
        title = {Reachability of Hybrid Systems in Space-Time},
        day = {7},
        month = {May},
        year = {2013},
        abstract = {Computing the reachable states of a hybrid system
                  is hard, in part because efficient algorithms are
                  available mainly for convex sets, while the states
                  reachable by time elapse, so-called flowpipes, are
                  generally nonconvex. When the dynamics are
                  piecewise affine, the nonconvexity takes a
                  particular form: when drawn along a time axis, the
                  flowpipe is convex at any point in time. We
                  exploit this property to lift efficient
                  approximation techniques from convex sets to
                  flowpipes. The approximation consists of a set of
                  piecewise linear scalar functions over continuous
                  time, which define at each time point a polyhedral
                  inner- and outer approximation. Reachability
                  operations that are difficult to carry out on
                  nonconvex sets correspond to simple operations on
                  these scalar functions. The resulting reachability
                  algorithm is precise, scalable, and provides good
                  error measurements. We present an implementation
                  in the SpaceEx verification platform and showcase
                  the performance on several examples.},
        URL = {http://chess.eecs.berkeley.edu/pubs/991.html}
    }
    

Posted by David Broman on 27 May 2013.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess