The classical view of epistemic logic is that an agent knows all the logical consequences of their knowledge base. This assumption of logical omniscience is often unrealistic and makes reasoning computationally intractable. One approach to avoid logical omniscience is to limit reasoning to a certain belief level, which intuitively measures the reasoning "depth".This paper investigates the computational complexity of reasoning with belief levels. First we show that while reasoning remains tractable if the level is constant, the complexity jumps to PSPACE-complete -- that is, beyond classical reasoning -- when the belief level is part of the input. Then we further refine the picture using parameterized complexity theory to investigate how the belief level and the number of non-logical symbols affect the complexity.

Logics of limited belief aim at enabling computationally feasible reasoning in highly expressive representation languages. These languages are often dialects of first-order logic with a weaker form of logical entailment that keeps reasoning decidable or even tractable. While a number of such logics have been proposed in the past, they tend to remain for theoretical analysis only and their practical relevance is very limited. In this paper, we aim to go beyond the theory. Building on earlier work by Liu, Lakemeyer, and Levesque, we develop a logic of limited belief that is highly expressive but remains decidable in the first-order and tractable in the propositional case and exhibits some characteristics that make it attractive for an implementation. We introduce a reasoning system that employs this logic as representation language and present experimental results that showcase the benefit of limited belief.

We introduce Limbo, a reasoning system for limited belief. The system features a highly expressive language with first-order quantification, functions and equality, sorts, and introspective belief modalities. Reasoning is based on clause subsumption, unit propagation, and case splits. Decidability and sometimes even tractability is achieved by limiting the number of case splits. We illustrate the practical utility of limited belief with toy examples as well as with the games of Sudoku and Minesweeper.

In a series of papers, Liu, Lakemeyer, and Levesque address the problem of decidable reasoning in expressive first-order knowledge bases. Here, we extend their ideas to accommodate conditional beliefs, as in “if she is Australian, then she presumably eats Kangaroo meat.” Perhaps the most prevalent semantics of a conditional belief is to evaluate the consequent in the most-plausible worlds consistent with the premise. In this paper, we devise a technique to approximate this notion of plausibility, and complement it with Liu, Lakemeyer, and Levesque's weak inference. Based on these ideas, we develop a logic of limited conditional belief, and provide soundness, decidability, and (for the propositional case) tractability results.

Robot sensors are usually subject to error. Since in many practical scenarios a probabilistic error model is not available, sensor readings are often dealt with in a hard-coded, heuristic fashion. In this paper, we propose a logic to address the problem from a KR perspective. In this logic, the epistemic effect of sensing actions is deferred to so-called fusion actions, which may resolve discrepancies and inconsistencies of recent sensing results. Moreover, a local closed-world assumption can be applied dynamically. When needed, this assumption can be revoked and fusions can be undone using a form of forgetting.

A fundamental task in reasoning about action and change is projection, which refers to determining what holds after a number of actions have occurred. A powerful method for solving the projection problem is regression, which reduces reasoning about the future to reasoning about the initial state. In particular, regression has played an important role in the situation calculus and its epistemic extensions. Recently, a modal variant of the situation calculus was proposed, which allows an agent to revise its beliefs based on so-called belief conditionals as part of its knowledge base. In this paper, we show how regression can be extended to reduce beliefs about the future to initial beliefs in the presence of belief conditionals. Moreover, we show how any remaining belief operators can be eliminated as well, thus reducing the belief projection problem to ordinary first-order entailments.

Recently Shapiro et al. explored the notion of iterated belief revision within Reiter's version of the situation calculus. In particular, they consider a notion of belief defined as truth in the most plausible situations. To specify what an agent is willing to believe at different levels of plausibility they make use of so-called belief conditionals, which themselves neither refer to situations or plausibilities explicitly. Reasoning about such belief conditionals turns out to be complex because there may be too many models satisfying them and negative belief conditionals are also needed to obtain the desired conclusions. In this paper we show that, by adopting a notion of only-believing, these problems can be overcome. The work is carried out within a modal variant of the situation calculus with a possible-world semantics which features levels of plausibility. Among other things, we show that only-believing a knowledge base together with belief conditionals always leads to a unique model, which allows characterizing the beliefs of an agent, after any number of revisions, in terms of entailments within the logic.