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

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

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

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

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

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

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

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

1 概述

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

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

存在不足,即對于每個非目標狀態(tài)可能存在較多向下層轉(zhuǎn)移的動作,并且當問題規(guī)模較大時,會存在大量重復搜索,降低求解效率。

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

2 相關(guān)定義

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

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

γ用來刻畫不確定性:在狀態(tài)s下執(zhí)行動作a所得到的狀態(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ī)劃問題) 規(guī)劃領(lǐng)域Σ下的規(guī)劃問題P是一個三元組(Σ,S0,Sg),其中,S0?S是初始狀態(tài)集合;Sg?S是目標狀態(tài)集合［6］。

定義3(不確定規(guī)劃的執(zhí)行結(jié)構(gòu)) 設(shè)π是規(guī)劃領(lǐng)域Σ=(S,A,γ)中的一個狀態(tài)動作序偶表,P= (Σ,S0,Sg)是Σ上的一個規(guī)劃問題,從初始狀態(tài)集S0所導出的π的執(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就是一個有向圖,其結(jié)點集Q是系統(tǒng)(以S0為初始狀態(tài)集)執(zhí)行規(guī)劃解時所可能到達的所有狀態(tài)的集合。T表示了所有可能的狀態(tài)轉(zhuǎn)移,K的終止狀態(tài)集合記為Sterminal(K),狀態(tài)s∈Q是K的終止狀態(tài)當且僅當不存在s′∈Q使得(s,s′)∈T。

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

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

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

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

基于該分層方法,改進求強規(guī)劃解策略,建立一個集合,記錄已被訪問節(jié)點的信息,當某一個初始狀態(tài)搜索到已被標記的狀態(tài)時,就停止向下搜索,這樣可以避免大量的重復搜索。

3.1 分層方法

設(shè)P=(Σ,S0,Sg)是一個不確定的狀態(tài)轉(zhuǎn)移系統(tǒng)Σ=(S,A,γ)上的一個規(guī)劃問題,初始狀態(tài)集合為S0,目標狀態(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),則對于第n+1層中的狀態(tài)可能存在不止一個動作到達第n層,則對動作進行篩選,篩選步驟如下:

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

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

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

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

分層方法具體過程如下:

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

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

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

(4)Sx={s:s?(S1∪S2∪…∪Sx-1),?Ax-1,?a∈Ax-1,γ(s,a)?(S1∪S2∪…∪Sx-1)},若Sx≠?,則對所有屬于該層的狀態(tài)的動作進行篩選,即(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 求強規(guī)劃解的方法

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

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

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

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

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

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

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

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

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

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

4.1 算法實現(xiàn)

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

其中,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行為對不確定系統(tǒng)進行分層,其中,第5行為構(gòu)建新的分層;第6行為對新構(gòu)建的分層中的狀態(tài)進行動作篩選。第8行～第12行進行初始化并開始求解強規(guī)劃解。

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

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

4.2 算法分析

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

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

5 算法示例及實驗對比

5.1 算法示例

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

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

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

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

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

5.2 實驗對比

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

表1 運行時間比較s

6 結(jié)束語

本文設(shè)計一種快速求解強規(guī)劃解的算法。該算法主要從兩方面進行優(yōu)化:(1)在原有分層基礎(chǔ)上,對非目標狀態(tài)的動作進行篩選,加快搜索速度; (2)改進求強規(guī)劃解的策略,避免對狀態(tài)的重復搜索。從理論上分析了改進后算法時間復雜度的范圍。實驗結(jié)果證明了其有效性。今后將從以下方面進行研究:(1)改進對非目標狀態(tài)篩選的策略,加快搜索速度;(2)運用本文算法求解不確定規(guī)劃中的強循環(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］.軟件學報,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]陳建林.強規(guī)劃解、弱規(guī)劃解的研究［D］.湘潭:湘潭大學,2011.

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

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

［12]胡雨隆,文中華,常 青,等.確定樹求強規(guī)劃解［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)可達關(guān)系的求解方法［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

勞佳琪,文中華,伍小輝,等.一種快速求強規(guī)劃解的算法［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

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

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

2014-03-07

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