Verifying Switched System Stability With Logic

Yong Kiam Tan, Stefan Mitsch, André Platzer

TL;DR

Switched systems—like a car shifting gears or a thermostat clicking on and off—can exhibit dangerous instability even if their individual operating modes are perfectly stable. This paper introduces a mathematically rigorous approach to prove the stability of these systems by treating them as looping computer programs and using differential dynamic logic (dL) to verify them, ensuring absolute mathematical soundness free from numerical errors.

What Problem Does This Paper Address?

In control theory, "switched systems" are a class of hybrid systems that jump between different continuous physical behaviors based on discrete control logic (e.g., an automatic cruise controller switching between "accelerate," "coast," and "brake" modes). A notorious quirk of these systems is that switching between two perfectly stable modes can inadvertently create a highly unstable system.

Engineers typically prove stability using Lyapunov functions—mathematical "energy" functions that strictly decrease over time, proving the system eventually settles at a safe equilibrium. While there are automated tools to find these functions, they often rely on floating-point numerical solvers. These solvers can suffer from subtle rounding errors, sometimes outputting a mathematically flawed Lyapunov function and falsely declaring a dangerous system "stable." This paper tackles the need for a trustworthy, computer-checked verification method that guarantees stability without falling victim to numerical approximations.

Methods

The authors bridge the gap between continuous control theory and discrete software verification using Differential Dynamic Logic (dL).

  1. Switched Systems as Looping Programs: Instead of traditional differential equations, the authors model switched systems as looping hybrid programs. The loop body contains both the discrete switching logic (e.g., if speed > 70, switch to brake) and the continuous physics (e.g., velocity' = -friction).
  2. Loop Invariants: In software verification, a "loop invariant" is a property that remains true before, during, and after a loop executes. The authors translate the continuous concept of Lyapunov functions into discrete loop invariants. If the "energy" of the system is bounded and decreasing across every iteration of the loop, the system is stable.
  3. Trust but Verify: The approach is implemented in the KeYmaera X theorem prover. To automate the process, the system uses Sum-of-Squares (SOS) numerical programming to guess a candidate Lyapunov function. However, KeYmaera X then uses strict symbolic logic to verify that candidate. If the numerical guess has floating-point errors, the prover rejects it.

Datasets

This paper does not use traditional machine learning datasets. Instead, the authors evaluate their approach on a benchmark suite of 10 classic switched system problems drawn from control theory literature, alongside three complex, real-world case studies:

  1. A longitudinal flight control model (Canonical Max System).
  2. An automated cruise controller.
  3. Brockett’s nonholonomic integrator (a classic system that cannot be stabilized by continuous feedback alone).

Key Insights and Ideas

  • Bridging CS and Control: By framing stability as "quantified loop safety," the authors elegantly unite discrete program verification with continuous control theory. You don't need to invent new math to handle the jumps in a switched system; standard software verification techniques work perfectly when combined with differential logic.
  • Ghost Switching: Just like programmers use "ghost variables" to help prove software correctness without changing the actual code, the authors introduce "ghost switching." This allows them to mathematically analyze non-differentiable systems (like those containing max() functions) by pretending the system switches modes, making the math solvable without altering the physical model.
  • Numerical Solvers Need Supervision: The authors demonstrate exactly why numerical solvers shouldn't be blindly trusted. During their cruise control case study, a standard numerical tool (Stabhyli) generated a Lyapunov function that was mathematically invalid due to tiny floating-point artifacts. The deductive logic approach successfully flagged this error, preventing a false proof of safety.

Key Results

  • High Automation: The KeYmaera X implementation successfully and automatically verified 9 out of the 10 benchmark examples.
  • Speed: Most of the automated stability proofs completed in just 2 to 20 seconds.
  • Flexibility: The deductive approach successfully handled highly complex edge cases. For example, Brockett's nonholonomic integrator requires an initial "event-triggered" phase to drive the system into a specific region before a stabilizing controller can take over. The logic-based approach easily adapted to this multi-stage stability argument.

Limitations and Future Work

  • Complex Math Bottlenecks: The approach still relies on finding a valid Lyapunov function. For time-dependent switching, the prover has to use polynomial Taylor approximations to handle exponential functions. If a system requires a very high-degree polynomial to be accurate, the prover can time out (as it did on Example 10 in their benchmark suite).
  • Future Work: Because the KeYmaera X prover independently and rigorously checks the math, the actual generation of the Lyapunov function doesn't need to be trusted. The authors suggest integrating a wider variety of untrusted heuristic, numerical, or AI-driven Lyapunov function generators in the future, knowing the prover will act as an infallible safety net.

Summary updated

Abstract

Switched systems are known to exhibit subtle (in)stability behaviors requiring system designers to carefully analyze the stability of closed-loop systems that arise from their proposed switching control laws. This paper presents a formal approach for verifying switched system stability that blends classical ideas from the controls and verification literature using differential dynamic logic (dL), a logic for deductive verification of hybrid systems. From controls, we use standard stability notions for various classes of switching mechanisms and their corresponding Lyapunov function-based analysis techniques. From verification, we use dL’s ability to verify quantified properties of hybrid systems and dL models of switched systems as looping hybrid programs whose stability can be formally specified and proven by finding appropriate loop invariants, i.e., properties that are preserved across each loop iteration. This blend of ideas enables a trustworthy implementation of switched system stability verification in the KeYmaera X prover based on dL. For standard classes of switching mechanisms, the implementation provides fully automated stability proofs, including searching for suitable Lyapunov functions. Moreover, the generality of the deductive approach also enables verification of switching control laws that require non-standard stability arguments through the design of loop invariants that suitably express specific intuitions behind those control laws. This flexibility is demonstrated on three case studies: a model for longitudinal flight control by Branicky, an automatic cruise controller, and Brockett’s nonholonomic integrator.
BibTeX
@inproceedings{tan2022verifying,
  author = {Yong Kiam Tan and Stefan Mitsch and André Platzer},
  title = {{Verifying Switched System Stability With Logic}},
  booktitle = {HSCC},
  year = {2022},
  doi = {10.1145/3501710.3519541},
}

Loading related content...

Figure