×

Conflict generalisation in ASP: learning correct and effective non-ground constraints. (English) Zbl 1468.68174

Summary: Generalising and re-using knowledge learned while solving one problem instance has been neglected by state-of-the-art answer set solvers. We suggest a new approach that generalises learned nogoods for re-use to speed-up the solving of future problem instances. Our solution combines well-known ASP solving techniques with deductive logic-based machine learning. Solving performance can be improved by adding learned non-ground constraints to the original program. We demonstrate the effects of our method by means of realistic examples, showing that our approach requires low computational cost to learn constraints that yield significant performance benefits in our test cases. These benefits can be seen with ground-and-solve systems as well as lazy-grounding systems. However, ground-and-solve systems suffer from additional grounding overheads, induced by the additional constraints in some cases. By means of conflict minimization, non-minimal learned constraints can be reduced. This can result in significant reductions of grounding and solving efforts, as our experiments show.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68N17 Logic programming
68T30 Knowledge representation

Software:

DLV2; Clingo
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alviano, M., Calimeri, F., Dodaro, C., Fuscà, D., Leone, N., Perri, S., Ricca, F., Veltri, P., and Zangari, J.2017. The ASP system DLV2. In LPNMR. LNCS, vol. 10377. Springer, 215-221. · Zbl 1472.68178
[2] Bogaerts, B. and Weinzierl, A.2018. Exploiting justifications for lazy grounding of answer set programs. In IJCAI. ijcai.org, 1737-1745.
[3] Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Maratea, M., Ricca, F., and Schaub, T.2020. ASP-Core-2 input language format. Theory Pract. Log. Program. 20,2, 294-309. · Zbl 1472.68180
[4] Dejong, G. and Mooney, R. J.1986. Explanation-based learning: An alternative view. Mach. Learn. 1, 2, 145-176.
[5] Faber, W., Pfeifer, G., and Leone, N.2011. Semantics and complexity of recursive aggregates in answer set programming. Artif. Intell. 175, 1, 278-298. · Zbl 1216.68263
[6] Friedrich, G., Ryabokon, A., Falkner, A. A., Haselböck, A., Schenner, G., and Schreiner, H.2011. (Re)configuration using answer set programming. In Configuration Workshop. CEUR-WS.org.
[7] Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T.2014. Clingo = ASP + control: Preliminary report. CoRR abs/1405.3694. · Zbl 1486.68027
[8] Gebser, M., Kaufmann, B., and Schaub, T.2012. Conflict-driven answer set solving: From theory to practice. Artif. Intell. 187, 52-89. · Zbl 1251.68060
[9] Gebser, M., Maratea, M., and Ricca, F.2020. The seventh answer set programming competition: Design and results. Theory Pract. Log. Program. 20,2, 176-204. · Zbl 1472.68026
[10] Van Harmelen, F. and Bundy, A.1988. Explanation-based generalisation = partial evaluation. Artif. Intell. 36, 3, 401-412. · Zbl 0655.68106
[11] Hirsh, H.1987. Explanation-based generalization in a logic-programming environment. In IJCAI. Morgan Kaufmann, 221-227.
[12] Leutgeb, L. and Weinzierl, A.2017. Techniques for efficient lazy-grounding ASP solving. In DECLARE. LNCS, vol. 10997. Springer, 132-148.
[13] Lintao, Zhang, Madigan, C. F., Moskewicz, M. H., and Malik, S.2001. Efficient conflict driven learning in a boolean satisfiability solver. In ICCAD. IEEE, 279-285.
[14] Mitchell, T. M.1997. Machine learning, International Edition. McGraw-Hill Series inComputer Science. McGraw-Hill.
[15] Mitchell, T. M., Keller, R. M., and Kedar-Cabelli, S. T.1986. Explanation-based generalization: A unifying view. Mach. Learn. 1, 1, 47-80.
[16] Redl, C.2016. Automated benchmarking of KR-systems. In RCRA@AI*IA. CEUR Workshop Proceedings, vol. 1745. CEUR-WS.org, 45-56.
[17] Russell, S. J. and Norvig, P.2010. Artificial Intelligence - A Modern Approach, Third International Edition. Pearson Education. · Zbl 0835.68093
[18] Ryabokon, A.2015. Knowledge-based (re)configuration of complex products and services. Ph.D. thesis, Alpen-Adria-Universität Klagenfurt.
[19] Shepherdson, J. C.1984. Negation as failure: A comparison of clark’s completed data base and reiter’s closed world assumption. J. Log. Program. 1, 1, 51-79. · Zbl 0575.68094
[20] Silva, J. P. M., Lynce, I., and Malik, S.2009. Conflict-driven clause learning SAT solvers. In Handbook of Satisfiability. IOS Press, 131-153.
[21] Taupe, R., Weinzierl, A., and Friedrich, G.2019. Degrees of laziness in grounding – effects of lazy-grounding strategies on ASP solving. In LPNMR. LNCS, vol. 11481. Springer, 298-311. · Zbl 1522.68115
[22] Weinzierl, A.2013. Learning non-ground rules for answer-set solving. In 2nd Workshop on Grounding and Transformations for Theories With Variables. 25-37.
[23] Weinzierl, A.2017. Blending lazy-grounding and CDNL search for answer-set solving. In LPNMR. LNCS, vol. 10377. Springer, 191-204. · Zbl 1491.68262
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.