[Newsletter] for April, 2014

                      ON DISCRETE EVENT SYSTEMS

Newsletter......................................... April, 2014

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. Journals
   2.1 Selections from the Automatica
       Volume: 50, Issue: 3, March 2014
   2.2 Selections from the IEEE Transactions on Automatic Control
       Volume: 59, Issue: 4, April 2014
   2.3 Selections from the IEEE Transactions on Automation Science and Engineering
       Volume: 11, Issue: 2, April 2014
   2.4 Selections from the IEEE Transactions on Robotics
       Volume: 30, Issue: 2, April 2014
   2.5 Selections from the Journal of Control Theory and Applications
       Volume: 12, Issue: 1



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

Personal note from the editor:





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

                         VOLUME: 50 ISSUE: 3
                               MARCH 2014

1)Robust control reconfiguration of resource allocation systems with Petri nets
and integer programming

Jun Li, MengChu Zhou, Tao Guo, Yahui Gan, Xianzhong Dai


Supervisory control reconfiguration can handle the uncertainties including resource failures
and task changes in discrete event systems. It was not addressed to exploit the robustness of
closed-loop systems to accommodate some uncertainties in the prior studies. Such exploitation
can cost-efficiently achieve reconfigurability and flexibility for real systems. This paper presents a
robust reconfiguration method based on Petri nets (PNs) and integer programming for
supervisory control of resource allocation systems (RASs) subject to varying resource allocation
relationships. An allocation relationship is seen as a control specification while the execution
processes requiring resources as an uncontrolled plant. First, a robust reconfiguration mechanism
 is proposed. It includes updating the PP-invariant-based supervisor and evolving the state of the
closed-loop system. The latter adapts to the control specification changes by the self-regulation of
 the closed-loop system’s state. Next, two novel integer programming models for control
reconfiguration are proposed, called a reconfiguration model with acceptability and reconfiguration
 one with specification correction. Since both models integrate the firability condition of transitions,
 no additional efforts are required for the state reachability analysis. Finally, a hospital emergency
service system is used as an example to illustrate them.

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

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

                           VOLUME: 59 ISSUE: 4
                                 APRIL 2014

1)Partial-Information State-Based Optimization of Partially Observable Markov
Decision Processes and the Separation Principle

Xi-Ren Cao, De-Xin Wang, Li Qiu


We propose a partial-information state based approach to the optimization of the long-run
average performance in a partially observable Markov decision process (POMDP). In this approach,
the information history is summarized (at least partially) by a (or a few) statistic(s), not necessary
sufficient, called a partial-information state, and actions depend on the partial-information state,
rather than system states. We first propose the “single-policy based comparison principle,” under
which we derive an HJB-type of optimality equation and policy iteration for the optimal policy
in the partial-information-state based policy space. We then introduce the Q-sufficient statistics
and show that if the partial-information state is Q-sufficient, then the optimal policy in the
partial-information state based policy space is optimal in the space of all feasible information state
 based policies. We show that with some further conditions the well-known separation principle holds.
 The results are obtained by applying the direct comparison based approach initially developed for
 discrete event dynamic systems.

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

2)On Most Permissive Observers in Dynamic Sensor Activation Problems

Dallal, E., Lafortune, S.


We consider the problem of dynamic sensor activation for fault diagnosis of discrete event systems
modeled by finite state automata under the constraint that any fault must be diagnosed within no more
than K + 1 events after its occurrence, a property called K-diagnosability. We begin by defining an
 appropriate notion of information state for the problem and defining dynamic versions of the projection
operator and information state evolution. We continue by showing that the problem can be reduced to
that of state disambiguation. Then we define the most permissive observer (MPO) structure that contains
 all the solutions to the problem, and we prove results showing that maintaining the K-diagnosability
 property is equivalent to satisfying the extended specification of the state disambiguation problem.
We then prove a monotonicity property of the extended specification, and show that this allows us to
reduce our information state, which in turn allows us to significantly reduce the complexity of our solution.
 Putting all of our results together, we obtain a MPO with a size complexity of O(2|X|(K+2)|X|2|E|),
compared with O(2|X|2 •K •2|E|) for the previous approach, where X and E are, respectively, the sets
of states and events of the automaton to diagnose. Finally, we provide an algorithm for constructing
the most permissive observer and demonstrate its scalability through simulation.

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

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

                                                       VOLUME: 11 ISSUE: 2
                                                              APRIL 2014

1)Optimal Computing Budget Allocation for Complete Ranking

Xiao, H., Lee, L.H., Ng, K


Previous research in ranking and selection focused on selecting the best design and subset selection.
 Little research has been done for ranking all designs completely. Complete ranking has been applied to
design of experiment, random number generator and population-based search algorithms.
In this paper, we consider the problem of ranking all designs. Our objective is to develop an efficient
simulation allocation procedure that maximizes the probability of correct ranking with fixed
limited computing budget. A previous allocation strategy of complete ranking based on indifference
zone formulation is conservative and not efficient enough. We use the optimal computing budget
allocation framework to further enhance the efficiency and reduce the amount of budget needed to
achieve the same probability of correct ranking. Compared with the previous allocation strategy,
our proposed allocation rule performs best under different scenarios.

Web site: https://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6457421

2)Optimal Supervisory Control of Flexible Manufacturing Systems by Petri
Nets: A Set Classification Approach

Chen, Y., Li, Z., Zhou, M.C.


Supervisory control is usually considered as an external control mechanism to a system by
controlling the occurrences of its controllable events. There exist Petri net models whose legal
reachability spaces are nonconvex. In this case, they cannot be optimally controlled by the conjunctions
of linear constraints. For Petri net models of flexible manufacturing systems, this work proposes a method
to classify the legal markings into several subsets. Each subset is associated with a linear constraint that
can forbid all first-met bad markings. Then, the disjunctions of the obtained constraints can make all legal
markings reachable and forbid all first-met bad markings, i.e., the controlled net is live and maximally
permissive. An integer linear programming model is formulated to minimize the number of the
constraints. A supervisory structure is also proposed to implement the disjunctions of the constraints.
Finally, examples are provided to illustrate the proposed method.

Web site: https://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6472740

3)Timed Compatibility Analysis of Web Service Composition: A Modular Approach
Based on Petri Nets

Du, Y., Tan, W., Zhou, M.C. 


Recently, the temporal constraint satisfiability is regarded as an important criterion in Web service
composition to guarantee its timely completion. This leads to a new challenge in analyzing the
compatibility of Web services under temporal constraints. The existing methods either do not
consider message mismatches between services in a composition or suffer from state-space explosion
 by verifying a service composition model as a whole; or lack the ability to generate execution
paths of each participating service. In this paper, we present a Petri net-based method to address these
three issues in a holistic manner, and also in a modular way. Compared with the existing work, the
proposed approach not only composes Web services by adding a mediation net to deal with message
mismatches, but also checks the compatibility w.r.t. temporal constraints by generating modular timed
state graphs. Furthermore, the reliable and usable execution paths that satisfy the timed
compatibility can be derived to guide service execution and avoid any temporal exception.

Web site: https://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6512068

4)Parameterized ACD Modeling of Flexible Manufacturing Systems

Choi, B.K., Kim, H., Kang, D., Jamjoom, A.A., Abdullah, M.A.


Activity cycle diagram (ACD), which is essentially a timed Petri net, is one of the oldest formal
modeling tools for discrete-event systems, and a flexible manufacturing system (FMS) is a highly
automated job shop that is used widely in mechanical and electronics industries. Previous FMS modeling
studies have indicated that formal modeling of real-life (or industrial) FMSs with classical ACDs
(or Petri nets) is almost impossible. This paper presents an incremental modeling procedure for building a
formal simulation model of a real-life FMS with parameterized ACD (P-ACD) that was proposed recently.
The incremental modeling procedure consists of job flow modeling, job routing modeling, dispatching
rule modeling, and refixture operation modeling. In this paper, a P-ACD model of a real-life FMS was
constructed and an FMS simulator was implemented from the proposed P-ACD model. A simulation experiment
was conducted in order to demonstrate the usefulness of the FMS simulator.

Web site: https://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6709574

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

                  VOLUME: 30 ISSUE: 2
                       APRIL 2014

1)Event-Based Stabilization of Periodic Orbits for Underactuated 3-D Bipedal
Robots With Left-Right Symmetry

Hamed, K.A., Grizzle, J.W.


Models of robotic bipedal walking are hybrid, with a differential equation that describes the
stance phase and a discrete map describing the impact event, that is, the nonstance leg contacting
the walking surface. The feedback controllers for these systems can be hybrid as well, including
both continuous and discrete (event-based) actions. This paper concentrates on the event-based
portion of the feedback design problem for 3-D bipedal walking. The results are developed in the
context of robustly stabilizing periodic orbits for a simulation model of ATRIAS 2.1, which is a highly
underactuated 3-D bipedal robot with series-compliant actuators and point feet, against external
disturbances as well as parametric and nonparametric uncertainty. It is shown that left–right
symmetry of the model can be used to both simplify and improve the design of event-based controllers.
Here, the event-based control is developed on the basis of the Poincaré map, linear matrix inequalities
and robust optimal control. The results are illustrated by designing a controller that enhances the
lateral stability of ATRIAS 2.1.

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

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

                                       VOLUME: 12 ISSUE: 1

1)Constrained optimal steady-state control for isolated traffic intersections

J. Haddad, D. Mahalel, I. Ioslovich, P. Gutman


The steady-state or cyclic control problem for a simplified isolated traffic intersection is considered.
The optimization problem for the green-red switching sequence is formulated with the help of a
discrete-event max-plus model. Two steady-state control problems are formulated: optimal steady-state
with green duration constraints, and optimal steady-state control with lost time. In the case when the
criterion is a strictly increasing, linear function of the queue lengths, the steady-state control problems
can be solved analytically. The structure of constrained optimal steady-state traffic control is revealed,
and the effect of the lost time on the optimal solution is illustrated.

Web site: http://jcta.alljournals.ac.cn/cta_en/ch/reader/view_abstract.aspx?file_no=JCTA12247


                                               The End