Efficient Reasoning in Multiagent Epistemic Logics

摘要

In many applications, agents must reason about what other agents know, whether to coordinate with them or to come out on top in a competitive situation. However in general, reasoning in a multiagent epistemic logic such as K_n has high complexity. In this paper, we look at a restricted class of knowledge bases that are sets of modal literals. We call these proper epistemic knowledge bases (PEKBs). We show that after a PEKB has been put in prime implicate normal form (PINF), an efficient database-like query evaluation procedure can be used to check whether an arbitrary query is entailed by the PEKB. The evaluation procedure is always sound and sometimes complete. We also develop a procedure to convert a PEKB into PINF. As well, we extend our approach to deal with introspection.