Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Answer Set Solving with Generalized Learned Constraints

Authors Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Patrick Lühne, Javier Romero, Torsten Schaub

PDF
Thumbnail PDF

File

OASIcs.ICLP.2016.9.pdf
  • Filesize: 0.77 MB
  • 15 pages

Document Identifiers

Author Details

Martin Gebser
Roland Kaminski
Benjamin Kaufmann
Patrick Lühne
Javier Romero
Torsten Schaub

Cite AsGet BibTex

Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Patrick Lühne, Javier Romero, and Torsten Schaub. Answer Set Solving with Generalized Learned Constraints. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016). Open Access Series in Informatics (OASIcs), Volume 52, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/OASIcs.ICLP.2016.9

Abstract

Conflict learning plays a key role in modern Boolean constraint solving. Advanced in satisfiability testing, it has meanwhile become a base technology in many neighboring fields, among them answer set programming (ASP). However, learned constraints are only valid for a currently solved problem instance and do not carry over to similar instances. We address this issue in ASP and introduce a framework featuring an integrated feedback loop that allows for reusing conflict constraints. The idea is to extract (propositional) conflict constraints, generalize and validate them, and reuse them as integrity constraints. Although we explore our approach in the context of dynamic applications based on transition systems, it is driven by the ultimate objective of overcoming the issue that learned knowledge is bound to specific problem instances. We implemented this workflow in two systems, namely, a variant of the ASP solver clasp that extracts integrity constraints along with a downstream system for generalizing and validating them.
Keywords
  • Answer Set Programming
  • Conflict Learning
  • Constraint Generalization
  • Generalized Constraint Feedback

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Alviano, C. Dodaro, N. Leone, and F. Ricca. Advances in WASP. In F. Calimeri, G. Ianni, and M. Truszczyński, editors, Proceedings of the Thirteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'15), pages 40-54. Springer, 2015. Google Scholar
  2. A. Biere, M. Heule, H. van Maaren, and T. Walsh, editors. Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications. IOS Press, 2009. Google Scholar
  3. G. Brewka, T. Eiter, and M. Truszczyński. Answer set programming at a glance. Communications of the ACM, 54(12):92-103, 2011. Google Scholar
  4. F. Calimeri, W. Faber, M. Gebser, G. Ianni, R. Kaminski, T. Krennwallner, N. Leone, F. Ricca, and T. Schaub. ASP-Core-2: Input language format. Available at https://www.mat.unical.it/aspcomp2013/ASPStandardization/, 2012.
  5. J. Charnley, S. Colton, and I. Miguel. Automated generation of implied constraints. In G. Brewka, S. Coradeschi, A. Perini, and P. Traverso, editors, Proceedings of the Seventeenth European Conference on Artificial Intelligence (ECAI'06), pages 73-77. IOS Press, 2006. Google Scholar
  6. M. Dao-Tran, T. Eiter, M. Fink, G. Weidinger, and A. Weinzierl. OMiGA : An open minded grounding on-the-fly answer set solver. In L. Fariñas del Cerro, A. Herzig, and J. Mengin, editors, Proceedings of the Thirteenth European Conference on Logics in Artificial Intelligence (JELIA'12), pages 480-483. Springer, 2012. Google Scholar
  7. B. De Cat and M. Bruynooghe. Detection and exploitation of functional dependencies for model generation. Theory and Practice of Logic Programming, 13(4-5):471-485, 2013. Google Scholar
  8. R. Dechter. Constraint Processing. Morgan Kaufmann Publishers, 2003. Google Scholar
  9. M. Gebser, R. Kaminski, B. Kaufmann, P. Lühne, J. Romero, and T. Schaub. Answer set solving with generalized learned constraints (extended version). Available at http://www.cs.uni-potsdam.de/wv/publications/, 2016.
  10. M. Gebser, R. Kaminski, M. Knecht, and T. Schaub. plasp: A prototype for PDDL-based planning in ASP. In J. Delgrande and W. Faber, editors, Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11), pages 358-363. Springer, 2011. Google Scholar
  11. M. Gebser, B. Kaufmann, and T. Schaub. Conflict-driven answer set solving: From theory to practice. Artificial Intelligence, 187-188:52-89, 2012. Google Scholar
  12. M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive databases. New Generation Computing, 9:365-385, 1991. Google Scholar
  13. E. Giunchiglia, Y. Lierler, and M. Maratea. Answer set programming based on propositional satisfiability. Journal of Automated Reasoning, 36(4):345-377, 2006. Google Scholar
  14. S. Haufe, S. Schiffel, and M. Thielscher. Automated verification of state sequence invariants in general game playing. Artificial Intelligence, 187-188:1-30, 2012. Google Scholar
  15. M. Helmert. Concise finite-domain representations for PDDL planning tasks. Artificial Intelligence, 173(5-6):503-535, 2009. Google Scholar
  16. M. Law, A. Russo, and K. Broda. Inductive learning of answer set programs. In E. Fermé and J. Leite, editors, Proceedings of the Fourteenth European Conference on Logics in Artificial Intelligence (JELIA'14), pages 311-325. Springer, 2014. Google Scholar
  17. V. Lifschitz. Answer set programming and plan generation. Artificial Intelligence, 138(1-2):39-54, 2002. Google Scholar
  18. F. Lin. Discovering state invariants. In D. Dubois, C. Welty, and M. Williams, editors, Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning (KR'04), pages 536-544. AAAI Press, 2004. Google Scholar
  19. P. Lühne. Generalizing learned knowledge in answer set solving. Master’s thesis, Hasso Plattner Institute, Potsdam, 2015. Google Scholar
  20. J. Marques-Silva and K. Sakallah. GRASP: A search algorithm for propositional satisfiability. IEEE Transactions on Computers, 48(5):506-521, 1999. Google Scholar
  21. B. O'Sullivan. Automated modelling and solving in constraint programming. In M. Fox and D. Poole, editors, Proceedings of the Twenty-fourth National Conference on Artificial Intelligence (AAAI'10), pages 1493-1497. AAAI Press, 2010. Google Scholar
  22. R. Otero. Induction of stable models. In C. Rouveirol and M. Sebag, editors, Proceedings of the Eleventh International Conference on Inductive Logic Programming (ILP'01), pages 193-205. Springer, 2001. Google Scholar
  23. J. Rintanen. An iterative algorithm for synthesizing invariants. In Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI'00), pages 806-811. AAAI/MIT Press, 2000. Google Scholar
  24. M. Sheeran, S. Singh, and G. Stålmarck. Checking safety properties using induction and a SAT-solver. In W. Hunt and S. Johnson, editors, Proceedings of the Third International Conference on Formal Methods in Computer-Aided Design (FMCAD'00), pages 108-125. Springer, 2000. Google Scholar
  25. Y. Vizel, G. Weissenbacher, and S. Malik. Boolean satisfiability solvers and their applications in model checking. Proceedings of the IEEE, 103(11):2021-2035, 2015. Google Scholar
  26. A. Weinzierl. Learning non-ground rules for answer-set solving. In D. Pearce, S. Tasharrofi, E. Ternovska, and C. Vidal, editors, Proceedings of the Second Workshop on Grounding and Transformation for Theories with Variables (GTTV'13), pages 25-37, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact