Abstraction is a powerful technique that has not been considered much for nonmonotonic reasoning formalisms including Answer Set Programming (ASP), apart from related simplification methods. We introduce a notion for abstracting from the domain of an ASP program that shrinks the domain size and over-approximates the set of answer sets, as well as an abstraction-&-refinement methodology that, starting from an initial abstraction, automatically yields an abstraction with an associated answer set matching an answer set of the original program if one exists. Experiments reveal the potential of the approach, by its ability to focus on the program parts that cause unsatisfiability and by achieving concrete abstract answer sets that merely reflect relevant details.

Abstraction is an important technique utilized by humans in model building and problem solving, in order to figure out key elements and relevant details of a world of interest. This naturally has led to investigations of using abstraction in AI and Computer Science to simplify problems, especially in the design of intelligent agents and automated problem solving. By omitting details, scenarios are reduced to ones that are easier to deal with and to understand, where further details are added back only when they matter. Despite the fact that abstraction is a powerful technique, it has not been considered much in the context of nonmonotonic knowledge representation and reasoning, and specifically not in Answer Set Programming (ASP), apart from some related simplification methods. In this work, we introduce a notion for abstracting from the domain of an ASP program such that the domain size shrinks while the set of answer sets (i.e., models) of the program is over-approximated. To achieve the latter, the program is transformed into an abstract program over the abstract domain while preserving the structure of the rules. We show in elaboration how this can be also achieved for single or multiple sub-domains (sorts) of a domain, and in case of structured domains like grid environments in which structure should be preserved. Furthermore, we introduce an abstraction-&-refinement methodology that makes it possible to start with an initial abstraction and to achieve automatically an abstraction with an associated abstract answer set that matches an answer set of the original program, provided that the program is satisfiable. Experiments based on prototypical implementations reveal the potential of the approach for problem analysis, by its ability to focus on the parts of the program that cause unsatisfiability and by achieving concrete abstract answer sets that merely reflect relevant details. This makes domain abstraction an interesting topic of research whose further use in important areas like Explainable AI remains to be explored.

Answer Set Programming (ASP) is a well-known formalism for Knowledge Representation and Reasoning, successfully employed to solve many AI problems, also thanks to the availability of efficient implementations. Traditionally, ASP systems are based on the ground&solve approach, where the grounding transforms a general input program into its propositional counterpart, whose stable models are then computed by the solver using the CDCL algorithm. This approach suffers an intrinsic limitation: the grounding of one or few constraints may be unaffordable from a computational point of view; a problem known as grounding bottleneck. In this paper, we develop an innovative approach for evaluating ASP programs, where some of the constraints of the input program are not grounded but automatically translated into propagators of the CDCL algorithm that work on partial interpretations. We implemented the new approach on top of the solver WASP and carried out an experimental analysis on different benchmarks. Results show that our approach consistently outperforms state-of-the-art ASP systems by overcoming the grounding bottleneck.

Abstract Answer Set Programming (ASP) is a well-known declarative formalism in logic programming. Efficient implementations made it possible to apply ASP in many scenarios, ranging from deductive databases applications to the solution of hard combinatorial problems. State-of-the-art ASP systems are based on the traditional ground&solve approach and are general-purpose implementations, i.e., they are essentially built once for any kind of input program. In this paper, we propose an extended architecture for ASP systems, in which parts of the input program are compiled into an ad-hoc evaluation algorithm (i.e., we obtain a specific binary for a given program), and might not be subject to the grounding step. To this end, we identify a condition that allows the compilation of a sub-program, and present the related partial compilation technique. Importantly, we have implemented the new approach on top of a well-known ASP solver and conducted an experimental analysis on publicly-available benchmarks. Results show that our compilation-based approach improves on the state of the art in various scenarios, including cases in which the input program is stratified or the grounding blow-up makes the evaluation unpractical with traditional ASP systems.

We describe the first automatic approach for merging coreference annotations obtained from multiple annotators into a single gold standard. This merging is subject to certain linguistic hard constraints and optimisation criteria that prefer solutions with minimal divergence from annotators. The representation involves an equivalence relation over a large number of elements. We use Answer Set Programming to describe two representations of the problem and four objective functions suitable for different data-sets. We provide two structurally different real-world benchmark data-sets based on the METU-Sabanci Turkish Treebank and we report our experiences in using the Gringo, Clasp and Wasp tools for computing optimal adjudication results on these data-sets.

In general, dynamic systems are systems with time-dependent behavior. Dynamic systems are characterized by the non-stationary data sequences they emit. One particular way to model these non-stationary sequences is to consider them as a sequence of stationary segments, regimes, where each regime is separated by regime switching points from both the preceding and subsequent regimes. In system identification and monitoring applications, it is crucial to correctly and timely detect these regime switching points. One promising estimation method that may be used for detecting regime switching points is the stochastic learning based weak estimation (SLWE) method by Oommen and Rueda. We use SLWE for estimating First Order Markov (FOM) probabilities between symbols emitted by a system and for predicting regime switching points. A switching point is detected when the SLWE estimator unlearns, i.e., adapts estimates of FOM probabilities to new observations, such that the estimate re-converges to a new value that reflects, for the new regime, the FOM dependency of system output tokens. In experiments with a real Dataset for Human Activity Recognition, we see that our method has attractive efficiency (time and space) and similar accuracy compared with the state-of the-art. Experiments with synthetic data, where we controlled noise and Hamming distance between regimes, show promising accuracy for noise rates up to 25%, a rate at which accuracy of state-of-the-art methods deteriorates. Our method is flexible and can be configured to use not only FOM but also second-order and prior symbol probabilities, and combinations thereof.

Industrial plant operators regularly observe a high number of alarms generated in a short period of time, a phenomenon which is referred to as alarm flooding. This causes plant downtime, not only because of the repair time but also by the time needed to identify the root cause of machine failure - which is difficult during an alarm flood. Therefore, diagnosis tools that perform root cause analysis to advise plant operators can help reduce the downtime, which is a crucial issue in industry. We analyse the reproducibility and applicability of an existing approach by Ahmed et al. (2013) which is based on agglomerative hierarchical clustering where raw data in the form of alarm logs is preprocessed, floods are detected, and then clustered. The aim is, that resulting clusters represent floods that originate from the same common root cause. We extend the approach with alternative similarity measures and perform experiments regarding their effectiveness in structuring industrial alarm flood data. In our evaluation we use a real industrial use case which contains more diverse data and a larger amount of data points compared with the original study.

Sequential data generated from various sources in a multi-mode industrial production system provides valuable information on the current mode of the system and enables one to build a model for each individual operating mode. Using these models in a multi-mode system, one may distinguish modes of the system and, furthermore, detect whether the current mode is a (normal or faulty) mode known from historical data, or a new mode. In this work, we model each individual mode by a probabilistic suffix tree (PST) used to implement variable order Markov models (VOMMs) and propose a novel unsupervised PST matching algorithm that compares the tree models by a matching cost once they are constructed. The matching cost we define comprises of a subsequence dissimilarity cost and a probability cost. Our tree matching method enables to compare two PSTs in linear time by one concurrent top-down pass. We use this matching cost as a similarity measure for k-medoid clustering and cluster PSTs obtained from system modes according to their matching costs. The overall approach yields promising results for unsupervised identification of modes on data obtained from of a physical factory demonstrator. Notably we can distinguish modes on two levels of granularity, both corresponding to human expert labels, with a RAND score of up to 73 % compared to a baseline of at most 42 %.

Abstract Answer set programming (ASP) is a well-established declarative paradigm. One of the successes of ASP is the availability of efficient systems. State-of-the-art systems are based on the ground+solve approach. In some applications, this approach is infeasible because the grounding of one or a few constraints is expensive. In this paper, we systematically compare alternative strategies to avoid the instantiation of problematic constraints, which are based on custom extensions of the solver. Results on real and synthetic benchmarks highlight some strengths and weaknesses of the different strategies.

We study abduction in First Order Horn logic theories where all atoms can be abduced and we are looking for preferred solutions with respect to three objective functions: cardinality minimality, coherence, and weighted abduction. We represent this reasoning problem in Answer Set Programming (ASP), in order to obtain a flexible framework for experimenting with global constraints and objective functions, and to test the boundaries of what is possible with ASP. Realizing this problem in ASP is challenging as it requires value invention and equivalence between certain constants, because the Unique Names Assumption does not hold in general. To permit reasoning in cyclic theories, we formally describe fine-grained variations of limiting Skolemization. We identify term equivalence as a main instantiation bottleneck, and improve the efficiency of our approach with on-demand constraints that were used to eliminate the same bottleneck in state-ofthe- art solvers. We evaluate our approach experimentally on the ACCEL benchmark for plan recognition in Natural Language Understanding. Our encodings are publicly available, modular, and our approach is more efficient than state-of-the-art solvers on the ACCEL benchmark.

Abstract As software systems are getting increasingly connected, there is a need for equipping nonmonotonic logic programs with access to external sources that are possibly remote and may contain information in heterogeneous formats. To cater for this need, hex programs were designed as a generalization of answer set programs with an API style interface that allows to access arbitrary external sources, providing great flexibility. Efficient evaluation of such programs however is challenging, and it requires to interleave external computation and model building; to decide when to switch between these tasks is difficult, and existing approaches have limited scalability in many real-world application scenarios. We present a new approach for the evaluation of logic programs with external source access, which is based on a configurable framework for dividing the non-ground program into possibly overlapping smaller parts called evaluation units. The latter will be processed by interleaving external evaluation and model building using an evaluation graph and a model graph, respectively, and by combining intermediate results. Experiments with our prototype implementation show a significant improvement compared to previous approaches. While designed for hex -programs, the new evaluation approach may be deployed to related rule-based formalisms as well.

HEX-programs extend logic programs under the answer set semantics with external computations through external atoms. As reasoning from ground Horn programs with nonmonotonic external atoms of polynomial complexity is already on the second level of the polynomial hierarchy, minimality checking of answer set candidates needs special attention. To this end, we present an approach based on unfounded sets as a generalization of related techniques for ASP programs. The unfounded set detection is expressed as a propositional SAT problem, for which we provide two different encodings and optimizations to them. We then integrate our approach into a previously developed evaluation framework for HEX-programs, which is enriched by additional learning techniques that aim at avoiding the reconstruction of the same or related unfounded sets. Furthermore, we provide a syntactic criterion that allows one to skip the minimality check in many cases. An experimental evaluation shows that the new approach significantly decreases runtime.

Pathfinding for a single agent is the problem of planning a route from an initial location to a goal location in an environment, going around obstacles. Pathfinding for multiple agents also aims to plan such routes for each agent, subject to different constraints, such as restrictions on the length of each path or on the total length of paths, no self-intersecting paths, no intersection of paths/plans, no crossing/meeting each other. It also has variations for finding optimal solutions, e.g., with respect to the maximum path length, or the sum of plan lengths. These problems are important for many real-life applications, such as motion planning, vehicle routing, environmental monitoring, patrolling, computer games. Motivated by such applications, we introduce a formal framework that is general enough to address all these problems: we use the expressive high-level representation formalism and efficient solvers of the declarative programming paradigm Answer Set Programming. We also introduce heuristics to improve the computational efficiency and/or solution quality. We show the applicability and usefulness of our framework by experiments, with randomly generated problem instances on a grid, on a real-world road network, and on a real computer game terrain.

Abstract We study the problem of finding optimal plans for multiple teams of robots through a mediator, where each team is given a task to complete in its workspace on its own and where teams are allowed to transfer robots between each other, subject to the following constraints: 1) teams (and the mediator) do not know about each other's workspace or tasks (e.g., for privacy purposes); 2) every team can lend or borrow robots, but not both (e.g., transportation/calibration of robots between/for different workspaces is usually costly). We present a mathematical definition of this problem and analyze its computational complexity. We introduce a novel, logic-based method to solve this problem, utilizing action languages and answer set programming for representation, and the state-of-the-art ASP solvers for reasoning. We show the applicability and usefulness of our approach by experiments on various scenarios of responsive and energy-efficient cognitive factories.