The project "Model-based Supervision of Composite Systems" (SuperCom) looks at complex component-based systems ranging from power distribution networks to web services and assembly lines. It aims at building tools that confer those systems the ability to self-diagnose problems and keep operating as efficiently as possible until faults are repaired.
Overview | Demonstrators | Research Team | Publications
Overview
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 precise 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 show 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 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
Demonstrators
 |
Power Supply Restoration The problem is to diagnose and reconfigure a power distribution system in such a way as to minimise breakdown costs. Due to sensor uncertainty, the location of the faults and the current network configuration cannot always be known with certainty. This leads to a tradeoff between acting to resupply customers and acting to gain additional information. The reconfiguration is constrained by the capacity of the lines and power sources, and attempts to optimise the power margins and the distance to the nominal configuration. |
|
Monitoring the Manufacture of Plastic Bags
Monitoring the production of a factory is critical both to ensure the quality of the production and to detect mistakes that can be costly and require stopping the production. Requiring operators to monitor every step of the production would be too tedious and would create a risk of introducing more mistakes. Our algorithms use the natural decentralised architecture of the factory and divide the diagnosis problem into smaller problems to monitor the system.
|
 |
 |
Monitoring Mail servers A user has sent a mail which has not been received: what happened?
The aim of our work is to automatically answer diagnosis questions on the behaviour of a mail server. It includes a study of the verbosity level required to monitor a mail server, and recommending actions to ensure the minimum amount of information required is logged.
|
Research Team
Staff |
||||
 |
 |
 |
 |
 |
| Anbulagan | Adi Botea | Alban Grastien |
Jussi Rintanen | Sylvie Thiébaux |
|
Students
|
||||
 |
 |
 |
 |
 |
| Andre Cire | Priscilla Kan John | Elena Kelareva |
Anika Schumann |
Sajjad Siddiqi |
|
Collaborators
|
||||
 |
 |
 |
||
| Olivier Buffet (CNRS) | Jinbo Huang | Yannick Pencolé (CNRS) |
Publications
- L. Blackhall and P. Kan-John. Model-Based Diagnosis of Hybrid Dynamical Networks for Fault Tolerant Control. 19th International Workshop on Principles of Diagnosis (DX-08), Blue Mountains (Australia), September 2008.
- P. Kan-John and A. Grastien. Local Consistency and Junction Tree for Diagnosis of Discrete-Event Systems. 18th European Conference on Artificial Intelligence (ECAI-08), IOS Press, Patras (Greece), July 2008. [pdf] © IOS Press
- A. Grastien and Anbulagan. Incremental Diagnosis of DES by Satisfiability. 18th European Conference on Artificial Intelligence (ECAI-08), IOS Press, Patras (Greece), July 2008. [pdf] © IOS Press
- J. Rintanen. A New Approach to Planning in Networks. 18th European Conference on Artificial Intelligence (ECAI-08), IOS Press, Patras (Greece), July 2008. [pdf] © IOS Press
- A. Ciré and A. Botea. Learning in Planning with Temporally Extended Goals and Uncontrollable Events. 18th European Conference on Artificial Intelligence (ECAI-08), IOS Press, Patras (Greece), July 2008. [pdf] © IOS Press
- A. Schumann and J. Huang. A Scalable Jointree Algorithm for Diagnosability. 23rd American National Conference on Artificial Intelligence (AAAI-08), AAAI Press, Chicago (USA), July 2008. [pdf]© AAAI Press
- A. Schumann, Y. Pencolé, and S. Thiébaux. A Spectrum of On-line Symbolic Diagnosis Approaches. 22nd American National Conference on Artificial Intelligence (AAAI-07), AAAI Press, Vancouver (Canada), July 2007. [pdf] © AAAI Press
- A. Grastien, Anbulagan, J. Rintanen, and E. Kelareva. Diagnosis of Discrete-Event Systems Using Satisfiability Algorithms. 22nd American National Conference on Artificial Intelligence (AAAI-07), AAAI Press, Vancouver (Canada), July 2007. [pdf] ©AAAI Press
- E. Kelareva, O. Buffet, J. Huang, and S. Thiébaux. Factored Planning Using Decomposition Trees. 20th International Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad (India), January 2007. [pdf] © IJCAI
- J. Rintanen. Complexity of Diagnosability for Succinct Transition Systems. 20th International Joint Conference on Artificial Intelligence (IJCAI-07), pages 538-544, Hyderabad (India), January 2007. [pdf] © IJCAI
- J. Rintanen and A. Grastien. Diagnosability Testing with Satisfiability Algorithms. 20th International Joint Conference on Artificial Intelligence (IJCAI-07), pages 532-537, Hyderabad (India), January 2007. [pdf] © IJCAI
- M.-O. Cordier and A. Grastien. Exploiting independence in a decentralised and incremental approach of diagnosis. 20th International Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad (India), January 2007. [pdf] © IJCAI
- A. Schumann and Y. Pencolé. Scalable Diagnosability Checking of Event-driven Systems, 20th International Joint Conference on Artificial Intelligence (IJCAI-07), 575-580, Hyderabad (India), January 2007. [pdf] © IJCAI
- Anika Schumann and Y. Pencolé. Efficient On-line Failure Identification for Discrete-event Systems, 6th IFAC Symposium on Fault Detection, Supervision and Safety of Technical Process (SAFEPROCESS-06), Beijing (P.R. China) August 2006. [pdf] © Elsevier
- Y. Pencolé, D. Kamenetsky, and A. Schumann. Towards Low-cost Diagnosis of Component-based Systems, 6th IFAC Symposium on Fault Detection, Supervision and Safety of Technical Process (SAFEPROCESS-06), Beijing (P.R. China) August 2006. [pdf] © Elsevier
- Y. Yan, Y. Pencolé, M.-O. Cordier, and A. Grastien. Monitoring Web Service Networks in a Model-based Approach. 3rd European Conference on Web Services (ECOWS-05), Växjö, Sweden, November 2005. [pdf]