CS代考程序代写 assembly algorithm Prof. Dr.-Ing. Jo ̈rg Raisch

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 2020/2021
Exercise sheet 4
Exercise 4.1 (Dental clinic revisited)
Consider the Petri net model obtained for the dental clinic in part a) of Exercise 1.1, shown in Figure 1. Now, let the following limitations be imposed:
• A maximum of 3 people can be in the waiting room at the same time.
• There cannot be more than 4 patients inside the clinic (in the waiting room or being treated) at the
same time.
Express these limitations as a specification for the system. Assuming that transitions t3 and t5 are observable but not controllable, and that t1, t2, and t4 are controllable and observable, determine if the specification is ideally enforceable. Justify your answer based on Definition 2.11 from the Lecture Notes.
t2 p2 t3
t1p1 p3
t4 p4 t5
p5
Figure 1: Petri net for the dental clinic.
CoSntrGol
Sys
tem
s
Fachgebiet Regelungssysteme
1

Exercise 4.2
p1
p3
t1
t2
t3
p2
p4
t4 p5 t5
The Petri net in Figure 2 is given.
Figure 2: Petri net for Exercise 4.2.
a) Specify a controller that guarantees that the number of tokens in p5 never exceeds 1 under the condition that all transitions are preventable (i.e., controllable) and observable.
b) Suppose, now, that t4 is an uncontrollable transition. Show that, in this case, the specification in item a) is not ideally enforceable.
c) Obtain two other specifications, (Γ1, b1) and (Γ2, b2), that are both at least as strict as the original one and ideally enforceable. Use the algorithm given on the attached worksheet. What are the resulting controllers?
2

Exercise 4.3
The following Petri net (Figure 3) represents a robotic assembly cell in which piston rods are assembled into engine blocks. Table 1 contains a description of every place. The number of tokens in a place denotes the number of resources that are involved in an operation.
t1 p1
p5
t5
t7 t8 t9
t2
t6
t3 t4
p2
p3 p4 p6 p7 p8 Figure 3: Petri net for Exercise 4.3.
Table 1: Description of the places of the Petri net from Figure 3.
Place Description
p1 Engine block and crankshaft are provided
p2 S-380 robot aligns the crankshaft
p3 S-380 robot grabs and positions a new piston rod
p4 The engine block is getting prepared
p5 M1 robot picks up a tool
p6 M1 robot places the piston rod into the engine block and returns the tool
p7 M1 robot places a coverage on the piston rod
p8 M1 robot tightens the coverage
The following resources are available: • 3 robots of type S-380
• 3 robots of type M1
• 2 tools
Express the boundedness of the resources in form of the inequality Γx ≤ b.
The transitions t6, t7, and t8 are neither preventable nor observable. Is the desired specification ideally enforceable under these circumstances? If not, find another specification that is at least as strict as the previous one and ideally enforceable. Determine the incidence matrix of the controller (Ac) as well as the initial marking (x0c ) of the controller places.1
1see: J. O. Moody and P. J. Antsaklis, “Petri net supervisors for DES with uncontrollable and unobservable transitions,” IEEE Transactions on Automatic Control, Vol. 45, No. 3, pp. 462–476, March 2000.
3

Prof. Dr.-Ing. Jo ̈rg Raisch
Germano Schafaschek
Behrang Nejad
Fachgebiet Regelungssysteme
Fakulta ̈t IV Elektrotechnik und Informatik Technische Universita ̈t Berlin Lehrveranstaltung ”Ereignisdiskrete Systeme“
Algorithm — control of Petri nets with unpreventable and unobservable transitions
The hereby presented algorithm for determining the “stricter” specification, or the vector r1 and the scalar r2 in
γ := r1 + r2γ ,
b := r2(b + 1) − 1 ,
(1)
is taken from the book Sistemi ad Eventi Discreti by A. Di Febbraro and A. Giua (McGraw-Hill, 2002). The authors consider only simple specifications γT x ≤ b, with γ ∈ Zn, b ∈ Z, and only allow natural values for r1 and r2, that is, r1 ∈ Nn, r2 ∈ N. For the more general case of a specification Γx ≤ b having the form shown in matrix inequality (2.15) from the lecture notes (page 29), it is always possible toapplythealgorithmseparatelytooneinequalityγiTx≤bi atatime,withi=1,…,q.
The Case of Unpreventable Transitions
Given a Petri net (N,x0) with n places and muc unpreventable (uncontrollable) transitions, let Auc denote the part of the incidence matrix that corresponds to these transitions. The specification to be enforced is given by γT x ≤ b. In order to determine r1 and r2 so that a stricter but ideally enforceable specification can be calculated according to (1), one constructs the following table of dimension (n + 1)×(muc +n+1):
C:= Auc In×n 0 , (2a) vT r1T r2
where In×n is the identity matrix, 0 is a null vector, and to start the algorithm the elements of the last row are defined as
vT :=γTAuc, r1 :=0, r2 :=1. (2b)
If the specification γT x ≤ b is not ideally enforceable, this means γT Auc 􏰈 0. Thus, add to the last row (or a positive multiple thereof) one of the previous rows (possibly multiplied by a positive integer) until vector v has only elements ≤ 0.
Formally, the algorithm for the case of unpreventable transitions consists of the following steps.
1. Construct the initial table according to (2).
2. Let J = {j | v(j) > 0} be the set of column indices corresponding to the positive entries of vector v.IfJ =∅,gotostep6.
3. If J ̸= ∅, select an index ̄j ∈ J and eliminate the element v( ̄j) as follows.
1

a) Determine the set of row indices that correspond to negative entries of column ̄j from Auc, I := {i | Auc(i, ̄j) < 0}. If I = ∅, then it is not possible to eliminate the positive entry v( ̄j). Go to step 5. b) Select an index ̄i ∈ I and compute d := lcm{|Auc( ̄i, ̄j)|, |v( ̄j)|}, the least common multiple of the absolute values of the two elements Auc( ̄i, ̄j) and v( ̄j). c) Multiply the last row of the table by d/|v( ̄j)| and add to it the ̄i-th row multiplied by d/|Auc( ̄i, ̄j)|, i. e., set C(m + 1, ·) := d C(m + 1, ·) + |v( ̄j)| The ̄j-th element of vector v is now 0. 4. Gotostep2. d C( ̄i, ·). |Auc( ̄i, ̄j)| 5. The algorithm ends with no result. 6. The algorithm ends and the last row of the table has the form vT r1T r2 . In case the algorithm ends with step 6, then v ≤ 0, whereas r1 ∈ Nn, r2 ∈ N. The stricter specification is thus given by (1), from which it can be shown that −γT Auc = −v ≥ 0 and therefore the new specification is ideally enforceable. The Case of Unpreventable and Unobservable Transitions A modified version of the presented algorithm also includes the case of unobservable transitions. The corresponding initial table in this case is C := Auc Auouc In×n 0 = Auc Auouc In×n 0 (3) vTuTr1Tr2 γTAucγTAuouc0...01 and one of the first n rows (or a positive multiple thereof) shall be added to the last row (possibly multiplied by a positive integer), until it holds that v ≤ 0 and u = 0. The steps for the case of unpreventable and unobservable transitions are the following. 1. Construct the initial table according to (3). 2. Let J = {j | v(j) > 0}. Apply the former version of the algorithm until J = ∅, meaning that v ≤ 0.
3. Now, let L = {l | u(l) ̸= 0} be the set of column indices corresponding to the non-zero entries of vector u. If L = ∅, go to step 7.
̄ ̄
4. If L ≠ ∅, select an index l ∈ L and eliminate the element u(l) as follows.
a) Determine the set of row indices that correspond to entries of column l ̄ from Auouc with ̄ ̄ ̄
opposite sign to u(l), Z := {z | sgn􏰉Auouc(z, l􏰊 = −sgn􏰉u(l)􏰊}. If Z = ∅, then it is not ̄
possible to eliminate the non-zero entry u(l). Go to step 6.
b) Select an index z ̄ ∈ Z and compute d := lcm{|Auouc(z ̄,l)|,|u(l)|}, the least common
multiple of the absolute values of the two elements Auouc(z ̄, l) and u(l).
2
̄ ̄ ̄ ̄

̄
c) Multiply the last row of the table by d/|u(l)| and add to it the z ̄-th row multiplied by
̄ d/|Auouc(z ̄, l)|, i. e., set
C(m + 1, ·) :=
d C(m + 1, ·) + d ̄ ̄
C(z ̄, ·).
|u(l)| |Auouc(z ̄, l)| The l-th element of vector u is now 0.
̄
5. Gotostep2.
6. The algorithm ends with no result.
7. The algorithm ends and the last row of the table has the form
vT uT r1T r2 .
Incasethealgorithmendswithstep7,thenv ≤ 0andu = 0,whereasr1 ∈ Nn, r2 ∈ N.The stricter specification is thus given by (1), from which it can be shown that −γT Auc = −v ≥ 0 and −γT Auouc = −u = 0, and therefore the new specification is ideally enforceable.
3