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">Analog computer</span> Computer that uses continuously varying data technology

An analog computer or analogue computer is a type of computer that uses the continuous variation aspect of physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved. In contrast, digital computers represent varying quantities symbolically and by discrete values of both time and amplitude.

<span class="mw-page-title-main">Differential geometry</span> Branch of mathematics dealing with functions and geometric structures on differentiable manifolds

Differential geometry is a mathematical discipline that studies the geometry of smooth shapes and smooth spaces, otherwise known as smooth manifolds. It uses the techniques of differential calculus, integral calculus, linear algebra and multilinear algebra. The field has its origins in the study of spherical geometry as far back as antiquity. It also relates to astronomy, the geodesy of the Earth, and later the study of hyperbolic geometry by Lobachevsky. The simplest examples of smooth spaces are the plane and space curves and surfaces in the three-dimensional Euclidean space, and the study of these shapes formed the basis for development of modern differential geometry during the 18th and 19th centuries.

<span class="mw-page-title-main">Dynamical system</span> Mathematical model of the time dependence of a point in space

In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space, such as in a parametric curve. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, the random motion of particles in the air, and the number of fish each springtime in a lake. The most general definition unifies several concepts in mathematics such as ordinary differential equations and ergodic theory by allowing different choices of the space and how time is measured. Time can be measured by integers, by real or complex numbers or can be a more general algebraic object, losing the memory of its physical origin, and the space may be a manifold or simply a set, without the need of a smooth space-time structure defined on it.

In engineering, a transfer function of a system, sub-system, or component is a mathematical function that models the system's output for each possible input. They are widely used in electronic engineering tools like circuit simulators and control systems. In some simple cases, this function can be represented as two-dimensional graph of an independent scalar input versus the dependent scalar output, called a transfer curve or characteristic curve. Transfer functions for components are used to design and analyze systems assembled from components, particularly using the block diagram technique, in electronics and control theory.

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

<span class="mw-page-title-main">Green's function</span> Impulse response of an inhomogeneous linear differential operator

In mathematics, a Green's function is the impulse response of an inhomogeneous linear differential operator defined on a domain with specified initial conditions or boundary conditions.

In control engineering, model based fault detection and system identification a state-space representation is a mathematical model of a physical system specified as a set of input, output and variables related by first-order differential equations or difference equations. Such variables, called state variables, evolve over time in a way that depends on the values they have at any given instant and on the externally imposed values of input variables. Output variables’ values depend on the values of the state variables.

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.

<span class="mw-page-title-main">Linear time-invariant system</span> Mathematical model which is both linear and time-invariant

In system analysis, among other fields of study, a linear time-invariant (LTI) system is a system that produces an output signal from any input signal subject to the constraints of linearity and time-invariance; these terms are briefly defined below. These properties apply (exactly or approximately) to many important physical systems, in which case the response y(t) of the system to an arbitrary input x(t) can be found directly using convolution: y(t) = (xh)(t) where h(t) is called the system's impulse response and ∗ represents convolution (not to be confused with multiplication). What's more, there are systematic methods for solving any such system (determining h(t)), whereas systems not meeting both properties are generally more difficult (or impossible) to solve analytically. A good example of an LTI system is any electrical circuit consisting of resistors, capacitors, inductors and linear amplifiers.

Nonlinear control theory is the area of control theory which deals with systems that are nonlinear, time-variant, or both. Control theory is an interdisciplinary branch of engineering and mathematics that is concerned with the behavior of dynamical systems with inputs, and how to modify the output by changes in the input using feedback, feedforward, or signal filtering. The system to be controlled is called the "plant". One way to make the output of a system follow a desired reference signal is to compare the output of the plant to the desired output, and provide feedback to the plant to modify the output to bring it closer to the desired output.

In control theory, a distributed-parameter system is a system whose state space is infinite-dimensional. Such systems are therefore also known as infinite-dimensional systems. Typical examples are systems described by partial differential equations or by delay differential equations.

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.

In control theory, the linear–quadratic–Gaussian (LQG) control problem is one of the most fundamental optimal control problems, and it can also be operated repeatedly for model predictive control. It concerns linear systems driven by additive white Gaussian noise. The problem is to determine an output feedback law that is optimal in the sense of minimizing the expected value of a quadratic cost criterion. Output measurements are assumed to be corrupted by Gaussian noise and the initial state, likewise, is assumed to be a Gaussian random vector.

In systems theory, closed-loop poles are the positions of the poles of a closed-loop transfer function in the s-plane. The open-loop transfer function is equal to the product of all transfer function blocks in the forward path in the block diagram. The closed-loop transfer function is obtained by dividing the open-loop transfer function by the sum of one and the product of all transfer function blocks throughout the negative feedback loop. The closed-loop transfer function may also be obtained by algebraic or block diagram manipulation. Once the closed-loop transfer function is obtained for the system, the closed-loop poles are obtained by solving the characteristic equation. The characteristic equation is nothing more than setting the denominator of the closed-loop transfer function to zero.

<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 which may be with respect to more than one independent variable.

The rebound attack is a tool in the cryptanalysis of cryptographic hash functions. The attack was first published in 2009 by Florian Mendel, Christian Rechberger, Martin Schläffer and Søren Thomsen. It was conceived to attack AES like functions such as Whirlpool and Grøstl, but was later shown to also be applicable to other designs such as Keccak, JH and Skein.

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.

Classical control theory is a branch of control theory that deals with the behavior of dynamical systems with inputs, and how their behavior is modified by feedback, using the Laplace transform as a basic tool to model such systems.

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.

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)
  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. doi: 10.1109/TAC.2016.2638961 . ISSN   1558-2523.