Formal Synthesis of Barrier Certificates Using Fourier Kolmogorov-Arnold Network

Xiongqi Zhang, Junwei Xu, Yang Wang, Dongming Xiang, Wang Lin, Zuohua DingAAAI 2025 · DOI

Abstract

Ensuring safety in cyber-physical systems (CPS) requires formal proofs that a system will never enter an unsafe state. This paper introduces KAN4BC, a framework that synthesizes barrier certificates using Fourier Kolmogorov-Arnold Networks (KANs). By utilizing learnable Fourier series on network edges, KAN4BC achieves higher expressiveness and smoother representations than traditional feed-forward neural networks (FNNs). Experimental results across seven benchmarks demonstrate that KAN4BC consistently outperforms existing tools like FOSSIL2.0 in both success rate and computational efficiency.

Introduction

In safety-critical applications such as autonomous driving or robotics, systems must be guaranteed to remain within a safe operating region. Barrier certificates serve as mathematical "fences" that separate safe states from unsafe ones. Traditionally, these certificates are synthesized using Sum-of-Squares (SOS) programming or FNNs. However, SOS programming scales poorly with system dimensionality, and FNNs with fixed activation functions (e.g., ReLU) often struggle to represent the complex, nonlinear boundaries required for non-polynomial systems.

Methodology

The KAN4BC framework addresses these limitations through a novel architecture and a robust verification loop.

Fourier Kolmogorov-Arnold Networks (KANs)

The core innovation is the use of Fourier KANs. Unlike standard neural networks that apply fixed activation functions at nodes, KANs place learnable functions on the edges connecting nodes. In this work, these functions are represented as Fourier series (sums of sines and cosines).

Architecture of the Fourier Kolmogorov-Arnold Network (KAN) with learnable Fourier curves on edges.

This choice is strategic: Fourier series are infinitely differentiable, making them ideal for calculating the Lie derivatives required for barrier certificate conditions. Furthermore, they provide explicit mathematical expressions that facilitate formal verification.

Learner-Verifier Loop

The synthesis process follows a two-stage iterative loop:

  1. Learner: Trains the Fourier KAN to satisfy barrier conditions—ensuring the function is negative in the safe set, positive in the unsafe set, and non-increasing along system trajectories.
  2. Verifier: Formally checks the candidate certificate. KAN4BC employs a hybrid approach combining SMT solvers (dReal) to find counterexamples and the Lipschitz method to provide deterministic proofs of validity.

Experimental Evaluation

The authors evaluated KAN4BC on seven benchmarks ($barr_1$ to $barr_7$) representing a variety of challenges:

  • Low-dimensional systems: Variants of the Van der Pol oscillator.
  • Non-polynomial dynamics: Systems involving trigonometric or exponential terms.
  • Robotics: A 3D model of a plane's angular velocity control ($barr_4$).
  • High-dimensional systems: A 4D model ($barr_7$).

Results and Discussion

KAN4BC demonstrated superior performance compared to FOSSIL2.0, a state-of-the-art tool utilizing standard FNNs.

Performance comparison between KAN4BC and FOSSIL2.0 across seven benchmarks.

Key findings include:

  • Universal Success: KAN4BC successfully found valid certificates for all seven benchmarks, whereas FOSSIL2.0 failed on several cases, such as $barr_3$.
  • Efficiency: KAN4BC was significantly faster in most instances. For $barr_1$, it converged in 5.14 seconds, nearly twice as fast as FOSSIL2.0's best configuration (10.50s).
  • Convergence: The learnable nature of Fourier KANs allowed for faster convergence with fewer iterations, indicating a more natural fit for safety boundary representation.

Conclusion

KAN4BC represents a significant advancement in the formal synthesis of barrier certificates. By leveraging the smoothness and expressiveness of Fourier KANs, the framework provides a more efficient and reliable path to safety verification for complex dynamical systems. Future work will focus on scaling the Lipschitz verification method and extending the framework to handle hybrid systems with discrete mode transitions.

Summary updated

BibTeX
@inproceedings{zhang2025formal,
  author = {Xiongqi Zhang and Junwei Xu and Yang Wang and Dongming Xiang and Wang Lin and Zuohua Ding},
  title = {{Formal Synthesis of Barrier Certificates Using Fourier Kolmogorov-Arnold Network}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i1.32101},
}
Figure