張 立,王茜竹,趙春江,汪 霞,姜大立
(1.后勤工程學院 現(xiàn)代物流研究所,重慶 401311;2.重慶郵電大學 電子信息與網(wǎng)絡工程研究院,重慶 400065;3.后勤工程學院 基礎部,重慶 401311)
近年來,隨著產(chǎn)品協(xié)同設計、網(wǎng)絡化制造、虛擬企業(yè)聯(lián)盟等協(xié)同計算理論與應用的快速發(fā)展,任務分配問題倍受關注。任務分配的關鍵是分配方法,不同的工業(yè)應用背景催生不同的任務分配方法,例如面向靜態(tài)確定環(huán)境的集中式任務分配方法[1]、面向柔性不確定條件的動態(tài)任務分配方法[2]以及各種優(yōu)化算法在任務分配問題上的應用[3-5]。與傳統(tǒng)的任務分配方法相比,基于多智能體系統(tǒng)(Multiagent System,MAS)的任務分配方法[6]具有獨特優(yōu)勢:一方面,任務候選Agent可以被賦予更多的理性與智能,使得其具有自治能力、主動參與決策;另一方面,當單個任務候選Agent能力不足時,可以通過MAS的協(xié)調(diào)機制請求其他任務候選Agent進行協(xié)作。由于Agent的自治特性和MAS的分布式自組織能力非常適合刻畫網(wǎng)絡化制造環(huán)境下的多實體協(xié)同生產(chǎn)模式,MAS模型常常被用于網(wǎng)絡化制造及云制造背景下的任務分配計算[7-8]。
在MAS 任務分配系統(tǒng)中,合同網(wǎng)(contract net)[9]是其中非常重要的協(xié)調(diào)機制。傳統(tǒng)的合同網(wǎng)機制雖然給基于MAS的任務分配協(xié)調(diào)帶來了諸多優(yōu)勢,但其純分布式結構所固有的控制復雜、通信量大、耗費資源多、不確定性突出等缺陷依然限制了實際場景下的有效應用,因此基于合同網(wǎng)機制的擴展成為研究熱點。近年來,在合同網(wǎng)擴展研究領域涌現(xiàn)出若干新穎的思路與方法并應用于工業(yè)實踐。例如:Hsieh等[10]提出兩層合同網(wǎng)協(xié)議并將其應用于人類心智系統(tǒng)(Human Mind System,HMS)的工作流規(guī)劃中;Billington等[11]應用有色Petri網(wǎng)技術擴展了合同網(wǎng)協(xié)議以支持多管理Agent的并發(fā)控制;Raza等[12]將質(zhì)量評價因素加入合同網(wǎng)協(xié)議中,稱之為Q-Contract Net,并將其應用于數(shù)字業(yè)務生態(tài)系統(tǒng)中。類似的研究還包括擴展合同網(wǎng)ECNP[13]、基于閾值和可用度的合同網(wǎng)[14]、基于熟人聯(lián)盟的合同網(wǎng)[15]、基于信任協(xié)議的合同網(wǎng)[16]、基于共享心智模型的合同網(wǎng)[17]、動態(tài)合同網(wǎng)[18]等。
上述文獻中,引入心智概念以提高合同網(wǎng)的協(xié)調(diào)效率、降低通信開銷是一種重要的改進思路[15-18]。但是,此類合同網(wǎng)協(xié)議改進主要集中于從招標Agent的角度討論熟人關系、信任度等心智狀態(tài)參數(shù),未見到從競標Agent的意愿進行研究的文獻。事實上,競標Agent的風險承受能力、繁忙狀況、參加任務時間緊迫性等因素將同樣決定其競標的態(tài)度,因此,需要考慮實際場景中競標Agent的半自治性并綜合招投標的整個過程對心智參數(shù)進行系統(tǒng)化設計;在中標決策函數(shù)方面,典型的研究[11-14]均以競標Agent的報價作為其決策依據(jù),忽略了在網(wǎng)絡化制造背景下同樣重要的競標Agent間的協(xié)作代價和任務距離代價,因此需要改進中標決策目標函數(shù),以使其更符合實際網(wǎng)絡化制造的需求。著眼上述問題,本文以MAS任務分配為研究對象,結合網(wǎng)絡化制造條件下制造商與供應商的非對等博弈應用背景改進合同網(wǎng)運行機制,提出一種基于心智與擴展合同網(wǎng)的多Agent任務分配協(xié)調(diào)方法。
基于心智模型的MAS任務分配機制的描述如圖1所示。圖中存在一個管理Agent和多個競標Agent,管理Agent與競標Agent之間通過基于合同網(wǎng)的方法進行任務分配協(xié)調(diào)控制。心智模型是基礎,基于心智狀態(tài)的招標優(yōu)化、競標報價和中標優(yōu)化將支持MAS 任務分配協(xié)調(diào)關鍵步驟的控制與決策。其任務分配的具體過程如下:①管理Agent對任務進行分解、組合、排序等預處理;②管理Agent將利用基于心智的競標Agent優(yōu)選算法,從所有可承擔該任務的Agent集中優(yōu)選Agent、形成競標Agent集并發(fā)送招標書;③競標Agent通過招標書屬性及競標決策函數(shù)計算成本,結合期望的利潤率進行報價、發(fā)送競標書;④管理Agent收集競標書并按照中標選擇算法選擇承擔任務Agent;⑤簽訂任務合同,完成任務分配。
該MAS任務分配過程設立管理Agent,由管理Agent對任務本身的要求與競標Agent的能力、資源進行集中規(guī)劃后分配給相應的競標Agent,這與集中式任務分配決策實施方式相吻合;在此基礎上,該任務分配過程充分考慮心智的特點,既包括管理Agent對任務承擔Agent的信任度、忠誠度、積極度的評價,也考慮競標Agent對自身風險承受度、繁忙度以及對任務緊迫度的評價,保持了競標Agent的半自治性。這種集中與半自治相結合的MAS任務分配過程更加適用于具有較強時效要求的松散耦合節(jié)點聯(lián)盟任務分配,如云制造、應急物資籌措等環(huán)境。
定義1 基于擴展合同網(wǎng)的MAS心智模型,定義為四元組〈agent_relation,Mental_parameter,Call_for_bidder,Bid〉。其中:agent_relation=〈agentm,agentp〉,分別表示管理Agent與任務候選Agent;Mental_parameter=〈B,L,A,RT,BD,UD〉,分別表示信任度、忠誠度、積極度、風險承受度、繁忙度和緊迫度等Agent心智參數(shù);Call_for_bidder=〈Cfb_df,Cfb_ca〉表示發(fā)標決策函數(shù)與算法;Bid=〈Bid_df,Bid_ca〉表示投標決策函數(shù)與算法。
心智參數(shù)Mental_parameter中各心智參數(shù)的具體符號表示、含義、范圍和更新公式如下:
(1)信任度B表示agentm對agentp歷史任務完成情況的評價,B∈[0…1]。其更新函數(shù)為
式中:L表示agentp完成任務ti-1的質(zhì)量,質(zhì)量越好L越臨近1;P表示agentp執(zhí)行任務ti-1的失敗程度,失敗得越徹底P越臨近1;δ與ε分別是任務完成的獎勵因子與任務失敗的懲罰因子。
(2)忠誠度L表示agentm與agentp隸屬關系的反映,L∈[0…1]。其更新函數(shù)為
忠誠度以組織結構樹進行量化。式(2)中,忠誠度為1表示絕對服從,此時agentp是agentm的直系子女;忠誠度為0 表示無隸屬,此時agentp與agentm不連通或者agentp是agentm的上層節(jié)點;否則,忠誠度為節(jié)點間距離的倒數(shù);設定忠誠度在確定的MAS任務求解環(huán)境中保持不變。
(3)積極度A表示agentp的競標積極性,A∈[0…1]。其更新函數(shù)為
式中:Nmax為準備分配任務ti時agentp收到的招標總次數(shù),Nti為agentp的中標次數(shù),令Nmax=0時A=0。
(4)風險承受度RT表示agentp承受風險的能力,RT∈[0…1]。其更新函數(shù)為
式中:σ與φ分別是任務完成的風險承受度變化因子與任務失敗時的變化因子;timei-1為任務ti-1的執(zhí)行時間,τ為執(zhí)行任務累計時間增加而產(chǎn)生的風險承受度變化因子。
風險承受度的變化依賴于歷史任務的完成情況和參與時間兩個要素。歷史任務完成得越好,agentp風險承受度越高;累計參與任務時間越長,agentp風險承受度越低。
(5)繁忙度BD表示agentp當前的忙碌狀況,BD∈[0…1]。其更新函數(shù)為
(6)緊迫度UD表示agentp對任務時間緊迫性的評估,UD∈[0…1]。其更新函數(shù)為
式中:ti.start_deadline為任務的最遲執(zhí)行時間,ET為評估函數(shù),ti.start_deadline越小,UD越大。
定義2 發(fā)標適合度。當準備分配任務ti時,發(fā)標適合度表示管理agentm對任務候選agentp是否適合參與競標的綜合評價值,記為Cf_Bidder_fitness(agentp,ti),
式中:B,L和A分別為信任度、忠誠度、積極度三種心智參數(shù);α,β,γ,μ,σ,ρ,φ為權重系數(shù)。當ti為普通任務NOR 時,發(fā)標決策參考的心智參數(shù)按權重從高到低分別為信任度、積極度、忠誠度;當ti為重要任務IMP時,發(fā)標決策參考的心智參數(shù)按權重從高到低分別為信任度、忠誠度;當ti為緊急任務ARD時,發(fā)標決策參考的心智參數(shù)按權重從高到低分別為忠誠度、信任度。
算法1 Call_for_bidder()。
步驟1 算法初始化。
定義一維數(shù)組T,C,A分別存儲任務、能力與Agent;定義一維數(shù)組Cand_bidder存儲待分配任務的候選Agent集;定義二維數(shù)組TC,AC分別存儲任務—能力、Agent—能力之間關系;定義三維數(shù)組TCA存儲任務與Agent之間關系;定義BD_limit表示發(fā)標限額。
步驟2 算法輸入。
輸入T,C,A,TC,AC;輸入任務、能力、Agent的數(shù)量。
步驟3 產(chǎn)生矩陣TCA。
步驟4 產(chǎn)生競標候選Agent集。
承蒙大冶市烹飪行業(yè)協(xié)會秘書長羅文兄的安排,在暖如春陽般的冬日,一位漂亮的導游姑娘帶領我們參觀了銅綠山古銅礦遺址博物館和至今仍在開采的天坑般的銅綠山銅礦礦區(qū)。
選取發(fā)標適合度值大的前BD_limit個Agent組成競標候選集Cand_bidder。步驟5 發(fā)送標書給競標候選Agent集Cand_bidder。
定義3 任務消耗預期。當準備分配任務ti某能力cj時,任務消耗預期表示agentp對執(zhí)行該需求耗費的預估值,記為Cost(agentp,ti,cj),
式中:RT,BD和UD分別為風險承受度、繁忙度、緊迫度三種心智參數(shù);penalty/reward表示任務能力/資源執(zhí)行的懲獎比;α,β,γ和δ為權重系數(shù)。待分配任務ti的性質(zhì)可為普通任務NOR、重要任務IMP、緊急任務ARD 三類,權重系數(shù)關系互異。
定義4 任務競標報價。當agentp對任務ti的某能力cj競標時,任務能力競標報價表示agentp對執(zhí)行任務ti需要的某能力cj所期望的價格,記為Price(agentp,ti,ci),
式中φ為利潤系數(shù),根據(jù)任務ti的性質(zhì)以及agentp對任務的渴望程度進行設置。
每個競標Agent計算得到自己的任務競標開價后,將其封裝進競標書并發(fā)送給管理agentm,然后等待競標結果。
5.1.1 問題假設
在網(wǎng)絡化制造MAS 任務分配環(huán)境中,假設所有任務與Agent按照分布的地理位置構成連通的拓撲網(wǎng)絡;任務ti所需的所有能力位于同一節(jié)點,而任務候選agentp的每個能力可分布在不同的節(jié)點中。假設為任務ti所需能力對應的所有候選(競標)Agent集。
定義5 基于心智與擴展合同網(wǎng)的MAS分布式任務分配模型。對于任意待分配任務ti,在其對應的競標Agent集中搜索某個Agent子集以組成任務分配Agent集RS},使得任務分配的總成本Cost(ti)最小。
Cost(ti)由三部分成本構成:①執(zhí)行任務距離成本,表示RS中每個agent提供給任務ti的能力位置到任務節(jié)點所在位置的拓撲距離之和;②執(zhí)行任務的協(xié)作成本,表 示RS中agent間的協(xié)作距離之和(協(xié)作距離的概念見定義6);③執(zhí)行任務的價格成本,表示RS中每個agent對任務ti中能力的競標報價。
定義6 組織結構樹OS_Tree 和協(xié)作距離Col_distance。組織結構樹OS_Tree是將現(xiàn)實中的各級實體組織描述成節(jié)點,并按隸屬關系映射形成的特殊樹狀結構;協(xié)作距離Col_distance是OS_Tree 中任意兩點間協(xié)作代價的衡量標準,其值等于連接兩節(jié)點路徑中邊的數(shù)目。節(jié)點與自身的Col_distance定義為0。兩點間的Col_distance越大,協(xié)作代價就越大。
任務分配總Cost(ti)的計算式如下:
算法2 Operation_agent_volting(Taskti)。
步驟1 算法初始化。
定義:二維數(shù)組CA存儲任務ti中能力集與其對應的競標Agent集,即用CA存儲;變量min_cost存儲任務分配的最小代價值;一維數(shù)組RS存儲MAS任務分配協(xié)調(diào)的結果集。
步驟2 算法輸入。
輸入CA;min_cost賦值為一大數(shù);RS=?。
步驟3 任務分配協(xié)調(diào)計算。
/* 算法中Calculate_cost函數(shù)計算承擔任務Agent集為{ac1,ac2,…,acn}時的任務分配總代價,其計算見式(10)*/
步驟4 返回任務分配結果。
return(RS)。
(1)管理agentm對任務實施agentp的任務執(zhí)行狀況進行評價,并重置心智參數(shù)B,A。
(2)任務實施agentp對自身任務執(zhí)行狀況進行評價,并重置相關心智參數(shù)RT,BD。
(3)Agent能力矩陣及拓撲位置更新。當任務分配后,需刪除相應的agentp已分配的能力ci;當任務成功執(zhí)行后,需恢復對應能力;類似地,還需修改能力ci的拓撲位置關系。
某制造企業(yè)需要制訂原材料采購計劃(任務t):需要采購的物資集Rt={r2,r4,r6,r8},需要供應商提供的能力如包裝、運輸、加工和裝卸等,形式化為需求集Ct={c1,c3,c5,c8};待選供應商Agent集A={a1,a3,a4,a5,a6,a8,a9,a11,a13,a14,a16}。
供應商Agent集與擬采購物資的關系為:Ar2={a1,a3,a4,a6,a11,a14,a16},Ar4={a1,a5,a8,a9,a11,a14},Ar6={a4},Ar8={a4,a5,a8,a11,a13,a14};供應商Agent集與所需能力的關系為:Ac1={a1,a3,a6,a9,a11,a13,a14},Ac3={a1,a4,a6,a8,a11,a16},Ac5={a1,a3,a4,a9,a14},Ac8={a9,a14}。
求解供應商Agent集RT:RT={ac1,ac3,ac5,ac8,ar2,ar4,ar6,ar8},使得任務分配的總成本Cost(t)最小(該例中的能力集與物資集均屬于agent的能力范疇,處理方式相同)。
擬分配原材料采購計劃任務t時,待選供應商Agent的心智狀態(tài)設置如表1所示;與任務分配相關的系數(shù)與常數(shù)設置如表2所示;采購企業(yè)與供應商間的拓撲距離如圖2所示;供應商間的組織結構如圖3所示。
表1 擬分配任務t時各候選Agent的心智狀態(tài)
表2 相關系數(shù)及常數(shù)設置情況
6.3.1 發(fā)標適合度CF_Bidder_fitness計算
由于任務t的性質(zhì)為普通任務,采購企業(yè)Agent根據(jù)式(7)以及表1、表2的初始值得到待分配任務Agent的發(fā)標適合度CF_Bidder_fitness的計算結果,如表3所示。
6.3.2 優(yōu)化發(fā)標Agent集并發(fā)標
采購企業(yè)Agent根據(jù)算法1 和發(fā)標限額常量BD_limit,選擇CF_Bidder_fitness值較大的供應商Agent形成擬發(fā)標Agent集;然后組織競標書并將其發(fā)給對應的擬發(fā)標Agent集。
表3 待分配任務Agent發(fā)標適合度Cf_Bidder_fitness的計算結果
由于任務t的性質(zhì)為普通任務,根據(jù)式(8)、式(9)以及表1、表2的相應初始值得到待分配任務Agent對承擔任務(能力)的預計開銷值Cost與競標報價Price,如表4所示。
表4 任務(能力)預計開銷Cost及競標報價Price 計算結果(Cost/Price)
根據(jù)采購企業(yè)與供應商網(wǎng)絡拓撲距離圖(如圖2)即可計算采購企業(yè)Agent與供應商Agent間的距離成本。
根據(jù)供應商組織結構圖(如圖3)即可計算供應商Agent節(jié)點兩兩間的協(xié)作距離,從而計算得到各任務分配候選Agent集合的總協(xié)作成本。
6.4.4 MAS任務分配協(xié)調(diào)
在Visual Studio 2008 環(huán)境下,基于Visual C++語言,以表1 和表2 中的數(shù)據(jù)為初始值,實現(xiàn)算法1和算法2,其用戶界面和運算結果如圖4所示。運算結果說明,將企業(yè)采購任務t的能力/物資子任務集{c1,c3,c5,c8,r2,r4,r6,r8}對 應分配給供應商Agent集{a3,a1,a3,a14,a3,a5,a4,a5},其任務分配的綜合成本最低。該算例仿真程序驗證了所提MAS任務分配算法的有效性。通過參數(shù)化的方法對程序的初始變量進行處理,即可實現(xiàn)支持基于不同初始數(shù)據(jù)集的MAS任務分配協(xié)調(diào),從而進一步提高程序的通用性。
本文綜合Agent心智建模的經(jīng)典文獻并針對網(wǎng)絡化制造背景下的實際需求,提出心智模型,包括信任度、忠誠度、積極度、風險承受度、繁忙度和緊迫度等心智因素,分別從管理Agent和競標Agent兩個角度進行應用,使心智模型更具系統(tǒng)性和實用性;另一方面,采用集中與分布結合的混合方式設計MAS任務分配協(xié)調(diào),管理Agent利用心智模型對競標Agent進行優(yōu)選,反映了競標Agent的績效;競標Agent利用心智模型進行競標報價,體現(xiàn)了競標Agent的績效;MAS 任務分配模型算法采用價格、協(xié)作與距離作為優(yōu)化代價的多目標因素,更能反映網(wǎng)絡化制造的需求。整個任務分配協(xié)調(diào)以任務所需的能力而不是整個任務作為處理的基礎,具有更精細的粒度與合理性。下一步工作中,將采用多屬性優(yōu)化方法對該機制中的重要參數(shù)權重取值進行研究,進一步提高本MAS 任務分配協(xié)調(diào)機制的實用性。
[1]PAPANTONOPOULOS S.System design in normative and actual practice:a comparative study of cognitive task allocation in advanced manufacturing systems[J].Human Factors and Ergonomics in Manufacturing &Service Industries,2004,14(2):181-196.
[2]LIU Hong,LIN Zongkai.A cooperative design approach supporting dynamic task assignation [J].Journal of Software,2001,12(12):1830-1836(in Chinese).[劉 弘,林宗楷.一種支持動態(tài)任務分配的協(xié)同設計方法[J].軟件學報,2001,12(12):1830-1836.]
[3]ZHONG Qiuxi,XIE Tao,CHEN Huowang.Task matching and scheduling by using genetic algorithms[J].Journal of Computer Research Development,2000,37(10):1197-1203(in Chinese).[鐘求喜,謝 濤,陳火旺.基于遺傳算法的任務分配與調(diào)度[J].計算機研究與發(fā)展,2000,37(10):1197-1203.]
[4]ALEKSANDAR J,ALVARO G,DIEGO A,et al.Distributed bees algorithm for task allocation in swarm of robots[J].IEEE Systems Journal,2012,6(2):296-304.
[5]ZHAO F Q,HONG Y,YU D M,et al.A hybrid algorithm based on particle swarm optimization and simulated annealing to holon task allocation for holonic manufacturing system[J].International Journal of Advanced Manufacturing Technology,2007,32(9/10):1021-1032.
[6]FATIMA S S,WOOLDRIDGE M.Adaptive task resources allocation in multi-agent systems[C]//Proceedings of the 5th International Conference on Autonomous Agents.New York,N.Y.,USA:ACM,2001:537-544.
[7]MONOSTORI L,VáNCZA J,KUMARA S R T.Agent-based systems for manufacturing[J].CIRP Annals-Manufacturing Technology,2006,55(2):697-720.
[8]XU X.From cloud computing to cloud manufacturing[J].Robotics and Computer-Integrated Manufacturing,2012,28(1):75-86.
[9]DAVIS R,SMITH R G.Negotiation as a metaphor for distributed problem solving[J].Artificial Intelligence,1983,20(1):63-109.
[10]HSIEH F S,CHIANG C Y.Workflow planning in holonic manufacturing systems with extended contract net protocol[C]//Proceedings of Next-Generation Applied Intelligence.Berlin,Germany:Springer-Verlag,2009:701-710.
[11]BILLINGTON J,GUPTA A K,GALLASCH G E.Modelling and analysing the contract net protocol-extension using coloured petri nets[C]//Proceedings of the 28th International Conference on Formal Techniques for Networked and Distributed Systems.Berlin,Germany:Springer-Verlag,2008:169-184.
[12]RAZA M,HUSSAIN F K,HUSSAIN O K,et al.Q-Contract net:a negotiation protocol to enable quality-based negotiation in digital business ecosystems[C]//Proceedings of 2010 International Conference on Complex,Intelligent and Soft-ware Intensive Systems.Washington,D.C.,USA:EEE,2010:161-167.
[13]FISCHER K,MüLLER J R G P,PISCHEL M.Cooperative transportation scheduling:an application domain for DAI[J].Applied Artificial Intelligence,1996,10(1):1-34.
[14]YANG Jian,LI Wenli,HONG Chunyu.Improvement to contract net protocol based on threshold and availability[J].Computer Integrated Manufacturing Systems,2009,15(5):1017-1022(in Chinese).[楊 件,李文立,洪春宇.基于閾值和可用度的合同網(wǎng)協(xié)議改進方案研究[J].計算機集成制造系統(tǒng),2009,15(5):1017-1022.]
[15]TAO Haijun,WANG Yadong,GUO Maozu,et al.A multiagent negotiation model based on acquaintance coalition and extended contract net protocol[J].Journal of Computer Research and Development,2006,43(7):1155-1160(in Chinese).[陶海軍,王亞東,郭茂祖,等.基于熟人聯(lián)盟及擴充合同網(wǎng)協(xié)議的多智能體協(xié)商模型[J].計算機研究與發(fā)展,2006,43(7):1155-1160.]
[16]YU Zhenhua,LIU Yu,CAI Yuanli.On wireless sensor networks collaboration based on an extended contract net protocol[J].Control and Decision,2009,24(1):61-65(in Chinese).[于振華,劉 宇,蔡遠利.基于擴展合同網(wǎng)協(xié)議的無線傳感器網(wǎng)絡協(xié)作方法研究[J].控制與決策,2009,24(1):61-65.]
[17]CHEN Ming,JIAN Yumei.Research on mental-coefficient based multi-agent contract net collaborative model[J].Computer Application and Software,2013,30(6):46-51(in Chinese).[陳 明,簡玉梅.基于心智系數(shù)的多Agent合同網(wǎng)協(xié)作模型研究[J].計算機應用與軟件,2013,30(6);46-51.]
[18]ZHANG Haijun,SHI Zhongzhi.Dynamic contract net protocol[J].Computer Engineering,2004,30(21):44-46(in Chinese).[張???,史忠植.動態(tài)合同網(wǎng)協(xié)議[J].計算機工程,2004,30(21):44-46.]