一種快速求強(qiáng)規(guī)劃解的算法

勞佳琪,文中華,2,伍小輝,唐 杰

(1.湘潭大學(xué)信息工程學(xué)院,湖南湘潭411105;2.湖南工程學(xué)院計(jì)算機(jī)與通信學(xué)院,湖南湘潭411104)

一種快速求強(qiáng)規(guī)劃解的算法

勞佳琪1,文中華1,2,伍小輝1,唐 杰1

(1.湘潭大學(xué)信息工程學(xué)院,湖南湘潭411105;2.湖南工程學(xué)院計(jì)算機(jī)與通信學(xué)院,湖南湘潭411104)

為提高求解效率,設(shè)計(jì)一種求強(qiáng)規(guī)劃解的簡化分層算法。以傳統(tǒng)分層算法為基礎(chǔ),引入貪心選擇策略,對(duì)每個(gè)非目標(biāo)狀態(tài)的動(dòng)作進(jìn)行篩選,去除對(duì)求解強(qiáng)規(guī)劃解無益的動(dòng)作,加快狀態(tài)向下搜索的速度,并在改進(jìn)分層的基礎(chǔ)上,優(yōu)化求強(qiáng)規(guī)劃解策略,由于在求解過程中會(huì)存在大量重復(fù)搜索,因此建立一個(gè)集合保存已訪問狀態(tài)的信息,避免對(duì)狀態(tài)的重復(fù)搜索。分析結(jié)果表明,在初始狀態(tài)到達(dá)目標(biāo)狀態(tài)路徑都不重合的情況下,改進(jìn)算法的時(shí)間復(fù)雜度為O(nm)(n為初始狀態(tài)個(gè)數(shù),m為層數(shù)),在都重合情況下為O(m),優(yōu)于普通正向搜索算法與反向搜索算法。

不確定規(guī)劃;強(qiáng)規(guī)劃解;分層狀態(tài);貪心策略;模型檢測;智能規(guī)劃

1 概述

智能規(guī)劃是人工智能領(lǐng)域的一個(gè)重要領(lǐng)域,不確定規(guī)劃［1］是其中的一個(gè)重要分支。在不確定規(guī)劃中,由于動(dòng)作效果是不確定的,一個(gè)規(guī)劃的執(zhí)行可能對(duì)應(yīng)許多個(gè)序列狀態(tài),因此找出一個(gè)序列使所有可能的執(zhí)行都到達(dá)目標(biāo)狀態(tài)(即強(qiáng)規(guī)劃解)是很有意義的。

模型檢測［2-3］是求解不確定規(guī)劃問題的一個(gè)重要方法,目前有很多關(guān)于基于模型檢測求解強(qiáng)規(guī)劃解［4］的研究,并且取得了許多重要成果。如文獻(xiàn)［5-6］提出運(yùn)用反向搜索法求解強(qiáng)規(guī)劃解,由于缺少引導(dǎo)信息,需要重復(fù)搜索大量無用動(dòng)作,因此文獻(xiàn)［7-9］提出運(yùn)用分層法求解強(qiáng)規(guī)劃解,與反向搜索法相比,該方法去除了大量無用的動(dòng)作,避免了許多無用搜索,加快了求解強(qiáng)規(guī)劃解的速度,但該方法仍

存在不足,即對(duì)于每個(gè)非目標(biāo)狀態(tài)可能存在較多向下層轉(zhuǎn)移的動(dòng)作,并且當(dāng)問題規(guī)模較大時(shí),會(huì)存在大量重復(fù)搜索,降低求解效率。

本文參考文獻(xiàn)［9-11］算法,提出一種快速求強(qiáng)規(guī)劃解的算法。改進(jìn)分層策略,使每個(gè)非目標(biāo)狀態(tài)僅保留一個(gè)向下轉(zhuǎn)移的動(dòng)作,并盡可能使處于同一層的非目標(biāo)狀態(tài)可以到達(dá)共同目的狀態(tài),完善求解強(qiáng)規(guī)劃解的策略［12］,避免重復(fù)搜索。

2 相關(guān)定義

在不確定規(guī)劃領(lǐng)域中,存在某些動(dòng)作的執(zhí)行效果是不確定的,那么一個(gè)規(guī)劃的執(zhí)行就會(huì)到達(dá)不同的狀態(tài)。但有時(shí)需要這樣一個(gè)規(guī)劃,一旦執(zhí)行它就一定會(huì)到達(dá)滿足某些條件的狀態(tài),因此,文獻(xiàn)［5］提出強(qiáng)規(guī)劃解的概念。主要定義如下:

定義1(不確定規(guī)劃領(lǐng)域) 一個(gè)規(guī)劃領(lǐng)域是一個(gè)不確定的狀態(tài)轉(zhuǎn)移系統(tǒng)Σ=(S,A,γ),其中,S是有限狀態(tài)集;A是有限動(dòng)作集;γ:S×A→2S是狀態(tài)轉(zhuǎn)移函數(shù)［5］。

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

定義2(規(guī)劃問題) 規(guī)劃領(lǐng)域Σ下的規(guī)劃問題P是一個(gè)三元組(Σ,S0,Sg),其中,S0?S是初始狀態(tài)集合;Sg?S是目標(biāo)狀態(tài)集合［6］。

定義3(不確定規(guī)劃的執(zhí)行結(jié)構(gòu)) 設(shè)π是規(guī)劃領(lǐng)域Σ=(S,A,γ)中的一個(gè)狀態(tài)動(dòng)作序偶表,P= (Σ,S0,Sg)是Σ上的一個(gè)規(guī)劃問題,從初始狀態(tài)集S0所導(dǎo)出的π的執(zhí)行結(jié)構(gòu)為K=＜Q,T＞,其中,Q?S和T?S×S是滿足以下條件的最小集合［13］:

(1)若s∈S0,則s∈Q。

(2)若s∈Q且?(s,a)∈π,s′∈γ(s,a),則s′∈Q且(s,s′)∈T。

執(zhí)行結(jié)構(gòu)K就是一個(gè)有向圖,其結(jié)點(diǎn)集Q是系統(tǒng)(以S0為初始狀態(tài)集)執(zhí)行規(guī)劃解時(shí)所可能到達(dá)的所有狀態(tài)的集合。T表示了所有可能的狀態(tài)轉(zhuǎn)移,K的終止?fàn)顟B(tài)集合記為Sterminal(K),狀態(tài)s∈Q是K的終止?fàn)顟B(tài)當(dāng)且僅當(dāng)不存在s′∈Q使得(s,s′)∈T。

定義5(可達(dá)狀態(tài)數(shù)) 設(shè)Σ=(S,A,γ)是一個(gè)規(guī)劃領(lǐng)域,若有n個(gè)狀態(tài)可以確定到達(dá)狀態(tài)sx,則稱sx的確定可達(dá)狀態(tài)數(shù)為n。若有m個(gè)狀態(tài)可以不確定到達(dá)狀態(tài)sx,則稱sx的不確定可達(dá)狀態(tài)數(shù)為m/2。sx的可達(dá)狀態(tài)數(shù)為確定可達(dá)狀態(tài)數(shù)與不確定可達(dá)狀態(tài)數(shù)之和,記為sxnum。

定義6(最大可達(dá)狀態(tài)數(shù)) 設(shè)Σ=(S,A,γ)是一個(gè)規(guī)劃領(lǐng)域,對(duì)于?s∈S,?a∈A,都有γ(s,a)= {si,si+1,…,si+n}(n≥0),若該集合中可達(dá)狀態(tài)數(shù)最大的狀態(tài)為sm(i≤m≤i+n),其可達(dá)狀態(tài)數(shù)記為max［γ(s,a)］。

3 狀態(tài)分層及強(qiáng)規(guī)劃求解算法

文獻(xiàn)［7］提出在求解強(qiáng)規(guī)劃解之前,首先對(duì)不確定系統(tǒng)中的狀態(tài)進(jìn)行分層,將大量對(duì)求解強(qiáng)規(guī)劃解無用的狀態(tài)動(dòng)作序偶去除,并且運(yùn)用正向搜索技術(shù)求解強(qiáng)規(guī)劃解,即從初始狀態(tài)開始向下搜索(假設(shè)目標(biāo)狀態(tài)位于最底層)。但當(dāng)初始狀態(tài)集S0較大時(shí),則需要對(duì)該集合中的每個(gè)狀態(tài)都進(jìn)行搜索,例如對(duì)于狀態(tài)s1∈S0,γ(s1,a1)=s2,s2?Sg,γ(s2,a2)=s3,s3∈Sg,則對(duì)于狀態(tài)s1的搜索完成。若此時(shí)有狀態(tài)s11∈S0并且γ(s11,a11)=s2,按照原有算法需要繼續(xù)對(duì)s2進(jìn)行搜索,那么就會(huì)產(chǎn)生重復(fù)搜索的情況,尤其當(dāng)不確定系統(tǒng)規(guī)模較大,初始狀態(tài)較多時(shí),會(huì)產(chǎn)生大量冗余搜索。因此,本文在文獻(xiàn)［7］的基礎(chǔ)之上,提出一種簡化的分層方法,對(duì)于每個(gè)非目標(biāo)狀態(tài)及其可執(zhí)行動(dòng)作集合,只保留一個(gè)向下轉(zhuǎn)移的動(dòng)作,并且該動(dòng)作保證所到達(dá)目標(biāo)狀態(tài)的可達(dá)狀態(tài)數(shù)為最大值,這樣可以保證不同的狀態(tài)在執(zhí)行向下轉(zhuǎn)移動(dòng)作時(shí),有很大的可能性轉(zhuǎn)移到同一個(gè)狀態(tài)。

基于該分層方法,改進(jìn)求強(qiáng)規(guī)劃解策略,建立一個(gè)集合,記錄已被訪問節(jié)點(diǎn)的信息,當(dāng)某一個(gè)初始狀態(tài)搜索到已被標(biāo)記的狀態(tài)時(shí),就停止向下搜索,這樣可以避免大量的重復(fù)搜索。

3.1 分層方法

設(shè)P=(Σ,S0,Sg)是一個(gè)不確定的狀態(tài)轉(zhuǎn)移系統(tǒng)Σ=(S,A,γ)上的一個(gè)規(guī)劃問題,初始狀態(tài)集合為S0,目標(biāo)狀態(tài)集合為Sg。貪心選擇策略(該過程類似于投票策略):假設(shè)不確定系統(tǒng)第n層狀態(tài)為:sj,sj+1,…,sj+x(x≥0),第n+1層狀態(tài)為:si,si+1,…,si+y(y≥0),則對(duì)于第n+1層中的狀態(tài)可能存在不止一個(gè)動(dòng)作到達(dá)第n層,則對(duì)動(dòng)作進(jìn)行篩選,篩選步驟如下:

(1)遍歷第n+1層中的所有狀態(tài)的動(dòng)作,只保留執(zhí)行后可到達(dá)第n層的動(dòng)作。

(2)找出第n層中可達(dá)狀態(tài)數(shù)最大且未被選中的狀態(tài)sj+m(m≤x)。

(3)對(duì)于第n+1層中的狀態(tài),只保留可到達(dá)sj+m的動(dòng)作。

(4)返回步驟(2),直到第n+1層中的所有狀態(tài)的動(dòng)作都被篩選。

分層方法具體過程如下:

(1)第1層為目標(biāo)狀態(tài)集合Sg(即最底層),S1=Sg。

(2)S2={s:s?S1,?A1,?a∈A1,γ(s,a)?S1}若S2≠?,則對(duì)所有屬于該層的狀態(tài)的動(dòng)作進(jìn)行篩選,即(s,ai)={s:s∈S2,a:?i,?j,j≠i,{ai,aj}?A1,max［γ(s,ai)］≥max［γ(s,aj)］}再進(jìn)行第3層分層。

(3)S2={s:s?(S1∪S2),?A2,?a∈A2,γ(s,a)?(S1∪S2)},若S3≠?,則對(duì)所有屬于該層的狀態(tài)的動(dòng)作進(jìn)行篩選,即(s,ai)={s:s∈S3,a:?i,?j,j≠i,{ai,aj}?A2,max［γ(s,ai)］≥max［γ(s,aj)］},再進(jìn)行第4層分層,否則結(jié)束分層。

(4)Sx={s:s?(S1∪S2∪…∪Sx-1),?Ax-1,?a∈Ax-1,γ(s,a)?(S1∪S2∪…∪Sx-1)},若Sx≠?,則對(duì)所有屬于該層的狀態(tài)的動(dòng)作進(jìn)行篩選,即(s,ai)={s:s∈Sx,a:?i,?j,j≠i,{ai,aj}?Ax-1, max［γ(s,ai)］≥max［γ(s,aj)］}為第x層(x≥2),否則結(jié)束分層。

通過上述步驟,則分層完畢。

3.2 求強(qiáng)規(guī)劃解的方法

若S0?S1∪S2∪…∪Sfloor,則強(qiáng)規(guī)劃解不存在。反之,開始求解強(qiáng)規(guī)劃解:由于經(jīng)過上述方法分層,在不確定系統(tǒng)中,每個(gè)狀態(tài)只保留一個(gè)向下層狀態(tài)轉(zhuǎn)移的動(dòng)作,并且該動(dòng)作保證所到達(dá)的狀態(tài)的可達(dá)狀態(tài)數(shù)最大,則不同的初始狀態(tài)在向下搜索的時(shí)候有很大的幾率會(huì)到達(dá)同一目標(biāo)狀態(tài)。

假設(shè)集合Solved保存了已經(jīng)遍歷過的狀態(tài),集合Answer保存已遍歷過的狀態(tài)動(dòng)作序偶。

首先從S0中選取任意選取一個(gè)狀態(tài)si,假設(shè)該狀態(tài)在第n層,則往下搜索,必然存在一條唯一路徑L1到達(dá)目標(biāo)狀態(tài)集合,并將S1-L加入到集合Solved。再從S0中選取一個(gè)狀態(tài)sj,則可能出現(xiàn)2種情況:

(1)sj∈Solved:若該狀態(tài)屬于Solved,則表明sj已被遍歷過,則必然存在一條路徑可以到達(dá)目標(biāo)狀態(tài),否則sj不可能屬于Solved集合。

(2)sj?Solved:若不屬于Solved,則進(jìn)行向下搜索,并把sj加入到集合Solved中。假設(shè)狀態(tài)sj下一次到達(dá)的狀態(tài)集合為Snext,則有以下3種情況:

1)Snext?Solved:停止向下搜索。

2)Snext∩Solved=?:將Snext集合加入到Solved集合中,即Solved=Solved∪Snext,再依次對(duì)Snext集合中的狀態(tài)進(jìn)行搜索,直到到達(dá)的狀態(tài)都屬于Solved集合或者Sg集合。

3)Snext∩Solved≠?且Snext?Solved:將Snext集合加入到Solved集合中,即Solved=Solved∪Snext,再依次對(duì)Snext中不屬于Solved的狀態(tài)進(jìn)行搜索,直到到達(dá)的狀態(tài)都屬于Solved集合或者Sg集合。

然后再從S0中選取一個(gè)狀態(tài),重復(fù)這一過程,直到S0為空集,返回強(qiáng)規(guī)劃解。

4 算法實(shí)現(xiàn)及分析

4.1 算法實(shí)現(xiàn)

設(shè)Σ=(S,A,γ)是一個(gè)不確定狀態(tài)轉(zhuǎn)移系統(tǒng);S0為初始狀態(tài)集合;Sg為目標(biāo)狀態(tài)集合;Solved為已訪問狀態(tài)的集合;Unsolved為未訪問狀態(tài)的集合;Answer保存已遍歷過的狀態(tài)動(dòng)作序偶。算法如下:

其中,STRONGNEW(S1,S2,…,Sfloor-1)={s:s?S1∪S2∪…∪Sfloor-1,γ(s,a)?S1∪S2∪…∪Sfloor-1,γ(s,a)≠?}SIMPLIFY(Sfloor)={(s,ai):s∈Sfloor,?i,?j,i≠j,max［γ(s,ai)］＞max［γ(s,aj)］}。

第4行～第7行為對(duì)不確定系統(tǒng)進(jìn)行分層,其中,第5行為構(gòu)建新的分層;第6行為對(duì)新構(gòu)建的分層中的狀態(tài)進(jìn)行動(dòng)作篩選。第8行～第12行進(jìn)行初始化并開始求解強(qiáng)規(guī)劃解。

SOLUTION函數(shù)的具體過程如下:

第2行～第6行,若狀態(tài)si屬于Solved集合,則不需要繼續(xù)向下搜索,否則將該狀態(tài)加入Solved集合中。第7行～第9行,若γ(si,a)?Solved,則將動(dòng)作序偶(si,a)加入Answer解集。第10行～第14行,狀態(tài)si執(zhí)行不確定動(dòng)作a之后,所到達(dá)狀態(tài)集合為si→a。若該集合與Solved集合存在交集,則接下去只需要搜索未被Solved集合包含的狀態(tài)。第15行～第19行,狀態(tài)si執(zhí)行不確定動(dòng)作a之后到達(dá)的狀態(tài)集合與Solved集合不存在交集,則再遞歸調(diào)用SOLUTION函數(shù),繼續(xù)向下搜索。

4.2 算法分析

由于分層消耗的時(shí)間與普通正向搜索算法分層所花費(fèi)的時(shí)間差別不大,因此主要分析求強(qiáng)規(guī)劃解時(shí)間。假設(shè)算法運(yùn)行時(shí)間為T(n,m),其中,n為初始狀態(tài)個(gè)數(shù);m為不確定系統(tǒng)分層后的層數(shù)。根據(jù)強(qiáng)規(guī)劃解的求解策略,考慮2種極端情況:(1)當(dāng)?shù)谝粋€(gè)狀態(tài)si∈S0搜索完畢后,其他所有狀態(tài)都屬于S1-L集合,那么T(n,m)=T(1,m),則時(shí)間復(fù)雜度為O(m);(2)對(duì)于?i,si∈S0(0≤i≤n),且S1-L∩S2-L∩…∩Sn-L=?,那么:

其中,C1,C2為常數(shù);則時(shí)間復(fù)雜度為O(nm)。

5 算法示例及實(shí)驗(yàn)對(duì)比

5.1 算法示例

設(shè)Σ=(S,A,γ)是一個(gè)確定狀態(tài)轉(zhuǎn)移系統(tǒng),不確定狀態(tài)轉(zhuǎn)移圖如圖1所示。已知S0={s1,s2},Sg= {s6,s7,s8},運(yùn)用本文算法求解該不確定系統(tǒng)的強(qiáng)規(guī)劃解。

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

首先進(jìn)行分層:S1={s6,s7,s8},接下去構(gòu)建第2層,由圖1可知S2={s3,s4,s5},需要對(duì)動(dòng)作進(jìn)行篩選,因?yàn)闋顟B(tài)s6的可達(dá)狀態(tài)數(shù)為1,s7的可達(dá)狀態(tài)數(shù)為2.5,s8的可達(dá)狀態(tài)數(shù)為1.5,則s3,s4,s5只保留到達(dá)s7的動(dòng)作。同理,構(gòu)建第3層,S3= {s1,s2},再進(jìn)行動(dòng)作篩選,則s1,s2只保留到達(dá)s4的動(dòng)作。篩選動(dòng)作后的不確定狀態(tài)轉(zhuǎn)移圖如圖2所示。

圖2 篩選動(dòng)作后的不確定狀態(tài)轉(zhuǎn)移圖

分層完畢后,開始進(jìn)行強(qiáng)規(guī)劃的求解。首先從狀態(tài)s1開始進(jìn)行搜索,直到到達(dá)目標(biāo)狀態(tài)。則Solved={s4,s7,s8},Answer={(s1,a2),(s4,a4)}再從狀態(tài)s2開始進(jìn)行搜索,由圖2可知,γ(s2,a)={s3,s4},因?yàn)閟4∈Sovled,則接下去只需要對(duì)s3進(jìn)行搜索,由于s7∈Solved,則只需把動(dòng)作序偶(s3,a3)加入Answer集合。最終得到的強(qiáng)規(guī)劃解為Answer={(s1,a2),(s4,a4),(s2,a1), (s3,a3)}。

5.2 實(shí)驗(yàn)對(duì)比

以下為普通正向搜索算法,改進(jìn)后正向搜索算法(本文算法)以及反向搜索算法的實(shí)驗(yàn)結(jié)果比較。實(shí)驗(yàn)環(huán)境均為Windows7+Core(TM)i3-3220 3.3 GHz+4.0 GB內(nèi)存+VC6。3種算法使用的數(shù)據(jù)輸入輸出過程相同,故其運(yùn)行時(shí)間沒有包括在內(nèi)。運(yùn)行時(shí)間比較如表1所示。根據(jù)表1可知,改進(jìn)后正向搜索算法與普通正向搜索算法相比,在求解速度有一定的提高。但從最后2組數(shù)據(jù)中得出,普通算法與改進(jìn)后算法時(shí)間是處于一個(gè)數(shù)量級(jí)的,這是由于在初始狀態(tài)搜索的路徑中幾乎不存在重合的狀態(tài)(即算法分析中的第2種情況),導(dǎo)致搜索時(shí)間增加。但這2種算法比反向搜索算法求解效率都要高。

表1 運(yùn)行時(shí)間比較s

6 結(jié)束語

本文設(shè)計(jì)一種快速求解強(qiáng)規(guī)劃解的算法。該算法主要從兩方面進(jìn)行優(yōu)化:(1)在原有分層基礎(chǔ)上,對(duì)非目標(biāo)狀態(tài)的動(dòng)作進(jìn)行篩選,加快搜索速度; (2)改進(jìn)求強(qiáng)規(guī)劃解的策略,避免對(duì)狀態(tài)的重復(fù)搜索。從理論上分析了改進(jìn)后算法時(shí)間復(fù)雜度的范圍。實(shí)驗(yàn)結(jié)果證明了其有效性。今后將從以下方面進(jìn)行研究:(1)改進(jìn)對(duì)非目標(biāo)狀態(tài)篩選的策略,加快搜索速度;(2)運(yùn)用本文算法求解不確定規(guī)劃中的強(qiáng)循環(huán)規(guī)劃解。

［1]Weld D S.Recent Advances in AI Planning［J］.AI Magazine,1999,20(2):93-123.

［2]Cimatti A,Roveri M.Conformant Planning via Symbolic Model Checking［J］.Journal of Artificial Intelligence Research,2000,13(3):305-338.

［3]Huang Wei,WenZhonghua,JiangYunfei,etal.Observation Reduction for Strong Plans［C］//Proceedings of the 20th International Joint Conference on Artificial Intelligence.Hyderabad,India:［s.n.］,2007:1930-1935.

［4]Marco P,Traverso P.Planning as Model Checking for Extended Goals in Nondeterministic Domains［C］// Proceedings of the 17th International Joint Conference on Artificial Intelligence.San Francisco,USA:［s.n.］, 2001:479-484.

［5]Cimatti A,Pistore M,Roveri M,et al.Weak,Strong,and Strong Cyclic Planning via Symbolic Model Checking［J］.Artificial Intelligence,2003,47(1):35-84.

［6]Cimatti A,Roved M,Traverso P.Strong Planning in Nondeterministic Domains via Model Checking［C］// Proceedings of the 4th International Conference on AI Planning Systems.Edinburgh,UK:［s.n.］,1998:36-43.

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

［8]Fu Jicheng,Vincent N,Farokh B,et al.Simple and Fast Strong Planning For Fully-observable Nondeterministic Planning Problems［C］//Proceedings of IJCAI’11.Barcelona,Spain:［s.n.］,2011:473-478.

［9]陳建林.強(qiáng)規(guī)劃解、弱規(guī)劃解的研究［D］.湘潭:湘潭大學(xué),2011.

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

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

［12]胡雨隆,文中華,常 青,等.確定樹求強(qiáng)規(guī)劃解［J］.計(jì)算機(jī)工程與應(yīng)用,2012,48(4):40-42.

［13]Ghallab M,Nau D,Traverso P.Automated Planning Theory and Practice［M］.［S.l.］:Morgan Kaufmann Publishers,2004.

［14]胡雨隆,文中華,常 青,等.不確定規(guī)劃中非循環(huán)可達(dá)關(guān)系的求解方法［J］.計(jì)算機(jī)仿真,2012,29(4): 114-117.

編輯 劉 冰

A Fast Algorithm for Solving Strong Planning Solution

LAO Jiaqi1,WEN Zhonghua1,2,WU Xiaohui1,TANG Jie1
(1.College of Information Engineering,Xiangtan University,Xiangtan 411105,China;
2.College of Computer and Communication,Hunan Institute of Engineering,Xiangtan 411104,China)

This paper designs a quick solution to solve the simplified layered strong planning algorithm to increase the settlement efficiency.It is based on the introduction of greedy strategy,screening for non-target state for each action.This algorithm removes useless action plan for solving the strong solution to accelerate the state down search speed.On the basis of improved stratification,optimization and strong strategic planning solution,because the solution process is repeated,there are a lot of searching,and therefore the algorithm creates a collection to save the state having access to information,to avoid duplication of state search.After analysis,in the condition that the paths which are the intial state to goal state are overlapping,and the time complexity of this algorithm isO(nm),(nis the number of the initial state,mis the number of layers).The time complexity isO(m)in the condition that all the initial states to the target states are coincident.And the results are better than the ordinary forward search algorithm and reverse search algorithm.

nondeterministic planning;strong planning solution;hierarchical state;greedy strategy;model checking; intelligent planning

勞佳琪,文中華,伍小輝,等.一種快速求強(qiáng)規(guī)劃解的算法［J］.計(jì)算機(jī)工程,2015,41(3):162-166.

英文引用格式:Lao Jiaqi,Wen Zhonghua,Wu Xiaohui,et al.A Fast Algorithm for Solving Strong Planning Solution［J］.Computer Engineering,2015,41(3):162-166.

1000-3428(2015)03-0162-05

:A

:TP18

10.3969/j.issn.1000-3428.2015.03.031

國家自然科學(xué)基金資助項(xiàng)目(61070232,61272295,61105039,61202398);湖南省重點(diǎn)學(xué)科建設(shè)基金資助項(xiàng)目(0812);湖南省教育廳科學(xué)研究基金資助一般項(xiàng)目(12C0399)。

勞佳琪(1990-),男,碩士研究生,主研方向:智能規(guī)劃;文中華,教授、博士生導(dǎo)師;伍小輝、唐 杰,碩士研究生。

2014-03-07

:2014-05-22E-mail:lywhlao@qq.com