Industrial Automation

IST / DEEC / API
Industrial Automation
(Automação de Processos Industriais)
Supervised Control of
Discrete Event Systems
http://users.isr.ist.utl.pt/~jag/courses/api1617/api1617.html
Prof. Paulo Jorge Oliveira, original slides

Prof. José Gaspar, rev. 2016/2017
Page 1
IST / DEEC / API Industrial Automation
Syllabus:
...
Chap. 8 - DESs and Industrial Automation [2 weeks]
Chap. 9 – Supervised Control of DESs [1 week]

* SCADA
* Methodologies for the Synthesis of Supervision Controllers
* Failure detection
Some jokes available in http://members.iinet.net.au/~ianw/cartoon.html

The End.
Page 2
IST / DEEC / API Chap. 9 – Supervised Control of DES
Some pointers on Supervised Control of DES

History: The SCADA Web, http://members.iinet.net.au/~ianw/
Monitoring and Control of Discrete Event Systems, Stéphane Lafortune,
http://www.ece.northwestern.edu/~ahaddad/ifac96/introductory_workshops.html
Tutorial: http://vita.bu.edu/cgc/MIDEDS/
http://www.daimi.au.dk/PetriNets/
Analysers & http://www.nd.edu/~isis/techreports/isis-2002-003.pdf (Users Manual)

Simulators: http://www.nd.edu/~isis/techreports/spnbox/ (Software)
Bibliography: * SCADA books http://www.sss-mag.com/scada.html

* K. Stouffer, J. Falco, K. Kent, "Guide to Supervisory Control and Data
Acquisition (SCADA) and Industrial Control Systems Security",
NIST Special Publication 800-82, 2006
* Moody J. e Antsaklis P., “Supervisory Control of Discrete Event
Systems using Petri Nets,” Kluwer Academic Publishers, 1998.
* Cassandras, Christos G., "Discrete Event Systems - Modeling and
Performance Analysis," Aksen Associates, 1993.
* Yamalidou K., Moody J., Lemmon M. and Antsaklis P.
Feedback Control of Petri Nets Based on Place Invariants
http://www.nd.edu/~lemmon/isis-94-002.pdf
Page 3
Supervision of DES: SCADA
Supervisory
Control
And
Data
Acquisition
Page 4
Supervision of DES
SCADA interface / GUI
Page 5
IST / DEEC / API
SCADA example,
Rail Monitoring
and Control
Page 6
Supervision of DES
SCADA vs ICS
Industrial Control Systems (ICS):
- Supervisory Control and Data Acquisition (SCADA) systems,
- Distributed Control Systems (DCS), or
- smaller configurations such as skid-mounted PLCs
ICSs are typically used in industries such as electric, water, oil-

and-gas, transportation, chemical, pharmaceutical, pulp-and-
paper, food and beverage, and discrete-manufacturing (e.g.
automotive, aerospace, and durable goods).
Page 7
Supervision of DES
SCADA topics
• Remote monitoring of the state of automation systems
• Logging capacity (resorting to specialized Databases)
• Able to access to historical information (plots along time,
with selectable periodicity)
• Advanced tools to design Human-Machine interfaces
• Failure Detection and Isolation capacity (threshold and/or
logical functions) on supervised quantities
• Access control
Page 8
IST / DEEC / API
Supervision of DES
SCADA system general layout
Page 9
Supervision of DES
Hardware Support Architecture of SCADA
A1 A1 MTU Legend:
...
MTU - Main Terminal Unit
Field Bus
RTU - Remote Term. Unit
S – Sensor
... ...
RTU1 RTUn S1 S1 A - Actuator
More terminology: Field Bus (IEC 61158) / PROFIBUS (Field Bus type,
Siemens), MODBUS (Schneider)
Page 10
Supervision of DES
Examples of software packages including
SCADA solutions
Page 11
Supervision of DES
And
Now
Something
Completely
Different
Page 12
Supervision of DES
Objectives of the Supervised Control
• Supervise and bound the work of the supervised DES

• Reinforce that some properties are verified
• Assure that some states are not reached
• Performance criteria are verified
• Prevent deadlocks in DES
• Constrain on the use of resources (e.g. mutual exclusion)
Page 13
Supervision of DES
Some history on Supervised Control
• Methods for finite automata [Ramadge et al.], 1989

• some are based on brute-force search (!)
• or may require simulation (!)
• Formal verification of software in Computer Science

(since the 60s) and on hardware (90, ...)
• Supervisory Control Method of Petri Nets, method based on

monitors [Giua et al.], 1992.
• Supervisory Control of Petri Nets based on Place Invariants

[Moody, Antsaklis et al.], 1994 (shares some similarities with the
previous one, but deduced independently!...).
Page 14
Supervision of DES
Advantages of the Supervisory Control of Petri Nets
• Mathematical representation is clear (and easy)

• Resorts only to linear algebra (matrices)
• More compact then automata
• Straightforward the representation of infinity state spaces
• Intuitive graphical representation available
The representation of the controller as a Petri Net leads to

simplified Analysis and Synthesis tasks
Page 15
Supervision of DES
Place Invariants
Place invariants are sets of places whose token count remains always constant.
Place invariants can be computed from integer solutions of wT D = 0. Non-zero
entries of w correspond to the places that belong to the particular invariant.
Supervisor Synthesis using Place Invariants [ISIS docs]:
What type of relations can be represented in the method of Place Invariants?

• Sets of linear constraints in the state space
• Representation of convex regions (there are extensions for non-convex regions)
• Constraints to guarantee liveness and to avoid deadlocks (that can be expressed, in
general, as linear constraints)
• Constraints on the events and timings (that can be expressed, in general, as linear
constraints)
Page 16
Methods of Analysis/Synthesis
Method of the Matrix Equations (just to remind)
The dynamics of the Petri net state can be written in

compact form as:
 k  1   k   Dqk 
where:
μ(k+1) - marking to be reached
μ (k) - initial marking
q(k) - firing vector (transitions)
D - incidence matrix. Accounts the balance of
tokens, giving the transitions fired.
Page 17
Methods of Analysis/Synthesis
How to build the Incidence Matrix? (just to remind)
For a Petri net with n places and m transitions
  N0 n
q  N0
m
D  D   D  , D   nm , D   N 0nm , D   N 0nm

The enabling firing rule is   Dq
Can also be written in compact form as the inequality   Dq  0,
interpreted element-by-element.
Note: in this course all vector and matrix inequalities are read element-by-element unless
otherwise stated.
Page 18
Methods of Synthesis
Some notation for the method
• The supervised system is modelled as a Petri net with
n places and m transitions, and incidence matrix
DP   nm .
• The supervisor is modelled as a Petri net with nC
places and m transitions, and incidence matrix
nC m
DC   .
• The resulting total system has an incidence matrix
D   ( n  nC )m .
Page 19
Theorem: Synthesis of Controllers based on Place Invariants (T1)
Given the set of linear state constraints that the supervised system must
follow, written as
L  P  b, P  N0n , L  Z nC n and b  Z nC .
If b  L P0  0,
then the controller with incidence matrix and the initial marking, respectively
DC   LDP , and  C  b  L P ,
0 0
enforce the constraints to be verified for all markings obtained from the initial
marking.
Page 20
Theorem - proof outline :
The constraint L P  b can be written as L P   C  b,

using the slack variables  C . They represent the marking
of the nC places of the controller.
To have a place invariant, the relation w D  0 must be

T
verified and in particular, given the previous constraint:

 DP 
w D  L I     0, resulting DC   LDP .
T
 DC 
From L P0   C0  b, follows that  C0  b  L P0 .

Page 21
Example of controller synthesis: Mutual Exclusion
Linear constraint: 2  4  1
p1 . . p
3
 1 
that can be written as:
t1 t3
 
p p L P  b 0 1 0 1 2   1.
2 4  3 
 
t2 t4 4 
 1 1 0 0  1
 1 1 0 0  0 
Incidence
DP    and initial  P0   .
Matrix  0 0 1 1  marking 1
   
 0 0 1  1 0 
Page 22
1
1) Test 0 
b  L P0  1  0 1 0 1   1  0.
1
  OK.
0 
2) Compute
 1 1 0 0 
 1 1 0 0 
DC   LDP  0 1 0 1    1 1  1 1,
 0 0 1 1 
 
and  0 0 1  1
 C  b  L  P  1.
0 0
OK.
Page 23
 1 1 00
3) Resulting in 1 1 0 0 

D0 0 1 1 
 
p1 . . p 0 0 1  1
3
 1 1  1 1 
t1 t3
1
0 
p pC p  
2 4  0  1
t4   OK.
t2 0  UAU!!!.
1
Page 24
Result using the function
LINENF.m of the
toolbox SPNBOX:
Page 25
Definition:
Maximal permissivity occurs when (i) all the linear constraints

are verified and (ii) all legal markings can be reached.
Lemmas:
L1) The controllers obtained with T1 have maximal permissivity.
L2) Given the linear constraints used, the place invariants

obtained with the controller synthesized with T1 are the same
as the invariants associated with the initial system.
Page 26
Example of controller synthesis s  N 0 , t  N 0 , n  N 0
n Readers / 1 Writer Linear constraint  2  n 4  n
(max n readers or 1 writer)
p1 s t p
3
That can be written as:  1 
t1 t3  
L P  b 0 1 0 n 2   n.
p p
 3 
2 4  
 4 
t2 t4
 1 1 0 0  s
 1 1 0 0  0 
Incidence
DP    and initial  P0   .
Matrix  0 0 1 1  marking t 
   
 0 0 1  1 0 
Page 27
Example of controller synthesis
n Readers / 1 Writer s
1) Test 0 
b  L P0  n  0 1 0 n   n  0.
t 
  OK.
0 
2) Compute
 1 1 0 0 
 1 1 0 0 
DC   LDP  0 1 0 n    1 1  n n,
 0 0 1 1 
 
and  0 0 1  1
 C  b  L P  n.
0 0 OK.
Page 28
 1 1 0
0
Example of controller synthesis 1 1 0 
0
n Readers / 1 Writer 
D0 0 1 1 
3) Resulting in  
0 0 1  1
 1 1  n n 
p1 s t p
3 s
t1 n 0 
t3  
0   t 
n pC  
p p 0 
2 4
t4 n OK.
t2 n UAU!!!.
Page 29
Supervision of DES
Advantages of the Method of the Place Invariants [ISIS docs]:
Other characteristics that can impact on the solutions?
• Existence and uniqueness
• Optimality of the solutions (e.g. maximal permissivity)
• Existence of transition non-controllable and/or not observable

(remind definitions for time-driven systems)
In general the solutions can be found solving:

Linear Programming Problems, with Linear Constraints
Page 30
Example of controller synthesis: s Producers / t Consumers
Incidence Initial
p1 s t p matrix marking
3
t1
 1 1 0 0  s
t3  1 1 0 0  0 
DP     P0   .
p p  0 0 1 1  t 
   
2 4
 0 0 1  1 0 
t2 t4
Let p2= #machines working, t2= product produced

p3= #consumers, t3= request to consume (e.g. transport product)
Q: How to write consume only when produced ? What is the linear constraint?
Not possible to write it as a linear constraint on places Lμp ≤ b .

Is it impossible to solve this problem with the proposed method ?
Page 31
Generalized linear constraint
Let the generalized linear constraint be
L P  FqP  Cv P  b,
 P  N 0 n , vP  N 0 m , qP  N 0 m ,
nC n nC m nC m
LZ ,F Z ,C  Z ,e b Z nC
,
where
*  P is the marking vector for system P;
* q P is the firing vector since t0;
* vP is the number of transitions (firing) that can occur,

also designated as Parikh vector.
Page 32
Methods of Synthesis Function LINENF of SPNBOX
Theorem: Synthesis of Controllers based on Place Invariants,

for Generalized Linear Constraints
Given the generalized linear constraint L  P  Fq P  Cv P  b ,
if b  L  P0  0, then the controller with incidence matrix
and initial marking, respectively
DC  max 0, LD P  C , F 

DC  max 0, F  max 0, LD P  C   min 0, LD P  C ,
 C  b  L  P  Cv P 0 ,
0 0
guarantees that constraints are verified for the states resulting from the
initial marking.
Page 33
Example of controller synthesis s  N 0 , t  N 0 , n  N 0
Producer / Consumer Linear constraint: v3  v2
p1 s t p that can be written as:
3
 v1 
t1 t3 CvP  b v 
L  0, F  0
0  1 1 0  2
 0.
p p v3 
2 4
 
t2 t4  v4 
 1 1 0 0  s
 1 1 0 0  0 
Incidence   Initial    .
DP  P
t 
 0 0 1 1 
0
matrix marking
   
 0 0 1  1 0 
Page 34
Producer / Consumer
1) Test b  L P0  0  0  0.
OK.
2) Compute DC  max 0, LD P  C , F 
DC  max 0, F  max 0, LD P  C   min 0, LD P  C ,
DC  max 0, [0  1 1 0], 0   [0 0 1 0]

DC  max 0,  [0 0 1 0]  min 0, [0  1 1 0]
 [ 0 0 0 0]  [ 0  1 0 0 ]  [ 0 1 0 0 ]
and  C  b  L  P  Cv P 0 ,
0 0
 C  b  L  P  0  0  0.
0 0
OK.
Page 35
 1 1 0 0 
Example of controller synthesis  1 1 0 0 
Producer / Consumer  
D   0 0 1 1 
3) Resulting in  
 0 0 1  1
 0 1  1 0 
p1 s t p
3 s
t1 0 
t3  
0   t 
pC  
p p 0 
2 4
t4 0  OK.
t2
UAU!!!.
Page 36
Methods of Synthesis Example of controller synthesis:

Producer Consumer
Result using the function
LINENF.m of the
toolbox SPNBOX:
Page 37
Incidence Initial
Bounded
Producer / p1 s t p matrix marking
3
Consumer t1 t3  1 1 0 0  s
 1 1 0 0  0 
DP     P0   .
p p  0 0 1 1  t 
2 4    
 0 0 1  1 0 
t2 t4
TWO linear constraints: The two linear constraints

can be written as:
 v3  v2 v3  v2  0  v1 
  Cv P  b   
v 
v2  v3  n v2  v3  n  0 1 1 0  2   0 
i.e. L  0, F  0 0 1  1 0   v   n 
  3  
s  N 0 , t  N 0 , n  N 0  
v 4 
Page 38
Bounded Producer / Consumer
1) Test 0 
b  L P0  b     0. OK.
2) Compute n 
  0  1 1 0   0 0 1 0 
D  max 0, 

 , 0     ,
  0 1  1 0   0 1 0 0 
C
  0  1 1 0     0  1 1 0  
  
DC  max 0, 0  max 0,      min 0,   
     
   0 1 1 0     0 1 1 0  
0 0 0 0   0  1 0 0   0 1 0 0 
      .
0 0 0 0   0 0  1 0   0 0 1 0 
and
0 OK.
 C  b  L P   .
n
0 0
Page 39
Methods of Synthesis  1 1 0 0 
Example of controller synthesis  1 1 0 0 
 
Bounded Producer / Consumer  0 0 1 1 
D 
 0 0 1  1
3) Resulting in
 0 1 1 0
 
p1 s t p
3
 0  1 1 0 
pC s
t1 2 t3 0 
n  
t 
p
2
p
4
0   
0  OK.
t2 pC t4 0 UAU!!!.
1  
n
Page 40
Methods of Synthesis:
adding Uncontrollable and Unobservable transitions
Definition of Uncontrollable Transition:

A transition is uncontrollable if its firing cannot be inhibited by an external
action (e.g. a supervisory controller).
Definition of Unobservable Transition:

A transition is unobservable if its firing cannot be detected or measured
(therefore the study of any supervisory controller can not depend from that
firing).
Proposition:
In a Petri net based controller, both input and output arcs to/from plant transitions are
used to trigger state changes in the controller. Since a controller cannot have arcs
connecting to unobservable transitions, then all unobservable transitions are also
implicitly uncontrollable.
Page 41
Methods of Synthesis:
adding Uncontrollable and Unobservable transitions
If t1 is controllable and t2 is uncontrollable:

- case (a), then t2 cannot be directly inhibited; it will eventually fire
- case (b), then t2 can be indirectly prevented from firing by inhibiting t1.
If t2 is unobservable and t3 is observable, then we cannot detect when t2

fires. The state of a supervisor is not changed by firing t2. However we can
indirectly detect that t2 has fired, by detecting the firing of t3.
Page 42
Definition: A marking μP is admissible if

i) LμP ≤ b and ii) μ’  R(C, μP ) verifies Lμ’ ≤ b
Definition: A Linear Constraint (L, b) is admissible if

i) LμPo ≤ b and
ii) μ’  R(C, μPo) such that Lμ’ ≤ b
μ’ is an admissible marking.
Note: ii) indicates that the firing of uncontrollable transitions can never lead from a
state that satisfies the constraint to a new state that does not satisfy the constraint.
Page 43
Proposition: Admissibility of a constraint
A linear constraint is admissible iff
• The initial markings satisfy the constraint.
• There exists a controller with maximal permissivity that forces the
constraint and does not inhibit any uncontrollable transition.
Two sufficient (not necessary) conditions:

Corollary: given a system with uncontrollable transitions,
l T Duc  0 implies admissibility.
Corollary: given a system with unobservable transitions,

l T Duo  0 implies admissibility.
Page 44
Methods of Synthesis Function MRO_ADM of SPNBOX
Lemma *: Structure of Constraint transformation
Let R1  Z nC n such that R1 P  0,

nC nC
R2  Z be a matrix with positive elements in the diagonal,
If there exists L  R1  R2 L
'
such that LP  b
' '
b '  R2 b  1  1,
then it is also verified that L P  b.
* Lemma 4.10 in [Moody98] pg46

Page 45
Example: design controller with t1 unobservable (1/4)
Objectives: μ1+ μ3 ≥1 and μ2+ μ3 ≥1 which can be written in matrix

form as
Example extracted from “Supervised Control of Concurrent Systems: A Petri Net

Structural Approach”, M. Iordache and P. Antsaklis, Birkhauser 2006.
Page 46
Dfp = Dfm = mf0 =

D= [-1 1 0;
-1 0 1; 1
0 1 0 1 0 0
+2 -1 -1]; 0 0 1 1 0 0 1
m0= [1 1 0]'; 2 0 0 0 1 1 0
1 0 0 0 0 1 0
L= -[1 0 1; 0 1 1]; 1 0 0 0 1 0 0
b= -[1; 1];
^ Bad news, supervisor touches t1 .
[Dp, Dm]=
incidence_split( D );
[Dfp, Dfm, mf0] =

linenf( Dp, Dm, L, b, m0 );
Page 47
Solution obtained with the function MRO_ADM.m of the SPNBOX toolbox:
Note: verify that Laμ≤ ba implies Lμ≤ b
Page 48
Finally the supervised controller is simply obtained from La and ba:
Dc   L a D p
 1 1 0
 2 0  1  
    1 0 1 
 0  2  1  2  1  1
 
0 1  1
 
0  1 1 
 c 0  ba  La  p 0
1 
 1  2 0  1  
    1
 1  0  2  1 0 Obtained the desired result:
 
1
supervisor does not touch t1 .

1 Page 49
IST / DEEC / API
This course is ending. What is next?
Page 50
IST / DEEC / API
This course is ending .
What
is
next ?
Page 51
IST / DEEC / API
Top 10 Challenges in Logic Control for Manufacturing Systems

by Dawn Tilbury from University of Michigan
10. Distributed Control (General management of distributed control applications,

Open/distributed control -- ethernet-based control)
9. Theory (No well-developed and accepted theory of discrete event control,
in contrast to continuous control)
8. Languages (None of the programming languages do what we need but nobody
wants a new programming language)
7. Control logic synthesis (automatically)
6. Standards (Machine-control standards -- every machine is different, Validated standards,

Standardizing different types of control logic programming language)
5. Verification (Standards for validation, Simulation and verification of controllers)
4. Software (Software re-usability -- cut and paste, Sophisticated software for logic control,
User-unfriendly software)
3. Theory/Practice Gap (Bridging the gap between industry and academia,
Gap between commercial software and academic research)
2. Education (Educating students for various PLCs, Education and keeping current with
evolution of new control technologies, Education of engineers in logic control,
Lack of curriculum in discrete-event systems)
And the number one challenge in logic control for manufacturing systems is...
1. Diagnostics (Integrating diagnostic tools in logic control, Standardized methodologies for design,
development, and implementation of diagnostics)
Page 52
The End .
Page 53

Industrial Automation

Uploaded by

Copyright:

Available Formats

Industrial Automation

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Industrial Automation

Uploaded by

Copyright:

Available Formats

IST / DEEC / API

Prof. Paulo Jorge Oliveira, original slides

Chap. 8 - DESs and Industrial Automation [2 weeks]

Chap. 9 – Supervised Control of DESs [1 week]

Some jokes available in http://members.iinet.net.au/~ianw/cartoon.html

Some pointers on Supervised Control of DES

Analysers & http://www.nd.edu/~isis/techreports/isis-2002-003.pdf (Users Manual)

Bibliography: * SCADA books http://www.sss-mag.com/scada.html

Supervision of DES: SCADA

ICSs are typically used in industries such as electric, water, oil-

Objectives of the Supervised Control

• Supervise and bound the work of the supervised DES

• Methods for finite automata [Ramadge et al.], 1989

• Formal verification of software in Computer Science

• Supervisory Control Method of Petri Nets, method based on

• Supervisory Control of Petri Nets based on Place Invariants

Advantages of the Supervisory Control of Petri Nets

• Mathematical representation is clear (and easy)

The representation of the controller as a Petri Net leads to

Supervisor Synthesis using Place Invariants [ISIS docs]:

What type of relations can be represented in the method of Place Invariants?

The dynamics of the Petri net state can be written in

D  D   D  , D   nm , D   N 0nm , D   N 0nm

The constraint L P  b can be written as L P   C  b,

To have a place invariant, the relation w D  0 must be

verified and in particular, given the previous constraint:

From L P0   C0  b, follows that  C0  b  L P0 .

Maximal permissivity occurs when (i) all the linear constraints

L1) The controllers obtained with T1 have maximal permissivity.

L2) Given the linear constraints used, the place invariants

Advantages of the Method of the Place Invariants [ISIS docs]:

Other characteristics that can impact on the solutions?

• Existence and uniqueness

• Optimality of the solutions (e.g. maximal permissivity)

• Existence of transition non-controllable and/or not observable

In general the solutions can be found solving:

Let p2= #machines working, t2= product produced

Not possible to write it as a linear constraint on places Lμp ≤ b .

* q P is the firing vector since t0;

* vP is the number of transitions (firing) that can occur,

Methods of Synthesis Function LINENF of SPNBOX

Theorem: Synthesis of Controllers based on Place Invariants,

DC  max 0, LD P  C , F 

DC  max 0, [0  1 1 0], 0   [0 0 1 0]

Methods of Synthesis Example of controller synthesis:

TWO linear constraints: The two linear constraints

Definition of Uncontrollable Transition:

Definition of Unobservable Transition:

If t1 is controllable and t2 is uncontrollable:

If t2 is unobservable and t3 is observable, then we cannot detect when t2

Definition: A marking μP is admissible if

Definition: A Linear Constraint (L, b) is admissible if

Two sufficient (not necessary) conditions:

Corollary: given a system with unobservable transitions,

Methods of Synthesis Function MRO_ADM of SPNBOX

Lemma *: Structure of Constraint transformation

Let R1  Z nC n such that R1 P  0,

then it is also verified that L P  b.

* Lemma 4.10 in [Moody98] pg46