James Delgrande

AIJ Journal 2023 Journal Article

A general framework for preferences in answer set programming

• Gerhard Brewka
• James Delgrande
• Javier Romero
• Torsten Schaub

We introduce a general, flexible, and extensible framework for quantitative and qualitative preferences among the stable models of logic programs. Since it is straightforward to capture propositional theories and constraint satisfaction problems with logic programs, our approach is also relevant to optimization in satisfiability testing and constraint processing. We show how complex preference relations can be specified through user-defined preference types and their arguments. We describe how preference specifications are handled internally by so-called preference programs, which are used for dominance testing. We also provide algorithms for computing one, or all, preferred stable models of a logic program, and study the complexity of these problems. We implemented our approach in the asprin system by means of multi-shot answer set solving technology. We demonstrate the generality and flexibility of our methodology by showing how easily existing preference languages can be implemented in asprin. Finally, we empirically evaluate our contributions and contrast them with dedicated implementations.

KR Conference 2020 Conference Paper

A Preference-Based Approach to Defeasible Deontic Inference

• James Delgrande

In this paper we present an approach to defeasible deontic inference. Given a set of rules R expressing conditional obligations and a formula A giving contingent information, the goal is to determine the most desirable outcome with respect to this information. Semantically, the rules R induce a partial preorder on the set of models, giving the relative desirability of each model. Then the set of minimal A models characterises the best that can be attained given that A holds. A syntactic approach is also given, in terms of maximal subsets of material counterparts of rules in R, and that yields a formula that expresses the best outcome possible given that A holds. These approaches are shown to coincide, providing an analogue to a soundness and completeness result. Complexity is not unreasonable, being at the second level of the polynomial hierarchy when the underlying logic is propositional logic. The approach yields desirable and intuitive results, including for the various “paradoxes” of deontic reasoning. The approach also highlights an interesting difference in how specificity is dealt with in nonmonotonic and deontic reasoning.

KR Conference 2020 Conference Paper

Dyadic Obligations over Complex Actions as Deontic Constraints in the Situation Calculus

• Jens Claßen
• James Delgrande

With the advent of artificial agents in everyday life, it is important that these agents are guided by social norms and moral guidelines. Notions of obligation, permission, and the like have traditionally been studied in the field of Deontic Logic, where deontic assertions generally refer to what an agent should or should not do; that is they refer to actions. In Artificial Intelligence, the Situation Calculus is (arguably) the best known and most studied formalism for reasoning about action and change. In this paper, we integrate these two areas by incorporating deontic notions into Situation Calculus theories. We do this by considering deontic assertions as constraints, expressed as a set of conditionals, which apply to complex actions expressed as GOLOG programs. These constraints induce a ranking of "ideality" over possible future situations. This ranking in turn is used to guide an agent in its planning deliberation, towards a course of action that adheres best to the deontic constraints. We present a formalization that includes a wide class of (dyadic) deontic assertions, lets us distinguish prima facie from all-things-considered obligations, and particularly addresses contrary-to-duty scenarios. We furthermore present results on compiling the deontic constraints directly into the Situation Calculus action theory, so as to obtain an agent that respects the given norms, but works solely based on the standard reasoning and planning techniques.

JAIR Journal 2019 Journal Article

A Generalisation of AGM Contraction and Revision to Fragments of First-Order Logic

• Zhiqiang Zhuang
• Zhe Wang
• Kewen Wang
• James Delgrande

AGM contraction and revision assume an underlying logic that contains propositional logic. Consequently, this assumption excludes many useful logics such as the Horn fragment of propositional logic and most description logics. Our goal in this paper is to generalise AGM contraction and revision to (near-)arbitrary fragments of classical first-order logic. To this end, we first define a very general logic that captures these fragments. In so doing, we make the modest assumptions that a logic contains conjunction and that information is expressed by closed formulas or sentences. The resulting logic is called first-order conjunctive logic or FC logic for short. We then take as the point of departure the AGM approach of constructing contraction functions through epistemic entrenchment, that is the entrenchment-based contraction. We redefine entrenchment-based contraction in ways that apply to any FC logic, which we call FC contraction. We prove a representation theorem showing its compliance with all the AGM contraction postulates except for the controversial recovery postulate. We also give methods for constructing revision functions through epistemic entrenchment which we call FC revision; which also apply to any FC logic. We show that if the underlying FC logic contains tautologies then FC revision complies with all the AGM revision postulates. Finally, in the context of FC logic, we provide three methods for generating revision functions via a variant of the Levi Identity, which we call contraction, withdrawal and cut generated revision, and explore the notion of revision equivalence. We show that withdrawal and cut generated revision coincide with FC revision and so does contraction generated revision under a finiteness condition.

KR Conference 2018 Conference Paper

Incorporating Relevance in Epistemic States in Belief Revision

• James Delgrande
• Pavlos Peppas

We present an account of relevance in belief revision where, intuitively, one wants to only consider the relevant part of an agent’s epistemic state in a revision. We assume that relevance is a domain-specific notion, and that (ir)relevance assertions are given as part of the agent’s epistemic state. Such assertions apply in a given context, and are of the form “in the case that formula σ holds, the Y part of the agent’s epistemic state is independent of the rest of the epistemic state”, where Y is part of the signature of the language. Two approaches are given, one in which (in semantic terms) conditions are placed on a faithful ranking on possible worlds to enforce the (ir)relevance assertions, and a second in which the possible worlds characterising the agent’s beliefs may be modified in a revision. These approaches are shown to yield the same resulting belief set. Corresponding postulates and a representation result are given. The overall approach is compared to that of Parikh’s for language splitting as well as with multivalued dependencies in relational databases.

IJCAI Conference 2017 Conference Paper

A Unifying Framework for Probabilistic Belief Revision

• Zhiqiang Zhuang
• James Delgrande
• Abhaya Nayak
• Abdul Sattar

In this paper we provide a general, unifying framework for probabilistic belief revision. We first introduce a probabilistic logic called p-logic that is capable of representing and reasoning with basic probabilistic information. With p-logic as the background logic, we define a revision function called p-revision that resembles partial meet revision in the AGM framework. We provide a representation theorem for p-revision which shows that it can be characterised by the set of basic AGM revision postulates. P-revision represents an "all purpose" method for revising probabilistic information that can be used for, but not limited to, the revision problems behind Bayesian conditionalisation, Jeffrey conditionalisation, and Lewis's imaging. Importantly, p-revision subsumes all three approaches indicating that Bayesian conditionalisation, Jeffrey conditionalisation, and Lewis' imaging all obey the basic principles of AGM revision. As well our investigation sheds light on the corresponding operation of AGM expansion in the probabilistic setting.

AAAI Conference 2015 Conference Paper

A Syntax-Independent Approach to Forgetting in Disjunctive Logic Programs

• James Delgrande
• Kewen Wang

In this paper, we present an approach to forgetting in disjunctive logic programs, where forgetting an atom from a program amounts to a reduction in the signature of that program. Notably, the approach is syntax-independent, so that if two programs are strongly equivalent, then the result of forgetting a given atom in each program is also strongly equivalent. Our central definition of forgetting is abstract: forgetting an atom from program P is characterised by the set of those SE consequences of P that do not mention the atom to be forgotten. We provide an equivalent, syntactic, characterization in which forgetting an atom p is given by those rules in the program that do not mention p, together with rules obtained by a single inference step from those rules that do mention p. Forgetting is shown to have appropriate properties; in particular, answer sets are preserved in forgetting an atom. As well, forgetting an atom via the syntactic characterization results in a modest (at worst quadratic) blowup in the program size. Finally, we provide a prototype implementation of this approach to forgetting.

AAAI Conference 2015 Conference Paper

asprin: Customizing Answer Set Preferences without a Headache

• Gerhard Brewka
• James Delgrande
• Javier Romero
• Torsten Schaub

In this paper we describe asprin1, a general, flexible, and extensible framework for handling preferences among the stable models of a logic program. We show how complex preference relations can be specified through user-defined preference types and their arguments. We describe how preference specifications are handled internally by so-called preference programs, which are used for dominance testing. We also give algorithms for computing one, or all, optimal stable models of a logic program. Notably, our algorithms depend on the complexity of the dominance tests and make use of multi-shot answer set solving technology.

JAIR Journal 2015 Journal Article

Belief Change with Uncertain Action Histories

• Aaron Hunter
• James Delgrande

We consider the iterated belief change that occurs following an alternating sequence of actions and observations. At each instant, an agent has beliefs about the actions that have occurred as well as beliefs about the resulting state of the world. We represent such problems by a sequence of ranking functions, so an agent assigns a quantitative plausibility value to every action and every state at each point in time. The resulting formalism is able to represent fallible belief, erroneous perception, exogenous actions, and failed actions. We illustrate that our framework is a generalization of several existing approaches to belief change, and it appropriately captures the non-elementary interaction between belief update and belief revision.

IJCAI Conference 2015 Conference Paper

The Logic of Qualitative Probability

• James Delgrande
• Bryan Renne

In this paper we present a theory of qualitative probability. Work in the area goes back at least to de Finetti. The usual approach is to specify a binary operator with φ ψ having the intended interpretation that φ is not more probable than ψ. We generalise these approaches by extending the domain of the operator from the set of events to the set of finite sequences of events. If Φ and Ψ are finite sequences of events, Φ Ψ has the intended interpretation that the summed probabilities of the elements of Φ is not greater than the sum of those of Ψ. We provide a sound and complete axiomatisation for this operator over finite outcome sets, and show that this theory is sufficiently powerful to capture the results of axiomatic probability theory. We argue that our approach is simpler and more perspicuous than previous accounts. As well, we prove that our approach generalises the two major accounts for finite outcome sets.

KR Conference 2014 Short Paper

Toward a Knowledge Level Analysis of Forgetting

• James Delgrande

KR Conference 2012 Conference Paper

Belief revision with sensing and fallible actions

• James Delgrande
• Hector Levesque

use of the notion of plausibility, taken from ranking functions (or ordinal conditional functions) [Spohn, 1988]. This work generalises previous work in that it integrates possibly-fallible actions, belief revision (via informing actions), and sensing. The overall approach is one that has received extensive treatment in the belief revision community: we associate with an agent a belief state that consists not just of a set of contingent beliefs, but also a plausibility ordering over other potential beliefs, expressed in terms of an ordering over situations. Consequently, if an agent discovers that its beliefs are incorrect, then the plausibility ordering provides a principled means for modifying its beliefs. Our approach is based on the situation calculus, which provides a full account of reasoning about action. Actions are described in terms of their preconditions and their effects, exploiting Reiter’s solution to the frame problem [Reiter, 2001]. We augment this by including the case where an agent may intend to execute one action but inadvertently executes another. (For example the agent may accidentally press a wrong button.) Consequently we allow that the agent’s beliefs may evolve according to one sequence of actions (the actions it believes that it executed) while the world evolves in a different direction (according to the actions that the agent actually executes). This also has an epistemic component, in that the agent may be aware of such alternatives, and so in executing an action will keep track of such (according to the agent, counterfactual) possibilities. If this was all there were to the story, then the agent’s beliefs would simply diverge more and more from the real situation. However, the agent may carry out sensing actions; such actions are, by definition, with respect to the actual situation, and so via sensing the agent may correct incorrect beliefs. As well, we also allow that an agent may be informed of some fact. The idea here is that if the agent is informed that φ, it will amend its beliefs so that it accepts φ. This operation is exactly that of belief revision [Gärdenfors, 1988; Peppas, 2008]. A key point is that an agent may be informed of some formula, φ, and later of some other formula ψ that conflicts with φ; in this case the agent would nonetheless maintain a consistent set of beliefs (except in the limiting case where ψ is inconsistent). This approach extends previous work in several respects. It provides a complete integration of an account of reasoning about action with belief revision. In so doing, it allows arbi- An agent will generally have incomplete and possibly inaccurate knowledge about its environment. In addition, such an agent may receive erroneous information, perhaps in being misinformed about the truth of some formula. In this paper we present a general approach to reasoning about action and belief change in such a setting. An agent may carry out actions, but in some cases may inadvertently execute the wrong one (for example, pushing an unintended button). As well, an agent may sense whether a condition holds, and may revise its beliefs after being told that a formula is true. Our approach is based on an epistemic extension to basic action theories expressed in the situation calculus, augmented by a plausibility relation over situations. This plausibility relation can be thought of as characterising the agent’s overall belief state; as such it keeps track of not just the formulas that the agent believes to hold, but also the plausibility of formulas that it does not believe to hold. The agent’s belief state is updated by suitably modifying the plausibility relation following the execution of an action. We show that our account generalises previous approaches, and fully handles belief revision, sensing, and erroneous actions.

AIJ Journal 2012 Journal Article

Parallel belief revision: Revising by sets of formulas

• James Delgrande
• Yi Jin

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 { α, β } from the set { α ∧ β }. 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.

KR Conference 2010 Conference Paper

Horn Clause Contraction Functions: Belief Set and Belief Base Approaches

• James Delgrande
• Renata Wassermann

Standard approachs to belief change assume that the underlying logic contains classical propositional logic. Recently there has been interest in investigating approaches to belief change, specifically contraction, in which the underlying logic is not as expressive as full propositional logic. In this paper we consider approaches to belief contraction in Horn knowledge bases. We develop two broad approaches for Horn contraction, corresponding to the two major approaches in belief change, based on Horn belief sets and Horn belief bases. We argue that previous approaches, which have taken Horn remainder sets as a starting point, have undesirable properties, and moreover that not all desirable Horn contraction functions are captured by these approaches. This is shown in part by examining model-theoretic considerations involving Horn contraction. For Horn belief set contraction, we develop an account based in terms of weak remainder sets. Maxichoice and partial meet Horn contraction is specified, along with a consideration of package contraction. Following this we consider Horn belief base contraction, in which the underlying knowledge base is not necessarily closed under the Horn consequence relation. Again, approaches to maxichoice and partial meet belief set contraction are developed. In all cases, constructions of the specific operators and sets of postulates are provided, and representation results are obtained. As well, we show that problems arising with earlier work are resolved by these approaches.

KR Conference 2008 Conference Paper

Belief Revision of Logic Programs under Answer Set Semantics

• James Delgrande
• Torsten Schaub
• Hans Tompits
• Stefan Woltran

We address the problem of belief revision in (nonmonotonic) logic programming under answer set semantics: given logic programs P and Q, the goal is to determine a program R that corresponds to the revision of P by Q, denoted P * Q. Unlike previous approaches in logic programming, our formal techniques are analogous to those of distance-based belief revision in propositional logic. In developing our results, we build upon the model theory of logic programs furnished by SE models. Since SE models provide a formal, monotonic characterisation of logic programs, we can adapt well-known techniques from the area of belief revision to revision in logic programs We investigate two specific operators: (logic program) expansion and a revision operator based on the distance between the SE models of logic programs. It proves to be the case that expansion is an interesting operator in its own right, unlike in classical AGM-style belief revision where it is relatively uninteresting. Expansion and revision are shown to satisfy a suite of interesting properties; in particular, our revision operators satisfy the majority of the AGM postulates for revision. A complexity analysis reveals that our revision operators do not increase the complexity of the base formalism. As a consequence, we present an encoding for computing the revision of a logic program by another, within the same logic programming framework.

AAAI Conference 2008 Conference Paper

Parallel Belief Revision

• James Delgrande

A recalcitrant 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. As noted by various researchers, this phenomenon is made explicit in the second postulate (C2) of the well-known Darwiche-Pearl framework, and so this postulate has been a point of criticism of this and related approaches. In contrast, we argue that the true culprit of this problem arises from a basic assumption of the AGM framework, that new information is represented by a single formula. We propose a more general framework for belief revision (called parallel belief revision) in which individual items of new information are represented by a set of formulas. In this framework, if one revises by a set of formulas, and then by the negation of some members of this set, then other members of the set are still believed after the revision. Hence the aforecited problem is discharged. We present first a basic approach to parallel belief revision, and next an approach that combines the basic approach with that of Jin and Thielscher. Postulates and semantic conditions characterizing these approaches are given, and representation results provided.

KR Conference 2006 Conference Paper

Iterated revision as prioritized merging

• James Delgrande
• Didier Dubois
• Jerome Lang

Standard accounts of iterated belief revision assume a static world, about which an agent receives a sequence of observations. More recent items are assumed to have priority over less recent items. We argue that there is no reason, given a static world, for giving priority to more recent items. Instead we suggest that a sequence of observations should be merged with the agent's beliefs. Since observations may have differing reliability, arguably the appropriate belief change operator is prioritized merging. We develop this view here, suggesting postulates for prioritized merging, and examining existing merging operators with respect to these postulates. As well, we examine other suggested postulates for iterated revision, to determine how well they fit with the prioritized merging interpretation. All postulates for iterated revision that we examine, except for Darwiche and Pearl's controversial C2, are consequences of our suggested postulates for prioritized merging.

KR Conference 2004 Conference Paper

Domain-Specific Preferences for Causal Reasoning and Planning

• James Delgrande
• Torsten Schaub
• Hans Tompits

We address the issue of incorporating domain-specific preferences in planning systems, where a preference may be seen as a soft constraint that it is desirable, but not necessary, to satisfy. To this end, we identify two types of preferences, choice preferences that give a preference over which formulas (typically subgoals) to establish, and temporal preferences, which specify a desirable ordering on the establishment of formulas. Preferences may be constructed from actions or fluents but, as we show, this distinction is immaterial. In fact, we allow preferences on arbitrary formulas build from action and fluent names. These preference orderings induce preference ordering on resulting plans, the maximal elements of which yield the preferred plans. We argue that the approach is general and flexible; as well, it handles conditional preferences. Our framework is developed in the context of transition systems; hence, it is applicable to a large number of different action languages, including the well-known language C. Furthermore, our results are applicable to general planning formalisms.

AIJ Journal 2001 Journal Article

A comparison of point-based approaches to qualitative temporal reasoning

• James Delgrande
• Arvind Gupta
• Tim Van Allen

We address the problem of implementing general, qualitative, point-based temporal reasoning. Given a database of assertions concerning relative occurrences of points in time, we are interested in various operations on this database, including compiling the assertions into a representation that supports efficient reasoning, determining whether a database is consistent, and computing the strongest entailed relation between two points. We begin by specifying a set of operations and their corresponding algorithms, applicable to general point-based temporal domains. We next consider a special-purpose reasoner, based on series-parallel graphs, which performs very well in a temporal domain with a particular restricted structure. We discuss the notion of a metagraph, which encapsulates local structure inside metaedges and uses special purpose algorithms within such local structures, to obtain a fast general point-based reasoner. That is, specifically, we use a very fast, series-parallel graph reasoner to speed up general point-based reasoning. We also analyse the TimeGraph reasoner of Gerevini and Schubert. For purposes of comparison, we have implemented four approaches: a generic point-based reasoner, the generic point-based reasoner with a ranking heuristic, a reasoner based on series-parallel graphs, and a version of Gerevini and Schubert's TimeGraph reasoner. We compare these different approaches, as well as the original TimeGraph-II reasoner of Gerevini and Schubert, on different data sets. We conclude that the series-parallel graph reasoner provides the best overall performance: our results show that it dominated on domains exhibiting structure, and it degraded gracefully when conditions were less than ideal, in that it did worse than the generic approach by only a constant factor in this case.