Computing Diverse Optimal Stable Models

Authors Javier Romero, Torsten Schaub, Philipp Wanko



PDF
Thumbnail PDF

File

OASIcs.ICLP.2016.3.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Javier Romero
Torsten Schaub
Philipp Wanko

Cite AsGet BibTex

Javier Romero, Torsten Schaub, and Philipp Wanko. Computing Diverse Optimal Stable Models. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016). Open Access Series in Informatics (OASIcs), Volume 52, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/OASIcs.ICLP.2016.3

Abstract

We introduce a comprehensive framework for computing diverse (or similar) solutions to logic programs with preferences. Our framework provides a wide spectrum of complete and incomplete methods for solving this task. Apart from proposing several new methods, it also accommodates existing ones and generalizes them to programs with preferences. Interestingly, this is accomplished by integrating and automating several basic ASP techniques - being of general interest even beyond diversification. The enabling factor of this lies in the recent advance of multi-shot ASP solving that provides us with fine-grained control over reasoning processes and abolishes the need for solver modifications and wrappers that were indispensable in previous approaches. Our framework is implemented as an extension to the ASP-based preference handling system asprin. We use the resulting system asprin 2 for an empirical evaluation of the diversification methods comprised in our framework.
Keywords
  • Answer Set Programming
  • Diversity
  • Similarity
  • Preferences

Metrics

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

References

  1. asprin. URL: http://www.cs.uni-potsdam.de/asprin.
  2. Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13). Springer, 2013. Google Scholar
  3. B. Andres, M. Gebser, M. Glaß, C. Haubelt, F. Reimann, and T. Schaub. Symbolic system synthesis using answer set programming. In Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13) [2], pages 79-91. Google Scholar
  4. M. Banbara, T. Soh, N. Tamura, K. Inoue, and T. Schaub. Answer set programming as a modeling language for course timetabling. Theory and Practice of Logic Programming, 13(4-5):783-798, 2013. Google Scholar
  5. C. Baral. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, 2003. Google Scholar
  6. G. Brewka, J. Delgrande, J. Romero, and T. Schaub. asprin: Customizing answer set preferences without a headache. In Proceedings of the Twenty-Ninth National Conference on Artificial Intelligence (AAAI'15), pages 1467-1474. AAAI Press, 2015. Google Scholar
  7. G. Brewka, J. Delgrande, J. Romero, and T. Schaub. Implementing preferences with asprin. In Proceedings of the Thirteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'15), pages 158-172. Springer, 2015. Google Scholar
  8. G. Brewka, I. Niemelä, and M. Truszczyński. Answer set optimization. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI'03), pages 867-872. Morgan Kaufmann, 2003. Google Scholar
  9. T. Eiter, E. Erdem, H. Erdogan, and M. Fink. Finding similar/diverse solutions in answer set programming. Theory and Practice of Logic Programming, 13(3):303-359, 2013. Google Scholar
  10. T. Eiter and G. Gottlob. On the computational cost of disjunctive logic programming. Annals of Mathematics and Artificial Intelligence, 15(3-4):289-323, 1995. Google Scholar
  11. T. Eiter and A. Polleres. Towards automated integration of guess and check programs in answer set programming: a meta-interpreter and applications. Theory and Practice of Logic Programming, 6(1-2):23-60, 2006. Google Scholar
  12. M. Gebser, C. Guziolowski, M. Ivanchev, T. Schaub, A. Siegel, S. Thiele, and P. Veber. Repair and prediction (under inconsistency) in large biological networks with answer set programming. In Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR'10), pages 497-507. AAAI Press, 2010. Google Scholar
  13. M. Gebser, R. Kaminski, B. Kaufmann, and T. Schaub. Clingo = ASP + control: Preliminary report. In Technical Communications of the Thirtieth International Conference on Logic Programming (ICLP'14), volume 14 of Theory and Practice of Logic Programming, 2014. Google Scholar
  14. M. Gebser, R. Kaminski, and T. Schaub. Complex optimization in answer set programming. Theory and Practice of Logic Programming, 11(4-5):821-839, 2011. Google Scholar
  15. M. Gebser, B. Kaufmann, R. Otero, J. Romero, T. Schaub, and P. Wanko. Domain-specific heuristics in answer set programming. In Proceedings of the Twenty-Seventh National Conference on Artificial Intelligence (AAAI'13), pages 350-356. AAAI Press, 2013. Google Scholar
  16. M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive databases. New Generation Computing, 9:365-385, 1991. Google Scholar
  17. E. Hebrard, B. Hnich, B. O'Sullivan, and T. Walsh. Finding diverse and similar solutions in constraint programming. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI'05), pages 372-377. AAAI Press, 2005. Google Scholar
  18. A. Nadel. Generating diverse solutions in SAT. In Proceedings of the Fourteenth International Conference on Theory and Applications of Satisfiability Testing (SAT'11), pages 287-301. Springer, 2011. Google Scholar
  19. V. Pareto. Cours d'economie politique. Librairie Droz, 1964. Google Scholar
  20. J. Romero, T. Schaub, and P. Wanko. Computing diverse optimal stable models (extended version). Available at http://www.cs.uni-potsdam.de/wv/publications/, 2016.
  21. T. Schaub and S. Thiele. Metabolic network expansion with ASP. In Proceedings of the Twenty-fifth International Conference on Logic Programming (ICLP'09), pages 312-326. Springer, 2009. Google Scholar
  22. H. Shimazu. Expertclerk: Navigating shoppers' buying process with the combination of asking and proposing. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI'01), pages 1443-1448. Morgan Kaufmann, 2001. Google Scholar
  23. S. Siddiqi. Computing minimum-cardinality diagnoses by model relaxation. In Proceedings of the Twenty-second International Joint Conference on Artificial Intelligence (IJCAI'11), pages 1087-1092. IJCAI/AAAI Press, 2011. Google Scholar
  24. P. Simons, I. Niemelä, and T. Soininen. Extending and implementing the stable model semantics. Artificial Intelligence, 138(1-2):181-234, 2002. Google Scholar
  25. Y. Zhu and M. Truszczyński. On optimal solutions of answer set optimization problems. In Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13) [2], pages 556-568. 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