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. Conferences
 2.1 Allerton Conference on Communication, Control, and Computing,
     Allerton House, Illinois, September 30 - October 2, 2009
 2.2 PETRI NETS 2009, PARIS, FRANCE, June 22 - 26, 2009

3. Journals
 3.1 Selections from International Journal of Control, Volume 82 Issue
     5, May 2009
 3.2 Selections from IEEE Transactions on Automatic Control, Volume: 54,
      Issue: 3, March 2009
 3.3 Selections from IEEE Transactions on Automatic Control, Volume: 54,
      Issue: 4, April 2009
 3.4 Selections from  IEEE Transactions on Software Engineering, Volume:
     35,  Issue: 2, March 2009
 3.5 Selections from Control Engineering Practice, Volume 17, Issue 5,
     May 2009
 3.6 Selections from IEEE Transactions on Automation Science and
     Engineering, Volume: 6, Issue: 2, April 2009
 3.7 Discrete Event Dynamic Systems, Volume 19, Number 2, June 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:

Welcome to the April 2009 edition of the DESTC newsletter,

Ryan

Contributed by: Ryan Leduc <leduc AT mcmaster dOt ca>

ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING
Allerton House, Illinois
September 30 - October 2, 2009

The Forty-Seventh Annual Allerton Conference on
Communication, Control, and Computing will be held
from Wednesday, September 30 through Friday, October
2, 2009, at Allerton House, the conference center of the
University of Illinois. Allerton House is located twentysix
miles southwest of the Urbana-Champaign campus of
the University in a wooded area on the Sangamon River.
It is part of the fifteen-hundred acre Robert Allerton Park,
a complex of natural and man-made beauty designated as
a National natural landmark. Allerton Park has twenty
miles of well-maintained trails and a living gallery of
formal gardens, studded with sculptures collected from
around the world.

Papers presenting original research are solicited in the
areas of communication systems, communication and
computer networks, detection and estimation theory,
information theory, error control coding, source coding
and data compression, queueing networks, control
systems, robust and nonlinear control, adaptive control,
optimization, dynamic games, large-scale systems,
robotics and automation, manufacturing systems, discrete
event systems, intelligent control, multivariable control,
computer vision-based control, learning theory, neural
networks, VLSI architectures for communications and
signal processing, and automated highway systems.

Information for authors: Regular papers suitable for
presentation in twenty minutes are solicited. Regular
papers will be published in full (subject to a maximum
length of eight 8.5" x 11" pages, in two column format) in
the Conference Proceedings.

For reviewing purposes of papers, a title and a five to ten
page extended abstract, including references and
sufficient detail to permit careful reviewing, are required.
Manuscripts must be submitted by Wednesday, July 1,
2009, following the instructions at the Conference
website: http://www.csl.uiuc.edu/allerton/.
Authors will be notified of acceptance via e-mail by
August 4, 2009, at which time they will also be sent
detailed instructions for the preparation of their papers for
the Proceedings.

Final versions of papers to be presented at the
conference must be submitted electronically prior to
the end of the Conference.

web site: click here

Contributed by: Ryan Leduc <leduc AT mcmaster dOt ca>

PETRI NETS 2009
PARIS, FRANCE
June 22 - 26, 2009

The 30th International Conference on Application and Theory of Petri
Nets and Other Models of Concurrency tutorials and associated workshops
are organized by the MeFoSyLoMa group that involves:

    * Universite P. & M. Curie - LIP6 (main organizer),
    * Conservatoire National des arts et metiers - Cedric,
    * Ecole Normale Superieure de Cachan - LSV,
    * Universite d'Evry Val d'Essone - IBISC,
    * Universite Paris Dauphine - LAMSADE,
    * Universite Paris 12 - LACL,
    * Universite Paris 13 - LIPN,
    * Telecom ParisTech - LTCI.

It will take place in the campus of Universite P. & M. Curie in Paris.
The language of the conference is english. In 2009, this event is
co-located with the 20th Rapid System Prototyping Symposium.

Important Dates

    * Submission of Papers: January 5, 2009 January 10, 2009
    * Notification: March 1, 2009
    * Final Version (camera-ready) Due: April 1, 2009
    * Workshops & Tutorials: June 22-23, 2009
    * Conference: June 24-26, 2009

web site: click here

Contributed by: Ryan Leduc <leduc AT mcmaster dOt ca>

SELECTIONS FROM INTERNATIONAL JOURNAL OF CONTROL
VOLUME 82 ISSUE 5
MAY, 2009

1) Hierarchical interface-based supervisory control with data events

Ryan J. Leduc

Abstract: 

Hierarchical interface-based supervisory control (HISC) decomposes a
discrete-event system into a high-level subsystem, which communicates
with n >= 1 low-level subsystems, through separate interfaces that
restrict the interaction of the subsystems. It provides a set of local
conditions that can be used to verify global conditions such as
nonblocking and controllability. As each clause of the definition can
be verified using a single subsystem, the complete system model never
needs to be stored in memory or traversed, offering potentially
significant savings in computational resources.

In this article, we extend the range of the behaviour of low-levels
that interfaces can model by adding a new type of event, low data
events and by relaxing some restrictions in the HISC definitions. This
allows us to (i) request events that do not need to be followed by an
answer event, (ii) start a low-level on a task and then poll it for
completion, (iii) be able to send additional commands while a low-level
is already processing a command (iv) model low-levels that behave as
buffers and (v) allow unsolicited information (status, etc.) to be sent
up from a low-level.

Besides greatly enriching the behaviour that can be modelled as
interfaces and thus expanding the systems that HISC can effectively be
applied to, the changes can enable behaviour to be moved from the
high-level to the low-levels. We demonstrate this when we discuss the
application of our method to a large manufacturing system example based
upon the AIP example, where we saw a 3.4 times reduction in computation
time and a 6.5 times reduction in memory use. This helps prevent the
high-level from growing too large, allowing the HISC method to apply to
larger systems.

web site: click here

Contributed by: Ryan Leduc <leduc AT mcmaster dOt ca>

SELECTIONS FROM IEEE TRANSACTIONS ON AUTOMATIC CONTROL
VOLUME: 54, ISSUE: 3
MARCH, 2009

1) On Solvability of a Decentralized Supervisory Control Problem With
Communication

Hiraishi, K.

Abstract: 

We study a decentralized control problem of discrete event systems with
communication. We first give a general automata-theoretic formalism
that enables us to handle various types of communication, including
delay. The decentralized control problem is shown to be undecidable
under this formalism. Next we propose a semi-decision procedure for
computing finite-state controllers to achieve a given specification in
the sense of bisimilarity between the controlled system and a given
specification. Using this procedure, we prove decidability of the
problem for two special cases, one is the case in which the
communication behavior is given as k -bounded-delay communication, and
the other is the case in which any cycle in the state transition
diagram of the system contains an event observable by all controllers.
We also show a method for optimizing controllers based on a graph problem.

web site: click here

Contributed by: Ryan Leduc <leduc AT mcmaster dOt ca>

SELECTIONS FROM IEEE TRANSACTIONS ON AUTOMATIC CONTROL
VOLUME: 54, ISSUE: 4
APRIL, 2009

1) An Efficient Approach for Online Diagnosis of Discrete Event Systems

Basile, F.; Chiacchio, P.; De Tommasi, G.

Abstract: 

A novel approach to fault diagnosis of discrete event systems is
presented in this paper. The standard approach is based on the offline
computation of the set of fault events that may have occurred at each
reachable state, providing a fast online diagnosis at a price of
excessive memory requirements. A different approach is here adopted,
which is based on the online computation of the set of possible fault
events required to explain the last observed event. This is efficiently
achieved by modelling the plant by Petri nets, since their mathematical
representation permits to formulate the fault diagnosis problems in
terms of mathematical programming, which is a standard tool. Moreover,
the graphical representation of the net allows the diagnoser agent to
compute off-line reduced portions of the net in order to improve the
efficiency of the online computation, without a big increase in terms
of memory requirement.

2) Application of Reachability Analysis for Stochastic Hybrid Systems
to Aircraft Conflict Prediction

Prandini, M.; Hu, J.

Abstract:

Aircraft conflict prediction can be naturally formulated as a
reachability analysis problem in a stochastic hybrid system framework.
In this technical note, a switching diffusion model is adopted to
predict the future positions of an aircraft following a given flight
plan, and the probability that the aircraft will enter an unsafe region
of the airspace is estimated through a numerical algorithm for
reachability computations. Simulation results are reported to
illustrate the approach.

web site: click here

Contributed by: Ryan Leduc <leduc AT mcmaster dOt ca>

SELECTIONS FROM IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
VOLUME: 35, ISSUE: 2
MARCH, 2009

1) Automated Trace Analysis of Discrete-Event System Models

Peter Kemper and Carsten Tepper

Abstract: 

In this paper, we describe a novel technique that helps a modeler gain
insight into the dynamic behavior of a complex stochastic discrete
event simulation model based on trace analysis. We propose algorithms
to distinguish progressive from repetitive behavior in a trace and to
extract a minimal progressive fragment of a trace. The implied
combinatorial optimization problem for trace reduction is solved in
linear time with dynamic programming. We present and compare several
approximate and one exact solution method. Information on the reduction
operation as well as the reduced trace itself helps a modeler to
recognize the presence of certain errors and to identify their cause.
We track down a subtle modeling error in a dependability model of a
multi-class server system to illustrate the effectiveness of our
approach in revealing the cause of an observed effect. The proposed
technique has been implemented and integrated in Traviando, a trace
analyzer to debug stochastic simulation models.

2) Model Checking Probabilistic and Stochastic Extensions of the
pi-Calculus

Gethin Norman, Catuscia Palamidessi, David Parker, and Peng Wu

Abstract:

We present an implementation of model checking for probabilistic and
stochastic extensions of the pi-calculus, a process algebra which
supports modelling of concurrency and mobility. Formal verification
techniques for such extensions have clear applications in several
domains, including mobile ad-hoc network protocols, probabilistic
security protocols and biological pathways. Despite this, no
implementation of automated verification exists. Building upon the
pi-calculus model checker MMC, we first show an automated procedure
for
constructing the underlying semantic model of a probabilistic or
stochastic pi-calculus process. This can then be verified using
existing
probabilistic model checkers such as PRISM. Secondly, we demonstrate
how for processes of a specific structure a more efficient,
compositional approach is applicable, which uses our extension of MMC
on each parallel component of the system and then translates the
results into a high-level modular description for the PRISM tool. The
feasibility of our techniques is demonstrated through a number of case
studies from the pi-calculus literature.

3) Model Checking Timed and Stochastic Properties with CSL^{TA}

Susanna Donatelli, Serge Haddad, Jeremy Sproston

Abstract: 

Markov chains are a well-known stochastic process that provide a
balance between being able to adequately model the system's behavior
and being able to afford the cost of the model solution. The definition
of stochastic temporal logics like Continuous Stochastic Logic (CSL)
and its variant asCSL, and of their model-checking algorithms, allows a
unified approach to the verification of systems, allowing the mix of
performance evaluation and probabilistic verification. In this paper we
present the stochastic logic CSLTA, which is more expressive than CSL
and asCSL, and in which properties can be specified using automata
(more precisely, timed automata with a single clock). The extension
with respect to expressiveness allows the specification of properties
referring to the probability of a finite sequence of timed events. A
typical example is the responsiveness property "with probability at
least 0.75, a message sent at time 0 by a system A will be received
before time 5 by system B and the acknowledgment will be back at A
before time 7", a property that cannot be expressed in either CSL or
asCSL. We also present a model-checking algorithm for CSLTA.

4) Counterexample Generation in Probabilistic Model Checking

Tingting Han, Joost-Pieter Katoen, Damman Berteun

Abstract:

Providing evidence for the refutation of a property is an essential, if
not the most important, feature of model checking. This paper considers
algorithms for counterexample generation for probabilistic CTL formulae
in discrete-time Markov chains. Finding the strongest evidence (i.e.,
the most probable path) violating a (bounded) until-formula is shown to
be reducible to a single-source (hop-constrained) shortest path
problem. Counterexamples of smallest size that deviate most from the
required probability bound can be obtained by applying (small
amendments to) k-shortest (hop-constrained) paths algorithms. These
results can be extended to Markov chains with rewards, to LTL model
checking, and are useful for Markov decision processes. Experimental
results show that typically the size of a counterexample is excessive.
To obtain much more compact representations, we present a simple
algorithm to generate (minimal) regular expressions that can act as
counterexamples. The feasibility of our approach is illustrated by
means of two communication protocols: leader election in an anonymous
ring network and the Crowds protocol.

web site: click here

Contributed by: Ryan Leduc <leduc AT mcmaster dOt ca>

SELECTIONS FROM CONTROL ENGINEERING PRACTICE
VOLUME 17, ISSUE 5
MAY, 2009

1) Real-time scheduling method for networked discrete control systems

Dong-Sung Kim, Dong-Hyuk Choi, Prasant Mohapatra

Abstract: 

This paper proposes a new scheduling method to obtain a maximum
allowable delay bound for a scheduling of networked discrete control
systems. The proposed method is formulated in terms of linear matrix
inequalities (LMI) and can give a much less conservative delay bound
than the existing methods. An event based network scheduling method is
presented based on the delay bound obtained through the proposed
method, and it can adjust the sampling period to allocate identical
utilization to each control loop. The presented method can handle
sporadic emergency data, periodic data, and non-real-time data.

web site: click here

Contributed by: Ryan Leduc <leduc AT mcmaster dOt ca>

SELECTIONS FROM IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING
VOLUME: 6, ISSUE: 2
APRIL, 2009

1) Decentralized Diagnosis of Event-Driven Systems for Safely Reacting
to Failures

Qiu, W.; Wen, Q.; Kumar, R.

Abstract: 

 We introduce the notion of safe-codiagnosability, extending the notion
of safe-diagnosability (Paoli and Lafortune, 2005) to the decentralized
setting. For a system, a certain subbehavior is deemed safe (captured
via a safety specification), and a further subbehavior is deemed
nonfaulty (captured via a nonfault specification).
Safe-codiagnosability requires that when the system executes a trace
that is faulty, there exists at least one diagnoser that can detect
this within bounded delay and also before the safety specification is
violated. The above notion of safe-codiagnosability may also be viewed
as an extension of the notion of codiagnosability (Qiu and Kumar,
2006), where the latter did not have any safety requirement. We show
that safe-codiagnosability is equivalent to codiagnosability together
with "zero-delay codiagnosability" of "boundary safe
traces". (A safe
trace is a boundary safe trace if there exists a single-event extension
that is unsafe.) We give an algorithm of polynomial complexity for
verifying safe-codiagnosability. For a safe-codiagnosable system, the
same methods as those proposed in (Qiu and Kumar, 2006) can be applied
for offline synthesis of individual diagnosers, as well as for online
diagnosis using them.

2) Errata to "Petri Net-Based Method for Compatibility Analysis
and Composition of Web Services in Business Process Execution
Language" [Jan 09 94-106]

Tan, W.; Fan, Y.; Zhou, M.

web site: click here

Contributed by: Ryan Leduc <leduc AT mcmaster dOt ca>

DISCRETE EVENT DYNAMIC SYSTEMS
VOLUME 19, NUMBER 2
JUNE, 2009

1)  State Observer for DES Under Partial Observation with Time Petri
Nets

Mohamed Ghazel, Armand Toguyeni and Pascal Yim 

Abstract: 

This paper deals with a state observation approach for Discrete Event
Systems with a known behavior. The system behavior is modeled using a
Time Petri Net model. The proposed approach exploits temporal
constraints to assess the system state and therefore detect and
determine faults given partial observability of events. The goal here
is to track the system state and to identify the event scenarios which
occur on the system. Our approach uses the class graph of the Time
Petri Net which models the complete system behavior to develop a state
observer which is a base to perform online fault detection and
diagnosing.

2)  Event Counting of Partially-Observed Discrete-Event Systems with
Uniformly and Nonuniformly Bounded Diagnosis Delays

Tae-Sic Yoo and Humberto E. Garcia 

Abstract:

We present an approach dealing with repeated fault events in the
framework of model-based monitoring of discrete-event systems (DES).
Various notions of diagnosability reported in the literature deal with
uniformly bounded finite detection of counting delays over all faulty
behaviors (uniform delays for brevity). The situation where the
diagnosability notion of interest fails to hold under a given
observation configuration leads typically to the deployment of more
observational devices (e.g., sensors), which may be costly or
infeasible. As an alternative to the additional deployment of
observational devices, one might want to relax the uniformity of
delays, while delays remain finite. To this end, we introduce a notion
of diagnosability characterized with nonuniformly bounded finite
counting delays (nonuniform counting delays for brevity), where finite
delay bounds can vary on faulty behaviors. To evaluate the introduced
notion of diagnosability with nonuniform counting delays, a
polynomial-time verification algorithm is developed. Notably, the
developed verification technique can readily be modified to construct a
computationally superior verification algorithm for diagnosability
under uniformly bounded finite counting delays (uniform counting delays
for brevity) as compared to an algorithm previously reported in the
literature. We also develop a novel on-line event counting algorithm
that improves the time and space complexities of the currently
available algorithms for the counting of special events.

3)  Basic Server Semantics and Performance Monotonicity of Continuous
Petri Nets

Cristian Mahulea, Laura Recalde and Manuel Silva 

Abstract: 

Continuous Petri nets were introduced as an approximation to deal with
the state explosion problem which can appear in discrete event models.
When time is introduced, the flow through a fluidified transition can
be defined in many ways. The most used in literature are constant and
variable speed (David and Alla, Discrete, continuous and hybrid Petri
nets, Springer-Verlag, 2005), which can be seen as some kind of finite
and infinite server interpretations of the transitions behavior, and
derived from stochastic (discrete) Petri nets (Silva and Recalde, Annu
Rev Control 28(2):253-266, 2004). In this paper we will compare
the results obtained with both relaxations for the broad class of
mono-T-semiflow reducible nets, and prove that, under some frequently
true conditions, infinite server semantics offers a throughput which is
closer to the throughput of the discrete system in steady state. In the
second part, it will be proved that the throughput of mono-T-semiflow
reducible net systems is monotone with respect to the speed of the
transitions and the initial marking of the net.

4)  Control of Parameterized Discrete Event Systems

Hans Bherer, Jules Desharnais and Richard St-Denis 

Abstract:

This paper investigates the control of parameterized discrete event
systems when specifications are given in terms of predicates and
satisfy a similarity assumption. This study is motivated by a weakness
in current synthesis methods that do not scale well to huge systems.
For systems consisting of similar processes under total or partial
observation, conditions are given to deduce properties of a system of n
processes (arbitrary size) from properties of a system of n_o processes
(bounded size), with n>=n_o. Furthermore, it is shown
how to infer a control policy for the former from the latter's, while taking into
account interconnections between processes.

5)  A Subgradient Descent Algorithm for Optimization of Initially
Controllable Flow Shop Systems

Kagan Gokbayrak and Omer Selvi 

Abstract:

We consider an optimization problem for deterministic flow shop systems
processing identical jobs. The service times are initially
controllable; they can only be set before processing the first job, and
cannot be altered between processes. We derive some waiting and
completion time characteristics for fixed service time flow shop
systems, independent of the cost formulation. Exploiting these
characteristics, an equivalent convex optimization problem, which is
non-differentiable, is derived along with its subgradient descent
solution algorithm. This algorithm not only eliminates the need for
convex programming solvers but also allows for the solution of larger
systems due to its smaller memory requirements. Significant
improvements in solution times are also observed in the numerical
examples.

web site: click here