一種多agen系統(tǒng)協(xié)調(diào)協(xié)調(diào)的步進(jìn)式全局規(guī)劃模型

一種多agen系統(tǒng)協(xié)調(diào)協(xié)調(diào)的步進(jìn)式全局規(guī)劃模型

1局部規(guī)劃+增量式策略許多秋季合作和磋商是組織能夠順利完成任務(wù)的關(guān)鍵。一般總結(jié)計劃（pgp）是解決流量差異的協(xié)調(diào)機(jī)制，但假設(shè)流量代理是未經(jīng)授權(quán)的。換言之，在調(diào)整操作時，資源只有考慮整體利益，而我們通?？吹降馁Y源都是私人的，所以我們必須考慮自己的利益。針對于此,本文對PGP進(jìn)行了改進(jìn),提出了一種步進(jìn)式部分全局規(guī)劃(PPGP),并主要針對基于時間或資源限制的任務(wù)類型,其改進(jìn)如下:1)在PGP中任務(wù)管理Agent通過廣播的形式將局部規(guī)劃分配給其它Agents,然后該Agent接收到來自其它Agents的disagreement信息,而每個disagreement信息都代表該Agent自身的局部規(guī)劃與任務(wù)管理Agent的局部規(guī)劃的沖突;而在PPGP中,Agents彼此間相互通訊來發(fā)現(xiàn)沖突,各Agent是平等的,不存在一個集中管理Agent。2)在PGP中,當(dāng)探測到?jīng)_突后,在解決沖突時,各Agen必須重新開始執(zhí)行各自的局部規(guī)劃來協(xié)調(diào)沖突;而我們在PPGP中,通過丟棄產(chǎn)生沖突的最不重要Agent的非強(qiáng)制性局部規(guī)劃來加快Agents間達(dá)成協(xié)商的速度。3)在解決沖突的過程中,我們在PPGP中采用了增量式策略來協(xié)調(diào)沖突。通過以上的改進(jìn),PPGP允許新加入的Agent同原系統(tǒng)中的Agents進(jìn)行協(xié)商,而且當(dāng)插入一個新的Agent后,原系統(tǒng)中的Agents不必重新開始協(xié)商。新的Agent通過探測沖突,并在不給已達(dá)成的協(xié)商帶來新的沖突的情況下解決沖突,以便盡快達(dá)成協(xié)商。2通過各全球規(guī)劃協(xié)調(diào)機(jī)制的完善2.1局部規(guī)劃的生成Agent是多Agent系統(tǒng)的基本組成成分,每個Agent的結(jié)構(gòu)主要包括三個通信子模塊:通信接口、規(guī)劃器和協(xié)調(diào)器。Agen的邏輯結(jié)構(gòu)如圖1所示,下面介紹各通信子模塊:通信接口:通信接口用來同其它Agents進(jìn)行交互信息,Agent通過消息傳遞模式以點(diǎn)對點(diǎn)或多播的形式進(jìn)行交互;規(guī)劃器:規(guī)劃器接收來自通信接口傳來的消息。而該消息可分為兩類:一類是該Agent分配的任務(wù),即它所要實現(xiàn)的目標(biāo);另一類是其它Agents關(guān)于該Agent局部規(guī)劃的disagreemen信息。因此,處理過程中有兩個映射函數(shù):一個是規(guī)劃構(gòu)造函數(shù),該函數(shù)用來構(gòu)造規(guī)劃以達(dá)到給定目標(biāo),在構(gòu)造中采用步進(jìn)方式以使規(guī)劃細(xì)節(jié)滿足時間約束,其映射關(guān)系可表示為:另一個是沖突探測函數(shù),該函數(shù)通過分析Agents間的disagreement消息來確定已構(gòu)建的局部規(guī)劃與新的Agents局部規(guī)劃之間的沖突,其映射關(guān)系可表示為:然后,規(guī)劃器將沖突消息傳遞給協(xié)調(diào)器。協(xié)調(diào)器:通過接收規(guī)劃器傳來的沖突消息后,對所有沖突提出解決方案,其映射關(guān)系可表示為:Agents之間通過通信了解彼此的規(guī)劃并預(yù)測可能產(chǎn)生的沖突,本文中Agents間是基于消息傳遞模式來進(jìn)行通信的。Agent通信的目的主要有以下幾種:接收任務(wù)、廣播局部規(guī)劃、接收沖突信息和發(fā)出沖突解決方案。新加入的Agent通過信息交互來探測原來系統(tǒng)中Agents的協(xié)商沖突,同時,它還要解決其自身規(guī)劃與已達(dá)成的協(xié)商之間的沖突。本文中,通過放寬原系統(tǒng)中Agents以及該新加入Agent的最不重要的部分局部規(guī)劃的約束來協(xié)調(diào)沖突。下面我們建立單個Agent的形式化模型,它可表示為一個三元組:<O,A,C>。其中,O表示該Agent的操作集,A表示該Agent的屬性集,C表示該Agent所要達(dá)到目標(biāo)的約束集,即Agent的子任務(wù)集,每個子任務(wù)就是一個約束,并且子任務(wù)都是不可再分的。Agents在協(xié)商中采用優(yōu)先權(quán)原則,Agent對其每個部分局部規(guī)劃分配不同的優(yōu)先權(quán)。我們假設(shè)對于強(qiáng)制性約束的優(yōu)先權(quán)p=0,對于非強(qiáng)制性約束的優(yōu)先權(quán)設(shè)為p=1,2,…;優(yōu)先權(quán)的值越大,則該約束的重要性就越小。下面給出幾個概念:強(qiáng)制性部分局部規(guī)劃αP0={oαj∈Oα|oαj滿足約束cα,j,p(cα,j)=0};非強(qiáng)制性部分局部規(guī)劃Pαi={oαj∈Oα|oαj滿足約束cα,j,p(cα,j)=i};局部規(guī)劃αP=ki=∪0Pαi,即它是強(qiáng)制性部分局部規(guī)劃與非強(qiáng)制性部分局部規(guī)劃的并集。2.2基于局部沖突的開發(fā)當(dāng)一個部分局部規(guī)劃協(xié)商失敗,Agent將根據(jù)策略分析部分局部規(guī)劃的整體效用,來決定是否移出該部分局部規(guī)劃,Agent的策略是優(yōu)先執(zhí)行Agent的強(qiáng)制性部分局部規(guī)劃,然后是非強(qiáng)制性部分局部規(guī)劃。該策略的意圖是:確保Agent協(xié)商的最低質(zhì)量而不是去重新尋找一個新的解決方案。假設(shè)有一Agents集Ag={a1,a2,…},這些Agents已經(jīng)就它們的規(guī)劃達(dá)成了協(xié)商,這時有一個新的Agent加入,這可能將破壞已達(dá)成的協(xié)商。因此,該新加入的Agent將收集所有的沖突信息,以便解決這些沖突。下面我們首先對沖突及其類型進(jìn)行定義:定義1設(shè)有Agenta和Agentb,當(dāng)Pa與Pb不一致時,我們稱Agenta與Agentb產(chǎn)生了沖突。定義2當(dāng)新加入的Agent的強(qiáng)制性部分局部規(guī)劃與原多Agents系統(tǒng)中的某個Agent的局部規(guī)劃沖突,稱發(fā)生了硬沖突。定義3當(dāng)新加入的Agent的非強(qiáng)制性部分局部規(guī)劃與原多Agents系統(tǒng)中的某個Agent的局部規(guī)劃沖突,稱產(chǎn)生了軟沖突。定義4當(dāng)新加入的Agent的局部規(guī)劃與原多Agents系統(tǒng)中的某個Agent的強(qiáng)制性局部規(guī)劃沖突,稱產(chǎn)生了緊急沖突。定義5當(dāng)新加入的Agent的局部規(guī)劃與原多Agents系統(tǒng)中的某個Agent的非強(qiáng)制性局部規(guī)劃沖突,稱產(chǎn)生了非緊急沖突。根據(jù)以上定義,我們可以將新加入的Agent(設(shè)為AgentN)的沖突分為以下四種類型:1)硬緊急沖突:當(dāng)AgentN的強(qiáng)制性局部規(guī)劃與原多Agents系統(tǒng)中的某個Agent的強(qiáng)制性局部規(guī)劃沖突;2)硬非緊急沖突:當(dāng)AgentN的強(qiáng)制性局部規(guī)劃與原多Agents系統(tǒng)中的某個Agent的非強(qiáng)制性局部規(guī)劃沖突;3)軟緊急沖突:當(dāng)AgentN的非強(qiáng)制性局部規(guī)劃與原多Agents系統(tǒng)中的某個Agent的強(qiáng)制性局部規(guī)劃沖突;4)軟非緊急沖突:當(dāng)AgentN的非強(qiáng)制性局部規(guī)劃與原多Agents系統(tǒng)中的某個Agent的非強(qiáng)制性局部規(guī)劃沖突;Agents間通過協(xié)商來解決沖突,并用規(guī)劃的效用函數(shù)進(jìn)行衡量,通過比較效用函數(shù)的值來選擇效用函數(shù)值大的規(guī)劃。每個部分局部規(guī)劃都有其效用,這里考慮兩個方面的特性,即規(guī)劃的質(zhì)量和執(zhí)行規(guī)劃的代價,而規(guī)劃的質(zhì)量可以通過其完成規(guī)劃所獲得的獎賞來衡量。它們分別可用公式(1)～(3)表示:其中,Pai表示某個Agent的部分局部規(guī)劃,獎賞函數(shù)Reward(c)表示約束滿足時獲得的獎賞值,代價函數(shù)cost(o)表示執(zhí)行的時間。步進(jìn)式策略按如下步驟執(zhí)行:step1對沖突集進(jìn)行排序,Conflicts={硬緊急沖突,硬非緊急沖突,軟緊急沖突,軟非緊急沖突};step2if時限未到且Conflicts非空then{con=Head(Conflicts);//從沖突集中取出沖突Conflicts=Tail(Conflicts)//將新的沖突加入到?jīng)_突集中resolution(con);}//解決沖突;step3if時限已到而Conflicts非空,then拋棄Conflicts中的所有沖突;下面我們將介紹如何解決沖突:5)對硬緊急沖突:如果AgentN的強(qiáng)制性部分局部規(guī)劃的效用值大于原多Agents系統(tǒng)中的強(qiáng)制性部分局部規(guī)劃的整體效用值,AgentN將保持現(xiàn)有規(guī)劃并發(fā)出消息,這樣原多Agents系統(tǒng)中的Agents將放松對各自的部分局部規(guī)劃的約束,如果時間允許的話,它們將提出新的局部規(guī)劃,同時它們還將接收到有關(guān)AgentN的部分局部規(guī)劃時限的消息。相反,如果AgentN的強(qiáng)制性部分局部規(guī)劃的效用值小于原多Agents系統(tǒng)中的Agents的強(qiáng)制性部分局部規(guī)劃的整體效用值,則AgentN將接受這些部分局部規(guī)劃并返回接收消息,然后等待Agents的確認(rèn)消息,但必須在AgentN的強(qiáng)制性部分局部規(guī)劃最后時限之前。6)對硬非緊急沖突:AgentN將維持它的強(qiáng)制性部分局部規(guī)劃而拒絕所有的非強(qiáng)制性部分局部規(guī)劃。7)對軟緊急沖突:AgentN將放松對它非強(qiáng)制性部分局部規(guī)劃約束或違反相應(yīng)的約束。8)對軟非緊急沖突:該沖突的解決方法與硬緊急沖突的解決方法大致相同,只是它是相對于非強(qiáng)制性部分局部規(guī)劃而言,這里不再累述了。我們可以看出,該沖突解決的方法是首先解決高優(yōu)先級別的沖突,以確保最重要的部分局部規(guī)劃能在最后時限之前執(zhí)行,同時,也確保了Agents的協(xié)商效率。3各局部規(guī)劃之間的協(xié)商我們通過實驗對PGP與PPGP進(jìn)行了比較:在一個多機(jī)器人環(huán)境中,每個機(jī)器人都擁有一個基于時限的局部規(guī)劃P={p1,p2,p3,…},由于資源的不可共享性,各機(jī)器人要想在最后時限之前開始執(zhí)行其規(guī)劃,它們必須進(jìn)行協(xié)商,以避免沖突。根據(jù)PPGP,首先對各部分局部規(guī)劃賦予不同的優(yōu)先級,設(shè)p(p1)=0,p(p2)=1,p(p3)=2,……,如此類推。這里p(p1)=0表示p1對于各機(jī)器人是強(qiáng)