標注Petri 網中的最小初始標識估計

徐淑琳，周廣瑞，岳 昊，2

（1.青島大學自動化學院，山東青島 266071；2.青島大學復雜性科學研究所，山東青島 266071）

0 概述

Petri 網是一種用于離散事件系統建模、分析和控制的工具，具有圖形和數學的雙重表現形式且可有效描述系統行為。近年來，Petri 網被應用于交通系統［1］和柔性裝配制造系統［2］等多種實際系統中，且在系統安全及可靠性分析［3-4］、業務流程分析［5-6］、交互控制［7］以及Web 服務分析和替代［8］中也有廣泛應用。隨著實際系統規模的增大，標識估計對離散事件系統的診斷［9］和控制器設計［10-11］等具有重要的作用。

關于Petri 網中標識估計問題的研究已經取得顯著成果［12-13］。文獻［12］基于對標注序列的觀察，討論了初始標識已知的Petri 網中的標識估計問題，并指出標識集可用一組具有固定結構的線性不等式來描述。文獻［13］也研究了標識估計問題，并證明所有可能的標識數目是關于k的函數。最小初始標識的估計成為當今研究的熱點之一，例如文獻［14］討論了含有可觀測變遷的標注Petri 網中的最小初始標識估計問題，并提出一種最小初始標識估計算法。文獻［15］將文獻［14］中的結果擴展到含有不可觀測變遷的標注Petri 網中。文獻［16］提出一種用于估計由標注Petri 網中的最小代價計劃序列的算法。文獻［17］通過使用基可達圖尋找標注Petri 網中最小代價變遷序列。

針對不可觀測變遷的存在給求解標注Petri 網建模制造系統中的最小資源帶來困難的問題，本文放寬對不可觀測變遷發生個數的限制，且允許可觀測在變遷前至多有2 個不可觀測變遷發生。為了更好地實現估計最小初始標識的目標，本文以標注Petri 網為工具，進一步討論了文獻［14-15］提出的最小初始標識估計問題，并提出一種基于動態規劃的新算法，以估計最小的初始標識。

1 基本概念

本節給出下文將會用到的Petri 網和標注Petri網的相關定義，更多詳細介紹可參閱文獻［14］。

定義1［18-19］將一個Petri 網定義為一個四元組N=（P，T，F，W），其中：1）P=｛p1，p2，…，pn｝是一個有限的庫所集，庫所使用空心圓圈表示；2）T=｛t1，t2，…，tm｝是一個有限的變遷集，變遷使用實心豎條表示；3）P∪T≠?，P∩T=?；4）F?（P×T）∪（T×P）為流關系集合；5）W：F→?=｛0，1，2，…｝稱為權函數。

如果pi和tj之間沒有弧，則W（pi，tj）=W（tj，pi）=0。如果N沒有直接的循環存在，則稱N是無環的。

定義2［17］在一個Petri 網N=（P，T，F，W）中，若P=｛p1，p2，…，pn｝，T=｛t1，t2，…，tm｝，則N的結構可用關聯矩陣A表示，其中：1）A=A+?A?；2）A?為N的輸入關聯矩陣，A?=［］是一個n行m列的整數矩陣，=W（pi，t）j（1≤i≤n，1≤j≤m）；3）A+為N的輸出關聯矩陣，A+=［］是一個n行m列的整數矩陣，=W（tj，pi）；4）若pi和tj之間沒有弧，則==0；5）A（：，t）（或者A?（：，t），A+（：，t））是A（或者A?，A+）中對應于變遷t的列，且A（：，t），A?（：，t），A+（：，t）均為列向量。

定義3（N，Μ0）是一個初始化的網系統，Μ0是系統的初始標識。映射Μ：P→? 稱為Petri 網N的一個標識，標識Μ的每個分量都對應相應庫所中托肯的數目，托肯用實心圓點表示。對于p∈P，庫所p中的托肯數記為Μ（p），標識Μ的所有庫所中的托肯總數記為。

定義4［14］Petri 網N=（P，T，F，W）具有以下變遷發生規則：

1）對于變遷t∈T，如果t的每個輸入庫所pinput都有至少A?（pinput，t）個托肯，則變遷t在標識Μ下具有發生權，并定義為Μ［t〉。

2）如果變遷t發生，則t的每個輸入庫所pinput都被移除A?（pinput，t）個托肯，并且t的每個輸出庫所poutput都增加A+（poutput，t）個托肯，變遷t在標識Μ下發生會使得系統到達一個新標識Μ?=Μ+A（：，t），并記為Μ［t〉Μ?。

定義5［20］Petri 網N=（P，T，F，W）的可達性可定義為：若存在t∈T使得Μ［t〉Μ?，則稱標識Μ?從Μ直接可達；若存在一個變遷序列σ=t1t2…tk，其中ti∈T，使得Μ［t1〉Μ1［t2〉…Μk?1［tk〉Μk=Μ?，則稱標識Μ?從Μ可達。按此規定，從Μ可達的一切標識集合記為R（Μ）。

定義6給定一個變遷序列σ∈T*，其中T*表示一系列有限長度的變遷序列集合。令π：T*→?n為一個映射，y=π（σ）是一個m維非負向量，稱為σ的發生數向量。y（i）表示變遷序列σ中變遷t出現的次數。對于零長度的空串?∈T*，其發生數向量為零向量，即π（?）=0m。

定義7［17］將一個標注Petri 網定義為一個四元組（N，Μ0，L∪｛?｝，l），其中：1）N=（P，T，A，W）是一個Petri 網，Μ0是Petri 網N的初始標識；2）L是非空標注的集合，標注用一個字母表示；3）l：T→L∪｛?｝是標注函數，其中每個變遷都對應一個字母或者一個空字符串∫。

由于本文考慮的是含有不可觀測變遷的標注Petri網，因此可以將變遷集合T劃分為所有不可觀測變遷的集合Tu和所有可觀測變遷的集合To這2 個集合，且滿足Tu∪To=T和Tu∩To=?。對于一個標注l∈L，用Tl=｛t∈T|l（t）=l｝表示與非空標注l對應的所有可觀測變遷的集合，Tu=｛t∈T|l（t）=?｝表示與空標注?對應的所有不可觀測變遷的集合，用|Tl|（或者|Tu|）表示對應于非空標注l（或者空標注?）的變遷數目，且滿足1≤|Tl|≤m，1≤|Tu|≤m。對于一個變遷序列σ=t1t2…tk，其對應的標注序列可定義為w=（σ）≡l（t1）l（t2）…l（tk）。

2 最小初始標識的求取

2.1 問題描述

文獻［14］考慮的是僅含有可觀測變遷的標注Petri 網，而本文的研究對象是含有不可觀測變遷的標注Petri 網，在觀察到一個標注后，所有可能的變遷發生序列的數目會呈指數級增長。因此，為了降低計算復雜度，本文進行以下假設：

假設1不可觀測變遷組成的子網是無環的。

根據假設1，在標注Petri 網N中，不可觀測變遷組成的子網沒有直接的循環存在。

假設2對于每個標注的觀察，可觀測變遷之前至多允許2 個不可觀測變遷發生。

根據假設2，在觀察到標注lj后，所有可能的變遷發生序列形如σu t，其中t∈To，l（t）=lj，σu∈T*u，σu可能為一個空串?。

考慮一個含有不可觀測變遷且初始標識未知的標注Petri 網N=（N，Μ0，L∪｛?｝，l）以及一個標注序列w=l1l2…lk，其中lj∈L，j∈｛1，2，…，k｝，本文的目標為尋找最小初始標識估計，即具有最小托肯總數的標識估計。

定義8［15］考慮一個標注Petri 網N=（N，Μ0，L∪｛?｝，l），給定一個標注序列w，將初始標識估計集合、極小初始標識估計集合、最小初始標識估計集合分別定義為：

假設Μ和Μ?是2 個分量個數相同的標識向量，其中Μ=［Μ（p1），Μ（p2），…，Μ（pn）］T，Μ?=［Μ ?（p1），Μ ?（p2），…，Μ ?（pn）］T，如果對任意的i∈｛1，2，…，n｝滿足Μ（pi）≤Μ ?（pi），則有Μ≤Μ?成立。假設一個標識集合Z=｛Μ1，Μ2，…，Μn｝，若對任意的i，j∈｛1，2，3，…｝且i≠j，都不存在Μj使得Μj≤Μi成立，則Μi為標識集合Z中的極小標識。由于小于等于關系是一種偏序關系，因此極小標識并不是唯一的。

在文獻［15］中，式（4）給出了極小初始標識的計算方法：

圖1 節點演化示意圖Fig.1 Schematic diagram of nodes evolution

圖2所示為一個標注Petri網（N，Μ0，L∪｛?｝，l），P=｛p1，p2，p3｝，T=｛t1，t2，t3，t4｝，其中To=｛t1，t4｝，Tu=｛t2，t3｝，（lt1）=a，（lt4）=b，（lt2）=（lt3）=?。給定一個標注序列w=ab，對w進行觀察后，利用式（4）計算極小初始標識估計，得到節點演化示意圖如圖3 所示，節點信息如表1 所示。觀察到標注序列ab后，當變遷序列t1t2t3t4發生時，得到極小初始標識估計集合為（w）=｛［0000］T｝，最小初始標識估計集合為I（w）=｛［0000］T｝，I（w）對應的變遷序列集合為｛t1t2t3t4｝，I（w）對應的發生數向量集合為｛［1111］T｝。

圖2 標注Petri 網示意圖Fig.2 Schematic diagram of labeled Petri nets

圖3 Petri 網的節點演化示意圖Fig.3 Schematic diagram of node evolution of Petri nets

表1 圖3 中每個節點對應的信息Table 1 Corresponding information of each node in Fig.3

2.2 最小初始標識算法估計

算法1最小初始標識估計算法

2.3 復雜性分析

由文獻［14］可知，第j階段的發生數向量的數目為nj=O（jb），b是一個依賴于Petri 網結構的參數。給定一個含有n個庫所、m個變遷的標注Petri 網，其中可觀測變遷和不可觀測變遷的個數分別為mo和mu，且有m=mo+mu成立。在觀察到一個標注后，所有可能不同的不可觀測發生數向量的數目為：

綜合考慮可觀測變遷和不可觀測變遷，基于假設2，可知第j階段發生數向量的數目為nj=（r?j）b。在第j?1 階段，一個發生數向量至多能產生r?m0個不同的發生數向量，因此第j階段新產生的發生數向量的總數為r?m0?nj?1=O［r?m0?（r?j）b］。在Petri 網中僅含有可觀測變遷的情況下，第j階段極小初始標識的數目為qj=O（jn），根據假設2，發生序列長度的最大值為3j，因此qj=O（（3j）n）=O（jn）。針對每個發生數向量，需要進行nj次比較以確定其是否已經出現在節點Rj中，若已出現過，則需要qj次比較來確定極小的初始標識估計?；谝陨戏治?，算法1 的計算復雜度為：

式（6）可簡化為：

因此，算法1 的計算復雜度是關于k的多項式。

3 應用實例

本節通過一個實例來驗證算法1 的有效性，并將運行結果與現有算法得到的結果進行對比分析。圖4給出了一個2臺并行機器的標注Petri網模型N=（N，Μ0，L∪｛?｝，l），庫所集P=｛p1，p2，p3，p4｝，變遷集T=｛t1，t2，t3，t4，t5，t6｝，其中To=｛t1，t2，t5，t6｝，Tu=｛t3，t4｝，l（t1）=a，l（t2）=b，l（t5）=c，l（t6）=d，l（t3）=l（t4）=?。p1為存放工件的資源庫所，變遷t1和t2表示由機器人分別將工件裝載至1 號機器和2 號機器上，p2表示工件被1 號機器加工，t3表示機器人將一部分工件從1 號機器上卸載并裝載至2 號機器上，p3表示工件被2 號機器加工，t5表示機器人將剩余的工件從1 號機器上卸載，t4表示機器人將工件從2 號機器上卸載，p4表示將來自1 號機器和2 號機器的工件進行再加工，t6表示將工件卸載。給定一個標注序列w=ad，運行算法1 后得到節點演化示意過程如圖5 所示，節點信息和弧上的標記信息分別如表2和表3所示。如圖5 所示，當觀察到標注a時，所有可能的變遷序列集合為｛t1，t3t1，t4t1，t3t4t1，t4t3t1，t3t3t1，t4t4t1｝，應該存在7個節點，但變遷序列t3t4t1和t4t3t1對應的發生數向量均為［101100］T，兩者對應的極小初始標識估計分別為［1100］T和［1110］T，顯然［1100］T≤［1110］T，根據算法1，當出現相同的發生數向量時，僅保留極小初始標識估計，因此刪掉變遷序列t4t3t1對應的初始標識估計及當前標識。當標注序列w=ad全部被觀察到后，得到極小初始標識估計集合為（w）=｛［1000］T｝，最小初始標識估計集合為Ι（w）=｛［1000］T｝，與Ι（w）對應的變遷序列集合為｛t1t3t4t6｝，與Ι（w）對應的發生數向量集合為｛［101101］T｝。

圖4 標注Petri 網系統示意圖Fig.4 Schematic diagram of labeled Petri net system

文獻［15］中限定可觀測變遷發生之前至多允許一個不可觀測變遷發生，則最小初始標識估計集合為Ι?（w）=｛［1001］T｝，發生數向量集合為｛［100001］T，［101001］T｝，變遷序列為｛t1t6，t1t3t6｝。假設Μ∈Ι（w），Μ?∈Ι?（w），則||Μ||=1，||Μ?||=2，由此可知||Μ||＜||Μ?||，因此，應用本文方法得到的最小初始標識具有更小的托肯總數，即系統完成指定的任務序列所需的初始資源更少。

圖5 運行算法1 后的節點演化示意圖Fig.5 Schematic diagram of node evolution after running algorithm 1

表2 圖5 中每個節點對應的信息Table 2 Corresponding information of each node in Fig.5

表3 圖5 中每條弧上的標記信息Table 3 Marking information of each arc in Fig.5

4 結束語

針對制造系統中的最小資源問題，本文建立標注Petri 網模型，并提出一種用于估計最小初始標識的算法。該算法放寬了不可觀測變遷發生個數的限制，并規定可觀測變遷之前至多允許2 個不可觀測變遷發生，以有效避免最小初始標識估計的窮舉計算。實驗結果表明，在含有不可觀測變遷的標注Petri 網中，應用本文算法估計的最小初始標識較現有算法得到的結果更優。下一步將利用時延Petri 網結構對本文算法進行優化，使得初始標識估計的托肯總數更小。