Implementation of a belief revision system using Binary Decision Diagrams

Staff Member:
Maurice Pagnucco

Project Name:
Implementation of a belief revision system using Binary Decision Diagrams

Belief revision deals with the study of the manner in which intelligent artefacts represent and maintain beliefs about their environment. As new information is received, the stock of beliefs needs to be altered so as to accommodate the new information: new information added and, possibly, older information relinquished. Binary Decision Diagrams (BDDs) are a compact and efficient representation of propositional formulae. Implement McCain and Turner's causal theory of action and determine its feasibility by developing a test suite of problems.


The field of reasoning about action deals with how rational agents (a robot, program, etc.) reason about the ramifications of performing actions in a particular domain. In short, it aims to investigate solutions to the famous frame problem in Artificial Intelligence.

Recently, several causal approaches to reasoning about action have been proposed as a way of providing concise solutions to the frame problem. In this project we propose to study one such proposal by McCain and Turner which has attracted a lot of attention due to the rather simple statement for determining possible states of the world after actions have been performed (this is not to say it will be easy to implement however!). The project will involve an implementation of McCain and Turner's approach (perferably in Java) followed by a study of its feasibility by running it on a number of examples (many can be found in the literature but more will need to be developed). If time allows we can consider other causal approaches also.

McCain and Turner's approach revolves around a fixed point calculation. It involves set intersection, application of causal rules and some automated theorem proving. Known algorithms will need to be implemented and combined to achieve the result. Testing will need to be carried out throughout the project but paarticularly towards the conclusion of the project.

An understanding of some logic would be advantageous although not essential (this can be covered by the appropriate course at the beginning of the Honours year). Some mathematical sophistication would be required and curiosity regarding the formal aspects of reasoning ideal.

Background Reading:

Maurice Pagnucco (