IEEE CONTROL SYSTEMS SOCIETY TECHNICAL COMMITTEE
ON DISCRETE EVENT SYSTEMS

    Ryan J. Leduc
    Chair, IEEE CSS Technical Committee on DES
    Dept. of Computing and Software
    McMaster University
    1280 Main Street West
    Hamilton, Ontario
    Canada L8S 4K1

    Phone: (905) 525-9140 Ext. 27962
    Fax: (905) 524-0340
    e-mail: leduc@mcmaster.ca
    WWW: http://www.cas.mcmaster.ca/~leduc/

DESTC Web Page: http://www.cas.mcmaster.ca/destc/

To subscribe/unsubscribe to the newsletter, please go here.

To submit news items and articles to this newsletter, go here.

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. Announcements
 2.1 ACM Eurosys Workshop on Feedback Control Implementation and Design in
     Computing Systems and Networks (FeBID 2010)
 2.2 PhD: DCSC, TU Delft, The Netherlands

3. Books
 3.1 Handbook of Hybrid Systems Control", by J. Lunze, F.
     Lamnabhi-Lagarrigue (Eds.)
 3.2 Discrete-Event Modeling and Simulation: A Practitioner's Approach",
     by Gabriel A. Wainer

4. Conferences
 4.1 IFAC Workshop on Discrete Event Systems (WODES 2010), Berlin,
     Germany, August 30 - September 1, 2010
 4.2 IEEE International Conference on Robotics, Automation and
     Mechatronics, Kuala Lumpur, Malaysia, June 7 - 9, 2010

5. Journals
 5.1 Selections from Automatica, Volume 45, Issue 11, November 2009
 5.2 Selections from IEEE Transactions on Systems, Man and Cybernetics, Part
     A: Systems and Humans, Volume: 39, Issue: 6, November 2009
 5.3 Discrete Event Dynamic Systems, Volume 19 Number 4, November 2009

Welcome to the newsletter of the IEEE Control Systems Technical Committee on Discrete Event Systems!

See http://www.cas.mcmaster.ca/destc/ for information on the DESTC.

Personal note from the editor:

Welocme to the Nov. 2009 DESTC newsletter,

Ryan

Contributed by: Eric Rutten <eric.rutten@inria.fr>

ACM EUROSYS WORKSHOP ON FEEDBACK CONTROL IMPLEMENTATION AND DESIGN IN
COMPUTING SYSTEMS AND NETWORKS (FEBID 2010)

---------------------------
Title:
---------------------------
Fifth International Workshop on Feedback Control Implementation and
Design in Computing Systems and Networks (FeBID 2010)

In conjunction with the ACM SIGOPS EuroSys 2010 Conference, Paris, France

---------------------------
Web site:
---------------------------
http://controlofsystems.org/febid2010/


---------------------------
Synopsis
---------------------------
FeBID is a series of workshops. In 2010, FeBID is associated with the
ACM SIGOPS EuroSys 2010 conference. The workshop aims to bring together
researchers, practitioners, system administrators, system programmers,
and others interested in the latest advances in the control of computer
systems and networks. The focus of the workshop is on novel, practical,
systems-oriented work. Please see the Conference Website for further
details: http://controlofsystems.org/febid2010/

FeBID explicitly encourages members of the systems community to explore
leading-edge topics and ideas before they are presented at a major
conference. Two formats of contributions are welcome: regular papers (6
pages), and position papers (2 pages).

FeBID will feature a Keynote speech on Introduction to "Control Theory
and Its Application to Computing Systems", given by Joseph L.
Hellerstein, Google. This talk provides an introduction to control
theory for computer scientists with an emphasis on applications,
industry implementations as well as research directions.

---------------------------
Dissemination
---------------------------
Accepted papers will be published in the proceedings of FeBID in the
ACM Digital Library.

Furthermore, selected papers from FeBID will be published in a special
issue of the ACM Operating Systems Review (OSR), see
http://www.sigops.org/osr.html.

---------------------------
Important dates
---------------------------
Paper submission:   February 1, 2010
Acceptance notification:   March 1, 2010
Final paper due:   March 29, 2010
Workshop:   April 13, 2010

---------------------------
Contact Email:
---------------------------
febid10-chairs@controlofsystems.org

---------------------------
Program Chairs
---------------------------
-       Sara Bouchenak, Grenoble University
-        Eric Rutten, INRIA Grenoble

---------------------------
Program Committee
---------------------------
-        Luis Almeida, Univ. of Aveiro, Portugal
-        Karl-Erik Arzen, Lund University
-        Yixin Diao, IBM T.J. Watson Research Center
-        Joseph L. Hellerstein, Google
-        Xenofon D. Koutsoukos, Vanderbilt University
-        Stephane Lafortune, University of Michigan
-        Jie Liu, Microsoft Research
-        Chenyang Lu, Washington University in St. Louis
-        Arif Merchant, Hewlett Packard Labs
-        Guillaume Pierre, Vrije Universiteit
-        Anders Robertsson, Lund University
-        Sharad Singhal, Hewlett Packard Labs
-        Emin Gun Sirer, Cornell University
        Bhuvan Urgaonkar, The Pennsylvania State University
        Qian Wang, Pennsylvania State University
        Yin Wang, HP Labs
        Xiaoyun Zhu, VMware

Contributed by: Ryan Leduc <leduc aT mcmasterDot cA>

PHD: DCSC, TU DELFT, THE NETHERLANDS

Project Title: 'Development of novel Hybrid Dynamical Models for the
study of Transportation Networks'

General Description:
Transportation Networks are ubiquitous nowadays. A reliable, resilient,
secure, and efficient operation
of these systems (such as road traffic networks, railway networks,
electricity networks, etc.) is of paramount importance both when
the systems are operated to the limits of their performance during
critical situations, as well as under regular operating conditions.
This can translate into a significant societal impact involving
economic growth and quality of life and the environment. A quantitative
and formal understanding of this complex systems calls for the
development of proper mathematical formalisms to model and analyze them.

Discrete-event systems are mathematical models developed to describe
synchronization and con- currency for time-dependent,
resource-constrained systems shared by multiple users. Hybrid Systems
are dynamical models that, by construction, are suitable at describing
complex systems, where analog/continuous/physical quantities interact
with discrete/digital ones.

The major goal of this project is to introduce a novel formal
mathematical framework that is capable of connecting the theory of
classes of discrete-event systems with that of (probabilistic) hybrid
systems. Secondly, the project will apply the generated model
framework in the description, analysis, verification and control of
classes of transportation networks. In particular, applications in
intelligent traffic control will be developed in connection with the
research team of Prof. Bart De Schutter at DCSC.

Candidate Profile:
We are looking for a candidate with an MSc degree, or equivalent
(expected graduates are also welcome to apply). We are seeking a
candidate with a strong background and interest in (applied)
mathematics and/or systems and control theory. The candidate is
expected to be involved in fundamental research and in applications at
the boundary of several research domains. A good command of the English
language is also required.

Further Information and Application Process:
Please contact Dr. Alessandro Abate (email: a.abate@tudelft.nl This
e-mail address is being protected from spambots. You need JavaScript
enabled to view it).

More information on this position can be obtained at:
http://www.dcsc.tudelft.nl/~aabate

Contributed by: Jan Lunze <Lunze@atp.rub.de>

HANDBOOK OF HYBRID SYSTEMS CONTROL

J. Lunze, F. Lamnabhi-Lagarrigue (Eds.)
Combridge University Press, 2009
ISBN 9780521765053
www.atp.rub.de/Books

Hybrid systems are dynamical systems that consist of components
with continuous and discrete behavior. Modeling, analysis and
design of such systems raise severe methodological questions,
because they necessitate to combine continuous-variable
system descriptions like differential and difference equations
with discrete-event models like automata or Petri nets.
Consequently, hybrid systems methodology is based on principles
and results of the theories of continuous and discrete systems,
which, until recently, have been elaborated separately with contributions
coming from the different disciplines like control
theory, computer science, and mathematics.

This handbook reviews the new phenomena and theoretical problems
brought about by the combination of continuous and discrete
dynamics and surveys the main approaches, methods and results that
have been obtained during the last decade of research in this
field.

TABLE OF CONTENTS

PART I: Theory
1. Introduction
2. Survey of modeling, analysis and control of hybrid systems
3. Hybrid automata
4. Switched and piecewise affine systems
5. Further switched systems
6. Hybrid systems: quantization and abstraction
7. Stochastic hybrid systems

PART II: Tools
8. Overview
9. Verification tools for linear hybrid systems
10. Tools for modeling, simulation, control and verification
11. Modeling, simulation and optimization environments
12. Interchange formats and tool integration

PART III: Applications
13. Energy management
14. Inidustrial controls
15. Automotive control
16. Networked control
17. Solar air conditions - a benchmark for hybrid systems control

Contributed by: Ryan Leduc <leduc aT mcmasterDot cA>

DISCRETE-EVENT MODELING AND SIMULATION: A PRACTITIONER'S APPROACH

Gabriel A. Wainer
CRC, 2009
ISBN 1420053361
http://www.sce.carleton.ca/faculty/wainer/index.html

Discrete Event Modeling and Simulation presents a practical approach
focused on the creation of discrete-event applications. The book
introduces the CD++ tool, an open-source framework that enables the
simulation of discrete-event models. After setting up the basic theory
of DEVS and Cell-DEVS, the author focuses on how to use the CD++ tool
to define a variety of models in biology, physics, chemistry, and
artificial systems. They also demonstrate how to map different modeling
techniques, such as Finite State Machines and VHDL, to DEVS. The
in-depth coverage elaborates on the creation of simulation software for
DEVS models and the 3D visualization environments associated with these
tools.

Contributed by: Joerg Raisch <raisch_att_controlDOTtuDASHberlin__DOTde>

IFAC WORKSHOP ON DISCRETE EVENT SYSTEMS (WODES 2010)
Berlin, Germany
August 30 - September 1, 2010

The 10th International Workshop on Discrete Event Systems (WODES 2010)
will be held on the campus of TU Berlin, August 30 - September 1,
2010.

The Workshop Series on Discrete Event Systems started in 1992. Since
then, workshops have been held every two years: in Prague (1992),
Antibes (1994), Edinburgh (1996), Cagliari (1998), Ghent (2000),
Zaragoza (2002), Reims (2004), Ann Arbor, Michigan (2006) and
Gothenborg (2008).

WODES 2010 will provide researchers from different fields (control
theoreticians and control engineers, software engineers and
computer scientists, operations research specialists) with an
opportunity to exchange information and new ideas, and to discuss
new developments in the field of DES theory and applications.

The workshop is intended to cover all topics in discrete event theory
and applications, including (but not limited to) the following:

* Formalisms and modelling methodologies: Petri nets, automata,
  statecharts, process algebras, max-plus algebra...

* Control of discrete-event systems with emphasis on supervisory
   control and on real time control

* Performance evaluation, diagnosis, optimisation, implementation and
   scheduling
* Discrete approaches for hybrid systems
* Applications including manufacturing systems, transportation
  systems, process control, distributed systems, telecommunication
  systems, software engineering, office automation, workflow,
  protocols...

Prospective authors are invited to submit full papers and proposals
for special sessions by March 31, 2010. The Proceedings of
WODES 2010 will be hosted on-line on the IFAC-PapersOnLine website.

web site: click here

Contributed by: Ryan Leduc <leduc aT mcmasterDot cA>

IEEE INTERNATIONAL CONFERENCE ON ROBOTICS, AUTOMATION AND MECHATRONICS
Kuala Lumpur, Malaysia
June 7 - 9, 2010

OBJECTIVES:  The goal of the RAM 2010 is to bring together experts from
the field of robotics, automation and mechatronics to discuss
on the state-of-the-art and to present new research findings and
perspectives of future developments with respect to the conference
themes. The RAM 2010 is held in conjunction with the IEEE International
Conference on Cybernetics and Intelligent Systems (CIS 2010).

The conference welcomes paper submissions from academics, researchers,
engineers, and students worldwide in but not limited to the
following areas:

Robotics and Automation in Unstructured Environment, Personal and
Service Robotics, Underwater Robotics, Medical Robots and Systems,
Robotics and Automation Applications, Sensor Design, Integration, and
Fusion, Computer and Robot Vision, Human-Robot Interfaces,
Haptics, Teleoperation, Telerobotics, and Network Robotics, Micro/Nano,
Distributed, Cellular, and Multi Robots, Biologically-Inspired Robots
and Systems, Sensor Based Robotics, Intelligent Transportation Systems,
Modeling, Planning and Control, Kinematics, Mechanics, and Mechanism
Design, Legged Robots, Wheeled Mobile Robots, Dynamics, Motion Control,
Force/Impedance Control, Architecture and Programming, Methodologies
for Robotics and Automation, Discrete Event Dynamic Systems, Petri
Nets, Virtual Reality, Manufacturing System Architecture, Design, and
Performance Evaluation, Computer Aided Production Planning, Scheduling,
and Control, Total Quality Management, Maintenance, and Diagnostics,
etc.
  
About Kuala Lumpur, Malaysia A delightful mix of cross-cultural
influences and traditions, Kuala Lumpur radiates an exciting, enticing
charm, which will no doubt pique your interest throughout your stay.
Kuala Lumpur, affectionately known as KL, is an amazing cultural
melting pot. Here, you will wander through communities of Chinese,
Malays, South Indians, East Malaysian ethnic groups, Thais,
Indonesians, Sikhs and a huge community of expats. Each community while
influencing each other's culture, offers its own festivals, food,
music, art and fashion. KL has a lively nightlife scene and a
fascinating art and performance culture, which blends contemporary and
traditional styles from many backgrounds. More detailed information is
available on the following website:
http://www.tourism.gov.my/en/destinations/state.asp?state=kl.

Invited Sessions:
The conference will feature invited sessions on specialized topics of
interests. The invited sessions are intended to usher in,
in-depth discussions in special areas relevant to the conference theme.
The session organizers will coordinate the associated review
process. The conference proceedings will include all papers from the
invited sessions.

Paper Submission: Papers must be written in English and should describe
original work. Papers should be submitted in the.PDF format to
http:// www.cis-ram.org/2010/onl-pap.html by January 15, 2010. The
length of the paper is limited to a maximum of 6 pages (US letter
size, single spacing, Times Roman of font size 10, double columns
format), including figures, tables and references. Upon acceptance,
authors will be required to register and present their papers. Papers
will be published in the conference proceedings only if at least
one of the authors is officially registered. All the papers in the
conference proceedings will be indexed in the IEEE Library, ISI
Proceedings, and EI Compendex database.

Important Deadlines:

Conference / Invited Session Paper Submission: 15 January 2010
Notification of Acceptance: 1 March 2010
Final Camera-Ready Manuscript: 1 April 2010

web site: click here

Contributed by: Ryan Leduc <leduc aT mcmasterDot cA>

SELECTIONS FROM AUTOMATICA
VOLUME 45, ISSUE 11
NOVEMBER, 2009

1) On-line fault detection in discrete event systems by Petri nets and
integer linear programming

Mariagrazia Dotoli, Maria Pia Fanti, Agostino Marcello Mangini, Walter
Ukovich

Abstract: 

The paper addresses the fault detection problem for discrete event
systems in a Petri Net (PN) framework. Assuming that the structure of
the PN model and the initial marking are known, faults are modelled by
unobservable transitions. Moreover, we assume that there may be
additional unobservable transitions associated with the system legal
behaviour and that the marking reached after the firing of any
transition is unknown. The proposed diagnoser works on-line: it waits
for the firing of an observable transition and employs an algorithm
based on the definition and solution of some integer linear programming
problems to decide whether the system behaviour is normal or exhibits
some possible faults. The results characterize the properties that the
PN modelling the system fault behaviour has to fulfill in order to
reduce the on-line computational effort.

web site: click here

Contributed by: Ryan Leduc <leduc aT mcmasterDot cA>

SELECTIONS FROM IEEE TRANSACTIONS ON SYSTEMS, MAN AND CYBERNETICS, PART
A: SYSTEMS AND HUMANS
VOLUME: 39, ISSUE: 6
NOVEMBER, 2009

1) Supervisor Synthesis for Enforcing a Class of Generalized Mutual
Exclusion Constraints on Petri Nets

Jiliang Luo; Weimin Wu; Hongye Su; Jian Chu

Abstract: 

The considered class of generalized mutual exclusion constraints
(GMECs) on a controlled Petri net are such that the
influence-uncontrollable subnets are forward-concurrent-free nets. Some
structural properties of forward-concurrent-free nets are firstly
proposed. Utilizing these properties, a method is then proposed to
transform a given conjunction of GMECs into a conjunction of admissible
GMECs. Furthermore, the necessary and sufficient condition of the
existence of the permissive supervisor is obtained, and the optimal
supervisor with a complexity of polynomial time is designed. The
theoretic results are illustrated by an example that synthesizes a
maximally permissive supervisor for a manufacturing system.

2) Comment on "On Siphon Computation for Deadlock Control in a Class of
Petri Nets"

Huixia Liu; Keyi Xing; Song Gao

Abstract:

It was claimed recently in the paper by Li and Zhou that ldquoa
polynomial time algorithm for finding the set of elementary siphons in
S3PRs is proposed, which avoids complete siphon enumerationrdquo.
However, this is incorrect because Proposition 1 and Corollary 6 of the
aforementioned paper, which lead to the claim, are both incorrect. In
this correspondence paper, Proposition 1 and Corollary 6 are disproved.
As a consequence, some claims of the aforesaid paper are denied. Two
examples are presented to disprove some claims of the previously
mentioned paper.

web site: click here

Contributed by: Ryan Leduc <leduc aT mcmasterDot cA>

DISCRETE EVENT DYNAMIC SYSTEMS
VOLUME 19 NUMBER 4
NOVEMBER, 2009

1) Prognosis of w-Languages for the Diagnosis of *-Languages: A
Topological Perspective

Andreas Bauer and Sophie Pinchinat  

Abstract: 

This article offers a novel perspective on the diagnosis of *-languages
via a topological characterization of w-languages. This allows for the
different concepts that currently exist in diagnosis of discrete-event
systems to be related to one another in a uniform setting and to study
their complexity. For this purpose, we introduce the notion of
prognosability of an w-language, which in the classical setting
corresponds to testing if a language is diagnosable and prediagnosable.
We show that we can build a prognoser for some w-language if this
language is open and saturated, where openness is usually implied in
the finitary setting. For both of these problems we present PSPACE
algorithms, and establish that prognosability (i.e., whether or not a
prognoser exists) for an w-language is a PSPACE-complete problem. Our
new characterization offers a novel point of view in the classical
setting of diagnosis.

2) Discrete Semantics for Hybrid Automata - 
Avoiding Misleading Assumptions in Systems Biology 

Alberto Casagrande, Carla Piazza and Alberto Policriti  

Abstract: 

Many natural systems exhibit a hybrid behavior characterized by a set
of continuous laws which are switched by discrete events. Such
behaviors can be described in a very natural way by a class of automata
called hybrid automata. Their evolution are represented by both
dynamical systems on dense domains and discrete transitions. Once a
real system is modeled in a such framework, one may want to analyze it
by applying automatic techniques, such as Model Checking or Abstract
Interpretation. Unfortunately, the discrete/continuous evolutions not
only provide hybrid automata of great flexibility, but they are also at
the root of many undecidability phenomena. This paper addresses issues
regarding the decidability of the reachability problem for hybrid
automata (i.e., "can the system reach a state a from a state b") by
proposing an "inaccurate" semantics. In particular, after observing
that dense sets are often abstractions of real world domains, we
suggest, especially in the context of biological simulation, to avoid
the ability of distinguishing between values whose distance is less
than a fixed epsilon. On the ground of the above considerations, we propose a
new semantics for first-order formulae which guarantees the
decidability of reachability. We conclude providing a paradigmatic
biological example showing that the new semantics mimics the real world
behavior better than the precise one.

3) SAT-Solving in Practice, with a Tutorial Example from Supervisory
Control

 Koen Claessen, Niklas Een, Mary Sheeran, Niklas Sorensson, Alexey
Voronov and Knut Akesson  

Abstract:

Satisfiability solving, the problem of deciding whether the variables
of a propositional formula can be assigned in such a way that the
formula evaluates to true, is one of the classic problems in computer
science. It is of theoretical interest because it is the canonical
NP-complete problem. It is of practical interest because modern
SAT-solvers can be used to solve many important and practical problems.
In this tutorial paper, we show briefly how such SAT-solvers are
implemented, and point to some typical applications of them. Our aim is
to provide sufficient information (much of it through the reference
list) to kick-start researchers from new fields wishing to apply
SAT-solvers to their problems. Supervisory control theory originated
within the control community and is a framework for reasoning about a
plant to be controlled and a specification that the closed-loop system
must fulfil. This paper aims to bridge the gap between the computer
science community and the control community by illustrating how
SAT-based techniques can be used to solve some supervisory control
related problems.

4) Supervisory Control of (max,+) Automata: A Behavioral Approach

Jan Komenda, Sebastien Lahaye and Jean-Louis Boimond

Abstract:

   A behavioral framework for control of (max,+) automata is proposed.
It is based on behaviors (formal power series) and a generalized
version of the Hadamard product, which is the behavior of a generalized
tensor product of the plant and controller (max,+) automata in their
linear representations. In the tensor product and the Hadamard product,
the uncontrollable events that can neither be disabled nor delayed are
distinguished. Supervisory control of (max,+) automata is then studied
using residuation theory applied to our generalization of the Hadamard
product of formal power series. This yields a notion of controllability
of formal power series as well as (max,+)-counterparts of supremal
controllable languages. Finally, rationality as an equivalent condition
to realizability of the resulting controller series is discussed
together with hints on future use of this approach.

5) Fault Diagnosis in Discrete Event Systems Modeled by Partially
Observed Petri Nets

Yu Ru and Christoforos N. Hadjicostis

Abstract:   In this paper, we study fault diagnosis in discrete event
systems modeled by partially observed Petri nets, i.e., Petri nets
equipped with sensors that allow observation of the number of tokens in
some of the places and/or partial observation of the firing of some of
the transitions. We assume that the Petri net model is accompanied by a
(possibly implicit) description of the likelihood of each firing
sequence. Faults are modeled as unobservable transitions and are
divided into different types. Given an ordered sequence of observations
from place and transition sensors, our goal is to calculate the belief
(namely, the degree of confidence) regarding the occurrence of faults
belonging to each type. To handle information from transition and place
sensors in a unified manner, we transform a given partially observed
Petri net into an equivalent (as far as state estimation and fault
diagnosis is concerned) labeled Petri net (i.e., a Petri net with only
transition sensors), and construct a translator that translates the
sensing information from place and transition sensors into a sequence
of labels in the equivalent labeled Petri net. Once this transformation
is established, we focus on the computation of beliefs on faults in a
given labeled Petri net and construct an online monitor that
recursively produces these beliefs by tracking the existence of faulty
transitions in execution paths that match the sequence of labels
observed so far. Using the transformed labeled Petri net and the
translated observation sequence, we can then compute the belief for
each fault type in partially observed Petri nets in the same way as in
labeled Petri nets.

web site: click here