Answer Set Programming - Reasoning Web - page 173

r 5 : ← inPath ( X,Y, ) ,inPath ( X 1 ,Y, ) ,X<>X 1 .

r 6 : ← node ( X ) , not reached ( X ) .

r 7 : ← start ( X ) , not inPath ( Y,X ) .

r 8 : inPath ( X,Y,C )[ C, 1] .

The only differences with respect to the Hamiltonian Path program of Section 4 are the
constraint r 7 , which ensures cyclicity of the path, and the weak constraint r 8 ,which
states the preference to avoid taking arcs with high cost in the path, and has the effect of
selecting those answer sets for which the total cost of arcs selected by inPath (which
coincides with the length of the path) is the minimum (i.e., the path is the shortest) .
The TSP encoding provided above is an example of the “guess, check and optimize”
programming pattern [42], which extends the original “guess and check” (see Section
4) by adding an additional “optimization part” which mainly contains weak constraints.
In the example above, the optimization part contains only the weak constraint r 8 .
Optimize Statements are syntactically somewhat simpler. They assign numeric values
to a set of ground literals, and thereby select those answer sets for which the sum of the
values assigned to literals which are true in the respective answer sets are maximal or
minimal. It is not hard to see that Weak Constraints can emulate Optimize Statements,
but not vice versa.

Aggregates and External Atoms. There are some simple properties, often arising in real-
world applications, which cannot be encoded in a simple and natural manner using ASP.
Especially properties that require the use of arithmetic operators on a set of elements
satisfying some conditions (like sum, count, or maximum) require rather cumbersome
encodings (often requiring an “external” ordering relation over terms), if one is con-
fined to classic ASP. On an abstract level, this can be viewed like having an “external
atom,” which use some external evaluator to determine truth or falsity. The best-known
type of programs with such external atoms are HEX programs, which evolved from dl-
programs that use description logics as external evaluators [44]. In the following, we
will stick with the more traditional numeric aggregates for simplicity.
Similar observations have also been made in related domains, notably database sys-
tems, which led to the definition of aggregate functions. Especially in database systems
this concept is by now both theoretically and practically fully integrated. When ASP
systems became used in real applications, it became apparent that aggregates are needed
also here. First, cardinality and weight constraints [43], which are special cases of ag-
gregates, have been introduced. However, in general one might want to use also other
aggregates (like minimum, maximum, or average), and it is not clear how to generalize
the framework of cardinality and weight constraints to allow for arbitrary aggregates. To
overcome this deficiency, ASP has been extended with special atoms handling aggre-
gate functions [45,46,47,48,38,49,50]. Intuitively, an aggregate function can be thought
of as a (possibly partial) function mapping multisets of constants to a constant.
An aggregate function is of the form f ( S ),where S is a set term of the form

{ Vars :

Conj ,where Vars is a list of variables and Conj is a conjunction of standard atoms,

and f is an aggregate function symbol .
The most common aggregate functions compute the number of terms, the sum of
non-negative integers, and minimum/maximum term in a set.

}