Skip to Content

TU Wien Fakultät für Informatik Knowledge-Based Systems Group
Top-level Navigation: Current-level Navigation:

Path: KBS > research > projects > inthex >

Tools: Drucken

Integrated Evaluation of Answer Set Programs and Extensions

supported by the Austrian Science Funds (FWF) under project number P27730.

Contents

Project team

Motivation and Background

HEX-programs are an extension of answer set programs towards integration of external sources of computation [eist2005, eist2006]. The integration is done via a universal and bidirectional interface for arbitrary sources of external computation through the notion of external atoms. For example, an external atom of the form &reach[g,n](X) might be used to access and reason about all nodes of a graph g that are reachable from node n, where the task of determining reachability is delegated to an external source of computation, respectively information source. The formalism has been successfully used in various kinds of applications like the SPARQL Query Language for RDF, which can be conveniently translated to HEX-programs (see [polleres2007b]), in planning [nev2007], and in ontology integration [hlkh2007, eite-etal-wi06]. These results show the effectiveness of incorporating external knowledge by means of external atoms.

The current evaluation approach for a given HEX-programs is as follows: (1) the reasoner constructs an evaluation graph for the program, consisting of subsets thereof and dependencies as edges; (2) following the structure of the evaluation graph starting at the nodes without predecessors, each component first grounded (i.e. translated into an equivalent variable-free program) and then solved, and its answer sets are added as facts to successive components; and (3) finally, the answer sets of the single components are combined to retrieve the answer sets of the overall program. However, several limitations of this approach have led to restricted use of the formalism in practice. We have identified three related main limitations to be described in the following. The limitations are not only related because they limit the practical use of the formalism, but also because we expect that one can overcome them by similar techniques like incremental ASP solving algorithms.

  1. While the solving algorithms for ground programs are efficient [efkr2012-tplp, efkrs2012-jelia, efkrs2012-aspocp, efkrs2014-jair], and a new grounding algorithm has been introduced [efkr2013-gttv, efkr2014-inap13], the grounder and the solver are currently opponents. Although not mandatory, splitting programs into components is sometimes strongly recommended in order to achieve a reasonable grounding performance. In fact, grounding a single rule can be exponential in the atoms of the input program, which can often be avoided by splitting the program. However, splitting is disadvantageous for the solving algorithm as learned knowledge cannot be propagated throughout the whole program.
  2. The second limitation of the current techniques concerns extensions of ASP, e.g. weak constraints, cardinality constraints and constraint atoms [gkost2009]. Although they can be naturally encoded as HEX-programs using tailored external atoms, good performance is often only possible with native implementations. As this is not an option for an average user, a convenient interface which allows for intervening the core algorithms is desirable. Currently, external sources are evaluated under interpretations which are complete on the input atoms and are expected to return all output tuples for which they evaluates to true. However, many external sources can provide partial output under incomplete input. Conversely, output tuples of an external atom may be unchanged if parts of the input change.
  3. Finally, in order to establish HEX as a formalism for larger applications, modularity techniques are required. Although there are some approaches in ordinary ASP, none of them is suited for providing both well-defined interfaces between modules and efficient evaluation. Some approaches provide a loose coupling of different modules with well-defined interfaces [ekr2013-inap11, sw2012], which is convenient. However, do to largely independent evaluation of modules, it is usually less efficient. On the other hand, approaches with a tight integration of modules introduce side conditions which need to be regarded, and thus are less accessible for average users (e.g. [gkkost2008, ggks2011]).

In all three limitations, the underlying problem can be found in largely independent processes which solve sub-problems of the evaluation problem due to a loose coupling of grounding/solving, logic program/ external sources and different program modules, respectively.

Goal of the project

The overall objective of the project is to overcome the limitations described above by the development of integrated reasoning algorithms which have a global view of the input program and interleave the sub-procedures during evaluation in an optimal way.

This motivates the following three main goals of the project:

  1. Integrated Grounding and Solving: The current grounding and solving algorithms of ASP solvers have been developed largely independently of each other. In order to optimize the overall efficiency, a tight integration of grounding and solving is necessary, which shall lead to a new class of solvers.
  2. Low-Level Interface for Extensions of ASP: Extensions of ASP can be elegantly rewritten to HEX-programs. However, for an efficient evaluation, novel interfaces for external sources are needed, which allow for intervening in the model-building algorithms.
  3. Modularity and Integration with Other Paradigms: Towards applicability of ASP and extensions for large applications, we aim at the integration of techniques for modular programming into the formalism.

State of the Project and Outlook

The project started in June 2015. As of September 2017, major achievements concerning all main goals have been made (see publications below). In 2018, the evaluation techniques were refined, applications were developed, and further experiments were conducted. The results have been published in journal publications. The project was finished in November 2018.

Software

Publications

2018

Christoph Redl.
Inlining External Sources in Answer Set Programs.
Theory and Practice of Logic Programming, 2018, To appear.
[ bib ]

Thomas Eiter, Tobias Kaminski, Christoph Redl, and Antonius Weinzierl.
Exploiting Partial Assignments for Efficient Evaluation of Answer Set Programs with External Sources.
In Journal of Artificial Intelligence Research, volume 62, pages 665-727, July 2018.
[ bib | paper ]

Christoph Redl.
Inconsistency in Answer Set Programs and Extensions.
Technical Report LOGCOMP RR-1923-18-04, Institut für Logic and Computation, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, June 2018.
[ bib | paper ]

Thomas Eiter, Stefano Germano, Giovambattista Ianni, Tobias Kaminski, Christoph Redl, Peter Schüller and Antonius Weinzierl.
The DLVHEX System.
KI - Künstliche Intelligenz, May 15, 2018.
[ bib | paper ]

Thomas Eiter, Tobias Kaminski, Christoph Redl, and Antonius Weinzierl.
Exploiting Partial Assignments for Efficient Evaluation of Answer Set Programs with External Sources.
Technical Report LOGCOMP RR-1923-18-02, Institut für Logic and Computation, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, January 2018.
[ bib | paper ]

Christoph Redl.
Inlining External Sources in Answer Set Programs.
Technical Report LOGCOMP RR-1923-18-01, Institut für Logic and Computation, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, January 2018.
[ bib | paper ]

2017

Christoph Redl.
Conflict-driven ASP Solving with External Sources and Program Splits.
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI 2017), August 19-25, 2017, Melbourne, Australia.
[ bib | poster | paper ]

Thomas Eiter, Tobias Kaminski, and Antonius Weinzierl.
Lazy-Grounding for Answer Set Programs with External Source Access.
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI 2017), August 19-25, 2017, Melbourne, Australia.

Thomas Eiter, Tobias Kaminski, Peter Schüller, Christoph Redl, and Antonius Weinzierl.
Answer Set Programming with External Source Access.
Reasoning Web. Semantic Interoperability on the Web - 13th International Summer School 2017, London, UK, July 7-11, 2017, Tutorial Lectures.
[ bib | slides | paper ]

Antonius Weinzierl.
Blending Lazy-Grounding and CDNL Search for Answer-Set Solving.
Proceedings of the Fourteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2017), July 3-6, 2017, Helsinki, Finland.

Christoph Redl.
Explaining Inconsistency in Answer Set Programs and Extensions.
Proceedings of the Fourteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2017), July 3-6, 2017, Helsinki, Finland.
[ bib | slides | paper ]

Christoph Redl.
Answer Set Programs with Queries over Subprograms.
Proceedings of the Fourteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2017), July 3-6, 2017, Helsinki, Finland.
[ bib | slides | paper ]

Christoph Redl.
On Equivalance and Inconsistency of Answer Set Programs with External Sources.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), February 4-9, 2017, San Francisco, California, USA.
[ bib | poster | paper ]

Christoph Redl.
Efficient Evaluation of Answer Set Programs with External Sources Based on External Source Inlining.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), February 4-9, 2017, San Francisco, California, USA.
[ bib | poster | paper ]

Christoph Redl.
Extending Answer Set Programs with Interpreted Functions as First-class Citizens.
Proceedings of the Nineteenth International Symposium on Practical Aspects of Declarative Languages (PADL 2017), January 16-17, 2017, Paris, France.
[ bib | slides | paper ]

Jakob Rath and Christoph Redl.
Integrating Answer Set Programming with Procedural Languages.
Proceedings of the Nineteenth International Symposium on Practical Aspects of Declarative Languages (PADL 2017), January 16-17, 2017, Paris, France.
[ bib | slides | paper ]

2016

Christoph Redl.
Automated Benchmarking of KR-Systems.
Proceedings of the Twenty-Third RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, November 28, 2016, Genova, Italy.
[ bib | slides | paper ]

Christoph Redl.
The DLVHEX System for Knowledge Representation and Reasoning (System Description).
Theory and Practice of Logic Programming, 16(4-5):866-883, 2016.
[ bib | slides | paper ]

Giovambattista Ianni, Francesco Calimeri, Stefano Germano, Andreas Humenberger, Christoph Redl, Daria Stepanova, Andrea Tucci, and Anton Wimmer.
Angry-HEX: an Artificial Player for Angry Birds Based on Declarative Knowledge Bases.
IEEE Transactions on Computational Intelligence and AI in Games, 8(2):128-139, 2016.
[ bib | paper ]

Thomas Eiter, Michael Fink, Giovambattista Ianni, Thomas Krennwallner, Christoph Redl, and Peter Schüller.
A Model Building Framework for Answer Set Programming with External Computations.
Theory and Practice of Logic Programming, 16(4):418-464, 2016
[ bib | paper ]

Thomas Eiter, Tobias Kaminski, Christoph Redl, and Antonius Weinzierl.
Exploiting Partial Assignments for Efficient Evaluation of Answer Set Programs with External Source Access.
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI 2016), July 9--15, 2016, New York, New York, USA.
[ bib | paper ]

Thomas Eiter, Christoph Redl, and Peter Schüller.
Problem Solving Using the HEX Family.
In Christoph Beierle, Gerhard Brewka, and Matthias Thimm, editors, Computational Models of Rationality - Essays dedicated to Gabriele Kern-Isberner on the occasion of her 60th birthday, Tributes, pages 150-174. College Publications, January 2016.
[ bib | paper ]

Thomas Eiter, Michael Fink, Thomas Krennwallner, and Christoph Redl.
Domain Expansion for ASP-Programs with External Sources.
In Artificial Intelligence, volume 233, pages 84-121, 2016
[ bib | paper ]

Christoph Redl.
The ABC Benchmarking System - User Guide.
Technical Report INFSYS RR-1843-16-01, Institut für Informationssysteme, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, January 2016.
[ bib | paper ]

2015

Thomas Eiter, Christoph Redl, and Peter Schüller.
Problem Solving Using the HEX Family.
Technical Report INFSYS RR-1843-15-07, Institut für Informationssysteme, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, December 2015.
[ bib | paper ]

Thomas Eiter, Mustafa Mehuljic, Christoph Redl, and Peter Schüller.
User Guide: dlvhex 2.X.
Technical Report INFSYS RR-1843-15-05, Institut für Informationssysteme, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, September 2015.
[ bib | paper ]

Giovambattista Ianni, Francesco Calimeri, Stefano Germano, Andreas Humenberger, Christoph Redl, Daria Stepanova, Andrea Tucci, and Anton Wimmer.
Angry-HEX: an Artificial Player for Angry Birds Based on Declarative Knowledge Bases.
IEEE Transactions on Computational Intelligence and AI in Games, 8(2):128-139, 2016.
[ bib ]

Thomas Eiter, Michael Fink, Giovambattista Ianni, Thomas Krennwallner, Christoph Redl, and Peter Schüller.
A Model Building Framework for Answer Set Programming with External Computations.
Theory and Practice of Logic Programming, 16(4):418-464, 2016.
[ bib ]

Alessandro De Rosis, Thomas Eiter, Christoph Redl, and Francesco Ricca.
Constraint Answer Set Programming based on HEX-Programs.
In Eighth Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2015), August 31, 2015, Cork, Ireland, August 2015.
[ bib ]

Thomas Eiter, Michael Fink, Giovambattista Ianni, Thomas Krennwallner, Christoph Redl, and Peter Schüller.
A Model Building Framework for Answer Set Programming with External Computations.
Technical Report INFSYS RR-1843-15-01, Institut für Informationssysteme, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, January 2015.
[ bib | paper ]

Cooperations

References

[eist2005]
Thomas Eiter, Giovambattista Ianni, Roman Schindlauer and Hans Tompits. A Uniform Integration of Higher-Order Reasoning and External Evaluations in Answer-Set Programming. In L. P. Kaelbling and A. Saffiotti, editors, Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05) Denver, USA, 2005.
[eist2006]
Thomas Eiter, Giovambattista Ianni, Roman Schindlauer and Hans Tompits. Effective Integration of Declarative Rules with External Evaluations for Semantic-Web Reasoning. In L. P. Kaelbling and A. Saffiotti, editors, Proceedings of the 3rd European Conference on Semantic Web (ESWC 2006), volume 4011 of LNCS, pages 273-287. Springer, 2009.
[polleres2007b]
Axel Polleres. From SPARQL to Rules (and back). Proceedings of the 16th World Wide Web Conference (WWW2007), pages 787-796, 2009.
[nev2007]
Davy Van Nieuwenborgh, Thomas Eiter, and Dirk Vermeir. Conditional Planning with External Functions. Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2007), volume 4483 of LNAI, pages 214-227. Springer, 2007.
[hlkh2007]
Robert Hoehndorf and Frank Loebe and Janet Kelso and Heinrich Herre. Representing default knowledge in biomedical ontologies: Application to the integration of anatomy and phenotype ontologies. BMC Bioinformatics, volume 8, pages 377, 2007.
[eite-etal-wi06]
Thomas Eiter and Giovambattista Ianni and Roman Schindlauer and Hans Tompits and Kewen Wang. Forgetting in Managing Rules and Ontologies. IEEE/WIC/ACM International Conference on Web Intelligence (WI 2006), pages 411--419. Hongkong, 2006.
[eite-etal-wi06]
Thomas Eiter and Michael Fink and Thomas Krennwallner and Christoph Redl. Forgetting in Managing Rules and Ontologies. IEEE/WIC/ACM International Conference on Web Intelligence (WI 2006), pages 411--419. Hongkong, 2006.
[efkr2012-tplp]
Thomas Eiter, Michael Fink, Thomas Krennwallner, and Christoph Redl. Conflict-driven ASP solving with external sources. Theory and Practice of Logic Programming: Special Issue 28th International Conference on Logic Programming (ICLP 2012), 12(4-5):659-679, July 2012. Published online: 05 September 2012.
[efkrs2012-jelia]
Thomas Eiter, Michael Fink, Thomas Krennwallner, Christoph Redl, and Peter Schüller. Exploiting Unfounded Sets for HEX-Program Evaluation. In Luis Fariñas del Cerro, Andreas Herzig, and Jérôme Mengin, editors, 13th European Conference on Logics in Artificial Intelligence (JELIA 2012), September 26-28, 2012, Toulouse, France, volume 7519 of LNCS, pages 160-175. Springer, September 2012.
[efkrs2012-aspocp]
Thomas Eiter, Michael Fink, Thomas Krennwallner, Christoph Redl, and Peter Schüller. Eliminating Unfounded Set Checking for HEX-Programs. In Michael Fink and Yuliya Lierler, editors, 5th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2012), September 4, 2012, Budapest, Hungary, pages 83-97, September 2012.
[efkrs2014-jair]
Thomas Eiter and Michael Fink and Thomas Krennwallner and Christoph Redl, and Peter Schüller. Efficient HEX-Program Evaluation Based on Unfounded Sets. In Journal of Artificial Intelligence Research, volume 49, pages 269-321, February 2014.
[efkr2013-gttv]
Thomas Eiter, Michael Fink, Thomas Krennwallner, and Christoph Redl. Grounding HEX-Programs with Expanding Domains. In David Pearce, Shahab Tasharrofi, Evgenia Ternovska, and Concepción Vidal, editors, 2nd Workshop on Grounding and Transformations for Theories with Variables (GTTV 2013), Corunna, Spain, September 15, 2013, pages 3-15, September 2013.
[efkr2014-inap13]
Thomas Eiter, Michael Fink, Thomas Krennwallner, and Christoph Redl. HEX-Programs with Existential Quantification. In Ricardo Rocha, editor, 20th International Conference on Applications of Declarative Programming and Knowledge Management (INAP 2013), Kiel, Germany, September 11-13, 2013. Post proceedings.
[ekr2013-inap11]
Thomas Eiter, Thomas Krennwallner, and Christoph Redl. HEX-Programs with Nested Program Calls. In Hans Tompits, editor, 19th International Conference on Applications of Declarative Programming and Knowledge Management (INAP 2011), volume 7773 of LNAI, pages 1-10. Springer, October 2013.
[sw2012]
Terrance Swift and David Scott Warren.
XSB: Extending Prolog with Tabled Logic Programming.< In Theory and Practice of Logic Programming (TPLP), pages 157-187, 2012.
[ggks2011]
Martin Gebser and Torsten Grote and Roland Kaminski and Torsten Schaub. Reactive Answer Set Programming. In J. P. Delgrande and W. Faber, editors, LPNMR, volume 6645 of Lecture Notes in Computer Science, pages 54–66. Springer, 2011.
[gkkost2008]
Martin Gebser and Roland Kaminski and Benjamin Kaufmann and Max Ostrowski and Torsten Schaub and Sven Thiele. Engineering an Incremental ASP Solver. In ICLP '08, pages 190–205, Berlin, Heidelberg, 2008. Springer-Verlag.
[gkost2009]
Martin Gebser and Roland Kaminski and Max Ostrowski and Torsten Schaub and Sven Thiele. On the Input Language of ASP Grounder Gringo. In E. Erdem, F. Lin, and T. Schaub, editors, LPNMR 2009, volume 5753 of Lecture Notes in Computer Science, pages 502–508. Springer Berlin Heidelberg, 2009.

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist die Fakultät für Informatik an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. / Disclaimer.