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

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

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

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

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

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

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

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

1 概述

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

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

2 相關(guān)定義

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

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

(2)A是一個(gè)有限動(dòng)作集;

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

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

定義2一個(gè)規(guī)劃問(wèn)題是由3個(gè)變量組成的三元組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在一個(gè)不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中,從狀態(tài)si開(kāi)始,執(zhí)行 γ(si+1,ai+1),γ(si+2,ai+2),…,γ(sn,an)后,可能存在一條路徑到達(dá)狀態(tài)sx,那么,稱(chēng)si到sx為不確定可達(dá)。對(duì)于任意sx都必有sx∈γ(sj,aj) (1＜x＜n,0＜j＜i)。

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

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

定義6在不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中,2個(gè)狀態(tài)之間的可達(dá)關(guān)系用函數(shù)G(si,sj)來(lái)表示,函數(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]利用矩陣乘的算法來(lái)求解可達(dá)關(guān)系。該算法先將不確定狀態(tài)轉(zhuǎn)移系統(tǒng)轉(zhuǎn)換為鄰接矩陣,然后通過(guò)鄰接矩陣的加和乘運(yùn)算獲得可達(dá)矩陣,時(shí)間復(fù)雜度比較高。

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

3.2 算法分析

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

處理確定動(dòng)作的算法中動(dòng)作起始狀態(tài)為u,終止?fàn)顟B(tài)個(gè)數(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á)。

處理確定動(dòng)作的算法具體如下:

狀態(tài)到狀態(tài)本身是確定可達(dá)的,所以,第2行、第3行表示狀態(tài)到自己本身是確定可達(dá)的;第5行～第7行表示確定動(dòng)作的起始狀態(tài)到終止?fàn)顟B(tài)是確定可達(dá);第8行中mulm代表第幾個(gè)不確定動(dòng)作,即不確定動(dòng)作的ID號(hào);第 10行的函數(shù)solveReach求任意2個(gè)點(diǎn)是否確定可達(dá),即執(zhí)行這個(gè)函數(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òng)作時(shí),分為確定可達(dá)和不確定可達(dá)兩部分進(jìn)行處理。其中,mulAcation[i][0]代表第i個(gè)不確定動(dòng)作的初始狀態(tài)數(shù)目(為1)和終止?fàn)顟B(tài)數(shù)目之和,這里假設(shè)為num+1,mulAcation[i][1]代表第i個(gè)不確定動(dòng)作的初始狀態(tài)的編號(hào),mulAcation[i][2,3,…,num+1]代表第i個(gè)不確定動(dòng)作的所有終止?fàn)顟B(tài)的編號(hào)。隊(duì)列actionQue用來(lái)保存所有不確定動(dòng)作的ID號(hào)。

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

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

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

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

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

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

4 算法實(shí)例分析

設(shè)Σ=(S,A,γ)是一個(gè)不確定狀態(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)處理確定動(dòng)作,根據(jù)算法中對(duì)確定動(dòng)作的處理可得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)處理不確定動(dòng)作,如圖 1所示,該不確定狀態(tài)轉(zhuǎn)移系統(tǒng)有 3個(gè)不確定動(dòng)作T1,T2,T3。對(duì)于T1有g(shù)raph[s4][s7]=1,graph[s5][s7]=1,即不確定動(dòng)作T1的終止?fàn)顟B(tài)集確定可達(dá)狀態(tài)s7。所以根據(jù)算法可得,該不確定動(dòng)作的起始狀態(tài)s2也確定可達(dá)狀態(tài)s7,即graph[s2][s7]=1,因此更新?tīng)顟B(tài)s2和狀態(tài)s7之間的可達(dá)關(guān)系。同時(shí),由于graph[s1][s2]=1,根據(jù)傳遞性有g(shù)raph[s1][s7]=1,因此更新?tīng)顟B(tài)s1和狀態(tài)s7之間的可達(dá)關(guān)系。同理,對(duì)于T2,T3可以得到graph[s3][s7]=1,更新這個(gè)可達(dá)關(guān)系。

至此已完成確定可達(dá)情況的處理,接下來(lái)處理不確定可達(dá)的情況。根據(jù)處理不確定動(dòng)作的算法可知,對(duì)于T2有g(shù)raph[s3][s1]=2,由于上文已得到狀態(tài)s3和狀態(tài)s1之間為確定可達(dá),因此不需要更新這個(gè)可達(dá)關(guān)系,仍為graph[s3][s1]=1;graph[s3][s5]=2,更新這個(gè)可達(dá)關(guān)系。同理,對(duì)于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 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

本文提出一種快速求解狀態(tài)可達(dá)關(guān)系的算法。通過(guò)實(shí)例說(shuō)明,本文算法可以更加高效、全面地得到不確定狀態(tài)系統(tǒng)的可達(dá)關(guān)系。在求解狀態(tài)可達(dá)關(guān)系的基礎(chǔ)上,下一步將對(duì)以下工作進(jìn)行研究:(1)基于可達(dá)關(guān)系求多Agent規(guī)劃解;(2)對(duì)狀態(tài)轉(zhuǎn)移系統(tǒng)中的動(dò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] 陳建林.強(qiáng)規(guī)劃解、弱規(guī)劃解的研究[D].湘潭:湘潭大學(xué),2011.

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

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

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

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

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

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

[13] 陳建林,文中華,朱 江,等.正向搜索算法求強(qiáng)規(guī)劃解[J].計(jì)算機(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

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

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

2013-12-30

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

中文引用格式:龍 鳳,文中華,唐 杰,等.不確定規(guī)劃中可達(dá)關(guān)系的快速求解算法[J].計(jì)算機(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.