一種Petri網最優控制序列的高效設計方法

2022-07-04 06:13:10鄒岷強馬子玥

西安電子科技大學學報 2022年3期

關鍵詞：定義

鄒岷強，馬子玥

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

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

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

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

1 基本定義

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

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

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

2 基本標識空間

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

定義2給定標識M和一個顯式變遷t∈TE：

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

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

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

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

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

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

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

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

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

其中，M1′是基本標識。將M1′視為新的初始標識，可以反復應用上述變遷拆分重排規則，最終得到發射序列：

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

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

3 最優控制序列設計

在Petri網的最優控制序列設計問題中，控制器需要計算出一個稱為“控制序列”的變遷序列，使得系統在源標識Ms下執行該控制序列可以到達某個屬于目標標識集合Mtarget的標識。在現實情況下，執行控制序列的目標通常是為了將部分子系統的局部資源清空，從而對其進行重構。這種情況下，期望的目標標識可由包含“≤”的不等式進行描述。因此，為了簡化問題，筆者考慮系統目標標識集合Mtarget由廣義互斥約束描述的情況。

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

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

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

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

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

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

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

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

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

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

算法1Petri網最優控制序列設計。

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

輸出：一個最優控制序列σ。

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

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

③ 令cmin=∞，vmin=v0；

⑤ 對所有顯式變遷t∈TE求解出其對應的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開始逐步探索基本標識空間，對每個已知結點Mi(即基本標識Mi)賦以非負實數D(i)以記錄從源結點Ms到該結點的當前已知最短路徑長度，稱為Ms到Mi的“距離”。在每次迭代時，選擇最接近源結點的未經檢查的結點(即D(i)值最小的結點)進行下一步檢查，并更新該結點的后繼結點的距離D(j)，稱為“松弛”。算法1的復雜度為|Mbasis||T|，即其時間復雜度與基本標識空間的大小與變遷的數量分別呈線性關系。

定理3算法1輸出的控制序列σ為最優控制序列。

4 算例

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

圖1 智能制造系統Petri網模型

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

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

由表1中的結果可知：

表1 不同源標識下算法1與ILP-D方法的求解結果對比

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

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

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

5 結束語