ASP and subset minimality: enumeration, cautious reasoning and MUSes. (English) Zbl 07702961
Summary: 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.
MSC:
| 68Txx | Artificial intelligence |
References:
| [1] | Alviano, M., Model enumeration in propositional circumscription via unsatisfiable core analysis, Theory Pract. Log. Program., 17, 708-725 (2017) · Zbl 1422.68217 |
| [2] | Alviano, M., Algorithms for solving optimization problems in answer set programming, Intell. Artif., 12, 1-14 (2018) |
| [3] | Alviano, M., Query answering in propositional circumscription, (Lang, J., Proc. of IJCAI (2018), ijcai.org), 1669-1675 |
| [4] | Alviano, M., Argumentation reasoning via circumscription with pyglaf, Fundam. Inform., 167, 1-30 (2019) · Zbl 1415.68214 |
| [5] | Alviano, M.; Dodaro, C., Model enumeration via assumption literals, Fundam. Inform., 167, 31-58 (2019) · Zbl 1415.68222 |
| [6] | Alviano, M.; Dodaro, C.; Fiorentino, S.; Previti, A.; Ricca, F., Enumeration of minimal models and muses in WASP, (Proceedings of LPNMR (2022), Springer), 29-42 · Zbl 07671876 |
| [7] | Alviano, M.; Dodaro, C.; Järvisalo, M.; Maratea, M.; Previti, A., Cautious reasoning in ASP via minimal models and unsatisfiable cores, Theory Pract. Log. Program., 18, 319-336 (2018) · Zbl 1451.68267 |
| [8] | Alviano, M.; Dodaro, C.; Leone, N.; Ricca, F., Advances in WASP, (Proc. of LPNMR (2015), Springer), 40-54 · Zbl 1467.68021 |
| [9] | Alviano, M.; Dodaro, C.; Ricca, F., Anytime computation of cautious consequences in answer set programming, Theory Pract. Log. Program., 14, 755-770 (2014) · Zbl 1307.68012 |
| [10] | Alviano, M.; Dodaro, C.; Ricca, F., A maxsat algorithm using cardinality constraints of bounded size, (Proc. of IJCAI (2015), AAAI Press), 2677-2683 |
| [11] | Amendola, G.; Dodaro, C.; Faber, W.; Ricca, F., Paracoherent answer set computation, Artif. Intell., 299, Article 103519 pp. (2021) · Zbl 1520.68180 |
| [12] | Amendola, G.; Dodaro, C.; Maratea, M., Abstract solvers for computing cautious consequences of ASP programs, Theory Pract. Log. Program., 19, 740-756 (2019) · Zbl 1434.68066 |
| [13] | Amendola, G.; Eiter, T.; Fink, M.; Leone, N.; Moura, J., Semi-equilibrium models for paracoherent answer set programs, Artif. Intell., 234, 219-271 (2016) · Zbl 1351.68259 |
| [14] | Arenas, M.; Bertossi, L. E.; Chomicki, J., Answer sets for consistent query answering in inconsistent databases, Theory Pract. Log. Program., 3, 393-424 (2003) · Zbl 1079.68026 |
| [15] | Bailey, J.; Stuckey, P. J., Discovery of minimal unsatisfiable subsets of constraints using hitting set dualization, (Proc. of PADL (2005), Springer), 174-186 |
| [16] | Balduccini, M.; Gelfond, M.; Watson, R.; Nogueira, M., The usa-advisor: a case study in answer set planning, (Eiter, T.; Faber, W.; Truszczynski, M., Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001, Proceedings (2001), Springer), 439-442 · Zbl 1010.68800 |
| [17] | Baral, C., Knowledge Representation, Reasoning and Declarative Problem Solving (2003), Cambridge University Press: Cambridge University Press URL · Zbl 1056.68139 |
| [18] | Barbara, V.; Buelli, D.; Guarascio, M.; Ierace, S.; Iiritano, S.; Laboccetta, G.; Leone, N.; Manco, G.; Pesenti, V.; Quarta, A.; Ricca, F.; Ritacco, E., A loosely-coupled neural-symbolic approach to compliance of electric panels, (Calegari, R.; Ciatto, G.; Omicini, A., Proceedings of the 37th Italian Conference on Computational Logic. Proceedings of the 37th Italian Conference on Computational Logic, Bologna, Italy, June 29 - July 1, 2022 (2022), CEUR-WS.org), 247-253 |
| [19] | Bauer, K.; Hinz, O.; van der Aalst, W. M.P.; Weinhardt, C., Expl(ai)n it to me - explainable AI and information systems research, Bus. Inf. Syst. Eng., 63, 79-82 (2021) |
| [20] | Belov, A.; Marques-Silva, J., Muser2: an efficient MUS extractor, J. Satisf. Boolean Model. Comput., 8, 123-128 (2012) · Zbl 1322.68178 |
| [21] | Bistarelli, S.; Rossi, F.; Santini, F., Conarglib: an argumentation library with support to search strategies and parallel search, J. Exp. Theor. Artif. Intell., 33, 891-918 (2021) |
| [22] | Brewka, G.; Delgrande, J. P.; Romero, J.; Schaub, T., asprin: customizing answer set preferences without a headache, (Proc. of AAAI (2015), AAAI Press), 1467-1474 |
| [23] | Brewka, G.; Eiter, T.; Truszczynski, M., Answer set programming at a glance, Commun. ACM, 54, 92-103 (2011) |
| [24] | Brewka, G.; Thimm, M.; Ulbricht, M., Strong inconsistency, Artif. Intell., 267, 78-117 (2019) · Zbl 1478.68362 |
| [25] | Bry, F.; Yahya, A. H., Positive unit hyperresolution tableaux and their application to minimal model generation, J. Autom. Reason., 25, 35-82 (2000) · Zbl 0960.03006 |
| [26] | Di Rosa, E.; Giunchiglia, E.; Maratea, M., Solving satisfiability problems with preferences, Constr. Int. J., 15, 485-515 (2010) · Zbl 1208.68199 |
| [27] | Dodaro, C.; Gasteiger, P.; Leone, N.; Musitsch, B.; Ricca, F.; Schekotihin, K., Combining answer set programming and domain heuristics for solving hard industrial problems (application paper), Theory Pract. Log. Program., 16, 653-669 (2016) · Zbl 1379.68281 |
| [28] | Dodaro, C.; Gasteiger, P.; Reale, K.; Ricca, F.; Schekotihin, K., Debugging non-ground ASP programs: technique and graphical tools, Theory Pract. Log. Program., 19, 290-316 (2019) · Zbl 1486.68025 |
| [29] | Dodaro, C.; Leone, N.; Nardi, B.; Ricca, F., Allotment problem in travel industry: a solution based on ASP, (ten Cate, B.; Mileo, A., Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Berlin, Germany, August 4-5, 2015, Proceedings (2015)), 77-92 |
| [30] | Dodaro, C.; Previti, A., Minipref: a tool for preferences in SAT (short paper), (Proc. of RCRA (2019), CEUR-WS.org) |
| [31] | Dvorák, W.; Gaggl, S. A.; Rapberger, A.; Wallner, J. P.; Woltran, S., The ASPARTIX system suite, (COMMA (2020), IOS Press), 461-462 |
| [32] | Dvorák, W.; Järvisalo, M.; Wallner, J. P.; Woltran, S., Complexity-sensitive decision procedures for abstract argumentation, Artif. Intell., 206, 53-78 (2014) · Zbl 1334.68206 |
| [33] | Erdem, E.; Gelfond, M.; Leone, N., Applications of answer set programming, AI Mag., 37, 53-68 (2016) |
| [34] | Erdem, E.; Lifschitz, V., Tight logic programs, Theory Pract. Log. Program., 3, 499-518 (2003) · Zbl 1079.68014 |
| [35] | Gaggl, S. A.; Manthey, N.; Ronca, A.; Wallner, J. P.; Woltran, S., Improved answer-set programming encodings for abstract argumentation, Theory Pract. Log. Program., 15, 434-448 (2015) · Zbl 1379.68292 |
| [36] | Gebser, M.; Kaminski, R.; Kaufmann, B.; Ostrowski, M.; Schaub, T.; Wanko, P., Theory solving made easy with clingo 5, (Proc. of ICLP (TC) (2016), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 2:1-2:15 |
| [37] | Gebser, M.; Kaufmann, B.; Neumann, A.; Schaub, T., Conflict-driven answer set enumeration, (Proc. of LPNMR (2007), Springer), 136-148 · Zbl 1149.68332 |
| [38] | Gebser, M.; Kaufmann, B.; Schaub, T., Conflict-driven answer set solving: from theory to practice, Artif. Intell., 187, 52-89 (2012) · Zbl 1251.68060 |
| [39] | Gebser, M.; Leone, N.; Maratea, M.; Perri, S.; Ricca, F.; Schaub, T., Evaluation techniques and systems for answer set programming: a survey, (Proc. of IJCAI (2018), ijcai.org), 5450-5456 |
| [40] | Gebser, M.; Pührer, J.; Schaub, T.; Tompits, H., A meta-programming technique for debugging answer-set programs, (AAAI (2008), AAAI Press), 448-453 |
| [41] | Gelfond, M.; Lifschitz, V., Classical negation in logic programs and disjunctive databases, New Gener. Comput., 9, 365-386 (1991) · Zbl 0735.68012 |
| [42] | Grasso, G.; Leone, N.; Manna, M.; Ricca, F., ASP at work: spin-off and applications of the DLV system, (Balduccini, M.; Son, T. C., Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning - Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday (2011), Springer), 432-451 |
| [43] | (van Harmelen, F.; Lifschitz, V.; Porter, B. W., Handbook of Knowledge Representation. Handbook of Knowledge Representation, Foundations of Artificial Intelligence, vol. 3 (2008), Elsevier) · Zbl 1183.68611 |
| [44] | Hasegawa, R.; Fujita, H.; Koshimura, M., Efficient minimal model generation using branching lemmas, (Proc. of CADE (2000), Springer), 184-199 · Zbl 0963.68180 |
| [45] | Ignatiev, A.; Previti, A.; Liffiton, M. H.; Marques-Silva, J., Smallest MUS extraction with minimal hitting set dualization, (Proc. of CP (2015), Springer), 173-182 |
| [46] | Janota, M.; Marques-Silva, J., On minimal corrections in ASP, (Proc. of RCRA (2017), CEUR-WS.org), 45-54 |
| [47] | Junker, U., QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems, (Proc. of AAAI (2004), AAAI Press / The MIT Press), 167-172 |
| [48] | Kaufmann, B.; Leone, N.; Perri, S.; Schaub, T., Grounding and solving in answer set programming, AI Mag., 37, 25-32 (2016) |
| [49] | Koshimura, M.; Nabeshima, H.; Fujita, H.; Hasegawa, R., Minimal model generation with respect to an atom set, (Proc. of FTP (2009), CEUR-WS.org) |
| [50] | Leone, N.; Pfeifer, G.; Faber, W.; Eiter, T.; Gottlob, G.; Perri, S.; Scarcello, F., The DLV system for knowledge representation and reasoning, ACM Trans. Comput. Log., 7, 499-562 (2006) · Zbl 1367.68308 |
| [51] | Liffiton, M. H.; Previti, A.; Malik, A.; Marques-Silva, J., Fast, flexible MUS enumeration, Constr. Int. J., 21, 223-250 (2016) · Zbl 1334.90080 |
| [52] | Liffiton, M. H.; Sakallah, K. A., Algorithms for computing minimal unsatisfiable subsets of constraints, J. Autom. Reason., 40, 1-33 (2008) · Zbl 1154.68510 |
| [53] | Lifschitz, V., Answer set planning, (Schreye, D. D., Logic Programming: The 1999 International Conference, Las Cruces, New Mexico, USA, November 29 - December 4, 1999 (1999), MIT Press), 23-37 |
| [54] | Manna, M.; Ricca, F.; Terracina, G., Taming primary key violations to query large inconsistent data via ASP, Theory Pract. Log. Program., 15, 696-710 (2015) · Zbl 1379.68114 |
| [55] | Marques-Silva, J.; Janota, M.; Mencía, C., Minimal sets on propositional formulae. problems and reductions, Artif. Intell., 252, 22-50 (2017) · Zbl 1419.68098 |
| [56] | Mencía, C.; Marques-Silva, J., Reasoning about strong inconsistency in ASP, (Proc. of SAT (2020), Springer), 332-342 · Zbl 07331031 |
| [57] | Miller, T., Explanation in artificial intelligence: insights from the social sciences, Artif. Intell., 267, 1-38 (2019) · Zbl 1478.68274 |
| [58] | Niemelä, I., A tableau calculus for minimal model reasoning, (Proc. of TABLEAUX (1996), Springer), 278-294 · Zbl 1412.68247 |
| [59] | Oetsch, J.; Pührer, J.; Tompits, H., Catching the ouroboros: on debugging non-ground answer-set programs, Theory Pract. Log. Program., 10, 513-529 (2010) · Zbl 1213.68182 |
| [60] | Pajunen, J.; Janhunen, T., Solution enumeration by optimality in answer set programming, Theory Pract. Log. Program., 21, 750-767 (2021) · Zbl 1530.68058 |
| [61] | Previti, A.; Marques-Silva, J., Partial MUS enumeration, (Proc. of AAAI (2013), AAAI Press) |
| [62] | Romero, J.; Schaub, T.; Wanko, P., Computing diverse optimal stable models, (Proc. of ICLP (Technical Communications) (2016), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 3:1-3:14 · Zbl 1428.68093 |
| [63] | Sakama, C.; Inoue, K., Paraconsistent stable semantics for extended disjunctive programs, J. Log. Comput., 5, 265-285 (1995) · Zbl 0827.68070 |
| [64] | Silva, J. P.M.; Sakallah, K. A., GRASP: a search algorithm for propositional satisfiability, IEEE Trans. Comput., 48, 506-521 (1999) · Zbl 1392.68388 |
| [65] | Simons, P.; Niemelä, I.; Soininen, T., Extending and implementing the stable model semantics, Artif. Intell., 138, 181-234 (2002) · Zbl 0995.68021 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
