[Newsletter] for December, 2013






                      ON DISCRETE EVENT SYSTEMS




Newsletter......................................... December, 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






         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.










1. Editorial




2. Announcement


         2.1 Post-doc position proposal


Allocation of control functions for construction of operational control architectures of critical systems




3. Journals


      3.1 Selections from the Automatica


          Volume: 49, Issue: 11, November 2013


          Volume: 49, Issue: 12, December 2013


     3.2 Selections from the IEEE Transactions on Control Systems Technology


          Volume: 21, Issue: 6, November 2013


 3.3 Selections from the IEEE Transactions on Automatic Control


          Volume: 58, Issue: 12, December 2013
















Welcome to the newsletter of the IEEE Control Systems Technical


Committee on Discrete Event Systems!




Personal note from the editor:




Welcome to the December 2013 newsletter.


















Contributed by: Jean-Marc Faure < faure@lurpa.ens-cachan.fr>




Post-doc position proposal


Allocation of control functions for construction of operational control


architectures of critical systems




(Apologies for multiple copies of this announcement)






The Automation Engineering team of LURPA is member of the research cluster


CONNEXION (Digital Control of Nuclear Power Plants for Export and Refurbishment),


funded by the French government in the frame of the program Investments for the Future.


Within this project, this team is responsible of the WP Control Functions Allocation and


Performance Evaluation of Operational Control Architectures. The work proposed for this


post-doc shall contribute to this WP and more precisely to the task Control Functions Allocation.




This task is the cornerstone of the construction of the operational control architecture;


its aim is to find a set of industrial controllers that is able to host all the control functions that have


 been previously specified, while satisfying constraints on capacities (maximal numbers of


inputs/outputs, memory size, …) and safety-related. It has been shown that this issue can be


formalized in the form of a constraint satisfaction problem with arithmetic and logic


constraints; two kinds of solutions may be searched: a set of feasible solutions, from which


the most appropriate solution is selected by an expert, or an optimal solution that


minimizes the number of industrial controllers.




Several worthwhile results have been already obtained (1,2) during the first phase of the


project by using ILP (integer linear programming) or reachability analysis techniques.


 However, scalability improvement and introduction of new allocation constraints requires


 these results be extended. Two approaches are currently under investigation:


combination of the above-mentioned techniques, to benefit from their complementary


strengths, and development of specific vector packing techniques. The selected candidate


 shall contribute to at least one of this research.





Designing operational control architectures of critical systems by reachability analysis.


Lemattre et al. IEEE CASE 2011, pp. 12–18



Using a meta-model to build operational architectures of automation systems for


critical processes. Lemattre et al. IEEE ETFA 2011, pp. 1–8




Candidate’s profile


The candidate must have a PhD in DES (Discrete Event Systems) and/or in OR (Operations Research)


with strong competences in discrete optimization. He/she must also have a good background in


experimentation with software tools of these fields.




•         Starting date: February/March 2014


•         Duration: 12 to 24 months


•         Location: Ecole Normale Superieure de Cachan, France


•         Salary: 2,300 € (net) per month




Applicants must send to jean-marc.faure@lurpa.ens-cachan.fr


•         A short CV (at most 2 pages)


•         A copy of their three main publications


•         A motivation letter


      .   2 cover letters














 Contributed by: Yulin Lei < leiyl11@mails.tsinghua.edu.cn >




Selections from the Automatica


                      Volume: 49, Issue: 11, November 2013


                      Volume: 49, Issue: 12, December 2013





A parameterized liveness and ratio-enforcing supervisor for a class of generalized Petri nets




Ding Liua, ZhiWu Lia, MengChu Zhou








The work proposes a synthesis method of supervisors for flexible manufacturing systems


modeled by a class of generalized Petri nets. A concept of resource usage ratios (RU-ratios) is


first presented to describe the occupation degree of a resource by an operation. Next, an intrinsically


 live structure characterized by a special numerical relationship between arc-weights and initia


l markings is investigated from a perspective of RU-ratios. Then, a new kind of supervisors is


synthesized on the ground of the generic nature of the intrinsically live structure. Such a supervisor


can achieve the purposes of both liveness-enforcement and resource usage ratio-enforcement of the


 system under consideration. Given a plant, it is easy to determine the topological structure of such a


 supervisor and the number of monitors is bounded by that of resources used in the plant. In addition,


 when the configuration of the plant model changes, the supervisor can be reusable through


adjusting control parameters only without rearrangement of connections. This makes it easy enough


 and intuitive to be used by industrial practitioners. Instead of maximal behavioral permissiveness,


 it pursues a precise usage of shared resources that are limited and valuable. Several examples are used


 to illustrate the proposed methods.




Web site: http://www.sciencedirect.com/science/article/pii/S0005109813003713







Integrated design of optimal supervisors for the enforcement of static and


behavioral specifications in Petri net models




F. Basilea, R. Cordoneb, L. Piroddi








Petri net (PN) supervisory control is often performed through a sequential procedure that


 introduces additional constraint layers over an initial unconstrained PN model, using generalized


 mutual exclusion constraints (GMECs) implemented as monitor places. This is typical, e.g., in the


 context of flexible manufacturing systems, where the initial model represents the production


sequences and the constraints are used to express static specifications, such as job limitations


or the usage of resources, and behavioral ones, as liveness, controllability, etc. This sequential


procedure may yield a redundant model, that is not easily reduced a posteriori. Also, it is difficult


 to ensure maximal permissivity with respect to multiple behavioral specifications. This paper,


 building on recent results regarding optimal supervisor design with branch & bound methods,


 proposes an integrated modeling approach that can be used to derive a minimal supervisor


 guaranteeing the attainment of an arbitrary set of static and behavioral specifications in a


maximally permissive way. Among behavioral specifications, deadlock-freeness, liveness,


reversibility and behavioral controllability are considered in the paper. The supervisor comes in the


 form of a simple set of GMECs or of a disjunction of sets of GMECs. Some examples emphasize


 the potential model size reductions that can be achieved.




Web site: http://www.sciencedirect.com/science/article/pii/S0005109813004196







Discrete-event modeling of multi-agent systems with broadcasting-based parallel composition




Rong Su








Multi-agent systems have been widely used in logistics and manufacturing. In this paper we develop


an automaton-based modeling framework for a special type of multi-agent systems, where agents are


 instantiated from a finite number of finite-state automaton templates, and interactions among


 agents are characterized via cooperative synchronization and broadcasting. To describe the


compositional behavior of all agents, we propose a novel broadcasting-based parallel composition


rule and show that it is commutative and associative. The effectiveness of this modeling framework


and the parallel composition rule is illustrated in a simple multi-agent system.




Web site: http://www.sciencedirect.com/science/article/pii/S0005109813004081







Feasibility of piecewise-constant control sequences for timed continuous Petri nets




Edouard Leclercq, Dimitri Lefebvre








In this study, the determination of control actions for timed continuous Petri nets is investigated


 by the characterisation of attractive regions in marking space. In particular, attraction in finite


 time, which is important for practical issues, is considered. Based on the characterisation of


attractive regions, the domain of admissible piecewise constant control actions is computed,


and sufficient conditions to verify the feasibility of the control objectives are proposed. As a


consequence, an iterative procedure is presented to compute piecewise constant control actions


that correspond to local minimum time control for timed continuous Petri nets.




Web site: http://www.sciencedirect.com/science/article/pii/S0005109813004500








Contributed by: Yulin Lei < leiyl11@mails.tsinghua.edu.cn >




Selections from the IEEE Transactions on Control Systems Technology


     Volume: 21 Issue: 6


November 2013





Eliminating Concurrency Bugs in Multithreaded Software: A New Approach Based


on Discrete-Event Control




Hongwei Liao, Yin Wang, Stanley, J., Lafortune, S.








Computer hardware is moving from uniprocessor to multicore architectures. One problem arising


 in this evolution is that only parallel software can exploit the full performance potential of multicore


 architectures, and parallel software is far harder to write than conventional serial software. One


 important class of failures arising in parallel software is circular-wait deadlock in multithreaded


programs. In our ongoing Gadara project, we use a special class of Petri nets, called Gadara nets, to


systematically model multithreaded programs with lock allocation and release operations. In this paper,


 we propose an efficient optimal control synthesis methodology for ordinary Gadara nets that


exploits the structural properties of Gadara nets via siphon analysis. Optimality in this context


refers to the elimination of deadlocks in the program with minimally restrictive control logic. We formally


 establish a set of important properties of the proposed control synthesis methodology, and show


that our algorithms never synthesize redundant control logic. We conduct experiments to evaluate the


 efficiency and scalability of the proposed methodology, and discuss the application of our results


to real-world concurrent software.




Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6403531








Contributed by: Yulin Lei < leiyl11@mails.tsinghua.edu.cn >




Selections from the IEEE Transactions on Automatic Control


                                             Volume: 58 Issue: 12


                                                   december 2013





Diagnosis of Discrete Event Systems Using Satisfiability Algorithms: A Theoretical


and Empirical Study




Grastien, A., Anbulagan, A.








We propose a novel algorithm for the diagnosis of systems modelled as discrete event systems.


Instead of computing all paths of the model that are consistent with the observations, we use a


 two-level approach: at the first level diagnostic questions are generated in the form does there


 exist a path from a given subset that is consistent with the observations?, whilst at the second level


 a satisfiability (SAT) solver is used to answer the questions. Our experiments show that this


 approach, implemented in SAT, can solve problems that we could not solve with other techniques.




Web site: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6572825










                                                              The End