一種Petri網(wǎng)最優(yōu)控制序列的高效設(shè)計方法

鄒岷強(qiáng)，馬子玥

(西安電子科技大學(xué) 機(jī)電工程學(xué)院，陜西 西安 710071)

在現(xiàn)代柔性可重構(gòu)自動控制系統(tǒng)中[1-4]，系統(tǒng)需要在多個生產(chǎn)模式之間進(jìn)行切換。由于模式切換往往需要系統(tǒng)處在某些特定的安全狀態(tài)下才能進(jìn)行，因此在收到指令時，相應(yīng)的控制器會被激活并接管系統(tǒng)，并通過執(zhí)行一組控制序列將系統(tǒng)驅(qū)動至安全狀態(tài)以進(jìn)行模式切換。通常情況下，系統(tǒng)中事件的執(zhí)行會產(chǎn)生一定的成本(例如物料或時間的消耗等)，因此人們往往期望能夠使用低成本的控制序列實現(xiàn)系統(tǒng)狀態(tài)的切換。在所有合法的控制序列中，成本最低的序列被稱為“最優(yōu)控制序列”。近些年來，如何高效在線計算最優(yōu)控制序列得到了人們的廣泛關(guān)注[5-6]。

Petri網(wǎng)作為離散事件系統(tǒng)的基本模型之一，已經(jīng)被用于包括柔性制造系統(tǒng)、無人倉儲、航電控制系統(tǒng)等各類可重構(gòu)自動控制系統(tǒng)的建模與分析[1-15]。因此，近年來人們對Petri網(wǎng)中的控制序列設(shè)計問題進(jìn)行了廣泛研究[5-10]，提出了許多設(shè)計最優(yōu)控制序列的方法，例如廣泛使用的模型預(yù)測控制[7]的搜索算法等。但是，此類搜索算法都是基于Petri網(wǎng)可達(dá)空間的窮舉搜索，因此不可避免地遇到狀態(tài)爆炸問題，使其在線計算效率低。另一方面，部分研究者提出的一些貪婪算法[8]和整數(shù)規(guī)劃[9-11]雖然計算速度較快，但是其得到的控制序列不能保證最優(yōu)，或是在線計算復(fù)雜度較高，往往不適用于實際情況。

近年來，CABASINO等[16]和MA等[17]提出了一種利用基本標(biāo)識來對Petri網(wǎng)可達(dá)空間進(jìn)行無損壓縮的方法，從而避免對狀態(tài)空間進(jìn)行窮舉，大幅減少了計算量。通過將基本標(biāo)識分析方法和Dijkstra搜索算法[18]相結(jié)合，筆者提出一種高效求解Petri網(wǎng)最優(yōu)控制序列的方法。算法將Dijkstra搜索的范圍限定在被控網(wǎng)的基本標(biāo)識空間中，從而在很大程度上緩解了窮舉可達(dá)空間帶來的狀態(tài)爆炸問題。同時，通過選擇合適的顯式變遷集合來構(gòu)建基本標(biāo)識空間，使得搜索過程中無需求解整數(shù)規(guī)劃。該算法具有在線計算量小、求解速度快的優(yōu)點，適用于受控系統(tǒng)需要對重構(gòu)請求作出快速響應(yīng)的場合。

1 基本定義

文中的Petri網(wǎng)由四元組N=(P，T，Pre，Post)表示。其中P為m個庫所的集合{p1，…，pm}，T為n個變遷的集合{t1，…，tn}。Pre與Post為N的輸入矩陣與輸出矩陣，分別為m行n列的非負(fù)整數(shù)矩陣。Petri網(wǎng)N的關(guān)聯(lián)矩陣定義為C=Post-Pre。

給定Petri網(wǎng)N=(P，T，Pre，Post)，其標(biāo)識M是一個m維的非負(fù)整數(shù)向量。若對于某一變遷t∈T，標(biāo)識M滿足M≥Pre(·，t)，則稱變遷t在標(biāo)識M下使能，記作M[t>。使能的變遷t在M下可以發(fā)射，記作M[t>M′，其中M′是系統(tǒng)經(jīng)變遷t發(fā)射后到達(dá)的標(biāo)識，其滿足狀態(tài)方程M′=M+Post(·，t) - Pre(·，t)=M+C(·，t)。對于一組標(biāo)識M、M′，若存在一組變遷序列σ=t1t2…tn，滿足M[t1>M1，M1[t2>M2，…，Mk-1[tk>M′，則稱標(biāo)識M′從標(biāo)識M可達(dá)，記作M[σ>M′，σ=t1t2…tn。用〈N，M0〉表示帶有初始標(biāo)識M0的Petri網(wǎng)N，稱為初始化的網(wǎng)系統(tǒng)?！碞，M0〉的可達(dá)空間定義為所有從M0可達(dá)的標(biāo)識組成的集合，記為R(N，M0)。

文中用T*表示T上所有由變遷組成的有限長度序列的集合，其上標(biāo)*為Kleene星號運算符。

2 基本標(biāo)識空間

定義1給定Petri網(wǎng)N，其變遷集合為T。若T的兩個子集TE和TI滿足(1)T=TE∪TI，TE∩TI=φ，且(2)TI導(dǎo)出的子網(wǎng)無環(huán)，則稱TE、TI為網(wǎng)變遷集合T的一個基本劃分，記為(TE，TI)。TE和TI分別稱為顯式變遷集合和隱式變遷集合。

定義2給定標(biāo)識M和一個顯式變遷t∈TE：

(2) 給定Σ(M，t)時，定義Y(M，t)={yσ|σ∈Σ(M，t)}，為t在標(biāo)識M下的解釋向量集合；

(3) 給定Y(M，t)時，定義Ymin(M，t)=minY(M，t)，為t在標(biāo)識M下的最小解釋向量集合。

定義3給定Petri網(wǎng)〈N，M0〉和其變遷的一個基本劃分(TE，TI)，其基本標(biāo)識空間Mbasis遞歸定義為：① 初始標(biāo)識M0∈Mbasis；② 若M∈Mbasis，則對所有t∈TE，所有y∈Ymin(M，t)，M′=M+C·y+C(·，t)∈Mbasis。

定義4給定Petri網(wǎng)〈N，M0〉和其變遷的基本劃分(TE，TI)。標(biāo)識M的隱可達(dá)標(biāo)識集合定義為

RI(M)={M′|M[t1t2…tn>M′，t1，t2，…，tn∈TI} 。

定理1若Petri網(wǎng)中M0[σ>M，則存在一組基本標(biāo)識M0-M1- … -Mn且M∈RI(Mn)。

M0[σ1t1>M1[σ2t2>M2…Mn-1[σntn>Mn[σn+1>M，

其中，M0是基本標(biāo)識。由于隱式變遷導(dǎo)出的子網(wǎng)無環(huán)，根據(jù)文獻(xiàn)[15]中定理3，如果σ1所對應(yīng)的發(fā)射向量y1不是M0下t1的最小解釋向量，則一定可以將σ1拆分為兩部分σ1′、σ1″，滿足M0[σ1′t1>M1′[σ1″σ2t2>M2，且σ1′所對應(yīng)的發(fā)射向量是M0下t1的最小解釋向量。那么前式可改寫為

M0[σ1′t1>M1′[σ1″σ2t2>M2…Mn-1[σntn>Mn[σn+1>M，

其中，M1′是基本標(biāo)識。將M1′視為新的初始標(biāo)識，可以反復(fù)應(yīng)用上述變遷拆分重排規(guī)則，最終得到發(fā)射序列：

其中，M0，M1′，…，Mn′都是基本標(biāo)識。因此M∈RI(Mn′)，定理成立。

根據(jù)定理1，無論如何選擇顯式變遷集合和隱式變遷集合，所有基本標(biāo)識均可由初始標(biāo)識到達(dá)，即滿足Mbasis?R(N，M0)，基本標(biāo)識集合一定是可達(dá)集合的子集。文獻(xiàn)[15-17]中的大量仿真結(jié)果表明，在合理選擇顯式變遷集合TE的情況下，一般有|Mbasis|?|R(N，M0)|，即基本標(biāo)識集合的規(guī)模遠(yuǎn)遠(yuǎn)小于可達(dá)集合。

3 最優(yōu)控制序列設(shè)計

在Petri網(wǎng)的最優(yōu)控制序列設(shè)計問題中，控制器需要計算出一個稱為“控制序列”的變遷序列，使得系統(tǒng)在源標(biāo)識Ms下執(zhí)行該控制序列可以到達(dá)某個屬于目標(biāo)標(biāo)識集合Mtarget的標(biāo)識。在現(xiàn)實情況下，執(zhí)行控制序列的目標(biāo)通常是為了將部分子系統(tǒng)的局部資源清空，從而對其進(jìn)行重構(gòu)。這種情況下，期望的目標(biāo)標(biāo)識可由包含“≤”的不等式進(jìn)行描述。因此，為了簡化問題，筆者考慮系統(tǒng)目標(biāo)標(biāo)識集合Mtarget由廣義互斥約束描述的情況。

假設(shè)1系統(tǒng)中的目標(biāo)標(biāo)識由一組廣義互斥約束[19](w，k)表示，即Mtarget={M|wTM≤k}。

定義5給定Petri網(wǎng)〈N，M0〉，N=(P，T，Pre，Post)。令Ms∈R(N，M0)為源標(biāo)識，Mtarget為目標(biāo)標(biāo)識集合，若滿足Ms[σ>M∈Mtarget，則稱該控制序列σ合法。合法控制序列的集合記作П(Ms，Mtarget)。

為了快速響應(yīng)控制需求，人們希望設(shè)計出有效算法，能夠高效地計算得到所需的合法控制序列。同時，變遷的發(fā)射存在一定成本，例如執(zhí)行相應(yīng)事件時發(fā)生的材料或時間的消耗。因此，人們希望得到的控制序列總成本(即該序列所包含的所有變遷的成本之和)盡可能低。

定義6定義成本向量c=[c(t1)，…，c(tn)]T≥ 0，為n維實數(shù)向量，其中c(t)為變遷t的單次發(fā)射成本。控制序列σ的發(fā)射成本定義為cTyσ。

定義7給定Petri網(wǎng)〈N，M0〉，成本向量c，源標(biāo)識Ms∈R(N，M0)，目標(biāo)標(biāo)識集合Mtarget=S(w，k)，若控制序列σ∈П(Ms，Mtarget)的成本cTyσ最小，則稱其為最優(yōu)控制序列，用σmin表示。

注意到定理1雖然保證了M必然屬于某個基本標(biāo)識Mn′的隱式可達(dá)標(biāo)識，但是滿足M∈RI(Mn′)的基本標(biāo)識Mn′(可能不惟一)并不能預(yù)先求得。因此，需要對基本標(biāo)識集合Mbasis中的每一個基本標(biāo)識都進(jìn)行一次判斷。

在文獻(xiàn)[17]中，通過求解整數(shù)線性規(guī)劃來判斷相應(yīng)的隱式變遷序列是否存在，因此需要求解大量的整數(shù)規(guī)劃問題，其實際計算效果并不理想。為規(guī)避整數(shù)線性規(guī)劃的求解，此處筆者提出一個關(guān)于選擇顯式變遷集合的條件。在該條件下，M∈RI(Mn′)的判定可以通過代數(shù)方法簡單計算完成，無需求解整數(shù)規(guī)劃問題。

定理2給定初始標(biāo)識為M0的Petri網(wǎng)N，成本向量c，源標(biāo)識Ms∈R(N，M0)，目標(biāo)標(biāo)識集合Mtarget=S(w，k)。若П(Ms，Mtarget)不是空集且變遷基本劃分(TE，TI)滿足：對所有隱式變遷t，滿足wTC(·，t)≥0，則一定存在一個最優(yōu)控制序列σmin=σ1t1σ2t2…σntn，滿足：Ms[σ1t1>M1[σ2t2>M2，…，Mn-1[σntn>Mn∈Mtarget，其中，Ms，M1，…，Mn均為基本標(biāo)識。

證明：假設(shè)σ∈П(Ms，Mtarget)，為一個最優(yōu)控制序列，則有cTyσ=cmin。根據(jù)定理1，可以將σ中的變遷進(jìn)行重新排列，得到序列σ′=σ1t1σ2t2…σntnσn+1∈П(Ms，Mtarget)，使得Ms[σ1t1>M1[σ2t2>M2…Mn-1[σntn>Mn[σn+1>Mt∈Mtarget。其中，Ms，M1，…，Mn均為基本標(biāo)識。由于序列σ′是由σ調(diào)整變遷順序得到，因此cTyσ′=cmin，即σ也是一個最優(yōu)控制序列。由于Mt∈Mtarget意味著wTMt≤k，且所有隱式變遷t均滿足wTC(·，t) ≥ 0，因此wTMn≤wTMt≤k，即Mn∈Mtarget。由于變遷的發(fā)射成本均非負(fù)，因此從序列σ′中刪去最后一段σn+1，得到的序列σ″=σ1t1σ2t2…σntn，也是合法的控制序列，且cTyσ″≤cTyσ′。由于cTyσ′已經(jīng)是最小，等號必然成立，即cTyσ″=cmin。這表明σ″=σ1t1σ2t2…σntn是一個最優(yōu)控制序列，定理得證。

定理2表明，若選擇基本劃分確保所有滿足wTC(·，t)≥0的變遷t都屬于隱式變遷集合TI(等價地，所有滿足wTC(·，t)<0的變遷t都屬于顯式變遷集合TE)，且合法控制序列集合不為空，則始終存在一個以顯式變遷結(jié)束的最優(yōu)控制序列。因此，在從Ms到Mn的每一步搜索中，都不需要通過求解整數(shù)規(guī)劃來驗證基本標(biāo)識Mi是否可以通過發(fā)射隱式變遷到達(dá)Mtarget，而只需要驗證Mi自身是否屬于Mtarget即可。根據(jù)假設(shè)1，這一條件可以通過檢查Mi是否滿足wTM≤k來直接驗證。在此情況下，無需求解整數(shù)規(guī)劃問題即可快速確定目標(biāo)集合的隱式可達(dá)性。

算法1Petri網(wǎng)最優(yōu)控制序列設(shè)計。

輸入：Petri網(wǎng)〈N，M0〉，N=(P，T，Pre，Post)，成本向量c，源標(biāo)識Ms，目標(biāo)標(biāo)識集合Mtarget=S(w，k)。

輸出：一個最優(yōu)控制序列σ。

① 選擇一個滿足條件的顯式變遷集合；

② 初始化π={v0}其中v0=(Ms，0，Φ，Φ，Φ)并將其標(biāo)記為new；

③ 令cmin=∞，vmin=v0；

⑤ 對所有顯式變遷t∈TE求解出其對應(yīng)的Ymin(M，t)；

⑥ 對Ymin(M，t)中的各個最小解釋向量y：

⑦ 令Mb′=Mb+Cy+C(·，t)；

⑧ 令q′=q+cTy+c(t)；

⑨ 令v′=(Mb′，q′，Mb，t，y)；

⑩ 若q′

算法1將從Ms開始逐步探索基本標(biāo)識空間，對每個已知結(jié)點Mi(即基本標(biāo)識Mi)賦以非負(fù)實數(shù)D(i)以記錄從源結(jié)點Ms到該結(jié)點的當(dāng)前已知最短路徑長度，稱為Ms到Mi的“距離”。在每次迭代時，選擇最接近源結(jié)點的未經(jīng)檢查的結(jié)點(即D(i)值最小的結(jié)點)進(jìn)行下一步檢查，并更新該結(jié)點的后繼結(jié)點的距離D(j)，稱為“松弛”。算法1的復(fù)雜度為|Mbasis||T|，即其時間復(fù)雜度與基本標(biāo)識空間的大小與變遷的數(shù)量分別呈線性關(guān)系。

定理3算法1輸出的控制序列σ為最優(yōu)控制序列。

4 算 例

考慮圖1所示的智能制造系統(tǒng)。其中生產(chǎn)線I：p1t2p2t3p3負(fù)責(zé)對待加工產(chǎn)品進(jìn)行預(yù)處理，生產(chǎn)線II：p4t6p6t9p8和生產(chǎn)線III：p5t7p7t10p9分別負(fù)責(zé)生產(chǎn)半成品A和B，經(jīng)p10集散分配后分別發(fā)往p11和p12進(jìn)行產(chǎn)品所需的表面工藝處理，之后經(jīng)過p13t17p14進(jìn)行組裝得到成品，成品校驗合格后進(jìn)入庫房。庫所p15的容量為9，即整個系統(tǒng)能容納的最大產(chǎn)品數(shù)量為9。

圖1 智能制造系統(tǒng)Petri網(wǎng)模型

該系統(tǒng)的初始標(biāo)識為M0= 9p15+2p16+7p17+4p18，即此時系統(tǒng)中各生產(chǎn)線處于空閑狀態(tài)。假設(shè)系統(tǒng)已經(jīng)運轉(zhuǎn)了一段時間，現(xiàn)突發(fā)故障，需執(zhí)行緊急重啟，必須在系統(tǒng)關(guān)閉之前盡快從生產(chǎn)線上卸下所有正在加工的產(chǎn)品，即目標(biāo)標(biāo)識集合Mtarget={M|M(p15)≥ 9}。為簡化問題，這里假定所有變遷的發(fā)射成本相等。

為了模擬上述調(diào)度問題，從系統(tǒng)的可達(dá)空間中隨機(jī)選取10組標(biāo)識作為調(diào)度源標(biāo)識，代表系統(tǒng)在運行了一段時間后所處的狀態(tài)。實驗程序基于Python 3.7.6編寫，在一臺配備Intel Core i7-10750H 2.60/2.59 GHz CPU，16 GB RAM的筆記本上進(jìn)行，使用的整數(shù)規(guī)劃求解器為Gurobi Optimizer 9.0.3學(xué)術(shù)版。分別使用算法1和基于整數(shù)線性規(guī)劃的Dijkstra方法(ILP-D)進(jìn)行求解，仿真結(jié)果如表1。其中，ILP-D方法是基于文獻(xiàn)[17]中的整數(shù)規(guī)劃求解方法，選取顯示變遷集合TE={t5，t11，t15，t17}。算法1考慮了顯式變遷集合的選擇條件，將滿足wTC(·，t) < 0的變遷加入，選取TE={t5，t11，t15，t18}。

由表1中的結(jié)果可知：

表1 不同源標(biāo)識下算法1與ILP-D方法的求解結(jié)果對比

(1) 在控制序列成本方面，算法1求解得到的控制序列成本與基于文獻(xiàn)[17]的ILP-D方法求解得到的結(jié)果一致，表明算法1得到的控制序列成本是最小的，印證了算法1的正確性。

(2) 在算法的搜索空間方面，算法1與ILP-D方法求解得到的搜索空間大小相仿，其中搜索空間最大約2 000個標(biāo)識。這一搜索空間規(guī)模遠(yuǎn)小于系統(tǒng)的可達(dá)空間規(guī)模(該系統(tǒng)的可達(dá)標(biāo)識數(shù)為763 428)。這是由于上述兩種算法均在基本標(biāo)識空間內(nèi)進(jìn)行Dijkstra搜索，而基本標(biāo)識空間通常比相應(yīng)的可達(dá)空間小很多。因此與傳統(tǒng)方法在可達(dá)空間中進(jìn)行窮舉相比，算法1能夠有效地緩解狀態(tài)爆炸問題。

(3) 從求解時間上看，針對同一源標(biāo)識求解最優(yōu)控制序列時，算法1所需的求解時間僅是ILP-D方法的10%甚至更低。這是由于算法1結(jié)合文中所述的基本標(biāo)識分析(定理2)合適地選取了顯式變遷集合，使得無需求解整數(shù)規(guī)劃即可快速確定目標(biāo)集合的隱式可達(dá)性，從而規(guī)避了繁復(fù)的整數(shù)規(guī)劃求解問題。因此，與文獻(xiàn)[17]中方法需反復(fù)求解整數(shù)規(guī)劃問題相比，算法1具有更低的計算復(fù)雜性與更高的求解效率。

5 結(jié)束語

筆者提出了一種基于基本標(biāo)識分析的Petri網(wǎng)最優(yōu)控制序列設(shè)計算法。該算法在Petri網(wǎng)的基本標(biāo)識空間中進(jìn)行Dijkstra搜索，可有效地緩解傳統(tǒng)方法窮舉完整狀態(tài)空間導(dǎo)致的狀態(tài)爆炸問題。同時，筆者還提出了一種變遷選取規(guī)則，通過選擇符合要求的顯式變遷集合，使得無需求解整數(shù)規(guī)劃即可快速確定目標(biāo)集合的隱式可達(dá)性，規(guī)避了繁復(fù)的整數(shù)規(guī)劃求解。與基于整數(shù)規(guī)劃的Dijkstra方法相比，筆者提出的方法在線計算量小、求解速度快，效率得到顯著提升。