基于拍賣算法的多機器人編隊時間優化

孫延標，黃潤才

（上海工程技術大學 電子電氣工程學院，上海 201620）

0 引言

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

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

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

1 領航-跟隨法編隊的運動學模型

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

1.1 領航者運動學模型

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

圖1 領航者運動學模型

由圖1可知，可將領航者的運動學模型表示為：

1.2 跟隨者運動學模型

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

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

圖2 領航—跟隨者運動學模型

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

跟隨者的位置點由領航者位置點可得：

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

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

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

對式(6)的兩邊求導可得系統的動態誤差方程為：

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

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

2 多機器人編隊的時間優化

多機器人協作任務經常是要求雜亂無序的各機器人以最快的時間到達指定的地點，形成需要的編隊隊形完成系統設定的任務。本文提出的多機器人編隊時間優化是通過領航者依據拍賣算法以各跟隨者投標競拍的目標點時間最優實現對隊形中各位置點的指定，最終完成編隊的隊形。

2.1 拍賣算法

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

目標點拍賣：作為拍賣方的領航者將需要跟隨的各個目標點拍賣出去。

圖3 目標點拍賣

跟隨者競拍：作為投標方的跟隨者依據自身的綜合優勢投標競拍適合自己的目標點。

圖4 跟隨者競拍

目標點分配：領航者根據最終的投標結果將各目標點分配給指定的跟隨者以完成編隊隊形。

圖5 目標點分配

2.2 時間優化

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

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

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

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

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

1) 作為拍賣方的領航機器人拍賣各個目標點；

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

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

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

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

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

初始的時間矩陣為：

最終的目標點分配矩陣為：

其中，R0為領航機器人，R1，…，Rn為各跟隨機器人，Rv0，Rv1…，Rvn為虛擬跟隨機器人，即需要跟隨的各目標點。

圖6 拍賣算法流程圖

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

3 仿真實驗

為了驗證本文提出的以拍賣算法優化實現領航—跟隨法多機器人編隊隊形的整體形成時間，使用MATLAB軟件進行仿真實驗。實驗以6個機器人編隊實現三角形隊形運動為例，各機器人的初始位姿任意，設領航者的初始位姿，跟隨者的初始位姿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仿真結果如下：

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

圖7 機器人的初始位姿以及目標點位置

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

圖8 機器人向目標點位置移動的運動過程

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

圖9 各機器人到達目標點位置形成的三角形隊形

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

圖10 各機器人向目標點位置移動的運動軌跡

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

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

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

4 結語

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

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