Abstract
This paper presents a formal framework for reasoning about nested knowledge in Discrete-Event Systems (DES). By modeling a hierarchy where a high-level agent observes the system to infer the knowledge state of a low-level agent, the authors unify various security and cooperation properties. We provide algorithmic structures for verification, demonstrating that high-order epistemic properties can often be checked with the same computational complexity as standard first-order properties.
Introduction
In Discrete-Event Systems (DES), such as manufacturing lines or robotic swarms, traditional analysis focuses on first-order properties: diagnosability (detecting faults) and opacity (hiding secrets). However, complex interactions require reasoning about "knowing what someone else knows." For instance, in a secure robotic system, it may be necessary to hide not just the robot's location, but also the fact that a base station has successfully localized the robot, preventing an adversary from inferring the system's readiness.
This research addresses the gap in high-order inference by moving from "What is the system doing?" to "What does Agent A think Agent B knows about the system?" This unified framework encompasses concepts like invisible attackers, knowledge security, and tacit cooperation.
The Two-Agent Knowledge Model
The core of the proposed framework is a hierarchical observer model.
As shown in the figure, the system consists of:
- Low-level observer ($H_o$): Observes system events to infer the current state (e.g., a system user or primary intruder).
- High-level observer ($H_a$): Independently observes the system to infer the knowledge state of the low-level observer.
To verify epistemic properties, the authors developed three algorithmic structures:
- Double-Estimator: A general approach building an estimator of an estimator, though it faces doubly-exponential complexity.
- Twin-Estimator: A more efficient construction for specific properties (e.g., certainty of the low-level observer), reducing complexity to a single exponential.
- State-Pair-Estimator: An optimized version for distinguishability-based properties, focusing on pairs of states the low-level observer might confuse.
Case Study and Results
The framework's utility is demonstrated through synthetic DFA models and a robot path-planning case study.
In the robot workspace example, the goal is to ensure "high-order opacity"—preventing an intruder from knowing when a user has successfully localized a robot within specific regions.
Key results include:
- Verification Efficiency: For a wide class of security properties, verification is PSPACE-complete, matching the complexity of standard first-order opacity. This suggests that adding a layer of nested knowledge does not necessarily make the problem computationally harder in the worst case.
- Formal Soundness: Rigorous proofs confirm that the Double-Estimator and Twin-Estimator constructions correctly decide epistemic properties.
- Delayed Knowledge: The framework successfully extends to "Finite Epistemic Diagnosability," where the high-level observer's realization may occur after a finite delay.
Conclusion and Future Work
This work provides a robust foundation for epistemic reasoning in DES. While currently limited to a two-agent hierarchy, it paves the way for multi-agent systems with mutual knowledge. Future research will focus on control synthesis—automatically designing controllers to enforce these properties—and improving scalability through symbolic verification or abstraction techniques to handle larger state spaces.
Summary updated