Answer set programming (ASP) is a declarative language for nonmonotonic reasoning based on stable model semantics, where stable models are classical models of the input program satisfying a stability condition: only necessary information is included in each of these models under the assumptions provided by the model itself for the unknown knowledge in the program, where unknown knowledge is encoded by means of default negation. Reasoning in presence of unknown knowledge is common for rational agents acting in the real world. It is also common that real world agents cannot meet all their desiderata, and therefore ASP programs may come with soft literals for representing numerical preferences over jointly incompatible conditions. Stable models are therefore associated with a cost given by the number of the unsatis ed soft literals, so that stable models of minimum cost are preferred. Algorithms and strategies for computing optimal stable models are reported in this paper, together with a brief discussion of their properties. Finally, the paper hints on how these algorithms can be extended to handle some qualitative preferences.
Answer set programming (ASP) is a declarative language for nonmonotonic
reasoning based on stable model semantics [1{5], and implemented by very e cient
systems [6{8]. A stable models is a classical model of the input program that
satis es an additional condition, referred as stability condition. Speci cally, a logic
program may refer to unknown knowledge via default negation, whose
interpretation is then xed by the stable model candidate; stated di erently, the stable
model candidate provides an assumption on the truth or falsity of relevant
unknown knowledge. On this new logic program, often referred in the literature as
program reduct, the stability condition requires that only necessary information is
included in the stable model candidate, which therefore must be subset-minimal
for the program reduct in order to be a stable model of the original program.
Such an intuitive notion of stable model easily extends to expressive language
constructs, among them aggregation functions [
Several real world applications take advantage of ASP for fast prototyping
and e cient evaluation. For example, USA-Advisor [
Reasoning in presence of unknown knowledge is common for rational agents
acting in the real world. It is also common that real world agents cannot meet
all their desiderata, and therefore ASP programs may come with soft literals for
representing numerical preferences over jointly incompatible conditions. Stable
models are therefore associated with a cost given by the number of the unsatis ed
soft literals, so that stable models of minimum cost are preferred. In fact, any
stable model describes a plausible scenario for the knowledge represented in the
input program, even if it may be only an admissible solution of non optimum cost.
In fact, many rational agents would still accept suboptimal solutions, possibly
with an estimate on the maximum distance to the optimum cost. This exibility
is also justi ed by the intrinsic complexity of the problem: the computation of
an optimum stable model requires in general at least linearly many calls to a 2P
oracle [
Taking into account such a high computational complexity, a good algorithm
for answer set optimization should produce better and better stable models
during the computation of an optimum stable model. Algorithms having this
property are called anytime in the literature [
Finally, it turns out that unsatis able core analysis can be e ciently used also
for the enumeration of models of circumscribed theories [
This research has been partially supported by the Italian Ministry for Economic Development (MISE) under project \PIUCultura { Paradigmi Innovativi per l'Utilizzo della Cultura" (n. F/020016/01-02/X27), and under project \Smarter Solutions in the Big Data World (S2BDW)" (n. F/050389/01-03/X32) funded within the call \HORIZON2020" PON I&C 2014-2020, and by Gruppo Nazionale per il Calcolo Scienti co (GNCS-INdAM).