不確定規(guī)劃中的多Agent帶權(quán)值強(qiáng)規(guī)化算法

伍小輝,文中華,李 洋,勞佳琪

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

不確定規(guī)劃中的多Agent帶權(quán)值強(qiáng)規(guī)化算法

伍小輝,文中華,李 洋,勞佳琪

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

在智能規(guī)劃領(lǐng)域中,以往對(duì)不確定規(guī)劃問(wèn)題的研究主要集中于單個(gè)Agent,而對(duì)多Agent規(guī)劃的研究則側(cè)重于確定規(guī)劃。針對(duì)該問(wèn)題,提出基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題,對(duì)所求解的強(qiáng)規(guī)劃解,設(shè)計(jì)使其所需動(dòng)作權(quán)值總和近似最小的算法。根據(jù)基于模型檢測(cè)的強(qiáng)規(guī)劃分層方法,對(duì)每個(gè)Agent進(jìn)行強(qiáng)規(guī)劃分層,合并所有Agent的分層信息,并在合并的過(guò)程中得到同層狀態(tài)之間的沖突表。在保證沖突最小的情況下,以最小動(dòng)作權(quán)值優(yōu)先的貪心方法,求出強(qiáng)規(guī)劃解。實(shí)驗(yàn)結(jié)果表明,該算法能較快地求解出使所選擇的動(dòng)作權(quán)值總和近似最小的強(qiáng)規(guī)劃解。

多Agent規(guī)劃;不確定規(guī)劃;強(qiáng)規(guī)劃解;模型檢測(cè);動(dòng)作權(quán)值;智能規(guī)劃

1 概述

智能規(guī)劃[1]是人工智能研究領(lǐng)域的一個(gè)重要分支,多Agent規(guī)劃[2]包含多個(gè)Agent的規(guī)劃問(wèn)題[3-4]。不確定規(guī)劃[5-6]和多Agent規(guī)劃在近年的IJCAI和AAAI中都有專門的會(huì)議。

以往對(duì)于不確定規(guī)劃的研究主要側(cè)重于單個(gè)Agent,而對(duì)于多Agent規(guī)劃的研究又著重于確定規(guī)劃。因?yàn)閷?shí)際的規(guī)劃問(wèn)題存在很多不確定因素,所以今后的多Agent規(guī)劃研究必然會(huì)考慮不確定動(dòng)作;而單個(gè)Agent的不確定規(guī)劃其實(shí)是基于多Agent的不確定規(guī)劃問(wèn)題的一個(gè)特例(即Agent數(shù)目為1)。眾所周知,多Agent規(guī)劃和不確定規(guī)劃都是當(dāng)今非常熱的研究領(lǐng)域,具有很重要的理論和應(yīng)用價(jià)值,所以在基于多Agent的不確定規(guī)劃問(wèn)題上的研究工作是非常有意義的。

文獻(xiàn)[7]最先提出了強(qiáng)規(guī)劃解的概念。文獻(xiàn)[8]又給出了有關(guān)弱規(guī)劃解、強(qiáng)規(guī)劃解和強(qiáng)循環(huán)規(guī)劃解的完整定義和說(shuō)明。一直以來(lái),求強(qiáng)規(guī)劃解都是不確定規(guī)劃研究中的熱點(diǎn),因?yàn)橄鄬?duì)于弱規(guī)劃解和強(qiáng)循環(huán)規(guī)劃解[9]而言,強(qiáng)規(guī)劃解更具有理論和應(yīng)用價(jià)值。另外,以往對(duì)于規(guī)劃的研究主要側(cè)重于規(guī)劃解本身,但是考慮到現(xiàn)實(shí)世界中,每個(gè)動(dòng)作的執(zhí)行都是有耗費(fèi)的,文獻(xiàn)[10]在不確定規(guī)劃中考慮了動(dòng)作耗費(fèi)的問(wèn)題,并將其稱作動(dòng)作權(quán)值。

本文將多Agent規(guī)劃和不確定規(guī)劃的研究相結(jié)合,引入動(dòng)作權(quán)值的概念,在不確定規(guī)劃中提出基于多Agent的帶權(quán)值問(wèn)題,并設(shè)計(jì)了求解強(qiáng)規(guī)劃解的算法,且該算法使所求得的強(qiáng)規(guī)劃解所需的動(dòng)作權(quán)值總和近似最小。

2 相關(guān)定義

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

γ用來(lái)表示不確定性,γ=(s,a)表示狀態(tài)s執(zhí)行動(dòng)作a所得到的狀態(tài)集合;若γ=(s,a)非空,則稱動(dòng)作a在狀態(tài)s下是可執(zhí)行的。在狀態(tài)s下可執(zhí)行的動(dòng)作集合記作A(s)={a:?s′∈γ(s,a)};其中,稱s′是s可達(dá)的,稱(s,a)為狀態(tài)動(dòng)作序偶;且至多存在一個(gè)動(dòng)作a,使得s′是s可達(dá)的。

定義2(不確定規(guī)劃問(wèn)題) 不確定規(guī)劃問(wèn)題P=＜Σ,I,G＞。其中,Σ是不確定規(guī)劃領(lǐng)域;I?S是初始狀態(tài)集合;G?S是目標(biāo)狀態(tài)集合。

定義3(不確定規(guī)劃的執(zhí)行結(jié)構(gòu)) 不確定規(guī)劃的執(zhí)行結(jié)構(gòu)K=＜Q,T＞。其中,Q?S和T?S×S是滿足以下條件的最小集合:

(1)若s∈S,那么s∈Q,并且滿足(2);

(2)若s∈Q且存在某個(gè)動(dòng)作a使得(s,a)∈π,那么對(duì)所有的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(不確定規(guī)劃的規(guī)劃解) 設(shè)Σ=＜S,A, γ＞是一個(gè)不確定規(guī)劃領(lǐng)域,P=＜Σ,I,G＞是Σ上的一個(gè)不確定規(guī)劃問(wèn)題,π是不確定規(guī)劃領(lǐng)域Σ中的一個(gè)狀態(tài)動(dòng)作序偶表,K=＜Q,T＞是π從S導(dǎo)出的執(zhí)行結(jié)構(gòu)。

(1)π是P的弱規(guī)劃解當(dāng)且僅當(dāng)(?s∈I) (?s′∈G∩Sterminal(K)),其中s′是s可達(dá)的。

(2)π 是P的強(qiáng)循環(huán)規(guī)劃解當(dāng)且僅當(dāng)Sterminal(K)?G,且(?s∈Q)(?s′∈Sterminal(K)),其中s′是s可達(dá)的。

(3)π是P的強(qiáng)規(guī)劃解當(dāng)且僅當(dāng)K是無(wú)環(huán)的,且Sterminal(K)?G。

若P有強(qiáng)規(guī)劃解,則稱可以從初始狀態(tài)強(qiáng)到達(dá)目標(biāo)狀態(tài)。

定義5(基于多Agent的帶權(quán)值不確定規(guī)劃領(lǐng)域) 基于多Agent的帶權(quán)值不確定規(guī)劃領(lǐng)域D=＜n,Σi=1,2,…,n,m,Wj=1,2,…,m＞。 其中,n表示 Agent的數(shù)目;Σi表示Agenti的不確定規(guī)劃領(lǐng)域;m表示動(dòng)作的數(shù)目;Wj表示執(zhí)行動(dòng)作aj需要耗費(fèi)的權(quán)值。

定義6(基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題) 基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題Ψ=＜D,n,Pi=1,2,…,n,S0,Sg＞。 其中,D表示基于多Agent的帶權(quán)值不確定規(guī)劃領(lǐng)域;n表示Agent的數(shù)目;Pi表示Agenti的不確定規(guī)劃問(wèn)題;S0?S是基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題的初始狀態(tài)集合;Sg?S是基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題的目標(biāo)狀態(tài)集合。

定義7(基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題的強(qiáng)規(guī)劃解) 設(shè)D=＜n,Σi=1,2,…,n,m,Wj=1,2,…,m＞是一個(gè)基于多Agent的帶權(quán)值不確定規(guī)劃領(lǐng)域,Ψ=＜D,n,Pi=1,2,…,n,S0,Sg＞是D上的一個(gè)基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題;那么在Ψ上的強(qiáng)規(guī)劃解 Π =(n,πi=1,2,…,n,wi=1,2,…,n),其中,n表示Agent的數(shù)目;πi表示Agenti在Pi上的強(qiáng)規(guī)劃解;wi表示Agenti在Pi上的近似最小動(dòng)作耗費(fèi)值?；诙郃gent的帶權(quán)值不確定規(guī)劃問(wèn)題的強(qiáng)規(guī)劃解Π保證任意一個(gè)Agent在執(zhí)行對(duì)應(yīng)的動(dòng)作序列的過(guò)程中不會(huì)出現(xiàn)沖突情況,并且能使每個(gè)Agent都能強(qiáng)到達(dá)自己的目標(biāo)狀態(tài)(所有Agent是在同一時(shí)間執(zhí)行動(dòng)作,沒(méi)有先后順序)。

圖1是一個(gè)基于多Agent的帶權(quán)值不確定規(guī)劃領(lǐng)域D,其中,動(dòng)作ai后面括號(hào)中的數(shù)值是執(zhí)行該動(dòng)作需要耗費(fèi)的權(quán)值,如a1(2)表示執(zhí)行動(dòng)作a1需要耗費(fèi)的權(quán)值為2。

圖1 基于多Agent的帶權(quán)值不確定規(guī)劃

假設(shè)在D上有一個(gè)基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題Ψ=＜D,2,P1,2,S0,Sg＞。其中,P1=＜Σ1,I1,G1＞;P2=＜Σ2,I2,G2＞,且 Σ1=Σ2;I1={s1,s2};G1={s7,s8};I2={s2};G2={s8};S0={s1,s2};Sg={s7,s8}。

那么求得的解為 Π =(2,π1,2,w1,2)。其中, π1={(s1,a1),(s3,a7),(s4,a8)};w1=7;π2={(s2,a3),(s6,a6),(s5,a9)},w2=13。

3 SPSMNPW算法

本文提出求解基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題的強(qiáng)規(guī)劃解的算法(Strong Planning Solution for Multi-agent Nondeterministic Planning with Weight,SPSMNPW)。

3.1 算法思想

算法首先使用基于模型檢測(cè)的強(qiáng)規(guī)劃分層方法[11-12],對(duì)每個(gè)Agent進(jìn)行分層。由定義7可知,基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題的強(qiáng)規(guī)劃解保證了每個(gè)Agent都有強(qiáng)規(guī)劃解;于是在單個(gè)Agent強(qiáng)規(guī)劃分層的時(shí)候,如果某個(gè)Agent分層失敗,即可判斷該規(guī)劃問(wèn)題沒(méi)有規(guī)劃解。它可以迅速排除那些因單個(gè)Agent無(wú)強(qiáng)規(guī)劃解而導(dǎo)致整個(gè)規(guī)劃問(wèn)題沒(méi)有強(qiáng)規(guī)劃解的規(guī)劃問(wèn)題,從而減少了搜索時(shí)間;在Agent個(gè)數(shù)和狀態(tài)數(shù)很大時(shí),優(yōu)化效果非常明顯。

在得到每個(gè)Agent的強(qiáng)規(guī)劃分層后,根據(jù)整個(gè)規(guī)劃問(wèn)題的初始狀態(tài)集合動(dòng)態(tài)的合并分層,并在合并分層的過(guò)程中求得每一層每個(gè)狀態(tài)的沖突表?？梢允褂盟阉魉惴ǖ玫剿械膹?qiáng)規(guī)劃解,然后從中選出動(dòng)作權(quán)值總和最小的解;但是求解的時(shí)間復(fù)雜度太高。所以本文利用沖突表,在保證動(dòng)作所到達(dá)狀態(tài)的沖突最小的情況下,以最小動(dòng)作權(quán)值優(yōu)先的貪心算法,可以快速求解出強(qiáng)規(guī)劃解,且所求得的強(qiáng)規(guī)劃解的動(dòng)作權(quán)值總和近似最小。如果求解的過(guò)程中遇到?jīng)_突,則使用后文的Solve-Conflicting()函數(shù)來(lái)處理沖突。

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

SPSMNPW算法的主要流程如下:

第2行～第6行是根據(jù)模型檢測(cè)中的強(qiáng)規(guī)劃分層方法對(duì)每個(gè)Agent進(jìn)行分層;如果某個(gè)Agent分層失敗,說(shuō)明該Agent沒(méi)有強(qiáng)規(guī)劃解,而基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題的強(qiáng)規(guī)劃解要求每個(gè)Agent都要有強(qiáng)規(guī)劃解,所以可以直接判斷這個(gè)規(guī)劃問(wèn)題沒(méi)有強(qiáng)規(guī)劃解,于是返回noSPSolution。

第7行是執(zhí)行多Agent強(qiáng)規(guī)劃函數(shù),并返回強(qiáng)規(guī)劃解的狀態(tài)動(dòng)作序偶表和得到該規(guī)劃解所需的動(dòng)作權(quán)值總和。

單個(gè)Agent的分層算法流程如下:

第3行是將AgentInfo[i]的目標(biāo)狀態(tài)集合作為第1層。

第4行～第9行是對(duì)AgentInfo[i]進(jìn)行分層。如果上一次分層為空,則跳出while()循環(huán),返回false。否則,繼續(xù)執(zhí)行while()循環(huán)結(jié)構(gòu)中的程序;若初始狀態(tài)集合中還有元素尚未包含于singleH[i]分層中時(shí),則使用函數(shù)Sel_NL()來(lái)選擇下一層的狀態(tài)加入singleH[i][++layer]中;若初始狀態(tài)集合中的元素全部包含于singleH[i]分層中,則返回true。

強(qiáng)規(guī)劃算法流程如下:

第2行的函數(shù)是根據(jù)多Agent不確定規(guī)劃的初始狀態(tài)集合S0和目標(biāo)狀態(tài)集合Sg,將所有Agent的單個(gè)分層singleH進(jìn)行合并。首先把S0中的元素作為wholeH的第1層;然后搜索wholeH第1層中的元素在singleH中可達(dá)的狀態(tài),加入wholeH的第2層;如此類推,搜索wholeH第i層中的元素在singleH中可達(dá)的狀態(tài),加入wholeH的第i+1層,直到所有狀態(tài)到達(dá)目標(biāo)狀態(tài)集合Sg。這種動(dòng)態(tài)合并的算法可以去除不必要的狀態(tài),且在合并的過(guò)程中可以求得wholeH中每一層每個(gè)狀態(tài)的沖突表confSet。

第3行～第6行是從AgentInfo[1]的第1層開(kāi)始,當(dāng)sA有效時(shí),在while()循環(huán)中執(zhí)行SPS-Search()函數(shù),搜索滿足條件的強(qiáng)規(guī)劃解。

第7行～第10行判斷是否所有的Agent都找到了強(qiáng)規(guī)劃解。如果存在Agent沒(méi)有找到強(qiáng)規(guī)劃解,則返回false;否則,返回強(qiáng)規(guī)劃解的狀態(tài)序偶表π和得到該強(qiáng)規(guī)劃解所需的動(dòng)作權(quán)值之和w。

強(qiáng)規(guī)劃解搜索算法流程如下:

第3行是當(dāng)搜索的層數(shù)小于1時(shí),搜索無(wú)效,返回。

第4行～第6行是當(dāng)AgentInfo[i]到達(dá)目標(biāo)狀態(tài)時(shí),則調(diào)用Get_Next_Agent(sA)函數(shù)。Get_Next_Agent(sA)函數(shù)返回下一次搜索的Agent和搜索的層數(shù);當(dāng)i等于n時(shí),下一次搜索的Agent為1,搜索的層數(shù)為j+1;當(dāng)i不等于n時(shí),下一次搜索的Agent為i+1,搜索層數(shù)不變。

第7行 ～第29行是判斷AgentInfo[i][j]的sourceStatus集合中的每個(gè)狀態(tài)是否都能到達(dá)下一層。第9行的Priority_Action_Seq()函數(shù)是利用沖突表confSet,在沖突最小的情況下,以最小代價(jià)優(yōu)先的貪心算法搜索得到狀態(tài)s的動(dòng)作集合actionSet。第10行～第21行是判斷actionSet中是否存在動(dòng)作a能強(qiáng)到達(dá)下一層;若存在,則更新相關(guān)的值,并置noConflictFlag為true,跳出循環(huán)。如果不存在,則執(zhí)行第22行～第28行。其中,在第23行中判斷此次搜索是否來(lái)自Solve-Conflicting()函數(shù)的調(diào)用;若是,返回?zé)o效的sA;否則,執(zhí)行第25行,調(diào)用Solve-Conflicting()函數(shù),處理沖突。在第27行中,當(dāng)判斷sA.layer≠sA′.layer時(shí),說(shuō)明處理沖突失敗,返回sA′;否則,繼續(xù)執(zhí)行for循環(huán)。

第30行 ～第31行是搜索成功,更新記錄該Agent信息的數(shù)組AgentInfo,并返回下一次搜索的Agent和搜索的層數(shù)。

處理沖突算法流程如下:

第2行對(duì)AgentInfo和Flag進(jìn)行備份,沖突解決不了時(shí)可以恢復(fù)數(shù)據(jù),避免數(shù)據(jù)修改之后無(wú)法恢復(fù)。

第3行 ～第13行是處理沖突的具體實(shí)現(xiàn)。第3行是從actionSet中選出一個(gè)動(dòng)作a。第4行是判斷當(dāng)AgentInfo[index]選擇動(dòng)作a以后,從動(dòng)作a所能到達(dá)的所有狀態(tài)中選擇一個(gè)狀態(tài)sj。第5行的GetConflictingAgent(sj)函數(shù)是找出在狀態(tài)sj上造成沖突的Agent集合agentT。第6行～第8行是對(duì)集合AgentT中的任意元素Ai,判斷使用SPS-Search(sA′=(Ai,layer))函數(shù)是否能夠解決沖突;如果存在某個(gè)Agent無(wú)法解決沖突,則跳出循環(huán)。第10行是如果動(dòng)作a在layer+1層所能到達(dá)的所有狀態(tài)sj都能解決沖突,則跳出循環(huán)去執(zhí)行第18行并返回sA。

第14行～第18行是當(dāng)無(wú)法解決沖突時(shí),恢復(fù)AgentInfo和Flag的值;并將layer-1,然后返回sA;也就是搜索AgentInfo[index]的上一層來(lái)解決沖突。

3.3 算法分析

3.3.1 復(fù)雜度分析

該算法的時(shí)間耗費(fèi)主要包括3個(gè)方面:Agent分層,分層合并;強(qiáng)規(guī)劃解搜索。設(shè)Agent數(shù)為n,狀態(tài)集大小為sn,動(dòng)作集大小為m。

通過(guò)分析上文的算法可知,Agent分層的最壞時(shí)間復(fù)雜度為O(sn2);分層合并的最壞時(shí)間復(fù)雜度為O(n×sn×m);強(qiáng)規(guī)劃解搜索的最壞時(shí)間復(fù)雜度為O(n×sn2×m)。顯然,SPSMNPW算法的時(shí)間復(fù)雜度為O(n×sn2×m)。

設(shè)x=max{sn,m},則算法的空間復(fù)雜度為O(n×sn×x)。

3.3.2 算法正確性證明

定理1基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題有強(qiáng)規(guī)劃解的必要條件是每個(gè)Agent的強(qiáng)規(guī)劃分層成功。

證明:由定義7可知,基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題的強(qiáng)規(guī)劃解要求每個(gè)Agent都有強(qiáng)規(guī)劃解;又根據(jù)文獻(xiàn)[12]的定理1可以證明,Agent有強(qiáng)規(guī)劃解的充分必要條件是它的強(qiáng)規(guī)劃分層成功。

所以每個(gè)Agent的強(qiáng)規(guī)劃分層成功是基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題有強(qiáng)規(guī)劃解的必要條件。

定理2強(qiáng)規(guī)劃算法Multi-Agent-SP()是正確的。

證明:強(qiáng)規(guī)劃算法能夠判斷一個(gè)基于多Agent的帶權(quán)值的不確定規(guī)劃問(wèn)題是否有強(qiáng)規(guī)劃解,因?yàn)樵撍惴ǖ慕K止只有2種情況:(1)每個(gè)Agent在不沖突的情況下都能求得強(qiáng)規(guī)劃解;(2)Agent之間因?yàn)闆_突無(wú)法解決,最終逆向收斂于第1層。

而在狀態(tài)轉(zhuǎn)移時(shí),每個(gè)狀態(tài)只會(huì)出現(xiàn)下面3種情況:(1)狀態(tài)通過(guò)執(zhí)行相應(yīng)動(dòng)作可以順利轉(zhuǎn)移到下一層;(2)狀態(tài)轉(zhuǎn)移到下一層時(shí)會(huì)造成沖突,但是最終可以解決沖突;(3)狀態(tài)轉(zhuǎn)移到下一層時(shí)會(huì)造成沖突,且沖突無(wú)法解決,從而返回上一層解決沖突。

從上面的分析可知,如果狀態(tài)出現(xiàn)第(1)種、第(2)種情況,則可以轉(zhuǎn)移到下一層,且當(dāng)所到達(dá)的下一層狀態(tài)是終止?fàn)顟B(tài)時(shí),該狀態(tài)的搜索結(jié)束;如果從初始狀態(tài)擴(kuò)展的所有狀態(tài)都最終到達(dá)終止?fàn)顟B(tài),則找到強(qiáng)規(guī)劃解,結(jié)束。

如果狀態(tài)出現(xiàn)第(3)種情況,則返回上一層,并記錄上一次搜索結(jié)果;然后重新搜索與之前所記錄結(jié)果不同的搜索結(jié)果;如果存在,則轉(zhuǎn)移到下一層繼續(xù)搜索;否則,再返回上一層解決沖突。如此循環(huán),最終要么沖突解決,搜索得到強(qiáng)規(guī)劃解;要么返回到第1層,且無(wú)法解決沖突,可判斷該問(wèn)題無(wú)強(qiáng)規(guī)劃解。

據(jù)上述分析可證明算法Multi-Agent-SP()是正確的。

算法SPSMNPW是由定理1和定理2的結(jié)論組成的,所以可以證明算法SPSMNPW是正確的。

4 實(shí)驗(yàn)結(jié)果及分析

根據(jù)本文提出的算法SPSMNPW設(shè)計(jì)實(shí)驗(yàn),可以較快求出基于多Agent的不確定規(guī)劃問(wèn)題強(qiáng)規(guī)劃解,且所需的動(dòng)作權(quán)值之和近似最小。通過(guò)實(shí)驗(yàn)證明了該算法的正確性和有效性。

本文設(shè)計(jì)了一個(gè)隨機(jī)算法,首先使用srand(time(0))避免偽隨機(jī);然后設(shè)定Agent和狀態(tài)數(shù);再使用rand()函數(shù)隨機(jī)生成測(cè)試所需的初始狀態(tài)集、目標(biāo)狀態(tài)集、動(dòng)作集等相關(guān)數(shù)據(jù);且為了更為客觀精確地測(cè)試算法的效率,動(dòng)作所關(guān)聯(lián)的狀態(tài)編號(hào)和狀態(tài)個(gè)數(shù)也用rand()函數(shù)隨機(jī)生成。通過(guò)該算法生成了1 000組在Agent個(gè)數(shù)為2,4,6,8,10,狀態(tài)數(shù)為50,70,90,110, 130,150時(shí)的樣例。使用SPSMNPW算法編寫的程序在這1 000組樣例上分別執(zhí)行10次的平均時(shí)間如表1所示。

表1 1 000組樣例的平均執(zhí)行時(shí)間 s

通過(guò)觀察實(shí)驗(yàn)數(shù)據(jù),發(fā)現(xiàn)實(shí)驗(yàn)結(jié)果與預(yù)期存在差異。實(shí)驗(yàn)預(yù)期應(yīng)該是:橫向比較時(shí),隨著Agent個(gè)數(shù)的增加,沖突的概率增大,處理沖突會(huì)耗費(fèi)更多的時(shí)間,所以運(yùn)行時(shí)間會(huì)逐漸增長(zhǎng);縱向比較時(shí),隨著狀態(tài)數(shù)的增加,Agent需要判斷的狀態(tài)數(shù)增加,分層的層數(shù)也會(huì)增加,運(yùn)行時(shí)間也會(huì)逐漸增長(zhǎng)。

通過(guò)進(jìn)一步研究和分析,發(fā)現(xiàn)隨著Agent的個(gè)數(shù)和狀態(tài)數(shù)的增加,找不到規(guī)劃解的概率也會(huì)增大,當(dāng)超過(guò)某一數(shù)值時(shí),這種增長(zhǎng)會(huì)非常迅速。而在SPSMNPW算法中可以通過(guò)執(zhí)行單個(gè)Agent分層算法去掉那些因單個(gè)Agent無(wú)強(qiáng)規(guī)劃解而導(dǎo)致整個(gè)多Agent不確定規(guī)劃領(lǐng)域無(wú)強(qiáng)規(guī)劃解的樣例。此外, Multi-Agent-SP算法中也優(yōu)化了因?yàn)闊o(wú)法解決沖突而提前結(jié)束搜索的情況。

為驗(yàn)證上述分析的正確性,本文再次設(shè)計(jì)了實(shí)驗(yàn)。首先根據(jù)SPSMNPW算法,在Agent個(gè)數(shù)為2, 4,6,8,10,狀態(tài)數(shù)為50,70,90,110,130,150時(shí),分別找出100組可以找到強(qiáng)規(guī)劃解的樣例。再次使用SPSMNPW算法在這100組樣例上分別執(zhí)行10次,所需的平均時(shí)間如表2所示。

表2 1 00組樣例的平均執(zhí)行時(shí)間 s

通過(guò)表2,可以驗(yàn)證之前對(duì)于表1結(jié)果不符合預(yù)期的分析是正確的。表2的結(jié)果顯示,隨著Agent的個(gè)數(shù)增加,運(yùn)行時(shí)間增長(zhǎng);隨著狀態(tài)數(shù)的增加,時(shí)間也增長(zhǎng);實(shí)驗(yàn)結(jié)果符合預(yù)期。

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

針對(duì)基于多Agent的帶權(quán)值不確定規(guī)劃問(wèn)題,本文設(shè)計(jì)了一個(gè)求強(qiáng)規(guī)劃解的算法。該算法使用了基于模型檢測(cè)的強(qiáng)規(guī)劃分層法,可以快速解決因單個(gè)Agent無(wú)強(qiáng)規(guī)劃解而導(dǎo)致的在整個(gè)規(guī)劃領(lǐng)域無(wú)強(qiáng)規(guī)劃解的問(wèn)題,從而減少搜索,達(dá)到優(yōu)化的目的。此外,在搜索過(guò)程中,使用沖突表confSet進(jìn)行優(yōu)化,盡可能避免沖突。另外,因?yàn)槭褂昧艘宰钚?dòng)作權(quán)值優(yōu)先的貪心算法,所以使問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)解決,且最終求得的強(qiáng)規(guī)劃解所需的動(dòng)作權(quán)值之和近似最小。實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。

今后還可以從以下2個(gè)方面進(jìn)行研究:(1)求解多Agent不確定規(guī)劃領(lǐng)域的強(qiáng)循環(huán)規(guī)劃解和弱規(guī)劃解;以及最小動(dòng)作權(quán)值的強(qiáng)循環(huán)規(guī)劃解和弱規(guī)劃解。(2)在全可觀察和部分可觀察條件下,對(duì)多Agent不確定規(guī)劃領(lǐng)域上的觀測(cè)信息進(jìn)行約簡(jiǎn)。

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

[2] Weiss G.Multiagent Systems:A Modern Approach to Distributed Artificial Intelligence[M].[S.l.]:MIT Press,1999.

[3] Yang Qiang,Wu Kangheng,Jiang Yunfei.Learning Action Models from Plan Examples Using Weighted Max-SAT[J].Artificial Intelligence,2007,171(2/3): 107-143.

[4] Gil Y.Description Logics and Planning[J].AI Magazine,2005,26(2):73-84.

[5] 饒東寧,蔣志華,姜云飛,等.對(duì)不確定規(guī)劃中觀察約簡(jiǎn)的進(jìn)一步研究[J].軟件學(xué)報(bào),2009,20(5): 1254-1268.

[6] Cimatti A,Roveri M,Traverso P.Automatic OBDD-based Generation of Universal Plans in Nondeterministic Domains[C]//Proceedings of the 15th National Conference on Artificial Intelligence.Madison,USA:[s.n.], 1998:875-881.

[7] Cimatti A,Roveri M,Traverso P.Strong Planning in Nondeterministic Domains via Model Checking[C]// Proceedings of the 4th International Conference on Artficial Intelligence Planning Systems. Pittsburgh, USA:[s.n.],1998:36-43.

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

[9] Fu Jicheng,Ng V,Bastani F B,et al.Simple and Fast Strong Cyclic Planning for Fully-observable Nondeterministic Planning Problems[C]//Proceedings of the 22nd International Joint Conference on Artificial Intelligence.Barcelona,Spain:[s.n.],2011:1949-1954.

[10] 陳建林,文中華,馬麗麗,等.一種求解最小權(quán)值強(qiáng)規(guī)劃的方法[J].計(jì)算機(jī)工程,2011,37(17):167-171.

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

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

編輯 顧逸斐

Multi-Agent Strong Planning Algorithm with Weight in Nondeterministic Planning

WU Xiaohui,WEN Zhonghua,LI Yang,LAO Jiaqi
(College of Information Engineering,Xiangtan University,Xiangtan 411105,China)

In the field of intelligent planning study,previous studies of nondeterministic planning focus on a single Agent,and research on multi-Agent planning focuses on determining planning.To solve this problem,this paper presents the cost strong planning problem in multi-Agent nondeterministic planning domain,and designs the strong planning algorithm to solve strong planning solution with approximate minimum sum of action cost.Based on model checking of strong hierarchical planning methods to make strong hierarchical planning for each Agent,it merges all Agent’s hierarchical information,and gets the conflicting table of the same level between states in the process of merging at the same time.Under guaranteeing minimum conflicting,this paper uses greedy method for minimum action cost priority to solve a strong planning solution.Experimental results show that the algorithm not only can solve strong planning solution with approximate minimum sum of action cost,but also runs quickly.

multi-Agent planning;nondeterministic planning;strong planning solution;model checking;action weight; intelligent planning

1000-3428(2015)01-0190-06

A

TP301.6

10.3969/j.issn.1000-3428.2015.01.035

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

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

2013-12-23

2014-03-06 E-mail:510280596@qq.com

中文引用格式:伍小輝,文中華,李 洋,等.不確定規(guī)劃中的多Agent帶權(quán)值強(qiáng)規(guī)化算法[J].計(jì)算機(jī)工程,2015, 41(1):190-195.

英文引用格式:Wu Xiaohui,Wen Zhonghua,Li Yang,et al.Multi-Agent Strong Planning Algorithm with Weight in Nondeterministic Planning[J].Computer Engineering,2015,41(1):190-195.