dcds_logo

Accepted Papers

Julien Provost, Jean-Marc Roussel and Jean-Marc Faure. Testing Programmable Logic Controllers from Finite State Machines specification

This paper shows, on the basis of experiments, that conformance test of programmable logic controllers with minimum-length test sequences built from specifications in FSMs may yield spurious results. A new approach to build test sequences is then proposed to remove, or at least strongly lessen, this issue.

Bouaziz Mohammed Farouk, Zamai Eric, Duvivier Frederic and Hubac Stéphane. Dependability of complex semiconductor systems: Learning Bayesian Networks for decision support

The production of microelectronic components is characterized by an important complexity of production, high rhythm of renewal technology, a strong customer requirement and an uncertain environment. This has an impact on the cycle time, cost and manufacturing efficiencies.

This paper presents a general methodology to manage the risks of complex semiconductors systems. A literature review about process control, risk analysis methods and Bayesian networks is presented. A first structure of the predictive behavior model is proposed, this model is based on probabilistic Bayesian techniques.

Luca Ferrarini, Massimo Allevi and Alessio Dedè. Implementation and testing of an online fault isolation methodology in a real industrial scenario

The diagnosis of manufacturing systems plays an important role in the safety of both systems and operators. The paper presents a real application of systematic approaches to fault identification problem in the manufacturing field up to the online implementation. The diagnostic method is a derived from the classical diagnoser one, with the explicit modeling of time-out and the explicit modeling of nominal and non-nominal control behavior. The aim of this novel diagnostic algorithm is to isolate faults that can occur in typical devices of machining centres. The diagnostic model and the approach has been defined and inserted in the model-driven architecture defined in the EU-MEDEIA project with the aim to describe a generic industrial plant as set of components.

Yannick Nke and Jan Lunze. Online control reconfiguration for a faulty manufacturing process

This paper proposes an online reconfiguration method for discrete event systems described by nondeterministic Input/Ouput automata. The method modifies the control law to circumvent the effects of sensor and internal system failures. It is based on a necessary and sufficient reconfigurability condition published recently. The main result is an online reconfiguration procedure that is based on backward and forward recovery strategies for discrete event systems subject to faults. After a failure has occurred, checkpoint states and control laws are iteratively computed until a state is found from which the process can be resumed. The applicability of the approach is demonstrated on a "pick & place system".

Alexandre Philippot. Survey on Diagnosis of a Pick and Place Benchmark

This paper is a survey to present a benchmark for a special session on diagnosis of Discrete Event Systems. This session consists in comparing several diagnosis approaches around a common example. A Pick and Place station from a simulating tool is used to simulate approaches without any risk of injury to man or damage to machine. The paper presents the benchmark components and defines control specification. It also deals with Key Performance Indicators to evaluate the proposition.

Mickael Danancher, Matthias Roth, Jean-Jacques Lesage and Lothar Litz. A comparative study of three model-based FDI approaches for Discrete Event Systems

In this paper three model-based Fault Detection and Isolation (FDI) approaches for Discrete Event Systems (DES) are evaluated. The considered approaches are the diagnoser approach, the templates approach and the residual approach. The investigated methods have different characteristics like timed / non-timed behavior and fault-free / faulty system models with important impacts on the model-building process and the respective effectiveness. By applying the three methods to the same benchmark system, their respective performances are analyzed in terms of fault detection and fault isolation ability, complexity of implementation and avoidance of false alarms.

Stefan Schneider, Mickaël Danancher and Lothar Litz. Timed Residuals for Fault Detection and Isolation in Discrete Event Systems

In this paper a new attempt for fault detection and isolation in discrete event systems is proposed. An identified model constitutes a timed observer of the fault-free system behavior. Non-acceptable plant operation is detected by comparing the behavior of the model with the observed system output. For fault isolation, timed residuals and generic fault symptoms – early and late events – are introduced. Time bounds are composed using interval arithmetic and normal distribution. In case of a fault, timed and untimed residuals are concluded in order to refine a set of potential faulty candidates. The method is applied to the given benchmark system of a virtual production plant with an external controller.

Sebastian Preuße and Hans-Michael Hanisch. Verifying Functional and Non-Functional Properties of Manufacturing Control Systems

Verification of control software is usually not applied in industrial practice because of additional work expenses and missing theoretical background that is necessary to apply this technique. Therefore, this contribution presents an integrated approach to verify functional and non-functional properties of manufacturing control systems. To support the user in creating a well-defined but also understandable specification of plant behavior, two approaches are introduced that specify functional requirements with Symbolic Timing Diagrams and non-functional ones with a Safety-Oriented Technical Language.

These behavior descriptions are then translated to temporal logic formulas to perform model-checking of the closed-loop system of plant and controller.

Alexandre Philippot and Veronique Carré-Ménétrier. Methodology to obtain local discrete diagnosers

This paper deals with an approach of diagnosis for manufacturing system considered as Discrete Event Systems. A decomposition of the plant by mechanical component is used to construct a decentralized diagnosis structure to reduce the combinatory explosion found in centralized structures. Local normal behavior is extracted from local Plant Element using controller information. Possible faults are identified by partition to construct abnormal behavior models. The approach is evaluated with key performance indicators and uses the Pick and Place benchmark proposed in the session.

Matthias Guedemann and Frank Ortmeier. Towards Model-driven Safety Analysis

Model-based safety analysis allows very high quality analysis of safety requirements. However, building adequate models for each analysis requires a lot of effort and expertise. Model-driven approaches help by automating the generation of analysis models. For safety analysis, both qualitative (i.e. what must go wrong for a system failure) and quantitative aspects (i.e. how probable is a system failure) are of great interest. Traditionally, the analysis of these aspects requires separate, tool-dependent formal models.

SAML is a tool-independent modeling framework that allows for the construction of models with both non-deterministic and probabilistic behavior.

SAML models can automatically be transformed into different state of the art formal analysis tools -- while preserving its semantics -- to analyze different aspects of safety. As a consequence both -- qualitative and quantitative -- model-based safety analysis can be done without any additional generation of models with transferable results.

This approach makes SAML an ideal intermediate language for a model-driven approach. Every higher-level language that can be transformed into SAML can be analyzed with all targeted formal analysis tools, new analysis tools can be added and the user of benefits from every advancement of the analysis tools.

Annie Francie Kouedeu, Jean-Pierre Kenne and Victor Songmene. Production, preventive and corrective maintenance planning in manufacturing systems under imperfect repairs

This paper deals with the joint analysis of the optimal production and maintenance planning problems for a manufacturing system subject to random failures and repairs. When a machine fails down, an imperfect repair is undertaken. The objective of this study is to minimize a discounted overall cost consisting of preventive and corrective maintenance costs, inventory holding cost and backlog cost. A two-level hierarchical decision making approach, based on the determination of the mean time between failures (first level) and the statement of a joint optimization of production, preventive and corrective maintenance policies (second level) is proposed. Hence the production, preventive and corrective maintenance rates are determined in the second level given the failure rates between failures, obtained from the first level. In the proposed model, the failure rate of the machine depends on the number of failures; hence, the control policies of the considered planning problems depend on the number of failures. A numerical example and a sensitivity analysis will illustrate the structure of the optimal control policies and the usefulness on the proposed approach.

Dejan Jovanovic. Philip K. Pollett Fault Diagnosis Using Consensus on Markov chains

In this paper a fault diagnosis procedure is proposed based on consensus in the group of local agents/experts. Local models are represented by Markov chains. Modelling consensus in the group of Markov chains as the mixture of corresponding chains, allows the estimation of optimal ratings in the consensus problem using the EM framework.

To work with unobservable Markov chains the proposed algorithm is possible to extend to the case of the Hidden Markov models (HMMs).

Geoffrey Fallet, Carole Duval, Christophe Simon, Philippe Weber and Benoit Iung. Expert judgment collecting and modeling: Application to the Integrated Risks Analysis (IRA) methodology

Assessment of different types of risks is today one of the challenges for an Integrated Risks Analysis (IRA)methodology. Indeed, whereas technical or environmental risks assessment can generally be done by means of statistical way, human and organizational considerations are more taken into account with the use of expert judgment. This considerations lead from a scientific point of view to address issues such as how the information provided by the experts can be collected and then modeled. Thus this paper aims at reviewing different ways needed to express expert knowledge but also different frameworks for representing the information collected. These two items have to support the full development of the IRA methodology.

Thomas Brunsch, Laurent Hardouin and Jörg Raisch. Modeling and Control of Nested Manufacturing Processes using Dioid Models

Manufacturing systems are frequently adapted to changing customer demands. However, every extension with respect to the hardware requires a modification of the corresponding model and controller. In this paper we propose a dioid model of manufacturing processes in which parts may visit the same resource more than once. The proposed model can be used to determine a controller that maintains the throughput while starting activities just-in-time. Furthermore, the model can easily be adapted in case of hardware modifications. Also nested processes, i.e., processes in which some activities of part k may be executed prior to activities of part (k + 1), can be modeled with the proposed approach.

Sahar Mohajerani, Robi Malik, Simon Ware and Martin Fabian. On the Use of Observation Equivalence in Synthesis Abstraction

In a previous paper we introduced the notion of synthesis abstraction, which allows efficient compositional synthesis of maximally permissive supervisors for large-scale systems of composed finite-state automata. In the current paper, observation equivalence is studied in relation to synthesis abstraction. It is shown that general observation equivalence is not useful for synthesis abstraction. Instead, we introduce additional conditions strengthening observation equivalence, so that it can be used with the compositional synthesis method. The paper concludes with an example showing the suitability of these relations to achieve substantial state reduction while computing a modular supervisor.

Eric Gascard and Zineb Simeu-Abazi. Automatic Construction of Diagnoser for Complex Discrete Event Systems

We study the problem of fault diagnosis in the context of communicating timed automata. Indeed, complex discrete event systems can be modelled as timed systems whose components communicate through channels. This paper starts with a description of our modelling methodology of discrete event systems as communicationg timed automata. Our work for diagnosis (detection and isolation) is based on the methodology known as the diagnoser approach. Starting from a model of the complex system, this approach compute a deterministic automaton, called a diagnoser, that uses observable events to detect the occurrence of a failure. This paper extends the diagnoser approach to communicating timed automata. The steps of the method are described by algorithms and illustated through a batch neutralisation process.

Sebastian Biallas, Joerg Brauer and Stefan Kowalewski. SAT-Based Abstraction Refinement for Programmable Logic Controllers

This paper studies the application of counterexample-guided abstraction refinement to programs written in Instruction List. More importantly, it presents an approach for automatic abstraction refinement based on SAT solving. This technique is based on an encoding of the semantics of Instruction List in propositional Boolean logic. Since elegant ideas and careful engineering have advanced SAT solvers to the state they can rapidly decide satisfiability of structured problems that involve thousands of variables, this approach scales well in practice. The true force of this method, however, is that a single description of the semantics of a program can be used to perform abstraction refinement in a number of abstract domains, including but not limited to intervals and bit sets, thereby decoupling the refinement from the chosen abstraction.

Jan Richter. Reliability Estimation using Unscented Transformation

In this paper, we consider the problem of fast reliability analysis with focus on mean and covariance for large-scale systems that consist of components with not necessarily exponential and possibly cross-correlated failure statistics. For its solution we propose to use the unscented transformation, an error-bounded deterministic sampling method known from filter theory. The estimation problem is approached from two different directions. From one perspective, the mean and variance of the system survival probability are estimated for a fixed time instant, whereas from the other perspective, mean and covariance of the failure times are estimated. The main difference between these perspectives is that the former is numerically better behaved than the latter. An example illustrates these methods.

Sahika Genc and Timothy L. Johnson. Automatic Adaptive Limit and Level Management of Arrhythmia Alarms

Automatic adaptive alarm limit and level management logic, to reduce workflow for electrocardiographic monitoring devices, is described. Performance and functional requirements for alarm limit and level adaptation logic are developed. The design for a single patient processing unit of adaptive alarm management logic for a single alarm, a collection of concurrent and asynchronous Timed Input/Output Automata, is presented. Performance results are provided on a data set consisting of 158 alarm records, roughly approximating a month's admissions in an Intensive Care Unit at a large hospital.

Clive Downes and Paul Chung. Hazards in Advising Autonomy

This paper describes the continuation of a research project to identify and develop tools for the identification and management of hazards likely to arise with the quality and reliability of automatic advice – such as in an automated system advisory function, especially where supporting a ?Sense & Avoid capability as embodied within an airborne autonomous system. An earlier literature survey has been used to map detail onto a Use Case model representing an outline certifiable system development process; thereby helping to identify an appropriate research direction within the broad range of potential end-user requirements. From this direction, an approach has emerged to evaluate hypothetical deviations from declared intent within a behavioral modeling framework to be styled upon Owen’s STAMP-Based Hazard Analysis (STPA) [1]. For this approach an outline exemplar describing an air-proximity hazard arising between two air-vehicles has been developed, and the representation of the control structure and system dynamics describing this model are considered. Arising from this model some consideration is then given towards the expression of a more systematic approach in the construction of such models, leading towards new methods to derive safety requirements for implementation within autonomous air systems.

Spyros Reveliotis. Optimized Scheduling of Complex Resource Allocation Systems through Approximate Dynamic Programming

In spite of the tremendous progress that has been attained by the scientific community on the sequencing and scheduling problems that underlie the operation of many technological applications, there is a remaining gap between the analytical insights and results offered by the existing scheduling theory and the solutions to the scheduling problems that are typically adopted in the industrial practice. The work undertaken in this project seeks to bridge this gap by tapping upon recent developments in the Supervisory Control of Resource Allocation Systems and Approximate Dynamic Programming. When combined, these two areas provide high-fidelity representations of the underlying dynamics and effective tools for developing (near-)optimal scheduling policies while explicitly managing the complexity that underlies the development and implementation of these policies. This write-up outlines the basic framework that supports the proposed approach and reports upon the current progress of the work.

Andrea Bobbio, Roberta Terruggia, Michele Minichino and Ester Ciancamerla. Reliability Analysis of Multi-source Multi-sink Critical Interacting Systems

Traditional reliability studies on probabilistic networks are devoted to evaluate the probability that two nodes or K nodes are connected, assuming that nodes are undifferentiated.

In flow networks, however, we need to distinguish between source nodes where the flow is generated and sink nodes where the flow is utilized. Sink nodes may usually be fed by many sources. To this end, we have extended the traditional studies to include multisource multi-sink networks. A case study is analysed consisting in a portion of an electrical grid controlled by a its SCADA system through a public telecommunication network.

Felix Felgner and Georg Frey. Multi-Phase Markov Models for Functional Safety Prediction

The contribution first describes the implementation of Continuous-Time Markov Chains (CTMC) in the language Modelica; this enables the simulation by powerful solvers making typical Functional Safety applications numerically more efficient and reliable than with classically used Discrete-Time Markov Chains (DTMC). Secondly, the CTMC are extended to Multi-Phase Markov Chains (CTMCMP) enabling the inclusion of maintenance (restoration) actions as well as online diagnostics, which is finally elaborated to the online prediction of an individual system’s safety quantities.

Kleanthis Thramboulidis, Doaa Soliman and Georg Frey. A Methodology to Upgrade Legacy Industrial Systems to Meet Safety Regulations

There is a need to upgrade legacy system in industry to conform with the norms and regulations on safety that are defined by recent standards. The great investment for the development of these systems is the main reason for the industry to look for approaches that upgrade existing systems instead of adopting a redevelopment of the whole system. In this paper we describe an approach to upgrade legacy industrial applications based on the IEC61131 function block model without the need to redesign the whole application. The approach that integrates the 3+1 SysML-view model with safety engineering is adopted and is tailored to the needs upgrading legacy applications. Challenges are identified and solutions are proposed towards the definition of the whole development process including the verification of the so generated safety application. A laboratory system is used as a case study in this paper to demonstrate the applicability of the proposed approach.

Gilbert Habib, Jean-François Pétin and Thierry Divoux. Dynamic adaptation of IEEE 802.11e priorities for improving temporal performance and safety of a Wireless Networked Discrete Control

This paper deals with Discrete Control Systems whose implementation is distributed among devices communicating through a Wireless Network. The use of wireless communication in these applications, called Wireless Networked Discrete Control System (WNDCS), offers many advantages, but the undeterministic behaviour of the network may have a negative impact on the temporal performance and safety of the control applications. This paper focuses on WNDCS communicating through IEEE 802.11e. It presents an algorithm that adapts the flow communication priorities according to the control states in order to increase the WNDCS quality of service and safety.

Francesco Basile, Pasquale Chiacchio, Jolanda Coppola and Gianmaria De Tommasi. Identification of Petri Nets using timing information

This paper deals with the identification problem for deterministic timed Petri net systems. The proposed algorithm identifies a timed Petri net starting from the observed timed sequence of transitions. The main idea is to use the timing information to accelerate the net identification with respect to the untimed approaches. Furthermore, exploiting the timing it is possible to determine a set of counterexamples, i.e., a set of strings that do not belong to the language, that can be used to improve the net identification. The identification approach proposed in this paper focuses on free labeled timed Petri nets.

Edouard Leclercq and Dimitri Lefebvre Geometric characterization of invariant regions for timed continuous Petri nets with control actions

Stability analysis and advanced control design require the characterization of positive invariant regions. In this contribution, this characterization is developed for contPNs with piecewise constant control actions according to a geometric approach. Upper and lower bounds of the maximal positive regions are proposed.

Maria Pia Fanti, Agostino Marcello Mangini and Walter Ukovich. Fault Detection by Labeled Petri Nets and Time Constraints

This paper generalizes a previous result on the diagnosis of discrete event systems in a Petri Net framework and based on Integer Liner Programming problem solutions. In particular, we assume like in the previous work that silent transitions model faults and both observable and unobservable transitions model the nominal system behavior. However, in this contribution observable transitions exhibit non determinism since several different transitions may share the same event label. Moreover, a timing structure of the events is considered. For this more general problem, a new fault detection strategy is devised, which enables to define a new diagnoser that detects faults in the new system setting. An example points out the efficiency of the proposed approach.

Elías Hernández-Flores, Ernesto López-Mellado and Antonio Ramírez-Treviño. Diagnosability Analysis of Partially Observable Discrete Event Models

This paper addresses the diagnosability property of discrete event models, which is a key feature in model-based failure diagnosis. Two main results are presented. The first one is an extended notion of the property coping with languages including blocking sequences, unobservable cycles, and sequences that exhibit the same observable projection; necessary and sufficient conditions for diagnosable languages are provided. In the second result, necessary and sufficient conditions for diagnosability of Interpreted Petri Nets (IPN) are given, based on the observations of reachable repetitive vectors; then an algorithm to verify sufficient conditions for diagnosability of deadlock-free IPN is proposed.