Probabilistic Logic Programming (PLP), exemplified by Sato and Kameya's PRISM, Poole's ICL, Raedt et al's ProbLog and Vennekens et al's LPAD, is aimed at combining statistical and logical knowledge representation and inference. A key characteristic of PLP frameworks is that they are conservative extensions to non-probabilistic logic programs which have been widely used for knowledge representation. PLP frameworks extend traditional logic programming semantics to a distribution semantics, where the semantics of a probabilistic logic program is given in terms of a distribution over possible models of the program. However, the inference techniques used in these works rely on enumerating sets of explanations for a query answer. Consequently, these languages permit very limited use of random variables with continuous distributions. In this paper, we present a symbolic inference procedure that uses constraints and represents sets of explanations without enumeration. This permits us to reason over PLPs with Gaussian or Gamma-distributed random variables (in addition to discrete-valued random variables) and linear equality constraints over reals. We develop the inference procedure in the context of PRISM; however the procedure's core ideas can be easily applied to other PLP languages as well. An interesting aspect of our inference procedure is that PRISM's query evaluation process becomes a special case in the absence of any continuous random variables in the program. The symbolic inference procedure enables us to reason over complex probabilistic models such as Kalman filters and a large subclass of Hybrid Bayesian networks that were hitherto not possible in PLP frameworks. (To appear in Theory and Practice of Logic Programming).

One of the goals of the study of music theory is to develop sets of rules to describe different styles of music. By formalising these rules so that their semantics are machine intelligible, it is possible to use computers to reason about and analyse these rules -- computational music theory. Anton is an automatic composition system based on this approach. It formalises the rules of Renaissance Counterpoint using AnsProlog and uses an answer set solver to compose pieces. This paper discusses Anton, presenting the ideas behind the system and focusing on the challenges of modelling and synthesising rhythm.

Building complete interactive narrative systems is hard. Building systems that are satisfying for naïve users is especially hard since small deficiencies in component technologies can easily destroy the experience for a user. In this paper I argue that we can ameliorate some of these technical limitations through careful choice of genre and style, and discuss a number of properties of farce that make it a particularly attractive choice. Then I will describe work in progress on Punch and Judy AI Playset, a system that allows users to explore possible narratives in the Punch and Judy story world.

The field of game AI is largely industry driven, lacking an agreed upon formalism for AI representation. Ad-hoc scripting languages, simple finite state machines, behaviour trees, and planners are employed, but not in a fashion adhering to any standard. As a result, reuse is sparse between games and formal analysis techniques are undeveloped. As research for a Ph.D. thesis, we propose to show that a layered Statechart-based AI is a suitable formalism for Game AI, enabling the use of model-driven development techniques such as reuse and high-level analysis including model-checking. The fundamentally modular nature of this approach leads naturally to reuse as a fundamental component of the design process. Supported by a clearly defined formalism, useful behavioural analyses become possible, such as testing reactions to various inputs at design time. We also explore transformations at the modelling level to enable procedural generation, allowing rapid deployment of varying AIs. Additionally, such a model allows for the generation of efficient code that can be directly inserted into games. Tool support for reuse, generation, and analysis will be developed, then employed in creating an industrial scale AI, proving that this formalism is appropriate for industrial use.

Morals are an important part of many stories, and central to why storytelling developed in the first place as a means of communication. They have the potential to provide a framework for developing story structure, which could be utilised by modern storytelling systems. To achieve this we need a general representation for morals. We propose patterns of character emotion as a suitable foundation. In this paper, we categorise Aesop’s fables based on the morals they convey, and use them as a source of emotion data corresponding to those morals. We use inductive logic programming to identify relationships between particular patterns of emotion and the morals of the stories in which they arise.

In this work, we propose Answer-Set Programming (ASP) as a tool for rapid prototyping of dynamic programming algorithms based on tree decompositions. In fact, many such algorithms have been designed, but only a few of them found their way into implementation. The main obstacle is the lack of easy-to-use systems which (i) take care of building a tree decomposition and (ii) provide an interface for declarative specifications of dynamic programming algorithms. In this paper, we present D-FLAT, a novel tool that relieves the user of having to handle all the technical details concerned with parsing, tree decomposition, the handling of data structures, etc. Instead, it is only the dynamic programming algorithm itself which has to be specified in the ASP language. D-FLAT employs an ASP solver in order to compute the local solutions in the dynamic programming algorithm. In the paper, we give a few examples illustrating the use of D-FLAT and describe the main features of the system. Moreover, we report experiments which show that ASPbased D-FLAT encodings for some problems outperform monolithic ASP encodings on instances of small treewidth. To appear in Theory and Practice of Logic Programming (TPLP).

This paper considers the fragment ∃∀SO of second-order logic. Many interesting problems, such as conformant planning, can be naturally expressed as finite domain satisfiability problems of this logic. Such satisfiability problems are computationally hard (ΣP2) and many of these problems are often solved approximately. In this paper, we develop a general approximative method, i.e., a sound but incomplete method, for solving ∃∀SO satisfiability problems. We use a syntactic representation of a constraint propagation method for first-order logic to transform such an ∃∀SO satisfiability problem to an ∃SO(ID) satisfiability problem (second-order logic, extended with inductive definitions). The finite domain satisfiability problem for the latter language is in NP and can be handled by several existing solvers. Inductive definitions are a powerful knowledge representation tool, and this moti- vates us to also approximate ∃∀SO(ID) problems. In order to do this, we first show how to perform propagation on such inductive definitions. Next, we use this to approximate ∃∀SO(ID) satisfiability problems. All this provides a general theoretical framework for a number of approximative methods in the literature. Moreover, we also show how we can use this framework for solving practical useful problems, such as conformant planning, in an effective way.

Automated reasoning about uncertain knowledge has many applications. One difficulty when developing such systems is the lack of a completely satisfactory integration of logic and probability. We address this problem directly. Expressive languages like higher-order logic are ideally suited for representing and reasoning about structured knowledge. Uncertain knowledge can be modeled by using graded probabilities rather than binary truth-values. The main technical problem studied in this paper is the following: Given a set of sentences, each having some probability of being true, what probability should be ascribed to other (query) sentences? A natural wish-list, among others, is that the probability distribution (i) is consistent with the knowledge base, (ii) allows for a consistent inference procedure and in particular (iii) reduces to deductive logic in the limit of probabilities being 0 and 1, (iv) allows (Bayesian) inductive reasoning and (v) learning in the limit and in particular (vi) allows confirmation of universally quantified hypotheses/sentences. We translate this wish-list into technical requirements for a prior probability and show that probabilities satisfying all our criteria exist. We also give explicit constructions and several general characterizations of probabilities that satisfy some or all of the criteria and various (counter) examples. We also derive necessary and sufficient conditions for extending beliefs about finitely many sentences to suitable probabilities over all sentences, and in particular least dogmatic or least biased ones. We conclude with a brief outlook on how the developed theory might be used and approximated in autonomous reasoning agents. Our theory is a step towards a globally consistent and empirically satisfactory unification of probability and logic.

In the area of reasoning about actions, one of the key computational problems is the projection problem: to find whether a given logical formula is true after performing a sequence of actions. This problem is undecidable in the general situation calculus; however, it is decidable in some fragments. We consider a fragment P of the situation calculus and Reiter’s basic action theories (BAT) such that the projection problem can be reduced to the satisfiability problem in an expressive description logic ALCO(U) that includes nominals (O), the universal role (U), and constructs from the well-known logic ALC. It turns out that our fragment P is more expressive than previously explored description logic based fragments of the situation calculus. We explore some of the logical properties of our theories. In particular, we show that the projection problem can be solved using regression in the case where BATs include a general “static” TBox, i.e., an ontology that has no occurrences of fluents. Thus, we propose seamless integration of traditional ontologies with reasoning about actions. We also show that the projection problem can be solved using progression if all actions have only local effects on the fluents, i.e., in P, if one starts with an incomplete initial theory that can be transformed into an ALCO(U) concept, then its progression resulting from the execution of a ground action can still be expressed in the same language. Moreover, we show that for a broad class of incomplete initial theories progression can be computed efficiently.

We define a notion of bounded action theory in the situation calculus, where the theory entails that in all situations, the number of ground fluent atoms is bounded by a constant. Such theories can still have an infinite domain and an infinite set of states. We argue that such theories are fairly common in applications, either because facts do not persist indefinitely or because one eventually forgets some facts, as one learns new ones. We discuss various ways of obtaining bounded action theories. The main result of the paper is that verification of an expressive class of first-order $\mu$-calculus temporal properties in such theories is in fact decidable. This paper is an abridged version of a paper appeared in KR'12.