Skip to Content

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

Path: KBS > research > projects > hexhex >

Tools: Drucken


Evaluation of ASP Programs with External Source Access

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


Contents


Project team

Motivation and Background

A notable extension of ASP are HEX-programs [eist2005, eist2006], which allow to specify meta-reasoning tasks through higher order atoms, and accommodate a universal 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. By the extensibility of HEX-programs, we can thus easily access very different kinds of information resources and reason about them, hence a flexible approach for knowledge integration is supported. Moreover, HEX-programs have 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:

This compilation approach is natural; however, it retricts the use of HEX-programs to applications with small to moderate-sized encodings and data instances, because the atom replacement leads to value guesses for the special atoms. Larger instances simply cannot be evaluated, as there are usually too many model candidates to generate, and to make matters worse, each model candidate potentially requires to issue external computations with high computational complexity in order to verify that it is a proper model. Thus, evaluating \hex-programs using current techniques can rarely be applied to real-world applications and instances.

On top of that, this approach raises expressiveness problems. Ordinary answer set programs use a closed domain, i.e., answer sets may only contain atoms that are constructible from the signature of the program. As the translations use answer set programs as target formalism, we are required to know the domain of external sources upfront; in our small example above, this would be the set of all terms in the thesaurus. Currently this is ensured by imposing rather strong syntactic restrictions on programs (strong safety) [eist2006]. However, this prevents value invention of external sources in many cases, and unnecessarily limits the high expressiveness of the underlying formalism in practice.

Goal of the project

The fundamental objective of our research is to advance Answer-Set Programming with respect to external sources in general, and in particular the HEX-semantics as its most important instance. There is a rich body of theorectical results already, and a growing list of natural and important applications of this ASP extension can be found. However, currently it is not used widly in practice because of the lack of an efficient reasoner. Therefore, developing efficient algorithms for evaluating HEX-programs will be a central goal of our research.

The current evaluation approach of HEX-programs, suffers from a rewriting bottleneck, which can not be overcome due to the impossibility to intervene the internals of model building. This calls for developing genuine algorithms for the computation of answer sets in presence of external atoms, specifically under the HEX-semantics, and will be the main contribution of our research. As discussed %we have seen above, another novelty of this formalism is a dynamic vocabulary which makes traditional strategies inapplicable.

State of the Project and Outlook

The overall project consists of two major phases. In the first phase we consider programs with fixed domains, while the second phase addresses value invention, domain expansion and grounding issues.

We started the first phase of our project by extending conflict-driven algorithms by external sources, and integrating those algorithms into our prototype system [efkr2012-iclp]. We made a distinction between uninformed learning, which consideres external sources as black boxes, and informed learning, which exploits meta-information (such as monotonicity and functionality) in order to apply more effective learning techniques. Our experiments show already a significant speedup. We then considered in HEX-programs with cyclic nonmonotonic external atoms, which are a special challange as they lift the answer set existence problem to the second level of the polynomia hierarchy. For evaluating such programs, we adopted the concept of unfounded sets for HEX-programs and exploited them for developing a new minimality checking algorithm [efkrs2012-jelia]. Finally, we developed a syntactic decision criterion, which allows for skipping the minimality check for programs with a certain structure [efkrs2012-aspocp]. A summary of the research on ground HEX-programs has also be given in [r2012-iclp-dc]. The results of this phase have been described in more detail in [efkrs2012-rr-1843-12-08], which was later published as a journal paper [efkrs2014-jair].

In the next step in our project we considered domain-expansion, i.e., programs which may introduce new constants into the program which are syntactically not part of the input. One goal was to relax the syntactic safety restrictions. However, instead of just introducing a new notion of safety, we developed an extensible safety framework, which may be instanciated with concrete safety criteria. This leads to the concept of liberally domain-expansion safe HEX-programs, which have been presented in [efkr2013-aaai]. We then developed a new grounding algorithm for this class of program and published it in [efkr2013-gttv]. An extension of this algorithm can also be used for grounding extensions of HEX-programs, as shown in [efkr2013-inap] and [efkr2014-inap13]. Currently, the research on domain-expansion is deepened to prepare a journal publication.

We further have defined a notion of support sets for HEX-programs which allow for a more efficient evaluation in many cases since the verification of external atom guesses can be skipped. Support sets can be implemented in an extension of our conflict-driven framework towards support for non-ground clauses [efrs2014-aaai].

In parallel to the theoretical work, new applications of HEX-programs have been presented in [fgirs2013-lpnmr], [ekr2013-inap11], [cfgirw2013-ijcai-angrybirds], and [cfgirw2013-pai]. In context of DL-programs, which were implemented on top of HEX-programs, the notion of repair answer sets has been introduced in [efs2013-ijcai].

Related to this project is also an alternative semantics for general logic programs with aggregates, which has been presented in [swdrkef2013-aij] and was implemented in our prototype system.

The project was finished in April 2015.

Software

Publications

2015

Cristina Feier, and Thomas Eiter.
Reasoning with forest logic programs using fully enriched automata.
In F. Calimeri, G. Ianni, and M. Truszczynski, editors, Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2015), volume 9345 of LNCS. Springer, 2015.
[ 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. Accepted for publication.
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.
Technical Report INFSYS RR-1843-15-01, Institut für Informationssysteme, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, January 2015.
bib | paper ]

Thomas Eiter, Michael Fink, Thomas Krennwallner, and Christoph Redl.
Domain Expansion for ASP-Programs with External Sources.
Technical Report INFSYS RR-1843-14-02, Institut für Informationssysteme, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, September 2014.
bib | paper ]

Daria Stepanova.
Inconsistencies in Hybrid Knowledge Bases.
PhD Thesis, Vienna University of Technology, A-1040 Vienna, Karlsplatz 13, March 2015.
bib | slides | 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.
Technical Report INFSYS RR-1843-15-01, Institut für Informationssysteme, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, January 2015.
bib | paper ]

2014

Thomas Eiter, Michael Fink, and Daria Stepanova
Computing Repairs for Inconsistent DL-programs over EL Ontologies.
In Fourteenth European Conference on Logics in Artificial Intelligence (JELIA 2014), September 24-26, 2014, Madeira, Portugal.
bib |  paper ]

Thomas Eiter, Michael Fink, Thomas Krennwallner, and Christoph Redl.
Domain Expansion for ASP-Programs with External Sources.
Technical Report INFSYS RR-1843-14-02, Institut für Informationssysteme, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, September 2014.
bib | paper ]

Francesco Calimeri, Michael Fink, Stefano Germano, Andreas Humenberger, Giovambattista Ianni, Christoph Redl, Daria Stepanova, and Andrea Tucci.
AngryHEX: an angry birds-playing agent based on HEX-programs.
Poster presentation, Angry Birds Competition 2014.
bib | paper ]

Thomas Eiter, Michael Fink, and Daria Stepanova
Towards Practical Deletion Repair of Inconsistent DL-programs.
In Twenty-First European Conference on Artificial Intelligence (ECAI 2014), August 18-22, 2014, Prague, Czech Republic.
bib |  paper ]

Daria Stepanova
Inconsistencies in Hybrid Knowledge Bases.
In Doctoral Consortium of KR 2014, July 20-24, 2014, Vienna, Austria.
bib |  paper ]

Thomas Eiter, Michael Fink, and Daria Stepanova
Towards Practical Deletion Repair of Inconsistent DL-programs.
In Twenty-Seventh International Workshop on Description Logics (DL 2014), July 17-20, 2014, Vienna, Austria.
bib |  paper ]

Christoph Redl.
Answer Set Programming with External Sources: Algorithms and Efficient Evaluation.
PhD Thesis, Vienna University of Technology, A-1040 Vienna, Karlsplatz 13, April 2014.
bib | slides | paper ]

Thomas Eiter, Michael Fink, Christoph Redl, and Daria Stepanova
Exploiting Support Sets for Answer Set Programs with External Evaluations.
In Twenty-Eighth AAAI Conference (AAAI 2014), July 27-31, 2014, Québec City, Québec, Canada, AAAI Press, July 2014.
bib | paper ]

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.
bib | paper ]

Yi-Dong Shen and Kewen Wang and Jun Deng and Christoph Redl and Thomas Krennwallner and Thomas Eiter, and Michael Fink.
FLP Answer Set Semantics without Circular Justifications for General Logic Programs.
In Artificial Intelligence, volume 213, pages 1-41, May 2014.
bib | paper ]

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.
bib | paper ]

2013

Francesco Calimeri, Michael Fink, Stefano Germano, Giovambattista Ianni, Christoph Redl, and Anton Wimmer.
AngryHEX: An Artificial Player for Angry Birds Based on Declarative Knowledge Bases.
In In Hans Tompits, editor, National Workshop and Prize on Popularize Artificial Intelligence (PAI 2013). Turin, Italy, December 2013.
bib | paper ]

Thomas Eiter, Michael Fink, Thomas Krennwallner, Christoph Redl, and Peter Schüller.
Improving HEX-Program Evaluation based on Unfounded Sets.
Technical Report INFSYS RR-1843-12-08, Institut für Informationssysteme, TU Wien, Favoritenstraße 9-11, A-1040 Vienna, September 2012.
bib | paper ]

Francesco Calimeri, Michael Fink, Stefano Germano, Giovambattista Ianni, Christoph Redl, and Anton Wimmer.
AngryHEX: an angry birds-playing agent based on HEX-programs.
Poster presentation, Angry Birds Competition 2013.
bib | paper ]

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.
bib | DOI | paper ]

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'13), Kiel, Germany, September 11-13, 2013, September 2013.
To appear.
bib | paper ]

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'13), Corunna, Spain, September 15, 2013, pages 3-15, September 2013.
bib | paper ]

Michael Fink, Stefano Germano, Giovambattista Ianni, Christoph Redl, and Peter Schüller.
ActHEX: implementing HEX programs with action atoms.
In Pedro Cabalar and TranCao Son, editors Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2013), September 15-19, 2013, Corunna, Spain, , volume 8148 of Lecture Notes in Computer Science, pages 317\96322. Springer Berlin Heidelberg, 2013. [ bib | paper ]

Thomas Eiter, Michael Fink, and Daria Stepanova
Data Repair of Inconsistent DL-Programs.
In Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013), August 3-9, 2013, Beijing, China
, IJCAI/AAAI, August 2013.
bib | paper ]

Thomas Eiter, Michael Fink, Thomas Krennwallner, and Christoph Redl.
Liberal Safety Criteria for HEX-Programs.
In Marie desJardins and Michael Littman, editors, Twenty-Seventh AAAI Conference (AAAI 2013), July 14-18, 2013, Bellevue, Washington, USA, pages 267-275. AAAI Press, July 2013.
bib | paper ]

2012

Thomas Eiter, Thomas Krennwallner, Matthias Prandstetter, Christian Rudloff, Patrick Schneider, and Markus Straub.
Semantically enriched multi-modal routing.
In Proceedings 19th World Congress on Intelligent Transport Systems (ITSWC-2012), Vienna, October 22-26, 2012, 2012.
[ paper ]

Thomas Eiter, Michael Fink, Thomas Krennwallner, Christoph Redl, and Peter Schüller.
Improving HEX-Program Evaluation based on Unfounded Sets.
Technical Report INFSYS RR-1843-12-08, Institut für Informationssysteme, TU Wien, September 2012. [ bib | paper ]
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 80-93. Springer, September 2012.
bib | DOI | paper ]

Christoph Redl.
Answer Set Programming with External Sources.
In Eighth ICLP Doctoral Consortium, Budapest, Hungary, September 4, 2012, pages 469\96475.
bib | paper ]

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, 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.
bib | paper ]
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, September 2012.
Published online: 05 September 2012.
bib | DOI | 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.

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.