Logic and Decision-Theoretic Methods for Planning under Uncertainty

AI Magazine

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.


Default Reasoning From Statistics

AAAI Conferences

There are two common but quite distinct interpretations of probabilities: they can be interpreted as a measure of the extent to which an agent believes an assertion, i.e., as an agent's degree of belief, or they can be interpreted as an assertion of relative frequency, i.e., as a statistical measure. Used as statistical measures probabilities can represent various assertions about the objective statistical state of the world, while used as degrees of belief they can represent various assertions about the subjective state of an agent's beliefs. In this paper we examine how an agent who knows certain statistical facts about the world might infer probabilistic degrees of beliefs in other assertions from these statistics. For example, an agent who knows that most birds fly (a statistical fact) may generate a degree of belief greater than 0.5 in the assertion that


the Scope of Reasoning: Preliminary Report

AAAI Conferences

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.


Non-monotonic Reasoning in Deductive Argumentation

arXiv.org Artificial Intelligence

Argumentation is a non-monotonic process. This reflects the fact that argumentation involves uncertain information, and so new information can cause a change in the conclusions drawn. However, the base logic does not need to be non-monotonic. Indeed, most proposals for structured argumentation use a monotonic base logic (e.g. some form of modus ponens with a rule-based language, or classical logic). Nonetheless, there are issues in capturing defeasible reasoning in argumentation including choice of base logic and modelling of defeasible knowledge. And there are insights and tools to be harnessed for research in non-monontonic logics. We consider some of these issues in this paper.


Curing Anomalous Extensions

AAAI Conferences

In a recent paper, Hanks and McDermott presented a simple problem in temporal reasoning which showed that a seemingly natural representation of a frame axiom in nonmonotonic logic can give rise to an anomalous extension, i.e., one which is counterintuitive in that it does not appear to be supported by the known facts. An alternative, less formal approach to nonmonotonic reasoning uses the mechanism of a truth maintenance system (TMS). Surprisingly, when reformulated in terms of a TMS, the anomalous extension noted by Hanks and McDermott disappears. We analyze the reasons for this. First it is seen that anomalous extensions are not limited to temporal reasoning, but can occur in simple non-temporal default reasoning as well.