We provide two approaches for explaining inconsistency in multi-context systems, where decentralized and heterogeneous system parts interact via nonmonotonic bridge rules. Inconsistencies arise easily in such scenarios, and nonmonotonicity calls for specific methods of inconsistency analysis. Both our approaches characterize inconsistency in terms of involved bridge rules: either by pointing out rules which need to be altered for restoring consistency, or by finding combinations of rules which cause inconsistency. We show duality and modularity properties, give precise complexity characterizations, and provide algorithms for computation using HEX-programs. Our results form a basis for inconsistency management in heterogeneous knowledge integration systems.

Galles and Pearl [1998] claimed that ``for recursive models, the causal model framework does not add any restrictions to counterfactuals, beyond those imposed by Lewis's [possible-worlds] framework.''  This claim is shown to be false.  Indeed, the opposite claim is true: recursive models are shown to correspond precisely to a subclass of (possible-world) counterfactual structures.  On the other hand, a slight generalization of recursive models, models where all equations have unique solutions, is shown to be incomparable in expressive power to counterfactual structures, despite the fact that the Galles and Pearl arguments should apply to them as well.  The problem with the Galles and Pearl argument is identified: an axiom that they viewed as irrelevant, because it involved disjunction (which was not in their language), is not irrelevant at all. 

Existing action calculi provide rich, declarative formalisms for reasoning about actions. BDI-based programming languages like AgentSpeak, on the other hand, are procedural and geared towards practical applications of cognitive agents. In this paper, we close the gap between these two lines of research by integrating action calculi and AgentSpeak programs. Specifically, we develop a new and purely declarative semantics for AgentSpeak, which paves the way for combining this language with any suitable action calculus in a strictly modular fashion. As the main technical result, we prove that the new declarative semantics is correct wrt. the standard operational semantics for AgentSpeak. This provides the basis for a modular integration of a BDI-based agent programming language with sophisticated methods for reasoning about actions.

We show that linear logic can serve as an expressive framework in which to model a rich variety of combinatorial auction mechanisms. Due to its resource-sensitive nature, linear logic can easily represent bids in combinatorial auctions in which goods may be sold in multiple units, and we show how it naturally generalises several bidding languages familiar from the literature. Moreover, the winner determination problem, i.e., the problem of computing an allocation of goods to bidders producing a certain amount of revenue for the auctioneer, can be modelled as the problem of finding a proof for a particular linear logic sequent.

In discrete dynamical systems change results from actions. As such, given a set of observations, diagnoses often take the form of posited events that result in the observed behaviour. In this paper we revisit formal characterizations of diagnosis, and their relationship to planning. We do so from both a theoretical and a computational perspective. In particular, we extend the characterization of diagnosis to deal with the case of incomplete information, and rich preferences. We also explore the use of state-of-the-art planning technology for the automated generation of diagnoses. Examining several classes of diagnosis problems, we provide both proof of concept and benchmark experiments, the latter showing superior performance to a leading diagnosis engine. Our findings help support the hypothesis that planning technology holds great promise for efficient generation of diagnoses.

Sequential diagnosis takes measurements of an abnormal system to identify faulty components, where the goal is to reduce the diagnostic cost , defined here as the number of measurements. To propose measurement points, previous work employs a heuristic based on reducing the entropy over a set of diagnoses , which can be impractical when the set of diagnoses is too large. Focusing on a smaller set of probable diagnoses scales the approach but generally leads to increased diagnostic cost. We propose a new diagnostic framework employing three new techniques — a more efficient heuristic for measurement point selection, abstraction-based sequential diagnosis, and component cloning — which scales to large systems with good performance in terms of diagnostic cost.

In particular, I will explain how the complexity scheduling, planning, graph problems, among others. The landscape differs for traditional reasoning and for query most well-known constraint satisfaction problem is propositional answering, and take a brief look at computational complexity satisfiability SAT. Of particular recent interest is satisfiability issues raised by implementations of DL query answering modulo theories (SMT), where the interpretation based on standard relational database systems. Throughout of some symbols is constrained by a background theory. For the tutorial, connections to the W3C-standard OWL are example, the theory of arithmetic restricts the interpretation drawn whenever possible. of symbols such as:,, 0, and 1. SMT draws on the most prolific problems in the past century What If You Wanted Someone (Else) to Use This?

Anytime search algorithms solve optimisation problems by quickly finding a (usually suboptimal) first solution and then finding improved solutions when given additional time. To deliver an initial solution quickly, they are typically greedy with respect to the heuristic cost-to-go estimate h. In this paper, we show that this low-h bias can cause poor performance if the greedy search makes early mistakes. Building on this observation, we present a new anytime approach that restarts the search from the initial state every time a new solution is found. We demonstrate the utility of our method via experiments in PDDL planning as well as other domains, and show that it is particularly useful for problems where the heuristic has systematic errors.

Computing a good policy in stochastic uncertain environments with unknown dynamics and reward model parameters is a challenging task. In a number of domains, ranging from space robotics to epilepsy management, it may be possible to have an initial training period when suboptimal performance is permitted. For such problems it is important to be able to identify when this training period is complete, and the computed policy can be used with high confidence in its future performance. A simple principled criteria for identifying when training has completed is when the error bounds on the value estimates of the current policy are sufficiently small that the optimal policy is fixed, with high probability. We present an upper bound on the amount of training data required to identify the optimal policy as a function of the unknown separation gap between the optimal and the next-best policy values. We illustrate with several small problems that by estimating this gap in an online manner, the number of training samples to provably reach optimality can be significantly lower than predicted offline using a Probably Approximately Correct framework that requires an input epsilon parameter.

Forward State Planning with Reachability Heuristics is arguably the most successful approach to Automated Planning up to date. In addition to an estimation of the distance to the goal, relaxed plans obtained with such heuristics provide the search with useful information such as helpful actions and look-ahead states. However, this information is extracted only from the beginning of the relaxed plan. In this paper, we propose using information extracted from the last actions in the relaxed plan to generate intermediate goals backwards. This allows us to use information from previous computations of the heuristic and reduce the depth of the search tree.