Abstract
Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and nonmonotonic reasoning. With ASP, computational problems are encoded by logic programs whose answer sets, corresponding to solutions, are computed by an ASP system. In general, several semantically equivalent programs might be defined for the same problem; however, performance of ASP systems while evaluating them might significantly vary. We propose an approach for automatically transforming an input logic program into an equivalent one that can be evaluated more efficiently. To this aim, one can make use of existing tree-decomposition techniques for rewriting selected rules into a set of multiple ones. The idea is to guide and adaptively apply them on the basis of proper new heuristics, in order to obtain a smart rewriting algorithm to be integrated into an ASP system. The method is rather general: it can be adapted to the system at hand and implement different preference policies. Furthermore, we define a set of new heuristics explicitly tailored at optimizing one of the main phases of the typical ASP computation, namely the grounding process; we make use of them in order to actually implement the approach into the ASP system DLV, and in particular into its grounding subsystem \(\mathcal I\)-DLV, and carry out an extensive experimental activity aimed at assessing the impact of the proposal.
This work has been partially supported by the Italian Ministry for Economic Development (MISE) under project “PIUCultura – Paradigmi Innovativi per l’Utilizzo della Cultura” (n. F/020016/01-02/X27), and under project “Smarter Solutions in the Big Data World (S2BDW)” (n. F/050389/01-03/X32) funded within the call “HORIZON2020” PON I&C 2014-2020.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We remark that this definition of safety is specific for the syntax considered herein. For a complete definition we refer the reader to [8].
- 2.
According to \(\mathsf {ASP\text {-}Core\text {-}2}\) syntax, the term (1..k) stands for all values from 1 to k.
- 3.
- 4.
Experiments have been performed on a NUMA machine equipped with two 2,8GHz AMD Opteron 6320 and 128 GiB of main memory, running Linux Ubuntu 14.04.4 (kernel ver. 3.19.0-25). Binaries have been generated by the GNU C++ compiler 5.4.0. We allotted 15 GiB and 600Â s to each system per each single run, as memory and time limits.
References
Abseher, M., Musliu, N., Woltran, S.: htd – a free, open-source framework for (customized) tree decompositions and beyond. In: Salvagnin, D., Lombardi, M. (eds.) CPAIOR 2017. LNCS, vol. 10335, pp. 376–386. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59776-8_30
Alviano, M., et al.: The ASP system DLV2. In: Balduccini, M., Janhunen, T. (eds.) LPNMR 2017. LNCS (LNAI), vol. 10377, pp. 215–221. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61660-5_19
Alviano, M., Dodaro, C., Leone, N., Ricca, F.: Advances in WASP. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS (LNAI), vol. 9345, pp. 40–54. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23264-5_5
Alviano, M., Faber, W., Greco, G., Leone, N.: Magic sets for disjunctive datalog programs. Artif. Intell. 187, 156–192 (2012)
Bichler, M., Morak, M., Woltran, S.: lpopt: a rule optimization tool for answer set programming. In: LOPSTR, pp. 114–130 (2016)
Bliem, B., Moldovan, M., Morak, M., Woltran, S.: The impact of treewidth on ASP grounding and solving. In: Sierra, C. (ed.) IJCAI, pp. 852–858. ijcai.org (2017). http://www.ijcai.org/Proceedings/2017/
Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92–103 (2011)
Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Ricca, F., Schaub, T.: Asp-core-2: input language format (2012). https://www.mat.unical.it/aspcomp2013/files/ASP-CORE-2.03b.pdf
Calimeri, F., FuscĂ , D., Perri, S., Zangari, J.: The ASP instantiator I-DLV. In: PAoASP, Espoo, Finland (2017)
Calimeri, F., Fuscà , D., Perri, S., Zangari, J.: I-DLV: the new intelligent grounder of DLV. Intelligenza Artificiale 11(1), 5–20 (2017)
Calimeri, F., FuscĂ , D., Perri, S., Zangari, J.: \(\cal{I}\)-DLV \(+\cal{MS}\): preliminary report on an automatic ASP solver selector. In: RCRA (2017, to appear)
Calimeri, F., Gebser, M., Maratea, M., Ricca, F.: Design and results of the fifth answer set programming competition. Artif. Intell. 231, 151–181 (2016)
Dal Palù, A., Dovier, A., Pontelli, E., Rossi, G.: GASP: answer set programming with lazy grounding. Fundamenta Informaticae 96(3), 297–322 (2009)
Dao-Tran, M., Eiter, T., Fink, M., Weidinger, G., Weinzierl, A.: OMiGA: an open minded grounding on-the-fly answer set solver. In: del Cerro, L.F., Herzig, A., Mengin, J. (eds.) JELIA 2012. LNCS (LNAI), vol. 7519, pp. 480–483. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33353-8_38
Eiter, T., Kaminski, T., Weinzierl, A.: Lazy-grounding for answer set programs with external source access. In: IJCAI, pp. 1015–1022 (2017)
Gebser, M., Kaminski, R., Kaufmann, B., Romero, J., Schaub, T.: Progress in clasp series 3. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS (LNAI), vol. 9345, pp. 368–383. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23264-5_31
Gebser, M., Maratea, M., Ricca, F.: The design of the sixth answer set programming competition. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS (LNAI), vol. 9345, pp. 531–544. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23264-5_44
Gebser, M., Maratea, M., Ricca, F.: What’s hot in the answer set programming competition. In: AAAI, pp. 4327–4329 (2016)
Gebser, M., Maratea, M., Ricca, F.: The design of the seventh answer set programming competition. In: Balduccini, M., Janhunen, T. (eds.) LPNMR 2017. LNCS (LNAI), vol. 10377, pp. 3–9. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61660-5_1
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9(3/4), 365–385 (1991). https://doi.org/10.1007/BF03037169
Gottlob, G., Grohe, M., Musliu, N., Samer, M., Scarcello, F.: Hypertree decompositions: structure, algorithms, and applications. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 1–15. Springer, Heidelberg (2005). https://doi.org/10.1007/11604686_1
Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions: a survey. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 37–57. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44683-4_5
Kaufmann, B., Leone, N., Perri, S., Schaub, T.: Grounding and solving in answer set programming. AI Mag. 37(3), 25–32 (2016)
Lefèvre, C., Nicolas, P.: The first version of a new ASP solver: ASPeRiX. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS (LNAI), vol. 5753, pp. 522–527. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04238-6_52
Leone, N., Perri, S., Scarcello, F.: Improving ASP instantiators by join-ordering methods. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) LPNMR 2001. LNCS (LNAI), vol. 2173, pp. 280–294. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45402-0_21
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. (TOCL) 7(3), 499–562 (2006)
Lifschitz, V.: Answer set planning. In: Gelfond, M., Leone, N., Pfeifer, G. (eds.) LPNMR 1999. LNCS (LNAI), vol. 1730, pp. 373–374. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-46767-X_28
Morak, M., Woltran, S.: Preprocessing of complex non-ground rules in answer set programming. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2012)
Ullman, J.D.: Principles of Database and Knowledge-Base Systems, vol. I. Computer Science Press, New York (1988)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Calimeri, F., FuscĂ , D., Perri, S., Zangari, J. (2018). Optimizing Answer Set Computation via Heuristic-Based Decomposition. In: Calimeri, F., Hamlen, K., Leone, N. (eds) Practical Aspects of Declarative Languages. PADL 2018. Lecture Notes in Computer Science(), vol 10702. Springer, Cham. https://doi.org/10.1007/978-3-319-73305-0_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-73305-0_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-73304-3
Online ISBN: 978-3-319-73305-0
eBook Packages: Computer ScienceComputer Science (R0)