Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T11:22:16.628Z Has data issue: false hasContentIssue false
  • English
  • Français

A multi-engine approach to answer-set programming*

Published online by Cambridge University Press:  15 August 2013

MARCO MARATEA ,
LUCA PULINA  and
FRANCESCO RICCA
MARCO MARATEA
Affiliation:
DIBRIS, Università degli Studi di Genova, Viale F. Causa 15, 16145 Genova, Italy (e-mail: [email protected])
LUCA PULINA
Affiliation:
POLCOMING, Università degli Studi di Sassari, Viale Mancini 5, 07100 Sassari, Italy (e-mail: [email protected])
FRANCESCO RICCA
Affiliation:
Dipartimento di Matematica, Università della Calabria, Via P. Bucci, 87030 Rende, Italy (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Answer-set programming (ASP) is a truly declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming, which has been recently employed in many applications. The development of efficient ASP systems is, thus, crucial. Having in mind the task of improving the solving methods for ASP, there are two usual ways to reach this goal: (i) extending state-of-the-art techniques and ASP solvers or (ii) designing a new ASP solver from scratch. An alternative to these trends is to build on top of state-of-the-art solvers, and to apply machine learning techniques for choosing automatically the “best” available solver on a per-instance basis.

In this paper, we pursue this latter direction. We first define a set of cheap-to-compute syntactic features that characterize several aspects of ASP programs. Then, we apply classification methods that, given the features of the instances in a training set and the solvers' performance on these instances, inductively learn algorithm selection strategies to be applied to a test set. We report the results of a number of experiments considering solvers and different training and test sets of instances taken from the ones submitted to the “System Track” of the Third ASP Competition. Our analysis shows that by applying machine learning techniques to ASP solving, it is possible to obtain very robust performance: our approach can solve more instances compared with any solver that entered the Third ASP Competition.

Keywords

answer-set programmingautomated algorithm selectionmulti-engine solvers
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Issue 6 , November 2014 , pp. 841 - 868
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

This is an extended and revised version of Maratea et al. (2012a, 2012b).

References

Aha, D., Kibler, D. and Albert, M. 1991. Instance-based learning algorithms. Machine learning 6, 1, 37–66.CrossRefGoogle Scholar
Balduccini, M. 2011. Learning and using domain-specific heuristics in ASP solvers. AI Communications – The European Journal on Artificial Intelligence 24, 2, 147–164.Google Scholar
Balduccini, M. and Lierler, Y. 2012. Practical and methodological aspects of the use of cutting-edge ASP tools. In Proc. of the 14th International Symposium on Practical Aspects of Declarative Languages (PADL 2012), Russo, C. V. and Zhou, N.-F., Eds. LNCS, vol. 7149. Springer, Philadelphia, PA, 78–92.CrossRefGoogle Scholar
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Tempe, AZ.Google Scholar
Brooks, D. R., Erdem, E., Erdogan, S. T., Minett, J. W. and Ringe, D. 2007. Inferring phylogenetic trees using answer set programming. Journal of Automated Reasoning 39, 4, 471–511.Google Scholar
Calimeri, F., Ianni, G. and Ricca, F. 2011. The third answer set programming system competition. Accessed July 2011 [online]. URL: https://www.mat.unical.it/aspcomp2011/.Google Scholar
Calimeri, F., Ianni, G. and Ricca, F. 2012. The third open answer set programming competition. Theory and Practice of Logic Programming, doi.10.1017/S1471068412000105.Google Scholar
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. and Veltri, P. 2011. The Third Answer Set Programming Competition: Preliminary report of the system competition track. In Proc. of LPNMR11. LNCS, Springer, Vancouver, Canada, 388–403.Google Scholar
Clark, K. L. 1978. Negation as failure. In Logic and Data Bases, Gallaire, H. and Minker, J., Eds. Plenum Press, New York, 293–322.Google Scholar
Cortes, C. and Vapnik, V. 1995. Support-vector networks. Machine learning 20, 3, 273–297.CrossRefGoogle Scholar
deAAAAMoura, L. M. and Bjørner, N. 2008. Z3: An efficient SMT solver. In Proc. of the 14th International Conference on Tools and Algorithms for Construction and Analysis of Systems, TACAS 2008, Budapest, Hungary, 337–340.Google Scholar
Drescher, C., Gebser, M., Grote, T., Kaufmann, B., König, A., Ostrowski, M. and Schaub, T. 2008. Conflict-driven disjunctive answer set solving. In Proc. of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), Brewka, G. and Lang, J., Eds. AAAI Press, Sydney, Australia, 422–432.Google Scholar
Eén, N. and Sörensson, N. 2003. An extensible SAT-solver. In Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. LNCS, Springer, Berlin, 502–518.Google Scholar
Eiter, T., Gottlob, G. and Mannila, H. 1997. Disjunctive datalog. ACM Transactions on Database Systems 22, 3 (Sept.), 364–418.CrossRefGoogle Scholar
Friedrich, G. and Ivanchenko, V. 2008. Diagnosis from first principles for workflow executions. Technical repport, Alpen Adria University, Applied Informatics, Klagenfurt, Austria. URL: http://proserver3-iwas.uni-klu.ac.at/download_area/Technical-Reports/technical_report_2008_02.pdf.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T., Schneider, M. T. and Ziller, S. 2011. A portfolio solver for answer set programming: Preliminary report. In Proc. of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), Delgrande, J. P. and Faber, W., Eds. LNCS, vol. 6645. Springer, Vancouver, Canada, 352–357.CrossRefGoogle Scholar
Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T. 2007. Conflict-driven answer set solving. In Proc. of the 12th International Joint Conference on Artificial Intelligence (IJCAI-07). Morgan Kaufmann Publishers, Hyderabad, India, 386–392.Google Scholar
Gebser, M., Schaub, T. and Thiele, S. 2007. GrinGo: A new grounder for answer set programming. In Logic Programming and Nonmonotonic Reasoning, 9th International Conference, LPNMR 2007. LNCS, vol. 4483. Springer, Tempe, AZ, 266–271.Google Scholar
Gebser, M., Schaub, T., Thiele, S. and Veber, P. 2011. Detecting inconsistencies in large biological networks with answer set programming. Theory and Practice of Logic Programming 11, 2–3, 323–360.CrossRefGoogle Scholar
Gelfond, M. and Leone, N. 2002. Logic programming and knowledge representation – the A-Prolog perspective. Artificial Intelligence 138, 1–2, 3–38.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming: Proceedings Fifth Intl Conference and Symposium. MIT Press, Cambridge, MA, 1070–1080.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385.Google Scholar
Gerevini, A., Saetti, A. and Vallati, M. 2009. An automatically configurable portfolio-based planner with macro-actions: Pbp. In Proc. of the 19th International Conference on Automated Planning and Scheduling, Gerevini, A., Howe, A. E., Cesta, A. and Refanidis, I., Eds. AAAI, Thessaloniki, Greece.Google Scholar
Giunchiglia, E., Lierler, Y. and Maratea, M. 2006. Answer set programming based on propositional satisfiability. Journal of Automated Reasoning 36, 4, 345–377.Google Scholar
Gomes, C. P. and Selman, B. 2001. Algorithm portfolios. Artificial Intelligence 126, 1–2, 43–62.CrossRefGoogle Scholar
Halder, A., Ghosh, A. and Ghosh, S. 2009. Aggregation pheromone density based pattern classification. Fundamenta Informaticae 92, 4, 345–362.Google Scholar
Hoos, H. H. 2012. Programming by optimization. Communications of the ACM 55, 2, 70–80.Google Scholar
Hühn, J. and Hüllermeier, E. 2009. Furia: An algorithm for unordered fuzzy rule induction. Data Mining and Knowledge Discovery 19, 3, 293–319.Google Scholar
Hutter, F., Hoos, H. H. and Leyton-Brown, K. 2010. Automated configuration of mixed integer programming solvers. In Proc. of the 7th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lodi, A., Milano, M., and Toth, P., Eds. LNCS, vol. 6140. Springer, Bologna, Italy, 186–202.Google Scholar
Hutter, F., Hoos, H. H., Leyton-Brown, K. and Stützle, T. 2009. ParamILS: An automatic algorithm configuration framework. Journal of Artificial Intelligence Research 36, 267–306.Google Scholar
Janhunen, T. 2006. Some (in)translatability results for normal logic programs and propositional theories. Journal of Applied Non-Classical Logics 16, 35–86.CrossRefGoogle Scholar
Janhunen, T., Niemelä, I. and Sevalnev, M. 2009. Computing stable models via reductions to difference logic. In Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR). LNCS. Springer, Postdam, Germany, 142–154.CrossRefGoogle Scholar
LeAAAACessie, S. and VanAAAAHouwelingen, J.C. 1992. Ridge estimators in logistic regression. Applied Statistics 41, 1, 191–201.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3 (July), 499–562.Google Scholar
Leyton-Brown, K., Nudelman, E., Andrew, G., Mcfadden, J. and Shoham, Y. 2003. A portfolio approach to algorithm selection. In Proc. of the 18th International Joint Conference on Artificial Intelligence, IJCAI-03, Acapulco, Mexico.Google Scholar
Lierler, Y. 2005. Disjunctive answer set programming via satisfiability. In Logic Programming and Nonmonotonic Reasoning – 8th International Conference, LPNMR'05, Diamante, Italy, September 2005, Proceedings, Baral, C., Greco, G., Leone, N., and Terracina, G., Eds. LNCS, vol. 3662. Springer Verlag, Cosenza, Italy, 447–451.Google Scholar
Lierler, Y. 2008. Abstract answer set solvers. In Logic Programming, 24th International Conference (ICLP 2008). LNCS, vol. 5366. Springer, Udine, Italy, 377–391.Google Scholar
Lifschitz, V. 1999. Answer set planning. In Proc. of the 16th International Conference on Logic Programming (ICLP'99), Schreye, D. D., Ed. MIT Press, Las Cruces, NM, 23–37.Google Scholar
Maratea, M., Pulina, L. and Ricca, F. 2012a. Applying machine learning techniques to ASP solving. In Technical Communications of the 28th International Conference on Logic Programming (ICLP 2012). LIPIcs, vol. 17. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, Germany, 37–48.Google Scholar
Maratea, M., Pulina, L. and Ricca, F. 2012b. The multi-engine ASP solver ME-ASP. In Proc. of Logics in Artificial Intelligence, JELIA 2012. LNCS, vol. 7519. Springer, Toulouse, France, 484–487.Google Scholar
Marczak, W. R., Huang, S. S., Bravenboer, M., Sherr, M., Loo, B. T. and Aref, M. 2010. Secureblox: Customizable secure distributed data processing. In SIGMOD Conference. ACM, Indianapolis, 723–734.Google Scholar
Marek, V. W. and Truszczyński, M. 1998. Stable models and an alternative logic programming paradigm. CoRR cs.LO/9809032.CrossRefGoogle Scholar
Mariën, M., Wittocx, J., Denecker, M. and Bruynooghe, M. 2008. Sat(id): Satisfiability of propositional logic extended with inductive definitions. In Proc. of the 11th International Conference on Theory and Applications of Satisfiability Testing, SAT 2008. LNCS. Springer, Guangzhou, China, 211–224.Google Scholar
Masoni, A., Carpinelli, M., Fenu, G., Bosin, A., Mura, D., Porceddu, I. and Zanetti, G. 2009. Cybersar: A lambda grid computing infrastructure for advanced applications. In Nuclear Science Symposium Conference Record (NSS/MIC), 2009 IEEE. IEEE, Orlando, FL, 481–483.Google Scholar
Mierswa, I., Wurst, M., Klinkenberg, R., Scholz, M. and Euler, T. 2006. Yale: Rapid prototyping for complex data mining tasks. In Proc. of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, Philadelphia, PA, 935–940.CrossRefGoogle Scholar
Niemelä, I. 1998. Logic programs with stable Model Semantics as a Constraint Programming Paradigm. In Proc. of the Workshop on Computational Aspects of Nonmonotonic Reasoning, Niemelä, I. and Schaub, T., Eds. Trento, Italy, 72–79.Google Scholar
Nogueira, M., Balduccini, M., Gelfond, M., Watson, R. and Barry, M. 2001. An A-Prolog decision support system for the space shuttle. In Practical Aspects of Declarative Languages, Third International Symposium (PADL 2001), Ramakrishnan, I., Ed. LNCS, vol. 1990. Springer, Las Vegas, NV, 169–183.Google Scholar
Nudelman, E., Leyton-Brown, K., Hoos, H. H., Devkar, A. and Shoham, Y. 2004. Understanding random SAT: Beyond the clauses-to-variables ratio. In Proc. of the 10th International Conference on Principles and Practice of Constraint Programming (CP), Wallace, M., Ed. LNCS. Springer, Toronto, Canada, 438–452.Google Scholar
Pulina, L. and Tacchella, A. 2007. A multi-engine solver for quantified boolean formulas. In Proc. of the 13th International Conference on Principles and Practice of Constraint Programming (CP), Bessiere, C., Ed. LNCS. Springer, Providence, RI, 574–589.Google Scholar
Pulina, L. and Tacchella, A. 2009. A self-adaptive multi-engine solver for quantified boolean formulas. Constraints 14, 1, 80–116.CrossRefGoogle Scholar
Quinlan, J. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Francisco, CA.Google Scholar
Ricca, F., Dimasi, A., Grasso, G., Ielpa, S.M., Iiritano, S., Manna, M. and Leone, N. 2010. A logic-based system for e-Tourism. Fundamenta Informaticae 105, 2010, 35–55Google Scholar
Ricca, F., Gallucci, L., Schindlauer, R., Dell'Armi, T., Grasso, G. and Leone, N. 2009. OntoDLV: An ASP-based system for enterprise ontologies. Journal of Logic and Computation 19, 4, 643–670.Google Scholar
Ricca, F., Grasso, G., Alviano, M., Manna, M., Lio, V., Iiritano, S. and Leone, N. 2012. Team-building with answer set programming in the Gioia-Tauro Seaport. Theory and Practice of Logic Programming 12, 3, 361–381.CrossRefGoogle Scholar
Rice, J. R. 1976. The algorithm selection problem. Advances in Computers 15, 65–118.CrossRefGoogle Scholar
Rullo, P., Policicchio, V. L., Cumbo, C. and Iiritano, S. 2009. Olex: Effective rule learning for text categorization. IEEE Transactions on Knowledge and Data Engineering 21, 8, 1118–1132.Google Scholar
Samulowitz, H. and Memisevic, R. 2007. Learning to solve QBF. In Proceedings of the 22th AAAI Conference on Artificial Intelligence. AAAI Press, Vancouver, Canada, 255–260.Google Scholar
Simons, P., Niemelä, I. and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 181–234.Google Scholar
Smaragdakis, Y., Bravenboer, M. and Lhoták, O. 2011. Pick your contexts well: Understanding object-sensitivity. In Proc. of the 38th Symposium on Principles of Programming Languages, POPL 2011. ACM, Austin, TX, 17–30.Google Scholar
smt-lib-web. 2011. The Satisfiability Modulo Theories Library. Accessed July 2011 [online]. URL: http://www.smtlib.org/.Google Scholar
Vallati, M., Fawcett, C., Gerevini, A., Hoos, H. and Saetti, A. 2011. Generating fast domain-specific planners by automatically configuring a generic parameterised planner. In Working notes of 21st International Conference on Automated Planning and Scheduling (ICAPS-11) Workshop on Planning and Learning. Freiburg, Germany.Google Scholar
Wittocx, J., Mariën, M. and Denecker, M. 2008. The idp system: A model expansion system for an extension of classical logic. In Logic and Search, Computation of Structures from Declarative Descriptions (LaSh 2008). Leuven, Belgium, 153–165.Google Scholar
Xu, L., Hutter, F., Hoos, H. H. and Leyton-Brown, K. 2008. SATzilla: Portfolio-based algorithm selection for SAT. Journal of Artificial Intelligence Research 32, 565–606.Google Scholar