Evaluation of ASP Programs with External Source Access

The advent of the World Wide Web and distributed systems fostered the development of formalisms that are geared towards modularity and integrating multiple data sources. The goal of this project is to develop and analyze efficient algorithms for evaluating nonmonotonic logic programs with access to external knowledge sources. In particular, this project will investigate advanced model-building 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. Currently, HEX- programs are evaluated by translating them into ordinary answer set programs which essentially guess the truth value of external atoms. Those programs are evaluated by standard ASP solvers to generate model candidates for the HEX-program. In a post-processing step, model candidates which are not consistent with the actual behavior of external sources are eliminated. However, this strategy has major shortcomings both in scalability and expressiveness. Using ordinary ASP solvers as black boxes leaves little room for influencing the model building process and pruning the in general vast search tree; many model candidates that fail to pass the post-processing step are created unnecessarily. Furthermore, ordinary ASP solvers pre-ground the program before reasoning, which requires that the translation approach knows all possible ground instances before evaluation. This inhibits introducing new values into the program (called value invention), which however is an important aspect of external source access. Overcoming these limitations requires, on the one hand, to intervene in the model-building process, which can only be done by developing native evaluation algorithms. On the other hand, it requires developing novel methods to handle non-ground HEX-programs (in particular, program grounding) to bring them closer to applications which need to handle new values from source access. Both are key concepts to improve HEX-program evaluation to scale with real-world instances and applications, measured in a suitable way. In this respect, the goal of the project is to substantially increase the scalability relative to the intrinsic complexity of program evaluation and of source accesses. Depending on the program structure, an exponential speed-up should be achievable in some relevant cases, while a prediction on average increase is difficult to make. However, we aim at a performance which is comparable to ordinary ASP solving modulo the computational complexity of the external sources involved. The outcome of this project will comprise novel, native model-finding algorithms for ASP programs with external source access, novel methods for handling non-ground programs, and a prototype implementation as a proof of concept to verify that the newly developed algorithms and methods do indeed scale on benchmark suites, motivated by existing benchmarks and real-world applications. We hold that our overall goal is achievable by extensive search space pruning. This shall be done, for instance, by learning techniques motivated by SAT solving, which keep track of the initial reasons for conflicts and directly jump back to that point. Thus, they avoid running into the same conflict again. This technique was already used for ordinary ASP solving and experimental results are promising. However, adopting it to HEX-programs is challenging since value invention makes evaluation much more complicated, also with respect to grounding (which in fact is impossible in general). Since practically relevant programs often do not exploit the full problem complexity, we further want to make theoretical investigations on program classes which allow for simplified evaluation. A modular structure shall allow for providing multiple algorithms for specific special cases. The actual algorithm selection will then be done by a superior control mechanism. This paves the way for further optimizations in the future. Our system shall eventually be publicly available as open source software to promote HEX-programs as a practical formalism.

This project focuses on a recent logic-based problem solving language as a common foundation of applications in the area of artificial intelligence, such as smart route planning, linguistics, robotics, and intelligent Web agents. Driven by the requirements of such applications, the language supports the integration of multiple, possibly distributed sources of computation and databases. However, this makes the evaluation of programs non-trivial, both conceptually and concerning computational resources.Pre-existing evaluation methods turned out to be unsatisfactory as they did not scale to applications of realistic size. Moreover, existing approaches were also depending on several language restrictions, which had to been adopted in order to facilitate computational evaluation; however, these restrictions limit the expressiveness and/or affect the convenient use of the language. The main goal of this project was therefore to develop novel evaluation methods towards increased scalability and to reduce language restrictions.The outcome of the project is a set of novel evaluation strategies, which has also been realized in a freely available prototype system. A suite of experiments was used to demonstrate that the main goals have been achieved. Additionally, the system was used for some realistic applications, including those mentioned above, in order to show the practical applicability of the results.