Authors: Bourdeaud'huy, Thomas; Yim, Pascal

Abstract: In this paper, we propose to synthesize timed Petri nets from structural and behavioural constraints. The identification problem is expressed as an integer linear programming problem, where unknows correspond to the structure of the Petri net. Using such a model, one can identify the components of the Petri Net incidence matrices as well as the durations associated to timed transitions. An objective function can be used to optimize these durations in order to obtain a model minimizing the duration of a particular firing sequence.

Keywords: identification,timed Petri nets,integer linear programming

Identifier: 10.3182/20070613-3-FR-4909.00044

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Monnin, Maxime; Iung, Benoit; Sénéchal, Olivier

Abstract: Availability is a determining factor in systems characterization. Because military systems must act in a hostile environment, they are particularly vulnerable in situations of unavailability. Military weapon systems can become unavailable due to system failures or damage to the system; in both cases, system regeneration is needed to restore availability. However, very few of the general dependability studies, or even the more specific availability studies take battlefield damage into account. This paper aims to define principles for weapon systems modeling that integrate both system failure and system damage, as well as the possibility of regeneration, into operational availability assessment. This modeling method uses a unified failure/damage approach based on state-space modeling.

Keywords: damage,failure,regeneration,availability assessment,stochastic activity networks,Monte Carlo simulation

Identifier: 10.3182/20070613-3-FR-4909.00029

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Qiu, Wenbin; Kumar, Ratnesh

Abstract: We propose a protocol for distributed state estimation, where distributed observers share their state estimation information through bounded-delay channels. A synchronized truncation strategy is proposed to further reduce the space and time complexity. An example is provided to illustrate the proposed distributed state-estimation protocol.

Keywords: discrete-event systems,state estimation,distributed systems

Identifier: 10.3182/20070613-3-FR-4909.00039

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Thorsley, David; Teneketzis, Demosthenis

Abstract: We consider the problem of actuator failure in supervisory control of decentralized discrete event systems. A subset of events that are disabled by the decentralized supervisor may, in actuality, be enabled as a result of interference in the signal from the supervisor to the actuator. Extending the method of Thorsley and Teneketzis (2006) to decentralized supervisors, we determine conditions that ensure that a given set of actuator failures can never allow the system to complete an undesirable sequence of events. We use the technique of fictitious play to find a member-by-member optimal control specification.

Keywords: discrete-event systems,supervisory control,game theory,optimization

Identifier: 10.3182/20070613-3-FR-4909.00030

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Merle, Guillaume; Roussel, Jean-Marc

Abstract: This paper presents a formal framework allowing to extend the simplification of static fault trees to fault trees built with gates PRIORITY AND. The laws which make these simplifications possible have been demonstrated thanks to a homogeneous algebraic definition of each gate studied. These definitions use a mathematical model of events able to take into account their order of appearance. The processing of an example points out the possibilities offered by this algebraic framework dedicated to non-repairable faults.

Keywords: fault trees,minimal cut sets,temporal gates,algebraic approach

Identifier: 10.3182/20070613-3-FR-4909.00008

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Zhao, Peng; Lu, Yan; Jafari, Mohsen A.; Amini, Ardavan

Abstract: In this article we propose an online fault detection and avoidance framework for distributed multi-agent systems. The main premise of our work follows the recent notions in autonomic and recovery oriented computing - not all faults can be determined and removed at the time of system design and testing. Thus some level of intelligence must be embedded into each agent's controller to ensure higher degree of system dependability. We assume that faults will eventually translate into a time-out condition in one or more agents. The proposed paradigm is illustrated for the case of unknown deadlock conditions in manufacturing applications.

Keywords: dependable Systems,distributed fault detection and avoidance,control law reconfiguration,online analysis,state/transition models

Identifier: 10.3182/20070613-3-FR-4909.00020

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Lukowicz, Miroslaw; Magott, Jan; Skrobanek, Pawel

Abstract: In electrical power systems, the coordination of protections in time domain is important and difficult problem. The time settings of protection relays have to be adapted to the time characteristics of electrical power system plants and the delay times of the other protections. In the paper, Fault Trees with Time Dependencies (FTTDs) are used in selection of values of the delay times of primary (local) and remote backup protections. In the FTTD, events and gates are characterized by time parameters. These time parameters are derived from the time characteristics of protection devices and the inherent delay times of protection equipment.

Keywords: power system protection,distance protection,remote backup protection,fault detection and isolation,fault tree with time dependencies

Identifier: 10.3182/20070613-3-FR-4909.00009

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Ferrari, Davide; Matta, Andrea

Abstract: The paper presents an approximate analytical method, based on decomposition techniques, that assesses the physical performance of small flow lines with both dedicated and shared buffer. The aim of the analytical method is to capture the interdependent behaviour of the machines in the line due to the shared buffers. The method deals with discrete and deterministic processing time, limited buffer capacity, and both time to repair (TTR) and time between failure (TBF) follow a geometric distribution. The accuracy of the analytical solutions is assessed with respect to results provided by simulation.

Keywords: performance evaluation,decomposition,flow line,analytic approximations,systems design,buffer,Markov models

Identifier: 10.3182/20070613-3-FR-4909.00004

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Bobbio, Andrea; Terruggia, Roberta

Abstract: Many social, economical and technological structures can be abstracted in the form of networks where the vertices are the entities of the system and the edges the physical or relational links among them. One relevant property of networks that make them a preferential structure both in natural and technological systems is that the connection between any two nodes of the networks can be achieved through many redundant paths, thus making the connection intrinsically reliable. Network reliability is studied in this paper by resorting to different approaches making use of the BDD representation of Boolean functions. The related algorithms are presented and their merits and limits are briefly discussed.

Keywords:

Identifier: 10.3182/20070613-3-FR-4909.00036

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Malik, Robi; Flordal, Hugo; Pena, Patrícia N.

Abstract: This paper studies abstraction methods suitable to verify very large models of discrete-event systems to be nonconflicting. It compares the observer property to methods known from process algebra, namely to conflict equivalence and observation equivalence. The observer property is shown to be the property that corresponds to conflict equivalence in the case where natural projection is used for abstraction. In this case, the observer property turns out to be the least restrictive condition that can be imposed on natural projection to enable compositional reasoning about conflicts. The observer property is also shown to be closely related to observation equivalence. Several examples and propositions are presented to relate different aspects of these methods of abstraction.

Keywords: discrete-event systems,large-scale systems,formal verification

Identifier: 10.3182/20070613-3-FR-4909.00037

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Yang, Hao; Cocquempot, Vincent; Jiang, Bin

Abstract: State estimation and fault diagnosis problems are discussed for a class of hybrid nonlinear systems modelled by hybrid automata, which have uncontrollable discrete mode transitions and parametric uncertainties. Two kinds of faults are considered: Continuous faults that affect each mode; Discrete faults that affect the mode transition. To estimate both the continuous and discrete states, a novel observer is designed for each mode whose estimation error is not affected by continuous faults and sensitive to discrete mode transitions. Sufficient conditions are given to achieve the state estimation goal for the overall hybrid system.

Keywords: hybrid system,observers,state estimation,fault diagnosis

Identifier: 10.3182/20070613-3-FR-4909.00047

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Declerck, Philippe

Abstract: A state-based approach for detection of changes in systems modelled as Timed Event Graph and Time Stream Event Graph is presented. We assume that the net in its nominal behavior is known and transitions are partitioned as observable and unobservable transitions. Considered faults are (possibly small) variations of dynamical models by respect to this nominal behavior. Using the algebra of dioids, the approach follows the same principle as the observers used in continuous systems.

Keywords: time stream event graphs,observer,estimation,detection,isolation, diagnostic, (min, max, +) functions

Identifier: 10.3182/20070613-3-FR-4909.00011

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Wagner, Florian; Münch, Philipp; Liu, Steven; Frey, Georg

Abstract: A formal development process for logic controllers using Signal Interpreted Petri Nets and FPGA technology is presented. The development process covers all steps from design to implementation and is supported by the SIPN-Editor toolbox, a graphical editor that allows design, analysis and implementation of SIPN algorithms. As a new feature to increase dependability of logic controllers the SIPN-Editor toolbox supports export to VHDL language which allows implementation of SIPN algorithms on FPGA hardware. The implementation on FPGA is not only much faster than on an ordinary PLC hardware but also more dependable in several aspects. An algorithm to calculate a guaranteed response time is also given.

Keywords: Petri nets,dependability,FPGA,development process

Identifier: 10.3182/20070613-3-FR-4909.00026

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Wang, Xi; Johnson, Timothy L.

Abstract: This paper considers the discovery and detection of repeating patterns in event sequence data, where the event patterns may be of variable duration, may be intermingled, and may be of variable length. These properties are characteristic of many types of monitoring and diagnostic alarm sequence data, and may be used in detecting both normal and abnormal behaviours of complex dynamic systems.

Keywords: fault detection,identification,monitoring,diagnosis,automata,dependability assessment,discrete event systems

Identifier: 10.3182/20070613-3-FR-4909.00012

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Huang, Tien-Chieh Samuel; Kwong, Raymond H. S.

Abstract: State-based fault diagnosis of discrete event systems is considered. The concept of resonating state cycles is introduced, which is used to develop a necessary and sufficient condition for diagnosability. An algorithm to test diagnosability is presented, and is shown to have polynomial complexity. Extensions of the algorithm to include a priori state estimates are discussed.

Keywords: discrete event systems,state-based fault diagnosis,polynomial diagnosability algorithm

Identifier: 10.3182/20070613-3-FR-4909.00017

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Bernard, Romain; Aubert, Jean-Jacques; Bieber, Pierre; Merlini, Christophe; Metge, Sylvain

Abstract: Since the ESACS and ISAAC projects, Airbus and Onera have been investigating failure propagation models and more specifically AltaRica model-based safety analysis. This paper presents results and lessons learnt from an industrial system architecture modeling experiment: rudder control system of the Airbus A340-500/600 aircraft. After introducing failure propagation model construction and analysis, the paper focuses on modeling the reconfigurations, the command/monitoring architecture and finally the latent failures. The main advantage of this approach is the improved readability of safety analysis results that facilitates a quick understanding of the system behaviour. This improves the communication between the safety and design communities.

Keywords: aerospace,fault tolerant system,formal methods,flight control,safety

Identifier: 10.3182/20070613-3-FR-4909.00010

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Wen, Q.; Kumar, R.; Huang, J.; Liu, H.

Abstract: We introduce a framework for fault-tolerant supervisory control of discrete-event systems. Given a plant, possessing both faulty and nonfaulty behavior, and a submodel for just the nonfaulty part, the goal of fault-tolerant supervisory control is to enforce a certain specification for the nonfaulty plant and another (perhaps more liberal) specification for the overall plant, and further to ensure that the plant recovers from any fault within a bounded delay so that following the recovery the system state is equivalent to a nonfaulty state (as if no fault ever happened). We formulate this notion of fault-tolerant supervisory control and provide a necessary and sufficient condition for the existence of such a supervisor, which involves the notion of stability (besides controllability and observability). An example of a power system is provided to illustrate the framework.

Keywords: discrete event systems,fault-tolerance,supervisory control,stability

Identifier: 10.3182/20070613-3-FR-4909.00032

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Ortmeier, Frank; Güdemann, Matthias; Reif, Wolfgang

Abstract: Formal safety analysis methods have gained a lot of importance during the last years. All these methods have in common, that they rely on a formal model of a system which describes desired, functional behavior as well as unwanted erroneous behavior correctly. Most of the time the formal models are created in an ad hoc manner. This is very error prone and therefore compromises the benefit of the following formal analysis. In this paper we present a systematic approach to formally model failure modes. The approach can be combined with most formal safety analysis. We apply the method to a real world case study: a radio-based railroad crossing. We illustrate the results by applying a formal safety analysis method on the model.

Keywords: formal methods,safety critical system,safety analysis,failure modes and effects analysis,fault tree analysis,dependability

Identifier: 10.3182/20070613-3-FR-4909.00027

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: None

Abstract:

Keywords:

Identifier: 10.3182/20070613-3-FR-4909.90001

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Roth, Matthias; Klein, Stéphane; Litz, Lothar

Abstract: In this paper, a method is proposed that generically determines fault models on the basis of the fault free I/O-behavior of sensor-actuator relations. It is shown how the I/O-behavior of standard components can be represented by patterns. These patterns are extended to fault models on the basis of a set of rules. It is possible to detect and locate state faults and time faults with the extended patterns. The patterns are used as observers for the online-diagnosis of a factory automation system.

Keywords: discrete event systems,fault detection,fault isolation

Identifier: 10.3182/20070613-3-FR-4909.00013

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Côme, E.; Bouillaut, L.; Aknin, P.; Oukhellou, L.

Abstract: Hidden Markov Random Fields (HMRF) are widely used in solving various problems. Image segmentation is an example of such HMRF success. This paper presents a post-processing tool based on such a model and designed to increase the relevancy of a diagnosis system for rail defects detection. In this application, the hidden Markov field is not only used to define a spatial smoothness prior as it is often done in image segmentation, but it is used to learn the spatial interaction between track singular points, and so the track label patterns. For this, an approach based on a semi-parametric model is presented.

Keywords: railways diagnosis,patterns,Markov field,parameter estimation,databases

Identifier: 10.3182/20070613-3-FR-4909.00005

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Dandachi, Abdulrahman; Lohmann, Sven; Engell, Sebastian

Abstract: This paper presents complexity metrics that can be used to compare different logic controller designs in the format of sequential function charts for the same automation task and to assess the quality characteristics of the designs like usability and maintainability. The proposed method helps to improve the quality of logic controller designs, and thereby can reduce life-cycle cost. The method is illustrated by a application example.

Keywords: logic controller,quality,complexity analysis,metrics,sequential function chart

Identifier: 10.3182/20070613-3-FR-4909.00023

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Soldani, Siegfried; Combacau, Michel; Subias, Audine; Thomas, Jérôme

Abstract: This paper deals with an approach for the localization of intermittent faults in discrete events systems with partial observability. The proposed methods are based on a discrete events model representing the normal functioning of the observable behavior of the monitored system. This model based on automata formalism is built from the design data. The detection step consists of a comparison between the flow of observable events emitted by the monitored system and the flow foreseen by the model. A localization mechanism, based on diagnoser approach, points out the set of events potentially responsible for the faults. These two mechanisms are designed in order to operate on-board, in real time. An example from the automotive domain is presented.

Keywords: fault detection,fault localization,discrete-events systems,automata,automotive,intermittent faults

Identifier: 10.3182/20070613-3-FR-4909.00015

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Cabasino, M. P.; Giua, A.; Seatzu, C.

Abstract: In this paper we deal with the problem of estimating the marking of an arbitrary labeled Petri net system where two forms of nondeterminism may occur. Firstly, there may exist unobservable transitions, i.e., transitions labeled with the empty string. Secondly, there may exist undistinguishable transitions, i.e., two or more transitions sharing the same symbol taken from a given alphabet E may simultaneously be enabled.

Keywords: Petri-nets,labeled Petri nets,marking estimation,observability

Identifier: 10.3182/20070613-3-FR-4909.00041

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007

Authors: Alessandri, A.; Baglietto, M.; Battistelli, G.

Abstract: Discrete-time systems are considered that may switch among different modes taken from a finite set. The system and measurement equations of each mode are assumed to be linear and perfectly known, but the current mode of the system is unknown. The focus here is on the estimation of the mode of the system in the presence of disturbances. Different techniques are proposed and compared, each one well suited for a specific situation. In particular, when disturbances belong to known compact sets, "exact" conditions for the determination of modes consistent with the measures are given. If noises are zero-mean random variables with unknown distributions, a minimum-distance criterion is proposed. Finally, in the case of Gaussian noises, a method based on the maximum likelihood is adopted.

Keywords:

Identifier: 10.3182/20070613-3-FR-4909.00045

Conference: 1st IFAC Workshop on Dependable Control of Discrete Systems (2007)

Location: École Normale Supérieure de Cachan, France

Start Date: Wed Jun 13 2007 - End Date: Fri Jun 15 2007