Research
Many complex systems consist of simple components organised to achieve an end goal such as electricity supply or the creation of a product on a factory line. Achieving optimal performance requires adequate supervision software to accurately diagnose problems and temporarily reconfigure the system. The goal of this project is to develop efficient algorithms and tools to do this and thus improve the quality of service in the targeted application areas. The main focus of the project is in model-based supervision, meaning that the supervision is based on a model of the system. The benefit of this is that the supervision task can be fully automated and it can be rigorously shown to be correct. Our approach is in strong contrast with the current practise in many industries in which supervision, including monitoring and diagnosis, is based on ad hoc rules a system expert has derived from his understanding of the working of the system. Ad hoc supervision methods are difficult to be shown to be correct and optimal. For example, it is often very difficult to derive ad hoc diagnosis rules that cover all possible faults and fault combinations. Model-based methods can avoid many of the pitfalls of ad hoc supervision methods.
Our research provides assistance with the resolution of three main problems by system designers and operators:
- establishing which aspects of the system are critical and need to be monitored
- finding out which faults are causing the system to behave abnormally
- deciding which actions to undertake to restore the service
We are developing a unique approach is based on recent advances in the fields of artificial intelligence, automated verification, and discrete-event systems, most notably model-based diagnosis, planning, and model-checking. The approach heavily relies on decentralised and symbolic algorithms.
What will this research achieve?
An improvement in the quality of service from complex dynamic systems in telecommunications, power, computer, transport, and manufacturing industries.
Who will benefit?
Both industry and the consumers of their services and products, from electricity to manufactured goods.
What are the key features?
Our technology is targeted at complex systems in which faults cannot be identified via a small number of obvious indicators. Instead, a complex combination of indicators, possibly over a long time span, has to be observed and analysed in order to infer a faulty behaviour. Our approach is model-based, which means that correct, accurate and efficient supervision methods can be obtained.
The inputs to the software are:
- a sequence of observations (an event log) derived from sensors
- a discrete-event model of the system. A more detailed system model enables more complex interactions of observations to be accounted for and yields more accurate knowledge of the system state.
Our technology is generic but can be tailored to different applications, including manufacturing, power distribution, computer networks, transportation, smart houses. It addresses 3 critical technical issues:
A. Modularity
Diagnosis systems in use in industry typically rely on alarm correlation and expert reasoning. They are difficult to maintain as any change in a component or the system's organisation may invalidate the expertise. This can lead to prohibitive re-development costs.
In contrast, we use model-based reasoning from a library of component models. When a component is upgraded or added to the system, only its model changes or gets added to the component library. The monitoring software does not change. Our technology is applicable to reconfigurable systems.
B. Flexibility
The technology can be tailored to applications with different real-time and space requirements. This is achieved by considering a spectrum of methods. These range from slower but space-efficient cooperative methods based on the component models, to the automatic off-line compilation of the component models to diagnosers and controllers that provide efficient on-line supervision.
C. Scalability.
State of the art model-based diagnosis techniques typically handle discrete-event systems of the order of 10^6 states. Our approach scales up to 10^100 states. This is achieved via:
- The application of powerful data structures and algorithms originally developed for artificial intelligence and computer aided validation and verification. These include binary decision diagrams (BDDs), satisfiability (SAT) and knowledge compilation algorithms.
- New problem partitioning techniques; these automatically decompose the problem into smaller, loosely coupled subproblems that are solved in a co-operative fashion. The partitioning makes use of join trees, decomposition trees, and time-slicing.
Progress update
- A range of efficient model-based methods have been designed
- A software platform and a number of demonstrators have been implemented
- 7 SuperCom publications accepted at the IJCAI and AAAI conferences in 2007
- 5 more at the ECAI and AAAI conferences in 2008
