Diagnosis

Diagnosis of dynamic systems: symbolic reasoning

We investigate the different approaches to solve the problem of diagnosis and monitoring of dynamic systems. Our research is mainly focused on the diagnosis of systems that are event-driven (discrete-event systems such as networks, immobots, web services...). Due to the complexity of the supervised systems, diagnosis algorithms have to search solutions (belief states) in a huge state-space. Currently, our challenge is to define a diagnosis framework using symbolic reasoning approaches and to investigate which classes of diagnosis problems can be defined symbolically and solved efficiently.

Diagnosability analysis of dynamic systems

Diagnosability is a concept which represents a set of properties that help to solve a diagnosis problem. Given a model of the system, the diagnosability problem consists in finding what are the caracteristics of the system that make the diagnosis problem easy, complex or not solvable. Thanks to this analysis, we are able to define what are the best diagnosis algorithms to solve the problem for a particular system if such algorithm exists. Another advantage is to provide an automatic and interactive feedback to help in the design and the specification of a system that has to be easily diagnosable.

Planning

Planning under uncertainty in complex environments

In the framework of the Dynamic Planning, Optimization and Learning Project (DPOLP) conducted in collaboration with the Defence Science and Technology Organisation (DSTO), we work on large planning domains involving time, resources and uncertainty. This research links approaches from planning, Markov Decision Problems as well as Petri Nets. The aim is not only to efficiently cope with all of the complexity of such real world planning problems, but also to enable fruitful interaction with the user: the automated process should provide an understandable plan with feedback about its quality, and allow rapidly re-planning when new information comes to light.

Policies for Markov decision processes

This research is focused on algorithms for computing generalised-policies for relational Markov decision processes (RMDP). An RMDP is a collection of MDP. From a learning perspective, we work in the field of relational reinforcement learning (RRL). We examine how we can exploit relational specifications of RMDP in order to create a policy language bias for use by a learner. Currently we are particularly interested in the case where a planner learns a "good" policy from experience (online) where, a priori, it is unlikely that policies in the space under consideration are optimal (or for that matter, explain some given collection of training data).

Optimisation

Backdoors, Backbones and their applications to optimisation problems

Some interesting concepts have been developed in the Artificial Intelligence community such as backbones and back-doors (see box). These have proved useful in solving many decision problems (decision problems are those where the question is 'does my problem even have a valid solution?')

This project looks at whether these sorts of concepts can be fruitfully applied to optimisation problems. Optimisation problems try to answer the question 'What is the best solution to my problem?.

Although very closely related (most optimisation problems can be stated as a decision problem, and vice-versa) the applicability of these concepts is not immeditely clear. This project will look at ways backdoors, backbones and similar concepts can be applied to optimisation problems. The goal is to produce ideas that can be incorporated into practical optimisation software.

Box: Backbones

Backbones are those parts of a solution that appear in ALL "best" solutions to a problem. If I am looking for the shortest path to my mother's house, then there may be several different paths of the same length. But if they all start with 'turn left onto Alpha St, then right onto Beta Cr', then Alpha St and Beta Cr are in the backbone of that problem.