1.4　制造系統的協調機制

通過對制造控制系統結構的演變分析可以看出，在復雜的、充滿不確定性擾動的動態制造環境中，合理的控制結構非常重要。但是隨著控制系統規模變大、結構變復雜，良好的協調機制和方法將對促使控制系統正常工作、提高制造系統的自適應性、控制的敏捷性和穩健性等起到至關重要的作用。

1.4.1　協調的基本概念

從廣義上來說，所謂協調就是多個事物對相互之間依賴關系的管理，這對于群體活動的有序進行具有重要作用。協調活動廣泛地存在于人類社會中，但是專門針對協調活動機制和原理的研究是源于人工智能（特別是多智能體系統）的研究需要。隨著需要求解問題規模的擴大，各因素之間的依賴關系和協調活動就會凸顯出愈發重要的地位。對于規模較大的問題，單個求解器（如個人、組織機構、動物、局部控制器等，以下以Agent代稱）往往缺乏足夠的資源、信息及能力去獨立解決問題，這就需要在合理分解問題的基礎上尋求多個具有不同資源、信息和能力的Agent共同完成全局問題的求解工作。由于各個子問題均是由全局問題分解而來的，它們相互之間既相對獨立，又相互關聯，這也導致各個Agent的子問題求解活動之間必然存在著相互依賴的關系，從而有機地構成了全局問題的求解過程。因此，對大規模問題的求解來說，協調活動是不可或缺的。

存在依賴關系且用來求解子問題的單個Agent為了將各自所解得的結果合并成為最終的全局解，需要通過交互以便協調各自行為，避免混亂和沖突，并達到最終的一致。在全局問題求解過程中，各Agent所擁有的信息、資源和能力均不同，其各自的目標也各有差異，因此，其行為方式各不相同，若無法達成一致，則可能演變成無序、沖突、混沌的狀態，從而使局勢往不利于求解全局問題的方向發展。而通過交互，個體Agent可以在處理自己任務的同時，及時了解其他Agent正在執行或將要執行的動作，并依據這些信息對自身的行為做出調整，最大化自己的效用函數并完成目標任務。Agent之間的信息交互往往是帶有目的性的，很多時候都是為了改變周圍Agent，對它們發出協調請求，影響接收方將來的行動。

協調技術與數據通信及中間件技術是有區別的。數據通信僅僅表示控制實體之間數據信息的傳遞過程，中間件技術則是指各個控制組件在動態開發系統中實現對等通信的技術，它們只強調過程而不關心信息交互后產生的后果。而協調技術強調的是借助信息交互后產生的對交互對象行為的相互影響，以及由此帶來的整體局勢的變化，并且，這種全局變化通常在協調活動開始之前就已經被作為協調的目標預見到了。

因此，良好的協調活動可以促使個體更好地認清局勢，采取與周邊個體協調一致的動作，使整體行為趨向于有序，以利于全局問題的求解，提升控制系統整體的性能，增強控制系統解決問題的能力，使智能控制系統可以處理更多的實際問題。而在制造系統控制領域中，協調的定義就是指制造系統的各個制造單元根據各自目標，在對已經擁有的資源進行合理安排的前提下，按照某種事先約定的規則進行相互協調，調節自身局部行為與全局總體目標之間的差異，使整個制造系統的生產活動從混沌轉為有序，通過協同工作，快速、有效地完成制造系統的制造任務。

1.4.2　協調機制的分類

協調機制是指多個子問題求解器Agent之間進行信息交互，并因此決定自己行為時所共同約定的規則。設計良好的協調機制可以有效調節各個Agent之間的行為，快速有效地抓住子問題與全局問題之間依賴關系中的主要矛盾，引導求解系統的局勢向有利于解決問題的大方向進化，最終使整個智能控制系統獲得優良的系統性能。因此，如何合理選擇和設計高效的協調機制，對于完成復雜系統的控制、改善系統的綜合性能具有至關重要的意義。

協調機制的分類如圖1.7所示，它是按照制造控制系統中的控制實體進行協調活動時相互通信的方式。本節將協調機制研究文獻中的常用方法進行了歸納和分類，其主要分為：顯式協調機制（Explicit Coordination）、隱式協調機制（Implicit Coordination）和其他形式協調機制。

1. 顯式協調機制（Explicit Coordination）

所謂顯式協調機制，就是制造控制系統中的各個控制實體在遵循共同約定的行為準則的前提下，通過信息傳遞明確表現出自身意圖的協調機制。在顯式協調機制工作過程中，控制實體之間必須進行交互，因此，首先，其必須具有通信模塊（有時會很復雜）。而單個控制實體做決策時往往也需要參考來自周圍控制實體的信息，導致其控制結構會變得復雜。但是，在制造系統協調過程中使用顯式協調機制時，參與協調的控制實體是允許拒絕別的控制實體的協調請求的，這就使各個控制實體可以具有各自不一樣的目標，從而使顯式協調機制既可以用于分布式制造系統的協調問題，也可以應用于各種動態開放的環境中。典型的方法主要有合同網協議（Contact Net Protocol，CNP）和拍賣機制等。

（1）合同網協議

CNP（合同網協議）是由Smith和Davis為了解決分布式問題求解系統的任務分配問題所提出的一種協調機制，其最早應用于傳感器的分布控制系統。當前，在制造領域的各個方面，CNP及改進式CNP得到了非常廣泛的應用，如車間調度、機械人協調、物流系統調控等，Caridi等人在其關于Multi-Agent系統的綜述中也指出，CNP的使用比例達到了53%。

CNP是模擬市場經濟中的投標機制，規定了控制實體的交換意圖過程。在使用CNP協議時，需要首先定義兩種重要的Agent：管理Agent和資源Agent。其中，管理Agent負責接收上級任務，然后進行評價，判斷是否可以由單個Agent獨立完成，若無法獨立完成，則向其余資源Agent發布任務標書。收到標書的資源Agent對任務招標信息進行評價，并對有能力完成的任務標書進行投標，否則繼續等待。管理Agent對返回的標書進行評價，并選出最優者，向其發出中標信息。雙方再次經過一輪協商確認后，簽訂最后協議，然后分配任務。

CNP運行的基礎和核心就是投標機制，其在制造系統調度領域中常用的投標策略主要分為面向工件的投標策略、面向資源的投標策略，以及面向工件和資源的雙向投標策略，其主要特征見表1.2。

雖然CNP在很多方面具有優點，但由于沒有很好地定義其協議范圍，導致其全局優化能力欠缺，并且難以預測系統性能。因此，為了改進CNP，建立更合適的協商框架，減少通信數據量，提高協調效率，使其可以應用于更多的場合，眾多專家學者對其進行研究，并陸續提出了大量的改進型合同網模型。例如，國際Agent技術推廣協會FIPA（The Foundation for Intelligent Physical Agents）在研究基于Agent應用的交互規范時，提出了迭代合同網協議，提高了多Agent協商的效率；日本學者Takuya在其研究中提出了通過范例推理的方法來減少協調過程中的通信總量；有的學者拓展了招標步驟，針對任務目標預先模擬招標，之后再根據評價進入協商過程，從而進一步優化了系統性能；或是對招標結果根據目標函數進行一定的修正，從而提高了改進后CNP的工作效率；通過對Multi-Agent系統中具有時間窗口的多AGV（Automated Guided Vehicle，自動導引小車）路線規劃問題進行研究，有學者提出了允許解除承諾的改進型CNP，提高了系統的整體運行性能。但是，CNP僅僅是對工作流程的一種規定，本身并不具有優化能力，且在協調過程中仍然不可避免地存在著通信量大、不確定性突出、耗費大量通信資源及可能引起死鎖等問題。

（2）拍賣機制

拍賣機制是一種在信息不完全情況下的靜態博弈，即拍賣方在給定自己的類型，以及給定其他參與人的類型與戰略選擇之間關系的條件下，使自己的期望效用最大化。在應用拍賣機制協商時，其中參與的各方Agent均是秉承自利原則的，拍賣方希望通過拍賣的方式將任務所要實現的目標最優化，而投標方則希望通過拍賣的過程以最小的消耗完成最多的任務。在研究拍賣型協調機制并改良其性能的過程中，人們主要是針對拍賣規則進行改進，研究買賣雙方所使用的策略，分析拍賣方法的性能。根據具體應用環境的變化和拍賣規則的不同，基于拍賣機制的協調方法可以有多種不同的規則，如Sandholm的多策略組合拍賣機制，FIPA組織提出的荷蘭式和英式標準化拍賣規則等。

除此以外，還有很多其他類似市場拍賣的協調機制，如通過對分布式制造環境下的制造加工任務的成本，計算出對應任務報價，應用基于價格模型的協商機制在制造Agent中對制造加工任務進行分配。通常情況下，對這種基于市場拍賣模型的協調機制來說，價格是主控因素，當參與協調任務的Agent數量增多時，可能會導致協同收斂過程變得緩慢，但是可以通過引入其他控制要素進行調節。

2. 隱式協調機制（Implicit Coordination）

所謂隱式協調機制，是指參與協調控制的各個Agent之間的交互方式與傳統的需要明確表示自身目的的顯示通信相反的通信協調方式，即它們相互之間并不發送明確的符號信息，甚至都不知道相互之間的存在，只是根據某些事先內部建立的完整的合作機制，依據系統中的各種“暗示”，各自進行活動。這樣可以保證單個Agent在處理局部問題上的自治性，又可以在一定程度上使其行為有利于全局目標，能為系統的群體利益做出貢獻。隱式協調機制是以某種隱式定義和系統中各Agent公認的規則作為單個Agent的行為邏輯，并以此為基礎對系統中的各Agent進行協調控制的機制，其可以保證系統中的各個Agent之間在不通過任何形式的形式化通信的前提下進行信息交互。一個典型的隱式協調應用范例是運用在現代數學分支學科—運籌學的博弈論中的各種協作機制，而另一個則是在一些群居的低等動物（如螞蟻、蜜蜂等）組成的社會群體中基于信息素的Stigmergic協商機制。

在這些由膜翅目或等翅目的昆蟲組成的低等動物社會群體中，昆蟲個體并不借助語言進行溝通，而是通過每個個體根據自身接收周邊環境的刺激而自發分泌出來的某種化學物質—信息素來相互交換信息，以此進行溝通。獨立的個體所釋放的信息素在其活動的環境中被整合，其他個體則依據環境中所能感知到的信息素強度來決定自己的行為動作。比如，昆蟲個體通過釋放性激素來告知群體的各個異性昆蟲“我準備好了”；蜂群或蟻群在遇到襲擊或入侵時，會釋放報警信息素（Alarm Pheromone）來通知整個群體對攻擊者或入侵者進行反擊行動；蜜蜂在發現蜜源后會在蜜源周圍釋放標記信息素（Labeling Pheromone），用以指示其他蜜蜂可以更快速地尋找到該處蜜源。由此可見，雖然群體中的每個個體之間沒有語言通信，但是，借助釋放在環境中的信息素的調節作用，螞蟻、蜜蜂等群居類昆蟲可以有效地引導個體快速地融入當前群體所需要的整體目標中，從而實現群體中個體的彼此行為的協調。雖然這些弱小的個體獨立生存能力很差，基本無法獨立生存，但僅依靠“感知—動作”這種個體本能動作，可以在信息素的幫助下，使數目龐大的個體形成一個可以有條不紊完成各種復雜任務，具有穩定有效協調合作秩序的群體，并在漫長的自然淘汰中存活下來，這直接證明了隱式協調機制的強大效能。

1956年，法國動物學家Grasse在對群居的昆蟲社會的運作機理進行深入研究后，專門構建了一個新詞—Stigmergic來表征昆蟲社會中這種利用非符號的異步交互方式，隨后，越來越多的研究者發現群居昆蟲社會中的這種基于隱式協調機制的調節方式在協調合作和群體秩序等方面有很多優秀的屬性。例如，參與隱式協調的Agent由于采用的是非符號式通信手段，其無須進行復雜的通信及信息處理，只需要一個簡單的行為決策模塊，因而其結構比較簡單。同時，昆蟲社會隱式協調機制成功的關鍵在于每個個體的利他原則，即Agent個體并不包含協調策略，其個體決策準則就是不計較個體利益，而是以便利地與他人協調為目的，這樣可以保證整個團體的穩定運作。因此，如何有效利用這種簡單的隱式協調機制已成為人工智能領域的一個研究熱點。

比如，將Stigmergic隱式協調機制應用到單電子隧道技術中的計算空間優化分配等方面，提高了計算效率。而在多臺機器人的任務協調分工方面應用了基于Stigmergic隱式協調機制進行優化分工。有的學者針對單元制造系統（Celluar Manufacturing System，CMS）中的多單元協作加工問題，提出了基于信息素的柔性路徑加工調度方法，利用Stigmergic協商機制建立了基于Multi-Agent的單元制造系統模型，并通過實驗驗證了Stigmergic協商機制的優化性能及系統良好的穩健性。而在車間控制系統層面上，有學者將基于激素的協商機制應用于其中，并以此為基礎建立了原型系統，驗證了Stigmergic協商機制在混合流水車間的控制系統中的應用，并取得了良好的效果。在Holonic制造系統中，研究者通過模擬螞蟻覓食的過程，提出了基于Stigmergic協商機制的制造控制系統，并通過案例仿真證明了基于Stigmergic的協商機制具有良好的任務優化能力，以及針對動態環境的自適應能力，指出其更適用于處理制造系統中的動態突發事件，或是利用RFID技術和基于Stigmergic的簡易機器人控制策略模型，通過大量實驗驗證在多機器人環境下該控制方法的可行性和高效性。

通過上述分析可以看出，基于Stigmergic的隱式協調機制采用的是非符號方式的通信，其通信負荷較低，內建的協調機制以利他性為原則，具有較高的優化性能和良好的自適應特性。而且，根據眾多研究應用可知基于Stigmergic的隱式協調機制還具有以下幾個主要特點：①環境是解的一部分，其不僅充當了信息傳遞的媒介，還起到了總合的作用，同時還隱含了系統的復雜性和動態性；②全局信息局部化，系統中各Agent給出的信息僅表達了局部信息，而其獲取的信息也非全局信息，而是局部環境中多個Agent給出的信息總和；③信息的獲取和給出不需要在時間上具有確定的對應關系，即采取的是異步通信方式。

通過對基于CNP的顯示協調機制和基于Stigmergic的隱式協調機制進行定性的對比分析可以發現：基于Stigmergic的隱式協調機制在系統目標的優化能力、系統計算負荷、通信負荷和消除系統內部變動所產生的漣漪效應等方面具有較大的優勢，但是，相比CNP，其在制造系統資源負荷平衡、針對任務變動的適應性及系統針對不同領域Agent的開放性等方面相對較弱。同時，在研究基于Stigmergic的隱式協調機制過程中，如何通過系統參數與獎懲算法的合理設計來加快系統適應過程也一直是本領域的研究熱點和難點。

3. 其他形式協調機制

針對半導體生產調度中批量生產交貨期問題，有學者提出了Look-Ahead任務協調分配策略，使批量生產下的交貨期問題得到了優化處理。針對協調分布式車輛檢測測試系統中的Agent，有研究者提出了PGP（Partial Global Planning）方法，利用其給各個Agent提供局部規劃，然后由各個Agent之間進行合作，交換各自的局部規劃來求解全局問題，進而完成總體目標。后來美國的Decker等人在PGP的基礎上進一步完善和擴展了其協調內容和方法，提出了GPGP（Generalized Partial Global Planning）協調規劃方法，利用模塊化的協商方式和圖形化任務描述語言TAEMS（Task Analysis，Environment Modeling and Simulation），為Multi-Agent系統提供動態的柔性協調方案和信息表達工具。在針對并行機協調調度問題研究中，將分支定界法與拉格朗日松弛法（Lagrangian Relaxation，LR）相結合的混合算法應用于其中，獲得良好的實驗結果。在柔性制造系統中，應用改進型的時間Petri網方法進行協調控制，并通過評價任務序列等待時間等指標來提高制造系統的快速響應性等性能；并且在分布式制造系統的協調調度中，也嘗試將混合Petri網方法應用于其中，這樣能夠有效地解決并行制造中的相關問題。

1.4.3　協調機制形式化描述方法

所謂制造系統協調機制的形式化描述，就是用具有嚴格語法和精確語義的描述能力足夠強的語言，對協調過程的并行性進行建模和分析，并能夠利用這種表達方式驗證和轉換交互協議的靜態和動態模型，其最終表述應該邏輯性強，簡單易懂，具有相應的工具支持。這也是形式化描述運用這些協調機制的現代制造系統體系結構的基礎。

目前，經常用于描述協調機制的典型方法有π演算、增強Dooley圖（Enhanced Dooley Graphs）、CPN（Colored Petri Nets）、AUML（Agent Unified Modeling Language）、STD（State Transition Diagrams）和DFA（Deterministic Finite Automata）等。

π演算是進程代數的一種，具有良好的數學和邏輯框架，可以對并行系統內部具有動態結構的進程及進程間的交互進行描述和分析，但難以對Agent模型進行形象的表述。Dooley圖可以詳細地表述Agent的各種狀態信息，但其無法對進程中的并行交互行為進行描述。CPN是一種基于圖形化的建模工具，對于描述分布式系統和并行系統中的交互協議非常適合，但其同樣缺乏針對單獨Agent描述的模塊化概念，并且當系統規模變大、復雜程度增加時，利用CPN進行建模描述時會產生狀態爆炸現象。STD表述簡潔，在對自治單元之間交互協議的描述中經常用到，但其對交互時間需要有確定的對應關系，即無法對異步通信形式進行表達，無法表示協議的集成。DFA可以在對Agent交互協議進行建模的同時對其進行驗證，但是面對復雜的Agent交互過程則顯得力不從心。