Title: Fast Verification of Control Barrier Functions via Linear Programming Show Chinese title

Title: 通过线性规划快速验证控制屏障函数

Abstract: Control barrier functions are a popular method of ensuring system safety, and these functions can be used to enforce invariance of a set under the dynamics of a system. A control barrier function must have certain properties, and one must both formulate a candidate control barrier function and verify that it does indeed satisfy the required properties. Targeting the latter problem, this paper presents a method of verifying any finite number of candidate control barrier functions with linear programming. We first apply techniques from real algebraic geometry to formulate verification problem statements that are solvable numerically. Typically, semidefinite programming is used to verify candidate control barrier functions, but this does not always scale well. Therefore, we next apply a method of inner-approximating the set of sums of squares polynomials that significantly reduces the computational complexity of these verification problems by transcribing them to linear programs. We give explicit forms for the resulting linear programs, and simulation results for a satellite inspection problem show that the computation time needed for verification can be reduced by more than 95%. Show Chinese abstract

Abstract: 控制 Barrier 函数是一种确保系统安全的流行方法，这些函数可用于强制保证某一集合在系统动态下的不变性。 一个控制 Barrier 函数必须具备某些特性，并且需要同时提出候选控制 Barrier 函数并验证它确实满足所需的特性。 针对后一个问题，本文提出了一种利用线性规划验证任意有限数量候选控制 Barrier 函数的方法。 我们首先应用实代数几何技术来制定可数值求解的验证问题陈述。 通常情况下，半定规划被用于验证候选控制 Barrier 函数，但这种方法并不总是具有良好扩展性。 因此，我们接下来应用一种内逼近和平方和多项式集合的方法，通过将其转录为线性规划显著降低了这些验证问题的计算复杂度。 我们给出了由此产生的线性规划的显式形式，卫星检查问题的仿真结果表明，验证所需的计算时间可以减少 95% 以上。