Answer Set Programming (ASP) is a well-known logic-based formalism that has been used to model and solve a variety of AI problems. For several years, ASP implementations primarily focused on the main computational task: the computation of one answer set of a (logic) program. Nonetheless, several AI problems, that can be conveniently modelled in ASP, require to enumerate solutions characterized by an optimality property that can be expressed in terms of subset-minimality with respect to some objective atoms. In this context, solutions are often either (i) answer sets that are subset-minimal w.r.t. the objective atoms or (ii) atoms that are contained in all subset-minimal answer sets, or (iii) sets of atoms that enforce the absence of answer sets on the ASP program at hand — such sets are referred to as minimal unsatisfiable subsets (MUSes). In all the above-mentioned cases, the corresponding computational task is currently not supported by plain state-of-the-art ASP solvers. In this paper, we study formally these tasks and fill the gap in current implementations by proposing several algorithms to enumerate MUSes and subset-minimal answer sets, as well as perform cautious reasoning on subset-minimal answer sets. We implement our algorithms on top of WASP and perform an experimental analysis on several hard benchmarks showing the good performance of our implementation.
File in questo prodotto:
Non ci sono file associati a questo prodotto.