Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In this paper, we consider a decentralized failure diagnosis problem for discrete event systems. Each local diagnoser makes a diagnosis decision based on local event observations. A sensor that detects the occurrence of an event may possibly fail due to, for example, aging degradation. It is desirable that the occurrence of any failure string should be correctly detected in the presence of sensor failures. We introduce a new notion of codiagnosability subject to permanent sensor failures, which is defined with respect to not only the set of nondeterministic local observation masks but also the global nondeterministic observation mask. Although the global observation mask is necessary to define codiagnosability, it is not used for performing decentralized diagnosis. The introduced notion of codiagnosability guarantees that the occurrence of any failure string can be correctly detected by a decentralized diagnoser within a bounded number of steps even if permanent sensor failures occur. We develop a method for verifying the codiagnosability property subject to permanent sensor failures. In addition, we compute the delay bound within which the occurrence of any failure string can be detected. PubDate: 2022-06-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Max-plus algebra is defined as the set of all real numbers with two binary operations (maximum and addition). This combination of the operations forms a very applicable tool for the investigation of systems working in discrete steps (discrete event dynamic systems). The search for the steady states in such systems leads to the study of the eigenvectors of the production matrix in the corresponding max-plus algebra. A vector x is said to be an eigenvector of a square matrix A if A ⊗ x = λ ⊗ x for some \(\lambda \in {\mathbb {R}}\) . In real systems, the input values are usually taken to be in some interval. This paper investigates the properties of eigenspaces for vectors with interval (inexact) coefficients. We suppose that an interval vector X can be split into two subsets according to a forall–exists quantification of its interval entries, i.e., X = X∀⊕X∃. If for any vector of X∀ there is at least one vector of X∃ such that their vector maximum is an eigenvector of A, then X is said to be a λ AE-eigenvector. Analogously, if there is at least one vector of X∃ such that for any vector of X∀ their vector maximum is an eigenvector of A, then X is said to be a λ EA-eigenvector. The properties of such eigenvectors are studied and their characterizations by equivalent conditions are presented. Polynomial and pseudopolynomial algorithms for checking some types of λ EA/λ AE-eigenvectors are suggested. PubDate: 2022-04-07
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract One of the challenges of fault diagnosis is to verify diagnosability of systems with huge state space efficiently. Model checking approaches have the potential to analyze such systems efficiently. In this work, we propose a model checking approach to deal with the problem of the diagnosability verification. We define the diagnosability property in the transition system framework. To check this property, we describe it by using an unique linear temporal logic (LTL) formula. Our approach can be carried out in model checker tools for formal verification of models, such as SPIN and NuSMV. To illustrate the efficiency of our approach we perform some experiments. First, we consider a railway level crossing benchmark, comparing the results of our approach in SPIN and NuSMV with the results found using DESLab and Supremica tools. Then, we perform an exploratory statistical analysis comparing the average size of verifiers computed with our approach in SPIN with the average size of verifiers (it number of states plus transitions) computed with DESLab, which is a tool for diagnosability verification of Discrete Event Systems (DES) that uses the same foundation idea. PubDate: 2022-04-04
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this work, we address the problem of synthesis of covert attackers in the setup where the model of the plant is available, but the model of the supervisor is unknown, to the adversary. To compensate the lack of knowledge on the supervisor, we assume that the adversary has recorded a (prefix-closed) finite set of observations of the runs of the closed-loop system, which can be used for assisting the synthesis. We present a heuristic algorithm for the synthesis of covert damage-reachable attackers, based on the model of the plant and the (finite) set of observations, by a transformation into solving an instance of the partial-observation supervisor synthesis problem. The heuristic algorithm developed in this paper may allow the adversary to synthesize covert attackers without having to know the model of the supervisor, which could be hard to obtain in practice. For simplicity, we shall only consider covert attackers that are able to carry out sensor replacement attacks and actuator disablement attacks. The effectiveness of our approach is illustrated on a water tank example adapted from the literature. PubDate: 2022-03-09
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Hierarchy is a tool that has been applied to improve the scalability of solving planning problems modeled using Supervisory Control Theory. In the work of Hill and Lafortune (2016), the notion of cost equivalence was employed to generate an abstraction of the supervisor that, with additional conditions, guarantees that an optimal plan generated on the abstraction is also optimal when applied to the full supervisor. Their work is able to improve their abstraction by artificially giving transitions zero cost based on the sequentially-dependent ordering of events. Here, we relax the requirement on a specific ordering of the dependent events, while maintaining the optimal relationship between upper and lower levels of the hierarchy. This present paper also extends the authors’ work (Vilela and Hill 2020) where we developed a new notion of equivalence based on cost equivalence and weak bisimulation that we term priced-observation equivalence. This equivalence allows the supervisor abstraction to be generated compositionally. This helps to avoid the explosion of the state space that arises from having to first synthesize the full supervisor before the abstraction can be applied. Here, we also show that models with artificial zero-cost transitions can be created compositionally employing the new relaxed sequential dependence definition. An example cooperative robot control application is used to demonstrate the improvements achieved by the compositional approach to abstraction proposed by this paper. PubDate: 2022-03-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This work is set in the context of supervisory control of discrete-event systems under partial observation. Attackers that are able to insert or erase occurrences of particular output symbols can tamper with the supervisor’s observation and by doing so, can lead the controlled system to undesirable states. We consider a scenario with multiple attackers, each one being an element of a set, called the attack set. We also assume that only one of the attackers within an attack set is acting, although we don’t know which one. According to previous results in the literature, a supervisor that enforces a given legal language, regardless of which attacker is acting, can be designed if the legal language is controllable and satisfies a property called P-observability for an attack set. The latter is an extended notion of observability and is related with the supervisor’s ability to always distinguish between outputs that require different control actions, even if the outputs were attacked. We present a new approach for checking if a given language is P-observable for an attack set, by first introducing a visual representation as well as some definitions that capture the attack’s effect. Additionally, we present two algorithms that together allow us to verify if a given language is P-observable for an attack set, when it is represented as an automaton. PubDate: 2022-03-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper we introduce and study weakly linear systems, i.e. systems consisting of matrix inequalities Eqs. 17–20, over the max-plus quantale which is also known as complete max-plus algebra. We prove the existence of the greatest solution contained in a given matrix X0, and present a procedure for its computation. In the case of weakly linear systems consisting of finitely many matrix inequalities, when all finite elements of matrices X0, As and Bs, s ∈ I are integers, rationals or particular irrationals and a finite solution exists, the procedure finishes in a finite number of steps. If in that case an arbitrary finite solution is given, a lower bound on the number of computational steps is calculated. Otherwise, we use our algorithm to compute approximations to finite solutions. PubDate: 2022-03-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Our work is integrated into a global methodology to design synchronously executed embedded critical systems. It is used for the development of medical devices implanted into human body to perform functional electrical stimulation solutions (used in pacemakers, deep brain stimulation...). These systems are of course critical and real time, and the reliability of their behaviors must be guaranteed. These medical devices are implemented into a programmable logic circuit in a synchronous way, which allows efficient implementation (space, consumption and actual parallelism of tasks execution). This paper presents a solution that helps to prove that the behavior of the implemented system respects a set of properties, using Petri nets for modeling and analysis purposes. But one problem in formal methods is that the hardware target and the implementation strategy can have an influence on the execution of the system, but is usually not considered in the modeling and verification processes. Resolving this issue is the goal of this article. Our work has two main results: an operational one, and a theoretical one. First, we can now design critical controllers with hard safety or real time constraints, being sure the behavior is still guaranteed during the execution. Second, this work broadens the scope of expressivity and analyzability of Petri nets extensions. Until then, none managed in the same formalism, both for modeling and analysis, all the characteristics we have considered (weights on arcs, specific test and inhibitor arcs, interpretation, and time intervals, including the management of effective conflicts and the blocking of transitions). PubDate: 2022-03-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This paper is about state estimation in a timed probabilistic setting. The main contribution is a general procedure to design an observer for computing the probabilities of the states for labeled continuous time Markov models as functions of time, based on a sequence of observations and their associated time stamps that have been collected thus far. Two notions of state consistency with respect to such a timed observation sequence are introduced and related necessary and sufficient conditions are derived. The method is then applied to the detection of cyber-attacks. The plant and the possible attacks are described in terms of a labeled continuous time Markov model that includes both observable and unobservable events, and where each attack corresponds to a particular subset of states. Consequently, attack detection is reformulated as a state estimation problem. PubDate: 2022-03-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The development of supervisory controllers for cyber-physical systems is a laborious and error-prone process. Supervisor synthesis enables control designers to automatically synthesize a correct-by-construction supervisor from a model of the plant combined with a model of the control requirements. From the supervisor model, controller code can be generated which is suitable for the implementation on a programmable logic controller (PLC). Supervisors for industrial systems that operate in close proximity to humans have to adhere to strict safety standards. To achieve these standards, safety PLCs (SPLCs) are used. For SPLC implementation, the supervisor has to be split into a regular part and a safety part. In previous work, a method is proposed to automatically split a supervisor model for this purpose. The method assumes that the provided plant model is a collection of finite automata. In this paper, the extension to extended finite automata is described. Additionally, guidelines are provided for modeling the plant and the requirements to achieve a favorable splitting. A case study on a rotating bridge is elaborated which has been used to validate the method. The case study spans all development steps, including the implementation of the resulting supervisor to control the real bridge. PubDate: 2022-03-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Supervisory controller synthesis is a means to compute correct-by-construction controllers for discrete event systems. As these systems and their requirements evolve over time, an updated supervisor needs to be computed each time an adaptation takes place. We consider the case that a supervisor has been synthesized for a given model, after which this model is (slightly) adapted. We investigate how we can make use of the previous synthesis result, in order to more efficiently compute the supervisor for the adapted model. We introduce model deltas as a means to describe the difference between pairs of models. Using the model deltas, a notion of atomic adaptations is introduced. For these atomic adaptations, algorithms are provided to compute the supervisor for the adapted model in a transformational manner from the previous synthesis result, rather than performing a completely new synthesis. These atomic adaptations can be iterated over, to transformationally compute a supervisor for model deltas that contain a number of atomic adaptations. To improve efficiency, it is shown how atomic adaptations can be grouped together based on their required computations and be processed at the same time. A running example is used to support the explanations on the functioning of the algorithms. The efficiency of the method is evaluated by means of both an academic and an industrial use case. PubDate: 2022-02-23
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The paper presents a novel approach for discovering Petri nets (PN) that include silent transitions from logs of event sequences. We propose a repairing method that extends existing discovery techniques that do not deal with silent transitions; such techniques may yield substructures that involve deadlocks. Such substructures, called inconsistent (IS), are detected through a structural pattern. IS are rewritten by adding new transitions labelled with event symbols already assigned to transitions in IS; the rewritten model has no deadlocks. Afterwards, the PN with duplicated event labels is transformed into an equivalent model with silent transitions. The algorithms derived from the technique, which have polynomial-time complexity, have been implemented and tested on examples of diverse structures. PubDate: 2022-02-07
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Opacity is an information flow property that captures the notion of plausible deniability in dynamic systems, that is whether an intruder can deduce that “secret” behavior has occurred. In this paper we provide a general framework of opacity to unify the many existing notions of opacity that exist for discrete event systems. We use this framework to discuss language-based and state-based notions of opacity over automata. We present several methods for language-based opacity verification, and a general approach to transform state-based notions into language-based ones. We demonstrate this approach for current-state and initial-state opacity, unifying existing results. We then investigate the notions of K-step opacity. We provide a language-based view of K-step opacity encompassing two existing notions and two new ones. We then analyze the corresponding language-based verification methods both formally and with numerical examples. In each case, the proposed methods offer significant reductions in runtime and space complexity. PubDate: 2022-02-02
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This paper studies the local and global robustness with q-step delay of max-plus linear systems, which requires part or all components of the state vectors remain unchanged under the bounded parameter perturbations after a finite number of steps. A graph approach based on the circuit with tail is proposed to determine the variable elements with respect to the local and global robustness. This approach induces a polynomial algorithm of finding the variable elements and their perturbation bounds, which is illustrated by numerical examples and simulations. The approach proposed is then applied in making train running-plan of railway transport systems, which allows the trains to have flexible traveling times. PubDate: 2021-12-20
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Opacity is an information flow property characterizing whether a system reveals its secret to a passive observer. Several notions of opacity have been introduced in the literature. We study the notions of language-based opacity, current-state opacity, initial-state opacity, initial-and-final-state opacity, K-step opacity, and infinite-step opacity. Comparing the notions is a natural question that has been investigated and summarized by Wu and Lafortune, who provided transformations among current-state opacity, initial-and-final-state opacity, and language-based opacity, and, for prefix-closed languages, also between language-based opacity and initial-state opacity. We extend these results by showing that all the discussed notions of opacity are transformable to each other. Besides a deeper insight into the differences among the notions, the transformations have applications in complexity results. In particular, the transformations are computable in polynomial time and preserve the number of observable events and determinism, and hence the computational complexities of the verification of the notions coincide. We provide a complete and improved complexity picture of the verification of the discussed notions of opacity, and improve the algorithmic complexity of deciding language-based opacity, infinite-step opacity, and K-step opacity. PubDate: 2021-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This paper proposes algorithms for supervisor synthesis in discrete event system models with distinguishers. Distinguishers are special components responsible to select an enabled event from a group of related refined events. They are a helpful modelling tool, but their use increases the state space and makes supervisor synthesis more difficult. The paper shows how general algorithms for modular or compositional synthesis can be enhanced by considering the special properties of distinguishers. This gives rise to systematic algorithms that compute least restrictive controllable and nonblocking supervisors, while working with only a part of the distinguisher model. A worked case study of a bottling plant demonstrates the efficacy of the approach. PubDate: 2021-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Engineering distributed self-adaptive systems is challenging due to multiple interacting components, some of which monitor and possibly modify the behavior of managed components that operate in highly dynamic settings. Formalizing such systems having a decentralized adaptation control has been recognized as a hard task. In this article, we introduce a formal framework based on Symmetric Nets (a well-established subclass of Colored Petri nets) for modeling and analyzing distributed self-adaptive discrete-event systems. Even though Petri Nets represent a sound and expressive formal model of concurrency and distribution, they cannot specify in a natural way structural changes enacted by adaptation procedures. We overcome this limitation by means of a two-layer modeling approach that enables clear separation of concerns and allows multiple decentralized adaptation procedures to be specified, validated, and verified against formal requirements. Validation and verification techniques are supported by powerful off-the-shelf tools tailored to Symmetric Nets. A self-healing manufacturing system case study is used to show applicability, advantages, and shortcomings of the approach. In particular, complexity issues are thoroughly discussed and mitigated by adopting complementary approaches based on interleaving reduction and behavioral symmetries exploitation. PubDate: 2021-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Timed Petri nets and max-plus automata are well known modelling frameworks for timed discrete-event systems. In this paper we present an iterative procedure that constructs a max-plus automaton from a timed Petri net while retaining the timed behaviour. Regarding the Petri net, we essentially impose three assumptions: (a) the Petri net must be bounded, i.e, the reachability graph must be finite; (b) we interpret the Petri net with single server semantics; and (c) the Petri net operates according to the race policy, i.e., the earliest possible transition will fire and thereby possibly consume tokens required by other competing transitions. Under these assumptions we show that the proposed procedure terminates with a finite deterministic max-plus automaton that realises the same timed behaviour as the Petri net. As a variation of the plain race policy, we also consider that a subsequently designed supervisor may temporarily disable distinguished transitions. Again, we present a terminating procedure that constructs a behaviour equivalent deterministic max-plus automaton. We demonstrate by example how the latter automaton can be utilised as an open-loop model in the context of supervisor control. PubDate: 2021-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we address the problem of failure detection and localization in a Timed Discrete Event System (TDES) such \((\max \limits ,+)\) -linear system graphically modeled by a Timed Event Graph (TEG). The considered failures are changes on holding times or tokens of the TEG places that can provoke shifts between an observed outcoming timed flow and an expected outcoming timed flow (for a given incoming timed flow). Indicators are built to first detect such shifts relying on the \((\max \limits ,+)\) algebraic framework and the residuation theory. An analysis of the indicators’ values provides information about time or event failure that could have happen. Then, thanks to the knowledge of the behavior of the system through its corresponding TEG, sets of failures that could explain the detected shifts are obtained. It comes from matrices of signatures for each indicator built on each observable output of the system. An example of application is proposed to experiment exhaustively failures of type time and event on each place of the TEG. PubDate: 2021-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This paper presents an automaton-based task and motion planning framework for multi-robot systems (MRS) to satisfy finite words of linear temporal logic (LTL) task specifications in parallel and concurrently. A parallel decomposition algorithm is developed to iteratively decompose a global task specification into a set of smaller subtask automata. Robots are assigned to the smallest task component in each subtask automaton. The capability transition system of the assigned robots and these subtask automata synthesize a corresponding set of subtask planning automata (SPA), each of which is either an independent satisfaction of an individual subtask automaton or a concurrent satisfaction of multiple subtask automata. The overall robot assignments and SPA can guarantee the MRS to satisfy all the subtask automata. Each SPA can generate a minimal cost task plan by taking into account the costs of multi-robot tasking. The robots then plan motions to execute the tasks associated with the minimal cost task plans. The proposed framework is demonstrated with a multi-robot experiment for manufacturing tasks in a lab setting. Extensive numerical simulations are also performed to evaluate the scalability, computational complexity, and execution efficiency of the proposed framework and show its advantages over the centralized task and motion planning strategy. PubDate: 2021-11-27
Hybrid journal (It can contain Open Access articles)
[2469 journals]
