Student Project Topics

Below is a list of topics for students who would like to work with me. For foreigner students (ie non Australian), it is very difficult for me to find fundings here in Australia. However, there are often many fundings in your countries. Send me an email in all cases.

Complexity of a diagnosis question

The problem of diagnosis is understanding what happens in a system given observations on its behaviour. In the model-based approach, it is often understood as computing all possible behaviours of the system. However, the diagnosis is often much more concrete and serves a real application. Some diagnosis questions are simpler to answer than other questions. In this project, we propose to investigate the complexity of answering particular questions given particular representations of the diagnosis.

Evaluation of the diagnosis cost

Diagnosis is the problem of understanding what happens in a system given observations of its behaviour. It is a prerequisite to find failures and perform repairs. Finding an accurate diagnosis is theoretically exponentially hard in the number of components of the system. In practice, the real cost highly depends on the system features. Some systems generate so many and so useful observations that the diagnosis is obvious; some systems require complex cross checkings to determine accurately what happened.

Being able to predict the cost is very important because we need to make sure that the diagnosis can be performed on time, and approximate techniques sometimes have to be used. This project proposes to find a method to empirically estimate this cost from the system model. Possible parameters include: the number of components, the number of states in the components, the ratio observable events/unobservable events, the tree-width of the system, etc.

Pre-processing in diagnosis by SAT

Diagnosis is the problem of understanding what happens in a system given observations of its behaviour. It is a prerequisite to find failures and perform repairs. A technique recently proposed for the diagnosis of DES is the use of Propositional Satisfiability (SAT), which is one of the most famous Computer Science problems.

The purpose of this project is to study how simple pre-processing actions impact on the runtime to solve the diagnosis. Typical techniques include local diagnosis which consists in performing a local non SAT-based diagnosis reasoning before running the SAT approach.

Automatic learning and accuracy of chronicles

Diagnosis is the problem of understanding what happens in a system given observations of its behaviour. It is a prerequisite to find failures and perform repairs. A popular method is the use of chronicles, patterns of temporary-constrained events. Each chronicle is associated with a particular type of behaviour (normal, failure, etc.), and the recognition of the chronicle implies the recognition of the associated behaviour.

A problem of the chronicle is that they are usually generated by hand by an expert. This implies many possible mistakes, from the simple typo to the default or the incompleteness in the expert knowledge. This project proposes to automatically learn chronicles from the system model (description of the system behaviour). It also includes the testing of the correctness of a set of chronicles.

Specialising SAT solvers for the diagnosis

Diagnosis is the problem of understanding what happens in a system given observations of its behaviour. It is a prerequisite to find failures and perform repairs. A technique recently proposed for the diagnosis of DES is the use of Propositional Satisfiability (SAT). SAT is one of the most famous Computer Science problems as it defines the NP-Complete complexity class and remains a hot research topic.

The aim of this project is to study the SAT heuristics that make the diagnosis problem easier to solve. It will suit particularly students who like to hack as SAT solvers are programs with no more than 1,000 lines but where any slight modification has a huge impact on the runtime.

Probabilistic reasonning on discrete event systems

Discrete-event system (DES) is a way to model many real-world systems ranging from network (electricity or water distribution, telecommunication), to satellites, cars, robots, etc. Because systems have systems with size exponential in the number of components, decentralised models are required.

To make any reasoning on the model practical, probabilistic information is often required. This project aims at studying how to model probabilistic DES and how to perform diagnosis reasoning on it (ie. determining what happened when incomplete observations are given from the model). The project will suit a student with a strong mathematical background.

Symbolic approach of diagnosis

Diagnosis is the problem of understanding what happens in a system given observations of its behaviour. It is a prerequisite to find failures and perform repairs.

Symbolic tools have proven very useful for reasoning about systems. Rather than enumerating possibilities, the symbolic approach describes them in a synthetic form such as: (the door is opened and the light is on) or (the radio is broken). The aim of this project is to explore the use of symbolic tools to solve diagnosis-related problems. These problems include (but are not limited to):

Useful Games

People tend to spend more and more time on games. When they do so, they often have to solve problems, and they get rewards when these problems are solved. Now, there exist very difficult problems that cannot be solved by computers because they require tastes or general knowledge. Rather than asking the computer to solve it, it is possible to ask a human to do it, as long as it is transformed into a game.

The purpose of this project is to identify a problem that is hard for a computer to solve, and to find a way to encode it into a game.

Back to index
Alban Grastien
Last modified: Mon Sep 28 16:58:44 EST 2009