S3PR網的一種最大許可活性監(jiān)督控制器設計方法

閆明明，趙 咪

（1.電子科技大學機電工程學院，四川 成都 610054；2.石河子大學機械電氣工程學院，新疆 石河子 832003）

0 引言

死鎖是對柔性制造系統(tǒng)（Flexible Manufacturing Systems，F(xiàn)MS）進行控制設計時必須考慮和解決的問題，實現(xiàn)優(yōu)化的無死鎖的FMS是目前工程設計者面臨的主要課題之一。并行FMS共享有限的資源，資源的不合理分配可能造成死鎖，降低系統(tǒng)的生產效率，甚至造成重大的經濟損失和災難性后果。Petri網能夠模擬離散事件系統(tǒng)的并發(fā)和沖突行為，并能反映系統(tǒng)的動態(tài)特性，非常適合復雜的并行FMS這種異步并發(fā)系統(tǒng)的建模、分析、控制和調度。通過對Petri網模型實施添加控制庫所及其連接弧等有效的系統(tǒng)設計，可以限制系統(tǒng)對資源的申請，達到阻止死鎖的目的［1－5］。受控網系統(tǒng)可達狀態(tài)的多少是評價Petri網控制器的一個重要指標。一個Petri網系統(tǒng)的可達狀態(tài)按標志描述可以劃分為死鎖標志、壞標志、危險標志和活標志四類［6－8］。對網系統(tǒng)進行控制設計的目的是去除死鎖標志和壞標志，即禁止標志，盡可能保留活標志和危險標志，即可保留標志。可以通過限制系統(tǒng)對資源的申請，保證所有的禁止狀態(tài)不可達，保留系統(tǒng)中的所有可達狀態(tài)［9］。

在Petri網的死鎖分析方法中，基于可達圖分析和結構分析的方法占主要地位?；诳蛇_圖分析的區(qū)域理論［2］可以獲得Petri網的最大許可控制器，但是該算法在具體實施時要產生網的可達圖，計算量巨大，甚至會出現(xiàn)狀態(tài)爆炸問題。基于結構分析的死鎖預防策略對Petri網模型中的嚴格極小信標添加控制庫所，使其不被清空，從而使受控網無死鎖或者活。然而現(xiàn)有的大部分信標控制策略添加控制庫所的方式對系統(tǒng)的約束過大，使得受控網的可達狀態(tài)無法達到最大許可數(shù)目。Piroddi等［5］基于信標理論提出一種次最優(yōu)的死鎖控制策略；Li和Zhou等［10］給出一種基于信標和區(qū)域理論的最大許可死鎖控制策略，改善了單獨用區(qū)域理論求解最優(yōu)控制器的計算復雜度。

本文針對Petri網的一個子類擁有資源的簡單加 工 進 程 系 統(tǒng) （System of Simple Sequential Process with Resources，S3PR）網提出一種基于結構分析的死鎖控制策略，若施加該策略后的活性Petri網控制器存在，則可以保證受控網具有最大許可行為。首先對原S3PR網系統(tǒng)的信標進行分析，獲得一組標志向量M表示的低于某個上限的廣義互斥約束集合，使信標的標志數(shù)不超過某個上限值，并添加控制庫所及相應的連接弧，若受控網是活網，則具有最大許可行為；否則，采用迭代方法對可能出現(xiàn)的所有可清空嚴格極小信標添加基于廣義互斥約束的控制器，使系統(tǒng)的所有禁止狀態(tài)不可達，即將網系統(tǒng)的所有可達狀態(tài)限制為可保留狀態(tài)。本策略將基于信標的死鎖預防控制策略轉化為禁止狀態(tài)監(jiān)控問題，因為算法有可能涉及到迭代，所以對可達狀態(tài)性能要求比較高的、結構相對簡單的網模型按本文策略進行控制，若施加控制后的受控網是活的，則可以得到最大許可Petri網控制器。

1 Petri網中的基本定義及性質［1，3－4，11］

Petri網是一種高效的圖形化的研究離散事件動態(tài)系統(tǒng)的建模工具，它的一些基本定義及性質如下所示。

定義1 令N＝（P，T，F(xiàn)）是一個Petri網系統(tǒng)，M0是網N的初始標志。一個廣義互斥約束（Generalized Mutual Exclusion Contraints，GMEC）（l，b）定義了一個合法標志集合 Ml（l，b）＝｛M∈IN｜P｜（lTM≤b｝，這里l：P→IN 表示加權向量，是一個從庫所到非負整數(shù)集上的映射，且b∈IN＋。其中‖l‖＝｛p∈P｜l（p）＞0｝是l的支撐，IN＋＝｛1，2，…｝是正整數(shù)集合。

一個廣義互斥約束可以表示為（l，b），或簡寫為l。

定義2 令N＝（P，T，F(xiàn)）為一個Petri網系統(tǒng)，M0是網N的初始標志。一組廣義互斥約束的集合（L，B），定義了一個合法標志集合Ml（L，B）＝∩mMl

i＝1（li，bi）＝｛M∈（IN｜P｜｜LTM≤B｝，其中L＝［l1｜l2｜…｜lm］，B＝［b1，b2，…，bm］T。

一組廣義互斥約束的集合可以表示為（L，B），或簡寫為L。

定義3 給定一個網系統(tǒng)（N，M0），N＝（P，T，F(xiàn)，W），以及一個GMEC約束（l，b），對該約束添加控制庫所V 后的網記為（NS，M0S），NS＝（P∪V，T，F(xiàn)S，WS），則［CS］（V，·）＝－lT［C］，M0S（V）＝b－lTM0，且?p∈P，［CS］（p，·）＝ ［C］（p，·），M0S（p）＝M0（p）。其中：［C］為網N 的關聯(lián)矩陣，［CS］為添加控制庫所后的關聯(lián)矩陣。

定義3對Petri網的一個GMEC約束添加一個控制庫所，該約束對應的禁止庫所（權值非零的庫所）多重集合和控制庫所組成一個庫所不變量，使得標志的加權和始終不超過該約束對應的上界，從而避免死鎖狀態(tài)。

性質1 令（N，M0），N＝（P，T，F(xiàn)）是一個普通Petri網系統(tǒng)，如果網N中沒有信標可能被清空，則稱（N，M0）是無死鎖的（deadlock－free）。

對Petri網的一些具體定義請參見文獻 ［1，11］。

2 死鎖預防策略

這里的死鎖預防策略是針對一類普通網S3PR網提出的。S3PR網的相關定義請參見文獻 ［1］。

性質2 一個擁有資源的簡單加工進程系統(tǒng)S3PR，是k（k∈IN＋）個擁有資源的簡單加工進程（Simple Sequential Process with Resources，S2PR）通過共享資源PRi融合而成的Petri網，N＝Oi＝1kNi＝（PS∪P0∪PR，T，F(xiàn)），k∈IN＋，Ni＝（Pi∪∪PRi，Ti，F(xiàn)i），Ni表示第i個S2PR網。其中：①Pi≠?，?Pi；②＝（Pi∪，Ti，F(xiàn)i＇）為一強連通狀態(tài)機，N＇i是從網Ni中移走PRi后的網；③N′i中每一個回路都包含庫所；④當任意兩個N′i共享一組資源庫所時，都是可組合的。

定義4 設N＝Oi＝1kNi＝（P∪P0∪PR，T，F(xiàn)）是一個S3PR網系統(tǒng)，Ir為包含資源r的極小P－不變式，其中｛r｝＝‖Ir‖∩PR，p0?‖Ir‖，P∩‖Ir‖≠?且Ir（r）＝1，稱H（r）＝‖Ir‖＼r為資源r的持有者。

定義5 設N＝Oi＝1kNi＝（P∪P0∪PR，T，F(xiàn)）是一個S3PR網系統(tǒng)，S是網N的一個信標，其中S＝SR∪SP，SR＝S∩PR，SP＝S＼PR，SR表示信標S中的資源，SP表示信標S中的工序狀態(tài)庫所。將信標S的補集以多集的形式定義為［S］＝r）＼S。［S］代表需使用資源r但不屬于信標S的庫所的集合，該集合中的元素是造成信標S被清空的直接原因。

定義6 設（N，M0）是一個Petri網系統(tǒng)，S是網N 的一個信標。如果?M∈R（N，M0），M（S）＞0成立，則稱S為可控信標。

對給定的S3PR網系統(tǒng)N＝Oi＝1kNi＝（P∪P0∪PR，T，F(xiàn)），可以對系統(tǒng)中每個可清空嚴格極小信標添加一個控制庫所，使其P－不變式可控，同時滿足不等式

式中：M是網N的標志向量，ξS是信標S的控制深度變量，0＜ξS＜M0（S）。因為S∪［S］是網N 的一個P－不變式的支撐，且不變式支撐在任何狀態(tài)下的托肯數(shù)總和保持不變，所以式（1）可以通過以下不等式的實現(xiàn)得到保證：

M（［S］）≤M0（S）－ξS。 （2）

由此可以得到如下定理：

定理1 設N＝Oi＝1kNi：＝（P∪P0∪PR，T，F(xiàn)）是一個S3PR網。若S是N的一個信標，則當滿足M（［S］）≤M0（S）－ξS或M（S）≤ξS時，信標S不會被清空。

由定理1知，通過對一個S3PR網系統(tǒng)中的所有可清空嚴格極小信標進行分析，可以得到一組類似（2）的GMEC集合，再采用定義3的方法添加相應的控制庫所和連接弧，可以保證原S3PR網中的所有信標均不會被清空。但是這樣一來，添加了控制庫所的新網中可能會產生新的可清空信標，導致受控網仍有死鎖狀態(tài)存在的可能。為此，筆者進行了探索并設計了以下迭代控制算法，在網結構不太復雜的情況下，可以得到具有最大許可行為的Petri網控制器，即若添加控制器后的受控網是活的，則可以達到最大可達狀態(tài)。

算法1 基于信標的死鎖控制最大許可控制器設計算法。

步驟4 求出信標的補集集合Π＊m，令Π＊m：＝｛［S1］，［S2］，…，［Sk］｝，k∈IN＋。

步驟5 由信標補集集合Π＊m得出狀態(tài)向量表示的 GMEC集合（L，B）：LM≤B，L＝［l1｜l2｜…｜lk］，B＝［b1，b2，…，bk］T。其中l(wèi)i為非零向量且li：＝ ［Si］，bi＝ M0（Si）－ξSi，ξSi：＝1，i＝1，2，…，k。

步驟6 根據(jù)定義3，對GMEC集合（L，B）添加控制庫所集合｛v｝＝｛v1，v2，…，vk｝，所得網記為（Nm′，Mm′）。

步驟8 Nm′＝ N′，Mm′＝ M0′。

步驟9 輸出網（N′，M0′）。

定理2 按算法1所述的死鎖預防策略對原網N 進行控制，受控網（N′，M0′）是一個ES3PR（system of extended simple sequential process with resources）網。

定理3 若算法1輸出活性控制器，則該控制器具有最大許可行為。

證明 因為每一個信標的控制深度變量取值為1，所以添加的控制庫所僅剔除了死鎖標志和必然導致死鎖的壞標志。因此，若算法1輸出活的控制器，則該控制器具有最大許可行為。

Petri網中可達狀態(tài)數(shù)目和可清空信標數(shù)目與網規(guī)模在理論上呈指數(shù)關系，即基于可達圖分析方法和基于結構分析的信標方法兩類控制策略都是指數(shù)復雜性的。因此，算法1關于網規(guī)模是指數(shù)復雜性的，算法1適用于對許可行為性能要求比較高、網規(guī)模不大、標志數(shù)偏多的S3PR網系統(tǒng)，若施加控制后的網為活網，則具有最大許可行為。

3 死鎖控制柔性制造系統(tǒng)應用實例

一個柔性制造系統(tǒng)（Flexible Manufacturing System，F(xiàn)MS）包括1臺機床M1和2個機器人R1，R2，生產兩種零件，其Petri網模型如圖1所示，庫所p7和p9用來表示機器人R1，R2，p8表示機床M1。該Petri網模型包含三個嚴格極小信標S1＝｛p2，p6，p7，p8｝，S2＝｛p3，p5，p8，p9｝，S3＝｛p6，p7，p8，p9｝，它們的補集分別為［S1］＝p1＋p5，［S2］＝p2＋p4，［S3］＝p1＋p2＋p4＋p5?；谒惴?得到圖1所示網系統(tǒng)的一組GMEC：

按照算法1添加3個控制庫所｛v1，v2，v3｝，控制庫所的初始資源數(shù)和前、后置分別為：

添加控制庫所｛v1，v2，v3｝后的受控網是無死鎖的，圖1網的最大許可行為是42，而本算法添加控制器后的受控網有42個可達狀態(tài)，說明該控制器是最大許可Petri網控制器。

再考慮一個結構稍微復雜一些的Petri網模型。圖2所示為一個具有兩個進程P1和P2的FMS的Petri網模型，這是一個S3PR網，它包含死鎖，可達狀態(tài)數(shù)為828。其中包括死標志38個、壞標志117個、危險標志96個、活標志577個，該網系統(tǒng)的最大可達狀態(tài)（即可保留狀態(tài)）為673個。網系統(tǒng)有3個嚴格極小信標S1＝｛p2，p7，p13，p14，p15，p16，p17，p18｝，S2＝｛p2，p7，p11，p13，p15，p16，p17，p18｝，S3＝｛p2，p5，p13，p14，p17｝，它們的補集分別是［S1］＝p3＋p5＋p6＋p9＋p10＋p11＋p12，［S2］＝p5＋p6＋p9＋p10，［S3］＝p3＋p11＋p12?；谒惴?可以得到一組GMEC為：

（l1，b1）：M（p3）＋M（p5）＋M（p6）＋M（p9）＋M（p10）＋M（p11）＋M（p12）≤5－1＝4，

（l2，b2）：M（p5）＋M（p6）＋M（p9）＋M（p10）≤4－1＝3，

（l3，b3）：M（p3）＋M（p11）＋M（p12）≤2－1＝1。

首先根據(jù)這些約束添加控制庫所｛v1，v2，v3｝，經分析可知添加了控制庫所｛v1，v2，v3｝后的受控網N′中有死鎖存在，即有新的可清空信標S4＝｛p7，p12，p14，p16，p18，v2，v3｝，S5＝｛p7，p11，p12，p16，p18，v2，v3｝，S6＝｛p5，p6，p12，p14，v2，v3｝，S7＝｛p5，p6，p11，p12，v2，v3｝產生?；谒惴?，很容易得到其補集分別為：［S4］＝2p3＋p5＋p6＋2p9＋2p10＋p11，M0′（S4）＝6，［S5］＝p3＋p5＋p6＋2p9＋2p10，M0′（S5）＝5，［S6］＝2p3＋p9＋p10＋p11，M0′（S6）＝4，［S7］＝p3＋p9＋p10，M0′（S7）＝3。

從而得到的另一組廣義相互抑制約束為：

采用控制算法1對網系統(tǒng)再添加4個控制庫所｛v4，v5，v6，v7｝，則添加控制庫所｛v1，v2，v3，v4，v5，v6，v7｝后的網記為（N′，M0′），且控制庫所的初始資源數(shù)和前、后置分別為：

此時得到的受控網系統(tǒng)（N′，M0′）是無死鎖的，且（N′，M0′）的可達狀態(tài)為673個，即該控制器具有最大許可行為。

4 結束語

本文針對Petri網的一個子類——S3PR網，提出一種有效的死鎖預防最優(yōu)化策略，利用信標理論，采用迭代方法對網系統(tǒng)中所有可能出現(xiàn)的可清空嚴格極小信標添加基于廣義互斥約束的控制器，使得系統(tǒng)的所有禁止狀態(tài)不可達，即將網系統(tǒng)的所有可達狀態(tài)限制為可保留狀態(tài)，從而保證系統(tǒng)不存在死鎖的狀態(tài)和步驟。對可達狀態(tài)性能要求比較高的、結構相對簡單的網模型按本文策略進行控制，可以得到活的、最大許可行為的Petri網控制器。下一步將主要針對降低死鎖預防最優(yōu)化控制策略的算法復雜度以及所獲得的最優(yōu)控制器的結構復雜性進行研究。

［1］ EZPELETA J，COLOM 段 ，MARTINEZ J.A Petri net based deadlock prevention policy for flexible manufacturing system［J］.IEEE Transactions on Robotics Automation，1995，11（2）：173－184.

［2］ UZAM M，ZHOU 段 .An iterative synthesis approach to Petri net based deadlock prevention policy for flexible manufacturing systems［J］.IEEE Transactions on Systems，Man，and Cybernetics：Part A，2007，37（3）：362－371.

［3］ GIUA A，SEATZU C.Liveness enforcing supervisors for railway networks using ES2PR Petri nets［C］／／Proceedings of the 6th International Workshop on Discrete Event Systems.Washington，D.C.，USA：IEEE，2002：55－66.

［4］ GIUA A，DICESARE F，SILVA M.Generalized mutual exclusion constraints on nets with uncontrollable translations［C］／／Proceedings of the 1992IEEE International Conference on Systems，Man and Cybernetics.Washington，D.C.，USA：IEEE，1992：974－979.

［5］ PIRODDI L，COSSALTER M，F(xiàn)ERRARINI I.A resource decoupling approach for deadlock prevention in FMS［J］.International Journal of Advanced Manufacturing Technology，2009，40（1／2）：157－170.

［6］ LI Zhiwu，HU Heshan，WANG Anrong.Design of livenessenforcing supervisors for flexible manufacturing systems using Petri nets［J］.IEEE Transactions on Systems，Man，and Cybernetics：Part C，2007，37（4）：517－526.

［7］ HUANG 段 .Deadlock prevention for sequence resource allocation systems［J］.Journal of Information Science and Engineering，2007，23（1）：215－231.

［8］ YAN Mingming，LI Zhiwu，WEI Na，et al.Optimal deadlock prevention policy for a class of Petri nets S3PMR［J］.Computer Integrated Manufacturing Systems，2008，14（1）：107－112，117（in Chinese）.［閆明明，李志武，韋 娜，等.S3PMR網的一種死鎖預防優(yōu)化策略［J］.計算機集成制造系統(tǒng)，2008，14（1）：107－112，117.］

［9］ YAN Mingming，ZHAO Mi.Maximally permissive deadlock prevention policy for FMS based on siphons［C］／／Proceedings of the International Conference on Mechanic Automation and Control Engineering.Washington，D.C.，USA：IEEE，2010：3319－3322.

［10］ LI Zhiwu，ZHOU Mengchu，JENG 段 .A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions［J］.IEEE Transactions on Automation Science and Engineering，2008，5（1）：182－188.

［11］ MURATA T.Petri nets：properties analysis and applications［J］.Proceedings of the IEEE，1989，77（4）：541－579.