多智能體群集系統分群行為研究進展

李成鳳， 張陽偉， 邵俊倩， 高 亮

(綏化學院，a.電氣工程學院; b.信息工程學院，黑龍江 綏化 152000)

0 引言

群集是自然界中普遍存在的一種現象[1]，受此啟發(fā)，多智能體系統的群集行為近年來也成為多智能體系統研究中的熱點問題[2]。隨著研究的深入，學者們發(fā)現完備的群集系統協同行為應分為組群和分群兩種形式。其中：組群是傳統意義上的群集行為，即要求某一區(qū)域內隨機分布的多個智能體能無碰撞地聚集并以相同的速度和運動方向共同執(zhí)行任務；而分群則是群集系統在各類分群誘因作用下分裂成為若干個子群的行為[3]。目前，對群集系統組群行為的研究已經取得了豐碩的成果，而對分群控制的研究仍處于初步開展階段，并主要集中在理想環(huán)境下分群算法的研究。鑒于此，本文將從系統組成、信息交互機制及分群的穩(wěn)定性分析方法3個角度對分群行為的研究現狀進行總結及分析，以期對分群控制的研究起到促進作用。

1 群集系統的組成

在研究群集系統分群行為時，首先要明確系統的組成。一般從構成群集系統的智能體異同角度來說，能夠實現分群的群集系統主要可以分為異構群集系統和同構群集系統兩類。

1.1 基于異構的群集系統分群

異構群集系統是指群體中的智能體之間存在結構或功能上的差異，如配備不同的傳感器導致感知能力不同，或物理屬性的差異導致動力學模型不同，但正是這些差異使得異構群集系統能夠完成相對復雜的任務[4]?，F對異構群集系統的分群研究成果進行總結，相關簡介見表1。表中：d為期望間距;r為感知半徑。

表1 異構群集系統的分群研究成果

文獻[5]智能體的異構體現為期望間距和感知范圍不同，提出了具有多個虛擬領導者的群集算法，認為分群可看作是相鄰個體或個體與虛擬靜態(tài)/動態(tài)障礙物之間的避障問題，且期望距離在分群過程中起關鍵作用。雖然該算法能夠有效地實現分群，但各子群卻需要按照期望間距事先劃分。

文獻[6]借鑒異質細胞的差異黏附模型，使個體間的差異體現在相互作用勢能上，即同類型個體、不同類型個體之間的相互作用勢能具有不同參數值，實現了兩種異構智能體的分群控制，但所設計的算法存在易陷入局部極小而導致分群失敗的問題。

文獻[7]提出了新型的勢能函數，進一步實現了具有多種類型的異構機器人的分群控制，并解決了文獻[6]的算法失效問題，但僅實現了全局交互下同等子群規(guī)模的分群行為。

文獻[8]受巴西果效應啟發(fā)，設計了每個個體的運動由隨機游動、趨同性和被其他個體排斥3種反應行為控制，從而實現了由不同虛擬尺寸機器人組成的異構群集系統的自組織分群行為。

文獻[9]基于粒子群算法(PSO)和最優(yōu)交互避碰(ORCA)算法，設計了具有多種類型的異構機器人分群算法，能夠實現任意子群規(guī)模、任意子群數量的分群，但未能給出算法的收斂性證明。

文獻[10]中個體差異體現在感知距離、期望距離和目標不同，II型智能體用于獲取真實目標信息并主動跟蹤真實目標，I型智能體僅需要給定的II型智能體信息以輔助II型智能體，對兩類智能體分別設計基于Reynolds規(guī)則[11]的控制輸入，實現分群跟蹤。但每個I型智能體所跟蹤的II型智能體也是事先分配的，即子群是事先劃分的。

1.2 基于同構的群集系統分群

同構的群集是指構成群集系統的所有智能體都被假設具有相同的模型結構和功能。目前基于同構假設的分群文獻居多，如文獻[12-22]均假設個體無差別，均具有相同的數學模型和環(huán)境感知能力等。與異構群集系統依靠異構屬性進行分群不同，由于個體無差別，故需引入不同分群誘因來實現分群目的?，F將同構群集系統的分群研究成果進行總結，相關簡介見表2。

表2 同構群集系統的分群研究成果

文獻[12]中設計距離概率項和概率密度項作為個體進行領導者選擇的依據，文獻[13]中個體利用蟻群算法規(guī)則選擇所要跟隨的領導者，并分別基于同一子群個體間和不同子群個體間的勢能函數設計控制策略，使群體分裂成跟蹤不同領導者的子群。但領導者作用范圍為全局，這與實際生物群體和工程應用相悖[23]，因此只適用于小規(guī)模的群集。此外，文獻[13]中個體根據接收到的領導者子群規(guī)模需求信息和周圍鄰居跟蹤不同領導者的情況選擇領導者，因此，需要個體具有一定的通信能力。

文獻[14]提出了基于領導者-跟隨者的分群控制算法，其中的領導者是群體中的真實個體，根據跟隨者到不同領導者的層級大小，采用廣播應答形式實現子群規(guī)?？煽氐姆秩嚎刂?，但既需廣播又需應答的信息交互增加了個體之間交互的復雜度，因此僅適合于具有廣播應答條件的小規(guī)模分群。

文獻[15-21]中的分群誘因均為外界環(huán)境刺激(如障礙物、危險等)，通過設計使邊緣個體感知到的外界環(huán)境刺激能在群內實現有效快速傳播的信息交互機制，結合經典的“分離-結對-聚集”規(guī)則[1]設計分群算法，實現自組織分群運動。雖然所設計的分群策略對群集的規(guī)模沒有約束，但子群規(guī)模和速度均不可控，僅適用于對稱刺激下等規(guī)模分群。

文獻[24-32]基于群體內部作用實現分群，其中，文獻[24]設計了同子群速度協同力、避免碰撞力和子群內聚力來實現多分群。但子群需事先劃分，因此，需要有高級控制中心進行協調。文獻[25-27]中個體間相互作用為遠程吸引、近程排斥和類高斯中程排斥作用，前兩者實現內聚和避免碰撞，后者實現群體分裂，并通過參數設置實現子群規(guī)模預測和設定。但該方法中每個個體都受預先設定的子群個數、排斥距離等全局分群參數控制，需引入集中式協調機制，故不適合大規(guī)模群集，并且所實現的分群通常為規(guī)模對稱分布的子群，未能實現按任務需求自發(fā)產生相匹配的子群規(guī)模，故其應用范圍有所局限[3]。文獻[28-29]基于內部作用實現二分群(分成速度大小相同、方向相反的兩個子群)。前者設計不同群體之間的作用力和相同群體內部作用力實現分群，后者設計包含排斥-吸引力以及摩擦力的兩群體相互作用模型實現分群。但該類方法僅能實現二分群，使其應用范圍受到較大限制。文獻[30-32]根據內部作用和初始條件約束實現基于C-S模型的分群。文獻[30-31]實現了二分群，受此啟發(fā)，文獻[32]實現了等級C-S模型的多分群，雖然通過計算初始數據，可確定有多少子群出現和哪些個體在同一個子群，但此方法僅在內部作用參數滿足一定條件且初始位置和速度具有有序關系時才能實現分群。因此，需要有高級控制中心對群體的初始狀態(tài)進行協調，不適合大規(guī)模群集。

文獻[33-36]基于合作對抗網絡實現分群，利用符號圖描述個體之間的合作競爭關系。文獻[33]基于合作對抗網絡，利用結構平衡的符號圖理論和指定的勢函數，在虛擬領導者和無領導者的情況下實現了二分群。文獻[34]實現了固定時間的二分群，文獻[35]針對文獻[34]推導過程中存在的缺陷，改進了協議證明推導方法，并降低控制策略參數取值的保守性，推廣了策略的應用范圍。文獻[36]針對文獻[30-34]分群過程中個體之間可能存在碰撞問題，利用新的固定時間穩(wěn)定定理和結構平衡符號圖理論，在固定時間內實現了無碰撞的二分群，并根據協議參數、網絡連通性和系統初始狀態(tài)，估計出每個不連通子群的規(guī)模上限。盡管該類方法能夠實現漸近和固定時間二分群，但群體中的合作對抗關系必須滿足結構平衡的假設條件。因此，需高級控制中心事先確立結構平衡的合作對抗關系，這使其應用范圍在二分群基礎上進一步增加了限制。

2 信息交互機制

與組群行為的形成類似，群集系統分群行為的產生也與智能體之間的信息交互密切相關。目前,分群行為研究中常用的信息交互機制主要包括基于固定鄰居距離的信息交互和選擇性信息交互。

2.1 基于固定鄰居距離的信息交互

基于固定鄰居距離的信息交互是指群集系統中的每個個體均與其感知范圍內的所有其他個體進行信息交互。這是通常意義上的局部信息交互，是群集系統組群行為研究中采用最多的信息交互機制[22]，目前大多數分群控制研究也都繼續(xù)沿用該信息交互機制。采用該機制的優(yōu)勢在于：1)更符合工程實際，因為實際的無人自主控制系統配備的傳感器或通信設備的探測范圍是有限的，個體只能通過傳感器探測到其感知范圍內的其他個體的運動狀態(tài)信息，或利用通信設備進行局部范圍內的信息交互；2)便于進行分群控制方法的理論分析，由于在該信息交互機制下，若個體1為個體2的鄰居，則個體2也為個體1的鄰居，整個群體所構成的信息交互拓撲圖為無向圖，個體的鄰接矩陣是元素為0和1的對稱陣，使得組群控制研究中廣泛使用的鄰接矩陣及拉普拉斯矩陣的對稱性等重要結論在分群控制研究中依然成立，進而可在分群控制中繼續(xù)沿用組群控制中的穩(wěn)定性分析方法。

但群集系統的群體規(guī)模通常較大，若采用基于固定鄰居距離的信息交互機制，個體要與感知范圍內的所有鄰居個體都進行信息交互，容易造成系統通信量過高、計算量過大的問題，進而導致算法速度降低。此外，為實現速度協同，通常采用的以固定鄰居距離的信息交互機制為基礎的速度平均方法，會導致群集系統難以實現應激分群行為[16]。

2.2 選擇性信息交互

與基于固定鄰居距離的信息交互不同，選擇性信息交互不是盲目地與感知范圍內的所有鄰居個體都進行信息交互，而是按照一定的規(guī)則或指標選擇感知范圍內的部分鄰居個體進行信息交互[37]。選擇性交互是在固定鄰居距離的交互基礎上，進一步結合生物群集現象所得出的信息交互機制，已成為多智能體群集研究的一個趨勢。現將選擇性信息交互機制進行總結，并對其各自的交互對象、不足及適用場合等進行詳細分析與討論，相關簡介見表3。

表3 選擇性信息交互機制研究成果

文獻[15]中位置信息采用基于固定鄰居距離方式進行交互，而速度信息則在鄰域跟隨機制和固定鄰居距離交互機制之間進行切換，執(zhí)行跟蹤行為時個體選擇其感知范圍內相對位置變化最大且距離較近的鄰居進行速度信息交互，當跟隨行為達到作用時限時，自動切換為固定鄰居距離交互。通過對個體跟隨目標的選擇和切換實現外界刺激的有效信息在群內定向傳播，達到分群目的?？梢?，速度信息交互模式的切換在一定程度上減少了個體間的信息交互量，控制規(guī)律也得到簡化。但在選擇局部跟隨目標時，會用到鄰居個體上一采樣時刻的位置信息，故需要群集內個體具有一定的記憶能力。

文獻[16]提出了一種結合鄰居運動方向、速度大小、距離、鄰居個數和自身感知距離等信息的綜合定量指標“信息耦合度(ICD)”，并基于ICD提出“min-max”速度信息交互機制，使個體僅選擇與ICD最大和最小的兩個鄰居進行速度信息交互，從而使個體能同時對鄰居中呈現的有序運動和異常變化情況保持敏感，滿足組群和分群行為兩方面的協同需求，并在大規(guī)模群集中體現出更高效的組群優(yōu)勢。與文獻[15]的速度信息交互切換模式相比，控制律得到了進一步簡化。但ICD涉及的信息較多，且定義相對復雜，因此，在文獻[17-19]中對其進行不同程度的簡化，以減少計算量，降低計算復雜度。

文獻[17]定義的ICD包括位置耦合項和速度耦合項，前者與個體及其鄰居相對位置有關，后者與個體和鄰居相對速度以及鄰居速度均值有關。但是,此ICD定義仍相對復雜，且由于ICD最大個體信息的融入，控制律也相對復雜。文獻[18]的ICD包括位置耦合項和相對運動耦合項，前者與個體相對位置有關，后者由采樣時間間隔內相對位置變化來表征?？梢姡琁CD僅由自身及鄰居位置信息決定，無需速度信息，減少了系統所要測量的信息量，增強了算法的實用性。文獻[19]采用采樣時間間隔內相對位置變化來表示ICD，使其定義得到進一步簡化。需指出，文獻[17-19]基于ICD最大的選擇性信息交互機制中，雖然是選擇ICD最大的鄰居個體進行信息交互，但在此基礎上的控制律設計中，個體信息交互的對象實質上仍為其所有鄰居，而最大ICD鄰居信息最終被融入分群控制律中，并在采樣間隔內與周圍特定鄰居建立強交互作用實現外部刺激信息的定向流轉，從而實現群集的自組織分群行為。

文獻[20]提出了基于平均交互和選擇交互的速度間歇性交互機制，利用系數調整兩種交互的權重，并設計隨群體速度狀態(tài)變化的ICD(由個體和其鄰居位置和速度信息來表征)閾值函數，使群體在無序運動狀態(tài)下閾值較大，很難發(fā)生選擇交互行為，傾向于融合行為，而當群體處于有序狀態(tài)時，閾值較小，易發(fā)生選擇交互行為，進而促進外部刺激信息的傳遞并誘發(fā)分群行為。此交互機制不僅有利于分群的產生，也有利于子群在外界刺激消失時再次融合為一個群體。但由于平均交互和選擇交互并存，計算量和復雜度會增加。

文獻[21]提出結對交互機制，令個體與其感知范圍內運動方向變化最大的個體產生結對行為，實現機器人運動狀態(tài)的調節(jié)，達到分群目的。但這種結對對象的選擇標準需要用到鄰居前一時刻的運動方向信息，因此，要求個體具有一定的記憶能力。

文獻[38]提出一種基于注意力的跟隨機制，使個體選擇跟隨其所感知到的最近目標或感知到目標且距離最近的鄰居，并將該機制融入到基于改進擬態(tài)物理法的分群控制律中，實現多目標環(huán)境下的分群行為。需要指出的是，該機制是根據鄰居狀態(tài)信息實現分群控制，而沒有以計算形式來選擇跟隨對象，減少了計算量與計算過程中的不確定因素，但這要求個體能夠識別鄰居是否檢測到目標。因此，該機制適用于具有識別能力的群集。

3 分群控制的穩(wěn)定性分析方法

穩(wěn)定性是分群控制方法的基本特性，是分群控制研究中的重點和難點之一。很多文獻均只通過仿真實驗驗證了所設計的分群控制算法的有效性，并未能從理論上給出相應的穩(wěn)定性分析。此外，選擇性信息交互機制的引入導致拓撲結構圖的有向性和不對稱性，提高了分群算法穩(wěn)定性的理論分析難度[3]。文獻[5]以圖論、矩陣論為基礎，利用Lyapunov穩(wěn)定性定理證明每個虛擬領導者對應的子群都能形成穩(wěn)定群集，利用Lasalle不變原理證明子群中個體速度一致。文獻[6,10,12]利用圖論、矩陣論、Lyapunov穩(wěn)定性定理分析了分群控制算法的穩(wěn)定性。文獻[7,13,18]利用圖論、矩陣論、Lasalle不變原理證明了所設計的分群算法的穩(wěn)定性。文獻[19]在定常時滯情況下，利用Lyapunov-Razumikhin定理導出了分群控制算法的充分條件。針對時變時滯情況，采用Lyapunov-Krasovskii泛函方法，利用線性矩陣不等式(LMI)得到了分群控制算法的充分條件。文獻[24]基于代數圖論和Barbalat引理建立了收斂準則，以保證子群聚集和速度一致，以及整個群集系統中所有智能體之間的避碰。文獻[30]利用Lyapunov泛函方法，得到每個子集合形成群集的充分條件。文獻[33]中的Lipschitz函數、Barbalat引理證明了二分群集控制算法的有效性。文獻[34]利用圖論、Lasalle不變原理和Barbalat引理解決了動態(tài)雙積分器中的二分群集問題。文獻[35-36]利用結構平衡圖理論、固定時間穩(wěn)定定理和Lyapunov穩(wěn)定性定理證明了二分群集策略的有效性。文獻[22]基于固定時間穩(wěn)定定理和結構平衡符號圖理論，給出了二分群集的充分條件，利用非光滑分析，可以在有限的時間內產生固定時間的非碰撞二分群集。

從上述研究成果看，目前用于分群控制穩(wěn)定性分析的方法主要包括圖論、矩陣論、Lyapunov穩(wěn)定性定理、Lasalle不變原理、Barbalat引理、泛函分析等。其中，圖論和矩陣論是分群控制設計和分析中不可缺少的理論基礎，與其他理論分析方法中的一種或幾種進行組合共同實現穩(wěn)定性的證明。另外，進行固定時間的分群算法的穩(wěn)定性分析時還要用到固定時間穩(wěn)定定理。

4 結束語

針對異構和同構群集系統分群問題展開的研究，在一定程度上實現了分群目的，但仍有各自的局限性。所界定的異構屬性不同，且實際異構屬性也不限于上述文獻所列，導致所設計的分群算法基本無法擴展到其他異構群集系統的分群控制中。而同構群集系統分群的子群規(guī)模、運動速度等大多仍不可控，還需要進一步研究如何在分群誘因的設計中去體現對分群的性能要求，以實現性能可控、滿足實際應用的分群效果。此外，目前所設計的分群控制算法大多只針對單一類型的群集系統，并不具有普適性。因此，同時適用于同構和異構群集系統的分群控制算法將是未來研究的一個重點。并且，與漸近分群相比，固定時間分群更具有工程意義，但目前關于固定時間的分群仍局限于二分群，還需進一步將其拓展至多分群集中。

多智能體群集系統的信息交互機制大多從模擬生物群集的信息交互機制入手，從上述研究成果可知這一思路的有效性。因此，想要使多智能體群集系統更好地顯現出生物群集系統所涌現的群體智能，需要結合生物學、統計學等領域在生物群集系統信息交互機制方面最新的研究，進一步深入研究和模擬生物群集系統的信息交互機制。

此外，與基于固定鄰居距離的信息交互群集相比，雖然選擇性信息交互機制的引入能夠使群集系統快速響應外界環(huán)境刺激實現分群行為，但卻增加了穩(wěn)定性分析難度；并且隨著研究的不斷深入，群集系統所處運行環(huán)境的復雜性和分群可控性要求也會提高，這將會給穩(wěn)定性的理論分析帶來新的挑戰(zhàn)，因此，要繼續(xù)深化現有的穩(wěn)定性分析方法，并積極拓展新的理論分析研究思路,探求適合于復雜環(huán)境下可控分群行為的穩(wěn)定性分析理論和方法。