Recently, much attention has focused on discrepancies between intuition and formalization in nonmonotonic reasoning systems, particularly with respect to the frame problem. For example, in the Hanks-McDermott shooting problem [Hanks and McDermott, 19861, a seemingly natural formalization in terms of Reiter's Default Logic [Reiter, 19801, using normal defaults, supports two interpretations of the events where only one appears to make intuitive sense. A partial solution to this quandary is proposed in [Morris, 19871, where it is shown that a very similar formulation using a truth maintenance system (TMS) supports only the intuitively sanctioned interpretation. Moreover, that interpretation is appropriately revised in response to new conflicting information by the mechanism of dependency-directed backtracking. One drawback of the TMS solution is that truth maintenance is quite limited as an inference mechanism. For example, it is not possible, given justifications A B and -A --, B, to conclude B. It is of interest to learn to what extent the inference methods of more powerful logic systems are compatible with intuitively sound nonmonotonic reasoning.

However, Perlis has shown that one of these formalisms, circumscription, is subject to certain counterintuitive limitations. Kraus and Perlis suggested a partial solution, but significant problems remain. In this paper, we observe that the unfortunate limitations of circumscription are even broader than Perlis originally pointed out. Moreover, these problems are not confined to circumscription; they appear to be endemic in current nonmonotonic reasoning formalisms. We develop a much more general solution than that of Kraus and Perlis, involving restricting the scope of nonmonotonic reasoning, and show that it remedies these problems in a variety of formalisms.

Decision theory and nonmonotonic logics are formalisms that can be employed to represent and solve problems of planning under uncertainty. We analyze the usefulness of these two approaches by establishing a simple correspondence between the two formalisms. The analysis indicates that planning using nonmonotonic logic comprises two decision-theoretic concepts: probabilities (degrees of belief in planning hypotheses) and utilities (degrees of preference for planning outcomes). We present and discuss examples of the following lessons from this decision-theoretic view of nonmonotonic reasoning: (1) decision theory and nonmonotonic logics are intended to solve different components of the planning problem; (2) when considered in the context of planning under uncertainty, nonmonotonic logics do not retain the domain-independent characteristics of classical (monotonic) logic; and (3) because certain nonmonotonic programming paradigms (for example, frame-based inheritance, nonmonotonic logics) are inherently problem specific, they might be inappropriate for use in solving certain types of planning problems. We discuss how these conclusions affect several current AI research issues.

Langlotz, Curtis, Shortliffe, Edward H.