A Semantic Approach to Decidability in Epistemic Planning (Extended Version)

• URL: http://arxiv.org/abs/2307.15485v1
• Date: Fri, 28 Jul 2023 11:26:26 GMT
• Title: A Semantic Approach to Decidability in Epistemic Planning (Extended Version)
• Authors: Alessandro Burigana, Paolo Felli, Marco Montali and Nicolas Troquard
• Abstract summary: We use a novel semantic approach to achieve decidability. Specifically, we augment the logic of knowledge S5$_n$ and with an interaction axiom called (knowledge) commutativity. We prove that our framework admits a finitary non-fixpoint characterization of common knowledge, which is of independent interest.
• Score: 72.77805489645604
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: The use of Dynamic Epistemic Logic (DEL) in multi-agent planning has led to a widely adopted action formalism that can handle nondeterminism, partial observability and arbitrary knowledge nesting. As such expressive power comes at the cost of undecidability, several decidable fragments have been isolated, mainly based on syntactic restrictions of the action formalism. In this paper, we pursue a novel semantic approach to achieve decidability. Namely, rather than imposing syntactical constraints, the semantic approach focuses on the axioms of the logic for epistemic planning. Specifically, we augment the logic of knowledge S5$_n$ and with an interaction axiom called (knowledge) commutativity, which controls the ability of agents to unboundedly reason on the knowledge of other agents. We then provide a threefold contribution. First, we show that the resulting epistemic planning problem is decidable. In doing so, we prove that our framework admits a finitary non-fixpoint characterization of common knowledge, which is of independent interest. Second, we study different generalizations of the commutativity axiom, with the goal of obtaining decidability for more expressive fragments of DEL. Finally, we show that two well-known epistemic planning systems based on action templates, when interpreted under the setting of knowledge, conform to the commutativity axiom, hence proving their decidability.

Related papers

• An epistemic logic for modeling decisions in the context of incomplete knowledge [9.104555003332344]
  This paper presents a new language for modeling decisions with incomplete knowledge. It combines three principles: stratification, autoepistemic logic, and definitions.
  arXiv  Detail & Related papers  (2023-12-18T13:27:04Z)
• From Heuristic to Analytic: Cognitively Motivated Strategies for Coherent Physical Commonsense Reasoning [66.98861219674039]
  Heuristic-Analytic Reasoning (HAR) strategies drastically improve the coherence of rationalizations for model decisions. Our findings suggest that human-like reasoning strategies can effectively improve the coherence and reliability of PLM reasoning.
  arXiv  Detail & Related papers  (2023-10-24T19:46:04Z)
• Interpretable Imitation Learning with Dynamic Causal Relations [65.18456572421702]
  We propose to expose captured knowledge in the form of a directed acyclic causal graph. We also design this causal discovery process to be state-dependent, enabling it to model the dynamics in latent causal graphs. The proposed framework is composed of three parts: a dynamic causal discovery module, a causality encoding module, and a prediction module, and is trained in an end-to-end manner.
  arXiv  Detail & Related papers  (2023-09-30T20:59:42Z)
• DELPHIC: Practical DEL Planning via Possibilities (Extended Version) [76.75197961194182]
  This work aims to push the envelop of practical DEL planning. We propose an equivalent semantics defined using, as main building block, so-called possibilities. To substantiate this claim, we implement both approaches in ASP and we set up an experimental evaluation to compare DELPHIC with the traditional, Kripke-based approach.
  arXiv  Detail & Related papers  (2023-07-28T10:09:45Z)
• Towards Trustworthy Explanation: On Causal Rationalization [9.48539398357156]
  We propose a new model of rationalization based on two causal desiderata, non-spuriousness and efficiency. The superior performance of the proposed causal rationalization is demonstrated on real-world review and medical datasets.
  arXiv  Detail & Related papers  (2023-06-25T03:34:06Z)
• Learnability with PAC Semantics for Multi-agent Beliefs [38.88111785113001]
  The tension between deduction and induction is perhaps the most fundamental issue in areas such as philosophy, cognition and artificial intelligence. Valiant recognised that the challenge of learning should be integrated with deduction. Although weaker than classical entailment, it allows for a powerful model-theoretic framework for answering queries.
  arXiv  Detail & Related papers  (2023-06-08T18:22:46Z)
• Learning a Structural Causal Model for Intuition Reasoning in Conversation [20.243323155177766]
  Reasoning, a crucial aspect of NLP research, has not been adequately addressed by prevailing models. We develop a conversation cognitive model ( CCM) that explains how each utterance receives and activates channels of information. By leveraging variational inference, it explores substitutes for implicit causes, addresses the issue of their unobservability, and reconstructs the causal representations of utterances through the evidence lower bounds.
  arXiv  Detail & Related papers  (2023-05-28T13:54:09Z)
• Nested Counterfactual Identification from Arbitrary Surrogate Experiments [95.48089725859298]
  We study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. Specifically, we prove the counterfactual unnesting theorem (CUT), which allows one to map arbitrary nested counterfactuals to unnested ones.
  arXiv  Detail & Related papers  (2021-07-07T12:51:04Z)
• Thinking About Causation: A Causal Language with Epistemic Operators [58.720142291102135]
  We extend the notion of a causal model with a representation of the state of an agent. On the side of the object language, we add operators to express knowledge and the act of observing new information. We provide a sound and complete axiomatization of the logic, and discuss the relation of this framework to causal team semantics.
  arXiv  Detail & Related papers  (2020-10-30T12:16:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.