We consider the problem of reasoning and planning with incomplete knowledge and deterministic actions. We introduce a knowledge representation scheme called PSIPLAN that can effectively represent incompleteness of an agent's knowledge while allowing for sound, complete and tractable entailment in domains where the set of all objects is either unknown or infinite. We present a procedure for state update resulting from taking an action in PSIPLAN that is correct, complete and has only polynomial complexity. State update is performed without considering the set of all possible worlds corresponding to the knowledge state. As a result, planning with PSIPLAN is done without direct manipulation of possible worlds. PSIPLAN representation underlies the PSIPOP planning algorithm that handles quantified goals with or without exceptions that no other domain independent planner has been shown to achieve. PSIPLAN has been implemented in Common Lisp and used in an application on planning in a collaborative interface.

Partially observable Markov decision processes (POMDPs) provide a general framework for AI planning, but they lack the structure for representing real world planning problems in a convenient and efficient way. Representations built on logic allow for problems to be specified in a compact and transparent manner. Moreover, decision making algorithms can assume and exploit structure found in the state space, actions, observations, and success criteria, and can solve with relative efficiency problems with large state spaces. In recent years researchers have sought to combine the benefits of logic with the expressiveness of POMDPs. In this paper, we show how to build upon and extend the results in this fusing of logic and decision theory. In particular, we present a compact representation of POMDPs and a method to update beliefs after actions and observations. The key contribution is our compact representation of belief states and of the operations used to update them. We then use heuristic search to find optimal plans that maximize expected total reward given an initial belief state

For over a decade, the Hidden Markov Model (HMM) has been the primary tool used for acoustic modeling in the field of speech recognition. In this paper we examine a more general approach using a Partially Observable Markov Decision Process (POMDP) to mo del the base phonetic unit. We introduce the concept of multiple phonetic context classes, one for each of the infinite possible contexts a phoneme can be in, and show how a POMDP can be used to represent such a model. Much the same way that tying mixtures at the state level across phonemes sharing linguistic properties is used to fill in gaps in the model space due to lack of data, the POMDP model can fill in additional gaps, in effect adding a second level of clustering driven by the data itself.

NIKL was the successor to KL‐ONE, the first knowledge representation system to implement “term subsumption” semantics. The primary goals for NIKL were to improve the expressivity and efficiency of KL‐ONE. In the process of developing and using NIKL as the primary representational vehicle for several applications, important new representational needs were identified and addressed, and issues both theoretical and practical in knowledge representation were formulated. In this paper, we present the core of NIKL by way of description, examples, and a model theoretic semantics. We describe the motivations behind the major NIKL design decisions, and discuss NIKL'S capabilities and limitations as a working representation system.