龍 鳳,文中華,唐 杰,王進(jìn)宗

(湘潭大學(xué)信息工程學(xué)院,湖南湘潭411105)

不確定規(guī)劃中可達(dá)關(guān)系的快速求解算法

龍 鳳,文中華,唐 杰,王進(jìn)宗

(湘潭大學(xué)信息工程學(xué)院,湖南湘潭411105)

在不確定規(guī)劃領(lǐng)域中,通常需要在同一個不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中解決多個規(guī)劃問題,如果能得到不確定規(guī)劃中狀態(tài)之間的可達(dá)關(guān)系即可方便求解該規(guī)劃問題,然而現(xiàn)有矩陣乘法求解可達(dá)關(guān)系時存在算法復(fù)雜度高的問題。為此,設(shè)計一種快速求解不確定規(guī)劃中狀態(tài)之間可達(dá)關(guān)系的算法,將確定動作和不確定動作區(qū)分處理,先求解所有確定動作的可達(dá)關(guān)系,再采用鏈表和隊列求解不確定動作的可達(dá)關(guān)系。實驗結(jié)果表明,與矩陣乘法相比,該算法能得到更全面的可達(dá)關(guān)系,且求解效率更高。

不確定規(guī)劃;可達(dá)關(guān)系;智能規(guī)劃;模型檢測;不確定性;不確定狀態(tài)轉(zhuǎn)移系統(tǒng)

1 概述

在現(xiàn)實世界中,存在許多不確定性問題。相對于確定規(guī)劃而言,不確定規(guī)劃[1-2]能夠更好地解決這些問題。這是近年來智能規(guī)劃的一個熱點研究領(lǐng)域。模型檢測是智能規(guī)劃中處理不確定規(guī)劃問題的一個重要算法?；谀Ｐ蜋z測[3-4]的不確定規(guī)劃也成為研究熱點,并取得了一些重要的成果,如:求解強、弱及強循環(huán)規(guī)劃解[5-6]的提出;對不確定狀態(tài)轉(zhuǎn)移系統(tǒng)進(jìn)行分層[7],刪除部分無用狀態(tài)序偶對,減小問題規(guī)模;不確定規(guī)劃中狀態(tài)之間的可達(dá)關(guān)系研究[8-9];基于模型檢測的不確定規(guī)劃中的狀態(tài)可達(dá)性研究[10];循環(huán)或非循環(huán)可達(dá)關(guān)系[11-12]的求解;正向搜索規(guī)劃解[13];觀察信息約簡[14-15]等。

在一個不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中,求解規(guī)劃問題時需要反復(fù)搜索動作來尋找目標(biāo)狀態(tài)。由于該搜索過程是沒有方向的,如果能夠得到不確定規(guī)劃中狀態(tài)之間的可達(dá)關(guān)系,則可以更加快速地求解規(guī)劃問題,減少冗余計算,建立系統(tǒng)引導(dǎo)信息。在文獻(xiàn)[8]中,給出了求解不確定規(guī)劃中的狀態(tài)之間的可達(dá)關(guān)系的算法,該算法將不確定狀態(tài)轉(zhuǎn)移系統(tǒng)轉(zhuǎn)換為鄰接矩陣,通過鄰接矩陣的加和乘運算獲得系統(tǒng)的可達(dá)矩陣,利用可達(dá)矩陣得到可達(dá)關(guān)系。但是,該算法在求解過程中具有一定的局限性,不能保證高效地得到可達(dá)關(guān)系。所以,本文提出一種快速求解不確定規(guī)劃中狀態(tài)間可達(dá)關(guān)系的算法,該算法對不確定狀態(tài)系統(tǒng)中的一些特殊的不確定動作進(jìn)行了處理,從而使得該算法可以更加高效、全面地得到不確定狀態(tài)系統(tǒng)的可達(dá)關(guān)系。

2 相關(guān)定義

定義1一個規(guī)劃領(lǐng)域是一個不確定的狀態(tài)轉(zhuǎn)移系統(tǒng)Σ=(S,A,γ),其中:

(1)S是一個有限狀態(tài)集;

(2)A是一個有限動作集;

(3)γ:S(A→2S是狀態(tài)轉(zhuǎn)移函數(shù)。

其中,利用γ刻畫不確定性:在s下執(zhí)行動作a可能得到的結(jié)果狀態(tài)集合就是γ(s,a)。若γ(s,a)非空,則稱動作a在狀態(tài)s下是可執(zhí)行的。在狀態(tài)s下可執(zhí)行動作的集合記為A(s)={a:?s∈γ(s,a)},并稱(s,a)為狀態(tài)動作序偶。

定義2一個規(guī)劃問題是由3個變量組成的三元組P=(Σ,I,G),其中:

(1)Σ=(S,A,γ)是不確定狀態(tài)轉(zhuǎn)移系統(tǒng);

(2)I?S是初始狀態(tài)集合;

(3)G?S是目標(biāo)狀態(tài)集合。

定義3在一個不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中,從狀態(tài)si開始,執(zhí)行 γ(si+1,ai+1),γ(si+2,ai+2),…,γ(sn,an)后,可能存在一條路徑到達(dá)狀態(tài)sx,那么,稱si到sx為不確定可達(dá)。對于任意sx都必有sx∈γ(sj,aj) (1＜x＜n,0＜j＜i)。

定義4在一個不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中,從狀態(tài)si開始,執(zhí)行 γ(si+1,ai+1),γ(si+2,ai+2),…,γ(sn,an)后,不存在任何路徑能夠到達(dá)狀態(tài)sx,那么,稱si到sx為確定不可達(dá)。其中,對于任意sx都有sx∈γ(sj,aj)(1＜x＜n,0＜j＜i)。

定義5在一個不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中,從狀態(tài)si開始,執(zhí)行 γ(si+1,ai+1),γ(si+2,ai+2),…,γ(sn,an)后,任意一條路徑都能到達(dá)狀態(tài)sx,那么,稱si到sx為確定可達(dá)。其中,對于任意sx都有sx∈γ(sj,aj)(1＜x＜n,0＜j＜i)。

定義6在不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中,2個狀態(tài)之間的可達(dá)關(guān)系用函數(shù)G(si,sj)來表示,函數(shù)G(si,sj)定義如下:

(1)G(si,sj)=0:si到sj為確定不可達(dá);

(2)G(si,sj)=1:si到sj為確定可達(dá);

(3)G(si,sj)=2:si到sj為不確定可達(dá)。

3 可達(dá)關(guān)系的求解算法

3.1 算法原理

文獻(xiàn)[8]利用矩陣乘的算法來求解可達(dá)關(guān)系。該算法先將不確定狀態(tài)轉(zhuǎn)移系統(tǒng)轉(zhuǎn)換為鄰接矩陣,然后通過鄰接矩陣的加和乘運算獲得可達(dá)矩陣,時間復(fù)雜度比較高。

本文提出的可達(dá)關(guān)系求解算法是將不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中確定動作和不確定動作進(jìn)行區(qū)別處理。這樣可以避免一些重復(fù)計算,從而提高求解效率。算法主要分為兩部分:(1)處理確定動作,確定動作的起始狀態(tài)到終止?fàn)顟B(tài)是確定可達(dá)的,只需進(jìn)行簡單處理。(2)處理不確定動作,首先處理確定可達(dá)的情況,若狀態(tài)s是不確定動作a的起始狀態(tài),且不確定動作a的所有終止?fàn)顟B(tài)都能確定可達(dá)狀態(tài)s′,則狀態(tài)s是確定可達(dá)狀態(tài)s′,然后處理不確定到達(dá)的情況,顯然,去除某些不確定動作的起始狀態(tài)到部分終止?fàn)顟B(tài)確定可達(dá)以外,余下的不確定動作的起始狀態(tài)到終止?fàn)顟B(tài)集都是不確定可達(dá)。同時,算法保證了確定可達(dá)具有傳遞性,即狀態(tài)a確定到達(dá)狀態(tài)b,b確定可達(dá)狀態(tài)c,那么狀態(tài)a必定確定可達(dá)狀態(tài)c。

3.2 算法分析

本文算法主要分為兩部分:(1)處理確定動作,求解確定動作的可達(dá)關(guān)系;(2)處理不確定動作,采用鏈表和隊列求解不確定動作的可達(dá)關(guān)系。設(shè)Σ=(S,A,γ)是一個不確定的狀態(tài)轉(zhuǎn)移系統(tǒng),其中有n個狀態(tài)。

處理確定動作的算法中動作起始狀態(tài)為u,終止?fàn)顟B(tài)個數(shù)為num,終止?fàn)顟B(tài)為v。數(shù)組graph[i][j]表示狀態(tài)i和狀態(tài)j的可達(dá)關(guān)系,即graph[i][j]為0代表不可達(dá),graph[i][j]為1代表確定可達(dá),graph[i][j]為2代表不確定可達(dá)。

處理確定動作的算法具體如下:

狀態(tài)到狀態(tài)本身是確定可達(dá)的,所以,第2行、第3行表示狀態(tài)到自己本身是確定可達(dá)的;第5行～第7行表示確定動作的起始狀態(tài)到終止?fàn)顟B(tài)是確定可達(dá);第8行中mulm代表第幾個不確定動作,即不確定動作的ID號;第 10行的函數(shù)solveReach求任意2個點是否確定可達(dá),即執(zhí)行這個函數(shù)后,可以保證graph具有傳遞性。

函數(shù)solveReach處理的具體流程如下:

函數(shù)solveReach的代碼中數(shù)組graph[i][j]表示狀態(tài)i和狀態(tài)j的可達(dá)關(guān)系,即graph[i][j]為0代表不可達(dá),graph[i][j]為1代表確定可達(dá),graph[i][j]為2代表不確定可達(dá)。第4行～第8行是確保確定可達(dá)具有傳遞性,即graph[i][k]= =1且graph[k][j]==1,那么就有g(shù)raph[i][j]==1。

處理不確定動作時,分為確定可達(dá)和不確定可達(dá)兩部分進(jìn)行處理。其中,mulAcation[i][0]代表第i個不確定動作的初始狀態(tài)數(shù)目(為1)和終止?fàn)顟B(tài)數(shù)目之和,這里假設(shè)為num+1,mulAcation[i][1]代表第i個不確定動作的初始狀態(tài)的編號,mulAcation[i][2,3,…,num+1]代表第i個不確定動作的所有終止?fàn)顟B(tài)的編號。隊列actionQue用來保存所有不確定動作的ID號。

處理不確定動作中確定可達(dá)的算法具體如下:

在處理確定可達(dá)的算法時,為了保證處理時可以進(jìn)行逆向查找,將不確定動作的ID號mulm保存在saHead[v]鏈表中,這樣可以通過這個鏈表找到mulm。第2行～第10行是求狀態(tài)u是否能夠確定到達(dá)狀態(tài)i,判斷算法如下:由于狀態(tài)u是不確定動作act的起始狀態(tài),因此如果這個不確定動作act的所有終止?fàn)顟B(tài)都確定可達(dá)狀態(tài)i,那說明狀態(tài)u也是確定可達(dá)狀態(tài)i;第12行的for循環(huán)更新每一個狀態(tài);第19行的for循環(huán)是處理的一種不確定動作嵌套的特殊情況,即不確定動作act的所有終止?fàn)顟B(tài)中的任意一個狀態(tài)是另外一個不確定動作的起始狀態(tài),如果這個不確定動作的ID號ra還沒有加入隊列,則將它加入到隊列中。至此,處理確定可達(dá)部分的算法結(jié)束。

處理不確定動作中不確定可達(dá)的算法具體如下:

在處理不確定可達(dá)的算法中,第2行的for循環(huán)是將所有保存在mulAction中的可達(dá)關(guān)系全部放入graph數(shù)組中,如果graph[u][v]已經(jīng)為1,則不需要更新,否則將graph[u][v]置為2。至此處理不確定動作的過程結(jié)束。

在執(zhí)行完處理確定動作和不確定動作的算法后,再執(zhí)行一遍solveReach函數(shù),就可以得到所有狀態(tài)對之間的可達(dá)關(guān)系。

對算法時間復(fù)雜度進(jìn)行分析,設(shè)規(guī)劃領(lǐng)域中有n個狀態(tài),該算法的時間主要用于2個部分,即處理確定動作的算法和處理不確定動作的算法。這兩部分中都用到了solveReach函數(shù),對solveReach函數(shù)的時間復(fù)雜度進(jìn)行分析:這部分算法的時間主要用于3個循環(huán),而且這3個循環(huán)都要遍歷規(guī)劃領(lǐng)域中的所有狀態(tài),時間復(fù)雜度為O(n3)。對于處理確定動作的算法進(jìn)行分析可知,這部分算法需要遍歷規(guī)劃領(lǐng)域的所有狀態(tài),最后需執(zhí)行solveReach函數(shù)來確保確定可達(dá)的傳遞性,時間復(fù)雜度為O(n+n3);在處理不確定動作的算法中,假設(shè)進(jìn)入隊列的次數(shù)為q,且需要遍歷規(guī)劃領(lǐng)域中所有的狀態(tài),最后還需執(zhí)行一遍solveReach函數(shù),時間復(fù)雜度為O(qn+n3)。根據(jù)對這兩部分算法的時間復(fù)雜度分析可知,快速求解可達(dá)關(guān)系的算法時間復(fù)雜度為O(qn+n3)。

4 算法實例分析

設(shè)Σ=(S,A,γ)是一個不確定狀態(tài)轉(zhuǎn)移系統(tǒng),如圖1所示。

圖1 不確定狀態(tài)轉(zhuǎn)移系統(tǒng)

根據(jù)本文算法可知,狀態(tài)到狀態(tài)本身是確定可達(dá)的,即graph[i][i]=1。算法分兩部分求可達(dá)關(guān)系:(1)處理確定動作,根據(jù)算法中對確定動作的處理可得graph[s1][s2]=1,即狀態(tài)s1確定可達(dá)狀態(tài)s2。同理,graph[s4][s7]=1,graph[s5][s7]=1,graph[s6][s7]=1,graph[s3][s6]=1,graph[s3][s1]=1。由于算法保證確定可達(dá)具有傳遞性,且有g(shù)raph[s6][s7]=1,graph[s3][s6]=1,因此有g(shù)raph[s3][s7]=1。(2)處理不確定動作,如圖 1所示,該不確定狀態(tài)轉(zhuǎn)移系統(tǒng)有 3個不確定動作T1,T2,T3。對于T1有g(shù)raph[s4][s7]=1,graph[s5][s7]=1,即不確定動作T1的終止?fàn)顟B(tài)集確定可達(dá)狀態(tài)s7。所以根據(jù)算法可得,該不確定動作的起始狀態(tài)s2也確定可達(dá)狀態(tài)s7,即graph[s2][s7]=1,因此更新狀態(tài)s2和狀態(tài)s7之間的可達(dá)關(guān)系。同時,由于graph[s1][s2]=1,根據(jù)傳遞性有g(shù)raph[s1][s7]=1,因此更新狀態(tài)s1和狀態(tài)s7之間的可達(dá)關(guān)系。同理,對于T2,T3可以得到graph[s3][s7]=1,更新這個可達(dá)關(guān)系。

至此已完成確定可達(dá)情況的處理,接下來處理不確定可達(dá)的情況。根據(jù)處理不確定動作的算法可知,對于T2有g(shù)raph[s3][s1]=2,由于上文已得到狀態(tài)s3和狀態(tài)s1之間為確定可達(dá),因此不需要更新這個可達(dá)關(guān)系,仍為graph[s3][s1]=1;graph[s3][s5]=2,更新這個可達(dá)關(guān)系。同理,對于T1,T3可以得到graph[s2][s4]=2,graph[s2][s5]=2,graph[s3][s5]=2,更新這些可達(dá)關(guān)系。

在執(zhí)行solveReach函數(shù)后得到graph[s1][s4]=2,graph[s1][s5]=2,graph[s3][s4]=2。

所以,該不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的確定可達(dá)關(guān)系和不確定可達(dá)關(guān)系如下:

5 實驗結(jié)果及分析

實驗環(huán)境均為Windows7+Core(TM)i3-3220

3.3 GHz+4.0 GB內(nèi)存 +VC6。實驗數(shù)據(jù)隨機生成。

表1為文獻(xiàn)[8]中求狀態(tài)可達(dá)關(guān)系的算法與本文提出快速求解狀態(tài)可達(dá)關(guān)系算法的實驗結(jié)果比較。

表1 執(zhí)行時間對比 s

由表1可知,當(dāng)不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中的狀態(tài)數(shù)目較少時,文獻(xiàn)[8]中的矩陣乘算法和本文算法的運行時間都很短,此時本文算法的優(yōu)勢不明顯。當(dāng)不確定狀態(tài)系統(tǒng)中的狀態(tài)數(shù)目較多時,本文算法的優(yōu)勢便突顯出來,證明它在求解可達(dá)關(guān)系時具有更高的效率。隨著狀態(tài)數(shù)的增長,由于時間復(fù)雜度不同,矩陣乘的運行時間增長速度較快,而本文算法的運行時間則增長平緩。

從實驗結(jié)果及分析可以看出,采用本文算法可以更加快速地得到不確定系統(tǒng)狀態(tài)之間的可達(dá)關(guān)系。

6 結(jié)束語

本文提出一種快速求解狀態(tài)可達(dá)關(guān)系的算法。通過實例說明,本文算法可以更加高效、全面地得到不確定狀態(tài)系統(tǒng)的可達(dá)關(guān)系。在求解狀態(tài)可達(dá)關(guān)系的基礎(chǔ)上,下一步將對以下工作進(jìn)行研究:(1)基于可達(dá)關(guān)系求多Agent規(guī)劃解;(2)對狀態(tài)轉(zhuǎn)移系統(tǒng)中的動作增加權(quán)值,求確定可達(dá)的狀態(tài)最短路徑。

[1] Huang Wei,Wen Zhonghua,Jiang Yunfei,etal. Comparison Between Two Languages Used to Express Planning Goals:CTL and EAGLE[C]//Proceedings of PRICAI’06.[S.l.]:Springer-Verlag,2006:180-189.

[2] Roveri C M.Conformant Planning via Model Checking and Heuristic Search[J].Artificial Intelligence,2004, 159(1/2):127-206.

[3] Bertoli P,Cimatti A,Roveri M,et al.Strong Planning Under Partial Observability[J].Artificial Intelligence, 2006,170(1):337-384.

[4] Roveri C M,Traverso P.Automatic OBDD-based Generation ofUniversalPlansin Non-deterministic Domains[C]//Proceedings of AAAI’98.Madison, USA:AAAI Press,1998:26-30.

[5] Cimatti A,Pistore M,Rovveri M,et al.Weak,Strong,and Strong Cyclic Planning via Symbolic Model Checking[J]. Artificial Intelligence,2003,147(1/2):35-64.

[6] 陳建林.強規(guī)劃解、弱規(guī)劃解的研究[D].湘潭:湘潭大學(xué),2011.

[7] 文中華,黃 巍,劉任任,等.模型檢測規(guī)劃中的狀態(tài)分層算法[J].軟件學(xué)報,2009,20(4):858-869.

[8] 文中華,黃 巍,劉任任,等.模型檢測規(guī)劃中的狀態(tài)之間的可達(dá)關(guān)系研究[J].計算機學(xué)報,2012,35(8): 1634-1643.

[9] 黃麗芳.基于不確定系統(tǒng)的狀態(tài)可達(dá)關(guān)系求規(guī)劃解的算法研究[D].湘潭:湘潭大學(xué),2013.

[10] 胡雨隆.基于模型檢測的不確定規(guī)劃中的狀態(tài)可達(dá)性研究[D].湘潭:湘潭大學(xué),2012.

[11] 黃麗芳,文中華,胡雨隆,等.不確定規(guī)劃中狀態(tài)循環(huán)可達(dá)關(guān)系的求解算法[J].計算機應(yīng)用研究,2013, 30(9):2689-2693.

[12] 胡雨隆,文中華,常 青,等.不確定規(guī)劃中狀態(tài)非循環(huán)可達(dá)關(guān)系的求解算法[J].計算機仿真,2012, 29(5):114-117.

[13] 陳建林,文中華,朱 江,等.正向搜索算法求強規(guī)劃解[J].計算機工程與應(yīng)用,2011,47(6):52-54.

[14] Huang Wei,Wen Zhonghua,Jiang Yunfei,etal. Structured Plans and Observation Reduction for Plans with Contexts[C]//Proceedings of IJCAI’09. Pasadena,USA:AAAI Press,2009:1721-1728.

[15] Huang Wei,Wen Zhonghua,Jiang Yunfei,et al.Observation Reduction for Strong Plans[C]//Proceedings of IJCAI’07.Hyderabad,India:AAAI Press,2007:1930-1935.

編輯 陸燕菲

Fast Solving Algorithm of Reachability Relation in Uncertain Planning

LONG Feng,WEN Zhonghua,TANG Jie,WANG Jinzong
(College of Information Engineering,Xiangtan University,Xiangtan 411105,China)

In uncertain planning field,it is frequent to solve many planning problems over a nondeterministic statetransition system in uncertain planning.So getting the state reachability for the nondeterministic state-transition system can make solving planning problems easier.However,the existing solution matrix multiplication of relations exist the problem of high algorithm complexity.Therefore,this paper presents a fast solving algorithm of reachability relation between the states in uncertain planning.The algorithm determines the certainly action and uncertainty actions separately.It determines the relationships between the certainty action,then solves relations between uncertain actions with lists and queues. Experimental result shows that the algorithm not only can get a more comprehensive relationship,but also has higher efficiency than the matrix multiplication algorithm.

uncertain planning;reachability relation;intelligent planning;model checking;uncertainty;uncertain statetransition system

1000-3428(2015)01-0196-04

A

TP18

10.3969/j.issn.1000-3428.2015.01.036

國家自然科學(xué)基金資助項目(61070232,61272295)。

龍 鳳(1989-),女,碩士研究生,主研方向:智能規(guī)劃;文中華,教授、博士生導(dǎo)師;唐 杰、王進(jìn)宗,碩士研究生。

2013-12-30

2014-03-26 E-mail:416807936@qq.com

中文引用格式:龍 鳳,文中華,唐 杰,等.不確定規(guī)劃中可達(dá)關(guān)系的快速求解算法[J].計算機工程,2015,41(1): 196-199.

英文引用格式:Long Feng,Wen Zhonghua,Tang Jie,et al.Fast Solving Algorithm of Reachability Relation in Uncertain Planning[J].Computer Engineering,2015,41(1):196-199.