Petri網(wǎng)的一類禁止?fàn)顟B(tài)問題的混合型監(jiān)控器算法設(shè)計

1、Petri網(wǎng)的一類禁止?fàn)顟B(tài)問題的混合型監(jiān)控器算法設(shè)計*國家自然科學(xué)基金(60503027),福建省自然科學(xué)基金計劃資助項目(A0710010)和福建省青年人才項目(2006F3087)資助羅繼亮(華僑大學(xué)信息學(xué)院, 泉州 362021， E-mail: ljlng77)摘要：針對廣義互斥約束下Petri網(wǎng)的不可控影響子網(wǎng)為狀態(tài)機的一類禁止?fàn)顟B(tài)問題，給出了觀測器的設(shè)計方法，并基于觀測器得到了求解最大允許控制策略的算法。利用觀測器將廣義互斥約束簡化為單禁止庫所約束，并將存在不可控變遷的問題簡化為相當(dāng)于變遷全部可控的問題，這有效地解決了不可控變遷帶來的計算復(fù)雜性問題。最后，利用一個地鐵交通調(diào)度示例驗

2、證和說明該監(jiān)控器設(shè)計方法。關(guān)鍵詞：Petri網(wǎng)，離散事件系統(tǒng)，監(jiān)控，禁止?fàn)顟B(tài)，混合型監(jiān)控器Combined Supervisor Synthesis for a Class of Forbidden State Problems in Petri NetsLUO Ji-liang(Huaqiao University, Quanzhou, 362021, P. R. China. Email:ljlng77)Abstract: A class of forbidden state problems in which the influence uncontrollable subnets ar

3、e state machines for the given general mutual exclusion constraint (GMEC) on plant Petri nets is addressed. A method of designing the observers is proposed, and an algorithm of synthesizing the optimal supervisors is obtained based on the observers. It makes it possible to transform a GMEC with mult

4、i forbidden places into that with only one forbidden place and to reduce the control problem with uncontrolled transitions into that without any uncontrolled transition. The computational complexity of the supervisor synthesis is then efficiently reduced. A metro line supervisory example illustrates

5、 the theoretic results.Keywords: Petri nets, Discrete Event System, Supervisory Control, Forbidden States, Combined Supervisor1.引言為了描述離散事件系統(tǒng)中多進(jìn)程共享資源有限而導(dǎo)致的沖突問題，文獻(xiàn)1以Petri網(wǎng)為模型引入了一類稱為廣義互斥約束的禁止?fàn)顟B(tài)控制規(guī)范。需要指出的是，當(dāng)存在不可控變遷時，需要進(jìn)行多步的可達(dá)性分析，即要列舉長度為的變遷多重集合序列，文獻(xiàn)2指出并發(fā)引起的變遷序列的交錯將導(dǎo)致系統(tǒng)的狀態(tài)空間爆炸，因此存在不可控變遷的禁止?fàn)顟B(tài)問題一直是離散事件系統(tǒng)監(jiān)控的

6、難點。從監(jiān)控器的實現(xiàn)形式的角度，目前為止已經(jīng)形成了三種類型的監(jiān)控器：第一類是結(jié)構(gòu)型監(jiān)控器，通過在對象網(wǎng)內(nèi)添加庫所來禁止某些可控變遷的激發(fā)，從而避免系統(tǒng)演化到禁止?fàn)顟B(tài)3-4；第二類是邏輯型監(jiān)控器，以受控Petri網(wǎng)為模型，監(jiān)控器是狀態(tài)的函數(shù)，它實時地為各控制庫所的標(biāo)識賦值，從而禁止某些可控變遷的激發(fā)5-7；第三類是混合型監(jiān)控器，以受控Petri網(wǎng)為模型，首先設(shè)計觀測器庫所，其次根據(jù)觀測器庫所的標(biāo)識計算各控制庫所標(biāo)識的賦值函數(shù)8-10。文獻(xiàn)11指出與邏輯型監(jiān)控器相比結(jié)構(gòu)型監(jiān)控器具有下列優(yōu)點：在線計算迅速，采用相同的規(guī)則構(gòu)建的監(jiān)控器子網(wǎng)和對象網(wǎng)有利于采用統(tǒng)一的Petri算法實現(xiàn)。但是在某些情況下不存

7、在最優(yōu)的結(jié)構(gòu)型監(jiān)控器12。文獻(xiàn)8指出，混合型監(jiān)控器在設(shè)計和計算上具有結(jié)構(gòu)型觀測器的優(yōu)點，而在監(jiān)控器的給出形式上具有邏輯型監(jiān)控器的優(yōu)點。本文給出了一類滿足下列條件的禁止?fàn)顟B(tài)問題的最優(yōu)混合型監(jiān)控器的設(shè)計方法：1）控制規(guī)范為廣義互斥約束；2）不可控影響子網(wǎng)為狀態(tài)機。根據(jù)狀態(tài)機的特性，我們設(shè)計了稱為觀測器的不影響對象網(wǎng)演變的庫所，它具有兩個性質(zhì)：一是其標(biāo)識不大于某一上界是判定當(dāng)前標(biāo)識為允許標(biāo)識的充要條件；二是其輸入變遷均為可控變遷。第一條性質(zhì)將多禁止庫所的約束簡化為單禁止庫所的約束；第二條性質(zhì)則使得我們在設(shè)計監(jiān)控器時不必考慮不可控變遷。因此利用觀測器就可以將原來存在不可控變遷的監(jiān)控問題簡化為相當(dāng)于變遷

8、全部可控的監(jiān)控問題。最后我們給出了利用觀測器設(shè)計最優(yōu)監(jiān)控器的算法。需要指出的是，本文對文獻(xiàn)10作了如下拓展：1）將控制規(guī)范從兩個禁止庫所的特殊約束推廣到一般的廣義互斥約束；2）將禁止?fàn)顟B(tài)問題從要求整個對象網(wǎng)為狀態(tài)機推廣到僅要求不可控影響子網(wǎng)為狀態(tài)機；3）大量地減小了觀測器的個數(shù)，文獻(xiàn)10要求一個禁止庫所對應(yīng)一個觀測器，而本文僅要求為一個廣義互斥約束設(shè)計一個觀測器。2 基本概念受控Petri網(wǎng)是一個五元組，記為， P是狀態(tài)庫所集；T是變遷集；是一個變遷和庫所或庫所和變遷組成的二元組的集合； C是控制庫所集；是控制庫所和變遷組成的二元組的集合?？煽刈冞w集表示為，不可控變遷的集合表示為。一個狀態(tài)庫所

9、p的輸入變遷集和輸出變遷集分別表示為和，一個變遷t的輸入和輸出庫所集分別表示為和。標(biāo)識是托肯在狀態(tài)庫所中的一個分布，表示為一個函數(shù)（列向量），其中第i維上的分量，表示狀態(tài)庫所含有的托肯數(shù)，。控制是托肯在控制庫所中的一個分布，表示為一個函數(shù)（列向量），其中第i維上的分量，表示控制庫所含有的托肯數(shù)，。，。一個受控Petri網(wǎng)也可以表示為一個有向圖，其中不可控變遷、可控變遷、庫所、控制庫所和托肯分別表示為杠、圓圈、方框和圓點。如果，那么t在標(biāo)識m下是狀態(tài)使能的。不可控變遷都是控制使能的。給定一個可控變遷t，如果它的輸入控制庫所在u下被標(biāo)識，那么它在控制u下是控制使能的。在當(dāng)前標(biāo)識和控制下，如果一個變

10、遷既是狀態(tài)使能的又是控制使能的，那么它是使能的。在受控Petri網(wǎng)內(nèi)，只有使能的變遷可以激發(fā)，并且一個變遷激發(fā)后將從它的每個輸入狀態(tài)庫所中去掉一個托肯，同時在它的每個輸出庫所中添加一個托肯，但并不改變它的輸入控制庫所內(nèi)的托肯?？刂茙焖耐锌鲜怯赏獠刻砑拥模灿赏獠刻蕹?。本文中Petri網(wǎng)的演變是基于并發(fā)的。一個變遷的多重集合表示為一個函數(shù)（列向量），其第i維上的分量表示相應(yīng)的變遷在該多重集合中出現(xiàn)的次數(shù)，。在標(biāo)識m和控制u下，的變遷能夠同時激發(fā)記做；激發(fā)將導(dǎo)致標(biāo)識演變?yōu)橛涀?。表示在控制u下從m開始連續(xù)激發(fā)不多于k個變遷多重集合到達(dá)的標(biāo)識的集合，k為非負(fù)整數(shù)。也稱為在u下從m開始k步可達(dá)的標(biāo)識

11、的集合。指系統(tǒng)從m開始k步不可控可達(dá)的標(biāo)識的集合。指系統(tǒng)從m不可控可達(dá)的標(biāo)識的集合。如果，那么對于任意自然數(shù)k, 。定義113：給定一個偏序集，如果，那么是X的下向集。為X的下向集的集合。狀態(tài)反饋控制策略是從標(biāo)識集到控制集合的全部下向集的集合的映射，記做，其中表示系統(tǒng)的所有標(biāo)識的集合，表示全體控制的集合。本文將沿用文獻(xiàn)14中關(guān)于允許性的偏序關(guān)系：，那么；如果，并且，那么。令k為任意自然數(shù)，表示在U下從m開始k步可達(dá)的標(biāo)識的集合。如果，那么對于任意自然數(shù)k, 16。廣義互斥約束是一個二元組，其中是狀態(tài)庫所的權(quán)值函數(shù)（向量），是標(biāo)識加權(quán)和的上界。禁止庫所集表示為。禁止標(biāo)識集表示為。合法標(biāo)識集表示為

12、。允許標(biāo)識集是無法不可控地到達(dá)任意禁止標(biāo)識的標(biāo)識的集合，表示為。為了敘述方便，本文考慮的控制規(guī)范默認(rèn)為上述定義的廣義互斥約束。如果，那么u是m的一個允許控制。如果u是m的一個允許控制，并且，那么u是m的一個最大允許的控制。如果，那么U是m的一個允許的狀態(tài)反饋控制策略。如果U是m的一個允許狀態(tài)反饋控制策略，并且，那么U是m的一個最大允許的狀態(tài)反饋控制策略。引理114 ：給定Petri網(wǎng)系統(tǒng)和廣義互斥約束，當(dāng)且僅當(dāng)時，存在最大允許的禁止?fàn)顟B(tài)監(jiān)控器。從到的路徑是一個庫所的序列，其中：并且，：。我們稱是的一條路徑。如果每相鄰的兩個庫所之間都有一個不可控變遷從前一個庫所連向后一個庫所，那么該路徑叫做不可

13、控路徑。庫所p的影響域是p的全部不可控路徑組成的集合。p的不可控影響子網(wǎng)為其全部不可控路徑組成的子網(wǎng)。在設(shè)計廣義互斥約束的狀態(tài)反饋的監(jiān)控器時，只需考慮禁止庫所的不可控影響子網(wǎng)。3 不可控影響子網(wǎng)為狀態(tài)機的Petri網(wǎng)上的可達(dá)性分析允許標(biāo)識的判據(jù)是解決禁止?fàn)顟B(tài)控制問題的關(guān)鍵，它可以通過對Petri網(wǎng)的可達(dá)性分析得到。本節(jié)將給出可以應(yīng)用于可達(dá)性分析的網(wǎng)性質(zhì)，從而為監(jiān)控器綜合奠定基礎(chǔ)。引理2： 給定一個Petri網(wǎng)N，設(shè)它的一個庫所p的不可控影響子網(wǎng)是狀態(tài)機，如果庫所在p的不可控影響子網(wǎng)內(nèi)，那么中的一個托肯可以導(dǎo)致p不可控地得到的托肯的最大個數(shù)是1。證明：根據(jù)不可控影響子網(wǎng)的定義，內(nèi)任何變遷都無法導(dǎo)

14、致p不可控得到的托肯。因為在p的不可控影響子網(wǎng)，所以必然有一條不可控路徑是從到p的，我們設(shè)該路徑為，因為是狀態(tài)機，所以連接內(nèi)相鄰的庫所的不可控變遷均只有一個輸入庫所和一個輸出庫所，所以中的一個托肯可以使得中的變遷組成的序列激發(fā)，從而導(dǎo)致p得到1個托肯。因為狀態(tài)機上的變遷均只有一個輸入和輸出庫所，且弧上的權(quán)值都是1，因此由中的1個托肯引起的任意變遷序列的激發(fā)不會使得不可控影響子網(wǎng)內(nèi)增加新的托肯?？v上所述，中的一個托肯可以導(dǎo)致p不可控地得到的托肯的最大個數(shù)是1。 ¢引理3： 給定一個Petri網(wǎng)N，設(shè)其中和分別對應(yīng)的不可控影響子網(wǎng)和均為狀態(tài)機，如果一個庫所同時包含在和各自的不可控影響子網(wǎng)

15、內(nèi)，那么中的一個托肯無法導(dǎo)致和同時被標(biāo)識。證明：因為狀態(tài)機上的變遷均只有一個輸入和輸出庫所，且弧上的權(quán)值都是1，因此由中的1個托肯引起的任意變遷序列的激發(fā)不會使得狀態(tài)機中增加新的托肯。因此根據(jù)引理2，中的一個托肯只能保證和中的一個同時被標(biāo)識。 ¢定義2： 給定Petri網(wǎng)和一個廣義互斥約束，設(shè)每一個禁止庫所的不可控影響子網(wǎng)是狀態(tài)機，庫所關(guān)系函數(shù)（行列矩陣）是從到非負(fù)整數(shù)集合的映射，記做，定義如下：其中是禁止庫所集，P為Petri網(wǎng)的庫所集。 定義3： 給定Petri網(wǎng)和一個廣義互斥約束，設(shè)每一個禁止庫所的不可控影響子網(wǎng)是狀態(tài)機，危險權(quán)值函數(shù)（維向量）是從庫所集到非負(fù)整數(shù)的映射，記做，

16、定義如下：其中是禁止庫所集，P為Petri網(wǎng)的庫所集，R是庫所關(guān)系函數(shù)。定理1： 給定Petri網(wǎng)和一個廣義互斥約束，設(shè)每一個禁止庫所的不可控影響子網(wǎng)是狀態(tài)機，那么下式成立：其中是危險權(quán)值函數(shù)，是Petri網(wǎng)的狀態(tài)空間，是從m不可控可達(dá)的全部標(biāo)識的集合。證明：根據(jù)引理2和定義2可知，庫所關(guān)系函數(shù)表示中的一個托肯將不可控地導(dǎo)致的最大增量。因此根據(jù)引理3和定義3可知，危險權(quán)值函數(shù)表示p中的一個托肯將不可控地導(dǎo)致加權(quán)標(biāo)識和的最大增量。因此在中標(biāo)識加權(quán)和的最大值等于。 ¢注釋1： 在從任意標(biāo)識m不可控可達(dá)的標(biāo)識集合中，定理1給出了標(biāo)識加權(quán)和的最大值，記做，顯然如果，那么當(dāng)前標(biāo)識m是允許標(biāo)識。

17、3 觀測器本節(jié)將利用上節(jié)中給出的網(wǎng)性質(zhì)在對象網(wǎng)中添加觀測器，從而將Petri網(wǎng)禁止標(biāo)識可達(dá)性分析計算融合為網(wǎng)結(jié)構(gòu)。定義4：給定Petri網(wǎng)和一個廣義互斥約束，設(shè)每一個禁止庫所的不可控影響子網(wǎng)是狀態(tài)機，變遷的增益函數(shù)（維向量）是從變遷集到整數(shù)集的映射，記做，定義如下： 其中T是Petri網(wǎng)的變遷集，是危險權(quán)值函數(shù)。定義5：給定Petri網(wǎng)和一個廣義互斥約束，設(shè)每一個禁止庫所的不可控影響子網(wǎng)是狀態(tài)機，按照下列規(guī)則添加到網(wǎng)內(nèi)的庫所O稱為觀測器：1） 給定一個變遷，如果，添加一條從O到t的有向弧，弧上的權(quán)值是；如果，t和O之間無有向?。蝗绻?，添加一條從t到O的有向弧，弧上的權(quán)值是。2） ，其中是危險權(quán)

18、值函數(shù)。下面的定理將給出觀測器的性質(zhì)，這些性質(zhì)是本文監(jiān)控器設(shè)計的基礎(chǔ)。定理2：給定Petri網(wǎng)和一個廣義互斥約束，設(shè)每一個禁止庫所的不可控影響子網(wǎng)是狀態(tài)機，庫所O是觀測器，那么下列結(jié)論成立：1） ，當(dāng)且僅當(dāng)時，m是允許標(biāo)識；2） 觀測器的輸入變遷均為可控變遷，即 ；3） 當(dāng)且僅當(dāng)時，監(jiān)控器存在；4） 觀測器不影響對象網(wǎng)中任何變遷的激發(fā)。證明：1）給定任意變遷t和任意標(biāo)識m，如果t的激發(fā)導(dǎo)致系統(tǒng)標(biāo)識從m到，即，那么根據(jù)觀測器的定義可知：其中是變遷的增益函數(shù)。根據(jù)變遷的增益函數(shù)的定義可知：根據(jù)式和式，可知：其中是危險權(quán)值函數(shù)。根據(jù)式和觀測器的定義可知：根據(jù)式可知，當(dāng)且僅當(dāng)時，m是允許標(biāo)識。因此根據(jù)

19、式，當(dāng)且僅當(dāng)時，m是允許標(biāo)識。 2） 根據(jù)定理1可知，因為，因此下式成立：根據(jù)式和式，可知：根據(jù)式和式可知：。因此觀測器的輸入變遷只能是可控變遷，即。 3）根據(jù)該引理的第1項可知，當(dāng)且僅當(dāng)時，初始標(biāo)識是允許標(biāo)識。根據(jù)引理1可知，當(dāng)且僅當(dāng)時，監(jiān)控器存在。4）假設(shè)觀測器將影響對象網(wǎng)的運行，那么存在一個標(biāo)識，在m下存在一個使能的變遷多重集合，它的激發(fā)將導(dǎo)致系統(tǒng)標(biāo)識變?yōu)?，且。根?jù)式(8)可知，因為且，所以，而這和假設(shè)相矛盾，因此假設(shè)是錯誤的，觀測器不會影響對象網(wǎng)的演變。 ¢注釋2：定理2給出了觀測器的性質(zhì)：第一條給出了允許標(biāo)識的判據(jù)，即當(dāng)且僅當(dāng)觀測器的標(biāo)識不大于k（廣義互斥約束中標(biāo)識加權(quán)和的

20、上界）時，當(dāng)前標(biāo)識是允許標(biāo)識，也就是說，只要保證觀測器的標(biāo)識不超過k就相當(dāng)于在對象網(wǎng)上實現(xiàn)了該廣義互斥約束。顯然我們利用觀測器將多禁止庫所廣義互斥約束問題簡化成了單禁止庫所約束問題。第二條說明只有可控變遷的激發(fā)才能夠使得觀測器的標(biāo)識增加。第三條給出了監(jiān)控器存在的充要條件。第四條說明觀測器并不影響對象網(wǎng)的狀態(tài)演變，即觀測器只起到了觀測的作用，而沒有控制的作用。4. 監(jiān)控器算法 根據(jù)觀測器的性質(zhì)，本節(jié)首先給出了監(jiān)控器存在的充要條件，其次設(shè)計了最大允許的狀態(tài)反饋監(jiān)控器算法。給定任意標(biāo)識m和一個控制u，根據(jù)定理2，當(dāng)且僅當(dāng)時，u是m的一個允許的控制；也就是說，當(dāng)且僅當(dāng)在中觀測器的最大標(biāo)識不大于k時，那

21、么u是m的一個允許的控制，因此在判斷u是不是m的允許的控制時，我們只需考慮觀測器的輸入變遷，根據(jù)定理2可知，因此在計算最大允許狀態(tài)反饋控制策略時，我們只需要考慮對象網(wǎng)中可控變遷，這實質(zhì)上是把存在不可控變遷的問題簡化成了變遷全部可控的問題。定理3：給定Petri網(wǎng)和一個廣義互斥約束，設(shè)每一個禁止庫所的不可控影響子網(wǎng)是狀態(tài)機，庫所O是觀測器。對于標(biāo)識和控制u，u是m的一個允許的控制的充要條件是：其中是變遷增益函數(shù)，是控制使能的可控變遷集，。證明：根據(jù)定理2可知，觀測器的輸入變遷都是可控變遷，及，因此只有可控變遷的激發(fā)才可以使得觀測器的標(biāo)識增加。中的庫所是觀測器的輸入變遷的輸入庫所，根據(jù)不可控影響子

22、網(wǎng)的定義，中的庫所都在不可控影響子網(wǎng)內(nèi)，而不可控影響子網(wǎng)是狀態(tài)機，因此如果，那么，t最多可以激發(fā)次。根據(jù)觀測器的定義，變遷增益函數(shù)表示觀測器與變遷之間有向弧上的權(quán)值，縱上所述可知：根據(jù)式和定理2可知，當(dāng)且僅當(dāng)式成立時，中的標(biāo)識均是允許標(biāo)識，及當(dāng)且僅當(dāng)式成立時，u是m的允許的控制。 ¢給定Petri網(wǎng)和一個廣義互斥約束，設(shè)每一個禁止庫所的不可控影響子網(wǎng)是狀態(tài)機，下面給出最大允許狀態(tài)反饋監(jiān)控器算法。算法1：最大允許狀態(tài)反饋監(jiān)控器算法輸入：受控Petri網(wǎng)和廣義互斥約束1） 確定每一個禁止庫所的不可控影響子網(wǎng)。2） 如果某個禁止庫所的不可控影響子網(wǎng)不是狀態(tài)機，算法退出。3） 計算庫所關(guān)系函

23、數(shù)，根據(jù)庫所關(guān)系函數(shù)確定危險權(quán)值函數(shù)。4） 根據(jù)危險權(quán)值函數(shù)計算變遷增益函數(shù)，根據(jù)變遷增益函數(shù)構(gòu)建觀測器。5） 如果，那么監(jiān)控器不存在，算法退出；否則執(zhí)行下一步。6） 那么給定任意可達(dá)標(biāo)識，它的最大允許狀態(tài)反饋控制策略U由下式給出：其中是變遷增益函數(shù)，是控制使能的可控變遷集，。輸出：狀態(tài)反饋控制策略U.注釋3：第14步是離線的，其中第4步（監(jiān)控器存在性的判斷）的依據(jù)是定理2。算法中只有第5步是在線的，它的依據(jù)是定理3。一旦得到式(14)，我們就可以利用它來計算任意允許標(biāo)識的最大允許狀態(tài)反饋控制策略。需要指出的是本文給出的最大允許控制策略與文獻(xiàn)5一樣都是不確定性的，即最大允許控制策略給出的是控制

24、的集合，在線控制時可以從該集合中隨機地或利用其它的控制目標(biāo)來選擇一個允許的控制。4 應(yīng)用舉例圖1. 一條地鐵線路相鄰幾個區(qū)段的Petri網(wǎng)模型文獻(xiàn)15討論了地鐵安全調(diào)度的問題，給出了一條地鐵線路交通系統(tǒng)的Petri網(wǎng)模型，如圖1所示。地鐵線路交通系統(tǒng)是由一條地鐵線路和單向行駛的多列車組成的系統(tǒng)，當(dāng)相鄰后一列車超速或者前一相鄰列車減速（比如故障停車）時，兩相鄰列車就會相撞，從而造成嚴(yán)重的安全事故，甚至導(dǎo)致整條地鐵線路交通混亂，經(jīng)濟損失巨大。安全調(diào)度就是通過對各地鐵運行狀態(tài)的監(jiān)控避免列車相撞，基本的安全調(diào)度策略是：將一條地鐵線路分為多個區(qū)段，限制地鐵線路的每一區(qū)段只能出現(xiàn)1列車，從而避免列車相撞。

25、對應(yīng)于地鐵線路交通系統(tǒng)的Petri網(wǎng)模型，安全調(diào)度問題可以描述為Petri網(wǎng)標(biāo)識的線性不等式約束。圖1的實線部分是一條地鐵線路4個相鄰區(qū)段的Petri網(wǎng)模型，它們分別是地鐵線路的第k-2、k-1、k和k+1區(qū)段，其中每一個區(qū)段用其對應(yīng)一列庫所來描述：區(qū)段k-2對應(yīng)的庫所是、和；區(qū)段k-1對應(yīng)的庫所是、和；區(qū)段k是一個車站，其對應(yīng)的庫所是和；區(qū)段k+1對應(yīng)的庫所是和。網(wǎng)內(nèi)的1個托肯表示1列車。所有的庫所排列成4行， 每行庫所代表了列車在區(qū)段內(nèi)的行車模式，第一行庫所的行車模式：在區(qū)段的起點啟動，在區(qū)段的終點停止；第二行庫所的行車模式：從區(qū)段的起點啟動，然后勻速駛過該區(qū)段；第三行庫所的行車模式：從區(qū)

26、段起始點開始一直勻速行駛，最后停止在該區(qū)段終點；第四行庫所的行車模式：列車勻速駛過整個區(qū)段。例如中有一個托肯的意義是：一列車在k-2區(qū)段內(nèi)行駛，它從起點開始勻速行駛，最后停在終點。變遷的激發(fā)具有兩個含義：1）列車離開其輸入庫所對應(yīng)的區(qū)段，并駛?cè)肫漭敵鰩焖鶎?yīng)的區(qū)段；2）列車的行車模式切換為該變遷的輸出庫所對應(yīng)的行駛模式。網(wǎng)內(nèi)存在不可控變遷，例如中含有一個托肯，那么1列車按照第二行庫所對應(yīng)的行車模式在區(qū)段k-2（對應(yīng)于）內(nèi)行駛，它在區(qū)段終點時速度不為0，它進(jìn)入k-1區(qū)段后起始速度不為0，因此中的托肯只能進(jìn)入或，即導(dǎo)致或激發(fā)，我們可以禁止其在k-1區(qū)段終點的速度不為0，因此是可控的；而我們不能禁止

27、其在k-1區(qū)段終點的速度為0，因此是不可控的。地鐵安全調(diào)度是要求地鐵線路的每個區(qū)段最多出現(xiàn)1列車，其對應(yīng)的Petri網(wǎng)控制目標(biāo)是一組廣義互斥約束：要求每列庫所的標(biāo)識之和不超過1。下面以k列庫所（車站）對應(yīng)的安全調(diào)度問題為例給出安全調(diào)度的控制策略：為了避免車站發(fā)生列車相撞，需要確保網(wǎng)的標(biāo)識滿足約束，即要求車站最多出現(xiàn)1列車。根據(jù)算法1計算最大允許的控制策略：1）確定庫所和的不可控影響子網(wǎng)和，僅包括庫所，包括庫所、和與它們相連的不可控變遷，顯然和均為狀態(tài)機，因此可以采用算法1來設(shè)計控制策略；2）根據(jù)定義2計算庫所關(guān)系函數(shù)：如果，那么，否則；如果i等于6、8或10時，否則。3）根據(jù)定義3利用庫所關(guān)系

28、函數(shù)給出危險權(quán)值函數(shù)：如果i等于6、8、9或10時，否則。根據(jù)危險權(quán)值函數(shù)計算變遷有效增益函數(shù)4）根據(jù)定義5，利用危險權(quán)值函數(shù)設(shè)計觀測器，如圖1中虛線部分所示。5），因此監(jiān)控器存在。6），。根據(jù)式(14)給出最大允許的控制策略：。顯然。文獻(xiàn)15在解決該監(jiān)控問題時，需要在線地分析不可控影響子網(wǎng)內(nèi)每個庫所狀態(tài)和每個變遷的狀態(tài)使能情況，然后計算最大允許控制策略。而且文獻(xiàn)15也指出其給出的控制器的在線計算的復(fù)雜性隨網(wǎng)規(guī)模呈指數(shù)級地增加。在這個例子中，利用觀測器我們將多禁止庫所廣義互斥約束簡化為不必考慮不可控變遷的單禁止庫所廣義互斥約束，從而徹底解決了不可控變遷帶來的“狀態(tài)空間爆炸”問題。因此無論網(wǎng)規(guī)模

29、如何增加，我們都只需在線求解一個不必考慮不可控變遷的單禁止庫所約束。5 結(jié)論本文給出了不影響對象網(wǎng)運行的觀測器的設(shè)計方法，從兩個方面對原來控制問題進(jìn)行了簡化：一是將多禁止庫所的廣義互斥約束簡化為單禁止庫所的廣義互斥約束，這樣在監(jiān)控器綜合時就從根本上避免了前向路徑問題14；二是將存在可控變遷的問題簡化為相當(dāng)于變遷全部可控的問題。這樣利用觀測器技術(shù)就把原來復(fù)雜的控制問題有效地簡化為相對簡單的控制問題。參考文獻(xiàn)1 A. Giua, F. DiCesare, and M. Silva, Generalized mutual exclusion constraints on nets with unco

30、ntrollable transitions, Proc. 1992 IEEE Int. Conf. on System, Man and Cybernetics, October, 1992, pp.974979.2 A. Giua, and X. L. Xie, Control of safe ordinary Petri nets with marking specifications using unfolding, Proc. IFAC WODES04: 7th Workshop on Discrete Event Systems (Reims, France), Sep. 2004

31、.3 J. O. Moody and P. J. Antsaklis, Petri net supervisors for DES with uncontrollable and unobservable transitions, IEEE Trans. Automatic Control, vol. 45, Mar. 2000, pp. 462-476.4 M. Uzam, Synthesis of feedback control elements for discrete event systems using Petri net models and theory of regions

32、, Int J Adv Mauf Technol, vol.24, 2004, pp.48-69.5 L. E. Holloway and A. S. Khare and Yu Gong, Computing bounds for forbidden state reachability functions for controlled Petri nets, IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Human, 34(3), 2004, pp.219-228.6 A. Ghaffari, N.

33、 Rezg, and X. L. Xie, Feedback control logic for forbidden-state problems of Marked Graphs: application to a real manufacturing system, IEEE Tran. on Automatic Control, 48(1), 2003, pp.18-29.7 Dong Li-da, Wu Wei-min, Xu Wei-hua and Chu Jian, Controller design for a class of controlled Petri netsJ, C

34、ontrol Theory and Applications, 2003, 20(5):678-684. 8 Wu Wei-min, Dong Li-da, Wang Xiao, Su Hongye, Chu Jian. Combined Petri net controller for discrete event systems. ACTA Automatica Sinica. 2003, 29(5):681-6889 羅繼亮, 吳維敏, 蘇宏業(yè), 褚健. 事件圖的混合監(jiān)控器設(shè)計，自動化學(xué)報，2007，33(2)：218-22110 羅繼亮, 吳維敏, 蘇宏業(yè), 褚健. 一類離散事件系統(tǒng)的

35、混合控制器設(shè)計, 系統(tǒng)工程理論與實踐. 2006,26(12):10510911 A. Giua, Petri net techniques for supervisory control of discrete event systems. Prc. Of 1st workshops on manufacturing and Petri nets, Oska, Japan, 1996.12 F. Basile, P. Chiacchio, and A. Giua, On the choice of suboptimal monitor places for supervisory contr

36、ol of Petri nets. Proc. Of 1998 IEEE Int. Conf. on Systems, Man, and Cybernetics, pp.752757.13 B. A. Davey, and H. A. Priestley, Introduction to lattices and order. Cambridge University Press, 199014 L. E. Holloway, B. H. Krogh, and A. Giua, A survey of Petri net methods for controlled discrete even

37、t systems, Discrete Event Dynamic Systems: Theory and Applications, 7, 1997, pp.151190.15 R. K. Boel, L. Ben-Naoum and V. V. Breusegem, On forbidden-state problems for a class of controlled Petri nets, IEEE Transactions on Automatic Control, 1995, 40(10):1717-1731.羅繼亮，男，1977年3月出生，博士，講師，從事離散事件系統(tǒng)監(jiān)控、Pe

38、tri 網(wǎng)理論與應(yīng)用等研究. 電話 E-mail: ljlng77, jlluo. (LUO Ji-Liang，Male, He was born in 1977. Received his Ph. D. degree in Department of Control Science and Engineering from Zhejiang University in 2006. He is currently a lecturer at Huaqiao University. His research interests include discrete ev

39、ent systems supervisory and Petri net theory and application. Phone: 86 E-mail: ljlng77, jlluo.)文章背景由計算機控制的很多大型對象都可以描述為離散事件系統(tǒng), 例如柔性制造系統(tǒng)、網(wǎng)絡(luò)通信系統(tǒng)、智能交通系統(tǒng)等等，甚至計算機體系本身就是一個典型的離散事件系統(tǒng)。由于資源有限，在離散事件系統(tǒng)中存在禁止?fàn)顟B(tài)問題，例如鐵路交通系統(tǒng)中兩列火車的沖撞、數(shù)據(jù)通信系統(tǒng)中緩存有限導(dǎo)致數(shù)據(jù)包的丟失、柔性制造系統(tǒng)中空間有限導(dǎo)致裝有工件的托盤沖撞、柔性制造系統(tǒng)中自動導(dǎo)航小車在通過共用區(qū)域時的沖撞等等

40、。為了系統(tǒng)的安全運行，禁止?fàn)顟B(tài)問題是一類急待解決的問題。由于圖形化和并行的優(yōu)點，Petri已經(jīng)成為離散事件系統(tǒng)主流的建模工具。本文是利用Petri網(wǎng)為離散事件系統(tǒng)的模型，研究了一類禁止?fàn)顟B(tài)問題，在分析網(wǎng)結(jié)構(gòu)的基礎(chǔ)上，得到了觀測器設(shè)計方法，并進(jìn)一步利用觀測器設(shè)計的監(jiān)控器的設(shè)計算法。Research BackgroundThe supervisory control theory was introduced in as a conceptual framework for studying the supervision of discrete event systems (DESs). Its

41、 objective is to synthesize a supervisor blocking some events to realize the given specified controlled behavior of the controlled system. Petri nets are a common formalism for the supervisor synthesis for DESs. And Petri nets have been successfully proposed as modeling formalism for DESs control as

42、 an alternative to controlled automata. The generalized mutual exclusion constraint (GMEC) is introduced in to express a set of forbidden states for a Petri net in which conflicts caused by restricted resource occur, such as the collisions of the trains in metro lines, the collisions of the pallets

43、in a manufacturing systems, resource conflicts, deadlocks, sequencing specification, and buffer overflow and operation rules in manufacturing systems.In this paper, we study a class of Petri net control problems to enforce a conjunction of GMECs on State Machines with uncontrollable transitions, and

44、 propose a method to design the optimal combined supervisor. For this kind of problems, there have been methods to design the structure supervisor and the mapping supervisor. For Petri nets with uncontrollable transitions, there not always is the optimal structural supervisor, and the computation co

45、mplexity of mapping supervisors is high and it is difficult to analyze the closed systems under mapping supervisors utilizing Petri net theory. For this class of control problems, the optimal combined supervisor synthesis method is proposed. The observer net is designed, and then, the optimal control policy is calculated based