lpopt : A Rule Optimization Tool for Answer Set Programming

• Autorzy: Bichler Manuel , Morak Michael , Woltran Stefan

Identyfikatory

DOI

10.3233/FI-2020-1990

• Języki publikacji: EN

Abstrakty

EN

State-of-the-art answer set programming (ASP) solvers rely on a program called a grounder to convert non-ground programs containing variables into variable-free, propositional programs. The size of this grounding depends heavily on the size of the non-ground rules, and thus, reducing the size of such rules is a promising approach to improve solving performance. To this end, in this paper we announce lpopt, a tool that decomposes large logic programming rules into smaller rules that are easier to handle for current solvers. The tool is specifically tailored to handle the standard syntax of the ASP language (ASP-Core) and makes it easier for users to write efficient and intuitive ASP programs, which would otherwise often require significant hand-tuning by expert ASP engineers. It is based on an idea proposed by Morak and Woltran (2012) that we extend significantly in order to handle the full ASP syntax, including complex constructs like aggregates, weak constraints, and arithmetic expressions. We present the algorithm, the theoretical foundations on how to treat these constructs, as well as an experimental evaluation showing the viability of our approach.

Słowa kluczowe

EN

logic programming; answer set programming; rule decomposition; tree decomposition; preprocessing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 177, nr 3/4
• Strony: 275--296
• Opis fizyczny: Bibliogr. 34 poz., rys.

Twórcy

autor

Bichler Manuel

• TU Wien, Vienna, Austria

autor

Morak Michael

• University of Klagenfurt, Austria

autor

Woltran Stefan

• TU Wien, Vienna, Austria

Bibliografia

• [1] Marek VW, Truszczyński M. Stable Models and an Alternative Logic Programming Paradigm. In: The Logic Programming Paradigm - A 25-Year Perspective, pp. 375-398. Springer, 1999.
• [2] Brewka G, Eiter T, Truszczynski M. Answer set programming at a glance. Commun. ACM, 2011. 54(12):92-103. doi:10.1145/2043174.2043195.
• [3] Gebser M, Kaminski R, Kaufmann B, Schaub T. Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2012. doi:10.2200/S00457ED1V01Y201211AIM019.
• [4] Gelfond M, Lifschitz V. The Stable Model Semantics for Logic Programming. In: Logic Programming, Proceedings of the Fifth International Conference and Symposium, (2 Volumes). 1988 pp. 1070-1080.
• [5] Gelfond M, Lifschitz V. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Comput., 1991. 9(3/4):365-386. doi:10.1007/BF03037169.
• [6] Alviano M, Calimeri F, Dodaro C, Fuscà D, Leone N, Perri S, Ricca F, Veltri P, Zangari J. The ASP System DLV2. In: Logic Programming and Nonmonotonic Reasoning - 14th International Conference, LPNMR, Proceedings. 2017 pp. 215-221. doi:10.1007/978-3-319-61660-5\_19.
• [7] Gebser M, Kaminski R, Kaufmann B, Schaub T. Clingo = ASP + Control: Preliminary Report. CoRR, 2014. abs/1405.3694. 1405.3694, URL http://arxiv.org/abs/1405.3694.
• [8] Alviano M, Dodaro C, Faber W, Leone N, Ricca F. WASP: A Native ASP Solver Based on Constraint Learning. In: Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013, Corunna, Spain, September 15-19, 2013. Proceedings. 2013 pp. 54-66. doi:10.1007/978-3-642-40564-8\_6.
• [9] Gebser M, Kaminski R, König A, Schaub T. Advances in gringo Series 3. In: Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR. Proceedings. 2011 pp. 345-351. doi:10.1007/978-3-642-20895-9\_39.
• [10] 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., 2006. 7(3):499-562. doi:10.1145/1149114.1149117.
• [11] Elkabani I, Pontelli E, Son TC. SmodelsA - A System for Computing Answer Sets of Logic Programs with Aggregates. In: Logic Programming and Nonmonotonic Reasoning, 8th International Conference, LPNMR 2005, Diamante, Italy, September 5-8, 2005, Proceedings. 2005 pp. 427-431. doi:10.1007/11546207\_40.
• [12] Alviano M, Faber W, Greco G, Leone N. Magic Sets for disjunctive Datalog programs. Artif. Intell., 2012. 187:156-192. doi:10.1016/j.artint.2012.04.008.
• [13] Leone N, Perri S, Scarcello F. Improving ASP Instantiators by Join-Ordering Methods. In: Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR, Proceedings. 2001 pp.280-294. doi:10.1007/3-540-45402-0\_21.
• [14] Catalano G, Leone N, Perri S. On demand Indexing Techniques for the DLV Instantiator. In: Proceedings of the Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP. 2008.
• [15] Perri S, Scarcello F, Catalano G, Leone N. Enhancing DLV instantiator by backjumping techniques. Ann. Math. Artif. Intell., 2007. 51(2-4):195-228. doi:10.1007/s10472-008-9090-9.
• [16] Morak M, Woltran S. Preprocessing of Complex Non-Ground Rules in Answer Set Programming. In: Technical Communications of the 28th International Conference on Logic Programming, ICLP 2012, September 4-8, 2012, Budapest, Hungary. 2012 pp. 247-258. doi:10.4230/LIPIcs.ICLP.2012.247.
• [17] Barilaro R, Ricca F, Terracina G. Optimizing the Distributed Evaluation of Stratified Programs via Structural Analysis. In: Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR. Proceedings. 2011 pp. 217-222. doi:10.1007/978-3-642-20895-9\_22.
• [18] Calimeri F, Faber W, Gebser M, Ianni G, Kaminski R, Krennwallner T, Leone N, Ricca F, Schaub T. ASP-Core-2 Input Language Format v2.03c, 2015. Accessed: 2016-06-27, URL https://www.mat.unical.it/aspcomp2013/ASPStandardization.
• [19] Calimeri F, Gebser M, Maratea M, Ricca F. Design and results of the Fifth Answer Set Programming Competition. Artif. Intell., 2016. 231:151-181. doi:10.1016/j.artint.2015.09.008.
• [20] Bichler M, Morak M, Woltran S. lpopt: A Rule Optimization Tool for Answer Set Programming. In: Logic-Based Program Synthesis and Transformation - 26th International Symposium, LOPSTR 2016, Edinburgh, UK, September 6-8, 2016, Revised Selected Papers. 2016 pp. 114-130. doi:10.1007/978-3-319-63139-4\_7.
• [21] Calimeri F, Perri S, Zangari J. Optimizing Answer Set Computation via Heuristic-Based Decomposition. Theory Pract. Log. Program., 2019. 19(4):603-628. doi:10.1017/S1471068419000036.
• [22] Arnborg S, Corneil DG, Proskurowski A. Complexity of Finding Embeddings in a K-tree. SIAM J. Algeb. Discr. Meth., 1987. 8(2):277-284. doi:10.1137/0608024.
• [23] Bodlaender HL. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J. Comput., 1996. 25(6):1305-1317. doi:10.1137/S0097539793251219.
• [24] Bichler M. Optimizing Non-Ground Answer Set Programs via Rule Decomposition. BSc Thesis, TU Wien. http://dbai.tuwien.ac.at/proj/lpopt, 2015.
• [25] Bodlaender HL, Koster AMCA. Treewidth computations I. Upper bounds. Inf. Comput., 2010. 208(3):259-275. doi:10.1016/j.ic.2009.03.008.
• [26] Abseher M, Musliu N, Woltran S. htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond. In: Integration of AI and OR Techniques in Constraint Programming - 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings. 2017 pp. 376-386. doi:10.1007/978-3-319-59776-8\_30.
• [27] Gebser M, Kaufmann B, Schaub T. Conflict-driven answer set solving: From theory to practice. Artif. Intell., 2012. 187:52-89. doi:10.1016/j.artint.2012.04.001.
• [28] Gebser M, Kaminski R, Kaufmann B, Romero J, Schaub T. Progress in clasp Series 3. In: Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR. Proceedings. 2015 pp. 368-383. doi:10.1007/978-3-319-23264-5\_31.
• [29] Heißenberger G. A System for Advanced Graphical Argumentation Formalisms. Master’s thesis, TU Wien, 2016. URL www.dbai.tuwien.ac.at/proj/adf/grappavis/.
• [30] Brewka G, Woltran S. GRAPPA: A Semantical Framework for Graph-Based Argument Processing. In: ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014). 2014 pp. 153-158. doi:10.3233/978-1-61499-419-0-153.
• [31] Diller M. Realising Argumentation using Answer Set Programming and Quantified Boolean Formulas. Ph.D. thesis, TU Wien, 2019. URL http://katalog.ub.tuwien.ac.at/AC15366124.
• [32] Brewka G, Diller M, Heissenberger G, Linsbichler T, Woltran S. Solving Advanced Argumentation Problems with Answer Set Programming. Theory Pract. Log. Program., 2020. 20(3):391-431. doi: 10.1017/S1471068419000474.
• [33] Bichler M, Morak M, Woltran S. The power of non-ground rules in Answer Set Programming. Theory Pract. Log. Program., 2016. 16(5-6):552-569. doi:10.1017/S1471068416000338.
• [34] Bichler M, Morak M, Woltran S. selp: A Single-Shot Epistemic Logic Program Solver. Theory Pract. Log. Program., 2020. 20(4):435-455. doi:10.1017/S1471068420000022.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).