Refining Constructive Hybrid Games

Rose Bohrer, André Platzer

Abstract

We extend the constructive differential game logic (CdGL) of hybrid games with a refinement connective that relates two hybrid games. We use this connective to prove a folk theorem relating hybrid games to hybrid systems.

Introduction

Cyber-Physical Systems (CPS)—such as autonomous vehicles, surgical robots, and smart power grids—operate at the critical intersection of discrete computational logic and continuous physical dynamics. Ensuring the safety and reliability of these systems is a significant challenge, particularly when they must operate in adversarial or unpredictable environments. Such scenarios are formally modeled as hybrid games, where a controller (Angel) competes against an environment or adversary (Demon).

While formal verification of hybrid systems—where a single agent controls all choices—is well-established, verifying hybrid games is significantly more complex. A long-standing "folk theorem" in the field suggests that if a winning strategy exists for a game, it should be possible to transform that game into a simpler, verified hybrid system. However, formalizing this transformation and proving its safety has remained a challenge. This paper addresses this gap by introducing a refinement calculus for Constructive Differential Game Logic (CdGL).

Methodology: Constructive Logic and Refinement

The authors utilize a constructive approach to logic. In CdGL, a proof that a player can win a game is not merely an existential claim; it is a concrete recipe or algorithm for a winning strategy. This "proofs-as-programs" paradigm is central to the paper's contributions.

The Refinement Connective

The paper introduces a new logical operator, the refinement connective ($\alpha \leq \beta$). This operator allows for formal reasoning about the relationship between two hybrid games. Specifically, if $\alpha \leq \beta$, then any winning strategy for game $\beta$ can be systematically mapped to a winning strategy for game $\alpha$. This provides a rigorous framework for relational reasoning, allowing developers to compare different versions of a controller or simplify complex models.

The Inlining Operation

The centerpiece of the methodology is the inlining operation. This recursive process takes a hybrid game and a corresponding proof of a winning strategy and "compiles" them into a hybrid system. During inlining, the non-deterministic choices previously made by Angel are resolved (determinized) according to the strategy found in the proof. Conversely, the choices made by the opponent (Demon) are preserved as non-deterministic transitions within the resulting system. To ensure mathematical soundness, the authors provide a semantics based on the Calculus of Inductive Constructions.

Key Insights

  1. The Proof is the Controller: Because the logic is constructive, the safety proof itself serves as the specification for the controller. Inlining acts as a bridge between high-level logical requirements and implementable system behavior.
  2. Collapsing Expressiveness: Hybrid games are mathematically more expressive than hybrid systems. The authors demonstrate that this gap is bridged once a specific strategy is known; the strategy effectively "collapses" the game's adversarial complexity into a system's structure.
  3. Handling Subnormality: Game logics are typically "subnormal," meaning they do not satisfy the standard K axiom of modal logic. The authors developed specific refinement rules to maintain logical soundness while accounting for these nuances.

Key Results and Theorems

The paper establishes three fundamental theorems that validate the inlining framework:

  • Systemhood: The output of the inlining operation is guaranteed to be a hybrid system, devoid of adversarial game dualities.
  • Inlining Transfer: A proof of safety for the original game is preserved through the inlining process. The resulting system is guaranteed to satisfy the same safety properties as the game from which it was derived.
  • Inlining Refinement: The generated system is a formal refinement of the original game, ensuring it operates within the bounds defined by the initial model.

The authors illustrate these concepts using a "push-pull cart" example, demonstrating how a mirroring strategy (where Angel moves to counteract Demon) can be formally inlined to create a verified, safe controller.

Conclusion and Future Work

This work provides a robust theoretical foundation for the automated synthesis of verified controllers from game-theoretic specifications. By formalizing the "folk theorem" relating games to systems, the authors enable more rigorous development of CPS. Future work involves integrating these logical foundations into practical synthesis tools like ModelPlex and addressing the computational challenges associated with complex, non-linear differential equations in high-dimensional spaces.

Summary updated

Abstract

We extend the constructive differential game logic (CdGL) of hybrid games with a refinement connective that relates two hybrid games. We use this connective to prove a folk theorem relating hybrid games to hybrid systems.
BibTeX
@inproceedings{bohrer2020refining,
  author = {Rose Bohrer and André Platzer},
  title = {{Refining Constructive Hybrid Games}},
  booktitle = {FSCD},
  year = {2020},
  doi = {10.4230/lipics.fscd.2020.14},
}
Figure