A new efficient and flexible algorithm for the design of testable subsystems

Ploix, S. ; Yassine, A. A. ; Flaus, J.-M.

International Journal of Applied Mathematics and Computer Science, Tome 20 (2010) no. 1, pp. 175-190.

Résumé

In complex industrial plants, there are usually many sensors and the modeling of plants leads to lots of mathematical relations. This paper presents a general method for finding all the possible testable subsystems, i.e., sets of relations that can lead to various types of detection tests. This method, which is based on structural analysis, provides the constraints that have to be used for the design of each detection test and manages situations where constraints contain non-deductible variables and where some constraints cannot be gathered in the same test. Thanks to these results, it becomes possible to select the most interesting testable subsystems regarding detectability and diagnosability criteria. Application examples dealing with a road network, a digital counter and an electronic circuit are presented.

Détail

Keywords: automatic test design, structural approach, fault diagnosis, analytical redundancy relations, relational algebra
Mots-clés : podejście strukturalne, diagnostyka uszkodzeń, algebra relacyjna

Bibliographie

[1] Blanke, M., Kinnaert, M. and Staroswiecki, M. (2003). Diagnosis and Fault Tolerant Control, Springer, Berlin.

[2] Cassar, J. and Staroswiecki, M. (1997). A structural approach for the design of failure detection and identification systems, IFAC, IFIP, IMACS Conference on Control of Industrial Systems, Belfort, France, pp. 329-334.

[3] Chittaro, L. and Ranon, R. (2004). Hierarchical model-based diagnosis based on structural abstraction, Artificial Intelligence 155(1-2): 147-182.

[4] Codd, E. (1970). A relational model of data for large shared data banks, Communications of the ACM 13(6): 377-387.

[5] Console, L., Picardi, C. and Ribando, M. (2000). Diagnosis and diagnosability analysis using process algebra, Proceedings of the Eleventh International Workshop on Principles of Diagnosis (DX-00), MX, Morelia, Mexico, pp. 25-32.

[6] Dague, P. (2001). Théorie logique du diagnostic à base de modèles, in B. Dubuisson (Ed.), Diagnostic, Intelligence artificielle et reconnaissance de formes, Hermès Science, Paris, pp. 17-104.

[7] Davis, R. (1984). Diagnostic reasoning based on structure and behavior, Artificial Intelligence 24(1-3): 347-410.

[8] De Kleer, J. and Williams, B. C. (1987). Diagnosing multiple faults, Artificial Intelligence 32(1): 97-130.

[9] De Kleer, J. and Williams, B. C. (1992). Diagnosis with behavioral modes, in W.C. Hamscher, I.de Kleer and L. Console (Eds), Readings in Model-Based Diagnosis, Morgan Kaufmann Publishers Inc., San Francisco, CA, pp. 124-130.

[10] Dechetr, R. (2003). Constraint Processing, Morgan Kaufmann Publishers, San Francisco, CA.

[11] Declerck, P. and Staroswiecki, M. (1991). Characterization of the canonical components of a structural graph for fault detection in large scale industrial plants, European Control Conference, Grenoble, France, pp. 298-303.

[12] Dulmage, A. L. and Mendelsohn, N. S. (1959). A structure theory of bi-partite graphs of finite exterior extension, Transactions of the Royal Society of Canada 53(III): 1-13.

[13] Frank, P. M. (1990). Fault diagnosis in dynamic systems using analytical and knowledge-based redundancy-A survey and some new results, Automatica 26(3): 459-471.

[14] Frisk, E. (2000). Residual generator for non-linear polynomial systems-A Grobner basis approach, IFAC Fault Detection, Supervision and Safety for Technical Processes, Budapest, Hungary, pp. 979-984.

[15] Fron, A. (1994). Programmation par contraintes, Addison-Wesley, Paris.

[16] Górny, B. and Ligęza, A. (2001). Review of systematic conflict generation in model-based diagnosis of dynamic systems, IFAC Workshop on Manufacturing, Modelling Manageent and Control, Prague, Czech Republic, pp. 86-91.

[17] Iwasaki, Y. and Simo, H. A. (1994). Causality and model abstraction, Artificial Intelligence 67(1): 143-194.

[18] Krysander, M., Åslund, J. and Nyberg, M. . (2008). An efficient algorithm for finding minimal overconstrained subsystems for model-based-diagnosis, IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans 38(1): 197-206.

[19] Krysander, M., Åslund, J. and Nyberg, M. (2005). An efficient algorithm for finding over-constrained sub-systems for construction of diagnostic tests, 16th International Workshop on Principles of Diagnosis (DX-05), Pacific Grove, CA, USA.

[20] Ligęza, A. and Górny, B. (2000). Systematic conflict generation in model-based diagnosis, SAFEPROCESS'2000: 4th IFAC Symposium on Fault Detection and Supervision and Safety for Technological Processes, Budapest, Hungary, Vol. II, pp. 1103-1108.

[21] Mishra, P. and Eich, M. (1992). Join processing in relational databases, ACM Computing Surveys 24(1): 63-113.

[22] Nayak, P. P. and Levy, A. Y. (1995). A semantic theory of abstractions, 14th International Joint Conference on Artificial Intelligence IJCAI-95, Montreal, Canada, pp. 196-203.

[23] Nyberg, M. and Krysander, M. (2003). Combining AI, FDI, and statistical hypothesis-testing in a framework for diagnosis, IFAC SAFEPROCESS'03, Washington, DC, USA, pp. 813-818.

[24] Patton, R., Frank, P. and Clark (Eds), R. (1989). Fault Diagnosis in Dynamic Systems, International Series in Systems and Control Engineering, Prentice Hall, London.

[25] Ploix, S., Désinde, M. and Michau, F. (2004). Assessment and diagnosis for virtual reality training, International Symposium on Advanced Robot Systems and Virtual Reality, Grenoble, France.

[26] Ploix, S., Désinde, M. and Touaf, S. (2005). Automatic design of detection tests in complex dynamic systems, 16th IFAC World Congress, Prague, Czech Republic.

[27] Ploix, S., Touaf, S. and Flaus, J. M. (2003). A logical framework for isolation in fault diagnosis, SAFEPROCESS' 2003, Washington, DC, USA.

[28] Pulido, B. and Alonso, C. (2002). Possible conflicts, arrs, and conflicts, 13th International Workshop on Principles of Diagnosis (DX02), Semmering, Austria, pp. 122-128.

[29] Reiter, R. (1987). A theory of diagnosis from first principles, Artificial Intelligence 32(1): 57-95.

[30] Russell, S. and Norvig, P. (2003). Artificial Intelligence, A Modern Approach, 2nd Ed., Prentice Hall, Upper Saddle River, NJ.

[31] Staroswiecki, M., Cocquempot, V. and Cassar, J. P. (1991). Observer based and parity space approaches for failure detection and identification, IMACS-IFAC International Symposium, Lille, France, Vol. 25, pp. 536-541.

[32] Staroswiecki, M. and Declerck, P. (1989). Analytical redundancy in nonlinear interconnected systems by means of structural analysis, IFAC AIPAC'89 Symposium, Nantes, France, Vol. 2, pp. 23-27.

[33] Struss, P. (1992). What's in SD? Towards a theory of modeling for diagnosis, in W. Hamscher, L. Console and J. De Kleer (Eds), Readings in Model-Based Diagnosis, Morgan Kaufman, San Francisco, CA, pp. 419-448.

[34] Travé-Massuyès, L., Escobet, T. and Olive, X. (2006). Diagnosability analysis based on component supported analytical redundancy relations, IEEE Transactions on Systems, Man, And Cybernetics-Part A: Systems and Humans 36(6): 1146-1160.

[35] Travé-Massuyès, L., Escobet, T. and Spanache, S. (2003). Diagnosability analysis based on component supported analytical redundancy relations, IFAC Workshop SAFEPROCESS' 2003, Washington, DC, USA, pp.897-902.

[36] Willsky, A. (1976). A survey of design methods for failure detection in dynamic systems, Automatica 21(4): 601-611.