Repeated executions of reasoning tasks for varying inputs are necessary in many applicative settings, such as stream reasoning. In this context, we propose an incremental grounding approach for the answerset semantic...
详细信息
Repeated executions of reasoning tasks for varying inputs are necessary in many applicative settings, such as stream reasoning. In this context, we propose an incremental grounding approach for the answerset semantics. We focus on the possibility of generating incrementally larger ground logic programs equivalent to a given non-ground one;so called overgrounded programs can be reused in combination with deliberately many different sets of inputs. Updating overgrounded programs requires a small effort, thus making the instantiation of logic programs considerably faster when grounding is repeated on a series of inputs similar to each other. Notably, the proposed approach works "under the hood", relieving designers of logic programs from controlling technical aspects of grounding engines and answerset systems. In this work we present the theoretical basis of the proposed incremental grounding technique, we illustrate the consequent repeated evaluation strategy and report about our experiments.
Propositional satisfiability (or satisfiability) and answer set programming are two closely related subareas of Artificial Intelligence that are used to model and solve difficult combinatorial search problems. Satisfi...
详细信息
Propositional satisfiability (or satisfiability) and answer set programming are two closely related subareas of Artificial Intelligence that are used to model and solve difficult combinatorial search problems. Satisfiability solvers and answerset solvers are the software systems that find satisfying interpretations and answersets for given propositional formulas and logic programs, respectively. These systems are closely related in their common design patterns. In satisfiability, a propositional formula is used to encode problem specifications in a way that its satisfying interpretations correspond to the solutions of the problem. To find solutions to a problem it is then sufficient to use a satisfiability solver on a corresponding formula. Niemela, Marek, and TruszczyA"ski coined answer set programming paradigm in 1999: in this paradigm a logic program encodes problem specifications in a way that the answersets of a logic program represent the solutions of the problem. As a result, to find solutions to a problem it is sufficient to use an answerset solver on a corresponding program. These parallels that we just draw between paradigms naturally bring up a question: what is a fundamental difference between the two? This paper takes a close look at this question.
answer set programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particu...
详细信息
answer set programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particular, many Al problems such as reasoning in a nonmonotonic setting can be directly formulated in ASP. Although the main problems of ASP are of high computational complexity, complete for the second level of the Polynomial Hierarchy, several restrictions of ASP have been identified in the literature, under which ASP problems become tractable. In this paper we use the concept of backdoors to identify new restrictions that make ASP problems tractable. Small backdoors are sets of atoms that represent "clever reasoning shortcuts" through the search space and represent a hidden structure in the problem input. The concept of backdoors is widely used in theoretical investigations in the areas of propositional satisfiability and constraint satisfaction. We show that it can be fruitfully adapted to ASP. We demonstrate how backdoors can serve as a unifying framework that accommodates several tractable restrictions of ASP known from the literature. Furthermore, we show how backdoors allow us to deploy recent algorithmic results from parameterized complexity theory to the domain of answer set programming. (C) 2015 Elsevier B.V. All rights reserved.
Gelfond and Zhang recently proposed a new stable model semantics based on Vicious Circle Principle in order to improve the interpretation of logic programs with aggregates. The paper focuses on this proposal, and anal...
详细信息
Gelfond and Zhang recently proposed a new stable model semantics based on Vicious Circle Principle in order to improve the interpretation of logic programs with aggregates. The paper focuses on this proposal, and analyzes the complexity of both coherence testing and cautious reasoning under the new semantics. Some surprising results highlight similarities and differences versus mainstream stable model semantics for aggregates. Moreover, the paper reports on the design of compilation techniques for implementing the new semantics on top of existing ASP solvers, which eventually lead to realize a prototype system that allows for experimenting with Gelfond-Zhang's aggregates.
A qualitative approach to decision making under uncertainty has been proposed in the setting of possibility theory, which is based on the assumption that levels of certainty and levels of priority (for expressing pref...
详细信息
A qualitative approach to decision making under uncertainty has been proposed in the setting of possibility theory, which is based on the assumption that levels of certainty and levels of priority (for expressing preferences) are commensurate. In this setting, pessimistic and optimistic decision criteria have been formally justified. This approach has been transposed into possibilistic logic in which the available knowledge is described by formulas which are more or less certainly true and the goals are described in a separate prioritized base. This paper adapts the possibilistic logic handling of qualitative decision making under uncertainty in the answer set programming (ASP) setting. We show how weighted beliefs and prioritized preferences belonging to two separate knowledge bases can be handled in ASP by modeling qualitative decision making in terms of abductive logic programming where (uncertain) knowledge about the world and prioritized preferences are encoded as possibilistic definite logic programs and possibilistic literals respectively. We provide ASP-based and possibilistic ASP-based algorithms for calculating optimal decisions and utility values according to the possibilistic decision criteria. We describe a prototype implementing the algorithms proposed on top of different ASP solvers and we discuss the complexity of the different implementations. (C) 2013 Elsevier Inc. All rights reserved.
Diagnosis, i.e., the detection and identification of faults, provides the basis for bringing systems back to normal operation in case of a fault. Diagnosis is a very important task of our daily live, assuring safe and...
详细信息
Diagnosis, i.e., the detection and identification of faults, provides the basis for bringing systems back to normal operation in case of a fault. Diagnosis is a very important task of our daily live, assuring safe and reliable behavior of systems. The automation of diagnosis has been a successful research topic for several decades. However, there are limitations due to complexity issues and lack of expressiveness of the underlying reasoning mechanisms. More recently logic reasoning like answer set programming has gained a lot of attention and practical use. In this paper, we tackle the question whether answer set programming can be used for automating diagnosis, focusing on industrial applications. We discuss a formalization of the diagnosis problem based on answer set programming, introduce a general framework for modeling systems, and present experimental results of an answer set programming based diagnosis algorithm. Past limitations like not being able to deal with numerical operations for modeling can be solved to some extent. The experimental results indicate that answer set programming is efficient enough for being used in diagnosis applications, providing that the underlying system is of moderate size. For digital circuits having less than 500 components, diagnosis time has been less than one second even for computing triple fault diagnoses.
In answer set programming (ASP), the user can define declaratively a problem and solve it with efficient solvers;practical applications of ASP are countless and several constraint problems have been successfully solve...
详细信息
In answer set programming (ASP), the user can define declaratively a problem and solve it with efficient solvers;practical applications of ASP are countless and several constraint problems have been successfully solved with ASP. On the other hand, solution time usually grows in a superlinear way (often, exponential) with respect to the size of the instance, which is impractical for large instances. A widely used approach is to split the optimization problem into subproblems (SPs) that are solved in sequence, some committing to the values assigned by others, and reconstructing a valid assignment for the whole problem by juxtaposing the solutions of the single SPs. On the one hand, this approach is much faster due to the superlinear behavior;on the other hand, it does not provide any guarantee of optimality: committing to the assignment of one SP can rule out the optimal solution from the search space. In other research areas, logic-Based Benders decomposition (LBBD) proved effective;in LBBD, the problem is decomposed into a master problem (MP) and one or several SPs. The solution of the MP is passed to the SPs that can possibly fail. In case of failure, a no-good is returned to the MP that is solved again with the addition of the new constraint. The solution process is iterated until a valid solution is obtained for all the SPs or the MP is proven infeasible. The obtained solution is provably optimal under very mild conditions. In this paper, we apply for the first time LBBD to ASP, exploiting an application in health care as case study. Experimental results show the effectiveness of the approach. We believe that the availability of LBBD can further increase the practical applicability of ASP technologies.
Explainable artificial intelligence (XAI) aims at addressing complex problems by coupling solutions with reasons that justify the provided answer. In the context of answer set programming (ASP) the user may be interes...
详细信息
Explainable artificial intelligence (XAI) aims at addressing complex problems by coupling solutions with reasons that justify the provided answer. In the context of answer set programming (ASP) the user may be interested in linking the presence or absence of an atom in an answerset to the logic rules involved in the inference of the atom. Such explanations can be given in terms of directed acyclic graphs (DAGs). This article reports on the advancements in the development of the XAI system xASP by revising the main foundational notions and by introducing new ASP encodings to compute minimal assumption sets, explanation sequences, and explanation DAGs. DAGs are shown to the user in an interactive form via the xASP navigator application, also introduced in this work.
The answer set programming (ASP) Competition is a biannual event for evaluating declarative knowledge representation systems on hard and demanding AI problems. The competition consists of two main tracks: the ASP syst...
详细信息
The answer set programming (ASP) Competition is a biannual event for evaluating declarative knowledge representation systems on hard and demanding AI problems. The competition consists of two main tracks: the ASP system track and the model and solve track. The traditional system track compares dedicated answerset solvers on ASP benchmarks, while the model and solve track invites any researcher and developer of declarative knowledge representation systems to participate in an open challenge for solving sophisticated AI problems with their tools of choice. This article provides an overview of the ASP Competition series, reviews its origins and history, giving insights on organizing and running such an elaborate event, and briefly discusses the lessons learned so far.
answer set programming is a declarative programming paradigm based on the answerset semantics of logic programs. This introductory article provides the mathematical background for the discussion of answerset program...
详细信息
answer set programming is a declarative programming paradigm based on the answerset semantics of logic programs. This introductory article provides the mathematical background for the discussion of answer set programming in other contributions to this special issue.
暂无评论