1 Introduction
Probability answer set programming [Saad and Pontelli2006, Saad2006, Saad2007a] is a declarative programming framework which aims to solve hard search problems in probability environments, and shown effective for probability knowledge representation and probability reasoning applications. It has been shown that many interesting probability reasoning problems are represented and solved by probability answer set programming, where probability answer sets describe the set of possible solutions to the problem. These probability reasoning problems include, but not limited to, reasoning about actions with probability effects and probability planning [Saad2007b]
, reinforcement learning in MDP environments
[Saad2008a], reinforcement learning in POMDP environments [Saad2011], contingent probability planning [Saad2009], and Bayesian reasoning [Saad2008b]. However, the unavailability of probability aggregates, e.g. expected values, in the language of probability answer set programming [Saad and Pontelli2006, Saad2006, Saad2007a] disallows the natural and concise representation of many interesting problems. This requires probability answer set programs to be capable of representing and reasoning in the presence of probability aggregates. The following stochastic dietary problem illuminates the need for probability aggregates.Example 1
Suppose we have three kinds of food: beef, fish, and turkey, where the amounts of vitamins of , , and per unit of each of these food are uncertain. Two scenarios are available for each amount of units of vitamins for each unit of food. The amounts of units of vitamins , , and per unit of beef are believed to be with probability and with probability. Per unit of fish, the amounts of units of vitamins are believed to be with probability and with probability. Per unit of turkey, the amounts of units of vitamins are believed to be with probability and with probability.
Assume each kind of food is available in packages of or units, presented by the predicate , where is a food, is the number of units of the food , and is the scenario in which the package is selected. We use to represent a unit of food has units of vitamin with probability in a scenario . The minimum daily requirement of vitamins , , and is , , and units, respectively.
The target is to find combinations of units of food that meet the minimum daily requirement of each vitamin. This requires finding the expected value of units of vitamins for each vitamin collected from each available food in every possible scenario, and compare this expected value with the minimum daily requirement of each vitamin.
This probability optimization problem can be represented by a disjunctive hybrid probability logic program with probability answer set semantics, DHPP [Saad2007a]. DHPP is an expressive probability answer set programming framework [Saad and Pontelli2006, Saad2006, Saad2007a] that allows disjunctions in the head of rules. We assume that atoms appearing without annotations, in DHPP programs, are associated with the annotation , and annotated atoms of the form are simply represented as . The DHPP program representation, , of the stochastic dietary problem, is given as follows, where is any arbitrary assignment of disjunctive pstrategies and contains rules of the form:
The last three rules in the above DHPP program representation of the stochastic dietary problem guarantee that only probability answer sets with sufficient supply of vitamins are generated.
The DHPP representation of the stochastic dietary problem described in Example (1) is fairly intuitive but rather complex, since the rules that represent the expected value of units of vitamins for each vitamin via the predicate , where is the expected value of units of vitamins for vitamin , contains complex summation that involves variables. Furthermore, this representation strategy is not feasible in general, especially, in the presence of multiple scenarios for each amount of units of vitamin per unit of food, multiple numbers of vitamins, and multiple types of food, which consequently will lead to very complex rules with very complex summations.
Therefore, we propose to extend the language of DHPP with probability aggregates to allow intuitive and concise representation and reasoning about realworld applications. To the best of our knowledge, this development is the first that defines semantics for probability aggregates in a probability answer set programming framework. DHPP is expressive form of probability answer set programming [Saad and Pontelli2006, Saad2006, Saad2007a] that allows disjunctions in the head of rules. It has been shown that; DHPP is capable of representing and reasoning with both probability uncertainty and qualitative uncertainty [Saad2007a]; it is a natural extension to the classical disjunctive logic programs, DLP, and its probability answer set semantics generalizes the classical answer set semantics of DLP [Saad2007a]; DHPP with probability answer set semantics generalizes the probability answer set programming framework of [Saad and Pontelli2006], which are DHPP programs with an atom appearing in the heads of rules. Moreover, it has been shown that DHPP is used in realworld applications in which quantitative probability uncertainly need to be defined over the possible outcomes of qualitative uncertainty [Saad2007a].
There were many proposals for defining semantics for classical aggregates in classical answer set programming [Faber et al.2010, Niemela and Simons2000, Pelov et al.2007, Pelov and Truszczynski2004, Ferraris and Lifschitz2005, Ferraris and Lifschitz2010, Pelov2004]. Among these proposals, [Faber et al.2010] is the most general intuitive semantics for classical aggregates in DLP. In [Faber et al.2010], declarative classical answer semantics for classical disjunctive logic program with arbitrary classical aggregates, denoted by DLP, including monotone, antimonotone, and nonmonotone aggregates, was provided. The proposed classical answer set semantics of DLP generalizes the classical answer set semantics of aggregatefree DLP. Moreover, classical answer sets of DLP are subsetminimal [Faber et al.2010], a vital property for nonmonotonic reasoning framework semantics.
The contributions of this paper are the following. We extend the original language of DHPP to allow any arbitrary probability annotation function including monotone, antimonotone, and nonmonotone annotation functions. We define the notions of probability aggregates and probability aggregate atoms in DHPP. We present two types of probability aggregates; the first type computes the expected value of a classical aggregate, e.g., the expected value of the minimum, the second type computes the probability of a classical aggregate, e.g, the probability of sum of values. In addition, we define the probability answer set semantics of DHPP with arbitrary probability aggregates, denoted by DHPP, including monotone, antimonotone, and nonmonotone probability aggregates. We show that the proposed probability answer set semantics of DHPP subsumes both the original probability answer set semantics of DHPP [Saad2007a] and the classical answer set semantics of DLP [Faber et al.2010], and consequently subsumes the classical answer set semantics of DLP [Gelfond and Lifschitz1991]. We show that the probability answer sets of DHPP are minimal probability models and hence incomparable, which is an important property for nonmonotonic probability reasoning.
2 Dhpp : Probability Aggregates Disjunctive Hybrid Probability Logic Programs
In this section we introduce the basic language of DHPP, the notions of probability aggregates and probability aggregate atoms, and the syntax of DHPP programs.
2.1 The Basic Language of DHPP
Let denotes an arbitrary firstorder language with finitely many predicate symbols, function symbols, constants, and infinitely many variables. A term is a constant, a variable or a function. An atom, , is a predicate in , where is the Herbrand base of . The Herbrand universe of is denoted by . Nonmonotonic negation or the negation as failure is denoted by . In probability aggregates disjunctive hybrid probability logic programs, DHPP, probabilities are assigned to primitive events (atoms) and compound events (conjunctions or disjunctions of atoms) as intervals in , where denotes the set of all closed intervals in . For , the truth order on is defined as iff and .
The type of dependency among the primitive events within a compound event is described by a probability strategy, which can be a conjunctive pstrategy or a disjunctive pstrategy. Conjunctive (disjunctive) pstrategies are used to combine events belonging to a conjunctive (disjunctive) formula [Saad and Pontelli2006]. The probability composition function, , of a probability strategy (pstrategy), , is a mapping , where the probability composition function, , computes the probability interval of a conjunction (disjunction) of two events from the probability of its components. Let be a multiset of probability intervals. For convenience, we use to denote .
A probability annotation is a probability interval of the form , where are called probability annotation items. A probability annotation item is either a constant in (called probability annotation constant), a variable ranging over (called probability annotation variable), or (called probability annotation function), where is a representation of a monotone, antimonotone, or nonmonotone total or partial function and are probability annotation items.
Let be an arbitrary set of pstrategies, where () is the set of all conjunctive (disjunctive) pstrategies in . A hybrid basic formula is an expression of the form or , where are atoms and and are pstrategies. Let be the set of all ground hybrid basic formulae formed using distinct atoms from and pstrategies from . If is a hybrid basic formula and is a probability annotation then is called a probability annotated hybrid basic formula.
2.2 Probability Aggregate Atoms
A symbolic probability set is an expression of the form , where is a variable or a function term and , are probability annotation variables or probability annotation functions, and is a conjunction of probability annotated hybrid basic formulae. A ground probability set is a set of pairs of the form such that is a constant term and are probability annotation constants, and is a ground conjunction of probability annotated hybrid basic formulae. A symbolic probability set or ground probability set is called a probability set term. Let be a probability aggregate function symbol and be a probability set term, then is said a probability aggregate, where , , , , , , , , , , . If is a probability aggregate and is an interval , called guard, where are constants, variables or functions terms, then we say is a probability aggregate atom, where .
Example 2
The following examples are representation for probability aggregate atoms.
Definition (1) below specifies that every probability aggregate function has its own set of local variables.
Definition 1
Let be a probability aggregate. A variable, , is a local variable to if and only if appears in and does not appear in the DHPP rule that contains .
For example, for the first probability aggregate atom in Example (2), the variables , , and are local variables to the probability aggregate .
Definition 2
A global variable is a variable that is not a local variable.
2.3 Dhpp Program Syntax
A DHPP rule is an expression of the form
where are atoms, are hybrid basic formulae or probability aggregate atoms, and are probability annotations.
A DHPP rule says that if for each , where , it is believable that the probability interval of is at least w.r.t. and for each , where , it is not believable that the probability interval of is at least w.r.t. , then there exists at least , where , such that the probability interval of is at least .
Definition 3
A DHPP program over a set of arbitrary pstrategies, , is a pair , where is a set of DHPP rules with pstrategies from , and is a mapping .
The mapping in the DHPP program definition associates to each atom, , a disjunctive pstrategy that is used to combine the probability intervals obtained from different DHPP rules with appearing in their heads. For the simplicity of the presentation, hybrid basic formulae that appearing in DHPP programs without probability annotations are assumed to be associated with the probability annotation . Nevertheless, probability annotated hybrid basic formulae of the form are simply represented as .
Example 3
The stochastic dietary problem described in Example (1) can be concisely and intuitively represented as DHPP program, , where is any arbitrary assignments of disjunctive pstrategies and consists of the following DHPP rules in addition to the facts represented by and described in Example (1).
where the expected value is computed by the probability aggregate . The last three DHPP rules of the DHPP program representation of the stochastic dietary problem described above guarantee that only probability answer sets that involve sufficient daily supply of each vitamin are generated.
Definition 4
The ground instantiation of a symbolic probability set
is the set of all ground pairs of the form , where is a substitution of every local variable appearing in to a constant from .
Definition 5
A ground instantiation of a DHPP rule, , is the replacement of each global variable appearing in to a constant from , then followed by the ground instantiation of every symbolic probability set, , appearing in .
The ground instantiation of a DHPP program, , is the set of all possible ground instantiations of every DHPP rule in .
Example 4
The ground instantiation of the DHPP rule
with respect to the DHPP program, , in Example (3), is given by:
3 Probability Aggregates Semantics
We present two types of probability aggregates. The first type computes the expected value of a classical aggregate, e.g., the expected value of the minimum, denoted by , , , , , , where
returns the expected value of a random variable and
, , , , return the expected value of the the classical aggregates , , , , respectively. The second type of probability aggregates computes the probability of a classical aggregate, e.g, the probability of sum of values, denoted by , , , , , where , , , , return the probability of the the classical aggregates , , , , respectively. Any probability aggregate is applied to a probability set that represents a random variable with all its possible values and their associated provability intervals.3.1 Probability Aggregates Mappings
Let be a set of objects. Then, we use to denote the set of all multisets over elements in . Let denotes the set of all real numbers and denotes the set of all natural numbers, and denotes the Herbrand universe. Let be a symbol that does not occur in . Therefore,

The mappings for the expected value probability aggregates are:

.

.

.

.

.


The mappings for the probability value probability aggregates are:

.

.

.

.

The application of and on the empty multiset return and respectively. The application of and on the empty multiset returns . The application of and on the empty multiset return and respectively. The application of on the empty multiset returns . However, the application of , , , on the empty multiset is undefined.
Definition 6
3.2 Semantics of Probability Aggregates
The semantics of probability aggregates is defined with respect to a pinterpretation, which is in turn a representation of probability sets. A probability annotated hybrid basic formula, , is true (satisfied) with respect to a pinterpretation, , if and only if . The negation of a probability annotated hybrid basic formula, , is true (satisfied) with respect to if and only if . The evaluation of a probability aggregate, and hence the truth valuation of a probability aggregate atom, are established with respect to a given pinterpretation, , as described by the following definitions.
Definition 7
Let be a ground probability aggregate and be a pinterpretation. Then, we define to be the multiset constructed from elements in the ground , where is true w.r.t. .
Definition 8
Let be a ground probability aggregate and be a pinterpretation. Then, the evaluation of with respect to is, , the result of the application of to , where if is not in the domain of and
where .
4 Dhpp Probability Answer Set Semantics
In this section we define the satisfaction, probability models, and the probability answer set semantics of probability aggregates disjunctive hybrid probability logic programs, DHPP.
Let be a DHPP rule and
and . We consider that probability annotated probability aggregate atoms that involve probability aggregates from , , , , , are associated to the probability annotation .
Definition 9
Let be a ground DHPP program, be a DHPP rule in , be a pinterpretation for , , , , , , , and , , , , . Then,

satisfies in iff .

satisfies in iff and .

satisfies in iff or and .

satisfies in iff and and .

satisfies in iff or and or .

satisfies in iff .

satisfies in iff .

satisfies iff satisfies and satisfies .

satisfies iff such that satisfies .

satisfies iff satisfies whenever satisfies or does not satisfy .

satisfies iff satisfies every DHPP rule in and

such that satisfies and satisfies
in the . 
such that are atoms in and
is hybrid basic formula in and .

Example 5
Let be a DHPP program, where is any arbitrary assignments of disjunctive pstrategies and consists of the DHPP rules:
The ground instantiation of is given by:
Let be a pinterpretation for that assigns to , to
Comments
There are no comments yet.