×

The external interface for extending WASP. (English) Zbl 1472.68183

Summary: Answer set programming (ASP) is a successful declarative formalism for knowledge representation and reasoning. The evaluation of ASP programs is nowadays based on the conflict-driven clause learning (CDCL) backtracking search algorithm. Recent work suggested that the performance of CDCL-based implementations can be considerably improved on specific benchmarks by extending their solving capabilities with custom heuristics and propagators. However, embedding such algorithms into existing systems requires expert knowledge of the internals of ASP implementations. The development of effective solver extensions can be made easier by providing suitable programming interfaces. In this paper, we present the interface for extending the CDCL-based ASP solver wasp. The interface is both general, that is, it can be used for providing either new branching heuristics or propagators, and external, that is, the implementation of new algorithms requires no internal modifications of WASP. Moreover, we review the applications of the interface witnessing it can be successfully used to extend wasp for solving effectively hard instances of both real-world and synthetic problems.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68N17 Logic programming
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Abseher, M., Gebser, M., Musliu, N., Schaub, T. and Woltran, S.2016. Shift design with answer set programming. Fundamenta Informaticae147, 1, 1-25. · Zbl 1373.68169
[2] 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 International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol. 10377. Springer, 215-221. · Zbl 1472.68178
[3] Alviano, M. and Dodaro, C.2016. Completion of disjunctive logic programs. In International Joint Conference on Artificial Intelligence. IJCAI/AAAI Press, 886-892.
[4] Alviano, M., Dodaro, C., Faber, W., Leone, N. and Ricca, F.2013. WASP: A native ASP solver based on constraint learning. In International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol. 8148. Springer, 54-66.
[5] Alviano, M., Dodaro, C., Leone, N. and Ricca, F.2015. Advances in WASP. In International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol. 9345. Springer, 40-54. · Zbl 1467.68021
[6] Alviano, M., Dodaro, C. and Maratea, M.2017. An advanced answer set programming encoding for nurse scheduling. In AI*IA. Lecture Notes in Computer Science, vol. 10640. Springer, 468-482.
[7] Alviano, M., Dodaro, C. and Maratea, M.2018. Shared aggregate sets in answer set programming. Theory and Practice of Logic Programming18, 3-4, 301-318. · Zbl 1451.68062
[8] Balduccini, M.2011. Learning and using domain-specific heuristics in ASP solvers. AI Communications24, 2, 147-164. · Zbl 1215.68207
[9] Balduccini, M., Gelfond, M., Watson, R. and Nogueira, M.2001. The USA-advisor: A case study in answer set planning. In International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol. 2173. Springer, 439-442. · Zbl 1010.68800
[10] Balduccini, M. and Lierler, Y.2017. Constraint answer set solver EZCSP and why integration schemas matter. Theory and Practice of Logic Programming17, 4, 462-515. · Zbl 1379.68038
[11] Baral, C.2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. · Zbl 1056.68139
[12] Bartholomew, M. and Lee, J.2013. Functional stable model semantics and answer set programming modulo theories. In International Joint Conference on Artificial Intelligence. IJCAI/AAAI, 718-724.
[13] Bartholomew, M. and Lee, J.2014. System aspmt2smt: Computing ASPMT theories by SMT solvers. In European Conference on Logics in Artificial Intelligence. Lecture Notes in Computer Science, vol. 8761. Springer, 529-542. · Zbl 1432.68055
[14] Baselice, S., Bonatti, P. A. and Gelfond, M.2005. Towards an integration of answer set and constraint solving. In International Conference on Logic Programming. Lecture Notes in Computer Science, vol. 3668. Springer, 52-66. · Zbl 1165.68481
[15] Biere, A. and Fröhlich, A.2015. Evaluating CDCL variable scoring schemes. In SAT. Lecture Notes in Computer Science, vol. 9340. Springer, 405-422. · Zbl 1471.68238
[16] Bomanson, J., Gebser, M., Janhunen, T., Kaufmann, B. and Schaub, T.2015. Answer set programming modulo acyclicity. In International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol. 9345. Springer, 143-150. · Zbl 1370.68044
[17] Bomanson, J., Gebser, M., Janhunen, T., Kaufmann, B. and Schaub, T.2016. Answer set programming modulo acyclicity. Fundamenta Informaticae147, 1, 63-91. · Zbl 1373.68170
[18] Brewka, G., Eiter, T. and Truszczynski, M.2011. Answer set programming at a glance. Communications of the ACM54, 12, 92-103.
[19] Cuteri, B., Dodaro, C., Ricca, F. and Schüller, P.2017. Constraints, lazy constraints, or propagators in ASP solving: An empirical analysis. Theory and Practice of Logic Programming17, 5-6, 780-799.
[20] Dodaro, C.2015. Computational Tasks in Answer Set Programming: Algorithms and Implementations. Ph.D. dissertation, University of Calabria.
[21] Dodaro, C., Alviano, M., Faber, W., Leone, N., Ricca, F. and Sirianni, M.2011. The birth of a WASP: Preliminary report on a new ASP solver. In Italian Conference on Computational Logic. CEUR Workshop Proceedings, vol. 810. CEUR-WS.org, 99-113.
[22] Dodaro, C., Gasteiger, P., Leone, N., Musitsch, B., Ricca, F. and Schekotihin, K.2016. Combining answer set programming and domain heuristics for solving hard industrial problems (application paper). Theory and Practice of Logic Programming16, 5-6, 653-669. · Zbl 1379.68281
[23] Dodaro, C., Leone, N., Nardi, B. and Ricca, F.2015. Allotment problem in travel industry: A solution based on ASP. In International Conference on Web Reasoning and Rule Systems. Lecture Notes in Computer Science, vol. 9209. Springer, 77-92.
[24] Dodaro, C. and Maratea, M.2017. Nurse scheduling via answer set programming. In International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol. 10377. Springer, 301-307. · Zbl 06769671
[25] Dodaro, C., Ricca, F. and Schüller, P.2016. External propagators in WASP: Preliminary report. In International RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion. CEUR Workshop Proceedings, vol. 1745. CEUR-WS.org, 1-9.
[26] Eén, N. and Sörensson, N.2003. An extensible sat-solver. In International Conference on Theory and Applications of Satisfiability Testing. Lecture Notes in Computer Science, vol. 2919. Springer, 502-518. · Zbl 1204.68191
[27] Erdem, E., Gelfond, M. and Leone, N.2016. Applications of answer set programming. AI Magazine37, 3, 53-68.
[28] Erdem, E. and Öztok, U.2015. Generating explanations for biomedical queries. Theory and Practice of Logic Programming15, 1, 35-78. · Zbl 1379.68059
[29] Friedrich, G.2015. Industrial success stories of ASP and CP: What’s still open? Joint invited talk at ICLP and CP 2015. http://booleconferences.ucc.ie/iclp2015speakers.
[30] Garro, A., Palopoli, L. and Ricca, F.2006. Exploiting agents in e-learning and skills management context. AI Communications19, 2, 137-154.
[31] Gavanelli, M., Nonato, M. and Peano, A.2015. An ASP approach for the valves positioning optimization in a water distribution system. Journal of Logic and Computation25, 6, 1351-1369. · Zbl 1344.68267
[32] Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T. and Wanko, P.2016. Theory solving made easy with clingo 5. In International Conference on Logic Programming (Technical Communications). OpenAccess Series in Informatics, vol. 52. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2:1-2:15.
[33] Gebser, M., Kaminski, R., Kaufmann, B., Romero, J. and Schaub, T.2015. Progress in clasp Series 3. In International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol. 9345. Springer, 368-383. · Zbl 1467.68181
[34] Gebser, M., Kaminski, R., Kaufmann, B. and Schaub, T.2012. Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers. · Zbl 1251.68060
[35] Gebser, M., Kaminski, R., Kaufmann, B. and Schaub, T.2014. Clingo = ASP + control: Preliminary report. CoRR abs/1405.3694. · Zbl 07107408
[36] Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T. and Schneider, M. T.2011. Potassco: The potsdam answer set solving collection. AI Communications24, 2, 107-124. · Zbl 1215.68214
[37] Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T.2008. Advanced preprocessing for answer set solving. In European Conference on Artificial Intelligence. Frontiers in Artificial Intelligence and Applications, vol. 178. IOS Press, 15-19.
[38] Gebser, M., Kaufmann, B., Romero, J., Otero, R., Schaub, T. and Wanko, P.2013. Domain-specific heuristics in answer set programming. In AAAI Conference on Artificial Intelligence. AAAI Press.
[39] Gebser, M., Kaufmann, B. and Schaub, T.2012. Conflict-driven answer set solving: From theory to practice. Artificial Intelligence187, 52-89. · Zbl 1251.68060
[40] Gebser, M., Kaufmann, B. and Schaub, T.2013. Advanced conflict-driven disjunctive answer set solving. In International Joint Conference on Artificial Intelligence. IJCAI/AAAI. · Zbl 1251.68060
[41] Gebser, M., Maratea, M. and Ricca, F.2015. The design of the sixth answer set programming competition. In International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol. 9345. Springer, 531-544. · Zbl 1418.68028
[42] Gebser, M., Maratea, M. and Ricca, F.2016. What’s Hot in the Answer Set Programming Competition. In AAAI Conference on Artificial Intelligence. AAAI Press, 4327-4329.
[43] Gebser, M., Maratea, M. and Ricca, F.2017. The sixth answer set programming competition. Journal of Artificial Intelligence Research60, 41-95. · Zbl 1418.68030
[44] Gebser, M., Ryabokon, A. and Schenner, G.2015. Combining heuristics for configuration problems using answer set programming. In International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol. 9345. Springer, 384-397. · Zbl 1467.68166
[45] Gelfond, M. and Lifschitz, V.1991. Classical negation in logic programs and disjunctive databases. New Generation Computing9, 3/4, 365-386. · Zbl 0735.68012
[46] Janhunen, T. and Niemelä, I.2016. The answer set programming paradigm. AI Magazine37, 3, 13-24.
[47] Janhunen, T., Tasharrofi, S. and Ternovska, E.2016. SAT-to-SAT: Declarative extension of SAT solvers with new propagators. In AAAI Conference on Artificial Intelligence. AAAI Press, 978-984.
[48] Kaufmann, B., Leone, N., Perri, S. and Schaub, T.2016. Grounding and solving in answer set programming. AI Magazine37, 3, 25-32.
[49] Koponen, L., Oikarinen, E., Janhunen, T. and Säilä, L.2015. Optimizing phylogenetic supertrees using answer set programming. Theory and Practice of Logic Programming15, 4-5, 604-619. · Zbl 1379.92038
[50] Lierler, Y., Maratea, M. and Ricca, F.2016. Systems, engineering environments, and competitions. AI Magazine37, 3, 45-52.
[51] Lifschitz, V.2016. Answer sets and the language of answer set programming. AI Magazine37, 3, 7-12.
[52] Manna, M., Ricca, F. and Terracina, G.2013. Consistent query answering via ASP from different perspectives: Theory and practice. Theory and Practice of Logic Programming13, 2, 227-252. · Zbl 1267.68082
[53] Manna, M., Ricca, F. and Terracina, G.2015. Taming primary key violations to query large inconsistent data via ASP. Theory and Practice of Logic Programming15, 4-5, 696-710. · Zbl 1379.68114
[54] Maratea, M., Pulina, L. and Ricca, F.2012. The multi-engine ASP solver ME-ASP. In European Conference on Logics in Artificial Intelligence. Lecture Notes in Computer Science, vol. 7519. Springer, 484-487.
[55] Marileo, M. C. and Bertossi, L. E.2010. The consistency extractor system: Answer set programs for consistent query answering in databases. Data & Knowledge Engineering69, 6, 545-572.
[56] Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L. and Malik, S.2001. Chaff: Engineering an efficient SAT solver. In Design Automation Conference. ACM, 530-535.
[57] Nieuwenhuis, R., Oliveras, A. and Tinelli, C.2006. Solving SAT and SAT modulo theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T). Journal of the ACM53, 6, 937-977. · Zbl 1326.68164
[58] Ostrowski, M. and Schaub, T.2012. ASP modulo CSP: The clingcon system. Theory and Practice of Logic Programming12, 4-5, 485-503. · Zbl 1260.68066
[59] Rossi, F., Van Beek, P. and Walsh, T., Eds. 2006. Handbook of Constraint Programming. Foundations of Artificial Intelligence, vol. 2. Elsevier. · Zbl 1175.90011
[60] Schüller, P.2016. Modeling variations of first-order horn abduction in answer set programming. Fundamenta Informaticae149, 1-2, 159-207. · Zbl 1373.68393
[61] Silva, J. P. M. and Sakallah, K. A.1999. GRASP: A search algorithm for propositional satisfiability. IEEE Transactions on Computers48, 5, 506-521. · Zbl 1392.68388
[62] Susman, B. and Lierler, Y.2016. SMT-based constraint answer set solver EZSMT (system description). In International Conference on Logic Programming (Technical Communications). OpenAccess Series in Informatics, vol. 52. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 1:1-1:15.
[63] Zhang, L., Madigan, C. F., Moskewicz, M. W. and Malik, S.2001. Efficient conflict driven learning in Boolean satisfiability solver. In IEEE/ACM International Conference on Computer-Aided Design. IEEE Computer Society, 279-285.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.