TL;DR
This paper introduces DELVO, a novel logic for reasoning about an agent's knowledge after non-deterministic actions, particularly in environments with distributed private data. It extends existing dynamic epistemic logics to handle "opaque" choices and compositions, where agents might not fully observe the outcome of an action, and also proposes a PDL-like logic, PDLVE, to explore similar concepts in a more abstract setting.
What Problem Does This Paper Address?
Understanding how an agent's knowledge changes after an action is a fundamental problem in AI and logic. Existing logics like Propositional Dynamic Logic (PDL) and Dynamic Epistemic Logic (DEL) handle deterministic actions and non-deterministic choices reasonably well. However, they often assume that agents can fully observe the consequences of an action. This paper tackles the challenge of modeling knowledge dynamics in scenarios where actions are non-deterministic, and agents have limited or "opaque" vision, meaning they might not be able to distinguish between different possible outcomes of an action. This is particularly relevant in "Semi-Public Environments" where data is distributed privately, and agents may not have constant access to all information. The paper aims to unify existing approaches and introduce new formalisms to capture these nuances of knowledge and action.
Methods
The core contribution is the introduction of DELVO (Dynamic Epistemic Logic with Vision and Ontic change). DELVO extends Dynamic Epistemic Logic (DEL) by incorporating:
- Vision: Agents have a vision function that specifies which variables they can observe. This is crucial for distinguishing between worlds.
- Ontic Change: Actions can change the state of the world (ontic change). DELVO uses "toggle sets" to model these changes, which is a more general approach than standard assignments.
- Opaque Choice and Composition: DELVO introduces operators for "opaque" non-deterministic choice (⊕) and sequential composition (;;). These operators model situations where an agent might not be able to distinguish between different outcomes of an action, even if their vision function would normally allow it. This is achieved by modifying the accessibility relations in action models.
The paper also proposes PDLVE (Propositional Dynamic Logic with Vision and Epistemic operators), a more abstract, PDL-like logic. PDLVE aims to capture similar concepts of opaque choice and composition but without relying on explicit action models, instead using PDL's more general atomic actions and relations.
The authors provide sound and complete axiomatizations for DELVO and establish embedding results that relate DELVO to existing logics like DEL and SPE (Semi-Public Environments), and also relate DELVO to PDLVE.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The "Opaque" Nature of Knowledge Dynamics: The most significant insight is the formalization of "opaque" choice and composition. The paper demonstrates that standard assumptions about how agents update their knowledge after non-deterministic actions break down when agents cannot fully distinguish outcomes. This leads to counter-intuitive results where an agent might know something after each individual action but not after the non-deterministic choice between them.
- Vision as a Key Differentiator: The concept of "vision" is central. It's not just about what an agent can see, but how that vision interacts with the non-deterministic nature of actions to determine what they can know.
- Unifying Frameworks: DELVO and PDLVE are presented as unifying frameworks that can encompass and extend existing logics like DEL and SPE, offering a more nuanced way to model knowledge in complex dynamic environments.
- Bridging PDL and DEL: The paper explores how to translate concepts from DEL (action models) into the more abstract PDL setting (PDLVE), highlighting the trade-offs and expressive power of each approach.
Key Results
- DELVO Logic: A new logic, DELVO, is defined with a sound and complete axiomatization, capable of modeling epistemic and ontic change with vision and opaque actions.
- PDLVE Logic: A PDL-like logic, PDLVE, is introduced to explore similar concepts in a more abstract setting, allowing for a richer class of actions.
- Embedding Results: The paper provides theorems showing how DELVO can be embedded into PDLVE and how DEL and SPE models can be translated into DELVO models, establishing formal relationships between these logics.
- Demonstration of Opaque Effects: Through examples, the paper illustrates how opaque choice and composition lead to different knowledge updates compared to standard, transparent actions. For instance, an agent might know
¬Kw2xafter an opaque actionx ⊕ T!but not after the transparent actionx ∪ T!.
Limitations and Future Work
- Vision Atoms: The authors suggest extending DELVO to allow vision atoms for arbitrary formulas, not just variables, to increase its expressive power.
- PDLVE Proof System: A significant piece of future work is the development of a proof system for PDLVE.
- Awareness and Higher-Order Vision: The paper points to existing work on distinguishing between the capability to use vision and its actual use, as well as notions of common knowledge vision, suggesting avenues for further research.
- Action Awareness: Investigating scenarios where agents are not aware of the actions being executed or certain variables is proposed.
- Comparison with Situation Calculus: A systematic comparison with the Situation Calculus framework is suggested.
- Generalization of PDLVE Actions: The paper notes that the PDLVE action definitions are somewhat restricted and could be generalized.
Summary updated