群體運動控制中的虛擬領(lǐng)導算法

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

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

群體運動控制中的虛擬領(lǐng)導算法

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

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

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

虛擬領(lǐng)導;碰撞檢測;聚合

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

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

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

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

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

圖1 實現(xiàn)流程圖Fig.1 Flow char t of the algor ithm

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

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

1 實時運動模型構(gòu)建

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

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

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

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

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

式中,pd,vd為個體為了達到虛擬領(lǐng)導的最優(yōu)狀態(tài)所需的位置和速度改變量,w為控制群體中個體的聚合程度函數(shù),ρ為控制群體大小的輸入量[3].

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

個體 j為了達到虛擬領(lǐng)導的最優(yōu)速度所需要的改變可用vdj表示為

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

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

2 避障設(shè)計

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

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

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

圖4 模糊控制函數(shù)Fig.4 Fuzzy control function

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

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

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

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

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

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

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

3 仿真結(jié)果分析

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

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

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

表 1 測試平臺Table 1 Test platform

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

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

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

圖6 未加入避障規(guī)則的群體運動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 結(jié) 束 語

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

[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

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

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