不確定規劃中的多Agent帶權值強規化算法

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

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

不確定規劃中的多Agent帶權值強規化算法

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

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

在智能規劃領域中,以往對不確定規劃問題的研究主要集中于單個Agent,而對多Agent規劃的研究則側重于確定規劃。針對該問題,提出基于多Agent的帶權值不確定規劃問題,對所求解的強規劃解,設計使其所需動作權值總和近似最小的算法。根據基于模型檢測的強規劃分層方法,對每個Agent進行強規劃分層,合并所有Agent的分層信息,并在合并的過程中得到同層狀態之間的沖突表。在保證沖突最小的情況下,以最小動作權值優先的貪心方法,求出強規劃解。實驗結果表明,該算法能較快地求解出使所選擇的動作權值總和近似最小的強規劃解。

多Agent規劃;不確定規劃;強規劃解;模型檢測;動作權值;智能規劃

1 概述

智能規劃[1]是人工智能研究領域的一個重要分支,多Agent規劃[2]包含多個Agent的規劃問題[3-4]。不確定規劃[5-6]和多Agent規劃在近年的IJCAI和AAAI中都有專門的會議。

以往對于不確定規劃的研究主要側重于單個Agent,而對于多Agent規劃的研究又著重于確定規劃。因為實際的規劃問題存在很多不確定因素,所以今后的多Agent規劃研究必然會考慮不確定動作;而單個Agent的不確定規劃其實是基于多Agent的不確定規劃問題的一個特例(即Agent數目為1)。眾所周知,多Agent規劃和不確定規劃都是當今非常熱的研究領域,具有很重要的理論和應用價值,所以在基于多Agent的不確定規劃問題上的研究工作是非常有意義的。

文獻[7]最先提出了強規劃解的概念。文獻[8]又給出了有關弱規劃解、強規劃解和強循環規劃解的完整定義和說明。一直以來,求強規劃解都是不確定規劃研究中的熱點,因為相對于弱規劃解和強循環規劃解[9]而言,強規劃解更具有理論和應用價值。另外,以往對于規劃的研究主要側重于規劃解本身,但是考慮到現實世界中,每個動作的執行都是有耗費的,文獻[10]在不確定規劃中考慮了動作耗費的問題,并將其稱作動作權值。

本文將多Agent規劃和不確定規劃的研究相結合,引入動作權值的概念,在不確定規劃中提出基于多Agent的帶權值問題,并設計了求解強規劃解的算法,且該算法使所求得的強規劃解所需的動作權值總和近似最小。

2 相關定義

定義1(不確定規劃領域) 不確定規劃領域Σ=＜S,A,γ＞。其中,S是一個有限狀態集;A是一個有限動作集;γ.S×A→2S是狀態轉換函數。

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

定義2(不確定規劃問題) 不確定規劃問題P=＜Σ,I,G＞。其中,Σ是不確定規劃領域;I?S是初始狀態集合;G?S是目標狀態集合。

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

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

(2)若s∈Q且存在某個動作a使得(s,a)∈π,那么對所有的s′(其中s′∈γ(s,a)),都有s′∈Q且(s,s′)∈T。

狀態s∈Q是K的一個終止狀態當且僅當不存在狀態s′∈Q,使得(s,s′)∈T。K是一個有向圖,其中,Q是在執行規劃解時能夠到達的所有狀態集合;T表示所有可能的狀態轉移。顯然,K的終止狀態代表規劃執行的終止,這里用Sterminal(K)表示執行結構K的終止狀態集。

定義4(不確定規劃的規劃解) 設Σ=＜S,A, γ＞是一個不確定規劃領域,P=＜Σ,I,G＞是Σ上的一個不確定規劃問題,π是不確定規劃領域Σ中的一個狀態動作序偶表,K=＜Q,T＞是π從S導出的執行結構。

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

(2)π 是P的強循環規劃解當且僅當Sterminal(K)?G,且(?s∈Q)(?s′∈Sterminal(K)),其中s′是s可達的。

(3)π是P的強規劃解當且僅當K是無環的,且Sterminal(K)?G。

若P有強規劃解,則稱可以從初始狀態強到達目標狀態。

定義5(基于多Agent的帶權值不確定規劃領域) 基于多Agent的帶權值不確定規劃領域D=＜n,Σi=1,2,…,n,m,Wj=1,2,…,m＞。 其中,n表示 Agent的數目;Σi表示Agenti的不確定規劃領域;m表示動作的數目;Wj表示執行動作aj需要耗費的權值。

定義6(基于多Agent的帶權值不確定規劃問題) 基于多Agent的帶權值不確定規劃問題Ψ=＜D,n,Pi=1,2,…,n,S0,Sg＞。 其中,D表示基于多Agent的帶權值不確定規劃領域;n表示Agent的數目;Pi表示Agenti的不確定規劃問題;S0?S是基于多Agent的帶權值不確定規劃問題的初始狀態集合;Sg?S是基于多Agent的帶權值不確定規劃問題的目標狀態集合。

定義7(基于多Agent的帶權值不確定規劃問題的強規劃解) 設D=＜n,Σi=1,2,…,n,m,Wj=1,2,…,m＞是一個基于多Agent的帶權值不確定規劃領域,Ψ=＜D,n,Pi=1,2,…,n,S0,Sg＞是D上的一個基于多Agent的帶權值不確定規劃問題;那么在Ψ上的強規劃解 Π =(n,πi=1,2,…,n,wi=1,2,…,n),其中,n表示Agent的數目;πi表示Agenti在Pi上的強規劃解;wi表示Agenti在Pi上的近似最小動作耗費值。基于多Agent的帶權值不確定規劃問題的強規劃解Π保證任意一個Agent在執行對應的動作序列的過程中不會出現沖突情況,并且能使每個Agent都能強到達自己的目標狀態(所有Agent是在同一時間執行動作,沒有先后順序)。

圖1是一個基于多Agent的帶權值不確定規劃領域D,其中,動作ai后面括號中的數值是執行該動作需要耗費的權值,如a1(2)表示執行動作a1需要耗費的權值為2。

圖1 基于多Agent的帶權值不確定規劃

假設在D上有一個基于多Agent的帶權值不確定規劃問題Ψ=＜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的帶權值不確定規劃問題的強規劃解的算法(Strong Planning Solution for Multi-agent Nondeterministic Planning with Weight,SPSMNPW)。

3.1 算法思想

算法首先使用基于模型檢測的強規劃分層方法[11-12],對每個Agent進行分層。由定義7可知,基于多Agent的帶權值不確定規劃問題的強規劃解保證了每個Agent都有強規劃解;于是在單個Agent強規劃分層的時候,如果某個Agent分層失敗,即可判斷該規劃問題沒有規劃解。它可以迅速排除那些因單個Agent無強規劃解而導致整個規劃問題沒有強規劃解的規劃問題,從而減少了搜索時間;在Agent個數和狀態數很大時,優化效果非常明顯。

在得到每個Agent的強規劃分層后,根據整個規劃問題的初始狀態集合動態的合并分層,并在合并分層的過程中求得每一層每個狀態的沖突表。可以使用搜索算法得到所有的強規劃解,然后從中選出動作權值總和最小的解;但是求解的時間復雜度太高。所以本文利用沖突表,在保證動作所到達狀態的沖突最小的情況下,以最小動作權值優先的貪心算法,可以快速求解出強規劃解,且所求得的強規劃解的動作權值總和近似最小。如果求解的過程中遇到沖突,則使用后文的Solve-Conflicting()函數來處理沖突。

3.2 算法實現

SPSMNPW算法的主要流程如下:

第2行～第6行是根據模型檢測中的強規劃分層方法對每個Agent進行分層;如果某個Agent分層失敗,說明該Agent沒有強規劃解,而基于多Agent的帶權值不確定規劃問題的強規劃解要求每個Agent都要有強規劃解,所以可以直接判斷這個規劃問題沒有強規劃解,于是返回noSPSolution。

第7行是執行多Agent強規劃函數,并返回強規劃解的狀態動作序偶表和得到該規劃解所需的動作權值總和。

單個Agent的分層算法流程如下:

第3行是將AgentInfo[i]的目標狀態集合作為第1層。

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

強規劃算法流程如下:

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

第3行～第6行是從AgentInfo[1]的第1層開始,當sA有效時,在while()循環中執行SPS-Search()函數,搜索滿足條件的強規劃解。

第7行～第10行判斷是否所有的Agent都找到了強規劃解。如果存在Agent沒有找到強規劃解,則返回false;否則,返回強規劃解的狀態序偶表π和得到該強規劃解所需的動作權值之和w。

強規劃解搜索算法流程如下:

第3行是當搜索的層數小于1時,搜索無效,返回。

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

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

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

處理沖突算法流程如下:

第2行對AgentInfo和Flag進行備份,沖突解決不了時可以恢復數據,避免數據修改之后無法恢復。

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

第14行～第18行是當無法解決沖突時,恢復AgentInfo和Flag的值;并將layer-1,然后返回sA;也就是搜索AgentInfo[index]的上一層來解決沖突。

3.3 算法分析

3.3.1 復雜度分析

該算法的時間耗費主要包括3個方面:Agent分層,分層合并;強規劃解搜索。設Agent數為n,狀態集大小為sn,動作集大小為m。

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

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

3.3.2 算法正確性證明

定理1基于多Agent的帶權值不確定規劃問題有強規劃解的必要條件是每個Agent的強規劃分層成功。

證明:由定義7可知,基于多Agent的帶權值不確定規劃問題的強規劃解要求每個Agent都有強規劃解;又根據文獻[12]的定理1可以證明,Agent有強規劃解的充分必要條件是它的強規劃分層成功。

所以每個Agent的強規劃分層成功是基于多Agent的帶權值不確定規劃問題有強規劃解的必要條件。

定理2強規劃算法Multi-Agent-SP()是正確的。

證明:強規劃算法能夠判斷一個基于多Agent的帶權值的不確定規劃問題是否有強規劃解,因為該算法的終止只有2種情況:(1)每個Agent在不沖突的情況下都能求得強規劃解;(2)Agent之間因為沖突無法解決,最終逆向收斂于第1層。

而在狀態轉移時,每個狀態只會出現下面3種情況:(1)狀態通過執行相應動作可以順利轉移到下一層;(2)狀態轉移到下一層時會造成沖突,但是最終可以解決沖突;(3)狀態轉移到下一層時會造成沖突,且沖突無法解決,從而返回上一層解決沖突。

從上面的分析可知,如果狀態出現第(1)種、第(2)種情況,則可以轉移到下一層,且當所到達的下一層狀態是終止狀態時,該狀態的搜索結束;如果從初始狀態擴展的所有狀態都最終到達終止狀態,則找到強規劃解,結束。

如果狀態出現第(3)種情況,則返回上一層,并記錄上一次搜索結果;然后重新搜索與之前所記錄結果不同的搜索結果;如果存在,則轉移到下一層繼續搜索;否則,再返回上一層解決沖突。如此循環,最終要么沖突解決,搜索得到強規劃解;要么返回到第1層,且無法解決沖突,可判斷該問題無強規劃解。

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

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

4 實驗結果及分析

根據本文提出的算法SPSMNPW設計實驗,可以較快求出基于多Agent的不確定規劃問題強規劃解,且所需的動作權值之和近似最小。通過實驗證明了該算法的正確性和有效性。

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

表1 1 000組樣例的平均執行時間 s

通過觀察實驗數據,發現實驗結果與預期存在差異。實驗預期應該是:橫向比較時,隨著Agent個數的增加,沖突的概率增大,處理沖突會耗費更多的時間,所以運行時間會逐漸增長;縱向比較時,隨著狀態數的增加,Agent需要判斷的狀態數增加,分層的層數也會增加,運行時間也會逐漸增長。

通過進一步研究和分析,發現隨著Agent的個數和狀態數的增加,找不到規劃解的概率也會增大,當超過某一數值時,這種增長會非常迅速。而在SPSMNPW算法中可以通過執行單個Agent分層算法去掉那些因單個Agent無強規劃解而導致整個多Agent不確定規劃領域無強規劃解的樣例。此外, Multi-Agent-SP算法中也優化了因為無法解決沖突而提前結束搜索的情況。

為驗證上述分析的正確性,本文再次設計了實驗。首先根據SPSMNPW算法,在Agent個數為2, 4,6,8,10,狀態數為50,70,90,110,130,150時,分別找出100組可以找到強規劃解的樣例。再次使用SPSMNPW算法在這100組樣例上分別執行10次,所需的平均時間如表2所示。

表2 1 00組樣例的平均執行時間 s

通過表2,可以驗證之前對于表1結果不符合預期的分析是正確的。表2的結果顯示,隨著Agent的個數增加,運行時間增長;隨著狀態數的增加,時間也增長;實驗結果符合預期。

5 結束語

針對基于多Agent的帶權值不確定規劃問題,本文設計了一個求強規劃解的算法。該算法使用了基于模型檢測的強規劃分層法,可以快速解決因單個Agent無強規劃解而導致的在整個規劃領域無強規劃解的問題,從而減少搜索,達到優化的目的。此外,在搜索過程中,使用沖突表confSet進行優化,盡可能避免沖突。另外,因為使用了以最小動作權值優先的貪心算法,所以使問題可以在多項式時間內解決,且最終求得的強規劃解所需的動作權值之和近似最小。實驗結果驗證了算法的有效性。

今后還可以從以下2個方面進行研究:(1)求解多Agent不確定規劃領域的強循環規劃解和弱規劃解;以及最小動作權值的強循環規劃解和弱規劃解。(2)在全可觀察和部分可觀察條件下,對多Agent不確定規劃領域上的觀測信息進行約簡。

[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] 饒東寧,蔣志華,姜云飛,等.對不確定規劃中觀察約簡的進一步研究[J].軟件學報,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] 陳建林,文中華,馬麗麗,等.一種求解最小權值強規劃的方法[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] 文中華,黃 巍,劉任任,等.模型檢測規劃中的狀態分層方法[J].軟件學報,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

國家自然科學基金資助項目(61070232,61272295,61105039)。

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

2013-12-23

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

中文引用格式:伍小輝,文中華,李 洋,等.不確定規劃中的多Agent帶權值強規化算法[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.