1、多Agent排隊(duì)系統(tǒng)構(gòu)造研究摘要協(xié)調(diào)與協(xié)作是多Agent研究的核心之一。排隊(duì)是實(shí)現(xiàn)多Agent協(xié)調(diào)與協(xié)作的關(guān)鍵技術(shù)。所謂多Agent排隊(duì)系統(tǒng)是指由多個(gè)申請(qǐng)效勞的顧客Agent和多個(gè)提供效勞的效勞臺(tái)Agent組成的一個(gè)較為松散的組織，由協(xié)調(diào)Agent通過調(diào)度來協(xié)調(diào)它們的行為。多Agent效勞臺(tái)休假排隊(duì)系統(tǒng)是在經(jīng)典排隊(duì)系統(tǒng)的根底上再添加一個(gè)休假策略，針對(duì)不同的應(yīng)用背景，引人各種各樣的休假行為和多Agent群集的思想，而形成的計(jì)算機(jī)系統(tǒng)。關(guān)鍵字agent；排隊(duì)；AS多Agent系統(tǒng)的混合式構(gòu)造一般是由集中式和分布式兩類構(gòu)造組成，它包含一個(gè)或多個(gè)管理效勞機(jī)構(gòu)，此構(gòu)造只對(duì)部分成員Agent以某種方式進(jìn)展

2、統(tǒng)一管理，參與解決Agent之間的任務(wù)劃分和分配、共享資源的分配和管理、沖突的協(xié)調(diào)等。其他Agent之間是平等的，它們的所有行為由自身做出決策。此種構(gòu)造平衡了集中式和分布式兩種構(gòu)造的優(yōu)點(diǎn)和缺乏，適應(yīng)分布式AS復(fù)雜、開放的特性，因此是目前AS普遍采用的系統(tǒng)構(gòu)造。2鑒于多Agent系統(tǒng)的混合式體系構(gòu)造，我們?cè)O(shè)計(jì)多Agent排隊(duì)系統(tǒng)。在多Agent排隊(duì)系統(tǒng)中主要由兩類Agent組成，分別是顧客Agent和效勞臺(tái)Agent。由于系統(tǒng)中效勞臺(tái)數(shù)量是有限的，而顧客數(shù)是無限的，怎樣來協(xié)調(diào)顧客Agent的行為呢?為了防止在申請(qǐng)效勞臺(tái)的時(shí)候發(fā)生沖突以及減少顧客與效勞臺(tái)交互的負(fù)擔(dān)，在多Agent排隊(duì)系統(tǒng)中，我們?cè)O(shè)

3、置了一個(gè)隊(duì)列Agent和一個(gè)協(xié)調(diào)Agent3。多Agent排隊(duì)系統(tǒng)構(gòu)造如圖1。協(xié)調(diào)Agent主要承當(dāng)調(diào)度任務(wù)，協(xié)調(diào)顧客Agent和效勞臺(tái)Agent的行為，以及管理效勞臺(tái)Agent。隊(duì)列Agent是連接顧客Agent和協(xié)調(diào)Agent的紐帶，主要管理隊(duì)列中的顧客Agent，以及代替顧客向協(xié)調(diào)Agent申請(qǐng)效勞臺(tái)。效勞臺(tái)Agent主要提供效勞給顧客Agent。圖1多Agent排隊(duì)系統(tǒng)體系構(gòu)造在我們?cè)O(shè)計(jì)的多Agent排隊(duì)系統(tǒng)中，約定：只有一個(gè)隊(duì)列Agent；顧客遵循以的到達(dá)率到達(dá)系統(tǒng)；效勞臺(tái)Agent的才能是一樣的，都可以效勞任何的顧客；效勞臺(tái)之間是并聯(lián)關(guān)系，效勞臺(tái)的效勞率遵循指數(shù)分布；協(xié)調(diào)Agent

4、采取先到先效勞FFS的調(diào)度策略。顧客Agent是分散的，而且是平等的，它們的行為由自身做出決策。在多Agent排隊(duì)系統(tǒng)中，Agent為了實(shí)現(xiàn)自己的目的的同時(shí)，必須互相協(xié)調(diào)，以致到達(dá)協(xié)作，那么必須以通信為基矗顧客Agent與隊(duì)列Agent之間、效勞臺(tái)Agent與隊(duì)列Agent之間，協(xié)調(diào)Agent和效勞臺(tái)Agent之間，我們采用消息傳送的方式。為了減輕過多的通信給系統(tǒng)帶來的負(fù)擔(dān)，我們暫且不支持顧客之間的通信。由此可知，構(gòu)造Agent的根本要素要有：Agent的心智狀態(tài)、Agent的知識(shí)庫、Agent的感知器、Agent的通信。下面給出這幾個(gè)要素的根本相關(guān)理論。在多Agent排隊(duì)系統(tǒng)中，顧客Agen

5、t、隊(duì)列Agent、效勞臺(tái)Agent以及協(xié)調(diào)Agent都需要一個(gè)根本的Agent為根底來建造。每個(gè)Agent都存在自己的心智狀態(tài)、知識(shí)庫、感知器以及通信模塊等。為了適應(yīng)環(huán)境的動(dòng)態(tài)變化和協(xié)調(diào)各自的行為，Agent必須利用知識(shí)，修改內(nèi)部狀態(tài)，即心智狀態(tài)entalstate。知識(shí)需要感知器感知環(huán)境以及通過通信器與其它Agent進(jìn)展交互而獲得。2.1Agent心智狀態(tài)的形式化描繪在我們的多Agent排隊(duì)系統(tǒng)中，Agent需要和其它Agent或環(huán)境交互，因此，Agent需要表示和維護(hù)環(huán)境的當(dāng)前狀態(tài)，這些信息可以根據(jù)新的信息的獲取而改變，并且可以以Agent的信念或知識(shí)的形式存在。另外Agent的存在是為

6、了實(shí)現(xiàn)自己的目的或問題的解決，而目的的實(shí)現(xiàn)需要多個(gè)Agent互相協(xié)調(diào)。因此，我們?cè)跇?gòu)造Agent心智狀態(tài)的時(shí)候，主要考慮Agent的信念B、愿望D、意圖I、目的G等因素。單個(gè)Agent心智狀態(tài)可以用下面的六元組表示：AgentB，D，I，G，brf，drf，irf其中：B：信念，描繪的是Agent關(guān)于環(huán)境和自身的信息，這些信息可能不完好，甚至是不正確的。可以分為確定的客觀事實(shí)和不確定的主觀態(tài)度。例如“T的父親是Ji，“我相信明天會(huì)下雨，前者是確定的客觀事實(shí)，而后者的正確性是不確定的。Belief：=FatBasedBelief|AttitudeBasedBelief；FatBasedBelie

7、f：=fat(x)|abutfat(x)；abutfat：=fat；AttitudeBasedBelief：=believe(id，t，s)；含義是Agent的信念含有客觀事實(shí)類信念和主觀態(tài)度類信念，客觀事實(shí)類信念包括事實(shí)以及有關(guān)此事實(shí)的知識(shí)。主觀態(tài)度類信念表示Agent在時(shí)間t，相信標(biāo)識(shí)符為id的Agent處于狀態(tài)s。D：愿望，描繪了Agent可以響應(yīng)的事件和可能采納的目的，由一個(gè)目的集組成。這些愿望可以具有不相容性，而且Agent也不必相信它的愿望是可實(shí)現(xiàn)的。I：意圖，描繪了Agent在自己將來的時(shí)間內(nèi)對(duì)自己行動(dòng)的預(yù)先安排，是Agent將來的行動(dòng)方向。根據(jù)當(dāng)前自身和環(huán)境狀態(tài)和目的連接起來，

8、建立方案集合。Intentin：=intend(t，g)tie(t)|believe(id，t，g)|gal(g)含義為：表示Agent感知到外界環(huán)境在時(shí)間t發(fā)生的事件或狀態(tài)所蘊(yùn)含的意圖g后，判斷Agent是否相信在該時(shí)間能實(shí)現(xiàn)該目的，然后向Agent提出實(shí)現(xiàn)目的的懇求。G：目的，即Agent希望進(jìn)入何種狀態(tài)，是Agent從愿望中選擇的子集，Agent可能要加以追求的。目的是Agent當(dāng)前擁有的選擇，然而，Agent還沒有采取詳細(xì)行動(dòng)的承諾。Gal：=gal(x)|abutfat(x)；abutfat(x)：=fat(x)|abutfat(x)含義是當(dāng)Agent獲得所要到達(dá)的目的x時(shí)，將查詢?cè)?/p>

9、目的所需的知識(shí)。brf：Agent信念修正函數(shù)。brf：，該函數(shù)根據(jù)當(dāng)前感知P和當(dāng)前的信念確定一個(gè)新的信念集合。drf：愿望修正函數(shù)。drf：，該函數(shù)根據(jù)Agent關(guān)于環(huán)境和目前意圖的當(dāng)前信念確定一個(gè)愿望。該函數(shù)的作用：一是Agent的愿望的產(chǎn)生是一個(gè)循環(huán)求精的過程，不斷地考慮和承諾部分實(shí)現(xiàn)的意圖，直到最后獲得目的；二是它產(chǎn)生的愿望必須與Agent當(dāng)前的信念和當(dāng)前的意圖相一致，irf：意圖修正函數(shù)。irf：，該函數(shù)基于Agent當(dāng)前信念、愿望和意圖確定一個(gè)新意圖。2.2Agent感知器算法我們知道人的感知器有眼、耳、鼻以及其它器官，機(jī)器人Agent有攝像機(jī)等。而軟件Agent是通過字符串編碼來

10、實(shí)現(xiàn)感知的。感知器是一個(gè)多輸入、單輸出的運(yùn)算系統(tǒng)4。主要有把感知的信息進(jìn)展預(yù)處理后輸出。我們把感知的信息進(jìn)展分類，52類表示對(duì)緊急或簡單的情況；2類表示需要慎思的信息。算法的根本步驟如下：1給定一個(gè)增廣的訓(xùn)練形式集x1，x2，.，xN，其中每個(gè)形式類別，分屬1類和2類。2置步數(shù)k=1，令增量=某正的常數(shù)，分別賦予初始增廣權(quán)矢量1的各分量較小的任意值。3輸入訓(xùn)練形式xk，計(jì)算判別函數(shù)值。4調(diào)整增廣權(quán)矢量，規(guī)那么是：假如和，那么；假如和，那么；假如和，或和，那么。得到判別函數(shù)dx之后，就可以進(jìn)展判別，將待識(shí)別形式x代入dx之中，當(dāng)dx0時(shí)那么判x1；假設(shè)dx0時(shí)那么判x2；假設(shè)dx=0：那么x的類

11、屬不能斷定。緊迫的任務(wù)可以立即得以處理，對(duì)時(shí)間要求不高的任務(wù)可以通過推理選擇最優(yōu)方案。2.3Agent的知識(shí)庫設(shè)計(jì)Agent的知識(shí)表示對(duì)自身和外界的認(rèn)識(shí)，是Agent問題求解的根底6。這些知識(shí)可能預(yù)先給定的，也可能是通過部分感知或與其它Agent的通信而獲得的。Agent知識(shí)庫是Agent活動(dòng)的根據(jù)，也是向外界承諾的基矗在這里知識(shí)庫主要存放Agent的各個(gè)方面的知識(shí)，主要包括以下內(nèi)容。關(guān)于系統(tǒng)組織構(gòu)造、智能、目的等有關(guān)整體性質(zhì)和行為的知識(shí)。關(guān)于理解自身的知識(shí)、行為、求解才能和目的等的知識(shí)。關(guān)于其它Agent的知識(shí)，即具有關(guān)于外部其它Agent的職責(zé)、技能、信念、目的、規(guī)劃等多方面的知識(shí)。關(guān)于A

12、gent間互相作用與通信的知識(shí)。關(guān)于領(lǐng)域世界及待求解問題的知識(shí)。這些知識(shí)是Agent進(jìn)展一切活動(dòng)的基矗Agent還知道哪些Agent與自己由橫向或縱向的聯(lián)絡(luò)，這些知識(shí)在進(jìn)展推理時(shí)起著關(guān)鍵的作用，它們同樣可以看作是Agent的知識(shí)。這些知識(shí)可以映射為事實(shí)、規(guī)那么等。對(duì)于知識(shí)庫我們可以用以下形式表示：KB:=FatBase|RuleBaseFatBase:=FatFat:=lauselause:=bjet1njuntinbjet2bjet:=bjet1njuntinbjet2RuleBase:=RuleRule:=Nae(prenditin1，result1)|(prenditin2，result

13、2)|.(prenditinn，resultn)Nae:=stringprenditini:=lauseresulti:=lause由于Agent每一次決策后都要進(jìn)展知識(shí)的更新。下面給出Agent的知識(shí)更新定理。定義1.1知識(shí)量7設(shè)X為Agent的某一領(lǐng)域，均為有限集或可列集，j=1，2，.，N(N為有限或)為X的一個(gè)表達(dá)，為Agent的一個(gè)表達(dá)測(cè)度，對(duì)任意的令那么稱I(xj)為表達(dá)中的一個(gè)基元xj的自蘊(yùn)含知識(shí)量，其中對(duì)數(shù)底數(shù)b1。定義1.2設(shè)xn，n=1，2，.是所有領(lǐng)域中一列獨(dú)立同分布的Agent知識(shí)量，分布函數(shù)均為Ft，假定F01。記這里，平均期望更新時(shí)間間隔，Tn是第n次更新發(fā)生的時(shí)間

14、，Nt表示Agent在時(shí)間0，t中發(fā)生的知識(shí)更新次數(shù)。其中，(t)=ENt稱為Agent知識(shí)的更新函數(shù)，有。(t)的導(dǎo)數(shù)。fn(t)是Fn(t)的知識(shí)更新強(qiáng)度。2.4Agent的通信模塊在多Agent排隊(duì)系統(tǒng)中，每個(gè)Agent自主的運(yùn)行，但是由于每個(gè)Agent僅擁有不完全的信息和問題求解才能，所以多個(gè)Agent必須互相通信、協(xié)同工作。通信是協(xié)作的基矗采用消息通信是實(shí)現(xiàn)靈敏復(fù)雜的協(xié)調(diào)策略的基矗使用規(guī)定的協(xié)議、Agent彼此交換的信息可以用來建立通信和協(xié)作機(jī)制。通信模塊主要包含如下的部分1：1sket接口：它的功能是將直接與協(xié)議有關(guān)的通信部分組合在一起，并給通信模塊的其它部分進(jìn)步一種通信方式，使通

15、信模塊的其它部分不用再考慮與發(fā)送協(xié)議有關(guān)的部分。sket接口包含以下內(nèi)容。效勞線程：sket接口中有一個(gè)效勞線程，它使用一個(gè)ServerSket不停地監(jiān)聽Agent的端口地址，一旦發(fā)現(xiàn)有消息到來，就啟動(dòng)一個(gè)消息線程處理這個(gè)消息，然后繼續(xù)監(jiān)聽。消息線程：由效勞線程啟動(dòng)。它的任務(wù)是讀入消息，并將消息送到承受緩沖區(qū)?？蛻艟€程：由發(fā)送線程啟動(dòng)。它的任務(wù)是將消息通過sket發(fā)出。2承受緩沖區(qū)：用來緩存從外界發(fā)來的消息。3發(fā)送緩沖區(qū)：用來緩存向外界發(fā)送的消息。4發(fā)送進(jìn)程：是一個(gè)常駐線程。它的任務(wù)是不斷監(jiān)視發(fā)送緩沖區(qū)，一旦有消息進(jìn)入發(fā)送緩沖區(qū)就啟動(dòng)sket接口中的方法來將消息發(fā)出。5承受線程：它的任務(wù)是不斷

16、查看承受緩沖區(qū)，一旦有消息進(jìn)入承受緩沖區(qū)就啟動(dòng)一個(gè)過濾線程來對(duì)消息進(jìn)展解釋和處理。6過濾線程：由承受線程啟動(dòng)。它調(diào)用語法分析將承受到的字符流的消息轉(zhuǎn)換成符合語法構(gòu)造的原語，然后調(diào)用解釋器來對(duì)原語解釋。7解釋器：解釋并處理一些簡單的且僅與通信模塊有關(guān)的一些通信原語。8地址?。和ㄐ拍K保存Agent的地址薄信息。9消息發(fā)送函數(shù)：調(diào)用轉(zhuǎn)化函數(shù)將原語轉(zhuǎn)化成字符流放入發(fā)送緩沖區(qū)。下面介紹幾種常用的消息：bindagenturl，sendernae，reEiverurl/發(fā)送注冊(cè)消息給對(duì)方shutdn(ntent，sendernae，reeiverurl)；/發(fā)送注銷信息給對(duì)方inquire(ntent，

17、sendernae，reeiverurl，senderurl)；/詢問承受Agent信息request(ntent，sendernae，reeiverrurl，senderurl)；/向承受Agent發(fā)送懇求信息2.5Agent的規(guī)劃模塊在AI領(lǐng)域，規(guī)劃是通過模擬人類求解復(fù)雜問題的過程而形成的一種方法。規(guī)劃的問題求解方法分為兩個(gè)過程：規(guī)劃過程和執(zhí)行過程。其中，規(guī)劃過程是針對(duì)某一任務(wù)，求取完成該任務(wù)的動(dòng)作序列，這一動(dòng)作序列稱為方案。方案是規(guī)劃過程的輸出結(jié)果。執(zhí)行過程是指按照集合實(shí)現(xiàn)問題求解，并監(jiān)控問題求解的進(jìn)展，當(dāng)出現(xiàn)意外情況方案無法執(zhí)行時(shí)，調(diào)整行為集合或再次規(guī)劃，直至任務(wù)完成。Agent的規(guī)劃

18、模塊負(fù)責(zé)建立中短期的行動(dòng)方案。它是一個(gè)部分的規(guī)劃。每個(gè)Agent根據(jù)目的集合、自身的狀態(tài)、對(duì)環(huán)境和其它Agent的理解，以及以往的經(jīng)歷規(guī)劃自身的行為。Agent規(guī)劃常用方法之一是將Agent的方案庫定義為一個(gè)與或圖構(gòu)造，其中，每一條方案由4部分組成。1方案目的表示該方案能到達(dá)的目的；2方案的前提表示方案執(zhí)行需要滿足的條件；3方案體表示方案內(nèi)容，由方案序列和方案子目的組成；4方案執(zhí)行結(jié)果表示執(zhí)行方案后外部世界的更新結(jié)果。有了這些根本要素以后，我們可以根據(jù)需求構(gòu)造根本的Agent了，下面給出Agent的工作流程及算法。2.6Agent工作流程及算法1Agent的工作原理Agent工作過程如圖2所示

19、，當(dāng)事件到達(dá)時(shí)，Agent根據(jù)前感知的環(huán)境信息、自身信息以及自己的才能，假設(shè)感知的信息比擬簡單或緊急，那么直接反響式?jīng)Q策，否那么，要慎思以后進(jìn)展規(guī)劃，最后產(chǎn)生決策，即，由信念修正產(chǎn)生目的，并做出相應(yīng)的方案集，然后選取相應(yīng)的行為集來完成一系列的方案，假如方案失敗，那么繼續(xù)更新信念集。圖2Agent的工作流程2Agent的工作流程算法根據(jù)Agent的工作原理，可將其工作流程算法描繪為：funtinAgent()Begin事件到達(dá)；將感知信息進(jìn)展分類；ifPisessyrurgenythenreatin；elseL1：B：=brf(P，B)；/根據(jù)感知和當(dāng)前信念集產(chǎn)生新的信念ptins：=ptin_Generatr(Envent_Queue，B，I，G)；/根據(jù)環(huán)境