基于協同學的Ｍｕｌｔｉ－Ａｇｅｎｔ合作系統研究

摘要：探討了協同學在Multi－Agent系統（MAS）合作中的應用；討論了MAS的協同合作，給出了基于協同學的Multi－Agent的協同模型，量化了Multi－Agent協同機制的協調效應，為其最優協同機制的選擇提供了依據。將序參量、自組織理論引入到MAS合作中，為MAS合作問題提供了一個新的解決思路。

關鍵詞：協同學；多代理;自組織;序參量

中圖分類號：TP301文獻標志碼：A

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



協同學是研究由完全不同性質的大量子系統（如電子、原子、細胞、神經原、力學元、光子、器官、動物乃至人類）所構成的各種系統，研究這些子系統是如何通過合作在宏觀尺度上產生空間、時間或功能結構[1]。協同是系統中諸多子系統相互協調、合作或同步的聯合作用，是系統整體性、相關性的內在表現。協同學是以系統論、信息論、控制論、突變論等為基礎，采用統計學和動力學相結合的辦法，通過類比分析，建立一整套數學模型和處理方法來研究協同系統從無序到有序的演變規律。合作問題是協同學研究的一個重要問題。

Multi－Agent系統（MAS）由分布在網絡上的多個Agent松散耦合成。通過Agent之間的相互合作以解決單一Agent能力和知識所不能處理的復雜問題。Agent合作是MAS最基本的特征，因此Multi－Agent合作機制成為MAS研究的一項重要內容。文獻[2]中提出兩種Multi－Agent合作結構，即不完全合作結構和完全合作結構；在此基礎上文獻[3]從“是否完全合作”“是否存在目標互換”“合作雙方的數量對比”等三個角度把Multi－Agent的合作結構分為16種，但Multi－Agent合作中的不確定性和競爭性使合作問題的研究十分復雜。而協同學中子系統通過競爭達成協同的理論，可以應用于Multi－Agent合作問題中，解決MAS中不同目標、能力的Agent協同一致完成任務。但目前應用協同學思想研究Multi－Agent合作的文獻還沒有，本文把協同學思想引入到Multi－Agent合作中，構建Multi－Agent合作的協同模型，實現整體效用的最大化。

1協同學

1．1幾個重要概念

(1)子系統。協同學將研究的對象稱為系統，而將組成系統的下一層次稱為子系統。在MAS中，每個Agent就是子系統。

(2)序參量。子系統總是存在著自發的無規則的獨立運動，同時又受到其他子系統對它的共同作用、因此存在著子系統之間關聯而形成的協同運動。序參量是系統相變前后所發生的質的飛躍的最突出標志。

(3)自組織。它是在沒有外界因素驅使下，開放式（與環境有物質、能量和信息交換的）系統在其子系統或元素間競爭—合作機制作用下，自發出現新的宏觀（整體）有序結構—時間、空間或功能有序新結構的現象。自組織理論是協同學的核心理論。

1．2協同

協同，就是系統中諸多子系統的相互協調、合作或同步的聯合作用，集體行為。一個復雜的系統，若子系統互相配合產生協同作用和合作效應，系統便處于自組織狀態，系統在宏觀上和整體上表現為具有一定的結構或功能。不同的系統性質會有不同，但都從不同側面揭示了從宏觀到微觀、從機械運動到生物運動的和諧性和協調性。 

協同系統是指由許多子系統組成的、能以自組織方式形成宏觀的空間、時間或功能有序結構的開放系統。系統演化過程中從無到有的變化通過序參量來表示。序參量來源于子系統之間的協同，能夠指示新結構的形成，同時起著支配子系統行為的作用。協同學認為，一個系統從無序到有序轉換的關鍵在于由一個大量子系統構成的開放系統內部發生的協同作用。它強調系統內部的關聯及系統發生變化時要素間的互相配合與耦合。

可以從協同成員對協同活動的貢獻、對各自觀點的表達方式上將協同方式分為以下三種：①協商（或對策）方式。②合作的方式。這種方式的協同工作可以描述成一個協作群體共同解決一個（或多個）問題，或協作完成一項（或多項）共同的任務。③創造的方式。

2Multi－Agent中的協同研究

MAS由一組具有自治性、主動性、反應性、社會性等特征的Agent組成，能夠自然、貼切、直觀地表示顯式世界中的計算實體及問題求解方式，成為解決動態環境中求解問題的重要方式。但由于Agent 能力和資源受限，Agent 需要相互協同來完成系統目標，因此要構建一個有效的MAS，需要詳細分析和設計系統內的協同過程，通過Agent協同合作去研究解決一些復雜的優化問題。

Agent存在語法、控制及語義上的異構；Agent的個數、能力、規劃及拓撲機構可能是動態的；Agent的“心理”狀態不可預測。以上特征增加了MAS協同合作的復雜性。

目前提出的解決MAS中協同問題的關鍵方法有如下三種：

（1）組織協同。采取組織的、分層組織的結構，提供一個具有系統視野的主Agent，由它來解決各個Agent的沖突，確保系統行為一致。主Agent通過從Agent組收集信息、創建計劃、向Agent分配任務來確保全局一致。主Agent始終是系統中起決定作用的序參量。隨著各Agent復雜性和動態性的增加，控制的瓶頸問題也愈加突出，一旦控制全局的主Agent崩潰，將導致整個系統崩潰。

（2）為了協同的合約。合同網協議（CNET）是最著名的協同合約。采取市場機制，通過任務共享實現有效合作，并引入不遵守承諾的懲罰措施，利用金融選擇定價理論獲得在不確定性環境中的靈活協同方案。

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

上述方法有一定的適用性但都存在局限。而協同學理論認為，在混沌的運動階段，系統中有數個序參量交互起作用，以此推動著結構形成的過程。在結構形成過程中，不是在始終地增加無序，而是把后來無序的各個部分吸引到已存在的有序狀態中來，最終促成結構的協同。本文認為Multi－Agent協作完成復雜任務的過程與此類似，可以應用該理論研究Multi－Agent在任務完成的協同過程。

在Multi－Agent系統中，由于Agent能力的差別，某個分階段任務的完成過程中，將由某個特定的Agent主宰任務的執行，即成為系統的序參量。由該Agent利用全局Agent的知識來選擇合作伙伴，完成任務。當該階段任務完成后，其他Agent成為新的“領導者”。Agent的交替領導過程中，系統結構由一個穩定狀態向另一個穩定狀態變化，推進著Agent之間的合作，實現整體目標。

3基于協同學的Multi－Agent協同模型

4模型分析

在MAS協同過程中，隨著外界環境的變化以及系統任務的進展，在不同的階段，系統需要不同的協調方法來指導Agent間的協調合作。這些特點符合自組織系統演變的開放性和遠離平衡態的條件。按照自組織的理論在系統由無序到有序、再由有序演變到更高的有序狀態，需要新的序參量來引起系統的演化。所以本文認為在Multi－Agent協同完成一個復雜任務中，協同任務的完成需要不斷適應外界和自身的變化，從而確立Agent的任務目標，優化協同效應，調整努力程度和行為模式。

因此在任務完成過程中，為使協同效應q最大化，優化矩陣A及矩陣B1，B2，…，Bn元素的取值，然后根據矩陣的取值來指導各個Agent的行為模式，以此達到Multi－Agent協同的優勢互補。如果有多種協同方法可以采用，那么可以通過對機制參數轉換為式（7）中的矩陣參數來評價各個方法的協同效應，選擇最優的協同方法，在時間、空間等資源的約束下達到整體協同效應的最優化。該模型適用于完成復雜實時任務的MAS，它是隨環境變化自適應調整行為的動態模型。

5結束語

在Multi－Agent合作研究中引入協同學理論，給出了基于協同學的Multi－Agent的協同合作模型。將MAS中各Agent的能力、目標量化為影響協同結果的變量，將協同機制量化為序參量。各參量共同作用，促使系統有序結構的形成，最終達到Multi－Agent協同合作的目標。該模型能夠較好地解決MAS中能力、目標的異構，實現任務的協同解決，是隨環境變化自適應調整行為的動態模型，評價不同協同機制對Agent任務完成的協調程度，為最優協調機制的選擇提供了依據。本文首次將協同學中的序參量、自組織等理論引入到MAS合作中，為MAS合作問題的解決提供了新的方式。

參考文獻：

［1］

哈肯 H.高等協同學[M].郭治安，譯.北京:科學出版社，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]李常洪，李敏強，寇紀淞. Multi－Agent合作結構研究[J].管理科學學報，2003，6(5):6－11.

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

[5]劉越，陳火旺，王懷民. 一種漸進式Multi－Agent合作理論[J].計算機學報，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]張嗣瀛.復雜性科學，整體規律與定性研究[J].復雜系統與復雜性科學，2005，2(1):71－83.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”