Answer Set Programming (ASP) is a declarative programming paradigm addressing combinatorial search and optimization problems. Thanks to ASP’s declarativity, domain experts can conveniently use the formalism to describe the characteristics of a problem at high level, delegating the search for solutions to efficient solvers. Indeed, prototyping a general and human-readable ASP program can often be accomplished within minutes to a few hours, without requiring deep knowledge of the solving process. However, one and the same problem can be represented in terms of different ASP programs, which may strongly influence the time required by solvers to return a solution. In case the solving performance turns out to be a bottleneck, considerable manual efforts may arise for identifying the reasons and revising the ASP program to speed up the solving process. Hence, we observe a trade-off between the two strengths of ASP: the ease of representing a problem versus high solving performance.

Our project tackles this discrepancy by determining and injecting relevant information into ASP programs for improving the solving performance, while also delivering knowledge and insights to domain experts. More specifically, we intend to develop methodologies to automatically extract structural properties of a problem at hand, derived from the ASP program along with problem instances given as representative examples. These properties will in turn be represented in ASP, and exploited to speed up the solving process. At the same time, the identified properties will be made accessible to domain experts through visual explanations, whose interactive feedback guides the analysis and possible revision of training examples.

This project enhances the state of the art by saving considerable manual efforts on extracting and exploiting implicit problem information, with particular emphasis on methods to explain the discovered application characteristics to domain experts. In addition to the automatic analysis of structural properties, we intend to provide visual and interactive user interfaces supporting the exploration by domain experts, e.g., to identify and revise incomplete problem specifications or representative examples in a targeted way. To prototype, evaluate, and supply the knowledge representation and reasoning methodologies pioneered in our project, we will implement a novel ASP-based system called EX3, named after its three main objectives: EXtract, EXploit, and EXplain knowledge.