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

• dreams-frehse-may-2013.pdf · application/pdf · 4123 kbytes

• 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.