Information Technology Reference
In-Depth Information
Ta b l e 1 .
Non-blocking and controllability synthesis
Conjunctive Synthesis
Workset Algorithm
Model
Reachable States Supervisor states
BDD Peak Computation Time (s)
BDD Peak Computation Time (s)
6
.
50
0
.
87
AGV
22929408
1148928
9890
2850
Parallel Man
5702550
5702550
12363
2
.
47
2334
1
.
57
0
.
05
0
.
10
Transfer line (1,3)
64
28
17
13
1
.
07
×
10
9
8
.
49
×
10
4
1
.
69
0
.
59
Transfer line (5,3)
2352
299
1
.
15
×
10
18
6
.
13
×
10
13
48
.
36
3
.
89
Transfer line (10,3)
31022
1257
1
.
23
×
10
27
4
.
42
×
10
20
−
−
12
.
80
Transfer line (15,3)
3032
Cat and mouse (1,1)
20
6
43
0
.
02
31
0
.
05
0
.
08
0
.
09
Cat and mouse (1,5)
605
579
2343
273
Cat and mouse (5,1)
1056
76
848
0
.
30
305
0
.
30
6
.
91
×
10
9
3
.
15
×
10
9
−
−
20
.
86
Cat and mouse (5,5)
15964
∗
- denotes memory out.
However, with DESs getting larger and more complicated, the conjunctive partition-
ing technique is not capable of synthesizing non-blocking and controllable supervisors
any more. The disjunctive partitioning, on the other hand, could successfully explore the
state space within acceptable time. In addition, the column ”BDD Peak”, the maximal
number of BDD nodes during the reachability computation shows that the disjunctive
partitioning together with heuristic decisions can effectively reduce the number of in-
termediate BDD nodes.
Heuristics.
Table 2 shows the computation time for synthesizing non-blocking super-
visors of the extended cat and mouse with different instances. Different combinations
of heuristics, presented in Section 4.2, are chosen to test the performance of the workset
algorithm. Empirically, for the models with relatively large dependency sets, the heuris-
tic pair (MaxF,RT) seems to be a good choice, although it hasn't been formally proved.
Observing the results from Table 2, the workset algorithm can handle problem instances
with either a large number of levels
n
or cats
k
rather well. However, with both num-
bers increasing, the computation time increases rapidly no matter which heuristic pair
is chosen.
Ta b l e 2 .
Computation time for non-blocking supervisors with different heuristics
Computation Time (s)
Cat and mouse (
n, k
) Workset(MaxF,R) Workset(MaxF,RT) Workset(MinF,R) Workset(MinF,RT)
(1
,
1)
0
.
04
0
.
06
0
.
05
0
.
05
(1
,
5)
0
.
30
0
.
27
0
.
33
0
.
36
(5
,
1)
0
.
08
0
.
08
0
.
09
0
.
08
(5
,
5)
3
.
15
2
.
90
3
.
85
3
.
42
(1
,
10)
0
.
67
0
.
66
0
.
75
0
.
73
(7
,
7)
21
.
4
17
.
6
25
.
5
22
.
9
(10
,
1)
0
.
23
0
.
20
0
.
24
0
.
23
(10
,
7)
100
.
3
88
.
5
136
.
4
138
.
0
