Probabilistic Modal Logic

摘要

A modal logic is any logic for handling modalities: concepts like possibility, necessity, and knowledge. Artificial intelligence uses modal logics most heavily to represent and reason about knowledge of agents about others' knowledge. This type of reasoning occurs in dialog, collaboration, and competition. In many applications it is also important to be able to reason about the probability of beliefs and events. In this paper we provide a formal system that represents probabilistic knowledge about probabilistic knowledge. We also present exact and approximate algorithms for reasoning about the truth value of queries that are encoded as probabilistic modal logic formulas. We provide an exact algorithm which takes a probabilistic Kripke structure and answers probabilistic modal queries in polynomial-time in the size of the model. Then, we introduce an approximate method for applications in which we have very many or infinitely many states. Exact methods are impractical in these applications and we show that our method returns a close estimate efficiently.