基于拍賣算法的多機(jī)器人編隊(duì)時(shí)間優(yōu)化

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

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

0 引言

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

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

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

1 領(lǐng)航-跟隨法編隊(duì)的運(yùn)動(dòng)學(xué)模型

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

1.1 領(lǐng)航者運(yùn)動(dòng)學(xué)模型

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

圖1 領(lǐng)航者運(yùn)動(dòng)學(xué)模型

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

1.2 跟隨者運(yùn)動(dòng)學(xué)模型

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

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

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

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

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

跟隨者的位置點(diǎn)與虛擬跟隨機(jī)器人位置點(diǎn)的誤差可表示為：

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

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

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

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

由上述可得跟隨者的運(yùn)動(dòng)學(xué)模型為：

2 多機(jī)器人編隊(duì)的時(shí)間優(yōu)化

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

2.1 拍賣算法

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

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

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

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

圖4 跟隨者競拍

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

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

2.2 時(shí)間優(yōu)化

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

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

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

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

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

1) 作為拍賣方的領(lǐng)航機(jī)器人拍賣各個(gè)目標(biāo)點(diǎn)；

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

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

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

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

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

初始的時(shí)間矩陣為：

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

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

圖6 拍賣算法流程圖

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

3 仿真實(shí)驗(yàn)

為了驗(yàn)證本文提出的以拍賣算法優(yōu)化實(shí)現(xiàn)領(lǐng)航—跟隨法多機(jī)器人編隊(duì)隊(duì)形的整體形成時(shí)間，使用MATLAB軟件進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)以6個(gè)機(jī)器人編隊(duì)實(shí)現(xiàn)三角形隊(duì)形運(yùn)動(dòng)為例，各機(jī)器人的初始位姿任意，設(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é)果如下：

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

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

機(jī)器人向目標(biāo)點(diǎn)位置移動(dòng)的運(yùn)動(dòng)過程如圖8所示。

圖8 機(jī)器人向目標(biāo)點(diǎn)位置移動(dòng)的運(yùn)動(dòng)過程

各機(jī)器人到達(dá)目標(biāo)點(diǎn)位置形成的三角形隊(duì)形如圖9所示。

圖9 各機(jī)器人到達(dá)目標(biāo)點(diǎn)位置形成的三角形隊(duì)形

各機(jī)器人向目標(biāo)點(diǎn)位置移動(dòng)的運(yùn)動(dòng)軌跡如圖10所示。

圖10 各機(jī)器人向目標(biāo)點(diǎn)位置移動(dòng)的運(yùn)動(dòng)軌跡

多機(jī)器人形成三角形隊(duì)形所用的編隊(duì)時(shí)間如表1所示。

表1 多機(jī)器人形成三角形隊(duì)形所用的編隊(duì)時(shí)間

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

4 結(jié)語

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

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