強(qiáng)規(guī)劃的最小期望權(quán)值求解算法?

袁 潤 文中華 戴良偉 陳秋茹

（1.湘潭大學(xué)信息工程學(xué)院 湘潭 411105）（2.湖南工程學(xué)院湖南省風(fēng)電裝備與電能變換協(xié)同創(chuàng)新中心 湘潭 411104）（3.湘潭大學(xué)智能計(jì)算與信息處理教育部重點(diǎn)實(shí)驗(yàn)室 湘潭 411105）

1 引言

智能規(guī)劃是人工智能近年來研究的一個(gè)重要領(lǐng)域［1～2］。隨著人工智能的快速發(fā)展，智能規(guī)劃中的不確定規(guī)劃問題逐漸成為國內(nèi)外學(xué)者的研究熱點(diǎn)［3］。目前，對不確定規(guī)劃問題的研究在國內(nèi)外都取得了許多的研究進(jìn)展［4～5］。最初，Cimatti等在文獻(xiàn)［6］給出了不確定規(guī)劃問題的強(qiáng)規(guī)劃解，弱規(guī)劃解和強(qiáng)循環(huán)規(guī)劃解的定義以及說明，并提出用模型檢驗(yàn)的方法來求解強(qiáng)規(guī)劃問題。之后，也有學(xué)者提出利用模式識別技術(shù)求弱、強(qiáng)、強(qiáng)循環(huán)規(guī)劃解［7］，具體地通過反向搜索算法求強(qiáng)規(guī)劃解，但其不足在于，搜索過程由于缺少引導(dǎo)信息，進(jìn)行了大量的無用搜索以及冗余計(jì)算操作，大大地降低了求解效率。文獻(xiàn)［8］則提出了一種簡單快速的完全可觀測的不確定規(guī)劃問題的強(qiáng)循環(huán)規(guī)劃求解算法。文獻(xiàn)［9］中探討了在部分可觀察下的規(guī)劃問題，提出一種約減觀察變量的方法。文獻(xiàn)［10～12］提出了用分層法求最小權(quán)值規(guī)劃解的方法，該方法是基于狀態(tài)分層設(shè)計(jì)的一種方法，相對于文獻(xiàn)［1］提出的反向搜索，通過實(shí)時(shí)更新所需搜索層數(shù)的上界和下界，從而避免了大量無用搜索和冗余計(jì)算，一定程度上提高了求解效率。

在實(shí)際生活中，由于受外部環(huán)境的干擾，不同狀態(tài)之間轉(zhuǎn)移和到達(dá)結(jié)果都是隨機(jī)的、不確定的，而且不同狀態(tài)在執(zhí)行不同的動作時(shí)所要耗費(fèi)的代價(jià)也是不同的。針對這一問題，本文對不確定規(guī)劃問題中的動作賦權(quán)值，用概率來表示狀態(tài)轉(zhuǎn)移的不確定性。在求強(qiáng)規(guī)劃解過程時(shí)，文獻(xiàn)［13］提出了一種最小權(quán)值求強(qiáng)規(guī)劃解的方法，該方法以耗費(fèi)代價(jià)總和最小為目標(biāo)函數(shù)，通過簡單地累加規(guī)劃解中動作權(quán)值來求得最小權(quán)值強(qiáng)規(guī)劃解，意義不大。在分析現(xiàn)實(shí)生活中統(tǒng)計(jì)得到的數(shù)據(jù)時(shí)，用數(shù)學(xué)期望是為了準(zhǔn)確地預(yù)期某件事未來可能的發(fā)展趨勢。最小數(shù)學(xué)期望的研究首先開始于經(jīng)濟(jì)理論的研究，經(jīng)濟(jì)理論中的一個(gè)重要的研究課題是如何度量不確定環(huán)境下人們的偏好問題，與本文所提的不確定環(huán)境下的最優(yōu)路徑規(guī)劃問題有類似之處。因此，本文嘗試將最小期望權(quán)值引入來解決智能規(guī)劃領(lǐng)域的問題。文獻(xiàn)［14］提出了期望權(quán)值的概念，該文將其作為求解強(qiáng)循環(huán)規(guī)劃解這一類問題的評判指標(biāo)。該方法的主要思想是使用深度優(yōu)先搜索求出規(guī)劃問題的所有強(qiáng)循環(huán)規(guī)劃解，再將解分別轉(zhuǎn)換成以狀態(tài)到目標(biāo)狀態(tài)的期望權(quán)值為變元的線性方程組，最后使用高斯消元法解方程組，從而找出最小期望權(quán)值強(qiáng)循環(huán)規(guī)劃解。結(jié)合文獻(xiàn)［13～14］，本文提出求動作權(quán)值總和的期望值最小的強(qiáng)規(guī)劃解，即最小期望權(quán)值強(qiáng)規(guī)劃解。在執(zhí)行強(qiáng)規(guī)劃解時(shí)，因?yàn)槊看螐某跏紶顟B(tài)到達(dá)目標(biāo)狀態(tài)所執(zhí)行過的動作個(gè)數(shù)是隨機(jī)的，對應(yīng)的所有動作的權(quán)值總和呈概率分布，此時(shí)動作的期望權(quán)值代表的是動作實(shí)際執(zhí)行時(shí)所耗費(fèi)的平均代價(jià)值。

本文首先將不確定規(guī)劃問題中的目標(biāo)狀態(tài)集并入已搜索狀態(tài)集，運(yùn)用反向搜索求最小期望權(quán)值強(qiáng)規(guī)劃解；在搜索過程中，需不斷將最小期望權(quán)值所對應(yīng)狀態(tài)并入已搜索狀態(tài)集，并更新未搜索狀態(tài)集，迭代上述搜索步驟，直到已搜索狀態(tài)集不變化為止，最后找出最小期望權(quán)值強(qiáng)規(guī)劃解。

2 相關(guān)定義

定義1（規(guī)劃領(lǐng)域）規(guī)劃領(lǐng)域是一個(gè)不確定的狀態(tài)轉(zhuǎn)換系統(tǒng)，其中每個(gè)狀態(tài)轉(zhuǎn)換都有一定的概率分布；它可以表示成一個(gè)四元組，即∑=＜S，A，γ，P＞，其中：

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

A是一個(gè)帶權(quán)值的有限動作集。每個(gè)動作的執(zhí)行是有耗費(fèi)權(quán)值的，執(zhí)行動作a用耗費(fèi)權(quán)值cost[a](a∈A)表示。

γ.S×A→2S是一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)。γ用來表示不確定性：γ=(s，a)表示狀態(tài)s執(zhí)行動作a所可能得到的結(jié)果狀態(tài)集合；若γ=(s，a)非空，則稱動作a在狀態(tài)s下是可執(zhí)行的。在狀態(tài)s下可執(zhí)行的動作集合記作 A(s)={a:?s'∈γ(s，a)}；其中，稱 s'是s可達(dá)的，稱(s，a)為狀態(tài)動作序偶。

P是一個(gè)概率分布。對于動作a∈A以及狀態(tài)s和s'∈S，Pa(s'|s)表示在狀態(tài)s下執(zhí)行動作a之后得到的結(jié)果狀態(tài)是s'的概率。對于任意的s∈S ，若存在 a∈A 和 γ=(s，a)={s1'，s2'，…，sx'}，那么就有

定義2（規(guī)劃問題）規(guī)劃問題是一個(gè)三元組Pro=＜∑，S0，Sg＞，其中 ∑ 是規(guī)劃領(lǐng)域，S0?S是初始狀態(tài)集合，Sg?S是目標(biāo)狀態(tài)集合。

定義3（執(zhí)行結(jié)構(gòu)）執(zhí)行結(jié)構(gòu)是一個(gè)二元組K=＜Q，T＞，其中，Q?S和T?S×S是滿足以下條件的最小集合：

若s∈S，那么s∈Q。

若s∈Q且存在某個(gè)動作a使得(s，a)∈π，那么對所有的 s'（其中 s'∈γ(s，a)）都有 s'∈Q 且(s，s')∈ T 。

狀態(tài)s∈Q是K的一個(gè)終止?fàn)顟B(tài)當(dāng)且僅當(dāng)不存在狀態(tài)s'∈Q，使得(s，s')∈T。 K是一個(gè)有向圖，其中，Q是在執(zhí)行規(guī)劃解時(shí)能夠到達(dá)的所有狀態(tài)集合，T表示所有可能的狀態(tài)轉(zhuǎn)移。顯然，K的終止?fàn)顟B(tài)代表規(guī)劃執(zhí)行的終止，這里用Sterminal(K)表示執(zhí)行結(jié)構(gòu)K的終止?fàn)顟B(tài)集。

定義4（強(qiáng)規(guī)劃解）設(shè) ∑=＜S，A，γ，P＞是一個(gè)規(guī)劃領(lǐng)域，Pro=＜∑，S0，Sg＞是∑上的一個(gè)規(guī)劃問題，π是規(guī)劃領(lǐng)域∑中的一個(gè)狀態(tài)動作序偶表，K=＜Q，T＞是π從S導(dǎo)出的執(zhí)行結(jié)構(gòu)。那么：

S是Pro的強(qiáng)規(guī)劃解當(dāng)且僅當(dāng)K是無環(huán)的，且

若Pro有強(qiáng)規(guī)劃解，則稱可以從初始狀態(tài)集強(qiáng)到達(dá)目標(biāo)狀態(tài)集；從初始狀態(tài)集開始搜索強(qiáng)規(guī)劃解，最終強(qiáng)到達(dá)目標(biāo)狀態(tài)集的過程稱作強(qiáng)規(guī)劃。

定義5（強(qiáng)規(guī)劃的最小期望權(quán)值）設(shè)∑=＜S，A，γ，P＞ 是 一 個(gè) 規(guī) 劃 領(lǐng) 域 ，Pro=＜∑，S0，Sg＞是 ∑上的一個(gè)規(guī)劃問題，則 Eπ是Pro的強(qiáng)規(guī)劃的最小期望權(quán)值之和（簡稱最小期望權(quán)值）。當(dāng)且僅當(dāng)π、π'是Pro的強(qiáng)規(guī)劃解，且對于 ?π'，都滿足 Eπ≤Eπ'。 Eπ定義為

其中，cost[a](a ∈Act(si) )表示所需的代價(jià)，即執(zhí)行動作a所耗費(fèi)權(quán)值；E[sx]表示未搜索狀態(tài)中新加入的狀態(tài)所對應(yīng)的期望權(quán)值之和，E[sl]表示sk所能到達(dá)的除sx的其他狀態(tài)所對應(yīng)的期望權(quán)值之和；由于狀態(tài)之間的轉(zhuǎn)換都是不確定的，所以Paj(sl|sk)表示由狀態(tài)sk到達(dá)狀態(tài)sl的概率。

3 算法思想及實(shí)現(xiàn)

由最小期望權(quán)值的定義（定義5）可知，執(zhí)行最小期望權(quán)值強(qiáng)規(guī)劃解的狀態(tài)動作序偶集合πmin，不但可以保證系統(tǒng)能從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)，而且所需動作的期望權(quán)值最小。

3.1 算法思想

經(jīng)濟(jì)學(xué)中，數(shù)學(xué)期望是度量不確定環(huán)境下人們的偏好問題。那么本文所提的不確定環(huán)境下的最優(yōu)路徑規(guī)劃問題也可類比應(yīng)用數(shù)學(xué)期望來解決。由于是求解不同狀態(tài)之間的最優(yōu)路徑，狀態(tài)與狀態(tài)轉(zhuǎn)換之間的動作是不確定的、有概率的，我們將動作賦予權(quán)值，那么動作權(quán)值的最小期望即路徑最小。

針對上述問題，本文設(shè)計(jì)了強(qiáng)規(guī)劃的最小期望權(quán)值求解算法（LEC）。由于該算法首先將目標(biāo)狀態(tài)集Sg加入已搜索狀態(tài)集Sgoal，然后反向搜索未加入中Sgoal的狀態(tài)，從中找到能強(qiáng)到達(dá)Sgoal，且所需期望權(quán)值最小的狀態(tài)；找到之后，將其加入Sgoal，并更新剩余未加入Sgoal中的狀態(tài)到達(dá)已搜索狀態(tài)集的最小期望動作權(quán)值；再迭代上述搜索步驟，直到Sgoal不再變化為止。

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

設(shè)帶權(quán)值的不確定規(guī)劃問題P的狀態(tài)集St中含有 n 個(gè)狀態(tài)其中 Act(si)是從狀態(tài)

si出發(fā)的動作集；E[si](1 ≤i≤n)用于保存從狀態(tài)si出發(fā)到達(dá)目標(biāo)狀態(tài)的強(qiáng)規(guī)劃解的最小期望權(quán)值，（即強(qiáng)規(guī)劃解中的最小的期望權(quán)值之和）；sAct[si](1 ≤i≤n)用于保存以狀態(tài)si為初始狀態(tài)的最小期望權(quán)值強(qiáng)規(guī)劃解；sSet為已經(jīng)求得的到達(dá)目標(biāo)狀態(tài)集且具有最小期望權(quán)值強(qiáng)規(guī)劃解的狀態(tài)集合；Sg表示目標(biāo)狀態(tài)集，Sgoal表示已搜索狀態(tài)集目標(biāo)狀態(tài)集。

強(qiáng)規(guī)劃的最小期望權(quán)值求解函數(shù)如下。

1）初始化；

2）更新到達(dá)已搜索狀態(tài)集Sgoal所需的最小期望權(quán)值；

3）找強(qiáng)到達(dá)目標(biāo)狀態(tài)集且所需的期望權(quán)值最小的狀態(tài)。

29. end if;

30. end if;

31. end for;

32.end for;

33.return E，sAct;

34.end;

第2～7行是初始化所有狀態(tài)到達(dá)目標(biāo)狀態(tài)集的最小期望權(quán)值。其中，目標(biāo)狀態(tài)到達(dá)目標(biāo)狀態(tài)集的最小權(quán)值初始化為0；其余的狀態(tài)到達(dá)目標(biāo)狀態(tài)集的最小權(quán)值初始化為+∞。

第8行是把目標(biāo)狀態(tài)集Sg加入到已搜索狀態(tài)集Sgoal。

第9～17行是更新 S–Sgoal集合中的狀態(tài)到達(dá)已搜索狀態(tài)集Sgoal所需的最小期望權(quán)值。其中，第10行是對于動作ai，如果它是狀態(tài)Sx下可執(zhí)行的動作，且Sx尚未加入Sgoal，并且Sx執(zhí)行動作ai所可能到達(dá)的狀態(tài)集合，則執(zhí)行第11行代碼，計(jì)算狀態(tài)Sx執(zhí)行動作ai后，強(qiáng)到達(dá)目標(biāo)狀態(tài)集Sg所需的期望權(quán)值minCost。第12行是判斷執(zhí)行動作ai的方案是否優(yōu)于已有的方案（即是否有，如果是，則在13、14行更新 E 和sAct；否則，保持原有方案。

第18～32行通過迭代來更新已搜索狀態(tài)集Sgoal。每次迭代之后，都會從尚未加入Sgoal的狀態(tài)中，將到達(dá)目標(biāo)狀態(tài)集所需期望權(quán)值最小的狀態(tài)加入Sgoal；并更新其余尚未加入Sgoal到達(dá)目標(biāo)狀態(tài)集所需的最小期望權(quán)值。

第19～22行是從集合S–Sgoal中找到能強(qiáng)到達(dá)目標(biāo)狀態(tài)集且所需的期望權(quán)值最小的狀態(tài)Sx，將其加入Sgoal。

第23～31行是在 Sx加入Sgoal之后，更新其余尚未加入Sgoal的狀態(tài)強(qiáng)到達(dá)目標(biāo)狀態(tài)集所需的最小期望權(quán)值。其中第24行是判斷尚未加入Sgoal的狀態(tài)SK是否存在動作a能夠通過Sx強(qiáng)到達(dá)Sgoal；如果是，則在第25行計(jì)算通過Sx強(qiáng)到達(dá)目標(biāo)狀態(tài)集的最小期望權(quán)值minCost；如果第26行判斷minCost小于原來方案的值，則在第27-28行更新E[sk]和sAct[sk]。這里之所以強(qiáng)調(diào)是通過Sx強(qiáng)到達(dá)目標(biāo)狀態(tài)，是因?yàn)槊看蔚贾辉赟goal中加入了Sx這個(gè)新元素；所以只需關(guān)注它所帶來的改變就可以了；這樣不但保證了算法本身的完備性，同時(shí)也減少了計(jì)算量。

3.3 算法時(shí)間復(fù)雜度分析

該算法分為三個(gè)步驟：1）初始化；2）更新到達(dá)已搜索狀態(tài)集Sgoal所需的最小期望權(quán)值；3）找強(qiáng)到達(dá)目標(biāo)狀態(tài)集且所需的期望權(quán)值最小的狀態(tài)。設(shè)有限狀態(tài)集大小為n，帶權(quán)值的有限動作集為m。

1）給定初始化部分算法復(fù)雜度為O(n)。

2）更新到達(dá)已搜索狀態(tài)集Sgoal所需的最小期望權(quán)值。

若所有的 si執(zhí)行動作 aj都到達(dá) Sgoal，且mincost小于si的期望值，更新其mincost值，此時(shí)為次優(yōu)解，其算法復(fù)雜度為O(m*n)；若只有唯一一個(gè)Sgoal滿足條件，即最優(yōu)解，其算法復(fù)雜度為O(m)。

3）找強(qiáng)到達(dá)目標(biāo)狀態(tài)集且所需的期望權(quán)值最小的狀態(tài)。

首先，需要計(jì)算狀態(tài)集合中所有狀態(tài)下的最小期望權(quán)值，并比較得出最小值；其次，迭代更新其余尚未加入Sgoal但卻可以強(qiáng)到達(dá)目標(biāo)狀態(tài)集的狀態(tài)，求出其所需的最小期望權(quán)值，此時(shí)如果尚未加入Sgoal的狀態(tài)SK不存在動作a能夠通過Sx強(qiáng)到達(dá)Sgoal條件，則算法取得最優(yōu)解，其算法復(fù)雜度為O(n2)；若滿足該條件，同時(shí)計(jì)算出來的最小期望權(quán)值均小于當(dāng)前狀態(tài)的期望權(quán)值，則為次優(yōu)解，次數(shù)復(fù)雜度為O(n3)。

4 算法實(shí)例分析

1）如圖1所示，是一個(gè)帶權(quán)值的不確定規(guī)劃領(lǐng)域 ∑=＜S，A，γ＞ 。 Pro=＜∑，S0，Sg＞ 是 ∑ 上的一個(gè)規(guī)劃問題。其中，S0={}s1是初始狀態(tài)集合，是目標(biāo)狀態(tài)集合。規(guī)劃問題Pro是在規(guī)劃領(lǐng)域∑上求出從初始狀態(tài)集合S0出發(fā)到達(dá)目標(biāo)狀態(tài)集合Sg的最小期望權(quán)值強(qiáng)規(guī)劃解。

圖1 帶權(quán)值的不確定規(guī)劃領(lǐng)域

算法首先對所有狀態(tài)到達(dá)Sg的E[si]進(jìn)行初始化。由上述可知，S1是初始狀態(tài)，S5是目標(biāo)狀態(tài)，那么E[s5]=0+∞。

第二次搜索：將上一次搜索得到的狀態(tài)S4并入Sgoal中，遍歷其余狀態(tài)，找到一個(gè)到目標(biāo)狀態(tài)的最小期望權(quán)值的狀態(tài)。此時(shí)，Sgoal={s4，s5}。

第三次搜索：將上一次搜索得到的狀態(tài)S3并入Sgoal中，遍歷其余狀態(tài)，找到一個(gè)到目標(biāo)狀態(tài)的最小期望權(quán)值的狀態(tài)。因?yàn)?s1?Sgoal，a1∈Act(s1γ(s，所以根據(jù)minCost公式，可得到E[s1]=159，sAct[s1]={a2， a5， a4} 。

然后再循環(huán)，執(zhí)行第四次、第五次搜索等，直到已搜索狀態(tài)集合S0中的所有狀態(tài)不再變化為止。

通過上述搜索，最終得到從由S1到S5的強(qiáng)規(guī)劃期望權(quán)值解為期望權(quán)值為159。

2）如圖2所示，通過增加不確定規(guī)劃問題的狀態(tài)數(shù)與動作數(shù)，重新按照上述步驟進(jìn)行求解，我們同樣可以獲得最小期望權(quán)值強(qiáng)規(guī)劃解。

圖2 增加狀態(tài)數(shù)與動作數(shù)后的帶權(quán)值不確定規(guī)劃

S1是初始狀態(tài)，S10是目標(biāo)狀態(tài)，那么E[s10]=0，均為+∞。

第二次搜索：將上一次搜索得到的狀態(tài)S8并入Sgoal中，遍歷其余狀態(tài)，找到一個(gè)到目標(biāo)狀態(tài)的最小期望權(quán)值的狀態(tài)。此時(shí)，Sgoal={s8，s10}。

然后再循環(huán)，執(zhí)行第四次、第五次搜索等等，直到已搜索狀態(tài)集合S0中的所有狀態(tài)不再變化為止。

通過上述搜索，最終得到從由S1到S10的強(qiáng)規(guī)劃 期 望 權(quán) 值 解 為 ：最小期望權(quán)值為162。

5 算法實(shí)驗(yàn)分析

本文的實(shí)驗(yàn)環(huán)境為：Windows10+Intel?CoreTMi5-4590@3.3GHz+4GB內(nèi)存。

根據(jù)本文提出的LEC算法設(shè)計(jì)實(shí)驗(yàn)，可以較快地求出不確定規(guī)劃問題的強(qiáng)規(guī)劃解，且所需要的期望權(quán)值之和近似最小。文獻(xiàn)［13］最早提出最小權(quán)值強(qiáng)規(guī)劃解的概念，本文所設(shè)計(jì)的LEC算法與其進(jìn)行運(yùn)行時(shí)間的比較，文獻(xiàn)［13］的算法在試驗(yàn)中用“算法1”表示，本文算法用“算法2”表示。通過幾組不同的狀態(tài)數(shù)的不確定規(guī)劃下進(jìn)行50組實(shí)驗(yàn)數(shù)據(jù)的平均運(yùn)行時(shí)間比較，如表1所示。

表1 求解最小權(quán)值強(qiáng)規(guī)劃解的運(yùn)行時(shí)間比較

上述實(shí)驗(yàn)是在狀態(tài)數(shù)與動作數(shù)相等的條件下進(jìn)行比較，為了更進(jìn)一步評判本文所提出的LEC算法，在狀態(tài)數(shù)相同的情況下，通過增加動作數(shù)進(jìn)行實(shí)驗(yàn)比較時(shí)間代價(jià)，通過幾組不同的狀態(tài)數(shù)以及不同的動作數(shù)進(jìn)行50組實(shí)驗(yàn)數(shù)據(jù)的平均運(yùn)行時(shí)間比較，如表2所示。

表1的試驗(yàn)中“算法1”和“算法2”分別用了分層策略和LEC權(quán)值兩種不同的策略進(jìn)行算法設(shè)計(jì)，從實(shí)驗(yàn)結(jié)果分析來看，在動作數(shù)和狀態(tài)數(shù)相同的情況下，“算法2”的實(shí)驗(yàn)時(shí)間代價(jià)明顯低于“算法1”。

現(xiàn)實(shí)生活中，不確定的動作數(shù)往往是大于其狀態(tài)數(shù)的，表2的實(shí)驗(yàn)中，通過狀態(tài)數(shù)相同，增加動作數(shù)的實(shí)驗(yàn)來比較其時(shí)間代價(jià)。實(shí)驗(yàn)預(yù)期結(jié)果是：當(dāng)狀態(tài)數(shù)一樣，大量增加不確定動作數(shù)時(shí)，計(jì)算最小期望權(quán)值的時(shí)間會較繁瑣，其時(shí)間代價(jià)會迅速增加。但是，表2的實(shí)驗(yàn)結(jié)果卻顯示其時(shí)間代價(jià)增長較緩。通過進(jìn)一步的分析研究，大量增加動作數(shù)后，算法只會選擇符合已加入Sgoal的最小期望權(quán)值，其余不滿足條件的，算法直接將其過濾，從而節(jié)省了一部分時(shí)間。

表2 狀態(tài)數(shù)相同動作數(shù)不同的運(yùn)行時(shí)間比較

通過與文獻(xiàn)［13］在狀態(tài)數(shù)與動作數(shù)相等的情況以及狀態(tài)數(shù)相同、動作數(shù)增加的兩組對比試驗(yàn)，我們可以得到以下結(jié)論：1）通過LEC算法求解最小權(quán)值強(qiáng)規(guī)劃解減少了時(shí)間代價(jià)；2）LEC算法加入不確定因素，更滿足實(shí)際情況，加入后隨著動作數(shù)的增加，時(shí)間代價(jià)增加較緩，這是因?yàn)椴淮_定規(guī)劃下不確定的動作增加使得要求的最小期望權(quán)值更明確，從而能在眾多的動作下選擇最小期望權(quán)值的強(qiáng)規(guī)劃解。

6 結(jié)語

針對不確定規(guī)劃問題，本文設(shè)計(jì)了LEC算法。該算法通過將不確定規(guī)劃問題中的目標(biāo)狀態(tài)集并入已搜索狀態(tài)集，然后通過反向搜索各狀態(tài)到達(dá)目標(biāo)狀態(tài)的最小期望權(quán)值強(qiáng)規(guī)劃解，直到求出初始所有的狀態(tài)的最小期望權(quán)值強(qiáng)規(guī)劃解，停止搜索。實(shí)驗(yàn)結(jié)果表明，使用本文設(shè)計(jì)求強(qiáng)規(guī)劃解算法，可以求出最小期望權(quán)值強(qiáng)規(guī)劃解，從而驗(yàn)證了算法的正確性，同時(shí)在符合實(shí)際條件下，該算法規(guī)避了許多不確定的動作數(shù)，算法效率更高。今后可以從以下方面進(jìn)行研究：

1）將求解最小期望權(quán)值強(qiáng)規(guī)劃解的思想應(yīng)用到多Agent規(guī)劃領(lǐng)域；2）改進(jìn)本文所設(shè)計(jì)的算法，用于求解最小期望權(quán)值弱規(guī)劃解；3）將狀態(tài)分層與本文所設(shè)計(jì)方法相結(jié)合，進(jìn)一步提升強(qiáng)規(guī)劃解求解的速度與精度。

［1］ Ghallab M，Nau D，Traverso P.Automated Planning The-ory and Practice［M］.［S.l.］：Massachusetts：Morgan Kaufmann Publishers，2004：1101-1132.

［2］丁德路，姜云飛.智能規(guī)劃及其應(yīng)用的研究［J］.計(jì)算機(jī)科學(xué)，2002，29（2）：100-103.DING Delu，JIANG Yunfei.Intelligent Planning and its Application［J］.Journal of computer sci-ence，2002，29（2）：100-103.

［3］Kuter U，Nau D，Reisner，et al.Using Classical Planners to Solve Nondeterministic Planning Problems［C］//Proc.of the 18th IntConf on Automated Planning and Sched-uling.Menlo Park，CA：AAAI press，2008：190-197.

［4］M.Ghallab，D.Nau，P.Traverso.Automated Planning：Therory and Practice［M］.Handbook of Knowledge Representation，2004.

［5］饒東寧，蔣志華，姜云飛，等.對不確定規(guī)劃中觀察約見的進(jìn)一步研究［J］.軟件學(xué)報(bào)，2009，20（5）：1254-1268.RAO Dongning，JIANG Zhihua，JIANG Yunfei，et al.Further Research on Observation Reduction in Non-Deterministic Planning［J］.Journal of software，2009，20（5）：1254-1268.

［6］Cimatti A，Roveri M，Traverso P.Strong planning in nondeterministic domains via model check-ing［C］//Proceedings of the 4th International Conference on Artificial Intelligence Planning Sys-tems（AIPS’98）.USA：Carnegie Mellon Univer-sity，1998：36-43.

［7］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-84.

［8］Fu J，Bastani F B，et al.Simple and fast strong cyclic planning for fully-observable nondeterministic planning problems［C］//IJCAI Proceedings-International Joint Conference on Artificial Intelligence.2011：1949-1954.

［9］周俊萍，殷明浩，谷文祥，等.部分可觀察強(qiáng)規(guī)劃中約減觀察變量的研究［J］.軟件學(xué)報(bào)，2009，20（2）：290-304.ZHOU Junping，YIN Minghao，GU Wenxiang，et al.Research on Decreasing Observation Varaiable for Strong Planning underPartialObservation ［J］.Journalof soft-ware，2009，20（2）：290-304.

［10］Bertoli P，Cimatti A，Roveri M，et al.Strong planning un-der partial observability［J］.Artificial Intelligence，2006，170（4/5）：337-384.

［11］陳建林，文中華，朱江，等.正向搜索方法求強(qiáng)規(guī)劃解［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（6）：52-54.CHEN Jianlin，WEN Zhonghua，ZHU Jiang，et al.Strong planning solution via forward search［J］.Computer Engi-neeringand Applications，2011，47（6）：52-54.

［12］伍小輝，文中華，李洋，等.分層法求最小權(quán)值強(qiáng)規(guī)劃解［J］.計(jì)算機(jī)科學(xué)，2015，42（2）：228-232.WU Xiaohui，WEN Zhonghua，LI Yang，et al.Solving Minimal Cost Strong Planning Solution by Hierarchical Algorithm［J］.Computer Science，2015，42（2）：228-232.

［13］陳建林，文中華，馬麗麗，等.一種求解最小權(quán)值強(qiáng)規(guī)劃的方法［J］.計(jì)算機(jī)工程，2011，37（17）：167-171.CHEN Jianlin，WEN Zhonghua，MA Lili，et al.Method of Solution Minimal Cost Strong Planning［J］.Computer Engineering，2011，37（17）：167-171.

［14］李洋，文中華，伍小輝，等.求最小期望權(quán)值強(qiáng)循環(huán)規(guī)劃解［J］.計(jì)算機(jī)科學(xué)，2015，04：217-220，257.LI Yang，WEN Zhonghua，WU Xiaohui，et al.Solving Strong Cyclic Planning with Minimal Expectation Weight［J］.Journal of computer science，2015，04：217-220，257.