×

Multi-shot ASP solving with clingo. (English) Zbl 1486.68027

Summary: We introduce a new flexible paradigm of grounding and solving in Answer Set Programming (ASP), which we refer to as multi-shot ASP solving, and present its implementation in the ASP system clingo. Multi-shot ASP solving features grounding and solving processes that deal with continuously changing logic programs. In doing so, they remain operative and accommodate changes in a seamless way. For instance, such processes allow for advanced forms of search, as in optimization or theory solving, or interaction with an environment, as in robotics or query answering. Common to them is that the problem specification evolves during the reasoning process, either because data or constraints are added, deleted, or replaced. This evolutionary aspect adds another dimension to ASP since it brings about state changing operations. We address this issue by providing an operational semantics that characterizes grounding and solving processes in multi-shot ASP solving. This characterization provides a semantic account of grounder and solver states along with the operations manipulating them. The operative nature of multi-shot solving avoids redundancies in relaunching grounder and solver programs and benefits from the solver’s learning capacities. clingo accomplishes this by complementing ASP’s declarative input language with control capacities. On the declarative side, a new directive allows for structuring logic programs into named and parameterizable subprograms. The grounding and integration of these subprograms into the solving process is completely modular and fully controllable from the procedural side. To this end, clingo offers a new application programming interface that is conveniently accessible via scripting languages. By strictly separating logic and control, clingo also abolishes the need for dedicated systems for incremental and reactive reasoning, like iclingo and oclingo, respectively, and its flexibility goes well beyond the advanced yet still rigid solving processes of the latter.

MSC:

68N17 Logic programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] AbiteboulS., HullR. and VianuV.1995. Foundations of Databases. Addison-Wesley. · Zbl 0848.68031
[2] AbseherM., BliemB., CharwatG., DusbergerF., HecherM. and WoltranS.2014. The D-FLAT system for dynamic programming on tree decompositions. In Proc. of the 14th European Conference on Logics in Artificial Intelligence (JELIA’14), E.Fermé and J.Leite, Eds. Lecture Notes in Artificial Intelligence, vol. 8761. Springer-Verlag, 558-572. · Zbl 1432.68053
[3] AlferesJ., PereiraL., PrzymusinskaH. and PrzymusinskiT.2002. LUPS: A language for updating logic programs. Artificial Intelligence138, 1-2, 87-116.10.1016/S0004-3702(02)00183-2 · Zbl 0995.68023
[4] AlvianoM., DodaroC., LeoneN. and RiccaF.2015. Advances in WASP. Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’15), CalimeriF., IanniG. and TruszczyńskiM., Eds. Lecture Notes in Artificial Intelligence, vol. 9345. Springer-Verlag, 40-54. · Zbl 1467.68021
[5] AlvianoM., FaberW. and GebserM.2015. Rewriting recursive aggregates in answer set programming: Back to monotonicity. Theory and Practice of Logic Programming15, 4-5, 559-573. URL: http://arxiv.org/abs/1507.03923.10.1017/S1471068415000228S1471068415000228 · Zbl 1379.68034
[6] AlvianoM. and LeoneN.2015. Complexity and compilation of GZ-aggregates in answer set programming. Theory and Practice of Logic Programming15, 4-5, 574-587.10.1017/S147106841500023XS147106841500023X · Zbl 1379.68035
[7] AndresB., KaufmannB., MatheisO. and SchaubT.2012. Unsatisfiability-based optimization in clasp. In Proc. of Technical Communications of the 28th International Conference on Logic Programming (ICLP’12), A.Dovier and V. SantosCosta, Eds., Leibniz International Proceedings in Informatics (LIPIcs), vol. 17. University of Potsdam, 212-221. · Zbl 1281.68204
[8] AndresB., RajaratnamD., SabuncuO. and SchaubT.2015. Integrating ASP into ROS for reasoning in robots. See Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’15), CalimeriF., IanniG. and TruszczyńskiM., Eds. Lecture Notes in Artificial Intelligence, vol. 9345. Springer-Verlag, 69-82. · Zbl 1467.68187
[9] BalducciniM. and JanhunenT., Eds. 2017. Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’17). Lecture Notes in Artificial Intelligence, vol. 10377. Springer-Verlag.
[10] BanbaraM., KaufmannB., OstrowskiM. and SchaubT.2017. Clingcon: The next generation. Theory and Practice of Logic Programming17, 4, 408-461.10.1017/S1471068417000138 · Zbl 1379.68040
[11] BaralC.2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. · Zbl 1056.68139
[12] BrewkaG., DelgrandeJ., RomeroJ. and SchaubT.2015a. asprin: Customizing answer set preferences without a headache. In Proc. of the 29th National Conference on Artificial Intelligence (AAAI’15), B.Bonet and S.Koenig, Eds. AAAI Press, 1467-1474.
[13] BrewkaG., DelgrandeJ., RomeroJ. and SchaubT.2015b. Implementing preferences with asprin. In Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’15), CalimeriF., IanniG. and TruszczyńskiM., Eds. Lecture Notes in Artificial Intelligence, vol. 9345. Springer-Verlag, 158-172. · Zbl 1467.68022
[14] BrewkaG., EiterT. and McIlraithS., Eds. 2012. Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR’12). AAAI Press.
[15] CabalarP. and SonT., Eds. 2013. Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13). Lecture Notes in Artificial Intelligence, vol. 8148. Springer-Verlag.
[16] CalimeriF., CozzaS. and IanniG.2007. External sources of knowledge and value invention in logic programming. Annals of Mathematics and Artificial Intelligence50, 3-4, 333-361.10.1007/s10472-007-9076-z · Zbl 1125.68026
[17] CalimeriF., FaberW., GebserM., IanniG., KaminskiR., KrennwallnerT., LeoneN., RiccaF. and SchaubT.2012. ASP-Core-2: Input language format [online]. URL: https://www.mat.unical.it/aspcomp2013/ASPStandardization.
[18] CalimeriF., IanniG. and TruszczyńskiM., Eds. 2015. Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’15). Lecture Notes in Artificial Intelligence, vol. 9345. Springer-Verlag.
[19] De CatB., BogaertsB., BruynoogheM. and DeneckerM.2014. Predicate logic as a modelling language: The IDP system. arXiv:1401.6312.
[20] de MouraL. and BjørnerN.2008. Z3: An efficient SMT solver. In Proc. of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’08), C.Ramakrishnan and J.Rehof, Eds. Lecture Notes in Computer Science, vol. 4963. Springer-Verlag, 337-340.
[21] De PooterS., WittocxJ. and DeneckerM.2013. A prototype of a knowledge-based programming environment. In Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management (INAP’11) and the 25th Workshop on Logic Programming (WLP’11), H.Tompits, S.Abreu, J.Oetsch, J.Pührer, D.Seipel, M.Umeda, and A.Wolf, Eds. Lecture Notes in Computer Science, vol. 7773. Springer-Verlag, 279-286.
[22] DelgrandeJ. and FaberW., Eds. 2011. Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’11). Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag.
[23] DelgrandeJ., SchaubT., TompitsH. and WoltranS.2008. Belief revision of logic programs under answer set semantics. In Proc. of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR’08), G.Brewka and J.Lang, Eds. AAAI Press, 411-421. · Zbl 1251.68057
[24] DelgrandeJ., SchaubT., TompitsH. and WoltranS.2009. Merging logic programs under answer set semantics. In Proc. of the 25th International Conference on Logic Programming (ICLP’09), P.Hill and D.Warren, Eds. Lecture Notes in Computer Science, vol. 5649. Springer-Verlag, 160-174. · Zbl 1251.68057
[25] DimopoulosY., GebserM., LühneP., RomeroJ. and SchaubT.2017. plasp 3: Towards effective ASP planning. In Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’17), Balduccini, M. and Janhunen, T., Eds. Lecture Notes in Artificial Intelligence, vol. 10377. Springer-Verlag, 286-300. · Zbl 1491.68190
[26] DodaroC., GasteigerP., LeoneN., MusitschB., RiccaF. and SchekotihinK.2016. Driving CDCL search. arXiv:1611.05190.
[27] DodaroC., RiccaF. and SchüllerP.2016. External propagators in wasp: Preliminary report. In Proc. of the 23rd International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA’16), CEUR Workshop Proceedings, vol. 1745, 1-9.
[28] EénN. and SörenssonN.2003. Temporal induction by incremental SAT solving. Electronic Notes in Theoretical Computer Science89, 4, 543-560.10.1016/S1571-0661(05)82542-3 · Zbl 1271.68215
[29] EénN. and SörenssonN.2004. An extensible SAT-solver. In Proc. of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT’03), E.Giunchiglia and A.Tacchella, Eds. Lecture Notes in Computer Science, vol. 2919. Springer-Verlag, 502-518.
[30] EiterT., FinkM., KrennwallnerT. and RedlC.2012. Conflict-driven ASP solving with external sources. Theory and Practice of Logic Programming12, 4-5, 659-679.10.1017/S1471068412000233S1471068412000233 · Zbl 1260.68060
[31] FebbraroO., LeoneN., GrassoG. and RiccaF.2012. JASP: A framework for integrating answer set programming with Java. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR’12)BrewkaG., EiterT. and McIlraithS., Eds. AAAI Press, 541-551.
[32] FinkM., GermanoS., IanniG., RedlC. and SchüllerP.2013. ActHEX: Implementing HEX programs with action atoms. In Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13), CabalarP. and SonT., Eds. Lecture Notes in Artificial Intelligence, vol. 8148. Springer-Verlag, 317-322.
[33] FuscàD., GermanoS., ZangariJ., AnastasioM., CalimeriF. and PerriS.2016. A framework for easing the development of applications embedding answer set programming. In Proc. of the 18th International Symposium on Principles and Practice of Declarative Programming (PPDP’16), J.Cheney and G.Vidal, Eds. ACM Press, 38-49.
[34] GebserM., GroteT., KaminskiR., ObermeierP., SabuncuO. and SchaubT.2012. Stream reasoning with answer set programming: Preliminary report. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR’12)BrewkaG., EiterT. and McIlraithS., Eds. AAAI Press, 613-617.
[35] GebserM., GroteT., KaminskiR. and SchaubT.2011. Reactive answer set programming. In Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR ’11). DelgrandeJ. and FaberW., Eds. Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag, 54-66. · Zbl 1327.68063
[36] GebserM., HarrisonA., KaminskiR., LifschitzV. and SchaubT.2015. Abstract Gringo. Theory and Practice of Logic Programming15, 4-5, 449-463. URL: http://arxiv.org/abs/1507.06576.10.1017/S1471068415000150S1471068415000150 · Zbl 1379.68031
[37] GebserM., JostH., KaminskiR., ObermeierP., SabuncuO., SchaubT. and SchneiderM.2013. Ricochet robots: A transverse ASP benchmark. In. Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13). CabalarP. and SonT., Eds. Lecture Notes in Artificial Intelligence, vol. 8148. Springer-Verlag, 348-360.
[38] GebserM., KaminskiR., KaufmannB., LindauerM., OstrowskiM., RomeroJ., SchaubT. and ThieleS.2015. Potassco User Guide, 2nd ed.University of Potsdam.
[39] GebserM., KaminskiR., KaufmannB., OstrowskiM., SchaubT. and SchneiderM.2011. Potassco: The Potsdam answer set solving collection. AI Communications24, 2, 107-124. · Zbl 1215.68214
[40] GebserM., KaminskiR., KaufmannB., OstrowskiM., SchaubT. and ThieleS.2008. Engineering an incremental ASP solver. In Proc. of the 24th International Conference on Logic Programming (ICLP’08), M. Garciade la Banda and E.Pontelli, Eds. Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, 190-205. · Zbl 1185.68159
[41] GebserM., KaminskiR., KaufmannB., OstrowskiM., SchaubT. and WankoP.2016. Theory solving made easy with clingo 5. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP’16), M.Carro and A.King, Eds., Open Access Series in Informatics (OASIcs), vol. 52, 2:1-2:15.
[42] GebserM., KaminskiR., KaufmannB. and SchaubT.2012. Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers. · Zbl 1251.68060
[43] GebserM., KaminskiR., KaufmannB. and SchaubT.2014. Clingo = ASP + control: Preliminary report. In Proc. of Technical Communications of the 30th International Conference on Logic Programming (ICLP’14), M.Leuschel and T.Schrijvers, Eds. Theory and Practice of Logic Programming, Online Supplement, vol. 14(4-5). URL: http://arxiv.org/abs/1405.3694v1.
[44] GebserM., KaminskiR., KönigA. and SchaubT.2011. Advances in gringo series 3. In Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR ’11). DelgrandeJ. and FaberW., Eds. Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag, 345-351.
[45] GebserM., KaminskiR., ObermeierP. and SchaubT.2015. Ricochet robots reloaded: A case-study in multi-shot ASP solving. In Proc. of Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation: Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday, T.Eiter, H.Strass, M.Truszczyński, and S.Woltran, Eds. Lecture Notes in Artificial Intelligence, vol. 9060. Springer-Verlag, 17-32. · Zbl 1432.68414
[46] GebserM., KaufmannB., OteroR., RomeroJ., SchaubT. and WankoP.2013. Domain-specific heuristics in answer set programming. In Proc. of the 27th National Conference on Artificial Intelligence (AAAI’13), M.desJardins and M.Littman, Eds. AAAI Press, 350-356.
[47] GebserM., KaufmannB. and SchaubT.2013. Advanced conflict-driven disjunctive answer set solving. In Proc. of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13), F.Rossi, Ed. IJCAI/AAAI Press, 912-918.
[48] GebserM., ObermeierP. and SchaubT.2013. A system for interactive query answering with answer set programming. In Proc. of the 6th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP’13), M.Fink and Y.Lierler, Eds. Vol. abs/1312.6143. CoRR.
[49] GelfondM. and LifschitzV.1988. The stable model semantics for logic programming. In Proc. of the 5th International Conference and Symposium of Logic Programming (ICLP’88), R.Kowalski and K.Bowen, Eds. MIT Press, 1070-1080.
[50] JanhunenT., KaminskiR., OstrowskiM., SchaubT., SchellhornS. and WankoP.2017. Clingo goes linear constraints over reals and integers. Theory and Practice of Logic Programming17, 5-6, 872-888.10.1017/S1471068417000242S1471068417000242 · Zbl 1422.68024
[51] KaminskiR., SchaubT. and WankoP.2017. A tutorial on hybrid answer set solving with clingo. In Proc. of the 13th International Summer School of the Reasoning Web, G.Ianni, D.Lembo, L.Bertossi, W.Faber, B.Glimm, G.Gottlob, and S.Staab, Eds. Lecture Notes in Computer Science, vol. 10370. Springer-Verlag, 167-203.
[52] KaufmannB., LeoneN., PerriS. and SchaubT.2016. Grounding and solving in answer set programming. AI Magazine37, 3, 25-32.10.1609/aimag.v37i3.2672
[53] LeoneN., PfeiferG., FaberW., EiterT., GottlobG., PerriS. and ScarcelloF.2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic7, 3, 499-562.10.1145/1149114.1149117 · Zbl 1367.68308
[54] LifschitzV. and TurnerH.1994. Splitting a logic program. In Proc. of the 11th International Conference on Logic Programming. MIT Press, 23-37.
[55] NieuwenhuisR., OliverasA. and TinelliC.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.10.1145/1217856.1217859 · Zbl 1326.68164
[56] OikarinenE. and JanhunenT.2006. Modular equivalence for normal logic programs. In Proc. of the 17th European Conference on Artificial Intelligence (ECAI’06), G.Brewka, S.Coradeschi, A.Perini, and P.Traverso, Eds. IOS Press, 412-416.
[57] OstrowskiM. and SchaubT.2012. ASP modulo CSP: The clingcon system. Theory and Practice of Logic Programming12, 4-5, 485-503.10.1017/S1471068412000142S1471068412000142 · Zbl 1260.68066
[58] SabuncuO. and LeiteJ.2017. moviola: Interpreting dynamic logic programs via multi-shot answer set programming. In Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’17), BalducciniM. and JanhunenT., Eds. Lecture Notes in Artificial Intelligence, vol. 10377. Springer-Verlag, 336-342. · Zbl 1491.68048
[59] SimonsP., NiemeläI. and SoininenT.2002. Extending and implementing the stable model semantics. Artificial Intelligence138, 1-2, 181-234.10.1016/S0004-3702(02)00187-X · Zbl 0995.68021
[60] SyrjänenT.2001. Lparse 1.0 user’s manual.
[61] ZhangY. and FooN.2006. Solving logic program conflict through strong and weak forgettings. Artificial Intelligence170, 8-9, 739-778.10.1016/j.artint.2006.02.002 · Zbl 1131.68037
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.