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

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

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

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

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

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

1 基本定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證明：假設(shè)σ∈П(Ms，Mtarget)，為一個(gè)最優(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)識(shí)。由于序列σ′是由σ調(diào)整變遷順序得到，因此cTyσ′=cmin，即σ也是一個(gè)最優(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)是最小，等號(hào)必然成立，即cTyσ″=cmin。這表明σ″=σ1t1σ2t2…σntn是一個(gè)最優(yōu)控制序列，定理得證。

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

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

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

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

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

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

③ 令cmin=∞，vmin=v0；

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

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

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

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

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

⑩ 若q′

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

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

4 算 例

考慮圖1所示的智能制造系統(tǒng)。其中生產(chǎn)線I：p1t2p2t3p3負(fù)責(zé)對(duì)待加工產(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)過(guò)p13t17p14進(jìn)行組裝得到成品，成品校驗(yàn)合格后進(jìn)入庫(kù)房。庫(kù)所p15的容量為9，即整個(gè)系統(tǒng)能容納的最大產(chǎn)品數(shù)量為9。

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

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

為了模擬上述調(diào)度問(wèn)題，從系統(tǒng)的可達(dá)空間中隨機(jī)選取10組標(biāo)識(shí)作為調(diào)度源標(biāo)識(shí)，代表系統(tǒng)在運(yùn)行了一段時(shí)間后所處的狀態(tài)。實(shí)驗(yàn)程序基于Python 3.7.6編寫，在一臺(tái)配備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)識(shí)下算法1與ILP-D方法的求解結(jié)果對(duì)比

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

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

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

5 結(jié)束語(yǔ)

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