基于協(xié)同學(xué)的Ｍｕｌｔｉ－Ａｇｅｎｔ合作系統(tǒng)研究

摘要：探討了協(xié)同學(xué)在Multi－Agent系統(tǒng)（MAS）合作中的應(yīng)用；討論了MAS的協(xié)同合作，給出了基于協(xié)同學(xué)的Multi－Agent的協(xié)同模型，量化了Multi－Agent協(xié)同機(jī)制的協(xié)調(diào)效應(yīng)，為其最優(yōu)協(xié)同機(jī)制的選擇提供了依據(jù)。將序參量、自組織理論引入到MAS合作中，為MAS合作問(wèn)題提供了一個(gè)新的解決思路。

關(guān)鍵詞：協(xié)同學(xué)；多代理;自組織;序參量

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)05－0063－03



協(xié)同學(xué)是研究由完全不同性質(zhì)的大量子系統(tǒng)（如電子、原子、細(xì)胞、神經(jīng)原、力學(xué)元、光子、器官、動(dòng)物乃至人類(lèi)）所構(gòu)成的各種系統(tǒng)，研究這些子系統(tǒng)是如何通過(guò)合作在宏觀尺度上產(chǎn)生空間、時(shí)間或功能結(jié)構(gòu)[1]。協(xié)同是系統(tǒng)中諸多子系統(tǒng)相互協(xié)調(diào)、合作或同步的聯(lián)合作用，是系統(tǒng)整體性、相關(guān)性的內(nèi)在表現(xiàn)。協(xié)同學(xué)是以系統(tǒng)論、信息論、控制論、突變論等為基礎(chǔ)，采用統(tǒng)計(jì)學(xué)和動(dòng)力學(xué)相結(jié)合的辦法，通過(guò)類(lèi)比分析，建立一整套數(shù)學(xué)模型和處理方法來(lái)研究協(xié)同系統(tǒng)從無(wú)序到有序的演變規(guī)律。合作問(wèn)題是協(xié)同學(xué)研究的一個(gè)重要問(wèn)題。

Multi－Agent系統(tǒng)（MAS）由分布在網(wǎng)絡(luò)上的多個(gè)Agent松散耦合成。通過(guò)Agent之間的相互合作以解決單一Agent能力和知識(shí)所不能處理的復(fù)雜問(wèn)題。Agent合作是MAS最基本的特征，因此Multi－Agent合作機(jī)制成為MAS研究的一項(xiàng)重要內(nèi)容。文獻(xiàn)[2]中提出兩種Multi－Agent合作結(jié)構(gòu)，即不完全合作結(jié)構(gòu)和完全合作結(jié)構(gòu)；在此基礎(chǔ)上文獻(xiàn)[3]從“是否完全合作”“是否存在目標(biāo)互換”“合作雙方的數(shù)量對(duì)比”等三個(gè)角度把Multi－Agent的合作結(jié)構(gòu)分為16種，但Multi－Agent合作中的不確定性和競(jìng)爭(zhēng)性使合作問(wèn)題的研究十分復(fù)雜。而協(xié)同學(xué)中子系統(tǒng)通過(guò)競(jìng)爭(zhēng)達(dá)成協(xié)同的理論，可以應(yīng)用于Multi－Agent合作問(wèn)題中，解決MAS中不同目標(biāo)、能力的Agent協(xié)同一致完成任務(wù)。但目前應(yīng)用協(xié)同學(xué)思想研究Multi－Agent合作的文獻(xiàn)還沒(méi)有，本文把協(xié)同學(xué)思想引入到Multi－Agent合作中，構(gòu)建Multi－Agent合作的協(xié)同模型，實(shí)現(xiàn)整體效用的最大化。

1協(xié)同學(xué)

1．1幾個(gè)重要概念

(1)子系統(tǒng)。協(xié)同學(xué)將研究的對(duì)象稱(chēng)為系統(tǒng)，而將組成系統(tǒng)的下一層次稱(chēng)為子系統(tǒng)。在MAS中，每個(gè)Agent就是子系統(tǒng)。

(2)序參量。子系統(tǒng)總是存在著自發(fā)的無(wú)規(guī)則的獨(dú)立運(yùn)動(dòng)，同時(shí)又受到其他子系統(tǒng)對(duì)它的共同作用、因此存在著子系統(tǒng)之間關(guān)聯(lián)而形成的協(xié)同運(yùn)動(dòng)。序參量是系統(tǒng)相變前后所發(fā)生的質(zhì)的飛躍的最突出標(biāo)志。

(3)自組織。它是在沒(méi)有外界因素驅(qū)使下，開(kāi)放式（與環(huán)境有物質(zhì)、能量和信息交換的）系統(tǒng)在其子系統(tǒng)或元素間競(jìng)爭(zhēng)—合作機(jī)制作用下，自發(fā)出現(xiàn)新的宏觀（整體）有序結(jié)構(gòu)—時(shí)間、空間或功能有序新結(jié)構(gòu)的現(xiàn)象。自組織理論是協(xié)同學(xué)的核心理論。

1．2協(xié)同

協(xié)同，就是系統(tǒng)中諸多子系統(tǒng)的相互協(xié)調(diào)、合作或同步的聯(lián)合作用，集體行為。一個(gè)復(fù)雜的系統(tǒng)，若子系統(tǒng)互相配合產(chǎn)生協(xié)同作用和合作效應(yīng)，系統(tǒng)便處于自組織狀態(tài)，系統(tǒng)在宏觀上和整體上表現(xiàn)為具有一定的結(jié)構(gòu)或功能。不同的系統(tǒng)性質(zhì)會(huì)有不同，但都從不同側(cè)面揭示了從宏觀到微觀、從機(jī)械運(yùn)動(dòng)到生物運(yùn)動(dòng)的和諧性和協(xié)調(diào)性。 

協(xié)同系統(tǒng)是指由許多子系統(tǒng)組成的、能以自組織方式形成宏觀的空間、時(shí)間或功能有序結(jié)構(gòu)的開(kāi)放系統(tǒng)。系統(tǒng)演化過(guò)程中從無(wú)到有的變化通過(guò)序參量來(lái)表示。序參量來(lái)源于子系統(tǒng)之間的協(xié)同，能夠指示新結(jié)構(gòu)的形成，同時(shí)起著支配子系統(tǒng)行為的作用。協(xié)同學(xué)認(rèn)為，一個(gè)系統(tǒng)從無(wú)序到有序轉(zhuǎn)換的關(guān)鍵在于由一個(gè)大量子系統(tǒng)構(gòu)成的開(kāi)放系統(tǒng)內(nèi)部發(fā)生的協(xié)同作用。它強(qiáng)調(diào)系統(tǒng)內(nèi)部的關(guān)聯(lián)及系統(tǒng)發(fā)生變化時(shí)要素間的互相配合與耦合。

可以從協(xié)同成員對(duì)協(xié)同活動(dòng)的貢獻(xiàn)、對(duì)各自觀點(diǎn)的表達(dá)方式上將協(xié)同方式分為以下三種：①協(xié)商（或?qū)Σ撸┓绞健＂诤献鞯姆绞健＿@種方式的協(xié)同工作可以描述成一個(gè)協(xié)作群體共同解決一個(gè)（或多個(gè)）問(wèn)題，或協(xié)作完成一項(xiàng)（或多項(xiàng)）共同的任務(wù)。③創(chuàng)造的方式。

2Multi－Agent中的協(xié)同研究

MAS由一組具有自治性、主動(dòng)性、反應(yīng)性、社會(huì)性等特征的Agent組成，能夠自然、貼切、直觀地表示顯式世界中的計(jì)算實(shí)體及問(wèn)題求解方式，成為解決動(dòng)態(tài)環(huán)境中求解問(wèn)題的重要方式。但由于Agent 能力和資源受限，Agent 需要相互協(xié)同來(lái)完成系統(tǒng)目標(biāo)，因此要構(gòu)建一個(gè)有效的MAS，需要詳細(xì)分析和設(shè)計(jì)系統(tǒng)內(nèi)的協(xié)同過(guò)程，通過(guò)Agent協(xié)同合作去研究解決一些復(fù)雜的優(yōu)化問(wèn)題。

Agent存在語(yǔ)法、控制及語(yǔ)義上的異構(gòu)；Agent的個(gè)數(shù)、能力、規(guī)劃及拓?fù)錂C(jī)構(gòu)可能是動(dòng)態(tài)的；Agent的“心理”狀態(tài)不可預(yù)測(cè)。以上特征增加了MAS協(xié)同合作的復(fù)雜性。

目前提出的解決MAS中協(xié)同問(wèn)題的關(guān)鍵方法有如下三種：

（1）組織協(xié)同。采取組織的、分層組織的結(jié)構(gòu)，提供一個(gè)具有系統(tǒng)視野的主Agent，由它來(lái)解決各個(gè)Agent的沖突，確保系統(tǒng)行為一致。主Agent通過(guò)從Agent組收集信息、創(chuàng)建計(jì)劃、向Agent分配任務(wù)來(lái)確保全局一致。主Agent始終是系統(tǒng)中起決定作用的序參量。隨著各Agent復(fù)雜性和動(dòng)態(tài)性的增加，控制的瓶頸問(wèn)題也愈加突出，一旦控制全局的主Agent崩潰，將導(dǎo)致整個(gè)系統(tǒng)崩潰。

（2）為了協(xié)同的合約。合同網(wǎng)協(xié)議（CNET）是最著名的協(xié)同合約。采取市場(chǎng)機(jī)制，通過(guò)任務(wù)共享實(shí)現(xiàn)有效合作，并引入不遵守承諾的懲罰措施，利用金融選擇定價(jià)理論獲得在不確定性環(huán)境中的靈活協(xié)同方案。

（3）為了協(xié)同的規(guī)劃。將協(xié)同問(wèn)題抽象成規(guī)劃問(wèn)題，目前存在集中式和分布式兩種Agent規(guī)劃模型。規(guī)劃需要節(jié)點(diǎn)共享和處理大量的信息，所以涉及到更多的計(jì)算和通信。

上述方法有一定的適用性但都存在局限。而協(xié)同學(xué)理論認(rèn)為，在混沌的運(yùn)動(dòng)階段，系統(tǒng)中有數(shù)個(gè)序參量交互起作用，以此推動(dòng)著結(jié)構(gòu)形成的過(guò)程。在結(jié)構(gòu)形成過(guò)程中，不是在始終地增加無(wú)序，而是把后來(lái)無(wú)序的各個(gè)部分吸引到已存在的有序狀態(tài)中來(lái)，最終促成結(jié)構(gòu)的協(xié)同。本文認(rèn)為Multi－Agent協(xié)作完成復(fù)雜任務(wù)的過(guò)程與此類(lèi)似，可以應(yīng)用該理論研究Multi－Agent在任務(wù)完成的協(xié)同過(guò)程。

在Multi－Agent系統(tǒng)中，由于Agent能力的差別，某個(gè)分階段任務(wù)的完成過(guò)程中，將由某個(gè)特定的Agent主宰任務(wù)的執(zhí)行，即成為系統(tǒng)的序參量。由該Agent利用全局Agent的知識(shí)來(lái)選擇合作伙伴，完成任務(wù)。當(dāng)該階段任務(wù)完成后，其他Agent成為新的“領(lǐng)導(dǎo)者”。Agent的交替領(lǐng)導(dǎo)過(guò)程中，系統(tǒng)結(jié)構(gòu)由一個(gè)穩(wěn)定狀態(tài)向另一個(gè)穩(wěn)定狀態(tài)變化，推進(jìn)著Agent之間的合作，實(shí)現(xiàn)整體目標(biāo)。

3基于協(xié)同學(xué)的Multi－Agent協(xié)同模型

4模型分析

在MAS協(xié)同過(guò)程中，隨著外界環(huán)境的變化以及系統(tǒng)任務(wù)的進(jìn)展，在不同的階段，系統(tǒng)需要不同的協(xié)調(diào)方法來(lái)指導(dǎo)Agent間的協(xié)調(diào)合作。這些特點(diǎn)符合自組織系統(tǒng)演變的開(kāi)放性和遠(yuǎn)離平衡態(tài)的條件。按照自組織的理論在系統(tǒng)由無(wú)序到有序、再由有序演變到更高的有序狀態(tài)，需要新的序參量來(lái)引起系統(tǒng)的演化。所以本文認(rèn)為在Multi－Agent協(xié)同完成一個(gè)復(fù)雜任務(wù)中，協(xié)同任務(wù)的完成需要不斷適應(yīng)外界和自身的變化，從而確立Agent的任務(wù)目標(biāo)，優(yōu)化協(xié)同效應(yīng)，調(diào)整努力程度和行為模式。

因此在任務(wù)完成過(guò)程中，為使協(xié)同效應(yīng)q最大化，優(yōu)化矩陣A及矩陣B1，B2，…，Bn元素的取值，然后根據(jù)矩陣的取值來(lái)指導(dǎo)各個(gè)Agent的行為模式，以此達(dá)到Multi－Agent協(xié)同的優(yōu)勢(shì)互補(bǔ)。如果有多種協(xié)同方法可以采用，那么可以通過(guò)對(duì)機(jī)制參數(shù)轉(zhuǎn)換為式（7）中的矩陣參數(shù)來(lái)評(píng)價(jià)各個(gè)方法的協(xié)同效應(yīng)，選擇最優(yōu)的協(xié)同方法，在時(shí)間、空間等資源的約束下達(dá)到整體協(xié)同效應(yīng)的最優(yōu)化。該模型適用于完成復(fù)雜實(shí)時(shí)任務(wù)的MAS，它是隨環(huán)境變化自適應(yīng)調(diào)整行為的動(dòng)態(tài)模型。

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

在Multi－Agent合作研究中引入?yún)f(xié)同學(xué)理論，給出了基于協(xié)同學(xué)的Multi－Agent的協(xié)同合作模型。將MAS中各Agent的能力、目標(biāo)量化為影響協(xié)同結(jié)果的變量，將協(xié)同機(jī)制量化為序參量。各參量共同作用，促使系統(tǒng)有序結(jié)構(gòu)的形成，最終達(dá)到Multi－Agent協(xié)同合作的目標(biāo)。該模型能夠較好地解決MAS中能力、目標(biāo)的異構(gòu)，實(shí)現(xiàn)任務(wù)的協(xié)同解決，是隨環(huán)境變化自適應(yīng)調(diào)整行為的動(dòng)態(tài)模型，評(píng)價(jià)不同協(xié)同機(jī)制對(duì)Agent任務(wù)完成的協(xié)調(diào)程度，為最優(yōu)協(xié)調(diào)機(jī)制的選擇提供了依據(jù)。本文首次將協(xié)同學(xué)中的序參量、自組織等理論引入到MAS合作中，為MAS合作問(wèn)題的解決提供了新的方式。

參考文獻(xiàn)：

［1］

哈肯 H.高等協(xié)同學(xué)[M].郭治安，譯.北京:科學(xué)出版社，1989:2－3.

[2]D’ INVERNO M， LUCK M， WOOLDRIDGER M. Cooperation structures:the 15th International Joint Conference on Artificial Intelligence[C].[S.l.]:[s.n.]，1997:600－605.

[3]李常洪，李敏強(qiáng)，寇紀(jì)淞. Multi－Agent合作結(jié)構(gòu)研究[J].管理科學(xué)學(xué)報(bào)，2003，6(5):6－11.

[4]胡旦華，馬永光，張宇晴.Multi－Agent系統(tǒng)中合作策略的研究[J].計(jì)算機(jī)仿真，2004，21（3）:130－132.

[5]劉越，陳火旺，王懷民. 一種漸進(jìn)式Multi－Agent合作理論[J].計(jì)算機(jī)學(xué)報(bào)，2003，26(4):454－459.

[6]ZHEN Hua. Study of multi－agent cooperation：proceedings of International Conference on Machine Learning and Cybernetics[C].[S.l.]:[s.n.]，2004:3014－3017.

[7]LARGE E W，CHRISTENSEN H I， BAJCSY R.Dynamic robot planning:cooperation through competition:IEEE International Conference on Robotics and Automation[C].[S.l.]:[s.n.]，1997:2306－2311.

[8]LI Changhong，LI Minqiang， KOU Jisong. Cooperation structure of multi－agent and algorithms:IEEE International Conference on AIS[C].[S.l.]:[s.n.]，2002:303－307.

[9]張嗣瀛.復(fù)雜性科學(xué)，整體規(guī)律與定性研究[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2005，2(1):71－83.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”