TL;DR
This paper introduces a new "refinement" connective for Constructive Differential Game Logic (CdGL), allowing us to formally relate different hybrid games. This enables proving that a winning strategy in one game transfers to another, and crucially, provides a rigorous method to synthesize hybrid systems from winning strategies of hybrid games. This bridges a significant gap between game-theoretic verification and practical system implementation.
What Problem Does This Paper Address?
Cyber-physical systems (CPSs) are often modeled using hybrid systems, which combine discrete logic with continuous dynamics. Hybrid games extend this by introducing adversarial players. While formal verification methods like Differential Game Logic (dGL) and its constructive variant (CdGL) can prove the existence of winning strategies for hybrid games, synthesizing actual hybrid systems from these strategies has been ad-hoc. This paper addresses the challenge of formally connecting the abstract world of hybrid games and winning strategies to the concrete world of implementable hybrid systems. They aim to provide a principled way to "reify" a winning strategy from a game into a system that embodies that strategy, making existing system synthesis tools applicable.
Methods
The core contribution is the introduction of a refinement connective for CdGL. This connective allows reasoning about relationships between games. Specifically, they define Demonic refinement ($\alpha \le_{i} \beta$) which states that if a player can win game $\alpha$ (under certain conditions), they can also win game $\beta$. This is crucial because it allows proving that a strategy for one game is "better" or "equivalent" to a strategy for another.
Building on this, they introduce reification, a process that takes a CdGL proof of a winning strategy for a hybrid game and transforms it into a hybrid system. This process is constructive, meaning the resulting system is guaranteed to implement the strategy. They prove three key properties of this reification:
- Systemhood: The reified object is indeed a hybrid system (i.e., it doesn't have adversarial choices).
- Transfer: The safety property proven for the game also holds for the reified system.
- Refinement: The reified system refines the original game, meaning any property provable for the system is also provable for the game.
The work leverages a type-theoretic semantics for CdGL and a natural deduction proof calculus for refinements.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Refinement as a Bridge: The refinement connective is the key innovation, providing a formal language to compare games and strategies. This is more powerful than just proving existence of strategies; it allows relating strategies to each other.
- Constructive Synthesis: The constructive nature of CdGL is essential. It guarantees that winning strategies are computable, which is a prerequisite for synthesizing them into actual systems.
- Reification: From Abstract to Concrete: The paper provides a formal, provably correct method to translate abstract winning strategies from games into concrete hybrid systems. This is a significant step towards automated synthesis of safety-critical CPSs.
- Systemhood, Transfer, and Refinement: These three properties form a robust specification for reification, ensuring that the synthesized system is not only a system but also faithfully represents the strategy and maintains the original safety guarantees.
- Demonic Refinement as Primary: The authors choose to focus on Demonic refinement, which aligns well with the goal of synthesizing systems where adversarial choices are handled deterministically.
Key Results
The paper presents a formal refinement calculus for CdGL and proves its soundness. The main theoretical results are Theorems 8, 9, and 10, which formally establish the properties of reification:
- Theorem 8 (Systemhood): A reified strategy from a hybrid game results in a hybrid system.
- Theorem 9 (Reification Transfer): If a game satisfies a property, its reified system also satisfies that property.
- Theorem 10 (Reification Refinement): The reified system refines the original game, meaning the system is a "more specific" or "more constrained" version of the game.
These theorems provide the theoretical foundation for using CdGL to synthesize hybrid systems.
Limitations and Future Work
- System-Test Fragment: The reification process is currently defined for "system-test" fragments of CdGL. This means that certain complex game modalities are not directly supported in the proofs used for reification. Future work could extend this to more general game structures.
- Practical Implementation: While the theoretical framework is established, the practical implementation of these refinement rules and the reification process within theorem provers is a significant undertaking.
- Comparing Strategies: The authors suggest that refinement can be used to compare the efficacy of different strategies or controllers, which is a promising avenue for future research.
- End-to-End Synthesis: The work lays the groundwork for integrating with existing synthesis tools like VeriPhy, enabling end-to-end verified synthesis of hybrid systems from game specifications.
- Formalizing Proofs: The proofs for the metatheoretic results are provided in a companion report, indicating that a full formalization within a proof assistant is a substantial effort.
Summary updated