多個體系統編隊分布式控制的循環追蹤算法

楊希祥，楊濤，楊慧欣，張為華

(國防科學技術大學 航天科學與工程學院，湖南 長沙，410073)

長久以來，自然界的群體行為受到學術界廣泛關注和研究，并在軍事作戰、航空航天、工業生產等諸多工程領域逐步得到應用，如多機器人編隊執行偵察、巡邏等任務，多顆衛星編隊飛行執行對地觀測任務及多無人飛行器編隊飛行執行攻擊任務等。大量研究表明，多個體系統協同工作使很多單個個體難以實現的任務變得簡單，多功能得以實現，系統整體性能得到極大提升。編隊控制是多個體系統編隊完成任務必須解決的關鍵問題。編隊控制主要內容包括隊形生成、隊形保持、隊形重構等。編隊控制算法是編隊控制的核心。國內外學者對此進行了積極研究[1?2]。編隊控制需設計合理的控制結構和控制策略?？刂撇呗苑譃榧锌刂坪头植际娇刂?。相對集中式控制，分布式控制更具優勢，目前，學者們已提出了多種分布式控制律。研究人員從生物運動中個體相互追蹤的行為出發，總結出基于循環矩陣的循環追蹤運動策略，提出將循環追蹤算法應用于編隊分布式控制的新思想，并將其應用于機器人、無人機等編隊控制[3?4]。目前，國內外關于循環追蹤算法尤其是其工程領域應用的研究較少。為此，本文作者對循環追蹤算法的歷史演進進行系統闡述，對典型循環追蹤模型進行推導，結合數值仿真，對算法的特點與性質進行深入分析，為循環追蹤算法理論研究和工程應用提供理論參考。

1 循環追蹤算法演進過程

1.1 經典追蹤算法(classic pursuit algorithm，ClaPA)

循環追蹤算法源于經典追蹤算法。追蹤的思想源于數學上的追蹤曲線。追蹤曲線的定義可簡要描述為，如果空間中一點q沿已知曲線運動，點p始終指向q并以相同速率運動，點p的運動軌跡即為追蹤曲線，這也是所謂的經典追蹤問題。學術界普遍認為法國數學家Bouguer首次研究了經典追蹤問題(1732年)，事實上，早在1672—1676年，Perrault就提出了追蹤曲線的問題[5]。

1748年，Ash首先描述了圓形追蹤問題：1只蜘蛛追蹤沿半圓形玻璃運動的蒼蠅。但直到1859年，同類問題才再次被提及，但沒有學者給出這一問題的解。1920年，Hathaway在《American Mathmatical Monthly》中重新描述了圓形追蹤問題，“圓形池塘中央的一只小狗，追蹤沿池塘邊運動的鴨子，狗與鴨子的運動速率為n:1，則小狗將按何種曲線運動？”。后來的研究表明：當速率比n＞1時，追蹤者最終可趕上目標；當速率比n=1時，追蹤者與目標具有相同運動軌跡，且穩定后位移差和相位差保持不變；當速率比n＜1時，追蹤者的運動軌跡為一有限圓，其與目標的運動半徑比為n(見圖1[16])。上述結果也反映了經典追蹤問題的一個共性規律，即只有當追蹤者速度大于被追蹤者時才能捕獲目標。

由經典追蹤問題衍生的經典追蹤算法在導彈、魚雷等攻擊機動目標的工程問題中得到研究和應用。

1.2 線性循環追蹤算法(linear cyclic pursuit algorithm，LCyPA)

1877年，法國數學家Lucas首次正式提出了循環追蹤問題：3只小狗分別位于平面內等邊三角形的頂點，依次追蹤，其運動將形成怎樣的軌跡？3月以后，Brocard回答了這一問題：若 3只小狗同時以等速追蹤，每只小狗的追蹤曲線均為對數螺旋曲線，且3只小狗最終交會于三角形內 1點，即著名的 Brocard點[5?6]。

圖1 不同速率比下圓形追蹤問題結果Fig. 1 Results for circle pursuit with different speed ratios

1908年，Hackett采用數值分析方法研究了循環追蹤問題的微分方程，他沒有采用等邊三角形的限制條件。1918年，Bateman在教材中提到了非對稱的3只小狗循環追蹤問題。在1950前，循環追蹤算法只是為數學家所熟知。1965年，Gardner在《Scientific American》雜志上開設了專欄，這一領域的研究才逐漸為其余領域所了解。在1962年，Clapham已將3只小狗問題擴展為一般性的n只小蟲問題[7]，即n只小蟲位于正n邊形的頂點，這也是循環追蹤領域極為著名的問題。后來的研究表明，如果每只小蟲均以相同速度依次追蹤其下一個數目對n取模的編號的小蟲，則所有小蟲的運動軌跡均為對數螺旋曲線，且最終交會于多邊形的中心。1969年，Watton 和Kydon提供了正多邊形問題的解，指出常速度假設不是必要的。許多學者對生物領域的追蹤現象進行了研究，發現許多動物，如螞蟻、蟋蟀、蜜蜂等，都存在類似循環追蹤的行為。1971年，Klamkin和Newman研究了小蟲不在正多邊形頂點的情況，研究結果表明，只要小蟲初始隊形不在同一條直線上，最終都將在1點處相遇。對于3只小蟲位于非等邊三角形頂點的情況，推導得出每只小蟲的速度與三角形邊長關系的表達式[8]。

1991年，Bruckstein等分析了規則和不規則多邊形初始位置、連續(以蟻群為對象)和離散的(以蟋蟀群和青蛙群為對象)追蹤形式、勻速和變速的循環追蹤問題。Smith等采用多層結構加速循環追蹤的收斂速度。Sinha和Ghose將線性循環追蹤問題推廣到個體具有不同控制增益的情況。

上述傳統的循環追蹤問題都是基于質點模型假設，追蹤者速度方向實時指向被追蹤者，不考慮實際能量限制或速度轉向的時間延遲引起的非線性，因此，在追蹤領域一般稱為線性循環追蹤(linear cyclic pursuit algorithm，LCyPA)。在實際工程問題中，轉動控制能量往往不足以達到 LCyPA要求，或需要一定反應時間才能完成速度方向指向目標的要求，LCyPA模型則不再適合準確描述個體的運動，非線性循環追蹤 (Nonlinear Cyclic Pursuit，NlCyP)模型與算法應運而生。

1.3 非線性循環追蹤算法(linear cyclic pursuit algorithm，LCyPA)

隨著輪載機器人編隊控制研究的蓬勃開展，循環追蹤算法研究擴展到非線性范圍，因為輪載機器人調整速度方向存在時間延遲。

Marshall等[3,9]對非線性循環追蹤算法進行了大量研究，提出了采用相對運動方式描述非線性循環追蹤行為的模型，將追蹤方式擴展到非相鄰成員的范圍，研究表明，包含所有成員的閉合信息交流環是產生統一構形的必要條件，他們還采用一組獨輪機器人進行了半實物仿真實驗，證明了非線性循環追蹤算法對工程問題的適用性。

Krishnaprasad等對非循環追蹤算法在自主移動機器人中的應用進行了大量研究。Zhang等研究了平面內多個體序貫追蹤問題，其中體現了循環追蹤的思想；Gehrels[10]以地面輪載機器人為例，對非線性循環追蹤算法進行了半實物仿真；Galloway[11]對循環追蹤算法的幾何特性、數學原理等進行了深入系統研究。

此外，東京大學等也在非線性循環追蹤領域開展了理論與試驗研究[12]。Hara等[13]研究了三維空間多個體系統編隊循環追蹤控制問題；Jaime[14]對基于循環追蹤方法的三維空間衛星編隊分布式控制進行了深入研究，提出一種特征分解方法，對循環追蹤方法進行了改進，并采用SPHERES試驗系統進行了驗證，還采用其解決電磁編隊衛星編隊控制問題。

2 線性循環追蹤模型

考慮二維空間中存在的一組n個體編隊，個體坐標由表示，t≥0。若對任一個體施加控制ui∈R2，使之追蹤個體i+1，i=1，2，…，n，追蹤對象以n取模 (簡記為 modn)。系統控制可統一描述為

式中，aij表示個體i受個體j影響的控制增益；i，j=1，2，…，n。全系統可表示為如下形式：

若循環追蹤控制中，個體i的運動僅受個體i+1作用，即式(2)描述的系統中，當j=i+1時，

當j≠i+1且j≠i時，aij=0；i=1，2，…，n。此時，直接指向成員i+1的控制ui∈R2變為

式中，a為常數。個體運動學方程為：

以向量形式表示為

式中：Π為基本循環矩陣；In為n階單位矩陣。此種追蹤方式表示“一對一”線性循環追蹤運動控制，信息交流機制相對簡單，更利于工程應用與實現。

3 非線性循環追蹤模型

以單輪機器人類型的非完整約束系統為例，其運動方程一般表示為

式中，(x,y)∈R2表示個體在平面內的位置；θ表示運動方向；(u,ω)∈R2表示切向速度和角速度控制輸入。式(7)描述個體運動簡單直觀，但不便描述需要的追蹤控制律。為此，引入在相對坐標系下描述非線性循環追蹤問題的方式[9]。系統中含2個成員和3個成員時，循環追蹤的相對運動描述如圖2所示。圖2中：ri表示個體i與i+1的距離；αi表示個體i實際速度方向與期望速度方向的夾角；βi表示個體i實際速度反方向與個體i+1速度方向的夾角。

個體i的運動方程可表示為

圖2 兩成員和三成員循環追蹤相對坐標Fig. 2 Relative coordinate in cyclic pursuit for two agents and three agents

對于包含n個成員的多個體系統，成員相對坐標式(8)定義的多個體系統相對運動方程存在如下關系：

(1) 若對個體運動施加控制：

式中：kα為常數控制增益，kα＞0，vR＞0，由于速度控制量為定值，因此，稱為定速的非線性循環追蹤算法，此時，式(8)轉化為

(2) 若對個體運動施加控制：

式中：kr＞0；kα＞0，為常數控制增益，由于速度控制量為隨相對距離變化的變量，因此，稱為變速的非線性循環追蹤算法，此時，式(8)轉化為

4 仿真結果與分析

4.1 線性循環追蹤仿真分析

分別以3個體系統和5個體系統為例，對線性循環追蹤進行仿真。任意設定個體初始位置，個體依次按逆時針追蹤。3個體循環追蹤仿真時，初始位置分別取為(3, 5)，(0, 0)，(6. 0)， 5個體循環追蹤仿真時，初始位置分別取為(2, 7)，(0, 3)，(4. 0)，(7. 3)，(4. 7)，a取為2.0。仿真結果如圖3和圖4所示，圖中，橫、縱坐標分別表示x向位置和y向位置，已進行無量綱化處理(下同)。

由圖3和4可以看出：無論是3個體系統，還是5個體系統，在線性循環追蹤中，個體均以對數螺旋曲線運動收斂于初始幾何中心，且個體運動軌跡均為逆時針環繞。事實上，這一性質對n個體系統均成立。

圖3 3個體線性循環追蹤結果Fig. 3 Linear cyclic pursuit results for 3 agents

圖4 5個體線性循環追蹤結果Fig. 4 Linear cyclic pursuit results for 5 agents

4.2 定速的非線性循環追蹤仿真分析

以3個體系統為例，對定速的非線性循環追蹤進行仿真分析。

個體初始位置取為(2, 2)，(0, 0)，(1.5. 0)，個體按序列編號順次追蹤，追蹤速度相同，均取為1.0，控制增益kα分別為 1.0，3.0，5.0，7.0，仿真結果如圖 5所示。由圖5可以看出，3個體最終分布于以初始幾何中心為圓心、半徑相同的圓上；隨kα增大，最終形成的圓形軌跡中心不變，半徑逐漸減小。這是因為隨控制增益增大，個體運動方向調整速度加快，逐步接近線性循環追蹤情形。

圖5 定速非線性循環追蹤結果Fig. 5 Results for fixed-speed nonlinear cyclic pursuit

4.3 變速的非線性循環追蹤仿真分析

以3個體系統為例，對變速的非線性循環追蹤進行仿真分析。個體初始位置取為(6, 2)，(0, 0)，(1.5. 0)，個體按序列編號順次追蹤，追蹤速度相同，不失一般性，控制增益kα取為 1.0，kr分別取 0.3，0.6，0.9，仿真結果如圖6所示。

圖6 變速非線性循環追蹤結果Fig. 6 Results for variety-speed nonlinear cyclic pursuit

由圖6可以看出：系統最終狀態與kr取值有關；當kr較小時，系統收斂于初始幾何中心；當kr增大到一定值時，系統收斂于以初始幾何中心為圓心、半徑相同的圓上；當kr繼續增大到一定值時，系統發散。因此，在變速的非線性循環追蹤中，控制增益的合理選取尤為重要。

需要特別說明的是：上述關于各種循環追蹤算法的仿真結果表明了一個重要性質，即多個體系統采用循環追蹤控制策略時，系統收斂的中心就是其初始幾何中心，與運動過程無關。

5 結論

(1)首次對循環追蹤算法的演進過程進行了系統總結。分別建立和推導了線性循環追蹤、定速非線性循環追蹤和變速非線性循環追蹤算法模型。

(2) 線性循環追蹤中，個體均以對數螺旋曲線軌跡收斂于初始幾何中心；定速非線性循環追蹤中，個體收斂于以初始幾何中心為圓心、半徑相同的圓上，且最終形成圓的半徑由角度控制增益決定；變速非線性循環追蹤中，系統最終狀態與kr有關，隨kr逐漸增大，系統經歷由收斂于初始幾何中心、收斂于以初始幾何中心為圓心的圓上和發散的不同狀態。

(3) 循環追蹤算法只需獲取個體局部信息，便可實現對系統的全局控制，是具有獨特優勢和廣闊應用前景的新方法。下一步將研究其在衛星編隊飛行控制中的應用。

[1]Desai J P, Ostrowski J P, Kumar V. Modeling and control of formations of nonholonomic mobile robots[J]. IEEE Transactions on Robotics and Automation, 2001, 17(6):905?908.

[2]Rahmani A, Ji M, Mesbahi M, et al. Controllability of multi-agent systems from a graph-theoretic perspective[J]. SIAM Journal on Control and Optimization, 2009, 48(1): 162?186.

[3]Marshall J A, Broucke M E, Francis B A. Formations of vehicles in cyclic pursuit[J]. IEEE Transactions on automatic control,2004, 49(11): 1963?1974.

[4]Gehrels T, Helum C, Rahul K, et al. Study of nonlinear cyclic pursuit strategies applied to MAV swarms[R]. Bangalore: Indian Institute of Science, Department of Aerospace Engineering, 2011:9?12.

[5]Nahin P J. The mathematics of pursuit and evasion[M].Princeton: Princeton University Press, 2007: 23?24.

[6]楊濤. 面向空間任務的追蹤理論與應用研究[D]. 長沙: 國防科學技術大學航天與材料工程學院, 2010: 7?8.YANG Tao. Research on pursuit theory and its application to space mission[D]. Changsha: National University of Defense Technology, College of Aerospace and Materials Engineering,2010: 7?8.

[7]Clapham J C. Playful mice[J]. Recreational Mathematics Magazine, 1962, 22(8): 6?7.

[8]Klamkin M S, Newman D J. Cyclic pursuit or 'the three bugs problem[J]. American MathematIcal Monthly, 1971, 40(6/7):631?639.

[9]Marshall J A. Coordinated autonomy: Pursuit formations of multivehicle systems[D]. Toronto: University of Toronto.Department of Electrical and Computer Engineering, 2005:5?10.

[10]Gehrels T. Pursuit techniques on pioneer robots[R]. Maryland:University of Maryland, Institute for Systems Research, 2007:8?16.

[11]Galloway K S. Cyclic pursuit: Symmetry, reduction and nonlinear dynamics[D]. Maryland: University of Maryland,Institute for Systems Research, 2011.

[12]Kim T H, Hara S, Hori Y. Stabilization of multi-agent dynamical systems for cyclic pursuit behavior[R]. Tokyo: University of Tokyo. School of Information and Science and Technology, 2009:10?13.

[13]Hara S, Kim T H, Hori Y. Distributed formation control for target-enclosing operations by multiple dynamics agents based on a cyclic pursuit strategy[R]. Tokyo: University of Tokyo.School of Information and Science and Technology, 2007: 7?15.

[14]Jaime L. New decentralized algorithms for spacecraft formation control based on a cyclic approach[D]. Massachusetts:Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2010.