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.
Introduction
In control theory, "switched systems" are a class of hybrid systems that jump between different continuous physical behaviors based on discrete control logic—for instance, 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 automated tools exist 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 addresses the need for a trustworthy, computer-checked verification method that guarantees stability without falling victim to numerical approximations.
Formalizing Stability as Program Logic
The authors bridge the gap between continuous control theory and discrete software verification using Differential Dynamic Logic (dL). The core innovation lies in modeling 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).
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 remains within specific regions (as shown in the stability and pre-attractivity diagrams above) across every iteration of the loop, the system is formally stable.
Implementation and Results
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. This "trust but verify" architecture ensures that the final proof is mathematically sound.
The implementation was evaluated on a benchmark suite of 10 classic switched system problems and three complex case studies, including a longitudinal flight control model and Brockett’s nonholonomic integrator. Key results include:
- High Automation: KeYmaera X successfully and automatically verified 9 out of 10 benchmark examples.
- Efficiency: Most automated stability proofs completed in just 2 to 20 seconds.
- Robustness: The deductive approach successfully flagged errors in existing numerical tools. During a cruise control case study, a standard tool (Stabhyli) generated a Lyapunov function that was mathematically invalid due to tiny floating-point artifacts; KeYmaera X correctly rejected it.
Conclusion
By framing stability as "quantified loop safety," this work unites discrete program verification with continuous control theory. The use of "ghost switching" further allows for the analysis of non-differentiable systems by mathematically modeling them as switching modes. While complex systems requiring high-degree polynomial approximations remain a challenge, the prover acts as an infallible safety net. Future work may involve integrating a wider variety of untrusted heuristic or AI-driven Lyapunov function generators, relying on the prover to rigorously validate their outputs.
Summary updated