群體機器人同步問題的分布式協同控制及優化

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

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

群體機器人同步問題的分布式協同控制及優化

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

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

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

群體機器人;同步;協同控制;分布式控制器;粒子群優化算法

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

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

1 分布式協同控制

1.1 群體機器人系統的協同適應性

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

本文首次提出了群體機器人系統的協同適應性的概念.

定義復雜動態環境中，機器人如何通過個體與個體之間以及個體與環境之間的交互，優化控制策略并調整自身行為，以適應環境和任務的動態變化的特性叫做群體機器人系統的協同適應性.

具體地從數學上可以描述為:

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

協同適應性的目的是max(E)(或min(E)).

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

1.2 群體模型

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

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

1.3 局部信息交互機制與機器人環境感知

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

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

圖1 機器人的鄰域結構Fig.1 Robots’neighborhood

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

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

1.4 控制器設計及穩定性分析

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

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

函數g(·)的類型為

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

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

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

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

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

式中:a、b是給定的正常數.

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

并且定義誤差狀態為=xi－=vi－，則有

定理對于如式(1)所示的群體機器人系統數學模型，若吸引排斥函數如式(4)所示，那么當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}.所以對于一致性環境有

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

從上述函數中計算出時間:

注意上述證明是在沒有任何關于群體拓撲結構的特定條件下進行的，即無論拓撲結構是固定的還是變化的，該分布式控制器都能夠實現穩定的群體同步運動.

2優化

2.1 粒子群優化算法

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

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

2.2 優化問題描述

3 仿真實驗與結果分析

3.1 穩定的群體同步仿真實驗結果與分析

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

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

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

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

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

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

通過上述仿真結果及分析，可見群體機器人的運動不僅不受群體中個體數量的限制，且能根據環境信息的變化自動調整運動方向和速度大小，實現了穩定的群體同步行為.

3.2 能量優化的仿真實驗

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

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

圖8 優化前不同參數對應能量曲線對比Fig.8 Comparisons of energy for different parameters before optimization

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

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

圖10 優化后能量消耗曲線Fig.10 Curve of energy consumption after optimization

4 結束語

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

［1］胡中功，李靜.群智能算法的研究進展［J］.自動化技術與應用，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年生，博士研究生，主要研究方向為群體機器人系統、強化學習.

李成鳳，女，1986年生，碩士研究生，主要研究方向為群體機器人系統、分布式優化.

田彥濤，男，1958年生，教授、博士生導師、博士.吉林大學自動化研究所所長，兼任中國自動化學會理事、中國自動化學會機器人專業委員會常務委員、吉林省自動化學會理事長、吉林省通信學會副理事長、吉林省電機工程學會常務理事，中科院沈陽自動化研究所先進制造技術實驗室學術委員會委員，中國自動化學會《機器人》學報編委、《吉林大學學報(信息科學版)》副主編.主要研究方向為復雜系統建模、優化與控制、分布式智能系統與網絡控制.近五年，完成國家“863”計劃項目1項、國家自然科學基金項目1項、吉林省科技發展計劃項目3項、國家“863”計劃智能機器人網點實驗室基金項目1項;目前負責承擔國家“863”計劃項目和國家自然科學基金項目等國家級科研項目3項、吉林省科技發展計劃重點項目3項.曾被評為國家機械部“優秀科技青年”、機械部和教育部跨世紀學科帶頭人，2004年評為吉林省拔尖創新人才.發表學術論文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.

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

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

book=3,ebook=27