Integrated Evaluation of Answer Set Programs and Extensions

The advent of the World Wide Web and distributed systems fostered the development of formalisms towards modularity and integrating multiple data sources. The goal of this project is to develop and analyze algorithms for HEX-programs, which are an extension of answer set programs (ASP) towards integration of external computation sources. In HEX-programs, external atoms model a bidirectional interface to external knowledge sources. While the algorithms for different sub-problems of the evaluation have been optimized largely independently in previous research, their interplay is a bottleneck in current applications. We have identified three related limitations of the current algorithms. First, due to the introduction of new constants by external sources (value invention), the optimal integration of the grounder and the solver is not straightforward. The current algorithm might give preference to the one or the other, but the optimization of the overall evaluation is challenging. Second, while external atoms are expressive and allow for a natural encoding of many ASP extensions (e.g., constraint ASP), the current algorithms are not competitive with native implementations due to a loose coupling of the external sources with the logic program. Third, large-scale applications require modularity techniques which decompose the overall program into manageable components. While there exist several approaches, the existing evaluation algorithms usually separate the components also during evaluation, which leads to efficiency limitations. In order to overcome these limitations, we plan to develop tightly integrated algorithms which have a global view of the program. In particular, new techniques for an optimal interplay of the grounder and the solver are necessary. Moreover, novel interfaces are required which allow for exploiting application-specific properties. This includes new means for querying external sources, such as partial or incremental queries; this also requires extensions in the formal semantics of the formalism. For modularity, we plan the provide a convenient interface between models from the user perspective but integrate multiple modules during evaluation in order to boost the efficiency. The expected outcome will comprise novel algorithms for HEX-programs, new methods for integrating and querying external sources, and an open-source implementation and evaluation as a proof of concept. We expect that the overall goals are tightly related and are achievable by using incremental ASP solving techniques. However, existing techniques introduce side constraints and the user has the burden to obey them. Since this is not an option for average users, we plan to make use of the techniques internally, but hide them from the user. This requires analysis of program classes and instances, automatic rewriting methods and new interfaces for external sources. We expect that the resulting algorithms do not only provide a better scalability, but also a better user convenience due to easier extensibility of the formalism.

This project focuses on a logic-based programming language, which was developed for applications in the area of artificial intelligence (including logistics, Semantic Web, planning, and robotics). A key feature of this language is the integration of the logic program with external sources (data or computation sources), e.g. databases, Web resources and route planners. However, this makes the evaluation of programs non-trivial, both conceptually and concerning computational resources. Existing approaches showed unsatisfactory performance because the logic program and external sources tightly influence each other, but the evaluation is split into several steps which are insufficiently interleaved. Previous approaches show in particular unsatisfactory performance for certain types of programs. This project aims at novel evaluation approaches towards the optimization of the evaluation. To this end, a tighter integration of the logic program and external sources was realized, by accessing external sources already during the evaluation of the program. Moreover, known properties of external sources can now be specified by their developers and are exploited during the evaluation.