[Newsletter] April2013

IEEE CONTROL SYSTEMS SOCIETY TECHNICAL COMMITTEE ON DISCRETE EVENT SYSTEMS Newsletter......................................... April, 2013 Editor: (Samuel) Qing-Shan Jia Chair, IEEE CSS Technical Committee on DES Center for Intelligent and Networked Systems Department of Automation Tsinghua University Beijing 100084 China Phone: (+86) 10-6277-3006 Fax: (+86) 10-6279-6115 e-mail: jiaqs@tsinghua.edu.cn WWW: http://cfins.au.tsinghua.edu.cn/personalhg/jiaqingshan/ It is the responsibility of the contributor to ensure that they have the necessary permissions/clearance required for the transmittal of their news item. _.___________________________________________________________________._ Contents: 1. Editorial 2. Journals 2.1 Selections from the Automatica Volume: 49, Issue: 4, April 2013 2.2 Selections from the Discrete Event Dynamic Systems: Theory and Applications Volume: 23, Issue: 2, June 2013 2.3 Selections from the IEEE Transactions on Automatic Control Volume: 58, Issue: 4, April 2013 2.4 Selections from the IEEE Transactions on Automation Science and Engineering Volume: 10, Issue: 2, 2013 _.___________________________________________________________________._ Editorial _.___________________________________________________________________._ Welcome to the newsletter of the IEEE Control Systems Technical Committee on Discrete Event Systems! Personal note from the editor: WELCOME TO THE APRIL 2013 NEWSLETTER. SAMUEL _.___________________________________________________________________._ Journals _.___________________________________________________________________._ Contributed by: Yulin Lei < leiyl11@mails.tsinghua.edu.cn > SELECTIONS FROM THE AUTOMATICA VOLUME: 49 ISSUE: 4 APRIL 2013 1) Joint state and event observers for linear switching systems under irregular sampling Le Yi Wanga; Wei Fengb; G. George Yinc; Abstract: Joint estimation of states and events in linear regime-switching systems is studied under irregular sampling schemes which stem from improved sampling and quantization methods for efficient utility of communication resources. Joint observability and sampling complexity are established, extending Shannon’s sampling theorem and our recent results on sampling complexity to joint estimation problems. Observer design and convergence analysis are conducted for systems under noisy observations. It is shown that our algorithms converge strongly with an error bound of the order O(1/N)O(1/N). Simulation examples are included to illustrate potential usages of the algorithms. Web site: http://www.sciencedirect.com/science/article/pii/S0005109813000149 _.___________________________________________________________________._ Contributed by: Yulin Lei < leiyl11@mails.tsinghua.edu.cn > SELECTIONS FROM THE DISCRETE EVENT DYNAMIC SYSTEMS: THEORY AND APPLICATIONS VOLUME: 23 ISSUE: 2 JUNE 2013 1) The level set method for the two-sided max-plus eigenproblem Stéphane Gaubert, Sergeĭ Sergeev Abstract: We consider the max-plus analogue of the eigenproblem for matrix pencils, A ⊗ x = λ ⊗ B ⊗ x. We show that the spectrum of (A,B) (i.e., the set of possible values of λ), which is a finite union of intervals, can be computed in pseudo-polynomial number of operations, by a (pseudo-polynomial) number of calls to an oracle that computes the value of a mean payoff game. The proof relies on the introduction of a spectral function, which we interpret in terms of the least Chebyshev distance between A ⊗ x and λ ⊗ B ⊗ x. The spectrum is obtained as the zero level set of this function. Web site: http://link.springer.com/article/10.1007/s10626-012-0137-z 2) Methods for the estimation of the size of lookahead tree state-space Creag Winacott, Behnam Behinaein, Karen Rudie Abstract: Limited lookahead supervision is a discrete-event systems framework in which control decisions are made by looking at finite-step projections of the behaviour of the system’s underlying automata. Projected system behaviour is represented as a lookahead tree with some depth limit decided on by the user. It can be difficult to strike a balance between the complexities associated with storing and analyzing the trees and the amount of information available to make decisions, both of which increase with depth. This paper considers the problem of accurately estimating the state space of lookahead trees with the intent of simplifying the process of determining a favourable depth to use. Although the estimation methods presented here apply cleanly to only certain kinds of automata, they also shed light onto the more complex behaviour of the others. Web site: http://link.springer.com/article/10.1007/s10626-012-0138-y 3) Concurrency bugs in multithreaded software: modeling and analysis using Petri nets Hongwei Liao, Yin Wang, Hyoun Kyu Cho, Jason Stanley, Terence Kelly, Stéphane Lafortune, Scott Mahlke, Spyros Reveliotis Abstract: In this paper, we apply discrete-event system techniques to model and analyze the execution of concurrent software. The problem of interest is deadlock avoidance in shared-memory multithreaded programs. We employ Petri nets to systematically model multithreaded programs with lock acquisition and release operations. We define a new class of Petri nets, called Gadara nets, that arises from this modeling process. We investigate a set of important properties of Gadara nets, such as liveness, reversibility, and linear separability. We propose efficient algorithms for the verification of liveness of Gadara nets, and report experimental results on their performance. We also present modeling examples of real-world programs. The results in this paper lay the foundations for the development of effective control synthesis algorithms for Gadara nets. Web site: http://link.springer.com/article/10.1007/s10626-012-0139-x 4) Scheduling and control of real-time systems based on a token player approach Patrice Bonhomme Abstract: Petri nets are a powerful formalism for the specification and verification of concurrent systems, such as sequential systems and manufacturing systems. To deal with real-time systems whose time issues become essential, different extensions of Petri nets with time have been proposed in the literature. In this paper, a new scheduling and control technique for real-time systems modeled by ordinary P-time Petri nets is proposed. Its goal is to provide a scheduling for a particular firing sequence, without any violation of timing constraints ensuring that no deadline is missed. It is based on the firing instant notion and it consists in determining an inequality system generated for a possible evolution (in terms of a feasible firing sequence for the untimed underlying Petri net) of the model. This system can be used to check reachability problems as well as evaluating the performances of the model considered and determining the associated control for a definite functioning mode and it introduces partial order on the execution of particular events. Web site: http://link.springer.com/article/10.1007/s10626-012-0140-4 5) Mixed integer programming in production planning with backlogging and setup carryover: modeling and algorithms Tao Wu, Kerem Akartunalı, Jie Song, Leyuan Shi Abstract: This paper proposes a mixed integer programming formulation for modeling the capacitated multi-level lot sizing problem with both backlogging and setup carryover. Based on the model formulation, a progressive time-oriented decomposition heuristic framework is then proposed, where improvement and construction heuristics are effectively combined, therefore efficiently avoiding the weaknesses associated with the one-time decisions made by other classical time-oriented decomposition algorithms. Computational results show that the proposed optimization framework provides competitive solutions within a reasonable time. Web site: http://link.springer.com/article/10.1007/s10626-012-0141-3 _.___________________________________________________________________._ Contributed by: Yulin Lei < leiyl11@mails.tsinghua.edu.cn > SELECTIONS FROM THE IEEE TRANSACTIONS ON AUTOMATIC CONTROL VOLUME: 58 ISSUE: 4 APRIL 2013 1) Periodic Event-Triggered Control for Linear Systems Heemels, W.P.M.H.; Donkers, M.C.F.; Teel, A.R. Abstract: Event-triggered control (ETC) is a control strategy that is especially suited for applications where communication resources are scarce. By updating and communicating sensor and actuator data only when needed for stability or performance purposes, ETC is capable of reducing the amount of communications, while still retaining a satisfactory closed-loop performance. In this paper, an ETC strategy is proposed by striking a balance between conventional periodic sampled-data control and ETC, leading to so-called periodic event-triggered control (PETC). In PETC, the event-triggering condition is verified periodically and at every sampling time it is decided whether or not to compute and to transmit new measurements and new control signals. The periodic character of the triggering conditions leads to various implementation benefits, including a minimum inter-event time of (at least) the sampling interval of the event-triggering condition. The PETC strategies developed in this paper apply to both static state-feedback and dynamical output-based controllers, as well as to both centralized and decentralized (periodic) event-triggering conditions. To analyze the stability and the $ {cal L}_{2}$-gain properties of the resulting PETC systems, three different approaches will be presented based on 1) impulsive systems, 2) piecewise linear systems, and 3) perturbed linear systems. Moreover, the advantages and disadvantages of each of the three approaches will be discussed and the developed theory will be illustrated using a numerical example. Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6310015&contentType=Journals+%26+Magazines&sortType%3Dasc_p_Sequence%26filter%3DAND%28p_IS_Number%3A6482628%29 2) Delayed Detectability of Discrete Event Systems Shu, S.; Lin, F. Abstract: In this paper, we extend detectability to delayed detectability in order to answer the following question. After observing $k_{1}+k_{2}$ observable events, can we determine the state of a system at the time when the $k_{1}th$ event was observed? If the answer is yes, we say that the system is delayed detectable. It involves two delays: the prior delay $k_{1}$ before the estimation is attempted and the post delay $k_{2}$ after which the estimation is completed. We investigate various properties of delayed detectability. We also provide polynomial algorithms to check delayed detectability. The usefulness of delayed detectability is not only evident by the state estimation problems it solves, which include current state estimation problem and initial state estimation problem, but also evident by the fact that two important properties in discrete event systems, namely observability and diagnosability, can both be shown to be special cases of delayed detectability. Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6338269&contentType=Journals+%26+Magazines&sortType%3Dasc_p_Sequence%26filter%3DAND%28p_IS_Number%3A6482628%29 3) Event-Based Sensor Data Scheduling: Trade-Off Between Communication Rate and Estimation Quality Wu, J.; Jia, Q.-S.; Johansson, K.H.; Shi, L Abstract: We consider sensor data scheduling for remote state estimation. Due to constrained communication energy and bandwidth, a sensor needs to decide whether it should send the measurement to a remote estimator for further processing. We propose an event-based sensor data scheduler for linear systems and derive the corresponding minimum squared error estimator. By selecting an appropriate event-triggering threshold, we illustrate how to achieve a desired balance between the sensor-to-estimator communication rate and the estimation quality. Simulation examples are provided to demonstrate the theory. Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6286997&contentType=Journals+%26+Magazines&sortType%3Dasc_p_Sequence%26filter%3DAND%28p_IS_Number%3A6482628%29 _.___________________________________________________________________._ Contributed by: Yulin Lei < leiyl11@mails.tsinghua.edu.cn > SELECTIONS FROM THE IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING VOLUME 10 ISSUE: 2 2013 1) Fault Detection by Labeled Petri Nets in Centralized and Distributed Approaches Fanti, M.P.; Mangini, A.M.; Ukovich, W. Abstract: This paper addresses the problem of online fault detection and diagnosis in discrete event systems modeled by labeled Petri nets and using Integer Linear Programming Problem (ILPP) solutions. In particular, unobservable (silent) transitions model faults and both observable and unobservable transitions model the nominal system behavior. Furthermore, observable transitions exhibit a kind of non determinism since several different transitions may share the same event label. This paper proposes two diagnosers that work in two different system settings. The first one is a centralized fault detection strategy: the diagnoser waits for an observable event and an algorithm defines and solves some ILPPs to decide whether the system behavior is normal or may exhibit some faults. In the second setting, the system consists of a set of interacting PN modules and each module is monitored by a diagnoser that has local information on the module structure. Moreover, each diagnoser observes and detects the faults of the module it is attached to and shares information in some of its places that are shared with other modules of the system. Some case studies show the two different approaches and point out the peculiarities of the proposed strategies. Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6236236&contentType=Journals+%26+Magazines&sortType%3Dasc_p_Sequence%26filter%3DAND%28p_IS_Number%3A6493467%29 2) Online Sensor Activation for Detectability of Discrete Event Systems Shu, S.; Huang, Z.; Lin, F. Abstract: In this paper, we investigate online sensor activation to ensure detectability of discrete event systems. Detectability requires that states of a system can be determined or certain pairs of states can be distinguished by an external observer eventually or periodically. Since minimal sensor activation policies for detectability may not exist, two new concepts are introduced: 1) $k$-step distinguishability is introduced for strong detectability and 2) information-preserving is introduced for strong periodic detectability. The online sensor activation is then proposed and is based on the best state estimate available at the time of decision making. Three algorithms are developed for online sensor activation. The first two algorithms are for strong detectability. They minimize sensor activation while preserving $k$ -step distinguishability. The third algorithm deals with strong periodic detectability. It minimizes sensor activation while preserving state information. Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6416960&contentType=Journals+%26+Magazines&sortType%3Dasc_p_Sequence%26filter%3DAND%28p_IS_Number%3A6493467%29 _.___________________________________________________________________._ The End _.___________________________________________________________________._