群體機器人同步問題的分布式協(xié)同控制及優(yōu)化

楊 茂，李成鳳，田彥濤，2

(1.吉林大學(xué)通信工程學(xué)院，吉林長春 130025;2.吉林大學(xué)工程仿生教育部重點實驗室，吉林長春 130025)

群體機器人同步問題的分布式協(xié)同控制及優(yōu)化

楊 茂1，李成鳳1，田彥濤1，2

(1.吉林大學(xué)通信工程學(xué)院，吉林長春 130025;2.吉林大學(xué)工程仿生教育部重點實驗室，吉林長春 130025)

主要研究群體機器人系統(tǒng)協(xié)同適應(yīng)性，通過局部信息交互下的分布式控制實現(xiàn)群體對復(fù)雜環(huán)境的適應(yīng).以同步現(xiàn)象為研究對象，結(jié)合虛擬力、最近鄰居原則以及環(huán)境因素，提出了一種可以解釋該現(xiàn)象的分布式控制器.并證明該控制器能夠使所有的群體成員在誤差允許的范圍內(nèi)收斂到一個共同速度，其優(yōu)點是僅需要局部信息就能夠?qū)崿F(xiàn)穩(wěn)定的群體行為.此外，在上述分布式控制器設(shè)計的基礎(chǔ)上進行了參數(shù)優(yōu)化，利用粒子群優(yōu)化算法實現(xiàn)能量消耗最少的目標(biāo).通過仿真實驗驗證了控制器及算法的可行性和有效性.

群體機器人;同步;協(xié)同控制;分布式控制器;粒子群優(yōu)化算法

在眾多生物群體中，如編隊遷徙的鳥群、結(jié)隊巡游的魚群、協(xié)同工作的蟻群、聚集而生的細(xì)菌菌落等，不存在協(xié)調(diào)者來協(xié)調(diào)大量自主個體，但整個系統(tǒng)卻呈現(xiàn)協(xié)調(diào)有序的狀態(tài).這使生物群體在覓食生存、逃避天敵等方面獲得單獨個體難以實現(xiàn)的優(yōu)勢，完成復(fù)雜、有一定目的或功能的活動［1］.群體機器人學(xué)受社會性昆蟲及群居動物群體行為的啟發(fā)，主要研究如何使大量相對簡單的機器人通過局部交互，涌現(xiàn)出智能群體行為.如何制定一定的規(guī)則，從系統(tǒng)論與控制學(xué)的觀點出發(fā)解釋這些現(xiàn)象，并對控制器參數(shù)進行優(yōu)化，可能對相關(guān)工程應(yīng)用有潛在效益.

1986年C.W.Reynolds在文獻(xiàn)［2］中建立了一個協(xié)調(diào)運動的行為模型.他將模擬的通用實體命名為“boids”，并且他的工作開啟了計算機圖形學(xué)中一個名為“人工生命”的新的研究課題.文獻(xiàn)［3］中Vicsek等人提出了基于最近鄰居原則的仿真模型，仿真結(jié)果表明所有粒子的速度能夠收斂到一個共同的值.盡管是分別提出的，但Vicsek模型是boids模型的一個特例.為了從數(shù)學(xué)上證明Vicsek的結(jié)果，Jadbabaie等人［4］提出了離散的運動學(xué)模型和依據(jù)最近鄰居原則的分布式控制器.他們使用了一些源自代數(shù)圖論的概念證明所有個體速度的收斂性，在他們后續(xù)的工作中［5－7］，對于固定的和動態(tài)的群體拓?fù)浣Y(jié)構(gòu)提出了一個連續(xù)的動態(tài)模型和一個分布式控制器.控制器包括基于最近鄰居的狀態(tài)的航向和速度調(diào)節(jié)成分，通過代數(shù)圖論和不連續(xù)穩(wěn)定性理論，證明控制器能夠引導(dǎo)所有機器人的航向收斂到一個公共值，并且所有的速度收斂到相同的值.Gazi和Passino［8］提出了群體成員的一個連續(xù)的一階運動學(xué)模型，并且運用虛擬作用的觀點提出用于分析n維空間中群體集聚的分布式控制器.文獻(xiàn)［8］表明個體能夠在有限的時間內(nèi)形成內(nèi)聚群體，并且其中也得到了群體大小的一個明確約束.文獻(xiàn)［9］中一類更廣泛的虛擬力函數(shù)是文獻(xiàn)［8］結(jié)論的擴展.在其后續(xù)工作中［10－12］，使用相同的方法證明了在某種特定環(huán)境中群體聚集行為的存在性.Liu等人［12］利用一個二階動力學(xué)模型來研究在某種具有噪聲的特定環(huán)境下的穩(wěn)定的群體覓食行為.然而，文獻(xiàn)［8－13］提出的所有控制器要求每個機器人知道所有其他機器人的狀態(tài)，這對于自然生物是不可能的.文獻(xiàn)［14］中Reif和Wang首先提出了超大規(guī)模機器人系統(tǒng)(very large scale robotic system)的概念，并提出一種使用人工勢場(artificial potential field)作為控制律的分布式控制方案.但是以上控制方法僅限于全局交互機制或者是無環(huán)境信息反饋的情況，且均未考慮控制器性能參數(shù)的優(yōu)化問題.本文針對群體機器人系統(tǒng)在復(fù)雜環(huán)境下的同步問題，利用鄰接矩陣的方法，設(shè)計了基于局部信息交互的分布式控制器，并進行了群體穩(wěn)定性分析，證明了該控制器無論是在切換拓?fù)溥€是固定拓?fù)潢P(guān)系下都能夠使得系統(tǒng)中的所有個體在環(huán)境信息反饋下實現(xiàn)同步.同時還對控制器進行了參數(shù)優(yōu)化，以實現(xiàn)能量優(yōu)化的目標(biāo).

1 分布式協(xié)同控制

1.1 群體機器人系統(tǒng)的協(xié)同適應(yīng)性

群體機器人系統(tǒng)是一類特殊的多機器人系統(tǒng)，其特殊性體現(xiàn)在如下幾方面:首先，在控制方式方面，多機器人系統(tǒng)可以是集中控制也可以是分布式控制，而群體機器人系統(tǒng)一定是分布式控制;其次，在系統(tǒng)規(guī)模方面，多機器人系統(tǒng)一般個體數(shù)量較少，而群體機器人系統(tǒng)數(shù)量很多;再次，在個體能力方面，多機器人系統(tǒng)中的個體一般較為復(fù)雜，而群體機器人系統(tǒng)的個體相對簡單;最后也是最重要的，在通信機制方面，多機器人系統(tǒng)一般是全局通信，而群體機器人系統(tǒng)是以局部通信為主要特征.以上特征決定了群體機器人系統(tǒng)具有魯棒性、可擴展性和適應(yīng)性等特點.

本文首次提出了群體機器人系統(tǒng)的協(xié)同適應(yīng)性的概念.

定義復(fù)雜動態(tài)環(huán)境中，機器人如何通過個體與個體之間以及個體與環(huán)境之間的交互，優(yōu)化控制策略并調(diào)整自身行為，以適應(yīng)環(huán)境和任務(wù)的動態(tài)變化的特性叫做群體機器人系統(tǒng)的協(xié)同適應(yīng)性.

具體地從數(shù)學(xué)上可以描述為:

設(shè)群體機器人系統(tǒng)中有N個機器人，r為機器人鄰居半徑;令ε(i，t)為第i個機器人在時間t時刻的局部環(huán)境狀態(tài)(i=1，2，…，N); ξ(i，t)為第i個機器人在時間t時刻其他鄰居機器人反饋的狀態(tài)信息;ω為滿足運動及環(huán)境約束的機器人動作集合;η(t)對應(yīng)t時刻的群體行為;E(η)表示對于群體行為的性能評估;V為群體機器人系統(tǒng)集體任務(wù)性能標(biāo)準(zhǔn).則群體機器人系統(tǒng)為

協(xié)同適應(yīng)性的目的是max(E)(或min(E)).

同步問題是群體機器人系統(tǒng)的研究中的經(jīng)典問題之一，是多機器人利用分布式感知能力通過控制器的作用最終達(dá)到速度(包含速率與方向)一致，該控制器通常是分布式控制器.而在實體機器人中，機器人通常依靠電池提供能量，其運行往往受限于電池容量，因此如何有效地使用有限的電池能量，對提高機器人的續(xù)航能力至關(guān)重要.這對于大量個體能量消耗問題尤為突出，因此，將優(yōu)化技術(shù)應(yīng)用群體機器人中是具有理論意義和實際工程價值的.

1.2 群體模型

考慮在n維空間中運動的機器人群體，假設(shè)個體同時運動并視為質(zhì)點，個體之間無通信延遲.對個體建模如下:

式中:i=1，2，…，N，xi∈Rn、vi∈Rn、mi和ui分別是機器人i的位置、速度、質(zhì)量和控制輸入.假設(shè)沒有擾動力作用在個體上，且mi已知.顯然，式(1)為典型的拉格朗日動態(tài)模型.

1.3 局部信息交互機制與機器人環(huán)境感知

如果滿足‖xi－xj‖≤d0，稱2個不同機器人i和j(i≠j)為彼此的鄰居，其中d0是給定的正數(shù)，通常由機器人的通信范圍決定.i?{j:‖xi－xj‖≤d0，j≠i，j=1，2，…，N}代表機器人i所有鄰居的集合.

可見，機器人的鄰域結(jié)構(gòu)是運動空間中分布的圓，半徑等于機器人的通信半徑，見圖1.若機器人的通信距離與運動空間相比足夠大，局部信息交互將會演化為全局交互.

圖1 機器人的鄰域結(jié)構(gòu)Fig.1 Robots’neighborhood

為簡化群體速度收斂的證明，本文運用代數(shù)圖論中鄰接矩陣來代表機器人的鄰居.對于機器人數(shù)目為N的群體，定義鄰接矩陣A=［aij］N×N，其中

假設(shè)群體在具有特定勢能函數(shù)ρ(x)的環(huán)境中運動，并且此函數(shù)具有有限斜率，即ρ(x)在xi的梯度(ρ(x))已知，通過在生物系統(tǒng)中的觀察可以證明此假設(shè)是正確的.

1.4 控制器設(shè)計及穩(wěn)定性分析

對每個機器人提出分布式控制器如下:

式中:kp、kv和kr是給定的正常數(shù)，g:Rn→Rn代表個體之間的吸引排斥函數(shù).

函數(shù)g(·)的類型為

式中:ga:R+→R+代表吸引項的大小，gr:R+→R+代表排斥項的大小.以向量y為例，所以實際的吸引、排斥分別是－yga‖y‖和ygr‖y‖，假設(shè)g(·)滿足下列條件:

1)g(·)是一個在相反方向運動的吸引排斥項的奇函數(shù)，也就是，g(y)=－g(－y).

2)存在惟一的距離δ使得ga(δ)=gr(δ).此外，

3)存在相應(yīng)的函數(shù)Ja:R+→R+和Jr:R+→R+，使得▽yJa(‖y‖)=yga‖y‖，▽yJr(‖y‖)=ygr‖y‖.

假設(shè)條件1)、2)、3)是由 Gazi和 Passino介紹的［15］.本文考慮吸引排斥函數(shù)由線性吸引項和有界排斥項組成:

式中:a、b是給定的正常數(shù).

假設(shè)群體在對每個機器人產(chǎn)生相同作用的一致性環(huán)境中運動，即ρ(x)= ▽xjρ(x)，?i≠j，從而有 －

并且定義誤差狀態(tài)為=xi－=vi－，則有

定理對于如式(1)所示的群體機器人系統(tǒng)數(shù)學(xué)模型，若吸引排斥函數(shù)如式(4)所示，那么當(dāng)t→∞時，vi→ˉ，所有個體將收斂到一個超球()={x:‖x－‖≤δ})，式中:

因為對任意矩陣S=ST＞0和向量x，有λmin(S)xT·x≤xTx≤xTSx≤λmax(S)xTx，其中 λmin(S)和λmax(S)分別代表S的最小和最大的特征值.并由式(2)定義的鄰接矩陣AN×N得

式中:d=max{‖xi－xj‖|i=1，2，…，N;j=1，2，…，N}.所以對于一致性環(huán)境有

推論群體同步收斂所需時間可估計，即

從上述函數(shù)中計算出時間:

注意上述證明是在沒有任何關(guān)于群體拓?fù)浣Y(jié)構(gòu)的特定條件下進行的，即無論拓?fù)浣Y(jié)構(gòu)是固定的還是變化的，該分布式控制器都能夠?qū)崿F(xiàn)穩(wěn)定的群體同步運動.

2優(yōu)化

2.1 粒子群優(yōu)化算法

PSO算法隨機地初始化為目標(biāo)函數(shù)的一個解群體，群體中的每個個體稱為一個粒子.每個粒子模仿鳥類的覓食行為，通過跟蹤2個“極值”來實現(xiàn)在搜索空間尋找最優(yōu)解的目的:一個是每個粒子當(dāng)前已搜索到的最優(yōu)位置(適應(yīng)度最大)，稱為個體極值Pbest;另一個是整個粒子群當(dāng)前已搜索到的最優(yōu)位置，稱為全局極值Gbest.PSO算法可描述如下:假設(shè)在D維搜索空間有m個粒子，粒子i在搜索空間的位置用向量Xi=［xi1xi2…xiD］T表示，其個體極值記為Pi=［pi1pi2…piD］T，而全局極值記為Pg=［pg1pg2…pgD］T.在迭代過程中，粒子i以速度v在搜索空間飛行.每個粒子的飛行速度及位置按下式進行修正:

式中:c1、c2為正常數(shù)，稱為加速因子，通常取c1=c2=2.0;r1，r2為［0，1］之間的隨機數(shù);w為慣性因子.在迭代過程中，粒子的速度向量被限制在［－Vmax，Vmax］范圍內(nèi)，以降低例子飛出搜索空間的概率;而粒子的位置向量被限制在［Xmin，Xman］范圍內(nèi).

2.2 優(yōu)化問題描述

3 仿真實驗與結(jié)果分析

3.1 穩(wěn)定的群體同步仿真實驗結(jié)果與分析

在仿真中，假設(shè)所有群體成員同構(gòu)并且質(zhì)量已知.本文選擇設(shè)計常數(shù)為kp=3.5，kv=2.3，kr=2.0，d0=10.隨機給定機器人的初始速度，在［－10，10］內(nèi)隨機給定初始位置.在下述圖形中星形和圓形分別代表機器人的初始位置和最終位置.

圖2和圖3分別顯示機器人個數(shù)為10個的群體在二維空間中的運動軌跡和速度收斂曲線，可以看出群體中所有機器人收斂到一個相同的速度，并且它們的間隔幾乎保持為常數(shù)，實現(xiàn)了穩(wěn)定的群體同步行為.

圖2 二維空間中機器人的運動軌跡(N=10)Fig.2 Robots’trajectories in 2－D environment(N=10)

圖3 二維空間中機器人的速度(N=10)Fig.3 Robots’velocity in 2－D environment(N=10)

圖4和圖5分別顯示機器人個數(shù)為100的群體在二維空間中的運動軌跡和速度曲線，群體的速度仍收斂，機器人間的間距仍基本恒定.此外，圖2和圖4所具有的環(huán)境信息不同，即初始化的環(huán)境梯度方向相反，因此機器人的運動方向也相反.

圖4 二維空間中機器人的運動軌跡(N=100)Fig.4 Robots’trajectories in 2－D environment(N=100)

圖5 二維空間中機器人的速度(N=100)Fig.5 Robots’velocity in 3－D environment(N=100)

圖6 三維空間中機器人的運動軌跡(N=15)Fig.6 Robots’trajectories in 3－D environment(N=15)

圖7 三維空間中機器人的速度(N=15)Fig.7 Robots’velocity in 3－D environment(N=15)

圖6和圖7分別是群體機器人(數(shù)量為15個)在三維空間中的運動軌跡和速度變化曲線，同樣，群體仍然能夠達(dá)到速度收斂和保持恒定間距的目的.

表1是群體機器人系統(tǒng)中每個個體運動角度隨時間變化情況(即協(xié)同適應(yīng)性中的性能評價指標(biāo))，可知隨時間的推移每個個體的角度最終趨于一致.

表1 二維空間中機器人運動的角度隨時間的變化Table 1 Robots’angle experimental results with time in 2-D environment (°)

通過上述仿真結(jié)果及分析，可見群體機器人的運動不僅不受群體中個體數(shù)量的限制，且能根據(jù)環(huán)境信息的變化自動調(diào)整運動方向和速度大小，實現(xiàn)了穩(wěn)定的群體同步行為.

3.2 能量優(yōu)化的仿真實驗

在機器人運動過程中，利用粒子群優(yōu)化算法對控制器的性能參數(shù)k=［kpkvkr］進行優(yōu)化，達(dá)到能量消耗最小的目的.

圖8表示參數(shù)k取不同值時，群體所消耗的能量的對比.可見，控制器的性能參數(shù)能夠影響系統(tǒng)消耗能量的大小，進而可以對控制器的性能參數(shù)進行優(yōu)化，達(dá)到能量消耗最小的目的.圖9顯示粒子對k值的尋優(yōu)過程，可以看出，利用粒子群優(yōu)化算法能夠使控制器的性能參數(shù)k經(jīng)過一段時間的調(diào)整達(dá)到了最優(yōu)值.

圖8 優(yōu)化前不同參數(shù)對應(yīng)能量曲線對比Fig.8 Comparisons of energy for different parameters before optimization

圖9 k最優(yōu)值的變化曲線Fig.9 Optimal k values with the iteration of PSO

圖10顯示相應(yīng)的優(yōu)化后的群體同步行為所消耗的能量，與圖8所示優(yōu)化前的能量相比，減小了3個數(shù)量級，得到了很好的優(yōu)化效果.

圖10 優(yōu)化后能量消耗曲線Fig.10 Curve of energy consumption after optimization

4 結(jié)束語

本文提出了群體機器人系統(tǒng)的協(xié)同適應(yīng)性的概念，針對于同步現(xiàn)象，在充分考慮環(huán)境信息及機器人之間的局部信息交互的前提下，設(shè)計了群體機器人系統(tǒng)的分布式控制以實現(xiàn)穩(wěn)定的同步運動，并對于完成時間進行了估計.利用粒子群優(yōu)化算法來優(yōu)化控制器中的相應(yīng)參數(shù)，進而解決同步過程中的能量優(yōu)化問題，仿真結(jié)果證明了方法的有效性.進一步的工作包括對于動態(tài)環(huán)境下的控制器設(shè)計;提出通用性強的吸引排斥函數(shù)，實現(xiàn)將時間、能量等相結(jié)合的綜合優(yōu)化目標(biāo)，從而得到更為理想的效果.

［1］胡中功，李靜.群智能算法的研究進展［J］.自動化技術(shù)與應(yīng)用，2008，27(2):13－15.

HU Zhonggong，LI Jing.The progress of swarm intelligence algorithms［J］.Techniques of Automation and Application，2008，27(2):13－15.

［2］REYNOLDS C W.Flocks，birds，and schools:a distributed behavioral model［C］//Proceedings of ACM Computer Graphics(SIGGRAPH’87).New York，USA:ACM，1987:25－34.

［3］VICSEK T，CZIROK A，Ben－JACOB E，COHEN I，SHOCHET O.Novel type of phase transition in a system of self－driven particles［J］.Physical Reviews Letter，1995，75(6):1226－1229.

［4］JADBABIE A，LIN J，MORSE A S.Coordination of groups of mobile autonomous agents using nearest neighborhood rules［J］.IEEE Transaction on Automatic Control，2003，48(6):988－1001.

［5］TANNER H G，JABABAIE A，PAPPAS G J.Flocking in fixed and switching networks［J］.IEEE Transaction on Automatic Control，2007，52(5):863－868.

［6］TANNER H G，JABABAIE A，PAPPAS G J.Stable flocking of mobile agent，part I:fixed topology［C］//Proceedings of Conference on Decision Control.Maui，HI，USA，2003:2010－2015.

［7］TANNER H G，JABABAIE A，PAPPAS G J.Stable flocking of mobile agent，part II:dynamic topology［C］//Proceedings of Conference on Decision Control.Maui，Hawaii，2003:2016－2021.

［8］GAZI V，PASSINO K M.Stability analysis of swarms［J］.IEEE Transaction on Automatic Control，2003，48:692－697.

［9］GAZI V，PASSINO K M.A class of attraction/repulsion functions for stable swarm aggregations［C］//Proceedings of Conference on Decision Control.Los Vegas，USA，2002:2842－2847.

［10］GAZI V，PASSINO K M.Stability analysis of swarms in an environment with an attractant/repellent profile［C］//Proceedings of American Control Conference.Anchorage，USA，2002:1819－1824.

［11］GAZI V，PASSINO K M.Stability analysis of social foraging swarms:combined effects of attractant/repellent profiles［C］//Proceedings of Conference on Decision Control.Las Vegas，USA，2002:114－123.

［12］GAZI V，PASSINO K M.Stability analysis of social foraging swarm［J］.IEEE Transaction on Systems，Man，and Cybernetics－Part B:Cybernetics，2004，34(1):539－557.

［13］LIU Yanfei，PASSINO K M.Stable social foraging swarms in a noisy environment［J］.IEEE Transaction on Automatic Control，2004，49(1):30－44.

［14］REIF J H，WANG Hongyan.Social potential fields:a distributed behavioral control for autonomous robots［J］.Robotics and Autonomous Systems，1999，27:171－194.

楊 茂，男，1982年生，博士研究生，主要研究方向為群體機器人系統(tǒng)、強化學(xué)習(xí).

李成鳳，女，1986年生，碩士研究生，主要研究方向為群體機器人系統(tǒng)、分布式優(yōu)化.

田彥濤，男，1958年生，教授、博士生導(dǎo)師、博士.吉林大學(xué)自動化研究所所長，兼任中國自動化學(xué)會理事、中國自動化學(xué)會機器人專業(yè)委員會常務(wù)委員、吉林省自動化學(xué)會理事長、吉林省通信學(xué)會副理事長、吉林省電機工程學(xué)會常務(wù)理事，中科院沈陽自動化研究所先進制造技術(shù)實驗室學(xué)術(shù)委員會委員，中國自動化學(xué)會《機器人》學(xué)報編委、《吉林大學(xué)學(xué)報(信息科學(xué)版)》副主編.主要研究方向為復(fù)雜系統(tǒng)建模、優(yōu)化與控制、分布式智能系統(tǒng)與網(wǎng)絡(luò)控制.近五年，完成國家“863”計劃項目1項、國家自然科學(xué)基金項目1項、吉林省科技發(fā)展計劃項目3項、國家“863”計劃智能機器人網(wǎng)點實驗室基金項目1項;目前負(fù)責(zé)承擔(dān)國家“863”計劃項目和國家自然科學(xué)基金項目等國家級科研項目3項、吉林省科技發(fā)展計劃重點項目3項.曾被評為國家機械部“優(yōu)秀科技青年”、機械部和教育部跨世紀(jì)學(xué)科帶頭人，2004年評為吉林省拔尖創(chuàng)新人才.發(fā)表學(xué)術(shù)論文70余篇，其中被SCI、EI、ISTP 檢索36篇.

Distributed coadaptive control and optimization of swarm robot synchronization

YANG Mao1，LI Cheng－feng1，TIAN Yan－tao1，2

(1.School of Communication Engineering，Jilin University，Changchun 130025，China;2.Key Laboratory of Bionic Engineering(Jilin University)，Ministry of Education，Changchun 130025，China)

Co－adaptive control mechanisms for swarm robot systems were investigated to see if swarms could adapt to complex environments by using distributed control with local information exchange.The phenomenon of synchronization was studied，and on that basis a decentralized controller was proposed.It combined the ideas of a virtual force，the nearest neighborhood law，and environmental factors.It was proven that this controller can enable all swarm members to converge to a common velocity with bounded errors，whether the swarm topology is fixed or dynamic.The advantage of this controller is that it just needs local information to provide stable group behavior.In addition，parameters were optimized on the basis of the proposed controller to achieve the goal of minimum energy consumption.To deal with particle swarm optimization algorithms(PSO)easily falling into local optimums and having low accuracy，an improved algorithm was put forward.This was used to solve the energy optimization problem.Simulation results are included that verified the controller and algorithm.

swarm robot;synchronization;cooperative control;distributed controller;PSO algorithms

TP18

A

1673－4785(2010)03－0247－07

10.3969/j.issn.1673－4785.2010.03.007

2009－11－12.

國家自然科學(xué)基金資助項目(60675057);吉林大學(xué)研究生創(chuàng)新基金資助項目(20091020).

田彥濤.E－mail:tianyt@jlu.edu.cn.

book=3,ebook=27