Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-24T17:26:18.841Z Has data issue: false hasContentIssue false
  • English
  • Français

Multi-shot ASP solving with clingo

Published online by Cambridge University Press:  10 July 2018

MARTIN GEBSER ,
ROLAND KAMINSKI ,
BENJAMIN KAUFMANN  and
TORSTEN SCHAUB Open the ORCID record for TORSTEN SCHAUB [Opens in a new window]
MARTIN GEBSER
Affiliation:
University of Potsdam, Germany
ROLAND KAMINSKI
Affiliation:
University of Potsdam, Germany
BENJAMIN KAUFMANN
Affiliation:
University of Potsdam, Germany
TORSTEN SCHAUB
Affiliation:
INRIA Rennes, France University of Potsdam, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 19 , Issue 1 , January 2019 , pp. 27 - 82
Copyright
Copyright © Cambridge University Press 2018 

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

We are grateful to Evgenii Balai, Javier Romero, and Adam Smith for many fruitful discussions on the paper. This work was partially funded by DFG Grant SCHA 550/9.

References

Abiteboul, S., Hull, R. and Vianu, V. 1995. Foundations of Databases. Addison-Wesley.Google Scholar
Abseher, M., Bliem, B., Charwat, G., Dusberger, F., Hecher, M. and Woltran, S. 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), Fermé, E. and Leite, J., Eds. Lecture Notes in Artificial Intelligence, vol. 8761. Springer-Verlag, 558–572.Google Scholar
Alferes, J., Pereira, L., Przymusinska, H. and Przymusinski, T. 2002. LUPS: A language for updating logic programs. Artificial Intelligence 138, 1–2, 87–116.Google Scholar
Alviano, M., Dodaro, C., Leone, N. and Ricca, F. 2015. Advances in WASP. Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'15), Calimeri, F., Ianni, G. and Truszczyński, M., Eds. Lecture Notes in Artificial Intelligence, vol. 9345. Springer-Verlag, 40–54.Google Scholar
Alviano, M., Faber, W. and Gebser, M. 2015. Rewriting recursive aggregates in answer set programming: Back to monotonicity. Theory and Practice of Logic Programming 15, 4–5, 559–573. URL: http://arxiv.org/abs/1507.03923.Google Scholar
Alviano, M. and Leone, N. 2015. Complexity and compilation of GZ-aggregates in answer set programming. Theory and Practice of Logic Programming 15, 4–5, 574–587.Google Scholar
Andres, B., Kaufmann, B., Matheis, O. and Schaub, T. 2012. Unsatisfiability-based optimization in clasp. In Proc. of Technical Communications of the 28th International Conference on Logic Programming (ICLP'12), Dovier, A. and Costa, V. Santos, Eds., Leibniz International Proceedings in Informatics (LIPIcs), vol. 17. University of Potsdam, 212–221.Google Scholar
Andres, B., Rajaratnam, D., Sabuncu, O. and Schaub, T. 2015. Integrating ASP into ROS for reasoning in robots. See Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'15), Calimeri, F., Ianni, G. and Truszczyński, M., Eds. Lecture Notes in Artificial Intelligence, vol. 9345. Springer-Verlag, 69–82.Google Scholar
Balduccini, M. and Janhunen, T., 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.Google Scholar
Banbara, M., Kaufmann, B., Ostrowski, M. and Schaub, T. 2017. Clingcon: The next generation. Theory and Practice of Logic Programming 17, 4, 408–461.Google Scholar
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press.Google Scholar
Brewka, G., Delgrande, J., Romero, J. and Schaub, T. 2015a. asprin: Customizing answer set preferences without a headache. In Proc. of the 29th National Conference on Artificial Intelligence (AAAI'15), Bonet, B. and Koenig, S., Eds. AAAI Press, 1467–1474.Google Scholar
Brewka, G., Delgrande, J., Romero, J. and Schaub, T. 2015b. Implementing preferences with asprin. In Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'15), Calimeri, F., Ianni, G. and Truszczyński, M., Eds. Lecture Notes in Artificial Intelligence, vol. 9345. Springer-Verlag, 158–172.Google Scholar
Brewka, G., Eiter, T. and McIlraith, S., Eds. 2012. Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR'12). AAAI Press.Google Scholar
Cabalar, P. and Son, T., 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.Google Scholar
Calimeri, F., Cozza, S. and Ianni, G. 2007. External sources of knowledge and value invention in logic programming. Annals of Mathematics and Artificial Intelligence 50, 3–4, 333–361.Google Scholar
Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Ricca, F. and Schaub, T. 2012. ASP-Core-2: Input language format [online]. URL: https://www.mat.unical.it/aspcomp2013/ASPStandardization.Google Scholar
Calimeri, F., Ianni, G. and Truszczyński, M., 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.Google Scholar
De Cat, B., Bogaerts, B., Bruynooghe, M. and Denecker, M. 2014. Predicate logic as a modelling language: The IDP system. arXiv:1401.6312.Google Scholar
de Moura, L. and Bjørner, N. 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), Ramakrishnan, C. and Rehof, J., Eds. Lecture Notes in Computer Science, vol. 4963. Springer-Verlag, 337–340.Google Scholar
De Pooter, S., Wittocx, J. and Denecker, M. 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), Tompits, H., Abreu, S., Oetsch, J., Pührer, J., Seipel, D., Umeda, M., and Wolf, A., Eds. Lecture Notes in Computer Science, vol. 7773. Springer-Verlag, 279–286.Google Scholar
Delgrande, J. and Faber, W., 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.Google Scholar
Delgrande, J., Schaub, T., Tompits, H. and Woltran, S. 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), Brewka, G. and Lang, J., Eds. AAAI Press, 411–421.Google Scholar
Delgrande, J., Schaub, T., Tompits, H. and Woltran, S. 2009. Merging logic programs under answer set semantics. In Proc. of the 25th International Conference on Logic Programming (ICLP'09), Hill, P. and Warren, D., Eds. Lecture Notes in Computer Science, vol. 5649. Springer-Verlag, 160–174.Google Scholar
Dimopoulos, Y., Gebser, M., Lühne, P., Romero, J. and Schaub, T. 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.Google Scholar
Dodaro, C., Gasteiger, P., Leone, N., Musitsch, B., Ricca, F. and Schekotihin, K. 2016. Driving CDCL search. arXiv:1611.05190.Google Scholar
Dodaro, C., Ricca, F. and Schüller, P. 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.Google Scholar
Eén, N. and Sörensson, N. 2003. Temporal induction by incremental SAT solving. Electronic Notes in Theoretical Computer Science 89, 4, 543–560.Google Scholar
Eén, N. and Sörensson, N. 2004. An extensible SAT-solver. In Proc. of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT'03), Giunchiglia, E. and Tacchella, A., Eds. Lecture Notes in Computer Science, vol. 2919. Springer-Verlag, 502–518.Google Scholar
Eiter, T., Fink, M., Krennwallner, T. and Redl, C. 2012. Conflict-driven ASP solving with external sources. Theory and Practice of Logic Programming 12, 4–5, 659–679.Google Scholar
Febbraro, O., Leone, N., Grasso, G. and Ricca, F. 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) Brewka, G., Eiter, T. and McIlraith, S., Eds. AAAI Press, 541–551.Google Scholar
Fink, M., Germano, S., Ianni, G., Redl, C. and Schüller, P. 2013. ActHEX: Implementing HEX programs with action atoms. In Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13), Cabalar, P. and Son, T., Eds. Lecture Notes in Artificial Intelligence, vol. 8148. Springer-Verlag, 317–322.Google Scholar
Fuscà, D., Germano, S., Zangari, J., Anastasio, M., Calimeri, F. and Perri, S. 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), Cheney, J. and Vidal, G., Eds. ACM Press, 38–49.Google Scholar
Gebser, M., Grote, T., Kaminski, R., Obermeier, P., Sabuncu, O. and Schaub, T. 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) Brewka, G., Eiter, T. and McIlraith, S., Eds. AAAI Press, 613–617.Google Scholar
Gebser, M., Grote, T., Kaminski, R. and Schaub, T. 2011. Reactive answer set programming. In Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR '11). Delgrande, J. and Faber, W., Eds. Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag, 54–66.Google Scholar
Gebser, M., Harrison, A., Kaminski, R., Lifschitz, V. and Schaub, T. 2015. Abstract Gringo. Theory and Practice of Logic Programming 15, 4–5, 449–463. URL: http://arxiv.org/abs/1507.06576.Google Scholar
Gebser, M., Jost, H., Kaminski, R., Obermeier, P., Sabuncu, O., Schaub, T. and Schneider, M. 2013. Ricochet robots: A transverse ASP benchmark. In. Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13). Cabalar, P. and Son, T., Eds. Lecture Notes in Artificial Intelligence, vol. 8148. Springer-Verlag, 348–360.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Lindauer, M., Ostrowski, M., Romero, J., Schaub, T. and Thiele, S. 2015. Potassco User Guide, 2nd ed. University of Potsdam.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T. and Schneider, M. 2011. Potassco: The Potsdam answer set solving collection. AI Communications 24, 2, 107–124.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T. and Thiele, S. 2008. Engineering an incremental ASP solver. In Proc. of the 24th International Conference on Logic Programming (ICLP'08), de la Banda, M. Garcia and Pontelli, E., Eds. Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, 190–205.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T. and Wanko, P. 2016. Theory solving made easy with clingo 5. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP'16), Carro, M. and King, A., Eds., Open Access Series in Informatics (OASIcs), vol. 52, 2:1–2:15.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B. and Schaub, T. 2012. Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B. and Schaub, T. 2014. Clingo = ASP + control: Preliminary report. In Proc. of Technical Communications of the 30th International Conference on Logic Programming (ICLP'14), Leuschel, M. and Schrijvers, T., Eds. Theory and Practice of Logic Programming, Online Supplement, vol. 14(4–5). URL: http://arxiv.org/abs/1405.3694v1.Google Scholar
Gebser, M., Kaminski, R., König, A. and Schaub, T. 2011. Advances in gringo series 3. In Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR '11). Delgrande, J. and Faber, W., Eds. Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag, 345–351.Google Scholar
Gebser, M., Kaminski, R., Obermeier, P. and Schaub, T. 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, Eiter, T., Strass, H., Truszczyński, M., and Woltran, S., Eds. Lecture Notes in Artificial Intelligence, vol. 9060. Springer-Verlag, 17–32.Google Scholar
Gebser, M., Kaufmann, B., Otero, R., Romero, J., Schaub, T. and Wanko, P. 2013. Domain-specific heuristics in answer set programming. In Proc. of the 27th National Conference on Artificial Intelligence (AAAI'13), desJardins, M. and Littman, M., Eds. AAAI Press, 350–356.Google Scholar
Gebser, M., Kaufmann, B. and Schaub, T. 2013. Advanced conflict-driven disjunctive answer set solving. In Proc. of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13), Rossi, F., Ed. IJCAI/AAAI Press, 912–918.Google Scholar
Gebser, M., Obermeier, P. and Schaub, T. 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), Fink, M. and Lierler, Y., Eds. Vol. abs/1312.6143. CoRR.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of the 5th International Conference and Symposium of Logic Programming (ICLP'88), Kowalski, R. and Bowen, K., Eds. MIT Press, 1070–1080.Google Scholar
Janhunen, T., Kaminski, R., Ostrowski, M., Schaub, T., Schellhorn, S. and Wanko, P. 2017. Clingo goes linear constraints over reals and integers. Theory and Practice of Logic Programming 17, 5–6, 872–888.Google Scholar
Kaminski, R., Schaub, T. and Wanko, P. 2017. A tutorial on hybrid answer set solving with clingo. In Proc. of the 13th International Summer School of the Reasoning Web, Ianni, G., Lembo, D., Bertossi, L., Faber, W., Glimm, B., Gottlob, G., and Staab, S., Eds. Lecture Notes in Computer Science, vol. 10370. Springer-Verlag, 167–203.Google Scholar
Kaufmann, B., Leone, N., Perri, S. and Schaub, T. 2016. Grounding and solving in answer set programming. AI Magazine 37, 3, 25–32.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, 499–562.Google Scholar
Lifschitz, V. and Turner, H. 1994. Splitting a logic program. In Proc. of the 11th International Conference on Logic Programming. MIT Press, 23–37.Google Scholar
Nieuwenhuis, R., Oliveras, A. and Tinelli, C. 2006. Solving SAT and SAT modulo theories: From an abstract Davis–Putnam–Logemann–Loveland procedure to DPLL(T). Journal of the ACM 53, 6, 937–977.Google Scholar
Oikarinen, E. and Janhunen, T. 2006. Modular equivalence for normal logic programs. In Proc. of the 17th European Conference on Artificial Intelligence (ECAI'06), Brewka, G., Coradeschi, S., Perini, A., and Traverso, P., Eds. IOS Press, 412–416.Google Scholar
Ostrowski, M. and Schaub, T. 2012. ASP modulo CSP: The clingcon system. Theory and Practice of Logic Programming 12, 4–5, 485–503.Google Scholar
Sabuncu, O. and Leite, J. 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), Balduccini, M. and Janhunen, T., Eds. Lecture Notes in Artificial Intelligence, vol. 10377. Springer-Verlag, 336–342.Google Scholar
Simons, P., Niemelä, I. and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 1–2, 181–234.Google Scholar
Syrjänen, T. 2001. Lparse 1.0 user's manual.Google Scholar
Zhang, Y. and Foo, N. 2006. Solving logic program conflict through strong and weak forgettings. Artificial Intelligence 170, 8–9, 739–778.Google Scholar