ESA_PetriNet: a Tool for Extracting Scenarios in Computer Controlled Systems
LAGIS, Ecole Centrale de Lille
Cité Scientifique, BP 48, Villeneuve d’Ascq, 59651, France
This paper deals with the dynamic reliability of a computer-controlled system by means of deriving critical scenarios from its Petri net model. These scenarios characterize how the system leaves the normal operating to go to the feared state by determining the sequences of actions (events) and state changes leading to dangerous situation. We present a method (algorithm) that takes into account the continuous dynamic of the system by a temporal abstraction, which makes it possible to determine more precisely the exact conditions of the occurrence of the feared event. The originality is that the order of occurrence of the events is taken into account, and impossible scenarios with respect to the continuous dynamic of the system are eliminated. The automation of all the steps of this method has led to the development of ESA_PetriNet tool (Extraction Scenarios & Analyzer by Petri Net model) and was applied on real industrial systems.
Dynamic reliability, critical scenarios, computer-controlled systems, hybrid aspect, Petri nets, temporal abstraction.
Malika Medjoudj was born in Tizi-ouzou (Algeria) on February 21, 1977. She received the Engineer Diploma degree in Electronics (Control) and the Diploma of Higher Education Applied in Technical English from Mouloud Mammeri University of Tizi-ouzou (Algeria) in 2001. She obtained the Master in Industrial Systems from UPS-LAAS-CNRS of Toulouse (France) in 2002 and the PhD in Industrial Systems from the same university and laboratory in March 2006. She is actually a Post Doctorate at the Ecole Centrale de Lille after a scientific stay of six months in the nuclear metrology service of the Université Libre de Bruxelles (FNRS-Belgium). Her research is related to the reliability of hybrid and dynamic systems (computer-controlled systems, embedded systems), checking of temporal constraints, extended Petri Nets for safety (transportation systems), feared scenarios and simulation.
CITE THIS PAPER AS:
Malika MEDJOUDJ, ESA_PetriNet: a Tool for Extracting Scenarios in Computer Controlled Systems, Studies in Informatics and Control, ISSN 1220-1766, vol. 17 (3), pp. 71-84, 2008.
Computer-controlled systems are energy systems (mechanical, hydraulic, electrical) ordered and controlled by one or several computers (computer science and electronics). These systems are used in the field of defense, space, nuclear (control of the nuclear power stations); car and avionic (embedded systems as mechatronic systems and computers flight, landing gear systems, ect). The software and material suppleness of these systems allowed a progressive integration of electronics in these named fields to improve both functions and services. However, this has caused an increased complexity in the design of these systems typically involving computers, which makes the control of their reliability difficult. In addition, the phase of design must be fast and inexpensive (i.e. less prototypes and at the later stages) with a level of guaranteed safety. In more cases for reasons of cost and implementation, material resources are limited and the system designers must avoid component redundancies within the system as much as possible. Reliability studies performed at the design phase have allowed a better control of the risks and reliability of the conceived systems. Indeed, the evaluation of the safety level during the systems conception allows the specification of piloting strategies and reconfiguration modes before the first tests on a real prototype. Computer-controlled systems are hybrid: continuous dynamics is applied to the power characteristics, and discrete dynamics is related to the numerical control and the existence of discrete events (failures and thresholds). The study of reliability of these hybrid and dynamic systems named dynamic reliability    or probabilistic dynamics   must necessarily take into account the existing interactions between their physical parameters (temperature, pressure, speed, etc.) and the failure of their components.
One way to evaluate the reliability of such complex systems is the extraction of critical scenarios leading to feared states. From a qualitative point of view, this is a question of characterizing these scenarios as soon as possible in the design phase, which makes it possible to evaluate their probabilities of occurrence in order to validate the architecture of the system or to evaluate the safety level of existent systems.
Traditional methods for reliability are insufficient because they don’t take into account the reconfiguration and the hybrid dynamic of the system. For example classical Failures Trees  are static and don’t take into account the order of appearance of the events. In effect, a sequence of events can lead to a feared event while the same events occurring in a different order or in different dates can avoid it. The time separating two events is not taken into account in the Failures Trees method; therefore, reconfigurations cannot be represented. Temporary failures are not either taken into account. Several extensions of classical methods were proposed to extend their field of application like Failure Trees with gates (A before B). These methods remain combinatory and unable to take into account the states changes and reconfigurations in the feared scenarios. Other methods were introduced as the Events Sequence Diagrams (ESD)  to allow a better visual presentation of the events ordered in time. Although the ESD represents in a clear way the scenarios in competition, they cannot be generated automatically and require a definition of states and transitions. All order and reconfiguration states must therefore be listed by the designer and in the case of the hybrid dynamic systems; the number of states is infinite if the energy party is taken into account. This problem is also encountered in the analytical methods based on Markov graphs. To take into account partially the dynamic of the system, methods of discretization were developed as the Discrete Dynamic Event Trees (DDET). The DDET generates the feared scenarios by failure propagation of the elementary components of the system. The limit of this method is that all the sequences of event constituting possible scenarios are generated. In order to better manage the multiple generated scenarios by the DDET, methods as DYLAM (Dynamic Logical Analytical Methodology) and DETAM (Dynamic Event Tree Analysis Method) were developed. Therefore, the time and order of execution of the events must be taken into account . Limits of quantitative methods based on simulation  are owed to the combinative states explosion. Because of the scarcity of the feared scenarios, these methods simulate in the most part of time the normal operating. It is however necessary to mention the existence of theoretical developments and methods to resolve the problem encountered in the simulation of systems in the presence of rare events . Indeed, techniques of acceleration of the simulation were developed and largely used with success, in particular in nuclear engineering. We can mention Monte Carlo Dynamic Event Tree (MCDET)  which is a coupling of the DDET with Monte Carlo Simulation  to investigate in a more efficient way the whole tree of events.
In the case of Petri nets , the combinative explosion affects the accessibility graph and not the original Petri net. So to avoid this combinative states explosion, a qualitative analysis method of reliability aiming to directly use the Petri net model of the system to extract the feared scenarios without generating the reachability graph was developed by . Unfortunately this method based on Linear Logic  operated only on the discrete aspect of the system and lot of impossible scenarios is generated. To determine more precisely the exact conditions of the occurrence of the feared event, i.e what has led the system to leave its normal operation and to evolve into the feared state, a method taking into account the continuous aspect and the temporal specifications of the system is developed by  . The originality of this approach, automated to result ESA_PetriNet tool , is that the order of occurrence of the events is taken into account, and impossible scenarios with respect to the continuous dynamic and the temporal specifications of the system are eliminated. ESA_PetriNet tool has been interfaced with TINA tool (Time Petri Net Analyzer) .
We will present the method and the basic of the algorithm in section 2, the ESA_PetriNet tool in section 3, the selected case study and the scenarios generation in section 4, and we will end by a conclusion.
We have presented in this paper a method automated to result ESA_PetriNet tool (Extraction & Scenarios Analyzer by Petri Net model) developed for extraction of feared scenarios from the Petri net model of computers-controlled systems. The taking into account of the continuous dynamic of these systems by temporal abstraction allows the elimination of a significant number of incoherence scenarios (relating to the continuous dynamic) and the respect of the order of appearance of the events. The computing time takes only few seconds. This tool has been used to generate feared scenarios from reel industrial systems of significant size: a Rafale landing gears control system of Dassault Aviation  and a decentralized radio-based railway level crossing control system . The aim in the last system, taken from a realistic specification of a new radio-based train control system  developed for the German Railways, was the evaluation of the safety  level to avoid collision. Note that we have improved some functions of ESA_PetriNet in  relating to the exploration way of the Petri net.
As it is mentioned in section 4, ESA_PetriNet was adapted to the checking of some properties (determining if the system satisfies certain properties like the duration of a scenario or accessibility between two states). A simple back exploration is enough to generate all the scenarios leading to the target state. Then a temporal abstraction is used to obtain temporal constraints networks. ESA_PetriNet has been used in the precedent landing gears system to check that the duration of a scenario is lower than certain limit  . It is important to note that we have implemented Monte Carlo simulation  in this tool to quantify the probability of occurrence of these scenarios . To improve this tool, we have to take into account the minimality of the scenarios to eliminate the unnecessary events and redundancy. We have also to improve the mechanism of enrichment of the marking (in some complex systems the invariants of places is not sufficient). The checking part can be supported by algorithms of research longest ways  .
The author would like to thank Hamid Demmou, Assistant Professor at Paul Sabatier University of Toulouse (France), Robert Valette, Directeur de recherche 2ème classe at LAAS-CNRS of Toulouse (France) for supervising this work during my PhD thesis at LAAS-CNRS. To access this tool, contact the author (firstname.lastname@example.org, actually a post doctorate under the support of the pole ST2 and the region Nord-Pas de Calais at LAGIS- Ecole Centrale de Lille) or Hamid Demmou (email@example.com).
- DUFOUR, F. and DUTUIT Y., Dynamic Reliability: A New Model, 13-ESREL2002 European Conference, Lyon-France, 18 au 21 Mars 2002.
- DEVOOGHT, J., Dynamic reliability, Advances in Nuclear Science and Technology 25, pp. 215-278, 1997.
- LABEAU, P.E., SMIDTS C., SWAMINATHAN S., Dynamic Reliability: Towards an Integrated Platform for Probabilistic Risk Assessment. Reliability Engineering and System Safety 68, pp. 219-254, 2000.
- DEVOOGHT, J., SMIDTS C., Probabilistic Reactor Dynamics – I: The Theory of Continuous Event Trees, Nuclear Science and Engineering, Vol. 111, pp. 229-240, 1992.
- DEVOOGHT, J., SMIDTS C., Probabilistic Reactor Dynamics – II: A Monte-Carlo Study of a Fast Reactor Transcient , Nuclear Science and Engineering, Vol. 111, pp. 241-256, 1992.
- LEE, W.S., GROSH, D.L., TILLMAN, F.A., LIE, C.H., Fault Tree Analysis, Methods, and Applications – A Review, IEEE Transactions on Reliability, ISSN 0018-9529; r-34, pp. 194-203, August 1st 1985.
- SWAMINATHAN, S., SMIDTS C., The Event Sequence Diagram Framework for Dynamic PRA, Reliability Engineering and System Safety 63, 1999, pp. 73-90.
- GARRET, C.J., GUARRO S.B., The Dynamic Flow graph Methodology for Assessing the Dependability of Embedded Software Systems, IEEE Transactions On Systems, Man, and Cybernetics, Vol. 25, No. 5, May 1995.
- MONCELET, G., CHRISTENSEN S., DEMMOU H., PALUDETTO M., PORRAS J., Qualitative an Quantitative Dependability Evaluation of a Simple Mechatronic System Using Colored Petri Nets, Workshop on practical use of colored Petri nets and DesignCPN, Aarhus, Denmark, June 98.
- VILLÉN-ALTAMIRANO, M., VILLÉN-ALTAMIRANO J., RESTART: A Straightforward Method for Fast Simulation of Rare Events, Proceedings of the 1994 Winter Simulation Conference, 1994, pp. 282-294.
- HOFER, E., KLOOS M., KRZYKACZ-HAUSMANN B., PESCHKE J., SONNENKALB M., Method enentwicklung zur simulativen Behandlung der Stochastik in probabilistischen, Sicherheitsanalysen der Stufe 2, Abschlußbericht, GRS-A-2997, Gesellschaft für Anlagen- und Reaktorsicherheit, Germany (2001).
- KALOS, M.H. and WHITLOCK P.A., Mont Carlo Methods, Vol. 1: Basics, John Wiley and Sons, New York, 1986.
- MURATA, T., Petri Nets: Properties, Analysis and Applications, IEEE Proc, Vol. 77, pp. 541-580, April 1989.
- DEMMOU, H., KHALFAOUI S., RIVIERE N., VALETTE R., Extracting Critical Scenarios from a Petri Net Model Using Linear Logic, Journal Européen des Systèmes Automatisés (APII-JESA), Vol. 36, N7, 2002, pp. 987-999.
- GIRARD, J.Y., Linear Logic, Theoretical Computer Science, Vol. 50, 1987, pp. 1-102.
- MEDJOUDJ, M., KHALFAOUI S., DEMMOU H., VALETTE R., A Method for Deriving Feared Scenarios in Hybrid Systems, Probabilistic Safety Assessment and Management (PSAM7-ESREL04), Berlin-Germany, 14-18 June 2004.
- MEDJOUDJ, M., Contribution à l’analyse des systèmes pilotés par calculateurs: Extraction de scénarios redoutés et vérification de contraintes temporelles, Thèse doctorale de l’Université Paul Sabatier, Toulouse-France, Mars 2006.
- MEDJOUDJ, M., DEMMOU H., VALETTE R., ESA_PetriNet tool: Extraction Scenarios & Analyzer by Petri Net Model : Application to the Extraction of Feared Scenarios in a Landing Gear System, European Simulation and Modeling Conference (ESM2006), LAAS-Toulouse-France, 23-25 October 2006, pp. 375-382.
- BERTHOMIEU, B., RIBET P.O., VERNADAT F., The tool TINA – Construction of Abstract State Spaces for Petri Nets and Time Petri Nets, International Journal of Production Research, Vol. 42, No. 14, 15 July 2004, pp. 2741-2756.
- CHAMPAGNAT, R., ESTEBAN P., PINGAUD H., VALETTE R., Modeling and Simulation of a Hybrid System Through Pr/Tr PN DAE Model, ADPM’98 3rd International Conference on Automation of Mixed Processes, Reims-France, 19-20 March 1998, pp. 131-137.
- DEMMOU, H., KHALFAOUI S., GUILHEM E., VALETTE R., Critical Scenarios Derivation Methodology for Mechatronic Systems, Reliability Engineering & System Safety, Vol. 84, No. 1, April 2004, pp.33-44.
- MEDJOUDJ, M. and YIM P., Extraction of Critical Scenarios in a Railway Level Crossing Control System, International Journal of Computers, Communication and Control (IJCCC) Vol. II, No. 3, 2007, pp. 252-268.
- JANSEN, L. and SCHNIEDER E., Traffic Control Systems Case Study: Problem Description and a Note on Domain-based Software Specification, Technical rapport, Technical University of Braunschweig, 2000.
- LAPRIE, J.C., Dependability: Basic Concepts and Terminology, Vol. 5, Springer, 1992.
- RIVIERE, N., DEMMOU H., VALETTE R., MEDJOUDJ M., Symbolic Temporal Constraint Analysis, an Approach for Verifying Hybrid Systems, 16th IFAC World Congress, Prague-République Tchèque, 3-8 July 2005.
- MEDJOUDJ, M. and LABEAU P.E., Estimation Monte Carlo de la probabilité d’atteindre des états redoutés basée sur la prédétermination de ces scénarios, 12P, PENTOM, Mons-Belgique. 9-10 juillet 2007.
- FLOYD, R.W., Algorithm 97: Shortest Path, Communications of the ACM Vol.5 Issue 6, page 345, June 1962.
- WARSHALL, S., A Theorem on Boolean Matrices, Journal of the ACM Vol. 9 Issue .1, pp. 11-12, January 1962.