Domain-specific heuristics are an essential technique for solving combinatorial problems efficiently. Current approaches to integrate domain-specific heuristics with Answer Set Programming (ASP) are unsatisfactory when dealing with heuristics that are specified non-monotonically on the basis of partial assignments. Such heuristics frequently occur in practice, for example, when picking an item that has not yet been placed in bin packing. Therefore, we present novel syntax and semantics for declarative specifications of domain-specific heuristics in ASP. Our approach supports heuristic statements that depend on the partial assignment maintained during solving, which has not been possible before. We provide an implementation in Alpha that makes Alpha the first lazy-grounding ASP system to support declaratively specified domain-specific heuristics. Two practical example domains are used to demonstrate the benefits of our proposal. Additionally, we use our approach to implement informed search with A*, which is tackled within ASP for the first time. A* is applied to two further search problems. The experiments confirm that combining lazy-grounding ASP solving and our novel heuristics can be vital for solving industrial-size problems.

Abstract Generalising and re-using knowledge learned while solving one problem instance has been neglected by state-of-the-art answer set solvers. We suggest a new approach that generalises learned nogoods for re-use to speed-up the solving of future problem instances. Our solution combines well-known ASP solving techniques with deductive logic-based machine learning. Solving performance can be improved by adding learned non-ground constraints to the original program. We demonstrate the effects of our method by means of realistic examples, showing that our approach requires low computational cost to learn constraints that yield significant performance benefits in our test cases. These benefits can be seen with ground-and-solve systems as well as lazy-grounding systems. However, ground-and-solve systems suffer from additional grounding overheads, induced by the additional constraints in some cases. By means of conflict minimization, non-minimal learned constraints can be reduced. This can result in significant reductions of grounding and solving efforts, as our experiments show.

Abstract Answer-Set Programming (ASP) is a powerful and expressive knowledge representation paradigm with a significant number of applications in logic-based AI. The traditional ground-and-solve approach, however, requires ASP programs to be grounded upfront and thus suffers from the so-called grounding bottleneck (i.e., ASP programs easily exhaust all available memory and thus become unsolvable). As a remedy, lazy-grounding ASP solvers have been developed, but many state-of-the-art techniques for grounded ASP solving have not been available to them yet. In this work we present, for the first time, adaptions to the lazy-grounding setting for many important techniques, like restarts, phase saving, domain-independent heuristics, and learned-clause deletion. Furthermore, we investigate their effects and in general observe a large improvement in solving capabilities and also uncover negative effects in certain cases, indicating the need for portfolio solving as known from other solvers.

Constraint answer set programming (CASP) is a family of hybrid approaches integrating answer set programming (ASP) and constraint programming (CP). These hybrid approaches have already proven to be very successful in various domains. In this paper we present first evaluation results for the CASP solver ASCASS, which provides novel methods for defining and exploiting problem-dependent search heuristics. Beyond the possibility of using already built-in problem-independent heuristics, ASCASS allows on the ASP level the definition of problem-dependent variable selection, value selection and pruning strategies, which guide the search of the CP solver. The proof-of-concept evaluation was carried out on benchmark instances of the real world Partner Units Problem (PUP). Due to a sophisticated heuristic, which cannot be represented by other ASP or CASP solvers, ASCASS shows superior performance.

Sequential diagnosis methods compute a series of queries for discriminating between diagnoses. Queries are answered by probing such that eventually the set of faults is identified. The computation of queries is based on the generation of a set of most probable diagnoses. However, in diagnosis problem instances where the number of minimal diagnoses and their cardinality is high, even the generation of a set of minimum cardinality diagnoses is unfeasible with the standard conflict-based approach. In this paper we propose to base sequential diagnosis on the computation of some set of minimal diagnoses using the direct diagnosis method, which requires less consistency checks to find a minimal diagnosis than the standard approach. We study the application of this direct method to high cardinality faults in knowledge-bases. In particular, our evaluation shows that the direct method results in almost the same number of queries for cases when the standard approach is applicable. However, for the cases when the standard approach is not applicable, sequential diagnosis based on the direct method is able to locate the faults correctly.

Constraint Satisfaction Problems (CSPs) have the big advantage of a succinct, declarative and easy to understand representation form. Unfortunately, solving CSPs is NP-complete in the general case. In order to cope with this, common CSP frameworks offer the possibility to use different built-in heuristics. However, the provided built-in heuristics are often not suitable to significantly boost solution calculation. Also the facilities for expressing domain-specific heuristics in a declarative manner within the CSP framework are typically very limited (e.g. by defining a static variable selection order)and thus are often not applicable. As a consequence such domain-specific heuristics are often implemented by means of custom propagators or custom constraints (e.g. a special constraint for bin packing problems) forcing domain experts and knowledge engineers to leave the declarative world and implement the heuristics in a procedural manner. In this paper we propose a new declarative language for expressing domain specific heuristics for CSPs which can be easily integrated in every CSP framework. We also describe a prototype implementation within a state-of-the-art CSP solver and present proof of concept results on real world configuration problem instances.

The Partner Units Problem (PUP) constitutes a challenging real-world configuration problem with diverse application domains such as railway safety, security monitoring, electrical engineering, or distributed systems. Although using the latest problem-solving methods including Constraint Programming, SAT Solving, Integer Programming, and Answer Set Programming, current methods fail to generate solutions for midsized real-world problems in acceptable time. This paper presents the QuickPup algorithm based on backtrack search combined with smart variable orderings and restarts. QuickPup outperforms the available methods by orders of magnitude and thus makes it possible to automatically solve problems which couldn’t be solved without human expertise before. Furthermore, the runtimes of QuickPup are typically below one second for real-world problem instances.

Effective debugging of ontologies is an important prerequisite for their broad application, especially in areas that rely on everyday users to create and maintain knowledge bases, such as the Semantic Web. In such systems ontologies capture formalized vocabularies of terms shared by its users. However in many cases users have different local views of the domain, i.e. of the context in which a given term is used. Inappropriate usage of terms together with natural complications when formulating and understanding logical descriptions may result in faulty ontologies. Recent ontology debugging approaches use diagnosis methods to identify causes of the faults. In most debugging scenarios these methods return many alternative diagnoses, thus placing the burden of fault localization on the user. This paper demonstrates how the target diagnosis can be identified by performing a sequence of observations, that is, by querying an oracle about entailments of the target ontology. To identify the best query we propose two query selection strategies: a simple "split-in-half" strategy and an entropy-based strategy. The latter allows knowledge about typical user errors to be exploited to minimize the number of queries. Our evaluation showed that the entropy-based method significantly reduces the number of required queries compared to the "split-in-half" approach. We experimented with different probability distributions of user errors and different qualities of the a priori probabilities. Our measurements demonstrated the superiority of entropy-based query selection even in cases where all fault probabilities are equal, i.e. where no information about typical user errors is available.

Constraint sets can become inconsistent in different contexts. We are interested in identifying minimal sets of constraints that have to be adapted or deleted in order to restore consistency. In this paper we sketch a highly efficient divide-and-conquer based diagnosis approach which identifies minimal sets of faulty constraints in a given over-constrained problem. This approach is specifically applicable in scenarios where the efficient identification of leading (preferred) diagnoses is crucial.

Debugging is an important prerequisite for the wide-spread application of ontologies, especially in areas that rely upon everyday users to create and maintain knowledge bases, such as the Semantic Web. Recent approaches use diagnosis methods to identify sources of inconsistency. However, in most debugging cases these methods return many alternative diagnoses, thus placing the burden of fault localization on the user. This paper demonstrates how the target diagnosis can be identified by performing a sequence of observations, that is, by querying an oracle about entailments of the target ontology. We exploit probabilities of typical user errors to formulate information theoretic concepts for query selection. Our evaluation showed that the suggested method reduces the number of required observations compared to myopic strategies.

This paper proposes a self-healing approach to handle exceptions in service-based processes and to repair the faulty activities with a model-based approach. In particular, a set of repair actions is defined in the process model, and repairability of the process is assessed by analyzing the process structure and the available repair actions. During execution, when an exception arises, repair plans are generated by taking into account constraints posed by the process structure, dependencies among data, and available repair actions. The paper also describes the main features of the prototype developed to validate the proposed repair approach for composed Web services; the self-healing architecture for repair handling and the experimental results are illustrated.

Efficient acquisition of constraint networks is a key factor for the applicability of constraint problem solving methods. Current techniques learn constraint networks from sets of training examples, where each example is classified as either a solution or non-solution of a target network. However, in addition to this classification, an expert can usually provide arguments as to why examples should be rejected or accepted. Generally speaking domain specialists have partial knowledge about the theory to be acquired which can be exploited for knowledge acquisition. Based on this observation, we discuss the various types of arguments an expert can formulate and develop a knowledge acquisition algorithm for processing these types of arguments which gives the expert the possibility to input arguments in addition to the learning examples. The result of this approach is a significant reduction in the number of examples which must be provided to the learner in order to learn the target constraint network.

Web mining systems exploit the redundancy of data published on the Web to automatically extract information from existing Web documents. The first step in the information extraction process is thus to locate within a limited period of time as many Web pages as possible that contain relevant information, a task which is commonly accomplished by applying focused crawling techniques. The performance of such a crawler can be measured by its "recall", i.e. the percentage of documents found and identified as relevant compared to the number of existing documents. A higher recall value implies that more redundant data is available, which in turn leads to better results in the subsequent fact extraction phase. In this paper, we propose xCrawl, a new focused crawling method which outperforms state-of-the-art approaches with respect to recall values achievable within a given period of time. This method is based on a new combination of ideas and techniques used to identify and exploit navigational structures of Websites, such as hierarchies, lists or maps. In addition, automatic query generation is applied to rapidly collect Web sources containing target documents. The proposed crawling technique was inspired by the requirements of a Web mining system developed to extract product and service descriptions and was evaluated in different application scenarios. Comparisons with existing focused crawling techniques reveal that the new crawling method leads to a significant increase in recall whilst maintaining precision.

Recommenders support effective product retrieval processes for online users. These systems propose repair actions in situations where no solution can be found and derive recommendations including a set of explanations as to why a certain product has been selected. In this context utility constraints (scoring rules) have to be defined which specify the way utilities of products, explanations, and repair alternatives are determined. Such constraints can be faulty which means that they calculate rankings in a way not expected by marketing and sales experts. The maintenance and repair of such constraints is an extremely error-prone task. In this paper we present an intelligent environment which supports the automated adaptation of faulty utility constraints taking into account existing marketing and sales requirements. In this context we discuss experiences from commercial projects.

One of the common approaches to extracting high-quality knowledge from Web sources is to exploit the redundancy of the published information. Therefore, a Web Mining System not only has to search for relevant Web pages but also has to somehow determine whether two pages describe the same entity in order to extract as much knowledge as possible about it. It has been shown that statistical clustering techniques are in general a suitable means to achieve this task by grouping documents that are supposed to contain similar information. However, when data is given in tabular form - which is for instance a typical way of describing items in online shops - existing document clustering algorithms show limited performance as documents containing tabular descriptions typically share a very common set of tokens although they describe different entities. In this paper we therefore propose a new document clustering approach that exploits hyperlinks and document metadata to extract candidates for entity names. These candidate names are subsequently used to cluster the documents and further improve these names, which are finally used to determine whether two documents describe the same entity. The detailed evaluation of our approach in two popular example domains showed its high accuracy in terms of precision and recall (F-Measure > 0.9).

We present a model for the integration of intelligent user interfaces and configuration techniques. This model enhances the capabilities of online stores by supporting the development of configuration systems that assist customers in a personalised way, while they selects the features of the products/services to be configured.

PURPOSE: Demonstration of a technique for three-dimensional (3-D) assessment of tracheal-stenoses, regarding site, length and degree, based on spiral computed tomography (S-CT). PATIENTS AND METHODS: S-CT scanning and automated segmentation of the laryngo-tracheal tract (LTT) was followed by the extraction of the LTT medial axis using a skeletonization algorithm. Orthogonal to the medial axis the LTT 3-D cross-sectional profile was computed and presented as line charts, where degree and length was obtained. Values for both parameters were compared between 36 patients and 18 normal controls separately. Accuracy and precision was derived from 17 phantom studies. RESULTS: Average degree and length of tracheal stenoses was found to be 60.5% and 4.32 cm in patients compared with minor caliber changes of 8.8% and 2.31 cm in normal controls (p << 0.0001). For the phantoms an excellent correlation between the true and computed 3-D cross-sectional profile was found (p << 0.005) and an accuracy for length and degree measurements of 2.14 mm and 2.53% respectively could be determined. The corresponding figures for the precision were found to be 0.92 mm and 2.56%. CONCLUSION: LTT 3-D cross-sectional profiles permit objective, accurate and precise assessment of LTT caliber changes. Minor LTT caliber changes can be observed even in normals and, in case of an otherwise normal S-CT study, can be regarded as artifacts.

In many domains, software development has to meet the challenges of developing highly adaptable software very rapidly. In order to accomplish this task, domain specific, formal description languages and knowledge-based systems are employed. From the viewpoint of the industrial software development process, it is important to integrate the construction and maintenance of these systems into standard software engineering processes. In addition, the descriptions should be comprehensible for the domain experts in order to facilitate the review process. For the realization of product configuration systems, we show how these requirements can be met by using a standard design language (UML-Unified Modeling Language) as notation in order to simplify the construction of a logic-based description of the domain knowledge. We show how classical description concepts for expressing configuration knowledge can be introduced into UML and be translated into logical sentences automatically. These sentences are exploited by a general inference engine solving the configuration task.

The state of the art in hardware design is the use of hardware description languages such as VHDL. The designs are tested by simulating them and comparing their output to that prescribed by the specification. A significant part of the design effort is spent on detecting unacceptable deviations from this specification and subsequently localizing the sources of such faults. In this paper, we describe an approach to employ model-based diagnosis for fault detection and localization in very large VHDL programs, by automatically generating the diagnosis model from the VHDL code and using observations about the program behavior to derive possible fault locations from the model. In order to achieve sufficient performance for practical applicability, we have developed a representation that provides a highly abstracted view of programs and faults, but is sufficiently detailed to yield substantial reductions in the fault localization costs when compared to the current manpower-intensive approach. The implementation in conjunction with the knowledge representation is designed with openness in mind in order to facilitate use of the highly optimized simulation tools available.

This paper describes ARTEX, a knowledge based system developed for quality assurance and fault localization in audio routing systems. Our system covers a large class of routing systems which may be flexibly configured. ARTEX uses an object-oriented model to represent the generic concepts and individual configurations. Fault localization strategies are realized by methods associated with objects and by heuristic rules focusing the diagnostic search.