'Knowing Whether' in Proper Epistemic Knowledge Bases. Miller, T., Muise, C., Felli, P., Pearce, A. R., & Sonenberg, L. In The 30th AAAI Conference on Artificial Intelligence, 2016.
'Knowing Whether' in Proper Epistemic Knowledge Bases [pdf]Paper  abstract   bibtex   1 download  
Proper epistemic knowledge bases (PEKBs) are syntactic knowledge bases that use multi-agent epistemic logic to represent nested multi-agent knowledge and belief. PEKBs have certain syntactic restrictions that lead to desirable computational properties; primarily, a PEKB is a conjunction of modal literals, and therefore contains no disjunction. Sound entailment can be checked in polynomial time, and is complete for a large set of arbitrary formulae in logics Kn and KDn. In this paper, we extend PEKBs to deal with a restricted form of disjunction: ‘knowing whether’. An agent i knows whether ϕ iff agent i knows ϕ or knows ¬ϕ; that is, iϕ ∨ i¬ϕ. In our experience, the ability to represent that an agent knows whether something holds is useful in many multi-agent domains. We represent knowing whether with a modal operator, ∆i, and present sound polynomial-time entailment algorithms on PEKBs with ∆i in Kn and KDn, but which are complete for a smaller class of queries than standard PEKBs.
@inproceedings{miller-aaai-16,
  author = {Tim Miller and Christian Muise and Paolo Felli and Adrian R. Pearce and Liz Sonenberg},
  year = {2016},
  booktitle = {The 30th AAAI Conference on Artificial Intelligence},
  keywords = {multi-agent planning, epistemic reasoning},
  url = {http://www.haz.ca/papers/miller-aaai-16.pdf},
  title = {'Knowing Whether' in Proper Epistemic Knowledge Bases},
  abstract = {Proper epistemic knowledge bases (PEKBs) are syntactic knowledge bases that use multi-agent epistemic logic to represent nested multi-agent knowledge and belief. PEKBs have certain syntactic restrictions that lead to desirable computational properties; primarily, a PEKB is a conjunction of modal literals, and therefore contains no disjunction. Sound entailment can be checked in polynomial time, and is complete for a large set of arbitrary formulae in logics Kn and KDn. In this paper, we extend PEKBs to deal with a restricted form of disjunction: ‘knowing whether’. An agent i knows whether ϕ iff agent i knows ϕ or knows ¬ϕ; that is, iϕ ∨ i¬ϕ. In our experience, the ability to represent that an agent knows whether something holds is useful in many multi-agent domains. We represent knowing whether with a modal operator, ∆i, and present sound polynomial-time entailment algorithms on PEKBs with ∆i in Kn and KDn, but which are complete for a smaller class of queries than standard PEKBs.}
}
Downloads: 1