CLASS PPT_230623_192915.pdf Co-reachable states

.

1. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Labelled Automata

2. Prof. Luca Ferrarini 2
Robot isnotdoing
anything(idle)
Now, weld!
Automaton –intuitive example

3. Prof. Luca Ferrarini 3
Now, weld!
Automaton –intuitive example

4. Prof. Luca Ferrarini 4
weld
Automaton –intuitive example

5. Prof. Luca Ferrarini 5
Robot
idle
Robot
welding
«weld»
•States
•Transitions
Automaton –graphical representation

6. Prof. Luca Ferrarini 6
q0q0 q1q1
a
states
event
•Statesare describedby names
•Events(associatedto transitions) are identifiedby letters
or «labels» («labelled» automata)
Automaton –intuitive idea

7. Prof. Luca Ferrarini 7
A (deterministic) finite state automatonA is described by a 4-
tuple A = (Q
A
,Σ
A
,i
A
,
A
) where:
•Q
A
is the finite set of states;
•Σ
A
is a finite set of events called alphabet;
•i
A
is the initial state (
? ?
)
•
?? ? ?
is the transition function that describes, for a
state and an event, the state that the automaton occupies
after the occurrence of that event (the transition).
Automaton –formal definition

8. Prof. Luca Ferrarini 8
•A sequenceof eventsiscalled trace
•A stringisa trace thatstartsfrom the initialstate
•Oftenin literature trace and stringare usedassynonyms
•The languageL(A) isthe set of allexecutablestringsof the
automatonA
Language

9. •Q
A
= {q0, q1, q2, q3}
•Σ
A
= {a, b, c}
•i
A
= q0
•
A
= {
((q0,a), q1), ((q1,b), q2), ((q1,c), q3
)
}
•L(A) = {ε, a, ab, ac}
Prof. Luca Ferrarini 9
AutomatonA
:
the eventε is the null event, and it
corresponds to “do nothing”
Example (1)
q0q0
q1q1
q3q3
q2q2

10. •Q
B
= {q0, q1, q2}
•Σ
B
= {a, b}
•i
B
= q0
•
B
= {(
(q0,a), q1), ((q1,b), q2), ((q2,a),q0)
}
•L(B) = {ε, a, ab, aba, abaa,
abaab,…}
Prof. Luca Ferrarini 10
AutomatonB
:
Example (2)
q0q0
q1q1
q2q2
The language is infinite,
even if the automaton is finite!

11. •Q
B
= {q0, q1, q2}
•Σ
B
= {a, b}
•i
B
= q0
•
B
= {(
(q0,a), q1), ((q1,b), q2), ((q2,a),q0)
}
•L(B) = {ε, a, ab, aba, abaa,
abaab,…}
•L(B) = {(aba)*, (aba)*a, (aba)*ab}
Prof. Luca Ferrarini 11
AutomatonB
:
Example (2)
q0q0
q1q1
q2q2
Notation * = infinite repetitions
(aba)* = (ε, aba, abaaba, …)

12. Reachable states
Prof. Luca Ferrarini 12
A state isreachableiff it ispossibleto reachitstarting from the
initialstate.
q0q0
q1q1
q3q3
q2q2
q4q4
q5q5

13. Reachable states
Prof. Luca Ferrarini 13
A state isreachableiff it ispossibleto reachitstarting from the
initialstate.
q0q0
q1q1
q3q3
q2q2
q4q4
q5q5
q4 and q5 are
unreachablestates

14. Reachable states
Prof. Luca Ferrarini 14
A state isreachableiff it ispossibleto reachitstarting from the
initialstate.
q0q0
q1q1
q3q3
q2q2
Unreachable states can be eliminated, but the alphabet remains
the same (Σ= {a, b, c, d, e})
… howcouldthisbe possible? And whatfor?

15. Accessible automaton
An accessibleautomaton is an automaton made only of
reachable states.
The accessibility function Ac(A) is a function that gives back an
automaton made only of the reachable states of the original
automaton A.
Prof. Luca Ferrarini 15
Ac(A)

16. Concatenation between alphabets
Concatenationbetween two alphabets Σ
1
and Σ
2
is an
operation that creates all possible couples of events taking one
event from the first alphabet and one from the second alphabet:
Σ
1
Σ
2
= { σ
1
σ
2
| σ
1
Σ
1
σ
2
Σ
2
}
It is possible to concatenate an alphabet with itself:
ΣΣ= Σ
6
= { σσ| σΣ }
Given an alphabet Σ, the Kleeneoperation (Kleene closure) is
defined as:
∗ g
?
g@4
with
4
ε
Prof. Luca Ferrarini 16

17. Language –formal definition
Prof. Luca Ferrarini 17
Given an automaton A = (Q
A
,Σ
A
,i
A
,
A
), its language L(A) can
be defined as follows:
where
?
∗
is the Kleene closure of the alphabet Σ
A.

18. Properties of the language
Prof. Luca Ferrarini 18
Givenan automatonA = (Q
A
,Σ
A
,i
A
,
A
) we can write the
following properties of its language L(A):
•L(A)Σ
A
∗
•Q
A
= L(A) = (trivialcase)
•Q
A
L(A) (L(A) = {ε} is the minimum possible
language)
•L(A) is prefix-closed

19. Properties of the language
Prof. Luca Ferrarini 19
Prefix
Givenastringσ,aprefixisasubstringofσ,ofanylength,
formedbytheleadingeventsofσ,soitisformedbytheevents
thatoccuratthebeginning,ontheleft-handside,ofσ.
Similarly,isthesetofallpossibleprefixesofσ.
Ex.σ=abc ={ε,a,ab,abc}
•A language L is prefix-closediffσL L
e.g., L(A) = {ε, a, ab, abb, abbc, abbca, abbcac, abbcb}

20. Sub-automaton
Given two automata A and B, we say that A is a sub-automaton
of B (AB) iff the following four conditions hold:
1.Q
A
Q
B
2.Σ
A
=Σ
B
3.i
A
=i
B
A B
Prof. Luca Ferrarini 20
A
B
Σ
A
={a,b,c}
Σ
B
={a,b,c}

21. Example
Prof. Luca Ferrarini 21
•A
•B
q0q0 q1q1 q2q2
x1x1 x2x2
Given the above two automata A and B with Σ
A
=Σ
B
, is B a sub-
automaton of A (BA)?

22. Example
Prof. Luca Ferrarini 22
•A
•B
q0q0 q1q1 q2q2
x1x1 x2x2
Given the above two automata A and B with Σ
A
=Σ
B
, is B a sub-
automaton of A (BA)?
YES! The names of the states are not important! What is
important is the following: the alphabetsand the transition
functions (structure) of the automata

23. Extension of the sub-automaton definition
Prof. Luca Ferrarini 23
•A
•B
q0q0 q1q1 q2q2
x1x1 x2x2
The sub-automata relation could also be defined by the
existence of a suitable injective function f, as follows:
f: Q
A
Q
B
such that s L(A) and s L(B), f(
A
(i
A
,s))=
B
(i
B
,s)
This definition places no restrictions on states names.
The state-space of a sub-automaton needs not be a subsetof
the super-automaton state-space.

24. Extension of the sub-automaton definition
Prof. Luca Ferrarini 24
•A
•B
q0q0 q1q1 q2q2
x1x1 x2x2
The sub-automata relation could also be defined by the
existence of a suitable injective function f,as follows:
f: Q
A
Q
B
such that s L(A) and s L(B), f(
A
(i
A
,s))=
B
(i
B
,s)
This definition places no restrictions on states names.
The state-space of a sub-automaton needs not be a subset of
the super-automaton state-space.
f f
No lossof generality!

25. Properties of sub-automata
•Reflexive:
•Transitive:
Prof. Luca Ferrarini 25

26. Equality
Prof. Luca Ferrarini 26
Structural(or Strong) equality(isomorphism):
Language (or Weak) equality:
??
Strong equalityWeakequality
Wewilluse onlystructuralequality.

27. Properties of equality
Prof. Luca Ferrarini 27
•Reflexive:
•Symmetric:
•Transitive:
N.B. Remember! The names of the states are not important

28. Synchronous composition
Given two
automata A = (Q
A
,Σ
A
,i
A
,
A
) and B = (Q
B
,Σ
B
,i
B
,
B
)
the synchronous composition (AB) of the two automata is
defined as a third automaton C = (Q
C
,Σ
C
,i
C
,
C
) where:
•Q
C
= Q
A
Q
B
•Σ
C
= Σ
A
Σ
B
•i
C
= (i
A
, i
B
)
?
?? ?? ? ?
?? ? ? ?
??? ? ?
Prof. Luca Ferrarini 28

29. Synchronous composition
Let’s now analyze 4 simple examples, playing a bit with
alphabets
Prof. Luca Ferrarini 29

30. Example (1)
Prof. Luca Ferrarini 30
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
It is impossible to compute!
We need alphabets first!
Compute the synchronous composition (5 minutes)
A
B

31. Example (1)
Prof. Luca Ferrarini 31
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
Σ
B
= {a, b, c}
L(B) ={ε, a, ab, abc}
Σ
A
={a, b}
L(A) ={ε, a, ab}
A
B

32. Example (1)
Prof. Luca Ferrarini 32
q0,x0q0,x0 q1,x0q1,x0 q2,x0q2,x0
Σ
B
= {a, b, c}
L(B) ={ε, a, ab, abc}
Σ
A
={a, b}
L(A) ={ε, a, ab}
q0,x1q0,x1 q1,x1q1,x1 q2,x1q2,x1
q0,x2q0,x2 q1,x2q1,x2 q2,x2q2,x2
q0,x3q0,x3 q1,x3q1,x3 q2,x3q2,x3
… too long…
let‘scompute directly
the accessiblepart!
Let’s start with
Q
C
= Q
A
Q
B

33. Example (1)
Prof. Luca Ferrarini 33
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
A
B
AB:
??????
?
:^
??????
?
??????
?
,??????, ??????
?
??????
?
,?????? if ??????∈??????
?
∩??????
?
??????
?
??????
?
,??????,??????
?
if ??????∈??????
?
−??????
?
??????
?
, ??????
?
??????
?
,?????? if ??????∈??????
?
−??????
?

34. Example (1)
Prof. Luca Ferrarini 34
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
A
B
AB:
(q1, x1)
??????
?
:^
??????
?
??????
?
,??????, ??????
?
??????
?
,?????? if ??????∈??????
?
∩??????
?
??????
?
??????
?
,??????,??????
?
if ??????∈??????
?
−??????
?
??????
?
, ??????
?
??????
?
,?????? if ??????∈??????
?
−??????
?

35. Example (1)
Prof. Luca Ferrarini 35
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
A
B
AB:
a
b?
(q1, x1)
??????
?
:^
??????
?
??????
?
,??????, ??????
?
??????
?
,?????? if ??????∈??????
?
∩??????
?
??????
?
??????
?
,??????,??????
?
if ??????∈??????
?
−??????
?
??????
?
, ??????
?
??????
?
,?????? if ??????∈??????
?
−??????
?

36. Example (1)
Prof. Luca Ferrarini 36
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
A
B
AB:
a
c?
b?
(q1, x1)
NO!
??????
?
:^
??????
?
??????
?
,??????, ??????
?
??????
?
,?????? if ??????∈??????
?
∩??????
?
??????
?
??????
?
,??????,??????
?
if ??????∈??????
?
−??????
?
??????
?
, ??????
?
??????
?
,?????? if ??????∈??????
?
−??????
?

37. Example (1)
Prof. Luca Ferrarini 37
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
A
B
AB:
??????
?
:^
??????
?
??????
?
,??????, ??????
?
??????
?
,?????? if ??????∈??????
?
∩??????
?
??????
?
??????
?
,??????,??????
?
if ??????∈??????
?
−??????
?
??????
?
, ??????
?
??????
?
,?????? if ??????∈??????
?
−??????
?

38. Example (1)
Prof. Luca Ferrarini 38
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
b
A
B
AB:
??????
?
:^
??????
?
??????
?
,??????, ??????
?
??????
?
,?????? if ??????∈??????
?
∩??????
?
??????
?
??????
?
,??????,??????
?
if ??????∈??????
?
−??????
?
??????
?
, ??????
?
??????
?
,?????? if ??????∈??????
?
−??????
?

39. Example (1)
Prof. Luca Ferrarini 39
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
b
(q2, x2)
A
B
AB:
??????
?
:^
??????
?
??????
?
,??????, ??????
?
??????
?
,?????? if ??????∈??????
?
∩??????
?
??????
?
??????
?
,??????,??????
?
if ??????∈??????
?
−??????
?
??????
?
, ??????
?
??????
?
,?????? if ??????∈??????
?
−??????
?

40. Example (1)
Prof. Luca Ferrarini 40
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
b
(q2, x2)
c
A
B
AB:
??????
?
:^
??????
?
??????
?
,??????, ??????
?
??????
?
,?????? if ??????∈??????
?
∩??????
?
??????
?
??????
?
,??????,??????
?
if ??????∈??????
?
−??????
?
??????
?
, ??????
?
??????
?
,?????? if ??????∈??????
?
−??????
?

41. Example (1)
Prof. Luca Ferrarini 41
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
b
(q2, x2)
c
(q2, x3)
A
B
AB:
??????
?
:^
??????
?
??????
?
,??????, ??????
?
??????
?
,?????? if ??????∈??????
?
∩??????
?
??????
?
??????
?
,??????,??????
?
if ??????∈??????
?
−??????
?
??????
?
, ??????
?
??????
?
,?????? if ??????∈??????
?
−??????
?

42. Example (1)
Prof. Luca Ferrarini 42
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
b
(q2, x2)
c
(q2, x3)
A
B
AB:
Σ
A||B
= Σ
A
Σ
B
= {a, b, c} L(AB) ={ε, a, ab, abc} = L(B)

43. Example (2)
Prof. Luca Ferrarini 43
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
A
B
Σ
B
= {a, b, c}
L(B) ={ε, a, ab, abc}
Σ
A
={a, b, c}
L(A) ={ε, a, ab}

44. Example (2)
Prof. Luca Ferrarini 44
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
A
B
AB:

45. Example (2)
Prof. Luca Ferrarini 45
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
A
B
AB:

46. Example (2)
Prof. Luca Ferrarini 46
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
A
B
AB:

47. Example (2)
Prof. Luca Ferrarini 47
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
b
A
B
AB:

48. Example (2)
Prof. Luca Ferrarini 48
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
b
(q2, x2)
A
B
AB:

49. Example (2)
Prof. Luca Ferrarini 49
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2
(q0, x0)
a
(q1, x1)
b
(q2, x2)
A
B
AB:
Σ
A||B
= Σ
A
Σ
B
= {a, b, c} L(AB)= L(A)L(B) ={ε, a, ab} =L(A)
x3x3

50. Example (3)
Prof. Luca Ferrarini 50
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
A
B
Σ
B
= {a, b}
L(B) ={ε, a, ab, aba}
Σ
A
={a, b}
L(A) ={ε, a, ab, abb}
x3x3

51. Example (3)
Prof. Luca Ferrarini 51
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
A
B
AB:
x3x3

52. Example (3)
Prof. Luca Ferrarini 52
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
A
B
AB:
x3x3

53. Example (3)
Prof. Luca Ferrarini 53
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
A
B
AB:
x3x3

54. Example (3)
Prof. Luca Ferrarini 54
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
b
A
B
AB:
x3x3

55. Example (3)
Prof. Luca Ferrarini 55
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
(q0, x0)
a
(q1, x1)
b
(q2, x2)
A
B
AB:
x3x3

56. Example (3)
Prof. Luca Ferrarini 56
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2
(q0, x0)
a
(q1, x1)
b
(q2, x2)
A
B
AB:
Σ
A||B
= Σ
A
Σ
B
= {a, b} L(AB)= L(A)L(B) ={ε, a, ab}
L(A), L(B)
x3x3
x3x3

57. Example (4)
Prof. Luca Ferrarini 57
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2 x3x3
A
B
Σ
B
= {a, b, c}
L(B) ={ε, a, ab, aba}
Σ
A
={a, b, c}
L(A) ={ε, a, ab, abb}
x3x3

58. Example (4)
Prof. Luca Ferrarini 58
q0q0 q1q1 q2q2
x0x0 x1x1 x2x2
(q0, x0)
a
(q1, x1)
b
(q2, x2)
A
B
AB:
Σ
A||B
= Σ
A
Σ
B
= {a, b} L(AB)= L(A)L(B) ={ε, a, ab}
L(A), L(B)
x3x3
x3x3

59. Observation
For shared events, the syncronous composition between A and
B extracts the common behaviour(that is, the common strings)
between the two automata operands A and B.
That is, an event in the alphabet of A and B is executed only if
both automata agree to execute it.
However, if an event is defined in only one alphabet, this is
accepted by the synchronous composition.
Prof. Luca Ferrarini 59

60. Observation
Special case: the two automata share the same alphabet, the
syncronous composition just extracts the common strings of the
two automata.
Mathematically, this means that the synchronous composition
computes the intersectionof the two languages.
if Σ
A
=Σ
B
then L(AB)= L(A)L(B)
If we want to forbid an event in the execution of a synchronous
composition between automata, the event must be contained in
each alphabet.
Prof. Luca Ferrarini 60

61. Propertiesof the synchronouscomposition
•Idempotent: A AA
•Commutative:A BBA
•Associative: A BC)(AB)CABC
•AB ABA
Prof. Luca Ferrarini 61

62. Refinement
GiventwoautomataA and B, itissaidthatA refinesB iffthe
synchronous composition between A and B is equal to A:
If A refines B, then Σ
B
Σ
A
because:ABA Σ
A
Σ
B
Σ
A
Σ
B
Σ
A
Prof. Luca Ferrarini 62

63. Propertiesof the refinement
•Reflexive:
•Antisimmetric:
•Transitive:
•
•
Prof. Luca Ferrarini 63

64. Example
Prof. Luca Ferrarini 64

65. Example
Prof. Luca Ferrarini 65

66. Example
Prof. Luca Ferrarini 66

67. Example
Prof. Luca Ferrarini 67
q0q0
q1q1
q2q2
q3q3
q4q4
q5q5
q7q7
q6q6
q8q8

68. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Automata Extensions

69. Prof. Luca Ferrarini 2
A marked state is a state that is more important than others and
that we want to use as target. Typically, it represents the
completion of a task or the achievement of a goal.
An automaton A with marked states (marked automaton) is
described by a 5- tuple A = (Q
A, Σ
A, i
A, δ
A, M
A) where the
extension of the formal definition of automaton is the set of
marked states M
A⊆Q
A.
Extension 1: marked states
q0 q1 q2
q3
q5
q4
Q
A= {q0, q1, q2, q3, q4, q5}
M
A= {q3, q4, q5}

70. Prof. Luca Ferrarini 3
Given a marked automaton A = (Q
A, Σ
A, i
A, δ
A, M
A), the marked
language Lm(A) is the subset of the automaton language made
of all the strings that reach a marked state:
N.B. The marked language is not necessarily prefix-closed.
Marked language
????????????????????????????????????=????????????∈ |????????????????????????????????????
????????????????????????
????????????,????????????∈????????????
????????????

71. Properties of the marked language
Prof. Luca Ferrarini 4
•Lm(A)⊆L(A)
•Q
A= ∅⇒Lm(A) = ∅•????????????
????????????∈????????????
????????????⇔????????????∈????????????????????????????????????
•Lm(A) is (in general) NOT prefix-closed

72. Prof. Luca Ferrarini 5
A state is co-reachableiff (starting from that state) it is possible
to reach a marked statethrough a trace s:
Co-reachable states
????????????∈????????????
????????????is co-reachable ⇔∃s∈????????????
????????????
∗| ????????????
????????????
????????????,????????????∈????????????
????????????

73. Example
Prof. Luca Ferrarini 6
Observations:
•L(A) is prefix-closed, but Lm(A) is not prefix-closed
•q4 is not reachable, but it is co- reachable
•????????????∉????????????????????????????????????because q0∉M
A
q0
q2 q5
q3q1
q4
M
A = {q3}
L(A) = {ε, a, b, ac, ad, bc, bd}
Lm(A) = {ac, ad, bc}

74. Co-accessible automaton
A co-accessibleautomaton is an automaton made only of co-
reachable states.
The co-accessibility function Co(A) is a function that extracts
only the co- reachable part of the automaton A (a sub- automaton
of A made only of co- reachable states).
Prof. Luca Ferrarini 7
Co(A)

75. Trim
An automaton is said to be trimiff it is both accessible and co-
accessible.
The operation of removing states and transitions from an initial
automaton A to make it trim is called trimmingand the resulting
automaton is denoted as Tr(A).
Prof. Luca Ferrarini 8
Tr(A)

76. Example
Prof. Luca Ferrarini 9
L(A) = {ε, a, b, ac, ad, bd, bc}
Lm(A) = {ac, ad, bc}
L(Tr(A)) = {ε, a, b, ac, ad, bc}≠L(A)
Lm(Tr(A)) = {ac, ad, bc} = Lm(A)

77. Observation
The language of a trim has the following property:
????????????Tr????????????=????????????????????????????????????
where ????????????????????????????????????is the set of all prefixes of the marked language
of the automaton A.
Example:
Lm(A) = {ac, ad, bc}
L(Tr(A)) = {ε, a, b, ac, ad, bc}= ????????????????????????????????????
Note: if ????????????????????????=????????????????????????????????????then the automaton A is a trim.
Prof. Luca Ferrarini 10

78. Non-marked counterpart
Given a marked automaton A = (Q
A, Σ
A, i
A, δ
A, M
A), the
automaton defined as (Q
A, Σ
A, i
A, δ
A) is called the non-marked
counterpart of A (nmcp(A)), as it does not specify the set of
marked states M
A.
Note that, if not specified, the set of marked states is equal to the
set of states:
(Q
A, Σ
A, i
A, δ
A) ≅(Q
A, Σ
A, i
A, δ
A, Q
A)
⇒M
A= Q
A(not M
A=∅)
Prof. Luca Ferrarini 11

79. Sub-automaton (extension 1)
Given the two marked automata Aand B, A is a sub-automaton
of B (A≤ B) iff:
1.nmcp(A) ≤nmcp(B)
2.M
A⊆M
B
Prof. Luca Ferrarini 12
(ΣA=ΣB)
A B
Example:

80. Equality (extension 1)
Prof. Luca Ferrarini 13
Strong equality(isomorphism):
A=B⇔????????????≤????????????∧B≤A
Weakequality(languageequality):
A=B⇔(????????????
????????????=????????????
????????????)∧
(????????????????????????=????????????(????????????))∧(????????????????????????????????????=????????????????????????(????????????))
Strong equality⇒Weakequality

81. Synchronous composition (extension 1)
Given two marked automata A and B, their synchronous
composition (A‖B) is performed the same way as if they were
non-marked automata. The only difference is that a state will be
a marked state in the resulting automaton A||B only if boththe
corresponding states of A and B are marked states:
A‖B= (Q
A×Q
B, Σ
A∪Σ
B, (i
A, i
B), ????????????
????????????||????????????,M
A||B)
M
A||B=M
A×M
B
Prof. Luca Ferrarini 14
Observation: no changes in the definition of the refinement occur

82. Prof. Luca Ferrarini 15
A forbidden state is a state that we want to avoid during the
execution.
A marked automaton A can be extended with forbidden states by
defining it as 6- tuple A = (Q
A, Σ
A, i
A, δ
A, M
A, X
A), where X
A⊆Q
A
is the set of forbidden states.
Extension 2: forbidden states
q0 q1 q2
q3
q5
q4
Q
A= {q0, q1, q2, q3, q4, q5}
M
A= {q4, q5}
X
A= {q3}

83. Prof. Luca Ferrarini 16
Given an automaton A = (Q
A, Σ
A, i
A, δ
A, M
A, X
A), the forbidden
language Lx(A) is the subset of the automaton language made
of all the strings that pass through forbidden states:
where ̅????????????is the set of prefixes of s.
Example: s = abc, ̅????????????= {ε, a, ab, abc}
Forbidden language
????????????????????????????????????=????????????∈ |????????????(????????????)????????????
????????????????????????
????????????,̅????????????∩????????????
????????????≠∅

84. Prof. Luca Ferrarini 17
The primed language is the language that avoids the forbidden
states:
L’(A) = L(A) –Lx(A)
The marked primed language is the language that allows to
reach the marked states without passing through forbidden
states:
Lm’(A) = Lm(A) –Lx(A)
Primed languages

85. Example
Prof. Luca Ferrarini 18
q0
q2 q5
q3q1
q4
Q
A = {q0, q1, q2, q3, q4, q5}
M
A = {q3}
X
A = {q2}Lm(A) = {ac, ad, bc}
Lx(A) = {b, bc, bd}
Lm’(A) = Lm(A) –Lx(A) = {ac, ad}

86. Prof. Luca Ferrarini 19
•Lx(A)⊆L(A)
•Q
A= ∅⇒Lx(A) = ∅
•????????????
????????????∈????????????
????????????⇔
LxA=LA⇒L
′
A=Lm′(A)=∅
Properties of the forbidden language

87. Purging
The operation of removing forbidden states is called purgingand
the resulting automaton is denoted as Pu(A).
Prof. Luca Ferrarini 20
Pu(A)
L’(A) = {ε, a, ab, abc, abd}
Lm’(A) = {abc, abd}
L’(Pu(A)) = {ε, a, ab, abc, abd}
Lm’(Pu(A)) = {abc, abd}

88. Observations
•The purging operation does not change the primed languages:
L’(Pu(A)) = L’(A) = L(A) –Lx(A)
Lm’(Pu(A)) = Lm’(A) = Lm(A) –Lx(A)
•The forbidden language of Pu(A) is the empty set:
Lx(Pu(A)) = ∅
Prof. Luca Ferrarini 21

89. Non-forbidden counterpart
Given an automaton A = (Q
A, Σ
A, i
A, δ
A, M
A, X
A), the automaton
defined as (Q
A, Σ
A, i
A, δ
A, M
A) is called the non-forbidden
counterpart of A (nfcp(A)), as it does not specify the forbidden
states.
Note that, if not defined, the set of forbidden states is equal to
the empty set:
(Q
A, Σ
A, i
A, δ
A, M
A) ≅(Q
A, Σ
A, i
A, δ
A, M
A, ∅)
⇒X
A= ∅
Prof. Luca Ferrarini 22

90. Sub-automaton (extension 2)
Given the two automata with forbidden states Aand B, A is a
sub-automatonof B (A≤ B) iff:
1.nfcp(A) ≤nfcp(B)
2.
X
B⊆X
A(that is ????????????
′
????????????⊆????????????
′
????????????,????????????
????????????
′
????????????⊆????????????????????????
′
????????????)
Example:
Prof. Luca Ferrarini 23
A B

91. Equality (extension 2)
Prof. Luca Ferrarini 24
Strong equality(isomorphism):
A=B⇔????????????≤????????????∧B≤A
Weakequality(languageequality):
A=B⇔(????????????
????????????=????????????
????????????)
∧????????????????????????=????????????????????????∧????????????????????????????????????=????????????????????????????????????∧
∧(????????????????????????????????????=????????????????????????(????????????))
Strong equality⇒Weakequality

92. Synchronous composition (extension 2)
Given two automata A and B with forbidden states, their
synchronous composition (A‖B)is performed the same way as if
they were automata without forbidden states. The only difference
is that a state will be a forbidden state in the resulting automaton
A||B only if at least oneof the corresponding states of A and B
is a forbidden state:
A‖B= (Q
A×Q
B, Σ
A∪Σ
B, (i
A, i
B), ????????????
????????????||????????????,M
A×M
B,X
A||B)
X
A||B=(Q
A×X
B)∪(X
A×Q
B)
Prof. Luca Ferrarini 25
Observation: no changes in the definition of the refinement occur

93. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Labelled Petri Nets

94. Introduction
Labelled automata are a powerful formalism used for modeling
the plant and the synthesisof the supervisor.
Labelled Petri nets are an alternative framework that can be
used for modelingonly, because they allow to represent infinite
states systemsand concurrent systems(composed of different
sub-systems working together).
Prof. Luca Ferrarini 2

95. Petri nets structure
A Petri netis a bipartite graph made of two node types:
•Places (P)
•Transitions (T)
Assumptions:
1.A node can be eithera place ora transition
2.There is at leastone node
Prof. Luca Ferrarini 3

96. Flow relation
The flow relationassociatesa place to a transitionor a transition
to a place:
Prof. Luca Ferrarini 4

97. Weighting and marking functions
Prof. Luca Ferrarini 5
Marking function:
Weighting function:

98. Weighting and marking functions
Prof. Luca Ferrarini 6
Marking function:
Weighting function:

99. Evolution rules
1.Transition t enabled:
2.Transition t fires(if enabled):
Prof. Luca Ferrarini 7
Notes:
•t isthe set of input placesof the transitiont
•tisthe set of output placesof the transitiont
•M’(p) isthe new markingafter the firing
•IfW(t, p) or W(p, t) doesnotexist, thenitisconsideredzero

100. Example (1)
Prof. Luca Ferrarini 8
Note: ifnotspecified, the weightingfunctionisequalto 1

101. Prof. Luca Ferrarini 9
5 55
Example (1)

102. Prof. Luca Ferrarini 10
5 55
6 65
enabled
Example (1)

103. Prof. Luca Ferrarini 11
fires
?
5 5 55

55
?
6 6 56

65
?
7 7 57

75
Example (1)

104. Prof. Luca Ferrarini 12
fires
?
5
?
6
?
7
Example (1)

105. Prof. Luca Ferrarini 13
Observations:
•The numberof marks(tokens) isnotpreserved
•Firingisinstantaneous
Example (1)

106. Example (2) –Self loop
Prof. Luca Ferrarini 14

107. Example (2) –Self loop
Prof. Luca Ferrarini 15
5 55
6 65
enabled

108. Example (2) –Self loop
Prof. Luca Ferrarini 16
fires
?
5
?
6
?
7

109. Example (2) –Self loop
Prof. Luca Ferrarini 17

110. Asynchronous behaviour
If multiple transitions are enabled, only one can fire at a time
and it is chosen randomly(non-deterministic behaviour).
Therefore, a single Petri net represents many different possible
evolutionsof the system.
Prof. Luca Ferrarini 18

111. Example –Asynchronous behaviour
Prof. Luca Ferrarini 19
t1 and t2 are enabled

112. Prof. Luca Ferrarini 20
t1 fires: t2 fires:
Example –Asynchronous behaviour

113. Prof. Luca Ferrarini 21
t1 and t3 are enabled t4 isenabled
Example –Asynchronous behaviour

114. Prof. Luca Ferrarini 22
t1 fires: t3 fires: t4 fires:
Example –Asynchronous behaviour

115. Prof. Luca Ferrarini 23
Theseare 3 differentpossibleevolutionsof the samePetri net,
after2 firings.
Example –Asynchronous behaviour

116. Infinite states systems representation
A discrete event systemcan be modeled by Petri nets where the
marks distributed in the placesrepresent the statesof the
system and the transitionsrepresent the change of state (so…
“transitions”!).
The power of Petri nets is in the possibility to represent infinite
state systems with a finite graph (which would not be possible
with automata, because we would have to draw infinite states):
Prof. Luca Ferrarini 24

117. Cuncurrent systems representation
Another advantage of Petri nets over automata is the possibility
to represent concurrent systems(systems composed of
different sub-systems working together) in a simple way, while
using automata it is not possible:
Prof. Luca Ferrarini 25
q0q0
q1q1
q2q2
Isita choiceor a parallelism?

118. Modeling structures
Sequence:
Firing of t1
enables t2
Prof. Luca Ferrarini 26
Choice
(alternative/conflict):
Firing of t1 disables t2
Parallelism:
Firing of t1 has
no effect on t2

119. Modeling structures
End of choice:
Prof. Luca Ferrarini 27
Start of parallelism:End of parallelism
(synchronization):
Importantrule: everytime youopen a choice/parallelism,
remember to closeit(to avoidwrongbehaviour of the net).

120. Example (1) –Correct
Prof. Luca Ferrarini 28
Start of parallelism
End of parallelism
Start of choice
End of choice

121. Example (1) –Correct
Prof. Luca Ferrarini 29

122. Example (1) –Correct
Prof. Luca Ferrarini 30

123. Example (1) –Correct
Prof. Luca Ferrarini 31

124. Example (1) –Correct
Prof. Luca Ferrarini 32

125. Example (1) –Correct
Prof. Luca Ferrarini 33

126. Example (1) –Correct
Prof. Luca Ferrarini 34

127. Example (2) –Wrong
Prof. Luca Ferrarini 35
Start of choice
End of parallelism

128. Example (2) –Wrong
Prof. Luca Ferrarini 36

129. Example (2) –Wrong
Prof. Luca Ferrarini 37

130. Example (2) –Wrong
Prof. Luca Ferrarini 38
Blockingbehaviour!
The transitioncannotfire

131. Example (3) –Wrong
Prof. Luca Ferrarini 39
End of choice
Start of parallelism

132. Example (3) –Wrong
Prof. Luca Ferrarini 40

133. Example (3) –Wrong
Prof. Luca Ferrarini 41

134. Example (3) –Wrong
Prof. Luca Ferrarini 42

135. Example (3) –Wrong
Prof. Luca Ferrarini 43

136. Example (3) –Wrong
Prof. Luca Ferrarini 44

137. Example (3) –Wrong
Prof. Luca Ferrarini 45

138. Example (3) –Wrong
Prof. Luca Ferrarini 46

139. Example (3) –Wrong
Prof. Luca Ferrarini 47

140. Example (3) –Wrong
Prof. Luca Ferrarini 48
An infinite
amountof marks
are generated!

141. Labelled Petri nets
A labelled Petri netis a Petri net in which each transition is
associated to a label:
PN = (P, T, F, M, W, Σ, f)
where:
•P, T are respectively the set of places and the set of
transitions;
•F is the flow relation;
•M, W are respectively the marking functionand the weighting
function;
•Σ is the alphabet;
•f: TΣ is a function that associates transitions with events
(labels) in the alphabet
Prof. Luca Ferrarini 49

142. Example
Prof. Luca Ferrarini 50
Σ = {a, b}
L(PN) = {ε, a, ab, aa}
N.B. The names of the
transitions(t1, t2, t3) are
univoqueby definition
becausetheyreferto a precise
object (thattransition), while
labels (a, b) referto the
functional behaviour of the
Petri net and thereforethey
can be replicated(theyhave
physical meaning).

143. Synchronous composition
The synchronous compositionbetween two labelled Petri nets
(
56 5 6
) is obtained by the union of their places, and
with a special set of transitions(
56
) defined as follows:
consider
5656
•if
5 6
, then labels a transition in
56
with the same
input/output places
•if
6 5
, then labels a transition in
56
with the same
input/output places
•if
56
, labels mtransition in
5
and nin
6
, then a
labels mntransitions in
56
, each of which has input/output
places as the union of input/output places of a transition of
5
and a transition of
6
Prof. Luca Ferrarini 51

144. Example (1) –Synchronous composition
Prof. Luca Ferrarini 52
The alphabets are comped of only executable events

145. Prof. Luca Ferrarini 53
Example (1) –Synchronous composition

146. Example (1) –Synchronous composition
Prof. Luca Ferrarini 54

147. Example (1) –Synchronous composition
Prof. Luca Ferrarini 55

148. Example (1) –Synchronous composition
Prof. Luca Ferrarini 56

149. Example (1) –Synchronous composition
Prof. Luca Ferrarini 57

150. Example (1) –Synchronous composition
Prof. Luca Ferrarini 58

151. Example (1) –Synchronous composition
Prof. Luca Ferrarini 59
Evolution

152. Example (1) –Synchronous composition
Prof. Luca Ferrarini 60
Evolution

153. Example (1) –Synchronous composition
Prof. Luca Ferrarini 61
Evolution
Blocked

154. Example (1) –Synchronous composition
Prof. Luca Ferrarini 62
Evolution

155. Example (1) –Synchronous composition
Prof. Luca Ferrarini 63
Evolution

156. Example (2) –Synchronous composition
Prof. Luca Ferrarini 64

157. Example (2) –Synchronous composition
Prof. Luca Ferrarini 65

158. Example (2) –Synchronous composition
Prof. Luca Ferrarini 66

159. Example (2) –Synchronous composition
Prof. Luca Ferrarini 67

160. Example (2) –Synchronous composition
Prof. Luca Ferrarini 68

161. Example (2) –Synchronous composition
Prof. Luca Ferrarini 69

162. Example (2) –Synchronous composition
Prof. Luca Ferrarini 70
Evolution: eventa

163. Example (2) –Synchronous composition
Prof. Luca Ferrarini 71
Evolution: eventa

164. Example (2) –Synchronous composition
Prof. Luca Ferrarini 72
Evolution: eventb

165. Example (2) –Synchronous composition
Prof. Luca Ferrarini 73
Evolution: eventb

166. Example (2) –Synchronous composition
Prof. Luca Ferrarini 74
Evolution: eventb
Blocked

167. Observation (1)
Like in the synchronouscompositionof labelledautomata, ifan
event iscontainedin boththe alphabets
5
and
6
, butitonly
appearsin one of the twoPetri nets, the event isblockedand
cannotbe executed.
Prof. Luca Ferrarini 75
5 6

168. Observation (2)
Like in the synchronouscompositionof labelledautomata, ifthe
twoPetri netsshare the samealphabet, the language of the
synchronouscompositionisthe intersectionbetweenthe two
languages.
Prof. Luca Ferrarini 76
5
ε
6
ε
7
ε

169. Prof. Luca Ferrarini 77
Example (3) –Synchronous composition
5 6

170. Prof. Luca Ferrarini 78
Example (3) –Synchronous composition
5 6

171. Reachability graph
Prof. Luca Ferrarini 79
M
0
M
0
4

172. Reachability graph
Prof. Luca Ferrarini 80
M
0
M
0
M
1
M
1
4 5

173. Reachability graph
Prof. Luca Ferrarini 81
M
0
M
0
M
1
M
1
M
2
M
2
4 5
6

174. Reachability graph
Prof. Luca Ferrarini 82
M
0
M
0
M
1
M
1
M
2
M
2
4 5
6

175. Reachability graph
Prof. Luca Ferrarini 83
4
M
0
M
0
M
1
M
1
5
6
M
2
M
2
M
3
M
3
7

176. Reachability graph
Prof. Luca Ferrarini 84
4
M
0
M
0
M
1
M
1
5
6
M
2
M
2
M
3
M
3
7

177. Reachability graph
Prof. Luca Ferrarini 85
M
0
M
0
M
1
M
1
M
2
M
2
4 5
6 7
M
3
M
3

178. Reachability graph
Prof. Luca Ferrarini 86
M
0
M
0
M
1
M
1
M
2
M
2
4 5
6 7
M
3
M
3

179. Reachability graph
Prof. Luca Ferrarini 87
M
0
M
0
M
1
M
1
M
2
M
2
4 5
6 7
M
3
M
3

180. Reachability graph
Prof. Luca Ferrarini 88
M
0
M
0
M
1
M
1
M
2
M
2
4 5
6 7
M
3
M
3
Observation:
the reachabilitygraphof
a labelledPetri net isa
labelledautomaton!

181. Property
Given two labelled Petri nets
5
and
6
, the following property
holds:
reach( ) = reach() reach()
where reach( . ) is the reachability graph.
Prof. Luca Ferrarini 89

182. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Plant Modeling

183. Prof. Luca Ferrarini 2
Problem statement: given a plant model (P) and a specification
on that model, synthetize a controller(supervisor) (C) in closed
loop with the plant such that the overall system satisfies as
much as possiblethe specification.
Introduction to the control problem
C P

184. Prof. Luca Ferrarini 3
Specifications can represent both the desired goalof the control
problem (positive specifications) or the constraints that the
plant should not break (negative specifications).
Specifications
C P SP≡

185. Prof. Luca Ferrarini 4
Specifications
C P SP≡
?
Observation: since both the plant and the specification are given,
it is not assured that the control (that must be designed) can
meet the specification. Maybe the specification be require “too
much” for the given plant.
Specifications can represent both the desired goalof the control
problem (positive specifications) or the constraints that the
plant should not break (negative specifications).

186. Prof. Luca Ferrarini 5
The plant is the target of our control problem and should
represent “no desires” at all:
•Non-marked(to mark the states is a matter of the
specification)
•Non-forbidden(to forbid the states is a matter of the
specification)
•Trim (the plant must be accessiblein order to be controlled)
•The alphabet Σ
Pmust contain onlyevents that are executable
by the plant
Modeling of the plant –automaton

187. Prof. Luca Ferrarini 6
It is easier to model separately each component of the plant
(e.g., robot, buffer, machining center), to then combine all the
modules using the synchronous composition:
??????=??????
1ฮ??????
2ฮ??????
3…ฮ??????
n
Modular approach

188. Prof. Luca Ferrarini 7
It is easier to model separately each component of the plant
(e.g., robot, buffer, machining center), to then combine all the
modules using the synchronous composition:
??????=??????
1ฮ??????
2ฮ??????
3…ฮ??????
n
Observation:
•If two or more modules do not have common events, they
work independently(e.g., two different machines that perform
different tasks in parallel)
•If two or more modules share the same alphabet, an event
can be executed either by all the modules together
(synchronization) or it is blocked
Modular approach

189. Prof. Luca Ferrarini 8
We learned two formalisms to model the plant:
•Automata (labelled)
•Petri nets (labelled)
In the next slides we will see how to use them.
Modeling of the plant
C P

190. Prof. Luca Ferrarini 9
Example 1 –plant modeling (automata)
Input
buffer
M1 M2
Output
buffer
AGV
The plant is composed of:
•Two machines (M1 and M2) that work one piece at a time
•An Automated Guided Vehicle (AGV) that performs load and
unload operations
•An input and an output buffer that store respectively raw
pieces and final products

191. Hypothesis:
•A raw piece is automatically loaded into M1 (we do not care
about the availability of raw pieces)
•The output buffer (unload station) has infinite capacity (we do
not care about output buffer getting full)
•The AGV moves pieces from M1 to M2 and from M2 to the
output buffer
Prof. Luca Ferrarini 10
Input
buffer
M1 M2
Output
buffer
AGV
Example 1 –plant modeling (automata)

192. Problem: model the behavior of the system using labelled
automata
We use a modular approach and we identify 3 different models:
M1, M2 and AGV (the buffers don’t need to be considered for the
hypotheses)
Prof. Luca Ferrarini 11
Input
buffer
M1 M2
Output
buffer
AGV
Example 1 –plant modeling (automata)

193. The possible events are:
•Load M1 (l1)
•Unload M1 (u1)
•Load M2 (l2)
•Unload M2 (u2)
•Load output buffer (lb)
Prof. Luca Ferrarini 12
Input
buffer
M1 M2
Output
buffer
AGV
Example 1 –plant modeling (automata)

194. Prof. Luca Ferrarini 13
M1 Q1 = {F1, O1}
Σ1 = {l1, u1}
i1 = F1
??????1 = {((F1,l1), O1), ((O1,u1), F1)}
L(M1) = {(l1 u1)*, (l1 u1)*l1}
F1 O1
F1 = M1 free
O1 = M1 occupied
Observation: thisisa syntheticmodelbecauseitdoesnottake
intoaccount the time neededfor the machiningof the piece
beforeM1 can be unloaded
Example 1 –plant modeling (automata)

195. Prof. Luca Ferrarini 14
M2
F2 O2
Q2 = {F2, O2}
Σ2= {l2, u2}
i2= F2
??????2 = {((F2,l2), O2), ((O2,u2), F2)}
L(M2) = {(l2 u2)*, (l2 u2)*l2}
F2 = M2 free
O2 = M2 occupied
Observation: thisisa syntheticmodelbecauseitdoesnottake
intoaccount the time neededfor the machiningof the piece
beforeM2 can be unloaded
Example 1 –plant modeling (automata)

196. Prof. Luca Ferrarini 15
AGV Q3 = {V, P1, P2}
Σ3= {u1, u2, l2, lb}
i3= V
??????3= {((V,u1), P1), ((V,u2), P2),
((P1,l2), V), ((P2,lb), V)}
L(AGV) = {((u1 l2)*(u2 lb)*)*,
((u1 l2)*(u2 lb)*)*u1,
((u1 l2)*(u2 lb)*)*u2}
P1 V P2
V = AGV idle(free)
P1 = AGV hasa piececoming from M1
P2 = AGV hasa piececoming from M2
Example 1 –plant modeling (automata)

197. Prof. Luca Ferrarini 16
The overallplantP can be modeledasthe synchronous
compositionof the 3 modulesM1, M2 and AGV:
P = M1||M2||AGV = (M1||M2)||AGV
Wecan first calculateM1||M2 and thenmake the synchronous
compositionwith the AGV.
Example 1 –plant modeling (automata)

198. Prof. Luca Ferrarini 17
M1||M2
F1F2 O1F2
F1O2 O1O2
Example 1 –plant modeling (automata)

199. Prof. Luca Ferrarini 18
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
M1||M2||AGV
Example 1 –plant modeling (automata)

200. Prof. Luca Ferrarini 19
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
M1||M2||AGV
Example 1 –plant modeling (automata)

201. Prof. Luca Ferrarini 20
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
Example 1 –plant modeling (automata)

202. Prof. Luca Ferrarini 21
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
O1F2P1
Example 1 –plant modeling (automata)

203. Prof. Luca Ferrarini 22
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
O1F2P1
Example 1 –plant modeling (automata)

204. Prof. Luca Ferrarini 23
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
O1F2P1
F1O2V
Example 1 –plant modeling (automata)

205. Prof. Luca Ferrarini 24
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
O1F2P1
F1O2V O1O2V
Example 1 –plant modeling (automata)

206. Prof. Luca Ferrarini 25
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
O1F2P1
F1O2V O1O2V
Example 1 –plant modeling (automata)

207. Prof. Luca Ferrarini 26
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
O1F2P1
F1O2V O1O2V
F1F2P2
Example 1 –plant modeling (automata)

208. Prof. Luca Ferrarini 27
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
O1F2P1
F1O2V O1O2V
F1F2P2 O1F2P2
Example 1 –plant modeling (automata)

209. Prof. Luca Ferrarini 28
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
O1F2P1
F1O2V O1O2V
F1F2P2 O1F2P2
Example 1 –plant modeling (automata)

210. Prof. Luca Ferrarini 29
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
M1||M2||AGV
O1F2P1
F1O2V O1O2V
F1F2P2 O1F2P2
Example 1 –plant modeling (automata)

211. Prof. Luca Ferrarini 30
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
M1||M2||AGV
O1F2P2
Example 1 –plant modeling (automata)

212. Prof. Luca Ferrarini 31
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
M1||M2||AGV
O1F2P2
Example 1 –plant modeling (automata)

213. Prof. Luca Ferrarini 32
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
M1||M2||AGV
O1F2P2
Example 1 –plant modeling (automata)

214. Prof. Luca Ferrarini 33
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
M1||M2||AGV
O1F2P2
Example 1 –plant modeling (automata)

215. Prof. Luca Ferrarini 34
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
M1||M2||AGV
O1F2P2
Example 1 –plant modeling (automata)

216. Prof. Luca Ferrarini 35
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
M1||M2||AGV
O1F2P2
F1O2P1
Example 1 –plant modeling (automata)

217. Prof. Luca Ferrarini 36
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
M1||M2||AGV
O1F2P2
F1O2P1
O1O2P1
Example 1 –plant modeling (automata)

218. Prof. Luca Ferrarini 37
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
M1||M2||AGV
Example 1 –plant modeling (automata)

219. Prof. Luca Ferrarini 38
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Mainproduction
cycle:
Example 1 –plant modeling (automata)

220. Prof. Luca Ferrarini 39
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Mainproduction
cycle:
1.Load M1
Example 1 –plant modeling (automata)

221. Prof. Luca Ferrarini 40
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Mainproduction
cycle:
1.Load M1
2.AGV unloads
M1
Example 1 –plant modeling (automata)

222. Prof. Luca Ferrarini 41
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Mainproduction
cycle:
1.Load M1
2.AGV unloads
M1
3.AGV loads M2
Example 1 –plant modeling (automata)

223. Prof. Luca Ferrarini 42
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Mainproduction
cycle:
1.Load M1
2.AGV unloads
M1
3.AGV loads M2
4.AGV unloads
M2
Example 1 –plant modeling (automata)

224. Prof. Luca Ferrarini 43
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Mainproduction
cycle:
1.Load M1
2.AGV unloads
M1
3.AGV loads M2
4.AGV unloads
M2
5.AGV loads
output buffer
Example 1 –plant modeling (automata)

225. Prof. Luca Ferrarini 44
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Mainproduction
cycle:
1.Load M1
2.AGV unloads
M1
3.AGV loads M2
4.AGV unloads
M2
5.AGV loads
output buffer
(cycleisrepeated)
Example 1 –plant modeling (automata)

226. Prof. Luca Ferrarini 45
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Second possible
cycle:
1.Load M1
2.AGV unloads
M1
3.Input buffer
loads M1
4.AGV loads M2
5.AGV unloads
M2
6.AGV loads
output buffer
(repeatfrom step 2)
Example 1 –plant modeling (automata)

227. Prof. Luca Ferrarini 46
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Third possible
cycle:
1.Load M1
2.AGV unloads
M1
3.AGV loads M2
4.Load M1
5.AGV unloads
M2
6.AGV loads
output buffer
(repeatfrom step 2)
Example 1 –plant modeling (automata)

228. Prof. Luca Ferrarini 47
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Fourthpossible
cycle:
1.Load M1
2.AGV unloads
M1
3.AGV loads M2
4.AGV unloads
M2
5.Load M1
6.AGV loads
output buffer
(repeatfrom step 2)
Example 1 –plant modeling (automata)

229. Prof. Luca Ferrarini 48
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
Deadlock!
Example 1 –plant modeling (automata)

230. Prof. Luca Ferrarini 49
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
The dedadlockis
causedby the fact
thatthe AGV is
occupiedwith a
product of M1 and
M2 isoccupied: the
AGV can notempty
M2 to the output
buffer and therefore
the plant isstuck.
Example 1 –plant modeling (automata)

231. Prof. Luca Ferrarini 50
F1F2V
O1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
The dedadlockis
causedby the fact
thatthe AGV is
occupiedwith a
product of M1 and
M2 isoccupied: the
AGV can notempty
M2 to the output
buffer and therefore
the plant isstuck.
To avoidthis
behaviour I should
forbidthe
execution of u1 if
bothmachinesare
occupied.
Example 1 –plant modeling (automata)

232. Prof. Luca Ferrarini 51
P1 V P2
F1F2 O1F2
F1O2 O1O2
A possiblesolutionisto definedesiredstates(markedstates)
and thenfindthe markedlanguage. How can wefindit?
Example 1 –plant modeling (automata)

233. Prof. Luca Ferrarini 52
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
M1||M2||AGV
O1F2V
The solutionistrimming. Ifwemarkthe initialstates, the
trimmingoperationwillautomaticallyremovethe notco-
reachablestates.
Example 1 –plant modeling (automata)

234. Prof. Luca Ferrarini 53
P1 V P2
F1F2 O1F2
F1O2 O1O2
F1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
F1O2P1
O1O2P1
M1||M2||AGV
O1F2V
Not co-
reachable
The solutionistrimming. Ifwemarkthe initialstates, the
trimmingoperationwillautomaticallyremovethe notco-
reachablestates.
Example 1 –plant modeling (automata)

235. Prof. Luca Ferrarini 54
The solutionistrimming. Ifwemarkthe initialstates, the
trimmingoperationwillautomaticallyremovethe notco-
reachablestates.
F1F2V
F1F2P1
F1O2V
F1F2P2
O1F2P1
O1O2V
O1F2P2
Tr(M1||M2||AGV)
O1F2V
Example 1 –plant modeling (automata)

236. Prof. Luca Ferrarini 55
Example 2 –plant modeling (Petri nets)
C1 M1 M2 C2
R
The plant is composed of:
•Two conveyor belts (C1 and C2) with infinite capacity
•Two machines (M1 and M2) that work one piece at a time
•A robot (R) that performs all load and unload operations
•A buffer (BUF) with a capacity of 4 pieces
BUF

237. Prof. Luca Ferrarini 56
Example 2 –plant modeling (Petri nets)
C1 M1 M2 C2
R
There are no specifications on the work-flow: we want to
model the plant with Petri netsin the most general way.
BUF

238. Prof. Luca Ferrarini 57
Example 2 –plant modeling (Petri nets)
M1 M2

239. Prof. Luca Ferrarini 58
Example 2 –plant modeling (Petri nets)
M1
load1
work1
unload1
M2
load2
work2
unload2

240. Prof. Luca Ferrarini 59
Example 2 –plant modeling (Petri nets)
BUF

241. Prof. Luca Ferrarini 60
Example 2 –plant modeling (Petri nets)
BUF
putget
Numberof avaliable
positions
Numberof products in
the buffer

242. Prof. Luca Ferrarini 61
Example 2 –plant modeling (Petri nets)
BUF
putget
Numberof avaliable
positions
Numberof products in
the buffer
R
Robot
avaliable
Robot
busy

243. Prof. Luca Ferrarini 62
Example 2 –plant modeling (Petri nets)
BUF
putget
Numberof avaliable
positions
Numberof products in
the buffer
R
unload1
Robot
avaliable
Robot
busy
load1

244. Prof. Luca Ferrarini 63
Example 2 –plant modeling (Petri nets)
BUF
putget
Numberof avaliable
positions
Numberof products in
the buffer
R
C1
get
unload2
unload1
Robot
avaliable
Robot
busy
C2
put
load2
load1

245. Prof. Luca Ferrarini 64
The overallplantP can be modeledasthe synchronous
compositionof the 4 modulesM1, M2, BUF and R:
P = M1||M2||BUF||R
Withouta specificationon the work-flow thisisverycomplexto
calculate.
Example 2 –plant modeling (Petri nets)

246. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Specification

247. Prof. Luca Ferrarini 2
Problem statement: given a plant model (P) and a specification
(SP) on that model, synthetize a controller(supervisor) (C) in
closed loop with the plant such that the overall system satisfies
as much as possiblethe specification.
Introduction to the control problem
C P

248. Prof. Luca Ferrarini 3
Specifications represent the goalof the control problem (positive
specifications) or the constraints (limits) on the plant behavior
(negative specifications).
Specifications
C P SP

249. Prof. Luca Ferrarini 4
Specifications represent the goalof the control problem (positive
specifications) or the constraints (limits) on the plant behavior
(negative specifications).
Specifications
C P SP
?
Observation: since both the plant and the specification are given,
it is not assured that the control (that must be designed) can
meet the specification.

250. Prof. Luca Ferrarini 5
Specification –formal definition
A specificationis defined as an automaton with marked and
forbidden states(6-tuple):
SP = (Q
SP
, Σ
SP
, i
SP
, δ
SP
, M
SP
, X
SP
)
With the only hypothesis
Σ
SP
Σ
P

251. Prof. Luca Ferrarini 6
Specification –formal definition
A specificationis defined as an automaton with marked and
forbidden states(6-tuple):
SP = (Q
SP
, Σ
SP
, i
SP
, δ
SP
, M
SP
, X
SP
)
With the only hypothesis
Σ
SP
Σ
P
•Partial specification:
Σ
SP
Σ
P
•Total specification:
Σ
SP
Σ
P

252. Prof. Luca Ferrarini 7
A specificationis defined as an automaton with marked and
forbidden states(6-tuple):
SP = (Q
SP
, Σ
SP
, i
SP
, δ
SP
, M
SP
, X
SP
)
With the only hypothesis
Σ
SP
Σ
P
•Partial specification:
Σ
SP
Σ
P
•Total specification:
Σ
SP
Σ
P
Observation: if an event is not present in the alphabet of the
specification (partial specification), it means that the plant can
execute it without any constraint.
Specification –formal definition

253. Prof. Luca Ferrarini 8
•M
SP
•M
SP
Q
SP
•X
SP
•X
SP
Q
SP
Observations

254. Prof. Luca Ferrarini 9
•M
SP
makes no sense
•M
SP
Q
SP
ok
•X
SP
ok
•X
SP
Q
SP
makes no sense
Observations

255. Prof. Luca Ferrarini 10
Example (1) –total specification
Given the plan model P, derive a specification SP1 that ensures
that the only possible string is ab:
P

256. Prof. Luca Ferrarini 11
Example (1) –total specification
Given the plan model P, derive a specification SP1 that ensures
that the only possible string is ab:
SP1P

257. Prof. Luca Ferrarini 12
Example (2) –total specification
Given the plan model P, derive a specification SP2 that ensures
that the plant executes only one event (aor b):
P

258. Prof. Luca Ferrarini 13
Example (2) –total specification
Given the plan model P, derive a specification SP2 that ensures
that the plant executes only one event (aor b):
P SP2

259. Prof. Luca Ferrarini 14
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3
Σ
SP
{a} Σ
P
{a,b}

260. Prof. Luca Ferrarini 15
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3
Σ
SP
{a} Σ
P
{a,b}
We put no constraints on the
event b (the plant is always
free to execute it)

261. Prof. Luca Ferrarini 16
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3

262. Prof. Luca Ferrarini 17
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3

263. Prof. Luca Ferrarini 18
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3

264. Prof. Luca Ferrarini 19
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3

265. Prof. Luca Ferrarini 20
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3

266. Prof. Luca Ferrarini 21
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3

267. Prof. Luca Ferrarini 22
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3

268. Prof. Luca Ferrarini 23
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3

269. Prof. Luca Ferrarini 24
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3

270. Prof. Luca Ferrarini 25
Example (3) –partial specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP3?
P SP3
P||SP3
The desired
behavior of P is
the synchronous
composition
between P and
SP3 (P||SP3)

271. Prof. Luca Ferrarini 26
Example (3) –Observations
•Thereare no easy relationshipsbetween the language of
the partialspecification L(SP3) and the language of the plant
L(P), but the result is the one we want (execute event aonly
once). That’s the reason why partial specifications are very
useful to express a desired behaviour in a clean, simple and
elegant way.

272. Prof. Luca Ferrarini 27
Example (3) –Observations
•There are no easy relationships between the language of
the partialspecification L(SP3) and the language of the plant
L(P), but the result is the one we want (execute event a only
once). That’s the reason why partial specifications are very
useful to express a desired behaviourin a clean, simple and
elegant way.
•The synchronous composition SP4 = P||SP3 can be itself
interpreted as a specification for the plant P –it yields the
same result as SP3-but it is total. The difference is that in
order to write the partial specification I don’t need to know the
model of the plant (the partial specification is not dependent
on the plant). On the contrary, to write the total specification I
need to know the plant model (the total specification is
dependent on the plant).

273. Prof. Luca Ferrarini 28
Example (4) –total specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP5?
P SP5
Σ
SP
{a,b} Σ
P
{a,b}

274. Prof. Luca Ferrarini 29
Example (4) –total specification
Given the plan model P, what is the meaning and which are the
consequences of the specification SP5?
P SP5
Σ
SP
{a,b} Σ
P
{a,b}
The executionof the event b is
forbidden
P||SP5 = SP5

275. Prof. Luca Ferrarini 30
Static and dynamic specifications
A static specification is a «special case» where the non-marked
and non-forbidden counter part is equal to the plant P:
nmnfcp(SP) = P
Therefore, to define a static specification it is enough to define
only the sets of marked and forbidden states (M
SP
and X
SP
).

276. Prof. Luca Ferrarini 31
Static and dynamic specifications
A static specification is a «special case» where the non-marked
and non-forbidden counter part is equal to the plant P:
nmnfcp(SP) = P
Therefore, to define a static specification it is enough to define
only the sets of marked and forbidden states (M
SP
and X
SP
).
A dynamic specification is a non-static specification.

277. Prof. Luca Ferrarini 32
Static and dynamic specifications
A static specification is a «special case» where the non-marked
and non-forbidden counter part is equal to the plant P:
nmnfcp(SP) = P
Therefore, to define a static specification it is enough to define
only the sets of marked and forbidden states (M
SP
and X
SP
).
A dynamic specification is a non-static specification.
Property of static specifications(S
SP
):
S
SP
P S
SP
P S
SP

PS
SP

278. Prof. Luca Ferrarini 33
Static and dynamic specifications
A static specification is a «special case» where the non-marked
and non-forbidden counter part is equal to the plant P:
nmnfcp(SP) = P
Therefore, to define a static specification it is enough to define
only the sets of marked and forbidden states (M
SP
and X
SP
).
A dynamic specification is a non-static specification.
Property of static specifications(S
SP
):
S
SP
P S
SP
P S
SP

PS
SP
Σ
SP
Σ
P
L(S
SP
)= L(S
SP
)L(P) L(S
SP
)L(P)

279. Prof. Luca Ferrarini 34
Observations
•By definition, a static specificationis also a total specification,
because its alphabet is the same of the one of the plant.
•A dynamic specificationcan be either a total specification or a
partial specification.
•The goal is to restrict the legal behaviourof the plant to the
behaviourthat is asked by the specification and this is shown
by the language L(SP)L(P).

280. Prof. Luca Ferrarini 35
Fundamental property
If we perform the synchronous compositionbetween any
specification(total, partial, static, dynamic) and the plant, we
always get an important automaton, S0: it can be seen as a
specification, it’s total, it refines the plant:
S0SP

P S0P
Σ
S0
Σ
P
L(S0)= L(S0)L(P) L(S
S0
)L(P)

281. Prof. Luca Ferrarini 36
Fundamental property
If we perform the synchronous compositionbetween any
specification(total, partial, static, dynamic) and the plant, we
always get an automaton S0 that refines the plant, with the
behaviourwanted by the specification:
S0SP

P S0P
Σ
S0
Σ
P
L(S0)= L(S0)L(P) L(S
S0
)L(P)
Proof:
S0P S0

PS0 SPPPS0SPPPS0
SP

PS0

282. Prof. Luca Ferrarini 37
Example (1)
P SP
Total or partial?
Static or dynamic?

283. Prof. Luca Ferrarini 38
Example (1)
P SP
Total or partial? Total(the alphabets are the same)
Static or dynamic?

284. Prof. Luca Ferrarini 39
Example (1)
P SP
Total or partial? Total(the alphabets are the same)
Static or dynamic? Dynamic(the desired behaviourcannot
be formulated in terms of states, but it
depends on the strings that have been
executed “before” -> we need “memory”)

285. Prof. Luca Ferrarini 40
Example (1)
P SP
SP

PSP SPPSP P

286. Prof. Luca Ferrarini 41
Example (2)
I1
W1
I2
W2
P1 P2
P = P1||P2
L1U1 L2 U2

287. Prof. Luca Ferrarini 42
Example (2)
I1
W1
I2
W2
P1 P2
P = P1||P2
SP
E
F
L1U1 L2 U2
U1L2

288. Prof. Luca Ferrarini 43
Example (2)
I1
W1
L1U1
I2
W2
L2U2
P1 P2
P = P1||P2
SP
E
F
U1L2
S0 = SP||P = SP||P1||P2

289. Prof. Luca Ferrarini 44
Example (2)
I1I2E
S0 = SP||P1||P2

290. Prof. Luca Ferrarini 45
Example (2)
I1I2E
W1I2E
L1
S0 = SP||P1||P2

291. Prof. Luca Ferrarini 46
Example (2)
I1I2E
W1I2E
L1
U1
S0 = SP||P1||P2
I1I2F

292. Prof. Luca Ferrarini 47
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
L1
U1
L2
S0 = SP||P1||P2

293. Prof. Luca Ferrarini 48
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
L1
U1
L2
U2
S0 = SP||P1||P2

294. Prof. Luca Ferrarini 49
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
L1
U1
L2
U2
S0 = SP||P1||P2
W1W2E
L1

295. Prof. Luca Ferrarini 50
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
L1
U1
L2
U2
S0 = SP||P1||P2
W1W2E
L1
I1W2F
U1

296. Prof. Luca Ferrarini 51
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
L1
U1
L2
U2
S0 = SP||P1||P2
W1W2E
L1
I1W2F
U1
U2

297. Prof. Luca Ferrarini 52
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
L1
U1
L2
U2
S0 = SP||P1||P2
W1W2E
L1
I1W2F
U1
U2
W1W2F
L1

298. Prof. Luca Ferrarini 53
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
L1
U1
L2
U2
S0 = SP||P1||P2
W1W2E
L1
I1W2F
U1
U2
W1W2F
L1
W1I2F
U2

299. Prof. Luca Ferrarini 54
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
L1
U1
L2
U2
S0 = SP||P1||P2
W1W2E
L1
I1W2F
U1
U2
W1W2F
L1
W1I2F
U2
L2

300. Prof. Luca Ferrarini 55
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
L1
U1
L2
U2
S0 = SP||P1||P2
W1W2E
L1
I1W2F
U1
U2
W1W2F
L1
W1I2F
U2
L2
L1

301. Prof. Luca Ferrarini 56
Example (2)
I1I2E
W1I2E
I1I2FI1W2E
W1W2E
I1W2F
W1W2FW1I2F
L1
L1
L1
L1
U1
L2
U2
U1
U2
L2
U2
U2
S0 = SP||P1||P2

302. Prof. Luca Ferrarini 57
Example (3)
I1
W1
L1U1
I2
W2
L2U2
P1 P2
P = P1||P2
SP1
E
F
U1L2
S0 = SP1||P = SP1||P1||P2
Σ
SP1
= {U1, L2, L1}

303. Prof. Luca Ferrarini 58
Example (3)
I1I2E
W1I2E
L1
S0 = SP1||P1||P2
L1 forbidden!
I1I2E

304. Prof. Luca Ferrarini 59
Example (4)
I1
W1
L1U1
I2
W2
L2U2
P1 P2
P = P1||P2
SP2
E
F
U1L2
S0 = SP2||P = SP2||P1||P2
Σ
SP2
= {U1, L2, L1}
L1

305. Prof. Luca Ferrarini 60
Example (4)
I1I2E
W1I2E
I1I2FI1W2E
W1W2E
I1W2F
W1W2FW1I2F
L1
L1
L1
L1
U1
L2
U2
U1
U2
L2
U2
U2
S0 = SP2||P1||P2
L1 is allowedONLY if
the buffer isempty(E)

306. Prof. Luca Ferrarini 61
Example (4)
I1I2E
W1I2E
I1I2FI1W2E
W1W2E
I1W2F
W1W2FW1I2F
L1
L1
L1
L1
U1
L2
U2
U1
U2
L2
U2
U2
S0 = SP2||P1||P2
L1 is allowedONLY if
the buffer isempty(E)

307. Prof. Luca Ferrarini 62
Example (4)
I1I2E
W1I2E
I1I2FI1W2E
W1W2E
I1W2F
W1W2FW1I2F
L1
L1
U1
L2
U2
U1
U2
L2
U2
U2
S0 = SP2||P1||P2
Unreachable states

308. Prof. Luca Ferrarini 63
Example (4)
I1I2E
W1I2E
I1I2FI1W2E
W1W2E
I1W2F
L1
L1
U1
L2
U2
U1
U2
U2
S0 = SP2||P1||P2

309. Prof. Luca Ferrarini 64
Example (5)
I1
W1
L1U1
I2
W2
L2U2
P1 P2
P = P1||P2
SP3
E
F
U1L2
S0 = SP3||P = SP3||P1||P2
Σ
SP3
= {U1, L2, L1, U2} (total)
L1,U2
U2

310. Prof. Luca Ferrarini 65
Example (5)
I1I2E
W1I2E
I1I2FI1W2E
W1W2E
I1W2F
L1
L1
U1
L2
U2
U1
U2
U2
S0 = SP3||P1||P2
No differences with
SP2||P1||P2, but partial
specification is easier to
handle (smaller automaton
and no need to be aware
of where every single
event is executed)

311. Prof. Luca Ferrarini 66
Modular approach
It is possible to adopt a modular approach also for specifications:
SPSPSPSP SP

312. Prof. Luca Ferrarini 67
Extra exercise
Given a plant model with an alphabet Σ including the events a
and b, write a specification that forbids the trace ab from being
executed:

313. Prof. Luca Ferrarini 68
Extra exercise
Given a plant model with an alphabet Σ including the events a
and b, write a specification that forbids the trace ab from being
executed:
SP:

314. Prof. Luca Ferrarini 69
Extra exercise
Given a plant model with an alphabet Σ including the events a
and b, write a specification that forbids the trace ab from being
executed:
SP:
Σ\{a}

315. Prof. Luca Ferrarini 70
Extra exercise
Given a plant model with an alphabet Σ including the events a
and b, write a specification that forbids the trace ab from being
executed:
SP:
Σ\{a}
a

316. Prof. Luca Ferrarini 71
Extra exercise
Given a plant model with an alphabet Σ including the events a
and b, write a specification that forbids the trace ab from being
executed:
SP:
Σ\{a}
a
Σ\{a,b}

317. Prof. Luca Ferrarini 72
Extra exercise
Given a plant model with an alphabet Σ including the events a
and b, write a specification that forbids the trace ab from being
executed:
SP:
Σ\{a}
a
Σ\{a,b}
a

318. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Synthesis of the supervisor

319. Prof. Luca Ferrarini 2
Problem statement: given a plant model (P) and a specification
(SP) on that model, synthetize a controller(supervisor) C in
closed loop with the plant such that the overall system satisfies
as much as possiblethe specification.
Introduction to the control problem
C P SP≡

320. Prof. Luca Ferrarini 3
Problems to solve
C P SP≡
1.Observing the plant
?

321. Prof. Luca Ferrarini 4
Problems to solve
C P SP≡
1.Observing the plant
2.Influencing the plant
?

322. Prof. Luca Ferrarini 5
Problems to solve
C P SP≡
1.Observing the plant
2.Influencing the plant
3.Fulfilling the specification
?

323. Prof. Luca Ferrarini 6
Problems to solve
C P SP≡
1.Observing the plant
2.Influencing the plant
3.Fulfilling the specification

324. Prof. Luca Ferrarini 7
Observing the plant –states and events
The plant is modeled as an automaton, therefore there are only
two possible kinds of observations:
•States(unique by definition)
•Events(not necessarily unique)
q1 q2q0 q3

325. Prof. Luca Ferrarini 8
Static vs Dynamic controller
If the statesof the plant are observable, it is possible to
implement a static controller (supervisor), that decides control
actions based only on the plant state.

326. Prof. Luca Ferrarini 9
Static vs Dynamic controller
If the statesof the plant are observable, it is possible to
implement a static controller (supervisor), that decides control
actions based only on the plant state.
If only eventsare observable, it is very likely that the controller
needs to reconstruct the plant state based on the knowledge of
the current and past observed events. This cannot be achieved
with a simple static controller. Therefore, a dynamic controller
(supervisor) must be implemented.

327. Prof. Luca Ferrarini 10
Example (static controller)
p1
p2
p0
p3
a
a
b
b
a
SP: execute only aab

328. Prof. Luca Ferrarini 11
Example (static controller)
p1
p2
p0
p3
a
a
b
b
a
SP: execute only aab
If the controller C reads the state of the plant (static controller), it
is very simple to design:
•IF P0 THEN “allow a”
•IF P1 THEN “allow a” (or “forbid b”)
•IF P2 THEN “allow b” (or “forbid a”)
Plant P

329. Prof. Luca Ferrarini 12
Example (dynamic controller)
p1
p2
p0
p4a
SP: execute abaor bab
b
p3 p5
a
a
b
b
Plant P

330. Prof. Luca Ferrarini 13
Example (dynamic controller)
p1
p2
p0
p4a
SP: execute abaor bab
In this case we cannot proceed as we did in the previous
example (the controller cannot be static): the controller C must
remember previous events and must have states on its own
(dynamic controller).
b
p3 p5
a
a
b
b
Plant P

331. Prof. Luca Ferrarini 14
Problems to solve
C P SP≡
1.Observing the plant
2.Influencing the plant
3.Fulfilling the specification

332. Prof. Luca Ferrarini 15
Influencing the plant –Asymmetric loop
The supervisory control theory (SCT) was invented by Ramadge
and Wonhamin 1987 andconsiders the plantas the only
system generating events (and so, languages). Therefore,
the supervisor cannot generate events but can only
disable/forbid some events (asymmetric loop). For this reason, it
can be represented with a simple matrix, called disablement
map.
S P
S: Q
P →Σ
P
If I cannot observe the states:
•S: Q
P ×Q
S→Σ
P
•S: Q
S ×Σ
P→Σ
P

333. Prof. Luca Ferrarini 16
Influencing the plant –Symmetric loop
The idea of symmetric loopwas invented by Balemiand it shows
two equivalent behaviours:
•C reads events from P and sends events to P
•P sends events to C and accepts events from C
We should always guarantee that the events sent are
actually accepted!
C P
Σ
P
Σ
C

334. Prof. Luca Ferrarini 17
Controller vs supervisor
C
«controller»
S «supervisor»
givespermissions
(allowsevents)
C «controller»
sendscommands
(orders)

335. Prof. Luca Ferrarini 18
Controller vs supervisor
Observation: the symmetric loopis more general because it can
represent both supervisor and controller, while the asymmetric
loopcan only represent the supervisor.
C
«controller»
S «supervisor»
givespermissions
(allowsevents)
C «controller»
sendscommands
(orders)

336. Prof. Luca Ferrarini 19
Influencing the plant –Kumar approach
The controller C is an automaton(not a map) that allows/forbids
events. The way to implement the interaction between the
controller and the plant (model of the closed loop system) is the
synchronous composition:
Pԡ??????
With the synchronous composition it is possible to allow or forbid
events just by correctly shaping the controller structure.

337. Prof. Luca Ferrarini 20
Observation
Since the controller is an automaton (not a simple map), we
must make sure that the interaction between the two systems
(controller and plant) is feasible:
•The plant must be able to accept the commands given by the
controller
•The controller must be able to understand the events that are
observed from the plant
C P
Σ
P
Σ
C

338. Prof. Luca Ferrarini 21
Observation
Since the controller is an automaton (not a simple map), we
must make sure that the interaction between the two systems
(controller and plant) is feasible:
•The plant must be able to accept the commands given by the
controller (controller should never send unfeasible requests)
•The controller must be able to understand the events that are
observed from the plant (controller must follow the plant)
C P
Σ
P
Σ
C

339. Prof. Luca Ferrarini 22
Problems to solve
C P SP≡
1.Observing the plant
2.Influencing the plant
3.Fulfilling the specification

340. Prof. Luca Ferrarini 23
Fulfilling the specification
There are different ways to interpret and fulfill the specification
(e.g., “as fast as possible”, “as cheap as possible”), but our
interpretation will be “with as little intervention as possible”
(maximum permissive approachor maximum freedom to the
plant).
Therefore, the supervisor S always follows the plant and does
not prevent events that cannot be forbidden.
To better describe this situation, we need to introduce
“controllability” concept

341. Prof. Luca Ferrarini 24
Controllable vs uncontrollable events
An event can be controllableor uncontrollablebased on the fact
that the controller can or cannot control it. This leads to a
partition on the set of events:
Σ
P=Σ
U∪Σ
C, Σ
U∩Σ
C=∅
Where:
•Σ
Uis the set of uncontrollable events
•Σ
Cis the set of controllable events

342. Prof. Luca Ferrarini 25
Controllability of the supervisor
Def: controllability of the controller S (supervisor) with respect to
the plant model P and the set of uncontrollable events Σ
U
∀??????∈????????????||??????, ∀??????
??????∈Σ
U:
??????
????????????
??????,s??????
??????∈Q
P⇒??????
????????????
??????,s??????
??????∈Q
S

343. Prof. Luca Ferrarini 26
Controllability of the supervisor
Def: controllability of the controller S (supervisor) with respect to
the plant model P and the set of uncontrollable events Σ
U
∀??????∈????????????||??????, ∀??????
??????∈Σ
U:
??????
????????????
??????,s??????
??????∈Q
P⇒??????
????????????
??????,s??????
??????∈Q
S
“If the plant accepts an uncontrollable event, then also the
supervisor must accept it.”

344. Prof. Luca Ferrarini 27
Example
Does it make sense?

345. Prof. Luca Ferrarini 28
Example
Does it make sense?
No, the supervisor should accept also the execution of the
uncontrollable event.

346. Prof. Luca Ferrarini 29
Observations
For the controller (supervisor), the concept of controllabilityhas
the same meaning of feasibility: a controllable supervisor is
also feasibleand vice versa.

347. Prof. Luca Ferrarini 30
Observations
For the controller (supervisor), the concept of controllabilityhas
the same meaning of feasibility: a controllable supervisor is
also feasibleand vice versa.
The synchronous composition is not enough: it does not
guarantee the feasibility of the controller. To ensure that the
controller is feasible, we must make sure that all uncontrollable
events are allowed to occur in the synchronous composition.
One possible way to do it is by ensuring that the alphabet of the
supervisor does not contain the set of uncontrollable events (in
this way the controller can never forbid the execution of an
uncontrollable event), but that is not always possible.

348. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Synthesis of the supervisor

349. Prof. Luca Ferrarini 2
Problem statement: given a plant model (P) and a specification
(SP) on that model, synthetize a controller(supervisor) C in
closed loop with the plant such that the overall system satisfies
as much as possiblethe specification.
Introduction to the control problem
C P SP≡

350. Prof. Luca Ferrarini 3
Fulfilling the specification
There are different ways to interpret and fulfill the specification
(e.g., “as fast as possible”, “as cheap as possible”), but our
interpretation will be “with as little intervention as possible”
(maximum permissive approachor maximum freedom to the
plant).
Therefore, the supervisor S always follows the plant and does
not prevent events that cannot be forbidden.
To better describe this situation, we need to introduce
“controllability” concept.

351. Prof. Luca Ferrarini 4
Controllable vs uncontrollable events
An event can be controllableor uncontrollablebased on the fact
that the controller can or cannot control it. This leads to a
partition on the set of events:
Σ
P=Σ
U∪Σ
C, Σ
U∩Σ
C=∅
Where:
•Σ
Uis the set of uncontrollable events
•Σ
Cis the set of controllable events

352. Prof. Luca Ferrarini 5
Controllability of the supervisor
(state-based definition)
Def: controllability of the controller S (supervisor) with respect
tothe plant model P and the set of uncontrollable events Σ
U
∀????????????∈????????????
????????????||????????????, ∀????????????
????????????∈Σ
U:
????????????
????????????
????????????
????????????,s????????????
????????????∈Q
P⇒????????????
????????????????????????
????????????,s????????????
????????????∈Q
S
“If the plant accepts an uncontrollable event, then also the
supervisor must accept it”

353. Prof. Luca Ferrarini 6
Controllability of the supervisor
(language-based definition)
Def: controllability of the controller S (supervisor) with respect
tothe plant model P and the set of uncontrollable events Σ
U
L(S)Σ
U∩L(P) ⊆L(S)
“The concatenation between the language of the controller and
the set of uncontrollable events intersected with the language of
the plant must be a subset of the language of the controller”

354. Prof. Luca Ferrarini 7
Example
Does it make sense?
P S (Σ
S=Σ
P) P||S

355. Prof. Luca Ferrarini 8
Example
Does it make sense?
No, the supervisor should accept also the execution of the
uncontrollable event.
S is not controllable!
P P||SS (Σ
S=Σ
P)

356. Prof. Luca Ferrarini 9
Observations
For the controller (supervisor), the concept of controllabilityhas
the same meaning of feasibility: a controllable supervisor is
also feasibleand vice versa.

357. Prof. Luca Ferrarini 10
Observations
For the controller (supervisor), the concept of controllabilityhas
the same meaning of feasibility: a controllable supervisor is
also feasibleand vice versa.
The synchronous composition is not enough: it does not
guarantee the feasibility of the controller. To ensure that the
controller is feasible, we must make sure that all uncontrollable
events are allowed to occur in the synchronous composition.
One possible way to do it is by ensuring that the alphabet of the
supervisor does not contain the set of uncontrollable events (in
this way the controller can never forbid the execution of an
uncontrollable event), but that is not always possible.

358. Prof. Luca Ferrarini 11
Theorem –existence of the supervisor
Lemma 1: S is controllable w.r.t.P and Σ
Uif and only ifP||S is
controllable w.r.t.P and Σ
U
Theorem
(existence of the supervisor): given the plant model P
and the specification K, then there exists a controllable
supervisor S, such that the closed- loop system satisfies
completely the specification, if and only if K is controllable and
K refines the plant.
∃controllable S | P||S=K ⇔K is controllable ∧K≺P

359. Prof. Luca Ferrarini 12
Theorem –existence of the supervisor
Lemma 1: S is controllable w.r.t.P and Σ
Uif and only ifP||S is
controllable w.r.t.P and Σ
U
Theorem
(existence of the supervisor): given the plant model P
and the specification K, then there exists a controllable
supervisor S, such that the closed- loop system satisfies
completely the specification, if and only if K is controllable and
K refines the plant.
∃controllable S | P||S=K ⇔K is controllable ∧K≺P
Proof:
•(⇒) if S is controllable, then K=P||S is controllable (lemma 1)
if P||S=K, then K ≺Pbecause K||P=P||S||P=P||S=K
•(⇐) if K is controllable, then S=K satisfies P||S=P||K=K

360. Prof. Luca Ferrarini 13
Corollary –supremal controllable supervisor
What if we are given a specification K which is not controllable?
Corollary(uncontrollable specification): given the plant model P
and the specification K, then there exists a controllable
supervisor S, such that the closed- loop system satisfies a sub-
automatonof the specification (not entirely K), if and only if
there exists S’≤K controllable and S’ refines the plant.
∃controllable S | P||S≤K ⇔∃a controllable S’ ≤K ∧S’≺P
Trivially, the supervisor S will be S’ (see the proof the Theorem).

361. Prof. Luca Ferrarini 14
Corollary –supremal controllable supervisor
If the specification K which is not controllable, how many
controllable subautomatadoes K have?
In general, many!
We could select the smallest, the fastest, etc. On the contrary,
we select the largestone, which basically means the most
permissiveone (less restrictive).
In this case the supervisor S’ will be the supremal(largest)
controllable sub- automaton of K (which is proved to be
unique).

362. Prof. Luca Ferrarini 15
Application of the theorem
1.Compute S
0= P||K(⇒S 0≺P)

363. Prof. Luca Ferrarini 16
Application of the theorem
1.Compute S
0= P||K (⇒S 0≺P)
2.Check controllabilityof S
0: if it is controllable, then we found
the solution, that is S=S
0.

364. Prof. Luca Ferrarini 17
Application of the theorem
1.Compute S
0= P||K(⇒S
0≺P)
2.Check controllabilityof S
0: if it is controllable, then we found
the solution, that is S=S
0.
3.If S
0is not controllable, then find the supremalcontrollable
sub-automatonof S
0:
S’ ≤S
0≺P ⇒S’≺S
0≺P ⇒S’≺P
S’ is found by simply removing uncontrollable statesfrom the
original supervisor S
0.

365. Prof. Luca Ferrarini 18
Example (1)
c1
c2
c3
c4
u1
u2
P K
c1
c3
c4
c2
u1
c4
c3

366. Prof. Luca Ferrarini 19
Example (1)
c1
c2
c3
c4
u1
u2
P K
c1
c3
c4
c2
u1
c4
c3
S0 = P||K c1

367. Prof. Luca Ferrarini 20
Example (1)
c1
c2
c3
c4
u1
u2
P K
c1
c3
c4
c2
u1
c4
c3
S0 = P||K c1
c2
c3

368. Prof. Luca Ferrarini 21
Example (1)
c1
c2
c3
c4
u1
u2
P K
c1
c3
c4
c2
u1
c4
c3
S0 = P||K c1
c2
c3
c4
u1

369. Prof. Luca Ferrarini 22
Example (1)
c1
c2
c3
c4
u1
u2
P K
c1
c3
c4
c2
u1
c4
c3
S0 = P||K c1
c2
c3
c4
u1
Uncontrollable
state
⇒Forbidden

370. Prof. Luca Ferrarini 23
Example (2)
c1
u2
c3
c4
u1
u2
P K
c1
c3
c4
u2
u1
c4
c3

371. Prof. Luca Ferrarini 24
Example (2)
c1
u2
c3
c4
u1
u2
P K
c1
c3
c4
u2
u1
c4
c3
S0 = P||K c1

372. Prof. Luca Ferrarini 25
Example (2)
c1
u2
c3
c4
u1
u2
P K
c1
c3
c4
u2
u1
c4
c3
S0 = P||K c1
u2
c3

373. Prof. Luca Ferrarini 26
Example (2)
c1
u2
c3
c4
u1
u2
P K
c1
c3
c4
u2
u1
c4
c3
S0 = P||K c1
u2
c3
c4
u1

374. Prof. Luca Ferrarini 27
Example (2)
c1
u2
c3
c4
u1
u2
P K
c1
c3
c4
u2
u1
c4
c3
S0 = P||K c1
u2
c3
c4
u1 The uncontrollable event u2
makes the system enter
uncontrollably into the forbidden
state!

375. Prof. Luca Ferrarini 28
Example (2)
c1
u2
c3
c4
u1
u2
P K
c1
c3
c4
u2
u1
c4
c3
S0 = P||K c1
u2
c3
c4
u1 The uncontrollable event u2
makes the system enter
uncontrollably into the forbidden
state!
One should always make sure
that this does not happen by
forbidding it.

376. Prof. Luca Ferrarini 29
Observations
The controllability check can be performed by the controllability
algorithmthat forbids all the uncontrollable states.
After that, we want to extend the set of forbidden states by
adding all the states that can uncontrollably evolve into
forbidden states.
This can be performed by the so- called extension algorithm. Its
name is due to the fact that the result is to extend the set of
forbidden states.

377. Prof. Luca Ferrarini 30
Example –extension algorithm
q0 q1 q2
q4
q3
q5
q6
q8
q7
c
c
c
c
c
c
u
u
u
u
u
S
Xs= {q7} →we start by having just 1 forbidden state (which
can be given by the specification or can be an
uncontrollable state)

378. Prof. Luca Ferrarini 31
Example –extension algorithm
q0 q1 q2
q4
q3
q5
q6
q8
q7
c
c
c
c
c
c
u
u
u
u
u
S
Xs= {q7, q5} →the set of forbidden states is extended at each
step by adding states that can evolve
uncontrollably into forbidden states.

379. Prof. Luca Ferrarini 32
Example –extension algorithm
q0 q1 q2
q4
q3
q5
q6
q8
q7
c
c
c
c
c
c
u
u
u
u
u
S
Xs= {q7, q5, q3}

380. Prof. Luca Ferrarini 33
Example –extension algorithm
q0 q1 q2
q4
q3
q5
q6
q8
q7
c
c
c
c
c
c
u
u
u
u
u
S
Xs= {q7, q5, q3}The arcs labelled with controllable events
that go into forbidden states can just be
removed (without forbidding more states)

381. Prof. Luca Ferrarini 34
Non-blockingness of the supervisor
The controller S is said to be non-blockingif it is able to reach
marked statesin closed loop (P||S). This is equivalent to
require that the controller S is trim(????????????
????????????????????????=L(S)).
“The supervisor should always allow to reach the goal (marked
states)”
The so obtained supervisor is called supremalcontrollable
non-blocking sub- automaton of the specification K.

382. Prof. Luca Ferrarini 35
Observations
The trimming algorithmcan create problems for controllability,
and viceversa, therefore all the algorithms that we have seen
might be executed several times before converging into a
solution.
There is not a correct order for executing the algorithms, but the
sequence must be repeated many times until the set of
forbidden states does not grow anymore.

383. Prof. Luca Ferrarini 36
Example
q0
q1 q2
q4q3 q5
a
b
c
d
e
f
g
h
q7
q6
Σ
U= {a, b, c, e, g, h}
X
S0= {q5}
S0

384. Prof. Luca Ferrarini 37
Example
q0
q1 q2
q4q3 q5
a
b
c
d
e
f
g
h
q7
q6
S1 = trim(S0)
Σ
U= {a, b, c, e, g, h}
X
S0= {q5, q4}

385. Prof. Luca Ferrarini 38
Example
q0
q1 q2
q4q3 q5
a
b
c
d
e
f
g
h
q7
q6
S2 (extension)
Σ
U= {a, b, c, e, g, h}
X
S0= {q5, q4, q3}

386. Prof. Luca Ferrarini 39
Example
q0
q1 q2
q4q3 q5
a
b
c
d
e
f
g
h
q7
q6
S3 = trim(S2)
Σ
U= {a, b, c, e, g, h}
X
S0= {q5, q4, q3}

387. Prof. Luca Ferrarini 40
Example
q0
q1 q2
q4q3 q5
a
b
c
d
e
f
g
h
q7
q6
S4 = S3 (extension)
Σ
U= {a, b, c, e, g, h}
X
S0= {q5, q4, q3}

388. Prof. Luca Ferrarini 41
Example
q0 q1 q2 q6
S supremalcontrollablenon-blockingsupervisor(sub-
automatonof S0)
a b c

389. Prof. Luca Ferrarini 42
Exercise –manufacturing cell
C1 M1 M2 C2
R
BUF
M1
load1
work1
unload1
M2
load2
work2
unload2
getput
BUF
R
C1
get
unload2
unload1
Robot
available
Robot
busy
C2
put
load2
load1

390. Prof. Luca Ferrarini 43
Exercise –manufacturing cell
Out of the synchronization of the 4 modules there are many
possible behaviours(the plant generates a lot of behaviours).
The goal of the specification is to limit the number of evolutions
and to restrict the behaviourof the plant in order to satisfy some
constraints.
Suppose the specification is C1 →M1 →(B) →M2 →C2 :
C1 M1 M2 C2
R
BUF
How can we model this specification?

391. Prof. Luca Ferrarini 44
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
SP (no buffer)

392. Prof. Luca Ferrarini 45
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
get
unload2
unload1
C2
put
load2
load1
C1
SP (no buffer)
C1

393. Prof. Luca Ferrarini 46
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
SP (no buffer)
R
C1
get
unload2
unload1
C2
put
load2
load1
C1 load1

394. Prof. Luca Ferrarini 47
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
SP (no buffer)
We do not need to explicitly write the
initial C1 transition because it is the only
one possible (we choose a partial
specification). We can start from load1.
R
C1
get
unload2
unload1
C2
put
load2
load1
load1

395. Prof. Luca Ferrarini 48
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
load1 unload1 load2 unload2 C2
SP (no buffer)

396. Prof. Luca Ferrarini 49
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
load1 unload1 load2 unload2 C2
SP (no buffer)
We must explicitly include C2
otherwise it could be executed
beforehand!

397. Prof. Luca Ferrarini 50
Exercise –manufacturing cell
The loop is not closed because it is not requested in the
specification (this is the representation of the execution of only
one sequence). Production systems are generally cyclic, but this
cyclic behaviourcan be implemented via software by repeating
this sequence.
load1 unload1 load2 unload2 C2

398. Prof. Luca Ferrarini 51
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
SP (with buffer)
load1 unload1 load2 unload2 C2

399. Prof. Luca Ferrarini 52
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
SP (with buffer)
load1 unload1 load2 unload2 C2
put
Start of choice

400. Prof. Luca Ferrarini 53
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
SP (with buffer)
load1 unload1 load2 unload2 C2
put
get

401. Prof. Luca Ferrarini 54
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
SP (with buffer)
load1 unload1 load2 unload2 C2
put
get
Correct?

402. Prof. Luca Ferrarini 55
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
SP (with buffer)
load1 unload1 load2 unload2 C2
put
get
Correct? NO! This is an end
of parallelism (we must use
an end of choice).

403. Prof. Luca Ferrarini 56
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
SP (with buffer)
load1 unload1 load2 unload2 C2
put
get
load2
end of choice

404. Prof. Luca Ferrarini 57
Exercise –manufacturing cell
M1
load1
work1
unload1
M2
load2
work2
unload2
put get
BUF
R
C1
get
unload2
unload1
C2
put
load2
load1
SP (with buffer)
load1 unload1 load2 unload2 C2
put
get
load2
The event load2 is
repeated! But this is
not a problem at all!

405. Prof. Luca Ferrarini 58
Exercise –manufacturing cell
SP (with buffer)
load1 unload1 load2 unload2 C2
put
get
load2
load1 unload1 load2 unload2 C2
SP (no buffer)

406. Prof. Luca Ferrarini 59
Exercise –manufacturing cell
load1 unload1 load2 unload2 C2
put
get
load2
Now let’s compute the synchronous compositionbetween the
specification, the two machine modelsand the buffer(we don’t
consider the robotbecause it would be too long).
M1(2)
SP
BUF
load1(2)
unload1(2)
work1(2)
put
get

407. Prof. Luca Ferrarini 60
Exercise –manufacturing cell
M1(2)
SP||M1
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2

408. Prof. Luca Ferrarini 61
Exercise –manufacturing cell
M1(2)
SP||M1
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2

409. Prof. Luca Ferrarini 62
Exercise –manufacturing cell
M1(2)
SP||M1
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2

410. Prof. Luca Ferrarini 63
Exercise –manufacturing cell
M1(2)
SP||M1
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

411. Prof. Luca Ferrarini 64
Exercise –manufacturing cell
M1(2)
SP||M1
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

412. Prof. Luca Ferrarini 65
Exercise –manufacturing cell
M1(2)
SP||M1
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1
Remember to close the loop!

413. Prof. Luca Ferrarini 66
Exercise –manufacturing cell
M1(2)
SP||M1
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

414. Prof. Luca Ferrarini 67
Exercise –manufacturing cell
M1(2)
SP||M1||BUF
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

415. Prof. Luca Ferrarini 68
Exercise –manufacturing cell
M1(2)
SP||M1||BUF
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

416. Prof. Luca Ferrarini 69
Exercise –manufacturing cell
M1(2)
SP||M1||BUF
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

417. Prof. Luca Ferrarini 70
Exercise –manufacturing cell
M1(2)
SP||M1||BUF
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

418. Prof. Luca Ferrarini 71
Exercise –manufacturing cell
M1(2)
SP||M1||BUF
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

419. Prof. Luca Ferrarini 72
Exercise –manufacturing cell
M1(2)
SP||M1||BUF
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1
Thisstate can be
eliminatedbecauseitis
duplicated(totallyuseless)

420. Prof. Luca Ferrarini 73
Exercise –manufacturing cell
M1(2)
SP||M1||BUF
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

421. Prof. Luca Ferrarini 74
Exercise –manufacturing cell
M1(2)
SP||M1||BUF||M2
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

422. Prof. Luca Ferrarini 75
Exercise –manufacturing cell
M1(2)
SP||M1||BUF||M2
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

423. Prof. Luca Ferrarini 76
Exercise –manufacturing cell
M1(2)
SP||M1||BUF||M2
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1

424. Prof. Luca Ferrarini 77
Exercise –manufacturing cell
M1(2)
SP||M1||BUF||M2
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1
work2

425. Prof. Luca Ferrarini 78
Exercise –manufacturing cell
M1(2)
SP||M1||BUF||M2
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1
work2

426. Prof. Luca Ferrarini 79
Exercise –manufacturing cell
M1(2)
SP||M1||BUF||M2
BUF
load1(2)
unload1(2)
work1(2)
put
get
load1 unload1 load2 unload2 C2
put
get
load2work1
work2

427. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Synthesis of the supervisor

428. Prof. Luca Ferrarini 2
Monolithic synthesis
Usually, modular approachis adopted for both the plantand
the specification(we can have a static specification and a
dynamic specification, or we can simply have different
specifications for different goals that we want to achieve).

429. Prof. Luca Ferrarini 3
Monolithic synthesis
Usually, modular approachis adopted for both the plantand
the specification(we can have a static specification and a
dynamic specification, or we can simply have different
specifications for different goals that we want to achieve).
The synthesis method we have seen is called monolithic
synthesis. It consists in performing the synchronous
compositionof all the plant modules (P=P1||P2||…) and all the
specification modules (SP=SP1||SP2||…) and then finding the
supremalcontrollable non- blocking supervisor of the
overall system (S≤S0=P||SP).
This is not always easy, due to the explosion of the number of
statesproduced by the synchronization among all the modules.

430. Prof. Luca Ferrarini 4
Modular synthesis
We want to find a way to preserve the modularity of the plant
and/or the specification, while still getting the same supervisor
that would be obtained using the monolithic synthesis.

431. Prof. Luca Ferrarini 5
Modular synthesis
We want to find a way to preserve the modularity of the plant
and/or the specification, while still getting the same supervisor
that would be obtained using the monolithic synthesis.
Example:
•Modular plant, monolithic (single) specification:
P1, P2, SP

432. Prof. Luca Ferrarini 6
Modular synthesis
We want to find a way to preserve the modularity of the plant
and/or the specification, while still getting the same supervisor
that would be obtained using the monolithic synthesis.
Example:
•Modular plant, monolithic (single) specification:
P1, P2, SP →S
01=P1||SP, S
02=P2||SP

433. Prof. Luca Ferrarini 7
Modular synthesis
We want to find a way to preserve the modularity of the plant
and/or the specification, while still getting the same supervisor
that would be obtained using the monolithic synthesis.
Example:
•Modular plant, monolithic (single) specification:
P1, P2, SP →S
01=P1||SP, S
02=P2||SP →S
1≤S
01, S
2≤S
02

434. Prof. Luca Ferrarini 8
Modular synthesis
We want to find a way to preserve the modularity of the plant
and/or the specification, while still getting the same supervisor
that would be obtained using the monolithic synthesis.
Example:
•Modular plant, monolithic (single) specification:
P1, P2, SP →S01=P1||SP, S02=P2||SP →S1≤S01, S2≤S02
•Monolithic plant, modular specification:
P, SP
1, SP
2→S
01=P||SP
1, S
02=P||SP
2 →S
1≤S
01, S
2≤S
02

435. Prof. Luca Ferrarini 9
Modular synthesis
In both cases we want S=S
1||S
2, where S≤S
0=P1||P2||SP (or
S0=P||SP
1||SP
2). If this is true, then modular synthesis is the
solution to the problem of the monolithic synthesis.
We want to find a way to preserve the modularity of the plant
and/or the specification, while still getting the same supervisor
that would be obtained using the monolithic synthesis.
Example:
•Modular plant, monolithic (single) specification:
P1, P2, SP →S01=P1||SP, S02=P2||SP →S1≤S01, S2≤S02
•Monolithic plant, modular specification:
P, SP
1, SP
2→S
01=P||SP
1, S
02=P||SP
2 →S
1≤S
01, S
2≤S
02

436. Prof. Luca Ferrarini 10
Modular plant and modular specification
Let's consider the most general case where both the plant and
the specification are modular (P=P1||P2 and SP=SP1||SP2).
For the seek of simplicity, let’s assume that all the alphabets
are the same(Σ
P1=Σ
P2=Σ
SP1=Σ
SP2). This is
not a mandatory
hypothesis, but it makes things much easier.

437. Prof. Luca Ferrarini 11
Modular plant and modular specification
Let's consider the most general case where both the plant and
the specification are modular (P=P1||P2 and SP=SP1||SP2).
For the seek of simplicity, let’s assume that all the alphabets
are the same(Σ
P1=Σ
P2=Σ
SP1=Σ
SP2). This is
not a mandatory
hypothesis, but it makes things much easier.
Moreover, let’s assume that SP1 only refers to P1 and SP2
only refers to P2. This is generally not true, but it is always
possible to reformulate the problem in a symmetric way:
SP1→P1||P2=P1’, SP2→P2=P2’ but P1’||P2’=P1||P2||P2=P
Therefore, this choice is redundant but not wrong.

438. Prof. Luca Ferrarini 12
Modular plant and modular specification
Given the plant P=P1||P2 and the specification SP=SP1||SP2, it
is possible to find the supremalcontrollable non- blocking
supervisors:
•S1 ≤S01=P1||SP1 (S1 controllableand non-blocking)
•S2 ≤S02=P2||SP2 (S2 controllableand non-blocking)

439. Prof. Luca Ferrarini 13
Modular plant and modular specification
Given the plant P=P1||P2 and the specification SP=SP1||SP2, it
is possible to find the supremalcontrollable non- blocking
supervisors:
•S1 ≤S01=P1||SP1 (S1 controllableand non-blocking)
•S2 ≤S02=P2||SP2 (S2 controllableand non-blocking)
Problem:
Is the supervisor of the overall system S=S1||S2
controllableand non-blocking?

440. Prof. Luca Ferrarini 14
Modular synthesis –controllability
Hp: S1 and S2 are controllable
Th: S=S1||S2 is controllable?
Proof:
L(S)Σ
U ∩L(P) ⊆L(S)
Language based definition of
controllability of S w.r.t. P and Σ
U

441. Prof. Luca Ferrarini 15
Modular synthesis –controllability
Hp: S1 and S2 are controllable
Th: S=S1||S2 is controllable?
Proof:
L(S)Σ
U ∩L(P) ⊆L(S)
L(S1||S2)Σ
U ∩L(P1||P2) ⊆L(S1||S2)

442. Prof. Luca Ferrarini 16
Modular synthesis –controllability
Hp: S1 and S2 are controllable
Th: S=S1||S2 is controllable?
Proof:
L(S)Σ
U ∩L(P) ⊆L(S)
L(S1||S2)Σ
U ∩L(P1||P2) ⊆L(S1||S2)
[L(S1) ∩L(S2)]Σ
U ∩[L(P1)∩L(P2)] ⊆L(S1) ∩L(S2)

443. Prof. Luca Ferrarini 17
Modular synthesis –controllability
Hp: S1 and S2 are controllable
Th: S=S1||S2 is controllable?
Proof:
L(S)Σ
U ∩L(P) ⊆L(S)
L(S1||S2)Σ
U ∩L(P1||P2) ⊆L(S1||S2)
[L(S1) ∩L(S2)]Σ
U ∩[L(P1)∩L(P2)] ⊆L(S1) ∩L(S2)
[L(S1)Σ
U∩L(S2)Σ
U]∩L(P1)∩L(P2) ⊆L(S1) ∩L(S2)

444. Prof. Luca Ferrarini 18
Modular synthesis –controllability
Hp: S1 and S2 are controllable
Th: S=S1||S2 is controllable?
Proof:
L(S)Σ
U ∩L(P) ⊆L(S)
L(S1||S2)Σ
U ∩L(P1||P2) ⊆L(S1||S2)
[L(S1) ∩L(S2)]Σ
U ∩[L(P1)∩L(P2)] ⊆L(S1) ∩L(S2)
[L(S1)Σ
U∩L(S2)Σ
U]∩L(P1)∩L(P2) ⊆L(S1) ∩L(S2)
L(S1)Σ
U∩L(P1)∩L(S2)Σ
U∩L(P2) ⊆L(S1) ∩L(S2)

445. Prof. Luca Ferrarini 19
Modular synthesis –controllability
Hp: S1 and S2 are controllable
Th: S=S1||S2 is controllable?
Proof:
L(S)Σ
U ∩L(P) ⊆L(S)
L(S1||S2)Σ
U ∩L(P1||P2) ⊆L(S1||S2)
[L(S1) ∩L(S2)]Σ
U ∩[L(P1)∩L(P2)] ⊆L(S1) ∩L(S2)
[L(S1)Σ
U∩L(S2)Σ
U]∩L(P1)∩L(P2) ⊆L(S1) ∩L(S2)
L(S1)Σ
U∩L(P1)∩L(S2)Σ
U∩L(P2) ⊆L(S1) ∩L(S2)
⊆L(S1) ⊆L(S2)
S1 (S2) is controllable w.r.t.P1 (P2) and Σ
U

446. Prof. Luca Ferrarini 20
Modular synthesis –controllability
Hp: S1 and S2 are controllable
Th: S=S1||S2 is controllable
Proof:
L(S)Σ
U ∩L(P) ⊆L(S)
L(S1||S2)Σ
U ∩L(P1||P2) ⊆L(S1||S2)
[L(S1) ∩L(S2)]Σ
U ∩[L(P1)∩L(P2)] ⊆L(S1) ∩L(S2)
[L(S1)Σ
U∩L(S2)Σ
U]∩L(P1)∩L(P2) ⊆L(S1) ∩L(S2)
L(S1)Σ
U∩L(P1)∩L(S2)Σ
U∩L(P2) ⊆L(S1) ∩L(S2)
We have proven controllability of S=S1||S2
⊆L(S1) ⊆L(S2)

447. Prof. Luca Ferrarini 21
Observation
Without the hypothesis on the alphabets (Σ
P1=Σ
P2=Σ
SP1=Σ
SP2)
the proof becomes much more complicated, but the
controllability of S=S1||S2 is still valid.

448. Prof. Luca Ferrarini 22
Modular synthesis –non-blockingness
Hp: S1 and S2 are non-blocking
Th: S=S1||S2 is non-blocking ?
Proof:
L
mS=LS
Non-blockingness of S
(S is trim)

449. Prof. Luca Ferrarini 23
Modular synthesis –non-blockingness
Hp: S1 and S2 are non-blocking
Th: S=S1||S2 is non-blocking ?
Proof:
L
mS=LS
L
mS1||S2=L(S1||S2)

450. Prof. Luca Ferrarini 24
Modular synthesis –non-blockingness
Hp: S1 and S2 are non-blocking
Th: S=S1||S2 is non-blocking ?
Proof:
L
mS=LS
L
mS1||S2=L(S1||S2)
L
mS1)∩L
m(S2=L
mS1∩L
mS2

451. Prof. Luca Ferrarini 25
Modular synthesis –non-blockingness
Hp: S1 and S2 are non-blocking
Th: S=S1||S2 is non-blocking ?
Proof:
L
mS=LS
L
mS1||S2=L(S1||S2)
L
mS1)∩L
m(S2=L
mS1∩L
mS2
Is it always true?

452. Prof. Luca Ferrarini 26
Modular synthesis –non-blockingness
Hp: S1 and S2 are non-blocking
Th: S=S1||S2 is non-blocking ?
Proof:
L
mS=LS
L
mS1||S2=L(S1||S2)
L
mS1)∩L
m(S2=L
mS1∩L
mS2
Is it always true?
NO, in general the right-end side is
larger than the left one!

453. Prof. Luca Ferrarini 27
Modular synthesis –non-blockingness
Hp: S1 and S2 are non-blocking
Th: S=S1||S2 is non-blocking iffS1 and S2 are non-conflicting
Proof:
L
mS=LS
L
mS1||S2=L(S1||S2)
L
mS1)∩L
m(S2=L
mS1∩L
mS2
S=S1||S2 is non-blockingif and only if S1 and S2
are non-conflicting!
NON-CONFLICTINGNESS

454. Prof. Luca Ferrarini 28
Example (1)
q0
q1
q0
q1
a
a
b
b
S1 S2

455. Prof. Luca Ferrarini 29
Example (1)
q0
q1
q0
q1
a
a
b
b
S1 S2
L
m
S1= {ε, ab, abab, …}
L
mS1= {ε, a, ab, aba, …}
L
m
S2= {a, ab, abb, abbb, …}
L
mS2= {ε, a, ab, abb, …}

456. Prof. Luca Ferrarini 30
Example (1)
q0
q1
q0
q1
a
a
b
b
S1 S2
L
m
S1= {ε, ab, abab, …}
L
mS1= {ε, a, ab, aba, …}
L
m
S2= {a, ab, abb, abbb, …}
L
mS2= {ε, a, ab, abb, …}
L
mS1)∩L
m(S2= {????????????????????????}

457. Prof. Luca Ferrarini 31
Example (1)
q0
q1
q0
q1
a
a
b
b
S1 S2
L
m
S1= {ε, ab, abab, …}
L
mS1= {ε, a, ab, aba, …}
L
m
S2= {a, ab, abb, abbb, …}
L
mS2= {ε, a, ab, abb, …}
L
mS1)∩L
m(S2= {????????????????????????} = {ε, a, ab}

458. Prof. Luca Ferrarini 32
Example (1)
q0
q1
q0
q1
a
a
b
b
S1 S2
L
m
S1= {ε, ab, abab, …}
L
mS1= {ε, a, ab, aba, …}
L
m
S2= {a, ab, abb, abbb, …}
L
mS2= {ε, a, ab, abb, …}
L
mS1)∩L
m(S2= {????????????????????????} = {ε, a, ab}
L
mS1∩L
mS2= {ε, a, ab}

459. Prof. Luca Ferrarini 33
Example (1)
q0
q1
q0
q1
a
a
b
b
S1 S2
L
m
S1= {ε, ab, abab, …}
L
mS1= {ε, a, ab, aba, …}
L
m
S2= {a, ab, abb, abbb, …}
L
mS2= {ε, a, ab, abb, …}
L
mS1)∩L
m(S2= {????????????????????????} = {ε, a, ab}
L
mS1∩L
mS2= {ε, a, ab}
Equal⇒non-conflicting

460. Prof. Luca Ferrarini 34
Example (1)
q0
q1
q0
q1
a
a
b
b
S1 S2
S1||S2
q0q0 q1q1 q0q1
a b

461. Prof. Luca Ferrarini 35
Example (2)
S1 S2
q1
q2
q0
q1
q2
q0
a
b
b
a
b
a

462. Prof. Luca Ferrarini 36
Example (2)
S1 S2
q1
q2
q0
q1
q2
q0
a
b
b
a
b
a
L
m
S1= {a, abba, …}
L
mS1= {ε, a, ab, abb, …}
L
m
S2= {a, abaa, …}
L
mS2= {ε, a, ab, aba, …}

463. Prof. Luca Ferrarini 37
Example (2)
S1 S2
q1
q2
q0
q1
q2
q0
a
b
b
a
b
a
L
m
S1= {a, abba, …}
L
mS1= {ε, a, ab, abb, …}
L
m
S2= {a, abaa, …}
L
mS2= {ε, a, ab, aba, …}
L
mS1)∩L
m(S2= {�????????????} = {ε, a}

464. Prof. Luca Ferrarini 38
Example (2)
S1 S2
q1
q2
q0
q1
q2
q0
a
b
b
a
b
a
L
m
S1= {a, abba, …}
L
mS1= {ε, a, ab, abb, …}
L
m
S2= {a, abaa, …}
L
mS2= {ε, a, ab, aba, …}
L
mS1)∩L
m(S2= {�????????????} = {ε, a}
L
mS1∩L
mS2= {ε, a, ab}

465. Prof. Luca Ferrarini 39
Example (2)
S1 S2
q1
q2
q0
q1
q2
q0
a
b
b
a
b
a
L
m
S1= {a, abba, …}
L
mS1= {ε, a, ab, abb, …}
L
m
S2= {a, abaa, …}
L
mS2= {ε, a, ab, aba, …}
L
mS1)∩L
m(S2= {�????????????} = {ε, a}
L
mS1∩L
mS2= {ε, a, ab}
Different⇒conflicting

466. Prof. Luca Ferrarini 40
Example (2)
S1 S2
q1
q2
q0
q1
q2
q0
a
b
b
a
b
a
S1||S2q0q0 q0q1
ba
q2q2
Is it non-blocking (trim)?

467. Prof. Luca Ferrarini 41
Example (2)
S1 S2
q1
q2
q0
q1
q2
q0
a
b
b
a
b
a
S1||S2q0q0 q1q1
ba
q2q2
Not trim!
Because from this state you
cannot reach any marked state.

468. Prof. Luca Ferrarini 42
Observations
The two automata S1 and S2 start sharing some path and reach
a common goal, but after that they do another step together and
they are blocked from reaching the next goal(the synchronous
compositionbetween S1 and S2 is not trim).
In order to make it trim, one should remove the non-coreachable
states(last state).

469. Prof. Luca Ferrarini 43
Observations
The two automata S1 and S2 start sharing some path and reach
a common goal, but after that they do another step together and
they are blocked from reaching the next goal(the synchronous
compositionbetween S1 and S2 is not trim).
In order to make it trim, one should remove the non-coreachable
states(last state).
The problem (still open for investigation) is:
in order to find those states starting uniquely from the modules, it is necessary to compute the synchronous
composition among all the modules that compose the
supervisor

473. Prof. Luca Ferrarini 44
Observations
That would eliminate all the advantages of the modular
synthesis.

474. Prof. Luca Ferrarini 45
Observations
That would eliminate all the advantages of the modular
synthesis.
However, wecan performthe full synchronouscompositionfor
analysis, butthenimplementthe control in a modular way!

475. Prof. Luca Ferrarini 46
Observations
That would eliminate all the advantages of the modular
synthesis.
However, wecan performthe full synchronouscompositionfor
analysis, butthenimplementthe control in a modular way!
Whichmeans:
•Trim the synchronouscompositionof allmodules
•Findthe blockingstates(markedlanguage)
•Implementthe single supervisors+ a coordinationmodulethat
forbidsthe blockingstates
•(of course) Implementa suitablecommunicationprotocolamongall
the supervisionmodules

476. Prof. Luca Ferrarini 47
Observations
That would eliminate all the advantages of the modular
synthesis.
However, wecan performthe full synchronouscompositionfor
analysis, butthenimplementthe control in a modular way!
Whichmeans:
•Trim the synchronouscompositionof allmodules
•Findthe blockingstates(markedlanguage)
•Implementthe single supervisors+ a coordinationmodulethat
forbidsthe blockingstates
•(of course) Implementa suitablecommunicationprotocolamongall
the supervisionmodules

477. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Diagnoser Automaton

478. Prof. Luca Ferrarini 2
ADiagnosticSystemisanautomaticsystem(aninference
engine)whichisabletoautomaticallyperformfaultdiagnosis.
Introduction

479. Prof. Luca Ferrarini 3
ADiagnosticSystemisanautomaticsystem(aninference
engine)whichisabletoautomaticallyperformfaultdiagnosis.
Twocomplementarytasks:
faultdetectionrecognizeswhetherthesystemisworkingin
normalconditionsorafaulthasoccurred
faultisolationandidentification localizethesystem
componentscausingthefaultandidentifythefault’snature
(criticality,size,importance,etc.)
Introduction

480. Prof. Luca Ferrarini 4
ADiagnosticSystemisanautomaticsystem(aninference
engine)whichisabletoautomaticallyperformfaultdiagnosis.
Twocomplementarytasks:
faultdetectionrecognizeswhetherthesystemisworkingin
normalconditionsorafaulthasoccurred
faultisolationandidentification localizethesystem
componentscausingthefaultandidentifythefault’snature
(criticality,size,importance,etc.)
Itisderivedusingthesameframeworkthatisusedforplant,
specificationandsupervisormodeling(labelledautomataor
labelledPetrinets).
Introduction

481. Prof. Luca Ferrarini 5
First diagnostic systems
Heating, Ventilation and Air Conditioning
(HVAC) systems

482. Prof. Luca Ferrarini 6
First diagnostic systems
Heating, Ventilation and Air Conditioning
(HVAC) systems
Photocopier machine
(1959)

483. Prof. Luca Ferrarini 7
First diagnostic systems
Heating, Ventilation and Air Conditioning
(HVAC) systems
Photocopier machine
(1959)
Automated Highway System (AHS) (1997)

484. Prof. Luca Ferrarini 8
Nowadays…
Diagnosticsystemsarebecoming
moreandmoreimportantinallthe
differentapplicationdomains,such
asmanufacturing,processcontrol,
industrialsystems,transportation,
communicationnetworks,control
systems,etc.

485. Prof. Luca Ferrarini 9
Given a closed-loop controlled plant
Diagnoser (conceptual problem)
C P
i u
m
y

486. Prof. Luca Ferrarini 10
Given a closed-loop controlled plant, the goal is to automatically
design a diagnoser(out of the loop)
Diagnoser (conceptual problem)
C P
i u
m
y
Diag

487. Prof. Luca Ferrarini 11
Given a closed-loop controlled plant, the goal is to automatically
design a diagnoser(out of the loop) such that, by simply
observing the I/O signals of the plant and the controller
(measurementsand control actions)
Diagnoser (conceptual problem)
C P
i u
m
y
Diag

488. Prof. Luca Ferrarini 12
Given a closed-loop controlled plant, the goal is to automatically
design a diagnoser(out of the loop) such that, by simply
observing the I/O signals of the plant and the controller
(measurementsand control actions), it is able to detect if a fault
has occurred or not.
Diagnoser (conceptual problem)
C P
i u
m
y
Diag
fault: Y/N
fault F

489. Prof. Luca Ferrarini 13
Withdiagnosticswerefertotheisolationandidentificationof
anomalousdynamicsthroughtheobservationofavailable
measurements.
Two main approaches:
Diagnostics approaches

490. Prof. Luca Ferrarini 14
Withdiagnosticswerefertotheisolationandidentificationof
anomalousdynamicsthroughtheobservationofavailable
measurements.
Two main approaches:
Non model-based: based only on signals/data (computer
science and telecommunicationfield)
Signal processing
Artificial intelligence and neural networks
…
Diagnostics approaches

491. Prof. Luca Ferrarini 15
Withdiagnosticswerefertotheisolationandidentificationof
anomalousdynamicsthroughtheobservationofavailable
measurements.
Two main approaches:
Non model-based: based only on signals/data (computer
science and telecommunicationfield)
Signal processing
Artificial intelligence and neural networks
…
Model-based: comparison between the real measurements
and the simulated evolution of a system model
State observers
Kalman Filter
…
Diagnostics approaches

492. Prof. Luca Ferrarini 16
DiscreteEventSystem(DES):event-drivensysteminwhichthe
stateevolutiondependsentirelyontheoccurrenceof
asynchronousdiscreteevents overtime(intuitiveand
powerfulmodellingapproachforindustrial/productionsystems).
Model-based diagnostic for DES

493. Prof. Luca Ferrarini 17
DiscreteEventSystem(DES):event-drivensysteminwhichthe
stateevolutiondependsentirelyontheoccurrenceof
asynchronousdiscreteevents overtime(intuitiveand
powerfulmodellingapproachforindustrial/productionsystems).
InaDiscreteEventSystem,faultscanbedescribedwithahigh
levelofabstraction(e.g.,valveisstuckclosed/open,sensoris
stuckonlow/high,…)andarerepresentedby unobservable
(non-observable)events,whichmeanseventsthathappenin
theplantbutcannotbedirectlysensed/measured.
Model-based diagnostic for DES

494. Prof. Luca Ferrarini 18
DiscreteEventSystem(DES):event-drivensysteminwhichthe
stateevolutiondependsentirelyontheoccurrenceof
asynchronousdiscreteevents overtime(intuitiveand
powerfulmodellingapproachforindustrial/productionsystems).
InaDiscreteEventSystem,faultscanbedescribedwithahigh
levelofabstraction(e.g.,valveisstuckclosed/open,sensoris
stuckonlow/high,…)andarerepresentedby unobservable
(non-observable)events,whichmeanseventsthathappenin
theplantbutcannotbedirectlysensed/measured.
Thegoalofmodel-baseddiagnosticapproach usingdiscrete
eventsmodelsistodetectunobservableevents(faults)using
strings(ortraces)ofobservableeventsonly.
Model-based diagnostic for DES

495. Prof. Luca Ferrarini 19
The existence of unobservable eventsintroduces another
partition on the set of events (alphabet) of an automaton P:
Σ
P
Σ
O
Σ
UO
Σ
O
Σ
UO
where:
•Σ
O
is the set of observable events
•Σ
UO
is the set of unobservable events
Observable and non-observable events

496. Prof. Luca Ferrarini 20
Observableeventsareplantmeasurements(controllerinput)
andcommands(controlleroutput).
Observations

497. Prof. Luca Ferrarini 21
Observableeventsareplantmeasurements(controllerinput)
andcommands(controlleroutput).
Unobservableeventsareplanteventsthatcannotbesensedor
measured,andtheycanbefaultyornot(unobservableevents
arenotnecessarilyfaults).
Observations

498. Prof. Luca Ferrarini 22
Observableeventsareplantmeasurements(controllerinput)
andcommands(controlleroutput).
Unobservableeventsareplanteventsthatcannotbesensedor
measured,andtheycanbefaultyornot(unobservableevents
arenotnecessarilyfaults).
Inthisscenario,faultsareassumedtobealwaysunobservable
events(e.g.,thecontrollercommandsthevalvetoopen,butthe
valveisstuckclosed,andIcannotrealizeituntil,forexample,a
sensormeasuresthatthereisnoflowoutgoingthevalve).
Observations

499. Prof. Luca Ferrarini 23
Inordertosolvethefaultdiagnosisproblembyfindingawayto
automaticallysynthetizeadiagnoserforourplant,wemust
acceptthehypothesisofpersistentfaults:whenacomponent
isinfault,itisinfaultforever(itbreaksdownanditmustbe
substituted).
Iffaultswouldnotbepersistent,thesystemwouldalternate
correctandfaultybehaviours,andthiswouldnotallowitto
performcorrectlyitstasknortoidentifyandisolatefaults.
Persistent faults hypothesis

500. Prof. Luca Ferrarini 24
The problem of fault diagnosis has two possible formulations:
Offline(diagnosability analysis): is my system able to
detect and isolate/identify faults (diagnosable)?
Must be done in simulation
Online(runtime diagnostics): has a fault occurred or not? If
yes, where?
Online and offline formulations

501. Prof. Luca Ferrarini 25
System model: labelled automata
Faults: unobservable events
Hypothesis: persistent faults
Inference engine based on:
system dynamics (model)
reachability analysis
Formulation:
Offline (diagnosability)
Online (runtime diagnostics)
Diagnoser automaton

502. Prof. Luca Ferrarini 26
Diagnoser approach (scheme)
Components
Models DES
Supervisor
Sensors
models
System
model
Step 1: Discrete System Model

503. Prof. Luca Ferrarini 27
Diagnoser approach (scheme)
Components
Models DES
Supervisor
Sensors
models
System
model
Diagnoser
Diagnostics
specification
Step 1: Discrete System Model Step 2:
Diagnosability
analisys
Runtime
diagnostics
Analysis
Synthesis

504. Prof. Luca Ferrarini 28
Step 1: Discrete System Model
Components
Models DES
Supervisor
Sensors
models
System
model
Diagnoser
Diagnostics
specification
Step 1: Discrete System Model Step 2:
Diagnosability
analisys
Runtime
diagnostics
Analysis
Synthesis

505. Prof. Luca Ferrarini 29
System model (with faults)
VCVC VOVO
VALVE
open_valve
close_valve

506. Prof. Luca Ferrarini 30
System model (with faults)
VCVC VOVO
open_valve
VALVE
close_valve
open_valve
close_valve

507. Prof. Luca Ferrarini 31
System model (with faults)
VCVC VOVO
SCSC
open_valve
VALVE
stuck_closed stuck_closed
close_valve
open_valve
close_valve

508. Prof. Luca Ferrarini 32
System model (with faults)
VCVC VOVO
SCSC
open_valve
VALVE
stuck_closed stuck_closed
close_valve
open_valve
close_valve
open_valve,
close_valve

509. Prof. Luca Ferrarini 33
System model (with faults)
VCVC VOVO
SOSO
SCSC
open_valve
open_valve,
close_valve
VALVE
stuck_closed
stuck_open
stuck_closed
stuck_open
close_valve
open_valve
close_valve
open_valve,
close_valve

510. Prof. Luca Ferrarini 34
System model (with faults)
VCVC VOVO
SOSO
SCSC P0P0 P1P1
open_valve
open_valve,
close_valve
VALVE
PUMP
stuck_closed
stuck_open
stuck_closed
stuck_open
close_valve
open_valve
close_valve
open_valve,
close_valve
start_pump
stop_pump
start_pump
stop_pump

511. Prof. Luca Ferrarini 35
System model (with faults)
VCVC VOVO
SOSO
SCSC P0P0 P1P1
C1C1 C3C3
C4C4
C2C2
open_valve
open_valve,
close_valve
VALVE
PUMP
SUPERVISOR
stuck_closed
stuck_open
stuck_closed
stuck_open
close_valve
open_valve
close_valve
open_valve,
close_valve
start_pump
stop_pump
start_pump
stop_pump
open_valve
close_valve
start_pump
stop_pump

512. Prof. Luca Ferrarini 36
System model (with faults)
Theoverallsystemisobtainedbythesynchronouscomposition
ofallthemodules(valve,pumpandsupervisor).Becarefulthat
faultsareunobservableevents andtheycanneverbe
forbiddenbythesupervisor(uncontrollable).
Example (first transitions):

513. Prof. Luca Ferrarini 37
System model (with faults)
Theoverallsystemisobtainedbythesynchronouscomposition
ofallthemodules(valve,pumpandsupervisor).Becarefulthat
faultsareunobservableevents andtheycanneverbe
forbiddenbythesupervisor(uncontrollable).
Example (first transition):
P0,VC,C1P0,VC,C1
P0,VO,C2P0,VO,C2
P0,SO,C1P0,SO,C1 P0,SC,C1P0,SC,C1
open_valve
stuck_closed
stuck_open

514. Prof. Luca Ferrarini 38
System model (with faults)
P0,VC,C1P0,VC,C1 P0,SO,C1P0,SO,C1 P0,SC,C1P0,SC,C1
stuck_closed
stuck_open
P0,VO,C2P0,VO,C2 P0,SO,C2P0,SO,C2 P0,SC,C2P0,SC,C2
stuck_closed
stuck_open
P1,VO,C3P1,VO,C3 P1,SO,C3P1,SO,C3 P1,SC,C3P1,SC,C3
stuck_closed
stuck_open
P0,VO,C4P0,VO,C4 P0,SO,C4P0,SO,C4 P0,SC,C4P0,SC,C4
stuck_closed
stuck_open
open_valve open_valve open_valve
start_pump start_pump start_pump
stop_pump stop_pump stop_pump
close_valve close_valve close_valve

515. Prof. Luca Ferrarini 39
Nominal dynamics
P0,VC,C1P0,VC,C1 P0,SO,C1P0,SO,C1 P0,SC,C1P0,SC,C1
P0,VO,C2P0,VO,C2 P0,SO,C2P0,SO,C2 P0,SC,C2P0,SC,C2
P1,VO,C3P1,VO,C3 P1,SO,C3P1,SO,C3 P1,SC,C3P1,SC,C3
P0,VO,C4P0,VO,C4 P0,SO,C4P0,SO,C4 P0,SC,C4P0,SC,C4
open_valve
start_pump
stop_pump
close_valve
NOMINAL DYNAMICS

516. Prof. Luca Ferrarini 40
Faulty dynamics
P0,VC,C1P0,VC,C1 P0,SO,C1P0,SO,C1 P0,SC,C1P0,SC,C1
stuck_closed
stuck_open
P0,VO,C2P0,VO,C2 P0,SO,C2P0,SO,C2 P0,SC,C2P0,SC,C2
stuck_closed
stuck_open
P1,VO,C3P1,VO,C3 P1,SO,C3P1,SO,C3 P1,SC,C3P1,SC,C3
stuck_closed
stuck_open
P0,VO,C4P0,VO,C4 P0,SO,C4P0,SO,C4 P0,SC,C4P0,SC,C4
stuck_closed
stuck_open
open_valve open_valve
start_pump start_pump
stop_pump stop_pump
close_valve close_valve
FAULTY DYNAMICS

517. P0,SO,C2P0,SO,C2
Prof. Luca Ferrarini 41
Faulty dynamics
open_valve
start_pump
stop_pump
close_valve
P0,VC,C1P0,VC,C1
P0,VO,C2P0,VO,C2
P1,VO,C3P1,VO,C3
P0,VO,C4P0,VO,C4
LEGAL EVENTS
BECOME UNSAFE!
P0,SO,C1P0,SO,C1
P1,SO,C3P1,SO,C3
P0,SO,C4P0,SO,C4
P0,SC,C1P0,SC,C1
P0,SC,C2P0,SC,C2
P1,SC,C3P1,SC,C3
P0,SC,C4P0,SC,C4

518. Prof. Luca Ferrarini 42
Thefaultydynamicsismuchwiderthanthenominal
dynamics(notethatinthisexamplewehaveonlyonefaulty
componentandonlytwofaults).
Insidethefaultydynamics,somelegaleventsmaybecome
unsafe(e.g.,thevalveisstuckclosedandthecontroller
activatesthepump,whichcreatesanoverpressureinthe
circuit).
Observations

519. Prof. Luca Ferrarini 43
Thefirstapproachtothefaultdiagnosisproblem( Stéphane
Lafortune,1996)aimstoincorporateintothesystemmodelthe
informationprovidedbythesensors attachedtothesystem:
thereadingsarerecordedinasensortableforallthereachable
(discrete)physicalstatesofthewholemodel.
Sensor table

520. Prof. Luca Ferrarini 44
Thefirstapproachtothefaultdiagnosisproblem( Stéphane
Lafortune,1996)aimstoincorporateintothesystemmodelthe
informationprovidedbythesensors attachedtothesystem:
thereadingsarerecordedinasensortableforallthereachable
(discrete)physicalstatesofthecompositemodel.
Example:
Flow sensor: (F, NF) (flow, no flow)
Pressure sensor: (PP, NP) (pressure, no pressure)
Sensor table
STATES SENSOR READINGS
(P0, -, -) NP, NF
(P1, VO, C3) PP, F
(P1, SO, C3) PP, F
(P1, SC, C3) PP, NF

521. Prof. Luca Ferrarini 45
Sensor table
STATES SENSOR READINGS
(P0, -, -) NP, NF
(P1, VO, C3) PP, F
(P1, SO, C3) PP, F
(P1, SC, C3) PP, NF

522. Prof. Luca Ferrarini 46
Sensor table
STATES SENSOR READINGS
(P0, -, -) NP, NF
(P1, VO, C3) PP, F
(P1, SO, C3) PP, F
(P1, SC, C3) PP, NF

523. Prof. Luca Ferrarini 47
Sincewewanttohavealanguage-basedmodel,itisnecessary
toconverttheinformationinthesensortabletoevents
(informationfromsensorreadingisembeddedintotheeventset)
andadditionalstatesareintroducedwhenunobservable
eventscausesobservablechangesinsensorreadings .
Example:
Flow sensor: (F, NF) (flow, no flow)
Pressure sensor: (PP, NP) (pressure, no pressure)
Sensor table
STATES SENSOR READINGS
(P0, -, -) NP, NF
(P1, VO, C3) PP, F
(P1, SO, C3) PP, F
(P1, SC, C3) PP, NF

524. Prof. Luca Ferrarini 48
System model (no sensor readings)
P0,VC,C1P0,VC,C1 P0,SO,C1P0,SO,C1
stuck_open
P0,VO,C2P0,VO,C2 P0,SO,C2P0,SO,C2
stuck_open
P1,VO,C3P1,VO,C3 P1,SO,C3P1,SO,C3
stuck_open
P0,VO,C4P0,VO,C4 P0,SO,C4P0,SO,C4
stuck_open
open_valve
start_pump
stop_pump
close_valve
P0,SC,C1P0,SC,C1
stuck_closed
P0,SC,C2P0,SC,C2
stuck_closed
P1,SC,C3P1,SC,C3
stuck_closed
P0,SC,C4P0,SC,C4
stuck_closed
open_valve
start_pump
stop_pump
close_valve
open_valve
open_valve
start_pump
stop_pump
close_valve

525. Prof. Luca Ferrarini 49
System model (with sensor readings)
P0,VC,C1P0,VC,C1 P0,SO,C1P0,SO,C1
stuck_open
P0,VO,C2P0,VO,C2 P0,SO,C2P0,SO,C2
stuck_open
P1,VO,C3P1,VO,C3 P1,SO,C3P1,SO,C3
stuck_open
P0,VO,C4P0,VO,C4 P0,SO,C4P0,SO,C4
stuck_open
open_valve,
NP, NF
start_pump,
PP, F
stop_pump,
NP, NF
close_valve,
NP, NF
P0,SC,C1P0,SC,C1
stuck_closed
P0,SC,C2P0,SC,C2
stuck_closed
P1,SC,C3P1,SC,C3
P0,SC,C4P0,SC,C4
stuck_closed
open_valve,
NP, NF
start_pump,
PP, F
stop_pump,
NP, NF
close_valve,
NP, NF
open_valve,
NP, NF
start_pump,
PP, NF
stop_pump,
NP, NF
close_valve,
NP, NF
stuck_closed

526. Prof. Luca Ferrarini 50
System model (with sensor readings)
P0,VC,C1P0,VC,C1 P0,SO,C1P0,SO,C1
stuck_open
P0,VO,C2P0,VO,C2 P0,SO,C2P0,SO,C2
stuck_open
P1,VO,C3P1,VO,C3 P1,SO,C3P1,SO,C3
stuck_open
P0,VO,C4P0,VO,C4 P0,SO,C4P0,SO,C4
stuck_open
open_valve,
NP, NF
start_pump,
PP, F
stop_pump,
NP, NF
close_valve,
NP, NF
P0,SC,C1P0,SC,C1
stuck_closed
P0,SC,C2P0,SC,C2
stuck_closed
P1,SC,C3P1,SC,C3
stuck_closed
P0,SC,C4P0,SC,C4
stuck_closed
F→NFF→NF
open_valve,
NP, NF
start_pump,
PP, F
stop_pump,
NP, NF
close_valve,
NP, NF
open_valve,
NP, NF
start_pump,
PP, NF
stop_pump,
NP, NF
close_valve,
NP, NF
NF
NEW STATE

527. Prof. Luca Ferrarini 51
The faulty component is the valve,
but we can see the effect only thanks
to the pump (typical situation)
Observation (1)
STATES SENSOR READINGS
(P0, -, -) NP, NF
(P1, VO, C3) PP, F
(P1, SO, C3) PP, F
(P1, SC, C3) PP, NF

528. Prof. Luca Ferrarini 52
Observation (2) –Symptoms
STATES SENSOR READINGS
(P0, -, -) NP, NF
(P1, VO, C3) PP, F
(P1, SO, C3) PP, F
(P1, SC, C3) PP, NF
AMBIGUITY: there are no symptoms
for the stuck open faulty dynamics

529. Prof. Luca Ferrarini 53
Observation (2) –Symptoms
STATES SENSOR READINGS
(P0, -, -) NP, NF
(P1, VO, C3) PP, F
(P1, SO, C3) PP, F
(P1, SC, C3) PP, NF
UNAMBIGUITY: there is a symptom
for the stuck closed fault (FNF)

530. Prof. Luca Ferrarini 54
Lateritwasdiscoveredthatthereisnoneedtointroducea
tableforsensors,andthustoaddpiecesofinformationinan
extra-form.Sensorscanbeconsideredaspartsofthesystem
andcanbesimplymodeledasautomata andcomposedwith
alltheothermodulesofthesystembyusingthe synchronous
composition.
Observation (3) –Sensors models
S0S0 S1S1
FLOW SENSOR
F
NF
S0S0 S1S1
PRESSURE SENSOR
PP
NP

531. Prof. Luca Ferrarini 55
Step 2: Analysis and Diagnoser Synthesis
Components
Models DES
Supervisor
Sensors
models
System
model
Diagnoser
Diagnostics
specification
Step 1: Discrete System Model Step 2:
Diagnosability
analisys
Runtime
diagnostics
Analysis
Synthesis

532. Prof. Luca Ferrarini 56
Diagnosability analysis
11
22
33
44 55
ba
f
ba
a a
uo
Thegoalistofindoutifitispossibletodetecttheunobservable
faulteventfbysensingonlytheobservableeventsaandb.
E
o
= {a, b}
E
uo
= {f, uo}
Fault = {f}

533. Prof. Luca Ferrarini 57
Diagnosability analysis
11
22
33
44 55
ba
f
ba
a a
uo
Thegoalistofindoutifitispossibletodetecttheunobservable
faulteventfbysensingonlytheobservableeventsaandb.
E
o
= {a, b}
E
uo
= {f, uo}
Fault = {f}
Byobservingabab…abthesystemcouldbeintwozones:one
notfaulty(P1)andonefaulty(P2).Onecannotdetectthefault
justbyobservingthe(ab)*loop(couldbeexecutedindefinitely).
P1 P2

534. Prof. Luca Ferrarini 58
Diagnosability analysis
11
22
33
44 55
ba
f
ba
a a
uo
Thegoalistofindoutifitispossibletodetecttheunobservable
faulteventfbysensingonlytheobservableeventsaandb.
E
o
= {a, b}
E
uo
= {f, uo}
Fault = {f}
Byobservingthetraceaa,thesystemisforsureintheP3zone
andonecanstatethatthefaulthasoccurred.Therefore, trace
aaisasymptomofthefaultf(itcouldneverbeexecuted).
P3

535. Prof. Luca Ferrarini 59
Diagnosability analysis
11
22
33
44 55
ba
f
ba
a a
uo
Thegoalistofindoutifitispossibletodetecttheunobservable
faulteventfbysensingonlytheobservableeventsaandb.
E
o
= {a, b}
E
uo
= {f, uo}
Fault = {f}
Sincetherearetwodifferentstringswitharbitrarylengthand
sameobservations(ab)*,butonlyoneofthemisfaulty ,the
faultfisnotdiagnosable.The(ab)*cycleissaidundefinedcycle.

536. Prof. Luca Ferrarini 60
Diagnoser synthesis –State observer
ThegoalistosynthetizeaDEScalled diagnoser(ordiagnostic
observer)whichisastateobserverthatisabletoperform
automaticallythediagnosabilityanalysis.

537. Prof. Luca Ferrarini 61
Diagnoser synthesis –State observer
ThegoalistosynthetizeaDEScalled diagnoser(ordiagnostic
observer)whichisastateobserverthatisabletoperform
automaticallythediagnosabilityanalysis.
Infact,thepresenceofunobservableeventscausesthesystem
automatontobecome non-deterministic:theproblemof
diagnosabilityistoestimatetheactualsystemstate.

538. Prof. Luca Ferrarini 62
Diagnoser synthesis –State observer
ThegoalistosynthetizeaDEScalled diagnoser(ordiagnostic
observer)whichisastateobserverthatisabletoperform
automaticallythediagnosabilityanalysis.
Infact,thepresenceofunobservableeventscausesthesystem
automatontobecome non-deterministic:theproblemof
diagnosabilityistoestimatetheactualsystemstate.
Themethodologyistocreatean equivalentdeterministic
automaton(observer) startingfromtheoriginal( non-
deterministic)one,inwhich:
Transitionsarelabelledwithonlyobservableevents
Eachstatecontainsanestimationofthesystemstates

539. Prof. Luca Ferrarini 63
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}

540. Prof. Luca Ferrarini 64
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
?

541. Prof. Luca Ferrarini 65
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3}
Until the first observation the
system can be in state 0 or in
state 3 (system state estimation)

542. Prof. Luca Ferrarini 66
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} ?
a

543. Prof. Luca Ferrarini 67
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} ?
a

544. Prof. Luca Ferrarini 68
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9}
a
The system can be in
one of these three states
(uncertainty increased)

545. Prof. Luca Ferrarini 69
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9}
a

546. Prof. Luca Ferrarini 70
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9}
a
{6}
d
System is surely in state 6
(uncertainty decreased)

547. Prof. Luca Ferrarini 71
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9}
{6} {7}
a
a
d

548. Prof. Luca Ferrarini 72
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9}
{6} {7}
a
a
d

549. Prof. Luca Ferrarini 73
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9}
{6} {7}
a
a
dd

550. Prof. Luca Ferrarini 74
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9}
{6} {7} {8}
a
a
dd
c

551. Prof. Luca Ferrarini 75
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9}
{6} {7} {8}
a
a
dd
c

552. Prof. Luca Ferrarini 76
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9} {2,5}
{6} {7} {8}
a
a
c
dd
c

553. Prof. Luca Ferrarini 77
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9} {2,5}
{6} {7} {8}
a
a
c
d dd
c

554. Prof. Luca Ferrarini 78
State observer –Example
00 11 22
66 77 88
99 5533 44
a c
bbb
d
a
a
d
c
c
d
E
o
= {a, c, d}
E
uo
= {b}
{0,3} {1,4,9} {2,5}
{6} {7} {8}
a
a
c
d dd
c

555. Production Systems Control
a.y. 2021 -2022
Prof. Luca Ferrarini
Diagnoser Automaton

556. Prof. Luca Ferrarini 2
Given a closed- loop controlled plant, the goal is to automatically
design a diagnoser(out of the loop) such that, by simply
observing the I/O signals of the plant and the controller
(measurementsand control actions), it is able to detect if a fault
has occurred or not.
Diagnoser (conceptual problem)
C P
i u
m
y
Diag fault: Y/N
fault F

557. Prof. Luca Ferrarini 3
The existence of unobservable eventsintroduces another
partition on the set of events (alphabet) of an automaton P:
Σ
P=Σ
O∪Σ
UO∧Σ
O∩Σ
UO=∅
where:
•Σ
Ois the set of observable events
•Σ
UOis the set of unobservable events
Observable and non-observable events

558. Prof. Luca Ferrarini 4
State observer –Example
0 1 2
6 7 8
9 53 4
a c
bbb
d
a
a
d
c
c
d
E
o= {a, c, d}
E
uo= {b}
{0,3} {1,4,9} {2,5}
{6} {7} {8}
a
a
c
d dd
c

559. Prof. Luca Ferrarini 5
Diagnosability definitions
Afaultfisdiagnosableifitcanbedetectedwithcertainty
withinafinitenumberofobservableeventsafterits
occurrence.Thismeansthatforeveryexecutiontracesof
eventsendingwithf,thereexistsasufficientlylong
continuationtracetsuchthatanyotherexecutiontrace
indistinguishablefromst(withthesamerecordof
observableevents)alsocontainsf.
(Sampathetal.,1995)
Afaultfisn-diagnosableifitcanbedetectedwithcertainty
withinaspecifiednumbernofobservableeventsafterits
occurrence.
s
f t

560. Prof. Luca Ferrarini 6
Natural projection
Themathematicalformalizationofthediagnosabilitydefinitionis
basedontwofunctions:theNaturalprojectionandtheInverse
(Reversed)projection.
TheNaturalprojectionistheoperationofeliminatingall
unobservableeventsfromanypossiblestringofanautomaton:

561. Prof. Luca Ferrarini 7
Inverse projection
Themathematicalformalizationofthediagnosabilitydefinitionis
basedontwofunctions:theNaturalprojectionandtheInverse
(Reversed)projection.
TheInverseprojectionistheinverseoperation, anditismore
complex.Infact,startingfromasingleobservableeventora
stringofobservableevents,theresultisaverylargesetof
stringscontainingalotofinterleavedunobservableevents:

562. Prof. Luca Ferrarini 8
Observation (1)

563. Prof. Luca Ferrarini 9
Observation (2)

564. Prof. Luca Ferrarini 10
Observation (2)
????????????
−1
[????????????????????????]
ThesearestringsofthelanguageLwiththesameobservations
ofs,butdifferentunobservableevents:ifallofthemcontain
thefault,thensisasymptomandthefaultisdiagnosable.

565. Prof. Luca Ferrarini 11
Mathematical formalization
Aprefix-closedlivelanguageLisdiagnosableif:
∀i∃|????????????
????????????∀????????????ending with ????????????
????????????
, ∀????????????∈⁄???????????????????????? with????????????≥????????????
????????????
the diagnosability condition D holds
????????????∈????????????
−1
????????????????????????????????????∩????????????⇒????????????
????????????∈????????????

566. Prof. Luca Ferrarini 12
Mathematical formalization
Aprefix-closedlivelanguageLisdiagnosableif:
∀i∃|????????????
????????????∀????????????ending with ????????????
????????????
, ∀????????????∈⁄???????????????????????? with????????????≥????????????
????????????
the diagnosabilitycondition D holds
????????????∈????????????
−1
????????????????????????????????????∩????????????⇒????????????
????????????∈????????????
Fixedasetofunobservableeventsanditspartitions,the
languageisdiagnosableifforeachfault‘f’,consideringeach
string‘s’endingwith‘f’andacontinuation‘t’sufficientlylong,
eachstringwiththesameobservableeventsas‘st’contains‘f’
(oratleastanunobservablefaultyeventofthesamegroupF).

567. Prof. Luca Ferrarini 13
Condition for diagnosability
Itcanbedemonstratedthatanecessaryandsufficient
conditionfortheLdiagnosabilityisthatthediagnoserdoes
nothaveundefinedcycles.
1
2
3
4 5
b a
f
b a
a a
uo

568. Prof. Luca Ferrarini 14
Condition for diagnosability
Itcanbedemonstratedthatanecessaryandsufficient
conditionfortheLdiagnosabilityisthatthediagnoserdoes
nothaveundefinedcycles.
Cycle1:ababab… nofault
1
2
3
4 5
b a
f
a
a a
uo
1
b

569. Prof. Luca Ferrarini 15
Condition for diagnosability
Itcanbedemonstratedthatanecessaryandsufficient
conditionfortheLdiagnosabilityisthatthediagnoserdoes
nothaveundefinedcycles.
Cycle1:ababab… nofault
Cycle2:ababab… fault
1
2
3
4 5
b a
f
a
a a
uob
2

570. Prof. Luca Ferrarini 16
Condition for diagnosability
Itcanbedemonstratedthatanecessaryandsufficient
conditionfortheLdiagnosabilityisthatthediagnoserdoes
nothaveundefinedcycles.
Cycle1:ababab… nofault
Cycle2:ababab… fault
⇒(ab)*isanundefinedcycle⇒fisnotdiagnosable
1
2
3
4 5
b a
f
b a
a a
uo

571. Prof. Luca Ferrarini 17
Observation
Ingeneral,theconstructionofthestateobserver(diagnoser)can
leadtoanexplosionofthenumberofstates(intheworst
case,thesizeoftheobserverisexponentialinthesizeofthe
automaton).
Notethatthiscanbeaverytoughproblembecauseingeneral
systemmodelshasaverylargenumberofstates(resultingfrom
thesynchronouscomposition), whichisalreadydifficultto
manage.

572. Prof. Luca Ferrarini 18
Observation
Ingeneral,theconstructionofthestateobserver(diagnoser)can
leadtoanexplosionofthenumberofstates(intheworst
case,thesizeoftheobserverisexponentialinthesizeofthe
automaton).
Notethatthiscanbeaverytoughproblembecauseingeneral
systemmodelshasaverylargenumberofstates(resultingfrom
thesynchronouscomposition), whichisalreadydifficultto
manage.
Twinmachinetechnique(polynomialtestfordiagnosability
withoutbuildingadiagnoser):afaultfisdiagnosableifthere
isnocoupleofinfinitetraceshavingthesameobservations,
suchthatfoccursinthefirsttracebutnotinthesecond
(Jiangetal.,2001; Yoo-Lafortune, 2002)

573. Prof. Luca Ferrarini 19
Diagnoser synthesis
Theonlydifferencebetweenadiagnoserandastateobserveris
inthepresenceofinformationaboutfaultoccurrenceineach
estimatedsystemstate.

574. Prof. Luca Ferrarini 20
Diagnoser synthesis
Theonlydifferencebetweenadiagnoserandastateobserveris
inthepresenceofinformationaboutfaultoccurrenceineach
estimatedsystemstate.
Alabelisaddedtoeachstatename:
“N”ifthefaulthasnotoccurred
“Y”ifthefaulthasoccurred

575. Prof. Luca Ferrarini 21
Diagnoser synthesis
Theonlydifferencebetweenadiagnoserandastateobserveris
inthepresenceofinformationaboutfaultoccurrenceineach
estimatedsystemstate.
Alabelisaddedtoeachstatename:
“N”ifthefaulthasnotoccurred
“Y”ifthefaulthasoccurred
Theupdatingruleforthelabelsfollowsthehypothesisof
persistentfaults:whenastateisreachedwithastringthat
containsthefault,thelabelisupdatedfromNtoYandnever
changesagain.

576. Prof. Luca Ferrarini 22
Label updating rule
X1-N X2-N
X1-Y X2-Y
No failures
No failures
X1-N
f
X2-Y
X1-Y
f
X2-Y

577. Prof. Luca Ferrarini 23
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

578. Prof. Luca Ferrarini 24
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

579. Prof. Luca Ferrarini 25
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
This is an uncertain statebecause it
contains both N and Y labels (one cannot
know if the system is in fault or not)
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

580. Prof. Luca Ferrarini 26
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
a
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

581. Prof. Luca Ferrarini 27
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
ab
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

582. Prof. Luca Ferrarini 28
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
ab
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

583. Prof. Luca Ferrarini 29
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y}
a
a
b
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

584. Prof. Luca Ferrarini 30
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y}
a
a
b
This is a certain (faulty)
statebecause it contains
only Y label (one is sure
that the fault has
happened)
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

585. Prof. Luca Ferrarini 31
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y}
a
a
b
a
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

586. Prof. Luca Ferrarini 32
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y} {3Y}
a
a
b
b
a
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

587. Prof. Luca Ferrarini 33
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y} {3Y}
a
a
a
b
b
a
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

588. Prof. Luca Ferrarini 34
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y} {3Y}
a
a
a
b
b
a
The diagnoser is complete, but…
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

589. Prof. Luca Ferrarini 35
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y} {3Y}
a
a
a
b
b
a
Cycle of uncertain states
⇒I can be always in doubt!
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

590. Prof. Luca Ferrarini 36
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y} {3Y}
a
a
a
b
b
a
Cycle of uncertain states
Is it undefined?
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}

591. Prof. Luca Ferrarini 37
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y} {3Y}
a
a
a
b
b
a
Cycle of uncertain states
Is it undefined?YES!
1 2

592. Prof. Luca Ferrarini 38
Diagnoser synthesis –Example (1)
1
2
3
4 5
b a
f
b a
a a
uo
E
o= {a, b}
E
uo= {f, uo}
Fault = {f}
{1N,3Y}
{2N,4Y,5Y}
{4Y,5Y} {3Y}
a
a
a
b
b
a
Cycle of uncertain states
Is it undefined?YES!
1 2
⇒Fault is not diagnosable!

593. Prof. Luca Ferrarini 39
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

594. Prof. Luca Ferrarini 40
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{1N,3N}
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

595. Prof. Luca Ferrarini 41
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
a
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

596. Prof. Luca Ferrarini 42
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{11N}
a
d
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

597. Prof. Luca Ferrarini 43
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
d e
{2N,5N,4N}
{1N,3N}
{11N}
{12N}
a
d
e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

598. Prof. Luca Ferrarini 44
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{11N}
{12N}
a
d
ed
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

599. Prof. Luca Ferrarini 45
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{11N}
{12N}
a
d
ed
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

600. Prof. Luca Ferrarini 46
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{6N,7N,9Y} {11N}
{12N}
a
c d
ed
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

601. Prof. Luca Ferrarini 47
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{6N,7N,9Y} {11N}
{8N,10Y} {12N}
a
c d
edd
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

602. Prof. Luca Ferrarini 48
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{6N,7N,9Y} {11N}
{8N,10Y}
{6N,9Y}
{12N}
a
c d
edd
e
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

603. Prof. Luca Ferrarini 49
Diagnoser synthesis –Example (2)
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{6N,7N,9Y} {11N}
{8N,10Y}
{6N,9Y}
{12N}
a
c d
edd
ed
d e
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}

604. Prof. Luca Ferrarini 50
Diagnoser synthesis –Example (2)
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{6N,7N,9Y} {11N}
{8N,10Y}
{6N,9Y}
{12N}
a
c d
edd
ed
d e

605. Prof. Luca Ferrarini 51
Diagnoser synthesis –Example (2)
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{6N,7N,9Y} {11N}
{8N,10Y}
{6N,9Y}
{12N}
a
c d
edd
ed
d e
Cycle of
uncertain states

606. Prof. Luca Ferrarini 52
Diagnoser synthesis –Example (2)
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{6N,7N,9Y} {11N}
{8N,10Y}
{6N,9Y}
{12N}
a
c d
edd
ed
d e
1 2
Cycle of
uncertain states
= undefined!

607. Prof. Luca Ferrarini 53
Diagnoser synthesis –Example (2)
E
o= {a, c, d, e}
E
uo= {b, f}
Fault = {f}
2 3
4 5
6 7
11
12
1
8 9
10
a b
b
f
c
de
a
d
c
de
{2N,5N,4N}
{1N,3N}
{6N,7N,9Y} {11N}
{8N,10Y}
{6N,9Y}
{12N}
a
c d
edd
ed
d e
⇒Fault is not
diagnosable!
1 2
Cycle of
uncertain states
= undefined!

608. Prof. Luca Ferrarini 54
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}

609. Prof. Luca Ferrarini 55
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y}
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}

610. Prof. Luca Ferrarini 56
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y}
a
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}

611. Prof. Luca Ferrarini 57
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N}
b
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
a

612. Prof. Luca Ferrarini 58
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga

613. Prof. Luca Ferrarini 59
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
d
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga

614. Prof. Luca Ferrarini 60
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
d
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga

615. Prof. Luca Ferrarini 61
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
{6Y}
td
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga

616. Prof. Luca Ferrarini 62
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
{6Y}
td
t
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga

617. Prof. Luca Ferrarini 63
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
{6Y}
td
t
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga

618. Prof. Luca Ferrarini 64
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
{6Y}
td
t
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga
Cycle of uncertain states

619. Prof. Luca Ferrarini 65
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
{6Y}
td
t
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga
Is this an undefined cycle?

620. Prof. Luca Ferrarini 66
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
{6Y}
td
t
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga
Is this an undefined cycle?
NO!! All faulty states end up in 6Y!
1
Symptom
No faulty cycles!

621. Prof. Luca Ferrarini 67
Diagnoser synthesis –Example (3)
1
2 3 4 5
6
8 9 10
7 11 12
f
a b g
t
t
d
a
f
b g
b g
d
{1N,2Y} {3Y,7N,8Y} {4Y,9Y,11N} {5Y,10Y,12N}
{6Y}
td
t
E
o= {a, b, d, g, t}
E
uo= {f}
Fault = {f}
b ga
Is this an undefined cycle?
NO!! All faulty states end up in 6Y!
1
No faulty cycles!
⇒Fault is
diagnosable!
Symptom

622. Prof. Luca Ferrarini 68
Multiple faults (fault partition)
Whendealingwithmultipledifferentfaults,itcouldbeusefulto
groupthemintodifferentclasses: onecannotbeinterestedin
identifyingthesinglefault,butjustitsclass.Thisprocedureis
calledfaultpartitionandcanbeusedtoachievediagnosability.
Example:
32 4
5
6
b fa fb
fc
uo
c
d
if F1 = {fa}, F2 = {fb}, F3 = {fc}, it is not diagnosable
if F1 = {fa, fb}, F2 = {fc}, it is diagnosable

623. Prof. Luca Ferrarini 69
Multiple faults (labels)
Thewaytopropagatetheinformationofmultiplefaultsisto
synthesizethediagnoserusingmorelabels:thelabel“N”
indicatesthatnofaulteventshaveoccurredandlabels“Fi”
indicatesthatafaultofthei-thclasshasoccurred.
Example:
X1-N
X1-F1
σ
f1 σ
f2
σ
f3
X1-F1,F2
X1-F1,F3

624. Prof. Luca Ferrarini 70
Diagnoser implementation
Ifthesystemisdiagnosable, thediagnoserisabletodetectand
isolatetheoccurrenceofeachfaulttype(classesdefinedby
thefaultpartition)enteringinacertainstateafterafinite
sequenceofsteps(executedevents).

625. Prof. Luca Ferrarini 71
Diagnoser implementation
Ifthesystemisdiagnosable, thediagnoserisabletodetectand
isolatetheoccurrenceofeachfaulttype(classesdefinedby
thefaultpartition)enteringinacertainstateafterafinite
sequenceofsteps(executedevents).
Theimplementationcanberealizedintwopossibleways:
offlinecomputeddiagnoser: completecharacterizationof
thediagnosisproblem(unrealisticforrealcomplexsystems)
andanefficientonlinesolutionintermsofdiagnosisresponse
time⇒lotofmemory,lowcomputationalpower
onlinecomputeddiagnoser(on-the-fly):real-timefault
diagnosisaftereachnewobservationacquired,itismore
computationallydemandingintermsofdiagnosisresponse
timebutthereisnoneedtostoreinmemorythecomplete
diagnoser⇒notmuchmemory,highcomputationalpower

626. Prof. Luca Ferrarini 72
Achieve diagnosability –Passive approach
Ifthesystemisnotdiagnosable, apossiblewaytoincrease
diagnosabilityistoincreasetheobservableeventsbyadding
newsensorstothesystem(passiveapproach).Thisisdoneby
aniterativeapproachuntilthediagnoserhasnomoreuncertain
cycles.

627. Prof. Luca Ferrarini 73
Achieve diagnosability –Passive approach
Ifthesystemisnotdiagnosable, apossiblewaytoincrease
diagnosabilityistoincreasetheobservableeventsbyadding
newsensorstothesystem(passiveapproach).Thisisdoneby
aniterativeapproachuntilthediagnoserhasnomoreuncertain
cycles.
Thisapproachworksundertheassumptionthatbyaddingnew
components(sensors)tothesystemweareactuallyreducing
complexityandnotintroducingmorefaultydynamics(sensors
arenotfaulty).

628. Prof. Luca Ferrarini 74
Achieve diagnosability –Passive approach
Ifthesystemisnotdiagnosable, apossiblewaytoincrease
diagnosabilityistoincreasetheobservableeventsbyadding
newsensorstothesystem(passiveapproach).Thisisdoneby
aniterativeapproachuntilthediagnoserhasnomoreuncertain
cycles.
Thisapproachworksundertheassumptionthatbyaddingnew
components(sensors)tothesystemweareactuallyreducing
complexityandnotintroducingmorefaultydynamics(sensors
arenotfaulty).
Moreover,morecomponentsmeanahighercostoftheoverall
system(trade- off).

629. Prof. Luca Ferrarini 75
Achieve diagnosability –Active approach
Anotherpossiblewaytoincreasediagnosabilityistochangethe
supervisorstrategy(activeapproach) .Infact,uncertaincycles
maybegeneratedbythesupervisor’sactionsandthereforeby
changingthesupervisoritcouldbepossibletoachieve
diagnosability.Thisisdonebyintroducingdiagnosability
restrictionsduringthesupervisordesignphase.

630. Prof. Luca Ferrarini 76
Achieve diagnosability –Active approach
Anotherpossiblewaytoincreasediagnosabilityistochangethe
supervisorstrategy(activeapproach) .Infact,uncertaincycles
maybegeneratedbythesupervisor’sactionsandthereforeby
changingthesupervisoritcouldbepossibletoachieve
diagnosability.Thisisdonebyintroducingdiagnosability
restrictionsduringthesupervisordesignphase.
Example:
C1 C3
C4
C2open_valve
close_valve
start_pump
stop_pump
C1 C3
C4
C2start_pump
stop_pump
open_valve
close_valve
Supervisor 1 (not diagnosable) Supervisor 2 (diagnosable)

631. Prof. Luca Ferrarini 77
Diagnosis methods –Decision structure
Threemainprocessingarchitecturesforfaultdiagnosis:
centralized:onemonolithicdiagnoserconstructedusing
theentireglobalsystemmodel(veryprecise,conceptually
simple,butwithprohibitivecomputationalcomplexitythat
makesitunusableforlarge- scalesystems)

632. Prof. Luca Ferrarini 78
Diagnosis methods –Decision structure
Threemainprocessingarchitecturesforfaultdiagnosis:
centralized:onemonolithicdiagnoserconstructedusing
theentireglobalsystemmodel(veryprecise,conceptually
simple,butwithprohibitivecomputationalcomplexitythat
makesitunusableforlarge- scalesystems)
decentralized:setofmultiplediagnosers,eachwithdifferent
observationcapabilities(partialorlocalobservations),butall
referringtothewholeglobalsystemmodel(thepurposeis
toaccountforthedecentralizationofinformationincomplex
interconnectedsystems,stillcomputationallycomplex)

633. Prof. Luca Ferrarini 79
Diagnosis methods –Decision structure
Threemainprocessingarchitecturesforfaultdiagnosis:
centralized:onemonolithicdiagnoserconstructedusing
theentireglobalsystemmodel(veryprecise,conceptually
simple,butwithprohibitivecomputationalcomplexitythat
makesitunusableforlarge- scalesystems)
decentralized:setofmultiplediagnosers,eachwithdifferent
observationcapabilities(partialorlocalobservations),butall
referringtothewholeglobalsystemmodel(thepurposeis
toaccountforthedecentralizationofinformationincomplex
interconnectedsystems,stillcomputationallycomplex)
distributed(modular):setofindividualdiagnosersthat
onlyusesubsystems(modules)withoutreferringtothe
globalsystemmodel(theaimistoimprovescalabilityand
robustnessasthediagnosisisperformedlocallyandto
ensureconsistencyallthediagnosersmustcommunicate)

634. Prof. Luca Ferrarini 80
Distributed diagnosis structure
Modulardiagnoser(modularsynthesis):insteadofhavingonly
onecentralizeddiagnoserfortheentiresystemmodel,each
subsystemhasitsowndiagnoserandtheoveralldiagnosability
canbeachievedbysharingtheinformationbetweenallthe
differentmodules(increasingthecollectiveknowledge).
Module #1 Module #2 Module #N
System model
Diagnoser #1 Diagnoser #2 Diagnoser #N
????????????
????????????,1∈????????????
1 ????????????
????????????,2∈????????????
2 ????????????
????????????,????????????∈????????????
N
Communication channel
Observations
Messages

635. Prof. Luca Ferrarini 81
Sensor reliability
Sofar,weassumedthatsensorreadingsarealwaysreliable
(observableevents).Inrealitytheyarenotperfectlyreliable
becausealsosensorscanbesubjectedtofaults:
misclassification:asensorreportsanincorrectreading
misdetection:asensordoesnotmakeareadingwhenevent
occurs

636. Prof. Luca Ferrarini 82
Sensor reliability
Sofar,weassumedthatsensorreadingsarealwaysreliable
(observableevents).Inrealitytheyarenotperfectlyreliable
becausealsosensorscanbesubjectedtofaults:
misclassification:asensorreportsanincorrectreading
misdetection:asensordoesnotmakeareadingwhenevent
occurs
Ifthesephenomenaareconsidered,thewaytosolvethe
diagnosisproblemistoconstructastochasticdiagnoser
(observer)thatcandeterminetheprobabilitythatafaulthas
occurred(Thorsley-Yoo-Garcia,2008) .

637. Prof. Luca Ferrarini 83
DES Diagnostic –Recap
DESDiagnostics: DiagnoserApproach
Model-baseddiagnosticapproach
DiagnosticStateObserver:Diagnoserautomaton
Detectfaultsmodeledasunobservableeventsstartingfrom
stringsofobservableevents(measures,commands)
Diagnosability:asystemisdiagnosableiftheoccurrenceofa
faultcanbeidentifiedbyobservingafinitesequenceof
observableevents
FaultPartition:groupoffaults(class)whichidentifiesfault
typesthatmustbeisolated
Diagnoserapplications:
Offline:diagnosabilityanalysis
Online:real-timefaultdetectionandisolation

638. Prof. Luca Ferrarini 84
Conclusions
Advantages:
Automaticsynthesisofthediagnosticautomaton
startingfromsystemandcontrolmodels(automatawith
parallelcompositionandobservergeneration)
Simpleimplementation(FSMwithsomeparticularlabelfor
eachstate….)
Disadvantages:
Intherealworldeverycomponentcanfail…soeveryreal
systemisnotdiagnosable(someinfallibilityhypothesis
mustbetakeninconsideration)
Complexautomatawithlotofstatesmakethesynthesis
ofthediagnoserverydifficult(morethan300statesfortwo
pressuresensorsandtwovalves…)

639. Prof. Luca Ferrarini 85
References
Mainlyinvolvedresearchers:
StéphaneLafortune(Univ.ofMichigan)
DemosthenisTeneketzis(Univ.ofMichigan)
KasimSinnamohideen(retiredfromJohnsonControls,Inc.)
MeeraSampath(WilsonCenterforR&T,XeroxCorp.)
RajaSengupta(CEDept.,Univ.ofCaliforniaatBerkeley)
RamiDebouk(GMResearchLab.)
Tae-SicYoo(ArgonneNationalLab.)
AndreaPaoli(Univ.ofBologna)
OlivierContant(Univ.ofMichigan)
SahikaGenc(Univ.ofMichigan)
DavidThorsley(Univ.ofMichigan)