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 [CFP: Diagnosis and Prognosis of DES at the 48th IEEE CDC 2009]

3. Journals
 3.1 Selections from International Journal of Control, Volume 82, Issue
     2, February 2009
 3.2 Selections from Automatica,  Volume 45, Issue 2, February 2009
 3.3 Discrete Event Dynamic Systems, Volume 19 Number 1, March 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 February edition of the DESTC newsletter,

Ryan

Contributed by: Naly Rakoto <rakoto@emn.fr>

[CFP: DIAGNOSIS AND PROGNOSIS OF DES AT THE 48TH IEEE CDC 2009]

%----------------------------------------------------------------%
	 Special Session at the 48th IEEE CDC 2009
%----------------------------------------------------------------%
 Call for Papers: Special session on:

    "Diagnosis and Prognosis of Discrete Event Systems"

at the forthcoming 48th IEEE Conference on Decision and Control 
(CDC 2009) and Chinese Control Conference 2009. The aim of the 
special session is to present new results from both the theoretical 
and the application-oriented research field of Diagnosis and 
prognosis of Discrete Event Systems (DES). The general diagnosis
problem of DES deals with the detection or identification 
of particular events which are fully or partially unobservable. 
The topics of the special session include, but are not limited to:
- Failure diagnosis of DES
- Prognosis of DES
- Applications of Diagnosis and Prognosis of DES

The combined 48th IEEE Conference on Decision and Control and 
28th Chinese Control Conference will be held in Shanghai, China 
on December 16-19, 2009.
http://www.ieeecss.org/CAB/conferences/cdc2009/index.php

The deadline for submission of full papers is March 1, 2009,
through the paperplaza site.
https://css.paperplaza.net/conferences/scripts/start.pl

Instructions:
Interested contributors please e-mail your short summaries (paper
title, authors, abstract, and contact details) to  one of the
organizers below at your earliest convenience (but no later than 
Feb. 15, 2009).

Organizers:
Shigemasa Takai (Kyoto Institute of Technology, Japan, takai@kit.ac.jp)
Naly Rakoto (Ecole des Mines de Nantes, France, rakoto@emn.fr)

%------------------------------------------------------------------%

Contributed by: Ryan Leduc <Leduc aTt mcmaster dOT CA>

SELECTIONS FROM INTERNATIONAL JOURNAL OF CONTROL
VOLUME 82, ISSUE 2
FEBRUARY, 2009

1) Supervisory control for fault-tolerant scheduling of real-time
multiprocessor systems with aperiodic tasks 

Seong-Jin Park; Kwang-Hyun Cho

Abstract:

Supervisory control theory is a well-established theoretical framework
for feedback control of discrete event systems whose behaviours are
described by automata and formal languages. In this article, we propose
a formal constructive method for optimal fault-tolerant scheduling of
real-time multiprocessor systems based on supervisory control theory.
In particular, we consider a fault-tolerant and schedulable language
which is an achievable set of event sequences meeting given deadlines
of accepted aperiodic tasks in the presence of processor faults. Such a
language eventually provides information on whether a scheduler (i.e.,
supervisor) should accept or reject a newly arrived aperiodic task.
Moreover, we present a systematic way of computing a largest
fault-tolerant and schedulable language which is optimal in that it
contains all achievable deadline-meeting sequences.

web site: click here

Contributed by: Ryan Leduc <Leduc aTt mcmaster dOT CA>

SELECTIONS FROM AUTOMATICA
VOLUME 45, ISSUE 2
FEBRUARY, 2009

1) Predictability of event occurrences in partially-observed
discrete-event systems

Sahika Genc, Stephane Lafortune

Abstract:

This paper studies the problem of predicting occurrences of a
significant event in a partially-observed discrete-event system. The
predictability of occurrences of an event in a system is defined in the
context of formal languages. The predictability of a language is a
stronger condition than the diagnosability of the language. Two
necessary and sufficient conditions for predictability of occurrences
of an event in systems modeled by regular languages are presented. Both
conditions can be algorithmically tested. The first condition employs
diagnosers. The second condition employs verifiers and results in a
polynomial-time (in the number of states) complexity test for
verification of predictability. When predictability holds, diagnosers
can be used online to predict the significant event.

web site: click here

Contributed by: Ryan Leduc <Leduc aTt mcmaster dOT CA>

DISCRETE EVENT DYNAMIC SYSTEMS
VOLUME 19 NUMBER 1
MARCH, 2009

1) Closed-loop Live Marked Graphs under Generalized Mutual Exclusion
Constraint Enforcement

Francesco Basile, Laura Recalde, Pasquale Chiacchio and Manuel Silva

Abstract:

Enforcing a supervisory control policy to avoid forbidden states on a
discrete event system modeled by a Petri net may result in a non live
system. This may happen even if the admissible states are specified by
Generalized Mutual Exclusion Constraints (GMECs). This leads to the
problem of synthesizing a maximally permissive control policy
preserving liveness of the system under a GMEC. This problem is very
interesting in practice, but difficult even for a restricted class of
systems. In this paper, we focus on systems which can be modeled as
live and safe Marked Graphs (MGs). On such systems, when some of the
transitions are uncontrollable, a GMEC can be forced by a monitor place
if a not maximally permissive policy is accepted, otherwise a more
complex control has to be adopted. Anyway, liveness of the closed-loop
system (plant plus control) is not guaranteed. Two sufficient
conditions to verify the closed-loop liveness of a live and safe MG
plant controlled by a monitor are derived. A sufficient condition for
closed loop liveness of MGs where a GMEC has been enforced on is
derived. In addition, a set of predicates is provided that enforces, in
a maximally permissive way, a GMEC while preserving closed-loop
liveness on live and safe MG systems under some restrictions.

2) A Multi-Component General Discrete System Subject to Different Types
of Failures with Loss of Units

 Juan Eloy Ruiz-Castro, Gemma Fernandez-Villodre and Rafael Perez-Ocon 


Abstract:

Discrete systems are used in several fields such as reliability and
computing and electronics in digital systems. On the other hand, there
are systems that cannot be continuously monitored and they can be
observed only at certain periods of time, via inspections, for example.
In this paper a repairable multi-component system subject to internal
and accidental external failures with loss of units is developed. The
system is composed of a finite number of units, including the main one
and the others disposed in cold standby. If a repairable failure
occurs, the main unit enters the repair channel. On the other hand, the
unit is removed if the failure is non-repairable. A repairman is
considered. The distribution of the lifetime of the main unit is a
general one and its phase-type representation is considered. Accidental
failures occur according to a general discrete renewal process. The
model is developed in detail and the up period is worked out up to no
units and up to total failure of the system. Some reliability measures
of interest such as the conditional probability of different types of
failures are calculated. The operating of the system is analysed
according to rewards introduced in the model. We have built complex
algorithms for calculating the measures defined in this paper. We have
introduced the RG-factorization method to work out these measures by
means of matrices with low order. The results have been implemented
computationally with Matlab. An example illustrates the model and the
number of units is optimised according to the average net reward.

3) Optimal Control of Discrete Event Systems with Weakly Hard Real-Time
Constraints 

Shixin Zhuang and Christos G. Cassandras

Abstract:

We consider Discrete Event Systems that can dynamically allocate
resources in order to process tasks with real-time constraints. In the
case of "weakly hard" constraints, a fraction of tasks is allowed to
violate them, as long as m out of any k consecutive tasks meet their
respective constraints. This is a generalization of a system with
purely hard real-time constraints where m = k = 1. For non-preemptive
and aperiodic tasks, we formulate an optimization problem where task
processing times are controlled so as to minimize a cost function while
guaranteeing that a "weakly hard" criterion is satisfied. We establish
a number of structural properties of the solution to this problem which
lead to an efficient algorithm that does not require any explicit
nonlinear programming problem solver. The low complexity of this
algorithm makes it suitable for on-line applications. Simulation
examples illustrate the performance improvements in such optimally
controlled systems compared to ad hoc schemes.

4) A New Learning Algorithm for Optimal Stopping

Vivek S. Borkar, Jervis Pinto and Tarun Prabhu	

Abstract:

A linear programming formulation of the optimal stopping problem for
Markov decision processes is approximated using linear function
approximation. Using this formulation, a reinforcement learning scheme
based on a primal-dual method and incorporating a sampling device
called 'split sampling' is proposed and analyzed. An illustrative
example from option pricing is also included.

5) Semi-linear Stochastic Difference Equations

Eitan Altman

Abstract:

We consider in this paper a class of vector valued processes that have
the form Y_n+1 =A_n (Y_n) + B_n.  B_n	is assumed
to be stationary ergodic and A_n  is assumed to have a divisibility
property. This class includes linear stochastic difference equations as
well as multi-type branching processes (with a discrete or with a
continuous state space). We derive explicit expressions for the
probability distribution as well as for the two first moments of state
vectors at the stationary regime. We then apply this approach to derive
two formalisms to describe the infinite server queue. The first is
based on a branching process approach adapted to phase type service
time distributions. The second is based on a linear stochastic
difference equation and is adapted to independent and generally
distributed service times with bounded support. In both cases we allow
for generally distributed arrival process (not necessarily i.i.d. nor
Markovian).

web site: click here