Abstract
Algorithm selection techniques are known to improve the performance of systems for several knowledge representation and reasoning frameworks.This holds also in the case of Answer Set Programming (ASP), which is a rule-based programming paradigm with roots in logic programming and non-monotonic reasoning. Indeed, the multi-engine approach to ASP solving implemented in me-asp was particularly effective on the instances of the third ASP competition. In this paper we report about the advances we made on me-asp in order to deal with the new standard language ASPCore 2.0, which substantially extends the previous version of the standard language.An experimental analysis conducted on the Fifth ASP Competition benchmarks and solvers confirms the effectiveness of our approach also in comparison to rival systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aha, D., Kibler, D., Albert, M.: Instance-based learning algorithms. Machine Learning 6(1), 37–66 (1991)
Alviano, M., Calimeri, F., Charwat, G., Dao-Tran, M., Dodaro, C., Ianni, G., Krennwallner, T., Kronegger, M., Oetsch, J., Pfandler, A., Pührer, J., Redl, C., Ricca, F., Schneider, P., Schwengerer, M., Spendier, L.K., Wallner, J.P., Xiao, G.: The fourth answer set programming competition: preliminary report. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS, vol. 8148, pp. 42–53. Springer, Heidelberg (2013)
Alviano, M., Dodaro, C., Faber, W., Leone, N., Ricca, F.: WASP: a native ASP solver based on constraint learning. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS, vol. 8148, pp. 54–66. Springer, Heidelberg (2013)
Alviano, M., Dodaro, C., Ricca, F.: Preliminary report on WASP 2.0. In: Konieczny, S., Tompits, H. (eds.) Proceedings of the 15th International Workshop on Non-Monotonic Reasoning (NMR 2014), pp. 1–5. Vienna, Austria (2014)
Balduccini, M.: Learning and using domain-specific heuristics in ASP solvers. AI Communications - The European Journal on Artificial Intelligence 24(2), 147–164 (2011)
Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Tempe, Arizona (2003)
Bomanson, J., Janhunen, T.: Normalizing cardinality rules using merging and sorting constructions. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS, vol. 8148, pp. 187–199. Springer, Heidelberg (2013)
Buccafurri, F., Leone, N., Rullo, P.: Enhancing Disjunctive Datalog by Constraints. IEEE Transactions on Knowledge and Data Engineering 12(5), 845–860 (2000)
Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Ricca, F., Schaub, T.: ASP-Core-2 input language format (since 2013). https://www.mat.unical.it/aspcomp2013/ASPStandardization
Calimeri, F., Gebser, M., Maratea, M., Ricca, F.: The design of the fifth Answer Set Programming competition. ICLP 2014 Technical Communications - CoRR abs/1405.3710 (2014). http://arxiv.org/abs/1405.3710
Cabalar, P.: Answer set; Programming? In: Balduccini, M., Son, T.C. (eds.) Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning. LNCS, vol. 6565, pp. 334–343. Springer, Heidelberg (2011)
Cabalar, P.: Answer set; Programming? In: Balduccini, M., Son, T.C. (eds.) Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning. LNCS, vol. 6565, pp. 334–343. Springer, Heidelberg (2011)
Calimeri, F., Ianni, G., Ricca, F., Alviano, M., Bria, A., Catalano, G., Cozza, S., Faber, W., Febbraro, O., Leone, N., Manna, M., Martello, A., Panetta, C., Perri, S., Reale, K., Santoro, M.C., Sirianni, M., Terracina, G., Veltri, P.: The third answer set programming competition: preliminary report of the system competition track. In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS, vol. 6645, pp. 388–403. Springer, Heidelberg (2011)
Dell’Armi, T., Faber, W., Ielpa, G., Leone, N., Pfeifer, G.: Aggregate functions in disjunctive logic programming: semantics, complexity, and implementation in DLV. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI) 2003, pp. 847–852. Morgan Kaufmann Publishers, Acapulco, August 2003
Drescher, C., Gebser, M., Grote, T., Kaufmann, B., König, A., Ostrowski, M., Schaub, T.: Conflict-driven disjunctive answer set solving. In: Brewka, G., Lang, J. (eds.) Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), pp. 422–432. AAAI Press, Sydney (2008)
Faber, W., Leone, N., Pfeifer, G.: Recursive aggregates in disjunctive logic programs: semantics and complexity. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 200–212. Springer, Heidelberg (2004)
Faber, W., Leone, N., Pfeifer, G.: Semantics and complexity of recursive aggregates in answer set programming. Artificial Intelligence 175(1), 278–298 (2011). special Issue: John McCarthy’s Legacy
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Clingo = ASP + Control: preliminary report. In: Theory and Practice of Logic Programming - Online-Supplement: Proc. of 30th International Conference on Logic Programming (ICLP 2014), pp. 1–9. Cambridge University Press (2014)
Gebser, M., Janhunen, T., Rintanen, J.: Answer set programming as sat modulo acyclicity. In: Schaub, T., Friedrich, G., O’Sullivan, B. (eds.) Proceedings of the Twenty-First European Conference on Artificial Intelligence (ECAI 2014). Frontiers in Artificial Intelligence and Applications, vol. 263, pp. 351–356. IOS Press (2014)
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T., Schneider, M.T., Ziller, S.: A portfolio solver for answer set programming: preliminary report. In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS, vol. 6645, pp. 352–357. Springer, Heidelberg (2011)
Gelfond, M., Leone, N.: Logic Programming and Knowledge Representation - the A-Prolog perspective. Artificial Intelligence 138(1–2), 3–38 (2002)
Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Logic Programming: Proceedings Fifth Intl. Conference and Symposium, pp. 1070–1080. MIT Press, Cambridge (1988)
Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing 9, 365–385 (1991)
Gomes, C.P., Selman, B.: Algorithm portfolios. Artificial Intelligence 126(1–2), 43–62 (2001)
Hoos, H., Kaminski, R., Schaub, T., Schneider, M.T.: ASPeed: ASP-based solver scheduling. In: Technical Communications of the 28th International Conference on Logic Programming (ICLP 2012). LIPIcs, vol. 17, pp. 176–187. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)
Hoos, H., Lindauer, M.T., Schaub, T.: Claspfolio 2: Advances in algorithm selection for answer set programming. TPLP 14(4–5), 569–585 (2014)
Janhunen, T.: Some (in)translatability results for normal logic programs and propositional theories. Journal of Applied Non-Classical Logics 16, 35–86 (2006)
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV System for Knowledge Representation and Reasoning. ACM Transactions on Computational Logic 7(3), 499–562 (2006)
Grosan, C., Abraham, A.: Machine learning. In: Grosan, C., Abraham, A. (eds.) Intelligent Systems. ISRL, vol. 17, pp. 261–268. Springer, Heidelberg (2011)
Maratea, M., Pulina, L., Ricca, F.: The multi-engine ASP solver me-asp. In: del Cerro, L.F., Herzig, A., Mengin, J. (eds.) JELIA 2012. LNCS, vol. 7519, pp. 484–487. Springer, Heidelberg (2012)
Maratea, M., Pulina, L., Ricca, F.: A multi-engine approach to answer-set programming. TPLP 14(6), 841–868 (2014). http://dx.doi.org/10.1017/S1471068413000094
Nguyen, M., Janhunen, T., Niemelä, I.: Translating answer-set programs into bit-vector logic. In: Tompits, H., Abreu, S., Oetsch, J., Pührer, J., Seipel, D., Umeda, M., Wolf, A. (eds.) INAP/WLP 2011. LNCS, vol. 7773, pp. 91–109. Springer, Heidelberg (2013)
Nudelman, E., Leyton-Brown, K., H. Hoos, H., Devkar, A., Shoham, Y.: Understanding random SAT: beyond the clauses-to-variables ratio. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 438–452. Springer, Heidelberg (2004)
O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., O’Sullivan, B.: Using case-based reasoning in an algorithm portfolio for constraint solving. In: Proc. of the 19th Irish Conference on Artificial Intelligence and Cognitive Science (2008)
Pulina, L., Tacchella, A.: A self-adaptive multi-engine solver for quantified boolean formulas. Constraints 14(1), 80–116 (2009)
Rice, J.R.: The algorithm selection problem. Advances in Computers 15, 65–118 (1976)
Samulowitz, H., Memisevic, R.: Learning to solve QBF. In: Proc. of the 22th AAAI Conference on Artificial Intelligence, pp. 255–260. AAAI Press, Vancouver (2007)
Silverthorn, B., Lierler, Y., Schneider, M.: Surviving solver sensitivity: an ASP practitioner’s guide. In: Technical Communications of the 28th International Conference on Logic Programming (ICLP 2012). LIPIcs, vol. 17, pp. 164–175. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)
Simons, P.: Extending and Implementing the Stable Model Semantics. Ph.D. thesis, Helsinki University of Technology, Finland (2000)
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: Portfolio-based algorithm selection for SAT. JAIR 32, 565–606 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Maratea, M., Pulina, L., Ricca, F. (2015). Advances in Multi-engine ASP Solving. In: Gavanelli, M., Lamma, E., Riguzzi, F. (eds) AI*IA 2015 Advances in Artificial Intelligence. AI*IA 2015. Lecture Notes in Computer Science(), vol 9336. Springer, Cham. https://doi.org/10.1007/978-3-319-24309-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-24309-2_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-24308-5
Online ISBN: 978-3-319-24309-2
eBook Packages: Computer ScienceComputer Science (R0)