Barrier certificate

Last updated

A barrier certificate [1] or barrier function is used to prove that a given region is forward invariant for a given ordinary differential equation or hybrid dynamical system. [2] That is, a barrier function can be used to show that if a solution starts in a given set, then it cannot leave that set.

Contents

Showing that a set is forward invariant is an aspect of safety, which is the property where a system is guaranteed to avoid obstacles specified as an unsafe set.

Barrier certificates play the analogical role for safety to the role of Lyapunov functions for stability. For every ordinary differential equation that robustly fulfills a safety property of a certain type there is a corresponding barrier certificate. [3]

History

The first result in the field of barrier certificates was the Nagumo theorem by Mitio Nagumo in 1942. [4] [5] The term "barrier certificate" was introduced later based on similar concept in convex optimization called barrier functions. [4]

Barrier certificates were generalized to hybrid systems in 2004 by Stephen Prajna and Ali Jadbabaie. [6]

Variants

There are several different types of barrier functions. One distinguishing factor is the behavior of the barrier function at the boundary of the forward invariant set . A barrier function that goes to zero as the input approaches the boundary of is called a zeroing barrier function. [7] A barrier function that goes to infinity as the inputs approach the boundary of are called reciprocal barrier functions. [7] Here, "reciprocal" refers to the fact that a reciprocal barrier functions can be defined as the multiplicative inverse of a zeroing barrier function.

Related Research Articles

<span class="mw-page-title-main">Partial differential equation</span> Type of differential equation

In mathematics, a partial differential equation (PDE) is an equation which computes a function between various partial derivatives of a multivariable function.

In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many other scientists since most systems are inherently nonlinear in nature. Nonlinear dynamical systems, describing changes in variables over time, may appear chaotic, unpredictable, or counterintuitive, contrasting with much simpler linear systems.

In mathematics, a linear differential equation is a differential equation that is defined by a linear polynomial in the unknown function and its derivatives, that is an equation of the form

In gauge theory and mathematical physics, a topological quantum field theory is a quantum field theory which computes topological invariants.

A hybrid system is a dynamical system that exhibits both continuous and discrete dynamic behavior – a system that can both flow and jump. Often, the term "hybrid dynamical system" is used, to distinguish over hybrid systems such as those that combine neural nets and fuzzy logic, or electrical and mechanical drivelines. A hybrid system has the benefit of encompassing a larger class of systems within its structure, allowing for more flexibility in modeling dynamic phenomena.

<span class="mw-page-title-main">Bellman equation</span> Necessary condition for optimality associated with dynamic programming

A Bellman equation, named after Richard E. Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. It writes the "value" of a decision problem at a certain point in time in terms of the payoff from some initial choices and the "value" of the remaining decision problem that results from those initial choices. This breaks a dynamic optimization problem into a sequence of simpler subproblems, as Bellman's “principle of optimality" prescribes. The equation applies to algebraic structures with a total ordering; for algebraic structures with a partial ordering, the generic Bellman's equation can be used.

In mathematics, the Picard–Fuchs equation, named after Émile Picard and Lazarus Fuchs, is a linear ordinary differential equation whose solutions describe the periods of elliptic curves.

In the mathematics of evolving systems, the concept of a center manifold was originally developed to determine stability of degenerate equilibria. Subsequently, the concept of center manifolds was realised to be fundamental to mathematical modelling.

<span class="mw-page-title-main">Schramm–Loewner evolution</span>

In probability theory, the Schramm–Loewner evolution with parameter κ, also known as stochastic Loewner evolution (SLEκ), is a family of random planar curves that have been proven to be the scaling limit of a variety of two-dimensional lattice models in statistical mechanics. Given a parameter κ and a domain in the complex plane U, it gives a family of random curves in U, with κ controlling how much the curve turns. There are two main variants of SLE, chordal SLE which gives a family of random curves from two fixed boundary points, and radial SLE, which gives a family of random curves from a fixed boundary point to a fixed interior point. These curves are defined to satisfy conformal invariance and a domain Markov property.

In mathematics, in the study of dynamical systems, the Hartman–Grobman theorem or linearisation theorem is a theorem about the local behaviour of dynamical systems in the neighbourhood of a hyperbolic equilibrium point. It asserts that linearisation—a natural simplification of the system—is effective in predicting qualitative patterns of behaviour. The theorem owes its name to Philip Hartman and David M. Grobman.

<span class="mw-page-title-main">Set-valued function</span> Function whose values are sets (mathematics)

A set-valued function is a mathematical function that maps elements from one set, the domain of the function, to subsets of another set. Set-valued functions are used in a variety of mathematical fields, including optimization, control theory and game theory.

In mathematics, the multiplicity of a member of a multiset is the number of times it appears in the multiset. For example, the number of times a given polynomial has a root at a given point is the multiplicity of that root.

<span class="mw-page-title-main">Scallop theorem</span>

In physics, the scallop theorem states that a swimmer that performs a reciprocal motion cannot achieve net displacement in a low-Reynolds number Newtonian fluid environment, i.e. a fluid that is highly viscous. Such a swimmer deforms its body into a particular shape through a sequence of motions and then reverts to the original shape by going through the sequence in reverse. At low Reynolds number, time or inertia does not come into play, and the swimming motion is purely determined by the sequence of shapes that the swimmer assumes.

<span class="mw-page-title-main">Ordinary differential equation</span> Differential equation containing derivatives with respect to only one variable

In mathematics, an ordinary differential equation (ODE) is a differential equation (DE) dependent on only a single independent variable. As with other DE, its unknown(s) consists of one function(s) and involves the derivatives of those functions. The term "ordinary" is used in contrast with partial differential equations (PDEs) which may be with respect to more than one independent variable, and, less commonly, in contrast with stochastic differential equations (SDEs) where the progression is random.

In mathematics, the Bony–Brezis theorem, due to the French mathematicians Jean-Michel Bony and Haïm Brezis, gives necessary and sufficient conditions for a closed subset of a manifold to be invariant under the flow defined by a vector field, namely at each point of the closed set the vector field must have non-positive inner product with any exterior normal vector to the set. A vector is an exterior normal at a point of the closed set if there is a real-valued continuously differentiable function maximized locally at the point with that vector as its derivative at the point. If the closed subset is a smooth submanifold with boundary, the condition states that the vector field should not point outside the subset at boundary points. The generalization to non-smooth subsets is important in the theory of partial differential equations.

<span class="mw-page-title-main">Alexander Varchenko</span>

Alexander Nikolaevich Varchenko is a Soviet and Russian mathematician working in geometry, topology, combinatorics and mathematical physics.

Mitio (Michio) Nagumo was a Japanese mathematician, who specialized in the theory of differential equations. He gave the first necessary and sufficient condition for positive invariance of closed sets under the flow induced by ordinary differential equations.

In theoretical physics, the curvature renormalization group (CRG) method is an analytical approach to determine the phase boundaries and the critical behavior of topological systems. Topological phases are phases of matter that appear in certain quantum mechanical systems at zero temperature because of a robust degeneracy in the ground-state wave function. They are called topological because they can be described by different (discrete) values of a nonlocal topological invariant. This is to contrast with non-topological phases of matter that can be described by different values of a local order parameter. States with different values of the topological invariant cannot change into each other without a phase transition. The topological invariant is constructed from a curvature function that can be calculated from the bulk Hamiltonian of the system. At the phase transition, the curvature function diverges, and the topological invariant correspondingly jumps abruptly from one value to another. The CRG method works by detecting the divergence in the curvature function, and thus determining the boundaries between different topological phases. Furthermore, from the divergence of the curvature function, it extracts scaling laws that describe the critical behavior, i.e. how different quantities behave as the topological phase transition is approached. The CRG method has been successfully applied to a variety of static, periodically driven, weakly and strongly interacting systems to classify the nature of the corresponding topological phase transitions.

<span class="mw-page-title-main">Physics-informed neural networks</span> Technique to solve partial differential equations

Physics-informed neural networks (PINNs), also referred to as Theory-Trained Neural Networks (TTNs), are a type of universal function approximators that can embed the knowledge of any physical laws that govern a given data-set in the learning process, and can be described by partial differential equations (PDEs).They overcome the low data availability of some biological and engineering systems that makes most state-of-the-art machine learning techniques lack robustness, rendering them ineffective in these scenarios. The prior knowledge of general physical laws acts in the training of neural networks (NNs) as a regularization agent that limits the space of admissible solutions, increasing the correctness of the function approximation. This way, embedding this prior information into a neural network results in enhancing the information content of the available data, facilitating the learning algorithm to capture the right solution and to generalize well even with a low amount of training examples.

Conley's fundamental theorem of dynamical systems or Conley's decomposition theorem states that every flow of a dynamical system with compact phase portrait admits a decomposition into a chain-recurrent part and a gradient-like flow part. Due to the concise yet complete description of many dynamical systems, Conley's theorem is also known as the fundamental theorem of dynamical systems. Conley's fundamental theorem has been extended to systems with non-compact phase portraits and also to hybrid dynamical systems.

References

  1. Prajna, Stephen, and Ali Jadbabaie. "Safety verification of hybrid systems using barrier certificates." International Workshop on Hybrid Systems: Computation and Control. Springer, Berlin, Heidelberg, 2004.
  2. Maghenem, M., Sanfelice, R. G. (February 2021). "Sufficient conditions for forward invariance and contractivity in hybrid inclusions using barrier functions". Automatica. 124: 109328. arXiv: 1908.03980 . doi:10.1016/j.automatica.2020.109328. ISSN   0005-1098.
  3. Stefan Ratschan: "Converse Theorems for Safety and Barrier Certificates". IEEE Trans. on Automatic Control, Volume 63, Issue 8, 2018
  4. 1 2 Ames, A. D., Coogan, S., Egerstedt, M., Notomista, G., Sreenath, K., Tabuada, P. (2019), Control Barrier Functions: Theory and Applications
  5. Nagumo, Mitio (1942), "Über die lage der integralkurven gewöhnlicher differentialgleichungen", Nippon Sugaku-Buturigakkwai Kizi Dai 3 Ki, 24: 551–559(in German). English translation in Marcel, Menner; Eugene, Lavretsky. "Translation of Nagumo's Foundational Work on Barrier Functions: On the Location of Integral Curves of Ordinary Differential Equations". arXiv: 2406.18614 .
  6. Prajna, S., Jadbabaie, A. (2004), Alur, R., Pappas, G. J. (eds.), Safety Verification of Hybrid Systems Using Barrier Certificates, Springer
  7. 1 2 Ames, A. D., Xu, X., Grizzle, J. W., Tabuada, P. (August 2017). "Control Barrier Function Based Quadratic Programs for Safety Critical Systems". IEEE Transactions on Automatic Control. 62 (8): 3861–3876. arXiv: 1609.06408 . doi: 10.1109/TAC.2016.2638961 . ISSN   1558-2523.