This is a case-study in knowledge representation. We analyze the 'one hundred prisoners and a lightbulb' puzzle. In this puzzle it is relevant what the agents (prisoners) know, how their knowledge changes due to observations, and how they affect the state of the world by changing facts, i.e., by their actions. These actions depend on the history of previous actions and observations. Part of its interest is that all actions are local, i.e. not publicly observable, and part of the problem is therefore how to disseminate local results to other agents, and make them global. The various solutions to the puzzle are presented as protocols (iterated functions from agent's local states, and histories of actions, to actions). The computational aspect is about average runtime termination under conditions of random ('fair') scheduling. The paper consists of three parts. First, we present different versions of the puzzle, and their solution. This includes a probabilistic version, and a version assuming synchronicity (the interval between prisoners' interrogations is known). The latter is very informative for the prisoners, and allows different protocols (with faster expected termination). Then, we model the puzzle in an epistemic logic incorporating dynamic operators for the effects of information changing events. Such events include both informative actions, where agents become more informed about the non-changing state of the world, and factual changes, wherein the world and the facts describing it change themselves as well. Finally, we give the expected termination results of several protocols when assuming random scheduling. This paper integrates the literature and presents novel contributions. Novel are: Firstly, Protocol 2 and Protocol 4. Secondly, the modelling in dynamic epistemic logic in its entirety - we do not know of a case study that combines factual and informational dynamics in a setting of non-public events, or of a similar proposal to handle asynchronous behaviour in a dynamic epistemic logic. Thirdly, our computational results on Protocol 2 and results from the manuscript from author Wu.

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.

We present a distributed algorithm for computing equilibria of heterogeneous nonmonotonic multi-context systems (MCS). The algorithm can be parametrized to compute only partial equilibria, which can be used for reasoning tasks like query answering or satisfiability checking that need only partial information and not whole belief states. Furthermore, caching is employed to cut redundant solver calls. As a showcase, we instantiate the MCS framework with answer set program contexts. To characterize equilibria of such MCS, we develop notions of loop formulas that enable reductions to the classical satisfiability problem (SAT). Notably, loop formulas for bridge rules between contexts and for the local contexts can be combined to a uniform encoding of an MCS into a (distributed) SAT instance. As a consequence, we can use SAT solvers for belief set building. We demonstrate this approach by an experimental prototype implementation, which uses an off-the-shelf SAT solver.

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.

Abduction is a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we focus on propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be Σ p 2 -complete in general. We consider variants obtained by restricting the allowed connectives in the formulae to certain sets of Boolean functions. We give a complete classification of the complexity for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete and polynomial cases; and we highlight sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.

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?

We often deal with dynamic worlds where actions are executed by agents and events may happen. Example of such worlds range from virtual worlds such as the world of a database to robots and humans in physical worlds. To understand the dynamics of such worlds as well as to be able to assert some control over such worlds one needs to reason about the actions and events and how they may change the world. In this invited talk we will present some of the important results in this field and present some future directions. In particular, we will discuss how theories and results from reasoning about actions and change can be combined with theories and results in dynamic epistemic logics to obtain a unified theory of multi-agent actions.

Invited Talk by Ian Horrocks Ontologies and ontology based systems are rapidly becoming mainstream technologies, with RDF and OWL now being deployed in diverse application domains, and with major technology vendors starting to augment their existing systems with ontological reasoning. For example, Oracle Inc. recently enhanced its well-known database management system with modules that use RDF/OWL ontologies to support "semantic data management," and their product brochure lists numerous application areas that can benefit from this technology, including enterprise information integration, knowledge mining, finance, compliance management and life science research. While gratifying to the KR research community, this success also brings with it many challenges. In particular, ontology reasoning systems will need to exhibit robust scalability if deployments in large scale applications are to be successful.