On the Completeness and Ordering of Path-Complete Barrier Functions

Mahathi Anand 1, Raphaël Jungers 2, Majid Zamani 3, Frank Allgöwer 4 · 2025

Read On the Completeness and Ordering of Path-Complete Barrier Functions by Mahathi Anand 1, Raphaël Jungers 2, Majid Zamani 3, Frank Allgöwer 4 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19561.txt.

Introduction

Mahathi Anand, Raphaël Jungers, Majid Zamani, and Frank Allgöwer present a 2025 paper on certifying safety for systems that switch between modes. Path-complete barrier functions pair algebraic safety witnesses with a graph describing allowed switching sequences. The graph half gives designers freedom, but its exact role was not fully pinned down.

The authors prove that path-completeness of the graph is necessary: without it, the safety conditions can fail to be valid. So the framework captures safety conditions completely, nothing is lost. They also give a systematic way to compare two such graphs. When one graph can simulate another, its safety conditions are always less conservative. The comparison holds regardless of the system's algebra or the witness template chosen.

Catalog record

CREATORMahathi Anand 1, Raphaël Jungers 2, Majid Zamani 3, Frank Allgöwer 4
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19561

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Completeness and Ordering of Path-Complete Barrier Functions Mahathi Anand 1, Raphaël Jungers 2, Majid Zamani 3, Frank Allgöwer 4 Abstract . This paper is concerned with path-complete barrier functions which offer a graph-based methodology for verifying safety properties in switched systems. The path-complete framework leverages algebraic (barrier functions) as well as combinatorial (graph) components to characterize a set of safety conditions for switched systems, thus offering high flexibility (two degrees of freedom) in searching for suitable safety certificates. In this paper, we do not propose any new safety criteria. Instead, we further investigate the role that the combinatorial component plays in the safety verification problem. First, we prove that path-completeness , which is a property on a graph that describes the switching sequences, is necessary to obtain a set of valid safety conditions. As a result, the path-complete framework is able to provide a complete characterization of safety conditions for switched systems. Furthermore, we provide a systematic methodology for comparing two path-complete graphs and the conservatism associated with the resulting safety conditions. Specifically, we prove that under some conditions, such as when there exists a simulation relation between two path-complete graphs, it is possible to conclude that one graph is always able to provide less conservative safety conditions than another, independent of the algebraic properties of the switched system and the template of the barrier function under consideration. Such a result paves the way for a systematic use of the path-complete framework with barrier functions, as one can then consistently choose the appropriate graph that provides less conservative safety conditions. 1. Introduction Traditionally, control theorists have focused on studying systems with purely continuous or discrete behaviors. However, many physical systems behave in a hybrid manner. Examples include chemical processes and energy systems [ 1 ] , robotics [ 2 ] , biological systems [ 3 ] , and air traffic management systems [ 4 ] . On the other hand, switched systems [ 5 ] exhibit continuous-time behavior with isolated discrete switching modes and can be used as abstractions for more complex hybrid systems. However, their analysis is still a challenging problem [ 6 , 7 ] that requires careful consideration. An important problem concerning switched systems is the analysis of safety properties. The safety verification problem entails ascertaining whether all the behaviors of the switched system avoid visiting some unsafe or undesirable configurations. One way to solve this problem is to construct simpler finite abstractions and analyze the abstract systems, e.g., in [ 8 , 9 , 10 ] , however, they suffer severely from the curse of dimensionality. More recently, discretization-free methods using barrier functions [ 11 , 12 ] have shown great promises in proving safety properties effectively and efficiently. They are real-valued functions that assign higher values to the unsafe states than the initial states, thus serving as a barrier between reachable and unsafe regions. Hence, the safety verification problem is reduced to finding suitable barrier functions. Related Literature. Several results in the literature utilize barrier functions in the context of switched and hybrid systems [ 11 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 ] . The existing approaches can be divided in two groups. The first one is the use of common barrier functions [ 14 , 13 ] , where a single barrier function is used to guarantee safety for all the discrete operating modes of the switched system. Unfortunately, the conditions imposed on the barrier function are quite restrictive, and one may not be able to find suitable common barrier functions even when the system is safe. To alleviate the conservatism, multiple barrier functions were proposed in [ 11 , 15 , 16 , 17 ] . Here, a barrier function is assigned to each operating mode of the switched (hybrid) system, and safety guarantees are obtained by ensuring not only mode safety but also safety at switching instances. More recently, inspired by path-complete Lyapunov functions for stability analysis [ 22 , 23 , 24 , 25 , 26 , 27 ] , we introduced in [ 28 ] a new framework for the safety of linear switched systems under arbitrary switching, based on a notion of path-complete barrier functions . This approach extends and generalizes the common and multiple barrier functions framework by introducing a combinatorial component to the safety verification problem via a graph. In particular, a so-called path-complete graph is used to encode the arbitrary switching sequences occurring in the system. Then, path-complete barrier functions are defined as a collection of functions so that each node of the graph is assigned a distinct barrier function. The edges within the graph enable algebraic conditions imposed on the barrier functions, such that the structure of the graph, together with the algebraic conditions, provide sufficient conditions for safety. It was also shown in [ 28 ] that depending on the choice of path-complete graphs, the approach provides less conservative results compared to the existing common and multiple barrier function framework. However, some unresolved questions regarding the path-complete framework remain. In this paper, we investigate in detail the special role that the choice of graphs plays in solving the safety verification problem. In this context, we address important questions concerning the completeness and ordering of path-complete barrier functions. Contributions. The contributions of this paper in comparison to [ 28 ] are three-fold. First, while [ 28 ] focused primarily on linear switched systems, we remove in this paper any such restrictions and provide results for general nonlinear systems. Second, we provide completeness arguments for the path-complete framework proposed in [ 28 ] . It is known that path-complete barrier functions only provide sufficient conditions for safety. In other words, given a system and a suitable path-complete graph, failure to find a barrier function does not mean that the system is unsafe. However, it is not yet clear whether the chosen graph is required to be path-complete to begin with. Therefore, in this paper, we ask whether path-completeness is necessary for proving safety properties, and answer this question affirmatively by constructing appropriate counterexamples, i.e., by constructing suitable unsafe systems where the lack of the path-completeness property in graphs may lead to invalid safety certificates. This enables us to prove that the path-complete framework encapsulates the complete set of graph-based conditions for the safety verification of switched systems. Thirdly, we investigate how the choice of graphs can influence the conservatism of the resulting safety conditions. In general, for a given system, the choice of a path-complete graph over which safety conditions are defined is not unique. As a result, different path-complete graphs lead to different algebraic conditions for safety verification, and the conservatism of the resulting conditions may differ. In this paper, we leverage techniques from graph theory to compare two path-complete graphs in terms of the conservatism of the resulting safety conditions. In particular, we define some simulation relations on the graphs under which one can order two path-complete graphs according to their conservatism, independently of the system or the barrier function template under consideration. Then, for any two path-complete graphs with some simulation relation, it is possible to objectively conclude in

Read the complete text