CS代考程序代写 algorithm 􏰋1 0 0 0 0􏰌 􏰋3􏰌

􏰋1 0 0 0 0􏰌 􏰋3􏰌
Prof. Dr.-Ing. Jo ̈rg Raisch
Germano Schafaschek
Soraia Moradi
Behrang Nejad
Fachgebiet Regelungssysteme
Fakulta ̈t IV Elektrotechnik und Informatik Technische Universita ̈t Berlin Lehrveranstaltung ”Ereignisdiskrete Systeme“ Wintersemester 2019/2020
Exercise 4 — Solution
Exercise 4.1
The specification can be written as
1 1 0 1 0x(k)≤ 4 . 􏰄 􏰃􏰂 􏰅 􏰄􏰃􏰂􏰅
Γb
One way to test for ideal enforceability is to compute the ideal controller and check if it can be realised
(according to Definition 2.11). The initial marking of the controller places is given by
x0c =b−Γx0 =[3 4]′ , and the controller incidence matrix by
􏰋−1 1 0 1 0􏰌 Ac=−ΓA= −1 0 1 0 1 ,
where A is the incidence matrix of the plant. The plant with the controller is shown in Figure 1. t2 p2 t3
pc1
t1p1 p3
t4 p4 t5
p5
Figure 1: Plant with controller (Exercise 4.1).
pc2
Since there are no unobservable transitions, it suffices to check if there are any arcs from controller places to uncontrollable transitions. The only uncontrollable transitions are t3 and t5, to which there are clearly no arcs from any of the controller places. Equivalently, we can check if condition (2.23) from the lecture notes holds; namely, if −ΓAouc ≥ 0 (note that here there is no need to check condition (2.24), since there are no unobservable transitions). In this case, −ΓAouc is formed by the third and fifth columns of Ac,
􏰋0 0􏰌 −ΓAouc = 1 1 ,
1

so clearly −ΓAouc ≥ 0, and (2.23) is verified.
What is left to check is the initial marking, according to condition (2.25). In this case, we have
x0 = [0 0 2 0 1]′, so Γx0 = [0 0]′ ≤ b, and (2.25) also holds. Having computed the ideal supervisor, however, this can actually be directly verified by simply checking x0c, since it is clear that condition (2.25) holds if and only if x0c ≥ 0.
We therefore conclude that the specification is ideally enforceable.
Exercise 4.2
a) ThespecificationcanbewrittenintheformΓx(k) ≤ b,withΓ = [0 0 0 0 1]andb = 1. Applying the standard procedure, one obtains x0c = 1 and Ac = [0 0 0 − 1 1].
b) We check condition (2.23) from the lecture notes (page 33). In this case we have −ΓAouc = −1, so the condition is not fulfilled and the specification is not ideally enforceable.
c) Applying the algorithm for the case of uncontrollable transitions: 1.
2. J = {1}
3. Let ̄j = 1
0100000 −1 0 1 0 0 0 0 C=0001000 −1 0 0 0 1 0 0 1000010
1000001 (since J ̸= ∅, proceed to step 3)
a) I = {2, 4}
b) Let ̄i=4;then,d=lcm{1,1}=1 c)
0100000 −1 0 1 0 0 0 0 C=0001000 −1 0 0 0 1 0 0 1000010
0000101
4. Gotostep2
2. J = ∅, therefore go to step 6
6. Thealgorithmends,yielding r1T =[0 0 0 1 0] and r2 =1
The new specification is then given by Γ1x(k) ≤ b1, with
Γ1 = [0 0 0 1 0] + Γ = [0 0 0 1 1] and b1 = b = 1 ,
and the new controller can be computed as
Ac1=−Γ1A=[00 −101] and x0c1=b1−Γ1×0=1.
Toobtainasecondspecification,weapplythealgorithmagain,onlynowchoosing ̄i=2 instep 3.b, as follows:
2

1.
2. J = {1}
3. Let ̄j = 1
0100000 −1 0 1 0 0 0 0 C=0001000 −1 0 0 0 1 0 0 1000010
1000001 (since J ̸= ∅, proceed to step 3)
a) I = {2, 4}
b) Let ̄i=2;then,d=lcm{1,1}=1 c)
0100000 −1 0 1 0 0 0 0 C=0001000 −1 0 0 0 1 0 0 1000010
0010001
4. Gotostep2
2. J = ∅, therefore go to step 6
6. Thealgorithmends,yielding r1T =[0 1 0 0 0] and r2 =1
The new specification is now given by Γ2x(k) ≤ b2, with
Γ2 = [0 1 0 0 0] + Γ = [0 1 0 0 1] and
and the new controller can be computed as Ac2=−Γ2A=[−1 −1001] and
x2(k) + x3(k) ≤ 3 , x5(k) + x6(k) + x7(k) + x8(k) ≤ 3 , x5(k) + x6(k) ≤ 2 ,
or, in matrix form,
0 1 1 0 0 0 0 0 3 0 0 0 0 1 1 1 1x(k)≤3.
00001100 2
􏰄 􏰃􏰂 􏰅 􏰄􏰃􏰂􏰅
Γb
The incidence matrix of the (ideal) controller can then be computed as
0 −1 0 1 0 0 0 0 0 Ac=−ΓA=0 0 0 0 −1 0 0 0 1.
0 0 0 0 −1 0 1 0 0
b2 = b = 1 ,
x0c2=b2−Γ2×0=0. The boundedness of the resources can be expressed by the following inequalities:
Exercise 4.3
3

Since in this case there are no transitions which are uncontrollable and observable, condition (2.23) from the lecture notes does not apply here. We therefore check condition (2.24). In this case, we have
0 0 0
Ac =−ΓAuouc =0 0 0 ̸=0,
010
so the condition does not hold and the specification is not ideally enforceable. Since the only line that contains a non-zero entry is the third one, we can alter only the third inequality in the specification by applying the algorithm for the case of uncontrollable and unobservable transitions.
1.
000100000000 000010000000 000001000000
−1 0 0 0 0 0 1 0 0 0 0 0 C= −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 001000000010
0 −1 0 0 0 0 0 0 0 0 0 1
2. Does not apply, skip to step 3
3. L = {2} (since L ≠ ∅, proceed to step 4)
4. Letl ̄=2
a) Z = {7}
b) Letz ̄=7;then,d=lcm{1,1}=1 c)
000100000000 000010000000 000001000000
−1 0 0 0 0 0 1 0 0 0 0 0 C= −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 001000000010
0 0 −1 0 0 0 0 0 0 1 0 1
5. Gotostep2
2. Does not apply, skip to step 3
3. L = {3} (since L ≠ ∅, proceed to step 4)
4. Letl ̄=3
a) Z = {8}
b) Letz ̄=8;then,d=lcm{1,1}=1
4

c)
000100000000 000010000000 000001000000
−1 0 0 0 0 0 1 0 0 0 0 0 C= −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 001000000010
000000000111
5. Gotostep2
2. Does not apply, skip to step 3
3. L = ∅, therefore go to step 7
6. Thealgorithmends,returning r1T =[0 0 0 0 0 0 1 1] and r2 =1
The third line of the specification is then changed:
Γ(3) = [0 0 0 0 0 0 1 1] + Γ(3) = [0 0 0 0 1 1 1 1] and
The new controller can then be computed as
b(3) = b(3) = 2 . 3
0 −1 0 1 0 0 0 0 0
Ac=−ΓA=0 0 0 0 −1 0 0 0 1 and x0c=b−Γx =3.
0
0 0 0 0 −1 0 0 0 1 2
5