孫延標(biāo)，黃潤才

（上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620）

0 引言

人工智能的快速發(fā)展，促進機器人系統(tǒng)進入了一個嶄新的研究領(lǐng)域，多機器人的編隊控制受到越來越多的研究者關(guān)注。人們對機器人復(fù)雜任務(wù)的完成要求越來越高，諸如營救行動、捕捉獵物以及障礙清除等一些任務(wù)中，傳統(tǒng)的單機器人已經(jīng)滿足不了需求，多機器人編隊的引入成為了可行的途徑。文獻[1]提出了一種多移動機器人編隊完成的分布式控制算法，該算法簡單易行，適合大量的機器人。按照多機器人編隊的體系結(jié)構(gòu)，編隊控制主要分為集中式、分布式和分層式三種[2]。集中式是由一個主控單元控制多機器人系統(tǒng)，該方法全局優(yōu)化能力較高，通常應(yīng)用在路徑規(guī)劃等方面[3]，但靈活性較差。分布式則是各機器人的行為自主決定，該方法靈活可靠，在任務(wù)分配方面很廣泛的應(yīng)用[4]，但全局目標(biāo)優(yōu)化能力較差。分層式是混合了集中式與分布式，機器人之間的協(xié)作性較強，文獻[5]提出了一種自然啟發(fā)性的方法用于多機器人的協(xié)調(diào)合作，平衡了任務(wù)的執(zhí)行。

常用的編隊控制方法有人工勢場法[6]、虛擬結(jié)構(gòu)法[7]、基于行為的方法[8]以及基于圖論的方法[9]等。文獻[6]采用人工勢場法維持多機器人的隊形并規(guī)劃各機器人的路徑，避免了各機器人之間的碰撞，實時性較強，但當(dāng)勢力場較多以及零勢能點存在時，機器人會在小范圍內(nèi)往復(fù)運動。文獻[7]將人工勢場法與虛擬結(jié)構(gòu)法相結(jié)合，可以有效的形成編隊隊形以及靈活的隊形變換，并且在編隊行進過程中很好的避免碰撞障礙物，但由于嚴格的隊形約束會受到頻繁的控制指令，通信過載，增加能耗。文獻[8]將多機器人的編隊任務(wù)分解成不同的行為，使用零空間的矩陣理論方法根據(jù)一定的優(yōu)先級融合行為形成最終的隊形，有著明確的隊形反饋，系統(tǒng)的應(yīng)變能力較強，但由于行為融合復(fù)雜，隊形的基本行為無法明確定義，編隊控制的穩(wěn)定性難以得到保證。文獻[9]將編隊整體看作一個有向圖，通過距離反饋控制率設(shè)計不同的控制策略形成編隊的隊形，隊形結(jié)構(gòu)穩(wěn)定，拓撲結(jié)構(gòu)簡單明了，但對于稀疏的圖，效率較低。這些方法在編隊形成的整體時間等性能上考慮的較少，然而在一些關(guān)鍵的任務(wù)中，如圍捕獵物、營救行動等編隊的過程中，隊形形成時間的長短，對任務(wù)的完成、能量的損耗有著重大影響，有效的縮短隊形形成時間，可以減少通信等待，快速完成相應(yīng)的任務(wù)。任務(wù)的分配在編隊控制中應(yīng)用的也非常多，合理的利用有效資源對編隊任務(wù)完成尤其重要。文獻[10]根據(jù)一些知識規(guī)則和策略采用合同網(wǎng)協(xié)議對各機器人任務(wù)分配，有效協(xié)調(diào)了多機器人編隊探索。文獻[11]將強化學(xué)習(xí)引入到拍賣算法中實現(xiàn)任務(wù)分配的動態(tài)調(diào)整，完成編隊的狩獵任務(wù)。文獻[12]利用市場架構(gòu)以最大化信息收益，來提高整個團隊協(xié)調(diào)探索的效率。文獻[13]提出一種確定拍賣人與競價值的方法，優(yōu)化了多機器人的任務(wù)分配。目前，各類編隊的最優(yōu)控制有著很多的局限性，與實際還有一定的差距，如以反復(fù)迭代對路徑優(yōu)化，造成時間過長滿足不了實時的要求；長時間頻繁的數(shù)據(jù)通信對系統(tǒng)的要求偏高以及動態(tài)環(huán)境下未知因素的欠考慮也會造成影響等。

針對上述研究的一些不足，本文在領(lǐng)航—跟隨法的基礎(chǔ)上，對多機器人隊形的形成時間進行了研究，融合了在多機器人系統(tǒng)中任務(wù)分配常用的拍賣算法[10～13]，將編隊的整體任務(wù)分解成了各機器人對跟隨目標(biāo)的投標(biāo)競拍追蹤任務(wù)。本文將隊形的形成時間作為編隊性能的重要指標(biāo)，以各機器人到達跟隨目標(biāo)點的運動時間作為投標(biāo)競拍的依據(jù)，最終完成指定的編隊隊形。

1 領(lǐng)航-跟隨法編隊的運動學(xué)模型

對于領(lǐng)航-跟隨法多機器人編隊，一般而言，作為領(lǐng)航者機器人的運動學(xué)模型可以依據(jù)自身的位姿信息來確定，而對于作為跟隨者機器人的運動學(xué)模型則必須是依據(jù)領(lǐng)航者的位姿信息，通過與領(lǐng)航者的相對距離和相對角度來構(gòu)建自身的運動學(xué)模型。因輪式移動機器人的無滑動滾動特征決定了多機器人系統(tǒng)滿足非完整約束的條件[14]，故在本文中主要以輪式的移動機器人為研究對象，采用與文獻[14]相似的表示方式。

1.1 領(lǐng)航者運動學(xué)模型

設(shè)移動機器人在全局坐標(biāo)系下的位姿信息為(x，y，θ)，其中，(x，y)為機器人對應(yīng)的位置坐標(biāo)，θ為方向角，即機器人的線速度方向與坐標(biāo)軸x軸正方向的夾角，如圖1所示，v(t)與w(t)分別表示機器人在某一時刻t下的線速度與角速度。并且機器人的位姿信息可由向量p=(x，y，θ)T表示。

圖1 領(lǐng)航者運動學(xué)模型

由圖1可知，可將領(lǐng)航者的運動學(xué)模型表示為：

1.2 跟隨者運動學(xué)模型

為了簡單方便的描述各機器人在整個編隊中的位置，將隊形中的領(lǐng)航者機器人標(biāo)記為RL，任意的跟隨者機器人標(biāo)記為RF，領(lǐng)航者期望跟隨的虛擬機器人標(biāo)記為RV，則領(lǐng)航—跟隨法編隊控制的運動學(xué)模型如圖2所示。

在圖2中，領(lǐng)航者機器人的線速度表示為vL，角速度表示為wL，線速度方向與坐標(biāo)軸x軸正方向的夾角表示為θL；跟隨者機器人的線速度表示為vF，角速度表示為wF，線速度方向與坐標(biāo)軸x軸正方向的夾角表示為θF[15]。將機器人兩車輪的軸心線連接的中點作為對象研究的參考點，則領(lǐng)航者與跟隨者這2個機器人參考點之間的距離表示為lL-F，領(lǐng)航者機器人的前進方向即線速度方向與2個機器人參考點連線的夾角表示為φL-F。

圖2 領(lǐng)航—跟隨者運動學(xué)模型

對于一個領(lǐng)航—跟隨法的多機器人編隊系統(tǒng)來說，整個團隊的運動軌跡通常是由領(lǐng)航者進行決定的，而跟隨者到達目標(biāo)點的運動軌跡往往是由領(lǐng)航者期望的虛擬跟隨機器人運動軌跡決定的。設(shè)跟隨者與領(lǐng)航者形成最終需要達到的期望距離與角度分別為，即虛擬跟隨機器人與領(lǐng)航者機器人之間的距離與角度分別為與。虛擬跟隨機器人的位置坐標(biāo)表示為（xV，yV），線速度方向與坐標(biāo)軸x軸正方向的夾角即方向角表示為θV，虛擬跟隨機器人的位置點由領(lǐng)航者機器人位置點可得：

跟隨者的位置點由領(lǐng)航者位置點可得：

跟隨者的位置點與虛擬跟隨機器人位置點的誤差可表示為：

通過旋轉(zhuǎn)矩陣，可將其旋轉(zhuǎn)變換到跟隨者機器人RF自身的坐標(biāo)系xF-yF下，則其誤差可表示為：

將式(3)和式(4)帶入式(5)中可得：

對式(6)的兩邊求導(dǎo)可得系統(tǒng)的動態(tài)誤差方程為：

對于虛擬跟隨機器人的引入，將多機器人編隊的隊形保持轉(zhuǎn)換成了實際跟隨機器人追蹤虛擬跟隨機器人的運動軌跡的控制，這種模型的建立可以描述任意多機器人編隊的隊形。

由上述可得跟隨者的運動學(xué)模型為：

2 多機器人編隊的時間優(yōu)化

多機器人協(xié)作任務(wù)經(jīng)常是要求雜亂無序的各機器人以最快的時間到達指定的地點，形成需要的編隊隊形完成系統(tǒng)設(shè)定的任務(wù)。本文提出的多機器人編隊時間優(yōu)化是通過領(lǐng)航者依據(jù)拍賣算法以各跟隨者投標(biāo)競拍的目標(biāo)點時間最優(yōu)實現(xiàn)對隊形中各位置點的指定，最終完成編隊的隊形。

2.1 拍賣算法

本文提出的拍賣方法主要分為3個過程：目標(biāo)點的拍賣、跟隨者的競拍以及目標(biāo)點的分配。

目標(biāo)點拍賣：作為拍賣方的領(lǐng)航者將需要跟隨的各個目標(biāo)點拍賣出去。

圖3 目標(biāo)點拍賣

跟隨者競拍：作為投標(biāo)方的跟隨者依據(jù)自身的綜合優(yōu)勢投標(biāo)競拍適合自己的目標(biāo)點。

圖4 跟隨者競拍

目標(biāo)點分配：領(lǐng)航者根據(jù)最終的投標(biāo)結(jié)果將各目標(biāo)點分配給指定的跟隨者以完成編隊隊形。

圖5 目標(biāo)點分配

2.2 時間優(yōu)化

對于無序的機器人形成指定的編隊隊形，在領(lǐng)航-跟隨法多機器人編隊中，以作為拍賣方的領(lǐng)航者對在編隊隊形中各個位置點的指定是通過對作為投標(biāo)方的跟隨者競拍到達各目標(biāo)點的時間優(yōu)化實現(xiàn)，其形式可以表示為：

其中，i代表在隊形中各實際機器人的編號；Tim為目標(biāo)函數(shù)，即機器人i到達跟隨目標(biāo)點m所需要的時間；cim為成本函數(shù)，即機器人i能夠到達跟隨目標(biāo)點m的綜合優(yōu)勢；Aim為獎勵函數(shù)，即機器人i到達跟隨目標(biāo)點m后隊形的形成程度，可通過目標(biāo)點相對于機器人i的綜合優(yōu)勢來計算。

機器人的綜合優(yōu)勢包括距離優(yōu)勢、角度優(yōu)勢與能量優(yōu)勢[16]，可用cl表示距離優(yōu)勢，cθ表示角度優(yōu)勢，ce表示能量優(yōu)勢：

其中，λ0=（λmax+λmin）/2，若令Cl（λmax）=Cl（λmin）=0.05，可得σ=0.6（λmax-λmin），λ為實際機器人與跟隨目標(biāo)點的距離；λmax、λmin分別為實際機器人和虛擬機器人與領(lǐng)航者的距離；θF、θV分別為實際機器人與虛擬機器人的方位角；EF、EV分別為實際機器人與虛擬機器人的單位能量。根據(jù)專家的一些經(jīng)驗，wl，wθ，we的值可取為0.5，0.3，0.2。

由最初得到的時間矩陣T出發(fā)，經(jīng)過迭代求解出完成編隊隊形最短時間的目標(biāo)點分配矩陣X，主要步驟為：

1) 作為拍賣方的領(lǐng)航機器人拍賣各個目標(biāo)點；

2) 作為投標(biāo)方的實際跟隨機器人以通過計算得出的到達各目標(biāo)點時間t競標(biāo)并將t排入到時間矩陣T中；

3) 領(lǐng)航機器人比較T中的元素，并將最大元素的值置為0；

4) 經(jīng)過重置后若T為對角矩陣，轉(zhuǎn)到步驟6)；若T中的某一行或者某一列有且僅有一個非零的元素，那么拍賣方就將該元素所在的行與列其他所有元素的值都置為0；

5) 重復(fù)步3)、4)直到可以得出T中每行每列只剩下一個非零的元素；

6) 拍賣方按照最終得到的時間矩陣T，在對應(yīng)位置同步設(shè)置分配矩陣X非零元素的值為1，其他元素的值為0，則可以得出最終的目標(biāo)點優(yōu)化分配矩陣X。

初始的時間矩陣為：

最終的目標(biāo)點分配矩陣為：

其中，R0為領(lǐng)航機器人，R1，…，Rn為各跟隨機器人，Rv0，Rv1…，Rvn為虛擬跟隨機器人，即需要跟隨的各目標(biāo)點。

圖6 拍賣算法流程圖

該方法簡單易行，將需要處理的最小值搜索問題較合理的轉(zhuǎn)換到領(lǐng)航-跟隨法多機器人編隊中作為投標(biāo)方的跟隨者上，減少了作為拍賣方的領(lǐng)航者計算量。在多機器人的團隊中，各跟隨者希望最大化隊形的完成時間而依此向領(lǐng)航者投標(biāo)競拍跟隨目標(biāo)點，但領(lǐng)航者希望最小化隊形的完成時間而依此向各跟隨者拍賣跟隨目標(biāo)點，最終領(lǐng)航者根據(jù)需要的結(jié)果協(xié)調(diào)完成系統(tǒng)指定的編隊。

3 仿真實驗

為了驗證本文提出的以拍賣算法優(yōu)化實現(xiàn)領(lǐng)航—跟隨法多機器人編隊隊形的整體形成時間，使用MATLAB軟件進行仿真實驗。實驗以6個機器人編隊實現(xiàn)三角形隊形運動為例，各機器人的初始位姿任意，設(shè)領(lǐng)航者的初始位姿，跟隨者的初始位姿RL=[-4 0 0]T，RF1=[-5 4 0]T，RF2=[-5 2 0]T，RF3=[-5 0 0]T，RF4=[-5 -2 0]T，RF5=[-5 -4 0]T仿真結(jié)果如下：

機器人的初始位姿以及目標(biāo)點位置如圖7所示。

圖7 機器人的初始位姿以及目標(biāo)點位置

機器人向目標(biāo)點位置移動的運動過程如圖8所示。

圖8 機器人向目標(biāo)點位置移動的運動過程

各機器人到達目標(biāo)點位置形成的三角形隊形如圖9所示。

圖9 各機器人到達目標(biāo)點位置形成的三角形隊形

各機器人向目標(biāo)點位置移動的運動軌跡如圖10所示。

圖10 各機器人向目標(biāo)點位置移動的運動軌跡

多機器人形成三角形隊形所用的編隊時間如表1所示。

表1 多機器人形成三角形隊形所用的編隊時間

由圖9可知，當(dāng)在拍賣算法編隊下的各機器人到達目標(biāo)點位置形成三角形隊形時，即編隊完成；領(lǐng)航—跟隨法編隊下的各機器人還未完全到達目標(biāo)點位置，即還未完成三角形隊形的編隊。由表1可知，在拍賣算法下，多機器人編隊完成所用的時間約為8.43s；在領(lǐng)航—跟隨法下，多機器人編隊完成所用的時間約為10.44s。綜上所訴，在本文提出的編隊方法下，多機器人編隊的隊形完成時間明顯縮短，隊形形成效率明顯提高。

4 結(jié)語

本文在考慮多機器人編隊整體隊形完成時間最小化的條件下，將編隊的控制問題轉(zhuǎn)換成了跟隨者投標(biāo)競拍的問題來求解，主要為：將拍賣算法應(yīng)用在領(lǐng)航-跟隨法多機器人編隊系統(tǒng)中領(lǐng)航者對跟隨者在隊形中各位置點的指定上，跟隨者以競價的方式獲得各自適合跟隨的目標(biāo)點來完成需要的隊形。最終仿真結(jié)果表明在本文提出的編隊控制方法下不僅隊形的形成效率較高，而且保證了隊形的完整性，靈活可靠。

在本文的多機器人編隊環(huán)境下拍賣方與投標(biāo)方之間有著較頻繁的數(shù)據(jù)交流，通信依賴較強，因此如何減輕各機器人之間的通信負擔(dān)是下一步的研究重點，此外對于領(lǐng)航-跟隨法多機器人編隊中領(lǐng)航者依賴性的解決也是研究重點。