```CS 367: Model-Based Reasoning
Lecture 11 (02/19/2002)
Gautam Biswas
Today’s Lecture
Today’s Lecture:


Finish up Supervisory Control
Onto Modeling of Continuous Systems: The Bond
Graph Approach
Supervisory Controller: Examples
Admissible strings: a1 precedes a2 iff b1 precedes b2
Build trim automata Ha such that Lm(Ha) contains only
those strings that contain the above ordering constraints
Is Ha blocking?
In general, how do we build supervisors? If all events
controllable and observable: L ( S / G )  L ( H ) and L ( S / G )  L
1
a
m
1
m
(H a )
Realizing Supervisors
How to build an automaton that realizes S?
Build an automaton that marks K, i.e.,
R  (Y , E , g ,  R , y 0 , Y ), where R is trim
Lm ( R )  L ( R )  K
L ( R  G )  L ( R )  L (G )  K  L (G )  K  L ( S / G )
L m ( R  G )  Lm ( R )  Lm (G )  Lm ( S / G )
Note that R has the same event set as G, therefore,
R G  RG
Control action S(s) is encoded into transition structure of R
S ( s )  [ E uc   ( f ( x 0 , s ))]  {  E c : s   K }
  R ( g ( y 0 , s ))
  R  G ( g  f (( y 0 , x 0 ), s ))
Standard Realization of S
Start with G in state x, R in state y, following the
execution of s  L ( S / G )
G generates  that is currently enabled, i.e., this
event set is present in R’s active event set at y
R executes the event as a passive observer of G
and the system now moves into states x’ and y’
Set of enabled events of G given by active event
set of R at y’
Induced Supervisor
Reverse Question: Given C, can the product CG
imply that C is controlling G
Depends on the controllability of L(C)
The supervisor for G induced by C is S
C
i
L ( S i / G )  L ( C  G ) iff L ( C ) is controllab le wrt L ( G ) and E uc
C
Reduced State Realization
L(S/G) = K may not be the most
economical way to represent S in
terms of an automata (memory
requirements)
Relax requirements L(R) = K, and
Come up with L ( R rs )  K
L ( R rs  G )  L ( S / G )
Collapse 2,5,6,7, and 8 into one state
Controllable sub languages and super languages of
an uncontrollable language
K is not controllable wrt M and Euc
K E uc  M  K
K  M
Two languages derived from K:


The supremal controllable sub language K: K  C

K (Inside K)
The infimal prefix-closed and controllable super
language of K: K  C (Outside K)
  K
C
 K  K  K
C
 M
Example: Supremally Controllable
Language
M  L (G ) k  L m ( H a )
K  { a 2 b 2 a 1b1 , a 2 a 1b 2 b1 , a 1 a 2 b1b 2 , a 1b1 a 2 b 2 }
E uc  { a 2 , b 2 } makes K uncontroll able
Re move from K all strings that contain a 1 a 2 as prefix
K 1  { a 2 b 2 a 1b1 , a 2 a 1b 2 b1 , a 1b1 a 2 b 2 }   K 1 not controllab le
Re move all strings that contain a 1 as prefix
K 2  { a 2 b 2 a 1b1 , a 2 a 1b 2 b1 } this is controllab le
K
C
 K2
Infimal Prefix-closed controllable
language
M & K as before
Extend string a1 a 2 with string of uncontroll able events
of length 1
K
C
 K  { a1 a 2 b 2 }
Supervisory Control Problems
BSCP: Basic Supervisory Control Problem
 Given G with event set E, and Euc  E, and an admissible
language La = La  L(G) find supervisor such that
L ( S / G )  La
L ( S / G ) is the largest
L ( S other / G )  L a
it can be , i .e .,
L ( S other / G )  L ( S / G )
Look up standard realization presented couple of lectures
ago (sec. 3.4.2)
DuSCP: Dual Version of SCP:minimum required language Lr
 L(G)
L ( S / G )  Lr
L ( S / G ) is the s mallest
L ( S other / G )  L r
it can be , i .e .,
L ( S other / G )  L ( S / G )
Supervisory Controller Problems
SCPT: Supervisory Controller with Tolerance



Ldes: desired language, try and achieve as much of it as
possible
Ltot: tolerated language, do not exceed tolerated
langauge
C
C
Solution: L ( S / G )  ( L tol  L des )
Non Blocking Supervisors
K E uc  L ( G )  K
Controllable:
Non blocking: Lm(G) closure:
K  K  L m (G )
typically holds by construction of K
Supervisory Controller with Blocking
Typically use two measures:
Blocking Measure:
Satisficing Measure:
BM ( S )  L ( S / G ) \ L m ( S / G )
SM ( S )  L m ( S / G )  L am
SM ( S )  L m ( S / G )
BM(S) and SM(S) conflicting, i.e., reducing one may
increase the other
Modular Control
Supervisor S combines the actions
of two or more supervisors, e.g.,
S1 and S2
S mod 12 ( s )  S 1 ( s )  S 2 ( s )
L ( S mod 12 / G )  L ( S 1 / G )  L ( S 2 / G )
L m ( S mod 12 / G )  L m ( S 1 / G )  L m ( S 2 / G )
We can always build R = R1  R2, but the point is
to use R1 and R2 and take the active event sets of
both at their respective states after execution of s
Modular Control Example: Dining
Philosophers
Philosopher i picks up for j is controllable
Philosopher putting down fork is uncontrollable
Remember there is only one marked state
Design two supervisors: one for each fork
(1T,
2f
Modular Control Example: Dining
Philosophers
Modular supervisor Smod12 = R1  R2  G
Did not cover
Unobservability
Decentralized Control
Modeling of Continuous
Dynamic Systems
The Bond Graph
Bond Graph Methodology
From Systems Dynamics
•formal and systematic method for modeling physical systems
•forces one to make explicit: issues about system functionality
and behavior assumptions
•unlike other modeling schemes…
directly grounded in physical reality…
1-1 correspondence with components and mechanisms of the
physical system modeled…
(as opposed to formal languages, such as logic)
Bond Graphs… Modeling Language
(Ref: physical systems dynamics – Rosenberg and Karnopp, 1983)
NOTE: The Modeling Language is domain independent…
Bond
Connection to enable Energy Transfer among
components
e
B
A
f
(directed bond from A to B).
each bond: two associated variables effort, e
flow, f
Bond Graphs
•modeling language (based on small number of primitives)
•dissipative elements: R
•energy storage elements: C, I
•source elements: Se, Sf
•Junctions: 0, 1
physical system
mechanisms
R
forces you to make assumptions
explicit
C, I
Se, Sf 0,1
uniform network – like representation:
domain indep.
Generic Variables:
Signals
effort, e
flow, f
NOTE: power = effort × flow.
energy = (power) dt.
elec.
voltage
current
mechanical
force
velocity
state/behavior of system: energy transfer between components…
rate of energy transfer = power flow
Energy Varibles
momentum, p= e dt : flux, momentum
displacement, q =  f dt : charge, displacement
Examples:
Mechanics
Effort
Force, F
Flow
Velocity, V
Power
FxV
Electricity
Voltage, V
Current, I
VxI
VI
Hydraulic
(Acoustic)
Pressure, P
Volume
flow rate
(Q)
PxQ
PQ
ThermoTemperature,
dynamics
T
Entropy
Q
flow rate

S
(thermal flow rate)
Pseudo
Energy
F. V.
Q

Q
```