Project Dynamo

John Bell
john.bell@dcs.qmw.ac.uk,
Wilfred Hodges
w.hodges@qmw.ac.uk,
Graham White
graham@dcs.qmw.ac.uk,
Department of Computer Science,
Queen Mary and Westfield College,
University of London.

The Dynamo Project, (An investigation of the model-based implementation of pragmatic reasoning) is a three-year EPSRC-funded research project investigating the model-building approach to implementing nonmonotonic reasoning, which has been running for just over six months.

Pragmatic reasoning

Pragmatic reasoning (commonsense reasoning, nonmonotonic reasoning) is concerned with context-dependent inference; with what follows from the premises in a given context. Typically the context is incompletely specified. In such cases we make assumptions about what is normal or typical or conventional given the context and its limitations. For example, an agent planning to catch a bus might reason that the bus will come on time because it normally does and there is no reason to think otherwise; that is, there is nothing about the context which leads the agent to think otherwise. Defeasible inference of this kind is essential in daily life and its formalisation and implementation is a central concern of AI.

A paradox

We are expert pragmatic reasoners. We are able to produce reasonable conclusions quickly and with little or no effort. By contrast we tend to find semantic reasoning (context-free deductive reasoning of the kind traditionally studied) difficult. However, attempts at providing proof-theoretical formalisations of pragmatic reasoning, in nonmonotonic logics such as Default Logic [Reiter 1980], suggest paradoxically that pragmatic reasoning is harder, both conceptually and technically, than semantic reasoning. For example, the application of a default rule is, in comparison with typical deduction rules, hard to grasp, and the task of determining whether a given sentence is in an extension of even a semi-normal default theory is, because of the consistency check, NP-hard in the propositional case and undecidable in the first-order case [Kautz and Selman 1989]. One response is to attempt to find tractable subsets of such logics.

The model-building approach

However, it is possible to use model theory to formalise pragmatic reasoning, and we propose to resolve the paradox of Section 2 by implementing the model theory of pragmatic logics. A general theory has been outlined [Bell 1995]. This recommends replacing mathematical models by tractable computational models in a principled way (model schemas, model circumscription), and then building (dynamic model theory) and evaluating the relevant computational models (evaluative confirmational proof theory).

Causal theories

In [Bell forthcoming] the programme recommended by the theory is carried out in the case of causal theories of the kind defined by Shoham [Shoham 1988] and extended by [Bell 1991]. To begin with, causal theories are reformulated on the basis of Kleene three-valued logic [Kleene 1952]. This simplifies the model theory, as it has the effect of removing possible-worlds structures from the models. As the interpretation of terms will be fixed by each causal theory, the uniqueness theorem guarantess that we need build only a single relevant model of it, and furthermore the theorem shows how this model can be constructed. In order to make such models tractable, we require that they have finite domains. Futhermore, it is not necessary to construct complete models. It is sufficient that for any time point t we can construct the time-bounded model M/t.; that is, the initial part of the model M "up to t". The construction starts with an initial time point t0 and model M/t0. Each M/t is then extended to M/t+1 by "temporal forward chaining" on the causal rules using the facts added at t as triggers. This is model building, rather than theorem proving, as the antecedents of causal rules are evaluated in M/t, and if these are true, their consequents are used to extend M/t. In particular a conjunct 'not p' occuring in the antecedent of a rule is simply evaluated in M/t; whereas establishing it proof-theoretically requires a (theoretically intractable) meta-level proof that p is not provable. The rules can thus be regarded as detailed instructions for building models. In static model theory, rules classify models. In dynamic model theory rules build models. In the class of models considered, the cost of building M/t is, in practice, polynominal, when the cost of applying a cuasal rule (making a causal inference in) M/t is linear.

Ongoing and Future Work

We are extending the work in Section 4 to more complex theories of causal reasoning, and aim to extend this work still further and apply the theory to teleological reasoning; in particular, to the persistence of mental states and rational agency [Bell 1995a]. The major problem is to restrict the number of computational models it is necessary to build and evaluate. This is can be done by extending the above idea of a model schema (one partial model representing a class of complete models) further; and many interesting ideas are being explored. The aim is to maintain mathematical integrity while achieving something like parity with human reasoners (natural complexity).

References

J. Bell (1991) Extended causal theories, Artificial Intelligence 48, 211-224.

J. Bell (1995) Pragmatic reasoning; a model-based theory. In: Applied Logic: How, What and Why? A selection of papers from the Applied Logic Conference, Amsterdam 1992. M. Masuch and L. Polos (eds.), Kluwer Academic Publishers, pp. 1-27. PostScript version available.

J. Bell (1995a) Changing Attitudes. In: Intelligent Agents. M.J. Wooldridge and N.R. Jennings (eds.). Springer Lecture Notes in AI, No 890. Springer: Berlin, pp. 40-55.

J. Bell (forthcoming) A model-based approach to predictive causal reasoning. In: Partiality, Modality and Nonmonotonicity. P. Doherty (ed.). To appear in the Studies in Logic, Language and Information series, CSLI Press: Stanford.

H. Kautz and B. Selman (1989) Hard problems for simple default logics, KR'89, 189-197.

S. Kleene (1952) Introduction to Metamathematics, North-Holland: Amsterdam.

R. Reiter (1980) A logic for default reasoning, Artificial Intelligence 13, 81-132.

Y. Shoham (1988), Reasoning About Change, MIT Press: Cambridge MA.

G. White, J. Bell and W. Hodges, Building Models of Prediction Theories, Working Paper, 1997. PostScript, dvi.