群體運動控制中的虛擬領導算法

劉維曉, 陳俊麗, 萬旺根, 黃 炳

(上海大學通信與信息工程學院,上海 200072)

群體運動控制中的虛擬領導算法

劉維曉, 陳俊麗, 萬旺根, 黃 炳

(上海大學通信與信息工程學院,上海 200072)

針對群體運動中的虛擬領導問題,提出一種多維空間中群體運動的虛擬領導算法.算法中的控制準則可以保證群中個體的狀態變化始終與虛擬領導同步,碰撞檢測和聚合規則可以有效控制群中相鄰個體的距離,避免出現碰撞或離群現象.仿真結果表明,該算法可以很好地實現隊列保持、聚合和避障的目的.

虛擬領導;碰撞檢測;聚合

Abstract:For the problem of multi-agent systemswith a virtual leader,we introduce a flocking algorithm of multi-agents moving in the multi-dimensional space with a virtual leader.The control law s of the algorithm ensure synchronous changes of state of individuals w ith the virtual leader.Collision detection and aggregation rulescan effectively control the distance between neighboring individuals to avoid collision or moving too far from the group.Simulation gives good results in maintaining the queue,aggregation and obstacle avoidance.

Key words:virtual leader;collision detection;aggregation

群聚行為是自然界中一種非常普遍的現象.群聚行為中的生物個體雖然都很簡單,但卻能協同工作,表現出很復雜的行為,如集中覓食、共同防御和建造漂亮的巢穴等.這種群居性生物中產生出的集體行為被稱為群體智能.群體智能存在于自然界的鳥群、魚群、細菌群等各種群體行為之中[1].群體智能利用群體優勢,在沒有集中控制、不提供全局模型的前提下,為尋找復雜問題解決方案提供了新的思路.自 20世紀 80年代以來,群體智能已經成為人工智能以及經濟、社會、生物等交叉學科的研究熱點和前沿領域[2].最近幾年,對群體智能中的控制理論研究正逐漸走進人們的視線,群體智能開始應用于一些控制領域,例如移動機器人的群體行為控制和機群的飛行控制等[3].

最早進行關于群體智能控制行為研究的是Reynolds[4],他于 1986年提出一個用于模擬鳥類聚集飛行行為的仿真模型,該模型中應用如下的定向行為規則:①分離規則;②列隊規則;③聚合規則.模型提出后,在這三種行為規則的前提下出現了各種各樣的改進模型和新的行為準則,例如用群體中兩個相鄰個體之間的局部吸引和排斥潛能定義分離和聚合行為準則[5],加入一些人工智能和回旋力來避障[6]等.Tanner等[7]提出了一系列可以控制群體穩定運動的控制準則,但是這些控制準則不能夠規范個體的最終速度和整個群體的運動朝向.因為在某些情況下,規則對每個個體有特定的速度、朝向或是目的地的規范,但是對于整個群體而言沒有一個共同的運動目標,因此,群體運動中的虛擬領導問題是一個重要的研究課題.

本課題研究的是多維空間中群體運動的虛擬領導問題.虛擬領導并不是一個實際存在的個體,而是人為設定的一個外部參考信號.虛擬領導的狀態由控制準則提供,群中個體狀態依據虛擬領導的狀態變化而變化.2003年,Jadbabaie等[8]提出了一種控制群體運動的虛擬領導算法,算法中設定虛擬領導的狀態是固定的,群中個體始終依照固定的速度和運動朝向進行運動,這種算法可以保證個體速度和運動朝向的一致性,但是不能滿足對實際群體運動中動態變化狀態的模擬.2006年,Olfati-Saber[9]提出了一種動態虛擬領導算法,算法中虛擬領導的狀態依據群中相鄰個體的速度和位置的動態累加獲得,滿足了一定的動態變化的模擬,但虛擬領導的控制中未加入碰撞檢測,因此,算法不能滿足大量群體長時間的運動模擬需要.

本研究提出了一種動態虛擬領導算法,算法中加入了一系列的控制準則,這些控制準則主要依賴于群體中個體鄰近體的運動狀態.控制準則中加入了避障和聚合規則,可以有效避免群中個體的碰撞和出現離群現象.控制準則應用于群體中的每個個體來控制個體的速度和位置狀態.準則中引入了控制群體聚合度的參數 S和控制群體大小的參數ρ,可以很好地控制群體中個體之間的聚合程度和群體中個體的數目,防止過多自由個體的出現.具體實現流程圖如圖1所示.向.朝向是群中個體如何在局部空間被定義的一種指示,主要有 Roll,Pitch和 Yaw組成.Roll是指繞著空間的 z軸旋轉 (朝著前后),Pitch是指繞著空間的 x軸旋轉 (左右偏轉),Yaw是指繞著空間的 y軸旋轉(上下運動).Row,Pitch和 Yaw主要決定了群體中個體的運動朝向.本研究通過給每一個個體定義一個速度矢量 v(x,y,z)來調整個體在 x,y,z軸的運動方向.

圖1 實現流程圖Fig.1 Flow char t of the algor ithm

圖2 定義的三維空間圖Fig.2 Def in ition of the three-d im ensional graph

圖3 空間中三個軸的旋轉定義Fig.3 Def in ition of the three ax is rotation

1 實時運動模型構建

本研究假設群體中有 N+1個個體在三維空間中運動.三維空間中“前”對應著 z軸的正向,“左”對應著 x軸的正向,“上”對應著 y軸的正向,空間坐標如圖2所示.

圖3為空間運動的另一個重要因素 ——朝

每一個個體的實時運動模型定義如下:

式中,p(x,y,z)∈R3N為群體中個體的位置矢量,v(x,y,z)∈R3N為群中個體的速度矢量,u(x,y,z)∈R3N為控制準則的反饋控制量.

在群體運動過程中,個體的速度和位置狀態都是不斷變化的,因此,需要虛擬領導的位置和速度狀態也是不斷變化的.控制準則應當保證群體中所有個體的狀態變化與虛擬領導同步,因此,控制準則的設計應當滿足以下兩個設計原則:①群體中個體的狀態變化應當保持一致性,并且以虛擬領導的狀態為參考;②群體中相鄰的個體之間應當保持一定的距離,并且要相互吸引,同時要避免碰撞[10].根據反饋控制輸入的設計原則,設定控制輸入的表達式如下:

式中,pd,vd為個體為了達到虛擬領導的最優狀態所需的位置和速度改變量,w為控制群體中個體的聚合程度函數,ρ為控制群體大小的輸入量[3].

對于群體運動而言,必須使群中個體有一個相對穩定和一致的位置狀態和速度狀態,從而保持運動的一致性[11].因此,對于整個具有 N+1個個體的群體而言,個體 j為了達到虛擬領導的最優位置所需要的改變可用 pjd表示為

個體 j為了達到虛擬領導的最優速度所需要的改變可用vdj表示為

式 (4)和 (5)中的 d為一個可以控制群體聚合程度的值,取值范圍在 0～1之間.d值越小,個體保持自身運動的趨勢越大;d值越大,受其他個體運動的影響也就越大.

由式 (4)和 (5)可以確定整個群體中個體的位置和速度的狀態改變量.根據控制準則的設計原則,除了要考慮位置和速度的狀態改變外,還需要考慮群體運動中另一個重要問題——躲避障礙.算法中的避障并不是指躲避障礙物,而是為了保持相鄰個體間的相對安全距離,避免碰撞和出現個體離群現象.

2 避障設計

避障設計是控制準則的另一個重要的組成部分,根據 Reynolds的算法設計原則,群體中相互臨近的個體應當保持一定的距離.如果相鄰個體之間的距離太近,它們應當自動分離;反之,當個體的距離太遠,它們應當自動聚合[12].

假設群體中的最大可視距離是 smax,即當群體中的兩個個體的距離小于 smax時,可認為它們是相鄰的個體.當相鄰個體的距離小于所設定的距離 d(d

根據上述群體運動的行為準則,可知避障設計是一個復雜的模糊行為.對于群體中的相鄰個體 i,j,設定兩個模糊控制函數[13]f(Δpdi,j)和 h(Δpdi,j),其中Δpdi,j如式 (3)所示.當相鄰個體 i,j的距離小于設定的距離 d(d

圖4 模糊控制函數Fig.4 Fuzzy control function

根據設定的模糊控制函數,可得如下的分離、聚合控制表達式:

在群體的運動過程中,個體之間的距離是隨時間不斷變化的,因此,群中個體的鄰近個體也不是固定的.聚合控制準則應當把個體的所有鄰近個體的狀態包括在內,因此,聚合控制準則也是一個隨時間不斷變化的量.將分離聚合控制函數應用到個體 i的所有鄰近個體,得到分離聚合準則 w為

在群體運動過程中,若群體數目過于龐大則容易造成個體的離群現象發生,影響群體運動的仿真效果,因此,應當添加一個控制群體大小的參數.設控制群體大小的參數為ρ,其大小主要取決于個體 j的當前位置與中心位置之間的距離,用下式表示:

反饋控制設計完畢后,還需對個體在運動中的運動朝向作如下定義:

式中,rx,ry,rz分別為旋轉角度在 Pitch,Yaw,Rdl三個方向上的分量值,vx,vy,vz為速度矢量 v(x,y,z)在三維空間 x軸,y軸,z軸方向的數值,g為重力,l可用個體的速度矢量表示如下:

式中,vn為個體的當前速度,v0為個體前一時刻的速度.

綜上可知,群體中的控制準則是為了規范群體中個體的運動狀態、規范個體在運動中每一個時刻的狀態改變量.個體的位置、速度和旋轉角度的實時變化都要以虛擬領導為參考,同時群中相鄰個體間應當保持一定的安全距離,盡量避免離群現象的發生.

3 仿真結果分析

本研究將群體運動中的控制準則用 OpenGL在VC++6.0上進行仿真.OpenGL是專業的圖形程序接口,是一個功能強大、調用方便的底層圖形庫,可使本研究設計的群體運動控制規則有一個方便直觀的顯示.在仿真過程中,可以自由調節群的數目和每個群體中個體的數目,不同的群體用不同的深淺進行區別顯示.

本研究在仿真中給群體運動的范圍設定了一個邊界(30,30,30),超過邊界范圍的個體成為自由活動的個體.個體的初始位置和速度矢量設定一個相同的隨機值,并受設定邊界的制約.試驗中通過rand()函數為速度矢量和位置矢量取值,具體值為(rand()＊ 30/5,rand()＊ 30/5,rand()＊ 30/5).設定個體的實時運動速度大小由個體的速度矢量所決定,具體大小由下式實現:

根據試驗效果,設定聚合控制參數 S的取值為0.55,使個體偏重于其他鄰近個體的影響.仿真測試平臺配置如表 1所示.具體的仿真結果如圖5～圖8所示.

表 1 測試平臺Table 1 Test platform

圖5 未加入控制準則的群體運動Fig.5 M ulti-agentsmovement w ithout control laws

圖5所示為未加入控制準則的群體運動.由圖可知,群體運動比較雜亂,整個群體的運動沒有統一的運動朝向,運動過程中容易產生離群現象,隨著時間的推移,個體都已獨自運動,無法成群.圖6為未加入避障規則的群體運動,個體之間不能很好地保持一定的距離,容易產生碰撞現象.圖7和圖8為加入了控制原則的群體,從仿真結果看,整個群體中的個體都是朝著相同的方向運動,并且保持了一定的距離,沒有出現碰撞現象.

本研究所提出的動態虛擬領導算法與文獻[8-9]中提出的虛擬領導算法相比,雖然在算法的復雜度上有所增加(具體表現在群體從初始雜亂狀態達到穩定狀態的時間),但是從整個群體的運動模擬顯示中可以看出,本算法可以很好地控制群體中個體的運動狀態,達到了群體模擬的預期效果.三種算法的具體比較如表 2所示,其中第二個比較項為本算法選用 25個個體在程序運行 10 s時進行統計的結果.

圖6 未加入避障規則的群體運動Fig.6 M ulti-agentsmovement w ithout collision detection and aggregation rules

圖7 算法控制下的多群體運動Fig.7 M ulti-agentsmovement w ith vir tual leader algor ithm

圖8 算法控制下的三個群體運動Fig.8 Three agen ts m ovem en t w ith v ir tual leader algor ithm

表 2 算法比較Table 2 Algor ithm compar ison

4 結 束 語

本研究提出的虛擬領導算法可以有效地保證群中個體運動狀態變化的一致性,降低了群體運動過程中離群現象產生的概率,減少碰撞現象的發生,實現群體運動中的隊列、隊形保持.然而,以下方面有待改進:①進一步優化虛擬領導算法,縮短個體達到穩態的運行時間;②盡可能地擴大可視范圍,減少自由個體的影響,同時平衡算法的復雜度和穩定性;③解決不同群之間的碰撞檢測問題.

[1] KENNEDY J,EBERHART R C.Swarm intelligence[M].USA:Academic Press,2001:10-12.

[2] OLFATI-SABER R,MURRAY R M.Consensus problems in networks of agents with switching topology and timedelays[J]. IEEE Transactions on Automatic Control,2004,49(9):1520-1533.

[3] SHIH,WANG L,CHU T G,et al.Flocking of multiagent systemswith a virtual leader[C]∥Proceeding of the 2007 IEEE Symposium on Artifical Life.2007:287-294.

[4] REYNOLDS C W. Flocks, herds, and schools: a distributed behavioral model[C]∥Computer Graphics,SIGGRAPH’87 Conference Proceedings.1987:25-34.

[5] GAZI V,PASSINO K M.Stability analysis of swarms[J].IEEE Transactionson Automatic Control,2003,48(4):692-697.

[6] TANNER H G. Flocking with obstacle avoidance in switching networks of interconnected vehicles[C]∥IEEE International Conference Robotics and Automation.2004:3006-3011.

[7] TANNER H G,JADBABA IE A,PAPPAS G J.Stable flocking of mobile agents[C]∥Proceeding of the 42ndIEEE Conference on Decision and Control.2003:2010-2021.

[8] JADBABA IE A,L IN J,MORSE A S.Coordination of groups of mobile autonomous agents using nearest neighbor rules[J]. IEEE Transactions on Automatic Control,2003,48(6):998-1001.

[9] OLFATI-SABER R. Flocking for multi-agent dynamic systems:algorithms and theory[J].IEEE Transactions on Automatic Control,2006,51(3):401-420.

[10] PESRAM I R,GORDON B W.Control and cohesion of energetic swarms[C]∥American Control Conference.2008:129-134.

[11] WANG Z Y,GU D B.Distributed cohesion control for leader-follower flocking [C]∥ Fuzzy Systems Conference.2007:1-6.

[12] WANG Z Y,GU D B.Fuzzy control of distributed flocking system[C]∥IEEE International Conference on Mechatronics and Automation.2007:2807-2812.

[13] SHIH,WANGL,CHU T G,et al.Tracking control for groups of mobile agents[C]∥American Control Conference.2007:3265-3270.

(編輯:趙 宇 )

Vir tual L eader Algor ithm for Flock ing M otion Control

L IU Wei-xiao, CHEN Jun-li, WAN Wang-gen, HUANGBing
(School of Communication and Information Engineering,Shanghai University,Shanghai 200072,China)

TP 391.9

A

1007-2861(2010)04-0349-06

10.3969/j.issn.1007-2861.2010.04.004

2009-01-09

國家高技術研究發展計劃(863計劃)資助項目 (2007AA01Z319);上海市教委重點學科建設資助項目 (J50104);國家自然科學基金資助項目(60873130)

陳俊麗 (1972～),女,副教授,博士,研究方向為多媒體信息處理.E-mail:jlchen@staff.shu.edu.cn