15
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Exact and Efficient Hamilton-Jacobi Reachability for Decoupled Systems

      Preprint
      ,

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Reachability analysis is important for studying optimal control problems and differential games, which are powerful theoretical tools for analyzing and modeling many practical problems in robotics, aircraft control, among other application areas. In reachability analysis, one is interested in computing the reachable set, defined as the set of states from which there exists a control, despite the worst disturbance, that can drive the system into a set of target states. The target states can be used to model either unsafe or desirable configurations, depending on the application. Many Hamilton-Jacobi formulations allow the computation of reachable sets; however, due to the exponential complexity scaling in computation time and space, problems involving approximately 5 dimensions become intractable. A number of methods that compute an approximate solution exist in the literature, but these methods trade off complexity for optimality. In this paper, we eliminate complexity-optimality trade-offs for time-invariant decoupled systems using a decoupled Hamilton-Jacobi formulation that enables the exact reconstruction of high dimensional solutions via low dimensional solutions of the decoupled subsystems. Our formulation is compatible with existing numerical tools, and we show the accuracy, computation benefits, and an application of our novel approach using two numerical examples.

          Related collections

          Most cited references13

          • Record: found
          • Abstract: found
          • Article: not found

          A fast marching level set method for monotonically advancing fronts.

          A fast marching level set method is presented for monotonically advancing fronts, which leads to an extremely fast scheme for solving the Eikonal equation. Level set methods are numerical techniques for computing the position of propagating fronts. They rely on an initial value partial differential equation for a propagating level set function and use techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. This paper describes a particular case of such methods for interfaces whose speed depends only on local position. The technique works by coupling work on entropy conditions for interface motion, the theory of viscosity solutions for Hamilton-Jacobi equations, and fast adaptive narrow band level set methods. The technique is applicable to a variety of problems, including shape-from-shading problems, lithographic development calculations in microchip manufacturing, and arrival time problems in control theory.
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              High-Order Essentially Nonoscillatory Schemes for Hamilton–Jacobi Equations

                Bookmark

                Author and article information

                Journal
                2015-03-19
                2016-03-20
                Article
                1503.05933
                6ad3a442-cd3d-4b9b-a7f0-8189a63ae11b

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                54th IEEE Conference on Decision and Control
                math.OC

                Numerical methods
                Numerical methods

                Comments

                Comment on this article