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. Journals
 2.1 Selections from IEEE Transactions on Automatic Control, Volume: 54,
      Issue: 7, July 2009
 2.2 Selections from IEEE Transactions on Systems, Man and Cybernetics, Part
     A: Systems and Humans, Volume: 39, Issue: 4, July 2009
 2.3 Discrete Event Dynamic Systems, Volume 19, Number 3, September 2009
 2.4 Selections from IEEE Transactions on Automation Science and
     Engineering, Volume: 6, Issue: 3, July 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:

Welecome to the July, 2009 newsletter,

Ryan

Contributed by: Ryan Leduc <leduc aT mcmaster DOT ca>

SELECTIONS FROM IEEE TRANSACTIONS ON AUTOMATIC CONTROL
VOLUME: 54, ISSUE: 7
JULY, 2009

1) Synthesis Method for Hierarchical Interface-Based Supervisory Control

Leduc, R. J.; Dai, P.; Song, R.

Abstract: 

  Hierarchical Interface-Based Supervisory Control (HISC) decomposes a
discrete-event system (DES) into a high-level subsystem which
communicates with n >= 1 low-level subsystems, through separate
interfaces. 

  It provides a set of local conditions that can be used to verify
global conditions such as nonblocking and controllability such that the
complete system model never needs to be constructed.

  Currently, a designer must create the supervisors himself and then
verify that they satisfy the HISC conditions.  In this paper, we 
develop a synthesis method that  can take advantage of the HISC 
structure. We replace the supervisor for each level by a corresponding
specification DES.  We  then construct for each level  a maximally
permissive supervisor that satisfies the corresponding HISC conditions.
However, the method does not guarantee global maximal permissiveness,
only  level-wise maximal permissiveness.

  We define a set of language-based fixpoint operators and show that
they compute the required level-wise supremal languages. We then
discuss the complexity of our algorithms and  show that they
potentially offer significant savings over  the monolithic approach. We
also briefly discuss a symbolic HISC verification and synthesis method
using Binary Decision Diagrams, that we have also developed.  

  A large manufacturing system example (worst-case statespace on the
order of 10^30) extended from the AIP example is briefly discussed. The
example showed that  we can now handle  a given level with a statespace
as large as 10^15 states, using less than 160MB of memory. This
represents a significant improvement in the size of systems that can be
handled by the HISC approach. A software tool for synthesis and
verification of HISC systems using our approach was also developed.

web site: click here

Contributed by: Ryan Leduc <leduc aT mcmaster dOT cA>

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

1) An Effective Algorithm to Find Elementary Siphons in a Class of
Petri Nets  

AnRong Wang; ZhiWu Li; JianYuan Jia; MengChu Zhou

Abstract: 

As a structural object of Petri nets, siphons play a key role in the
development of deadlock prevention policies for resource allocation
systems. Elementary siphons are a novel concept in net theory. Based on
graph theory, this paper proposes an effective algorithm with
polynomial complexity to find a set of elementary siphons for a linear
system of simple sequential processes with resources (LS3 PR), a
subclass of Petri nets, which can model many flexible manufacturing
systems. The algorithm is established through the use of a resource
directed graph and complementary sets of strict minimal siphons (SMS)
of the net. The upper bound of the number of SMS in such a net is
identified. A running example is used to demonstrate the proposed method.

2)  Soundness for $S$- and $A$-Timed Workflow Nets Is Undecidable

Tiplea, F.L.   Macovei, G.I.  

Abstract: 

The main purpose of workflow management systems is to support the
definition, execution, and control of workflow processes. With or
without time constraints, workflow management systems should satisfy
certain correctness properties. The most important and widely used is
the soundness property . In this paper, we focus on the soundness
property for two classes of Petri-net-based workflow management systems
with time constraints, S- and A-timed workflow nets (WNs), and we show
that this property is undecidable for them. The proof technique, based
on the undecidability of the halting problem for deterministic counter
machines, shows first that the reachability, coverability, boundedness,
and quasi-liveness problems are undecidable for these two classes of
timed WNs, and then, as a consequence, the undecidability of the
soundness problem is derived.

web site: click here

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

DISCRETE EVENT DYNAMIC SYSTEMS
VOLUME 19, NUMBER 3
SEPTEMBER, 2009

1) Time-Optimal Coordination of Flexible Manufacturing Systems Using
Deterministic Finite Automata and Mixed Integer Linear Programming

Avenir Kobetski, Martin Fabian
 
Abstract:

Automation and flexibility are often mentioned as key concepts in
modern production industry. To increase the level of flexibility,
deterministic finite automata (DFA) can be used to model, specify and
verify the production systems. Often, it is also desirable to optimize
some production criteria, such as for example the cycle time of a
manufacturing cell. In this paper, a method for automatic conversion
from DFA to a mixed integer linear programming (MILP) formulation is
first presented. This conversion is developed for a number of DFA
structures that have shown to be useful in practical applications.
Special attention is paid to reducing the search region explored by the
MILP solver. Second, a conversion from the MILP solution to a DFA
supervisor is described. This allows to combine the advantages of DFA
modeling with the efficiency of MILP and supervisory control theory to
automatically generate time-optimal, collision-free and non-blocking
working schedules for flexible manufacturing systems.

2) Ordinal Optimization and Quantification of Heuristic Designs

Zhen Shen, Yu-Chi Ho, Qian-Chuan Zhao

Abstract:

This paper focuses on the performance evaluation of complex man-made
systems, such as assembly lines, electric power grid, traffic systems,
and various paper processing bureaucracies, etc. For such problems,
applying the traditional optimization tool of mathematical programming
and gradient descent procedures of continuous variables optimization
are often inappropriate or infeasible, as the design variables are
usually discrete and the accurate evaluation of the system performance
via a simulation model can take too much calculation. General search
type and heuristic methods are the only two methods to tackle the
problems. However, the "goodness+ of heuristic methods is generally
difficult to quantify while search methods often involve extensive
evaluation of systems at many design choices in a large search space
using a simulation model resulting in an infeasible computation burden.
The purpose of this paper is to address these difficulties
simultaneously by extending the recently developed methodology of
Ordinal Optimization (OO). Uniform samples are taken out from the whole
search space and evaluated with a crude but computationally easy model
when applying OO. And, we argue, after ordering via the crude
performance estimates, that the lined-up uniform samples can be seen as
an approximate ruler. By comparing the heuristic design with such a
ruler, we can quantify the heuristic design, just as we measure the
length of an object with a ruler. In a previous paper we showed how to
quantify a heuristic design for a special case but we did not have the
OO ruler idea at that time. In this paper we propose the OO ruler idea
and extend the quantifying method to the general case and the multiple
independent results case. Experimental results of applying the ruler
are also given to illustrate the utility of this approach.

3) Optimal Node Visitation in Acyclic Stochastic Digraphs with
Multi-threaded Traversals and Internal Visitation Requirements

Theologos Bountourelis, Spyros Reveliotis
 
Abstract: 

The original definition of the problem of optimal node visitation (ONV)
in acyclic stochastic digraphs concerns the identification of a routing
policy that will enable the visitation of each leaf node a requested
number of times, while minimizing the expected number of the graph
traversals. The original work of Bountourelis and Reveliotis (2006)
formulated this problem as a Stochastic Shortest Path (SSP) problem,
and since the state space of this SSP formulation is exponentially
sized with respect to the number of the target nodes, it also proposed
a suboptimal policy that is computationally tractable and
asymptotically optimal. This paper extends the results of Bountourelis
and Reveliotis (2006) to the cases where (i) the tokens traversing the
graph can "split" during certain transitions to a number of
(sub-)tokens, allowing, thus, the satisfaction of many visitation
requirements during a single graph traversal, and (ii) there are
additional visitation requirements attached to the internal graph
nodes, which, however, can be served only when the visitation
requirements of their successors have been fully met. In addition, the
presented set of results establishes stronger convergence properties
for the proposed suboptimal policies, and it provides a formal
complexity analysis of the considered ONV formulations. From a
practical standpoint, the extension of the original results performed
in this paper enables their effective usage in the application domains
that motivated the ONV problem, in the first place.

4) Partially Observable Markov Decision Process Approximations for
Adaptive Sensing

Edwin K. P. Chong, Christopher M. Kreucher, Alfred O. Hero

Abstract:

Adaptive sensing involves actively managing sensor resources to achieve
a sensing task, such as object detection, classification, and tracking,
and represents a promising direction for new applications of discrete
event system methods. We describe an approach to adaptive sensing based
on approximately solving a partially observable Markov decision process
(POMDP) formulation of the problem. Such approximations are necessary
because of the very large state space involved in practical adaptive
sensing problems, precluding exact computation of optimal solutions. We
review the theory of POMDPs and show how the theory applies to adaptive
sensing problems. We then describe a variety of approximation methods,
with examples to illustrate their application in adaptive sensing. The
examples also demonstrate the gains that are possible from nonmyopic
methods relative to myopic methods, and highlight some insights into
the dependence of such gains on the sensing resources and environment.

5) Optimal Control of Production Processes with Variable Execution Times

Davide Giglio, Riccardo Minciardi, Simona Sacone, Silvia Siri

Abstract:

The paper deals with the optimal control of production processes
characterized by the possibility of performing operations (relevant to
the processing of a set of jobs) with variable execution times. A
production process relevant to a single machine is addressed first. An
optimization problem with a quite general cost function is considered,
and some properties of optimal solutions are derived. Then, a
particular version of the problem is analyzed, in which the cost
function is the weighted sum of the quadratic earliness and tardiness
of jobs and of quadratic deviations between pre-defined nominal unitary
processing times and the actual ones. The decision variables of the
problem are the possible idle times inserted before job executions and
the processing times of jobs. This single machine problem is stated as
an optimal control problem and a closed-loop solution is derived. Then,
a second production process is considered, in which multiple machines
serve jobs in parallel, again with variable processing times and with
different processing costs. With reference to this second production
scheme, a significant decision problem refers to the splitting of jobs
over the different machines. Then, on the basis of a sensitivity
analysis of the single machine problem solution, some conditions to
verify the optimality of a pre-defined splitting are derived. An
on-line splitting scheme using such conditions is finally presented.

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: 3
JULY, 2009

1)  Reachability Graph of Finite and Deterministic DEVS Networks

 Hwang, M. H.   Zeigler, B. P.
 
Abstract:

This paper shows how to generate a finite-vertex graph, called a
reachability graph for discrete-event system specification (DEVS)
network. The reachability graph is isomorphic to a given original DEVS
network in terms of behavior but the number of vertices as well as the
number of edges of the reachability graph are finite.

2)  Inference-Based Ambiguity Management in Decentralized
Decision-Making: Decentralized Diagnosis of Discrete-Event Systems

Kumar, R.   Takai, S. 

Abstract: 

The task of decentralized decision-making involves interaction of a set
of local decision-makers, each of which operates under limited sensing
capabilities and is thus subjected to ambiguity during the process of
decision-making. In our prior work, we made a key observation that such
ambiguities are of differing gradations and presented a framework for
inferencing over varying ambiguity levels to arrive at local and global
control decisions. We develop a similar framework for performing
diagnosis in a decentralized setting. For each event-trace executed by
a system being monitored, each local diagnoser issues its own diagnosis
decision (failure or nonfailure or unsure), tagged with a certain
ambiguity level (zero being the minimum). A global diagnosis decision
is taken to be a "winning" local diagnosis decision, i.e., one with a
minimum ambiguity level. The computation of an ambiguity level for a
local decision requires an assessment of the self-ambiguity as well as
the ambiguities of the others, and an inference based up on such
knowledge. In order to characterize the class of systems for which any
fault can be detected within a uniformly bounded number of steps (or
"delay"), we introduce the notion of $N$ -inference-diagnosability for
Failures (also called  $N$-inference F-diagnosability), where the index
$N$ represents the maximum ambiguity level of any winning local
decision. We show that the codiagnosability introduced in   is the same
as 0-inference F-diagnosability; the conditional F-codiagnosability
introduced in  ,  is a type of 1-inference F-diagnosability; the class
of higher-in- dex

3)  Clarification on the Computation of Liveness-Enforcing Supervisor
for Resource Allocation Systems With Uncontrollable Behavior

Hu, H.   Li, Z.

Abstract: 

In previous work, an acceptable transformation of an unacceptable
specification on a Petri net can be implemented through a set of
mathematical programming formulations. However, such a method becomes
invalid when no solution exists in practice. In this paper, we
reestablish these formulations and show their correctness.

web site: click here