不確定規劃中循環可達狀態信息的維護*

張瀟妮 文中華，2 彭擎宇

（1.湘潭大學信息工程學院 湘潭 411105）（2.湖南工程學院計算機與通信學院 湘潭 411104）

1 引言

智能規劃的基礎模型通過圖來建立［1］，近年來，對智能規劃的建模從確定圖模型擴展到不確定圖模型［2］。不確定規劃放寬以往經典規劃的一些基本假設，使之更接近實際情況的解答，現已應用到不少領域中。

在不確定規劃［3］中，有許多求解不確定規劃解［4～6］與一些復雜查詢的問題研究（如：蛋白質分子之間是否有交互作用，找尋網絡安全中的不確定攻擊圖的攻擊路徑［7～8］等）。在求解與查詢過程中，由于狀態之間的可達信息缺乏，會有大量重復的搜索，因此，有不少學者在可達性查詢［9］研究取得重要成果，如：基于樹形結構的可達性查詢［10～12］，利用矩陣的性質求解狀態之間的可達性［13～15］等，基于區間樹的求解算法只能盡大可能地獲取節點之間的可達關系，不能良好地求解整個系統中的各個節點之間的可達關系。在動態環境中，對狀態可達性的研究更多的是基于狀態之間的確定可達的操作，若是可達即為確定可達，否則為不可達，忽略了狀態之間的不確定可達，此外，對有向圖的要求大多是無環的。

在不確定規劃中，它考慮了每一個動作效果的存在性，也就考慮了狀態之間的可達性的不確定性。本文通過矩陣來建立問題模型，充分考慮狀態之間的動作執行的不確定性，準確表達狀態間的可達性（確定可達、不確定可達與不可達），提出了一種新的狀態可達關系的維護算法，對動態環境下的不確定性動作的存在變動性所影響的狀態之間的可達關系進行局部更新維護，適用于循環不確定系統中。該方法根據已有的信息可達矩陣和變更之后的不確定系統的鄰接矩陣的信息，重新進行轉發，對可達矩陣進行局部更新，取得新的狀態可達矩陣，避免重新求解。

2 相關定義

定義1：一個三元組可表示為規劃領域中的不確定的狀態轉換系統，即∑=＜S,A,γ＞其中：S是一個有限狀態集；A是一個有限動作集；γ:S×A→2s是狀態轉移函數。

定義2：設∑=＜S,A,γ＞是一個不確定狀態轉移系統，從狀態si開始，執行γ=(si,ax)之后，可能到達的狀態集合SL={s|s∈(sx,ax),s?{s1,s2,…,sn},1 ≤x≤n} 中的一個狀態，若si∈γ(sj,aj)(?i,i＜j)，則稱∑=＜S,A,γ＞為循環不確定狀態轉移系統s∈γ(sj,aj)(?i,i＜j)，否則為非循環不確定狀態轉移系統。

定義3：在一個不確定狀態轉移系統中，用函數d(s1,s2) 來表示s1和s2兩個狀態間的可達關系?？蛇_關系定義如下：

當狀態s1存在一條非循環路徑確定可達狀態s2時，則稱s1到s2確定可達，d(s1,s2)=1；

當狀態s1存在一條路徑L并且s2∈SL時，則稱s1到s2不確定可達，d(s1,s2)=T；

當狀態s1的任意一條路徑L都有s2?SL時，則稱s1到s2不可達，d(s1,s2)=0；

其中狀態自己到狀態自己為確定可達d(si,si)=1(1 ≤i≤n)，此類關系構成的矩陣即是可達矩陣。

定義4：通過一個唯一標識關聯區分不確定狀態轉移系統中任意不確定動作，記為Tx。狀態si執行Tx后可能到達的狀態集合Tx.mark={sm,sn,s0,…,sz}稱為不確定動作Tx的信念狀態。Tx.num是不確定動作Tx的信念狀態個數。

定義5：在一個不確定狀態轉移系統，用s-i→s-j表示將狀態si的可達信息s-i傳遞給狀態sj，d'(si,sj)表示經信息傳遞后獲取的狀態si到狀態sj的可達關系。其信息傳遞原則如下：

若d(si,sk)=1，d(si,sj)=1||T||0 ，則s-i→s-j：d'(si,sj)=1；

若d(si,sk)=0 ，d(si,sj)=1||T||0 ，則s-i→s-j：d'(si,sj)=d(si,sj)；

若d(si,sk)=Tn，d(si,sj)=Tm，則s-i→s-j：d'(si,sj)=Tn+Tm；

若d(si,sk)=Tn，d(si,sj)=Tn，si-j[Tn].value=si-j[Tn].value+card(si-k[Tn].mark-(si-j[Tn].mark∩sk-j[Tn].mark))，當si-j[Tn].value=Tn.value，則s-i→s-j：d'(si,sj)=1，否則為d′(si,sj)=Tn。

3 算法思想

3.1 狀態標記

狀態標記記錄著該狀態的最新狀態信息的更新是經哪個狀態傳遞的，更新原則如下。

1）不確定系統的鄰接矩陣中所有狀態的初始標簽tag均為0，若經由傳遞后可達信息不變，tag 仍記為0。

2）狀態間的可達關系經傳遞后形成確定可達關系或是由不可達成為不確定可達時，則更新為最新傳遞可達信息的狀態；

3）判斷可達關系是否不確定時，若根據原狀態si與sv的可達關系，狀態sv與狀態sx的可達關系，可得知狀態si到狀態sx的可達關系，此時記錄six.tag為最后一狀態編號加1。

當系統中狀態si與sv的執行動作因其它因素發生變動（包括邊的添加與刪除操作），則需重新判斷狀態si與狀態sv的可達關系，與原系統的可達矩陣中的對應信息對比，若是不一致，則說明該狀態的可達信息變更了，因此經該狀態sv作為中間狀態傳遞的可達信息也就會受到影響，需進行更新；否則，無需更新。在此過程中，也會有狀態不受該執行動作變動的影響，但仍需對其進行轉發，直至受其影響的狀態均進行比較、轉發操作或可達信息不再變更時，則該系統的狀態確定可達信息已求解出。

3.2 狀態可達關系更新

狀態之間可達關系更新步驟如下。

1）若狀態si與sv(i＜v)的可達關系變動，則將可達矩陣R中滿足s-v.tag＞=i的狀態sv的可達信息恢復到變更后的鄰接矩陣B的狀態sv對應可達信息，同時將狀態si（s-v.tag＜v）的可達信息再次傳遞到狀態sv。

2）若可達信息里原狀態可達矩陣D的狀態sv與當前狀態sv不一致，則將sv中s-v.tag＜v的信息重新進行傳遞，將需要更新的狀態（sx.tag＜v）的可達信息（需滿足s-x.tag＞=v）恢復為變更后的鄰接矩陣B的該狀態對應的可達信息，再進行傳遞，更新記錄可達信息變更的最后一狀態Colcmax，與其狀態可達標記。

3）狀態sv的可達信息傳遞之后，再將下一狀態sv+1且sv+1.tag＜v+1的可達信息進行傳遞，判斷哪些狀態的可達信息需要進行更新，重復2）操作。

4）依次進行轉發，直到最后更新的狀態的可達信息與原可達矩陣一致或者最后一個狀態的信息進行轉發，則結束與原狀態可達矩陣的比較。

5）最后，再對可達矩陣進行遍歷，找出所有元素值為0的點即為不確定可達矩陣。

證明：

可達狀態相關可達信息恢復到變更后的鄰接矩陣對應信息，經信息的傳遞，不會因為缺失其它狀態傳遞的信息而影響其最終的確定可達信息。因此，在信息傳遞之后，只需對找出所有不確定可達狀態對即可。

1）若狀態si與狀態sv之間是一型確定可達，可直接通過鄰接矩陣或經信息傳遞可得。

2）若狀態si與狀態sv之間是二型確定可達，有此兩種情形：當si-j[Tx].value=Tx.num，且狀態sv并非Tx的信念狀態時，根據中間狀態的可達信息，向確定可達狀態的傳遞信息原則，則必存在狀態sj(i≤j≤Colcmax) ，使得si-j[Tx].value=Tx.num，且si-j.tag＜=i，此si-j可達信息不會恢復變更后的鄰接矩陣對應可達信息；當sij的可達信息由原可達矩陣的確定可達恢復到不確定可達時，即狀態sv是Tx的信念狀態時，根據狀態向其確定可達的狀態進行傳遞信息原則，則必存在狀態sj(i≤j≤Colcmax)，且si-j.tag＜=i，si-j[Tx].value=Tx.num-1，sv=si-v[Tx].mark-si-j[Tx].mark，經信息的發送，使得si-v[Tx].value=Tx.num。

4 算法實現

設∑=(S,A,γ)為不確定狀態轉移系統，S為狀態集合，D為∑=(S,A,γ)的原狀態可達矩陣，B表示∑′=(S,A,γ′)狀態之間可達關系發生變更后的鄰接矩陣，R是∑′=(S,A,γ′)狀態可達信息更新后的狀態可達矩陣。算法如下：

根據原系統中的可達矩陣信息進行更新，第2行是對狀態之間的執行動作發生變更的不確定系統∑'的鄰接矩陣的更新；第3～5 行是對受其影響的狀態所擁有的可達信息與原系統中的可達矩陣進行對比并根據原則更新可達信息，否則直接進行下一狀態的傳遞，且當j=Colcmax時，結束更新；第6 行FINDCERTAIN（∑，R）函數是根據確定可達的狀態標簽快速找出變動后不確定系統∑',γ')其影響的狀態，并需將其狀態可達信息進行傳遞，取得受其影響的其它狀態對之間的可達信息；第7 行是對不確定系統∑',γ')中狀態之間的不確定可達關系進行修正。

函數FINDCERTAIN（∑，R）的具體實現過程如下：

第4行收集狀態si所擁有的可達信息。第5～7行尋找狀態si確定到達的狀態并將其可達信息傳遞給狀態sk，第8 行更新狀態變更的最大編號，確保受其影響的狀態都進行了判斷。其中函數DELIVER（sk，s-i）的實現過程如下：

5 算法實例及仿真實驗分析

如圖1，設∑=(S,A,γ) 為不確定狀態轉移系統。將通過文中描述的信息傳遞優化算法對此轉移系統進行維護。

圖1 原不確定狀態轉移系統

參考文獻［15］的算法可得該不確定系統的狀態可達矩陣如下：

若因為一些原因使其不確定系統的狀態s1與s2由確定可達變成不確定可達T3，與其它不確定動作進行區分，此時的不確定狀態轉移系統如圖2所示。

圖2 可達關系改變后的不確定系統

其鄰接矩陣變更為

因狀態s1到狀態s2與s3的可達信息都發生了變動，所以需將原可達矩陣D中可達狀態s2與s3中分別滿足s-2.tag＞=1 與s-3.tag＞=1 的可達信息恢復到變更后的鄰接矩陣B的狀態s2與s3的對應可達信息，此時Colcmax=3，可得：

重新將狀態s1的可達信息進行信息傳遞，根據R[1][j].tag＜1 且R[1][j]=1 的條件，可知狀態s1無法進行轉發。

但R[i][2]≠D[i][2]且Colcmax=3，則狀態s2需重新進行信息傳遞，根據R[2][j]=1 且R[2][j].tag＜2 條件，可知R[2][3]=1，將可達矩陣R中狀態s2的可達信息傳遞給狀態s4，先將可達狀態s4的滿足S-4.tag＞=2 的可達信息恢復到變更后的鄰接矩陣B的狀態s4的對應可達信息，再將R[i][2].tag＜2 的狀態可達信息進行轉發，根據傳遞規則，得：

R[2][j]=1 再由狀態s3進行信息傳遞，根據R[3][j]=1 且R[i][3].tag＜3 條件，可知R[3][1]=1 和R[3][4]=1，因此可達矩陣R中狀態s3將自己的可達信息傳遞給確定可達的狀態s1和狀態s4，此時Colcmax=4 根據信息傳遞規則可得：

R[i][4]的可達信息D[i][4]的可達信息相等，且Colcmax=4，因此不需再更新。

這樣已找出了變更后的不確定系統中所有確定可達關系，最后對更新后的可達矩陣R中元素值為0 的狀態可達關系進行判斷，最終得到的可達矩陣為

仿真實驗對比如下。

以下為采用本文改進的信息傳遞方法維護狀態可達關系與采用信息傳遞法、矩陣相乘法重新進行更新系統的狀態可達關系的實驗結果比較，三個算法的輸入數據均相同，運算時間如表1所示。

表1 運行時間對比

當狀態數較少時，系統中的動作也會比較少，狀態之間的可達路徑會屈指可數。當系統中的單個動作執行發生變動時，可能會牽引到整個系統的狀態之間的可達關系的變動。因此，此時系統中可達關系的局部維護與重新求解系統中可達關系的運行的時間相差不大。

當系統中狀態數逐漸增加時，其系統之中的動作也隨之增加。由于狀態之間的可達關系可以通過其它動作的執行與其它狀態間接取得聯系，從而一個執行動作的變動一般也不會影響整個系統中的狀態可達關系。因此，該動作的變動影響的大多數是系統中的局部狀態之間的可達關系，從而它的求解運算量會比重新求解系統中的可達關系小很多，從而提高效率，且比文獻［15］所運行的時間要少。

6 結語

本文從不確定系統中的信息傳遞方法切入，為加強算法的適用性，深入挖掘各個狀態維度的可達信息，快速求解系統的可達關系，維護不確定系統的相對穩定性。今后的進一步工作有：

1）完善系統傳遞方法，進一步提高求解效率。

2）將傳遞法的思想應用到多Agent 系統，或求解不確定規劃的規劃解中。