A General Framework for Expressing Preferences in Causal Reasoning and Planning

We consider the problem of representing arbitrary preferencesin causal reasoning and planning systems. In planning, a preferencemay be seen as a goal or constraint that is desirable, but notnecessary, to satisfy. To begin, we define a very general querylanguage for histories, or interleaved sequences of world statesand actions. Based on this, we specify a second language inwhich preferences are defined. A single preference defines abinary relation on histories, indicating that one history ispreferred to the other. From this, one can define global preferenceorderings on the set of histories, the maximal elements of whichare the preferred histories. The approach is very general andflexible; thus it constitutes a ‘base’ languagein terms of which higher-level preferences may be defined. Tothis end, we investigate two fundamental types of preferencesthat we call choice and temporal preferences. We consider concretestrategies for these types of preferences and encode them interms of our framework. We suggest how to express aggregatesin the approach, allowing, e.g. the expression of a preferencefor histories with lowest total action costs. Last, our approachcan be used to express other approaches and so serves as a commonframework in which such approaches can be expressed and compared.We illustrate this by indicating how an approach due to Sonand Pontelli can be encoded in our approach, as well as thelanguage PDDL3.     

A note on evidence and confirmation in machine learning

This paper addresses the problem in inductive generalization of determining when a general hypothesis is supported by a particular instance. If we accept that, first, some facts do indeed support a general hypothesis and, second, that an instance that supports a hypothesis also supports all logical consequences of the hypothesis, then unintuitive and problematic results are immediately forthcoming. These assumptions lead, for example, to the conclusion that a blue Honda is confirming evidence for the hypothesis that ravens are black. This problem is variously known as the paradoxes of confirmation or Hempel's paradox . In this paper I develop a formal characterization of the problem. The assumption that whatever supports all classical consequences of the hypothesis is rejected. Rather, I argue that a weaker notion of consequence should be adopted for determining what consequences of a hypothesis are supported by the same evidence. An extant formal system for learning from examples is used to address these problems of evidential support, and it is shown that in this framework the problems do not arise.     

A foundational approach to autonomous knowledge acquisition

A formal, foundational approach to autonomous knowledge acquisition is presented. In particular, "learning from examples" and "learning from being told" and the relation of these approaches to first-order representation systems are investigated. It is assumed initially that the only information available for acquisition is a stream of facts, or ground atomic formulae, describing a domain. On the basis of this information, hypotheses expressed in set-theoretic terms and concerning the application domain may be proposed. As further instances are received, the hypothesized relations may be modified or discarded, and new relations formed. The intent though is to characterize those hypotheses that may potentially be formed, rather than to specify the subset of the hypotheses that, for whatever reason, should be held.
Formal systems are derived by means of which the set of potential hypotheses is precisely specified, and a procedure is derived for restoring the consistency of a set of hypotheses after conflicting evidence is encountered. In addition, this work is extended to where a learning system may be "told" arbitrary sentences concerning a domain. Included in this is an investigation of the relation between acquiring knowledge and reasoning deductively. However, the interaction of these approaches leads to immediate difficulties which likely require informal, pragmatic techniques for their resolution. The overall framework is intended both as a foundation for investigating autonomous approaches to learning and as a basis for the development of such autonomous systems.     

Parallel belief revision: Revising by sets of formulas

The area of belief revision studies how a rational agent may incorporate new information about a domain into its belief corpus. An agent is characterised by a belief state K, and receives a new item of information α which is to be included among its set of beliefs. Revision then is a function from a belief state and a formula to a new belief state.We propose here a more general framework for belief revision, in which revision is a function from a belief state and a finite set of formulas to a new belief state. In particular, we distinguish revision by the set $\{\alpha ,\beta \}$ from the set $\{\alpha \wedge \beta \}$. This seemingly innocuous change has significant ramifications with respect to iterated belief revision. A problem in approaches to iterated belief revision is that, after first revising by a formula and then by a formula that is inconsistent with the first formula, all information in the original formula is lost.This problem is avoided here in that, in revising by a set of formulas S, the resulting belief state contains not just the information that members of S are believed to be true, but also the counterfactual supposition that if some members of S were later believed to be false, then the remaining members would nonetheless still be believed to be true. Thus if some members of S were in fact later believed to be false, then the other elements of S would still be believed to be true. Hence, we provide a more nuanced approach to belief revision. The general approach, which we call parallel belief revision, is independent of extant approaches to iterated revision. We present first a basic approach to parallel belief revision. Following this we combine the basic approach with an approach due to Jin and Thielscher for iterated revision. Postulates and semantic conditions characterising these approaches are given, and representation results provided. We conclude with a discussion of the possible ramifications of this approach in belief revision in general.     

A Classification and Survey of Preference Handling Approaches in Nonmonotonic Reasoning

In recent years, there has been a large amount of disparate work concerning the representation and reasoning with qualitative preferential information by means of approaches to nonmonotonic reasoning. Given the variety of underlying systems, assumptions, motivations, and intuitions, it is difficult to compare or relate one approach with another. Here, we present an overview and classification for approaches to dealing with preference. A set of criteria for classifying approaches is given, followed by a set of desiderata that an approach might be expected to satisfy. A comprehensive set of approaches is subsequently given and classified with respect to these sets of underlying principles.     

Representing von Neumann–Morgenstern Games in the Situation Calculus

Sequential von Neumann–Morgernstern (VM) games are a very general formalism for representing multi-agent interactions and planning problems in a variety of types of environments. We show that sequential VM games with countably many actions and continuous utility functions have a sound and complete axiomatization in the situation calculus. This axiomatization allows us to represent game-theoretic reasoning and solution concepts such as Nash equilibrium. We discuss the application of various concepts from VM game theory to the theory of planning and multi-agent interactions, such as representing concurrent actions and using the Baire topology to define continuous payoff functions.     

On a rule-based interpretation of default conditionals

In nonmonotonic reasoning, a default conditional α→β has most often been informally interpreted as a defeasible version of a classical conditional, usually the material conditional. There is however an alternative interpretation, in which a default is regarded essentially as a rule, leading from premises to conclusion. In this paper, we present a family of logics, based on this alternative interpretation. A general semantic framework under this rule-based interpretation is developed, and associated proof theories for a family of weak conditional logics is specified. Nonmonotonic inference is easily defined in these logics. Interestingly, the logics presented here are weaker than the commonly-accepted base conditional approach for defeasible reasoning. However, this approach resolves problems that have been associated with previous approaches.      

The complexity of minimum partial truth assignments and implication in negation-free formulae

In Artificial Intelligence there has been a great deal of interest in the tradeoff between expressiveness and tractability for various areas of symbolic reasoning. Here we present several complexity theory results for two areas, wherein we restrict the application of negation. First, we consider the problem of determining a minimum satisfying assignment for a (restricted) propositional sentence. We show that the problem of determining a minimum satisfying assignment for a sentence in negation-free CNF, even with no more than two disjuncts per clause, is NP-complete. We also show that unlessP=NP, no polynomial time approximation scheme can exist for this problem. However, the problem is in polynomial time if either each clause contains exactly one negative and one positive literal or we use exclusive-OR in the clauses instead of the more standard inclusive-OR. Second, the problem of determining logical implication between sentences composed solely of conjunctions and disjunctions is shown to be as difficult as that between arbitrary sentences. We also study this problem when the sentences are restricted to being in CNF or DNF. Determining whether a CNF sentence logically implies a DNF sentence is co-NP-complete, but in all other cases this problem is polynomial time. We argue that these results are relevant, first to areas where a least solution (in some fashion) is desired, and second, to limited deductive systems.