侯向輝,盧 濤,張美玉,簡(jiǎn)琤峰

(浙江工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院數(shù)字媒體技術(shù)研究所,杭州 310023)

1 引 言

群組機(jī)器人是由一群無(wú)差別的微型機(jī)器人組成的群體,具有典型分布式系統(tǒng)的特征,通過(guò)這些有限個(gè)的能力局限的機(jī)器人交互、協(xié)調(diào)等來(lái)完成復(fù)雜的任務(wù).與傳統(tǒng)智能機(jī)器人相比,群組機(jī)器人在靈活性、成本控制、穩(wěn)定性等方面有著絕對(duì)的優(yōu)勢(shì).文獻(xiàn)[1]將群組機(jī)器人用于水下通信方面,文獻(xiàn)[2]將其用于部署無(wú)線網(wǎng)狀網(wǎng)絡(luò)(WMN),群組機(jī)器人也被應(yīng)用于圖形展示[3]以及工業(yè)紡織[4]等方面,可見(jiàn)群組機(jī)器人在各個(gè)領(lǐng)域正發(fā)揮獨(dú)特的作用.群組機(jī)器人的研究領(lǐng)域中,路徑規(guī)劃是關(guān)鍵一步,其目的是為了在機(jī)器人能接受的能量消耗成本下并避免碰撞以實(shí)現(xiàn)目標(biāo)配置.當(dāng)前已有相關(guān)研究解決群體機(jī)器人路徑規(guī)劃問(wèn)題,如領(lǐng)導(dǎo)者-跟隨者策略,行為和規(guī)則方法,虛擬結(jié)構(gòu)方式、基于壓縮voronoi圖實(shí)現(xiàn)自組裝的方法等[5,6].領(lǐng)導(dǎo)者跟隨策略方面,Peng等人提出的方法[7]是通過(guò)選出領(lǐng)導(dǎo)機(jī)器人,其它機(jī)器人并保持一定距離的跟隨來(lái)實(shí)現(xiàn)的,R.Haghighi等人為了更好地解決機(jī)器人數(shù)量較多的問(wèn)題而提出的多組協(xié)調(diào)控制方法也是基于領(lǐng)導(dǎo)者-跟隨者策略.Xu、L.Pitonakova等人提出的[8,9]基于行為和規(guī)則方法通過(guò)模擬生物活動(dòng)規(guī)律來(lái)實(shí)現(xiàn)機(jī)器人的路徑規(guī)劃,A.Kolling則將人類群體交互(HSI)的概念引入機(jī)器人的路徑規(guī)劃當(dāng)中[10].L.Pitonakova等人提出的信息-成本-獎(jiǎng)勵(lì)(ICR)框架,該框架涉及機(jī)器人獲取和共享信息與群體利用信息的能力,以便在特定任務(wù)和環(huán)境的情況下有效通過(guò)獎(jiǎng)勵(lì)機(jī)制合理規(guī)劃?rùn)C(jī)器人的運(yùn)動(dòng).虛擬結(jié)構(gòu)方面還有Ren等人提出的虛擬結(jié)構(gòu)在車編隊(duì)中的分散[11].由Wei等人提出的基于質(zhì)心Voronoi鑲嵌[12]的智能控制算法[13]為解決L.Bayindir提出的中央?yún)f(xié)調(diào)思想提供了可行方案,Wei等實(shí)現(xiàn)的同步協(xié)作調(diào)度策略CVT(Centroidal Voronoi Tessellation)算法在時(shí)間和路程損耗上都有了很大程度上的優(yōu)化,然而這一通過(guò)壓縮來(lái)驅(qū)使機(jī)器人移動(dòng)的方案仍然存在這一些問(wèn)題:1)由于采用了被動(dòng)的壓縮方案,僅通過(guò)限定可活動(dòng)區(qū)域來(lái)趨使機(jī)器人到達(dá)目標(biāo)點(diǎn)會(huì)造成一定的誤差;2)CVT算法的死鎖(deadlock)現(xiàn)象需要花費(fèi)大量的時(shí)間去判斷;3)由于采用矩形組合的方式實(shí)現(xiàn)目標(biāo)配置,所以無(wú)法形成帶有弧度的目標(biāo)配置,目標(biāo)配置類型較少;4)CVT算法要求初始分布為均勻分布,但是當(dāng)機(jī)器人堆積在一處時(shí),會(huì)為矩陣劃分帶來(lái)困難,方案適用性方面較差;5)由于并未為機(jī)器人設(shè)置目標(biāo)地,在迭代的過(guò)程中,機(jī)器人的運(yùn)動(dòng)缺少目的性,能量消耗過(guò)多；6)死鎖(deadlock)現(xiàn)象在高維頻發(fā),造成CVT算法在高維求解能力上表現(xiàn)較差.

本文提出的VBIT(Voronoi′s Boundary Intersection Tessellation)算法是一種主動(dòng)性同步協(xié)作調(diào)度策略,首先確定目標(biāo)配置的目標(biāo)點(diǎn)(TP),采用Hungarian算法[14,15]為每個(gè)機(jī)器人分配TP,確定TP與起始點(diǎn)(DP)的連線與根據(jù)Voronoi圖劃分算法確定的多邊形區(qū)域(cell)之間的位置關(guān)系[16]并將兩者的交點(diǎn)作為機(jī)器人下一步運(yùn)動(dòng)起始點(diǎn)的方法,來(lái)完成機(jī)器人主動(dòng)完成自組裝任務(wù)的目的,通過(guò)matlab仿真對(duì)比實(shí)驗(yàn)證明了VBIT算法在時(shí)間消耗和路徑長(zhǎng)度上的改進(jìn)效果,并展示了幾種復(fù)雜的目標(biāo)配置以及高維時(shí)的求解能力.

2 CVT算法

CVT算法的核心思想是利用Centroidal Voronoi的特點(diǎn)來(lái)實(shí)現(xiàn)機(jī)器人之間的碰撞避免和群組機(jī)器人的全局路徑規(guī)劃,通過(guò)壓縮機(jī)器人的可活動(dòng)區(qū)域來(lái)改變每一個(gè)cell的質(zhì)心位置,以該點(diǎn)作為下一次迭代時(shí)機(jī)器人的目標(biāo)位置,如此地反復(fù)操作,將所有機(jī)器人驅(qū)使到目標(biāo)位置,過(guò)程中發(fā)生的死鎖情況,通過(guò)粒子擾動(dòng)來(lái)打破.

時(shí)間方面:由于傳統(tǒng)CVT算法在機(jī)器人的移動(dòng)問(wèn)題上始終是被動(dòng)的,所以造成了每次的壓縮過(guò)程中部分機(jī)器人的移動(dòng)緩慢.在迭代后期,由于可行區(qū)域壓縮的程度并不大,質(zhì)心的移動(dòng)距離小,所以后期群組機(jī)器人整體的移動(dòng)也十分緩慢,造成了無(wú)故的時(shí)間消耗,同時(shí)死鎖的判斷也需要耗費(fèi)大量的時(shí)間.在復(fù)雜的目標(biāo)配置以及機(jī)器人數(shù)量較多的情況下,CVT算法發(fā)生死鎖的概率大大增加,造成其在復(fù)雜目標(biāo)配置及高維情況下求解的時(shí)間大幅增長(zhǎng)或無(wú)法得出目標(biāo)配置.

路徑方面:傳統(tǒng)CVT算法通過(guò)將壓縮后形成的質(zhì)心位置作為下一次機(jī)器人運(yùn)動(dòng)的目標(biāo)點(diǎn),這一策略雖能避免機(jī)器人之間的碰撞,但由于質(zhì)心的位置通常與機(jī)器人到目標(biāo)點(diǎn)的路線有一定的偏差,且每次的質(zhì)心位置僅與當(dāng)前的壓縮程度有關(guān),與目標(biāo)配置并無(wú)直接關(guān)系.

方案適用性方面:傳統(tǒng)CVT算法通過(guò)將機(jī)器人包含在不同的矩形區(qū)域中,通過(guò)壓縮這些區(qū)域,來(lái)實(shí)現(xiàn)不同形狀的目標(biāo)配置,該方案在較簡(jiǎn)單的目標(biāo)配置下表現(xiàn)出了較好的適用性,但是對(duì)于包含任意曲線或更為復(fù)雜的2D目標(biāo)配置則無(wú)法實(shí)現(xiàn).

3 VBIT算法

以上分析可見(jiàn),CVT算法的缺陷在于缺少主動(dòng)性,僅依靠被動(dòng)壓縮可活動(dòng)區(qū)域來(lái)達(dá)成目標(biāo)配置的方法在自組裝過(guò)程中會(huì)出現(xiàn)很多的不可控情況,其在目標(biāo)配置的精度和時(shí)間上的表現(xiàn)仍有較大的改進(jìn)空間.針對(duì)傳統(tǒng)CVT算法的缺陷,VBIT算法進(jìn)行了如下改進(jìn)來(lái)解決相應(yīng)問(wèn)題.VBIT算法不再通過(guò)壓縮可行區(qū)域的方案來(lái)驅(qū)使機(jī)器人到達(dá)目標(biāo)配置,而是將目標(biāo)配置具象化為若干的坐標(biāo)點(diǎn),由這些目標(biāo)配置點(diǎn)來(lái)描述目標(biāo)配置.匈牙利算法在此基礎(chǔ)上分配機(jī)器人和目標(biāo)配置點(diǎn)之間的對(duì)應(yīng)關(guān)系,當(dāng)機(jī)器人與目標(biāo)配置點(diǎn)之間的對(duì)應(yīng)關(guān)系確定后,分別做機(jī)器人與其對(duì)應(yīng)目標(biāo)配置點(diǎn)之間的連線,(為方便描述,在此定義機(jī)器人以及起始點(diǎn)的個(gè)數(shù)均為n)相應(yīng)地這條直線會(huì)與每個(gè)機(jī)器人所在的cell有一個(gè)交點(diǎn)P={Pi,i∈1,2,…,n}或TP已經(jīng)位于cell內(nèi),如有交點(diǎn),則這個(gè)交點(diǎn)將被作為該機(jī)器人下一次運(yùn)動(dòng)的目標(biāo)點(diǎn),否則直接移動(dòng)到TP.如此迭代,使得每個(gè)機(jī)器人都運(yùn)動(dòng)到目標(biāo)位置.目標(biāo)配置具象化可以有效解決目標(biāo)配置精度問(wèn)題、實(shí)現(xiàn)了算法的主動(dòng)性.匈牙利分配算法能夠有效地解決機(jī)器人與起始點(diǎn)的分配關(guān)系,減少了路徑長(zhǎng)度以及時(shí)間損耗,下面對(duì)VBIT算法的細(xì)節(jié)處進(jìn)行描述，流程圖如圖1所示.

圖1 VBIT算法流程圖Fig.1 VBIT algorithm flow chart

VBIT算法的整體流程:

1.得到目標(biāo)配置;

2.根據(jù)目標(biāo)配置求得相應(yīng)目標(biāo)點(diǎn)的坐標(biāo)位置,另外還有機(jī)器人初始位置,可活動(dòng)區(qū)域等參數(shù);

3.判斷是否所有機(jī)器人均到達(dá)目標(biāo)點(diǎn),如果是,則算法結(jié)束,否則順序執(zhí)行;

4.利用匈牙利算法為每個(gè)機(jī)器人分配目標(biāo)點(diǎn);

5.根據(jù)當(dāng)前機(jī)器人位置在可行區(qū)域內(nèi)生成Voronoi圖;

6.首先判斷每個(gè)目標(biāo)點(diǎn)是否在對(duì)應(yīng)機(jī)器人所在cell內(nèi),如果是,則直接將機(jī)器人移動(dòng)到目標(biāo)點(diǎn).否則,求得該機(jī)器人到對(duì)應(yīng)起始點(diǎn)連線與本cell的交點(diǎn),將機(jī)器人移動(dòng)到該點(diǎn).當(dāng)所有機(jī)器人移動(dòng)完后,返回到步驟3.

在上述過(guò)程中,TP坐標(biāo)位置、匈牙利算法與分配目標(biāo)點(diǎn)問(wèn)題的結(jié)合、判斷TP是否在cell內(nèi)、求解交點(diǎn)坐標(biāo)這些問(wèn)題在后續(xù)會(huì)進(jìn)行描述.

3.1 基于匈牙利算法的匹配

首先要解決機(jī)器人目標(biāo)配置分配問(wèn)題的標(biāo)準(zhǔn)化并建立標(biāo)準(zhǔn)化模型.要求解的是路徑最小和問(wèn)題,每一個(gè)機(jī)器人與起始點(diǎn)是惟一的一對(duì)一關(guān)系.可以歸類為指派問(wèn)題的數(shù)學(xué)模型,該模型的數(shù)學(xué)公式表達(dá)為:

目標(biāo)函數(shù):

(1)

Zij為成本函數(shù),記錄第i個(gè)機(jī)器人到j(luò)起始點(diǎn)的路徑距離,MinY為總成本.

i,j=1,2,…,n

(2)

(3)

約束條件

(4)

在本文的應(yīng)用環(huán)境中,成本函數(shù)矩陣Z由每個(gè)機(jī)器人對(duì)應(yīng)所有起始點(diǎn)的距離所組成,且Z為方陣.如表1所示.

表1 成本函數(shù)矩陣Z
Table 1 Cost function matrix Z

TPRBj=1j=2j=3……i=1z11z12z13……i=2z21z22z23……i=3z31z32z33…………………………zij

算法步驟:

步驟1.建立資源分配問(wèn)題的效益矩陣z0(n*n).

步驟2.從效益矩陣z0每行減去該行最小的元素,使得每行都有一個(gè)零元素,得到z1.

步驟3.從z1每列減去該列最小的元素,使得每列都有一個(gè)零元素,得到z2.

步驟4.用最少的直線覆蓋z2中的零元素得到z3,如果最少直線的數(shù)量等于n,轉(zhuǎn)入步驟6,否則轉(zhuǎn)入步驟 5.

步驟5.矩陣z3中所有未被直線覆蓋的元素減去未被覆蓋元素中最小的元素,同時(shí)在直線相交點(diǎn)加上該最小元素得到z4,令z2=z4,轉(zhuǎn)步驟4.

步驟6.從零元素最少的行或列開(kāi)始指派,直到所有任務(wù)都指派完畢,得到最優(yōu)指派方案P.

計(jì)算過(guò)程中涉及到的同行加減一個(gè)常數(shù)后的矩陣Z是否會(huì)發(fā)生變化,以下公式證明了前后求得的最優(yōu)解是相同的.

定理1.設(shè)矩陣Z的第i行對(duì)應(yīng)的常數(shù)為di

(5)

(6)

f與c僅是兩個(gè)常數(shù),所以兩目標(biāo)在相同約束條件下,最優(yōu)解是相同的.

MinY=sum(P.*Z0)

(7)

目標(biāo)函數(shù)MinY即為所求最小路徑成本.

3.2 機(jī)器人和對(duì)應(yīng)目標(biāo)點(diǎn)連線與機(jī)器人所在cell的交點(diǎn)問(wèn)題

首先需要判斷起始點(diǎn)是否在機(jī)器人所在cell內(nèi),如果不在,則位置關(guān)系如圖2所示,否則,位置關(guān)系如圖3所示.

從圖2,圖3中可以看出利用匈牙利算法為每個(gè)機(jī)器人分配的起始點(diǎn)和機(jī)器人當(dāng)前位置的連線與機(jī)器人所在cell的交點(diǎn)即為機(jī)器人下次運(yùn)動(dòng)的起始點(diǎn),這樣在最大程度上保證了機(jī)器人移動(dòng)的路徑優(yōu)化程度.

圖2 目標(biāo)點(diǎn)位于cell外Fig.2 Target point is outside the cell

圖3 目標(biāo)點(diǎn)位于cell內(nèi)Fig.3 Target point in the cell

求交的實(shí)現(xiàn)方法為PNPLOY算法,首先判斷起始點(diǎn)是否在cell內(nèi),如果待測(cè)點(diǎn)在多邊形內(nèi),從起始點(diǎn)引出一條射線必會(huì)與多邊形有至少一個(gè)交點(diǎn).交點(diǎn)為奇數(shù)個(gè)時(shí)表示該點(diǎn)位于多邊形內(nèi)部,反之則位于外部.偽代碼表示為:

int count=0;

//以起始點(diǎn)P為端點(diǎn)從右向左引一條射線L

for(cell的一條邊S)//遍歷cell的每一條邊

if(P在邊S上)

P位于cell內(nèi);

end

if(S不是水平的)

if(S的一個(gè)端點(diǎn)在L上)

if(該端點(diǎn)是S的較大端點(diǎn))

count++;

end

else if(S與L相交)

count++;

end

end

end

if(count%2==0)

P不在cell內(nèi);

else

P位于cell內(nèi);

end

由此可得到起始點(diǎn)與cell之間的位置關(guān)系,如果位于cell內(nèi),則將機(jī)器人直接移動(dòng)到TP,如果位于cell外,那么交點(diǎn)坐標(biāo)(Xb,Yb)可以表示為:

(8)

(9)

其中(x1,y1),(x2,y2)為第一條線段的端點(diǎn)坐標(biāo),(x3,y3),(x4,y4)為第二條線段的端點(diǎn)坐標(biāo).

將機(jī)器人移動(dòng)到得到的交點(diǎn)坐標(biāo)(Xb,Yb)上.

3.3 Sambot方向的控制

在自組裝的過(guò)程中,角度控制也是關(guān)鍵問(wèn)題,它一直是研究的熱門話題.例如,當(dāng)目標(biāo)配置已知時(shí),van den Berg 等人于2008年提出了實(shí)時(shí)多主體導(dǎo)航角度控制的“互惠速度障礙”的概念.Yu和Lavalle在2012年、Turpin等在2013和2012年提出了置換不變路徑規(guī)劃算法來(lái)控制每個(gè)機(jī)器人的方向.上述算法不適用于此,因?yàn)镾ambots的導(dǎo)航過(guò)程在不同的階段有不同的管理機(jī)制.在自組裝過(guò)程中,每個(gè)Sambot的運(yùn)動(dòng)都是自發(fā)的,在到達(dá)目標(biāo)位置之前的這個(gè)階段,Sambot采用了基于行為的控制方法,即控制器由一系列行為組成,每個(gè)行為用于實(shí)現(xiàn)特定的功能.每一種行為都包括一系列的運(yùn)動(dòng)方案,包括(a)避免碰撞,(b)自轉(zhuǎn),(c)前進(jìn)/后退直線運(yùn)動(dòng)和(d)前進(jìn)/后退弧運(yùn)動(dòng).當(dāng)Sambot到達(dá)?？繀^(qū)時(shí),僅僅通過(guò)自主移動(dòng)的行為控制方法來(lái)同時(shí)滿足線性和角位移約束是非常困難的.因此,我們采用基于動(dòng)力學(xué)的兩步路徑規(guī)劃算法來(lái)實(shí)現(xiàn)每個(gè)Sambot的定向控制.根據(jù)該算法,對(duì)接區(qū)域的導(dǎo)航過(guò)程分為兩個(gè)步驟:首先滿足角位移約束,然后滿足線性位移條件.這樣就減輕了約束條件,有效地降低了控制難度.

3.4 Sambots自組裝路徑規(guī)劃控制的假設(shè)

對(duì)于自組裝環(huán)境,目前的工作我們只考慮2D平面的情況,以下采取5種假設(shè).

1)開(kāi)始時(shí),Sambots在2D矩形區(qū)域內(nèi)具有近似均勻的分布.

2)Sambots能夠確定他們的位置和方向.

3)Sambots有足夠的力量完成他們的動(dòng)作,通信,對(duì)接和對(duì)接后的整體運(yùn)動(dòng).

4)Sambots完全啟動(dòng),受非完整約束.

5)忽略運(yùn)動(dòng)中的碰撞和避障問(wèn)題.

根據(jù)上述假設(shè),群體中的代理機(jī)器人不僅知道所有機(jī)器人的狀態(tài),而且知道全局最終的期望狀態(tài).這指向一個(gè)集中式算法,而不是分布式算法.這里采用集中式算法是為了保證自組裝的實(shí)現(xiàn).

3.5 VBIT目標(biāo)配置模型

通過(guò)自組裝,多個(gè)Sambots可以形成具有多種配置的機(jī)器人聚集體.在這里,我們只考慮二維空間中Sambots的自組裝問(wèn)題.VBIT算法采用的模型包括了CVT算法建立在一個(gè)平面上的三種典型配置,包括直線,十字和H形.除這些開(kāi)鏈模型外,還有閉鏈形式的環(huán)型配置.

圖5展示了由9個(gè)Sambot組成的直線型目標(biāo)配置,圖6展示了由11個(gè)機(jī)器人組成的H型目標(biāo)配置.其中×表示DP,為TP,實(shí)線邊框表示形成的目標(biāo)配置形狀,圓圈表示機(jī)器人當(dāng)前位置.值得注意的是,對(duì)于任何的目標(biāo)配置,只需要考慮目標(biāo)配置的點(diǎn)坐標(biāo)即可.同理,可以增加機(jī)器人的數(shù)量來(lái)達(dá)到相同的效果,與CVT算法所采用的矩陣壓縮再拼接的方法相比,CVT算法不僅存在死鎖情況,而且每次壓縮之前要通過(guò)一定的比例關(guān)系求出對(duì)應(yīng)目標(biāo)配置的邊框坐標(biāo)位置,對(duì)于稍微復(fù)雜的cross型以及H型配置要事先為每個(gè)矩形分配所包含的機(jī)器人個(gè)數(shù),過(guò)程繁復(fù)且效率不高,得到的機(jī)器人路徑有過(guò)多的冗余,后期的迭代會(huì)較為遲緩,在時(shí)間上的表現(xiàn)也有所瑕疵.VBIT算法為主動(dòng)性的路徑規(guī)劃方案,且每個(gè)機(jī)器人都有自己對(duì)應(yīng)的目標(biāo)點(diǎn),因此對(duì)比CVT算法,無(wú)論是在消耗時(shí)間還是在機(jī)器人運(yùn)動(dòng)路徑長(zhǎng)度上,VBIT算法都有明顯的優(yōu)勢(shì).從圖5-圖6中可以發(fā)現(xiàn),VBIT為每個(gè)機(jī)器人規(guī)劃的路徑均為直線,最大程度上減少了無(wú)謂的路徑損耗,每一個(gè)機(jī)器人在自己的cell內(nèi)向目標(biāo)點(diǎn)的運(yùn)動(dòng),都是最大程度上接近目標(biāo)點(diǎn)的,所以迭代次數(shù)會(huì)大幅減少.文獻(xiàn)[6]中提到的三個(gè)問(wèn)題:如何有效地減少死鎖的可能性,如何準(zhǔn)確判斷死鎖狀態(tài)以及如何及時(shí)對(duì)死鎖進(jìn)行判斷.這三個(gè)問(wèn)題集中在死鎖上,死鎖發(fā)生的原因?yàn)闄C(jī)器人的運(yùn)動(dòng)由壓縮可活動(dòng)區(qū)域來(lái)實(shí)現(xiàn),機(jī)器人的運(yùn)動(dòng)沒(méi)有主動(dòng)性,造成如圖4最右端所展現(xiàn)的死鎖情況(兩個(gè)機(jī)器人上下重疊,沒(méi)有達(dá)到我們預(yù)期的一字排開(kāi)的要求),這些問(wèn)題在VBIT算法下都能得到有效地解決,并且隨著粒子的增加,VBIT算法在時(shí)間以及路徑上都表現(xiàn)得一樣優(yōu)秀、成功地尋找到了最優(yōu)的全局規(guī)劃方案,在本文的第四章會(huì)對(duì)上述說(shuō)明給出證明.

圖4 CVT算法的死鎖現(xiàn)象圖5 VBIT算法實(shí)現(xiàn)的line型目標(biāo)配置圖6 VBIT算法實(shí)現(xiàn)的H型目標(biāo)配置Fig.4 DeadlockofCVTalgorithmFig.5 VBITalgorithm'sline-typetargetFig.6 VBITalgorithm'sH-typetargetconfigurationconfiguration

最后,需要提一下的是,由于每次的迭代過(guò)程中,機(jī)器人始終是運(yùn)動(dòng)到cell的邊界上的,所以為了避免機(jī)器人之間的碰撞,可以按照機(jī)器人當(dāng)前的運(yùn)動(dòng)軌跡作一定的回溯操作,使機(jī)器人退回到自己所在的cell內(nèi).

4 仿真結(jié)果與對(duì)比分析

4.1 仿真結(jié)果

通過(guò)Matlab仿真和實(shí)驗(yàn)對(duì)比驗(yàn)證了新算法的有效性.直線型、十字型、H型在Sambot的工程上都有廣泛的應(yīng)用,線型的可以用來(lái)模仿蛇等無(wú)足動(dòng)物,十字型和H型的則可以組合搭配模仿生成多足類爬行動(dòng)物等.下面對(duì)這三種典型的配置模型進(jìn)行對(duì)比試驗(yàn),由于CVT算法中并未涉及到環(huán)型配置,則僅展示環(huán)型目標(biāo)配置形成的過(guò)程和時(shí)間消耗.傳統(tǒng)CVT算法無(wú)法給出具體的目標(biāo)配置點(diǎn)坐標(biāo),遂按照一定的比例來(lái)為CVT構(gòu)造出一個(gè)目標(biāo)配置與VBIT算法相同的目標(biāo)配置.由于CVT算法在H型目標(biāo)配置、高維情況下有頻繁的死鎖情況發(fā)生,導(dǎo)致CVT算法無(wú)法得到目標(biāo)配置,本文僅對(duì)較為復(fù)雜的H型進(jìn)行高維實(shí)驗(yàn),其它目標(biāo)配置的高維情況本文不展開(kāi)描述.

表2以9機(jī)器人line型、9機(jī)器人十字型、11機(jī)器人H型、12機(jī)器人circle型為例說(shuō)明,其中Crs表示圍成目標(biāo)配置的點(diǎn)坐標(biāo),Point表示與之對(duì)應(yīng)的目標(biāo)點(diǎn).

實(shí)驗(yàn)參數(shù)如表2所示.

相應(yīng)地增加機(jī)器人數(shù)量則按照一定的比例分別為CVT以及VBIT改變Crs坐標(biāo)以及Point坐標(biāo).由于傳統(tǒng)CVT算法會(huì)產(chǎn)生一定的誤差,為了后續(xù)的對(duì)比試驗(yàn)描述,在此先做以下定義:已知Sambot的規(guī)格為80mm×102mm,為了在坐標(biāo)系中轉(zhuǎn)化更加方便,將規(guī)格近似成為100mm×100mm.本文設(shè)定允許的誤差容限分別為1mm,5mm,10mm.100mm在本實(shí)驗(yàn)中對(duì)應(yīng)的大小為1,轉(zhuǎn)換后的誤差容限對(duì)應(yīng)在方陣中的大小為0.01、0.05、0.1.這一誤差容限的意義為所有的機(jī)器人與對(duì)應(yīng)目標(biāo)點(diǎn)的距離都應(yīng)小于這一數(shù)值,記為ε>max(Z)(Z為前文所提及的成本矩陣).

表2 目標(biāo)配置對(duì)照表

Table 2 Target configuration comparison table

CVTVBITLINE_TYPECrs=[0.5,4.5;0.5,5.5;9.5,5.5;9.5,4.5]Point=[1,5;2,5;3,5;4,5;5,5;6,5;7,5;8,5;9,5]CROSS_TYPECrs=[2.5,4.5;2.5,5.5;4.5,5.5;4.5,7.5;5.5,7.5;5.5,5.5;7.5,5.5;7.5,4.5;5.5,4.5;5.5,24.5,2.5;4.5,4.5]Point=[3,5;4,5;5,5;6,5;7,5;5,7;5,6;5,4;5,3]

本次對(duì)比實(shí)驗(yàn)是在同一臺(tái)電腦上進(jìn)行的,為了保證實(shí)驗(yàn)的公平性,對(duì)比試驗(yàn)中所有的參數(shù)都相同,包括機(jī)器人初始位置、地圖大小、目標(biāo)配置位置等,比較不同數(shù)量機(jī)器人下的時(shí)間損耗和路徑長(zhǎng)度,對(duì)比試驗(yàn)中將VBIT算法與CVT算法在三個(gè)誤差容限ε=(0.01,0.05,0.1)內(nèi)的表現(xiàn)進(jìn)行對(duì)比.在line型目標(biāo)配置組下,隨著粒子的增加,僅在x軸上對(duì)可移動(dòng)范圍做延伸.Cross以及H型配置下,可活動(dòng)區(qū)域按比例擴(kuò)大.圖7-圖10是時(shí)間以及路徑長(zhǎng)度對(duì)比圖.

圖7 LINE型時(shí)間消耗圖8 LINE型平均路徑長(zhǎng)度圖9 H型時(shí)間消耗圖10 H型平均路徑長(zhǎng)度對(duì)比圖對(duì)比圖對(duì)比圖對(duì)比圖Fig.7 LINE-type'stimeFig.8 LINE-type'saveragepathFig.9 H-type'stimeFig.10 H-type'saveragepathconsumptioncomparisonchartlengthcomparisonchartconsumptioncomparisonchartlengthcomparisonchart

從三組對(duì)比試驗(yàn)中可以看出,時(shí)間消耗方面:在LINE型以及CROSS型下,CVT在不同誤差容限中的時(shí)間消耗均顯示出近似指數(shù)增長(zhǎng)的趨勢(shì),而VBIT算法的時(shí)間消耗的增長(zhǎng)幅度很小,始終保持在一個(gè)較低的水平.在H型目標(biāo)配置下,CVT在不同誤差容限下呈現(xiàn)出相較于LINE與CROSS型幅度更大的增長(zhǎng)趨勢(shì),是因?yàn)镠型目標(biāo)配置相對(duì)更復(fù)雜,更容易陷入死鎖.VBIT算法則保持在一個(gè)較低的水平,且增幅很小.路徑長(zhǎng)度方面,VBIT的平均路徑長(zhǎng)度在絕大多數(shù)情況下都要小于CVT所規(guī)劃出的路徑長(zhǎng)度,由于機(jī)器人初始位置是隨機(jī)的,所以路徑長(zhǎng)度并沒(méi)有一個(gè)比較清晰的規(guī)律.從每個(gè)算法自身來(lái)看,在三種目標(biāo)配置下,CVT算法在機(jī)器人數(shù)量增加后,所消耗的時(shí)間隨著誤差容限的增加而減少,其中不同誤差容限內(nèi),H型的差距最為明顯,CROSS型次之,LINE型最不明顯,這也是由于目標(biāo)配置復(fù)雜度造成的.CVT算法在不同誤差容限下的路徑長(zhǎng)度也基本隨著誤差容限的增加而減少.而VBIT算法無(wú)論是在什么樣的目標(biāo)配置下,其時(shí)間消耗始終保持在一個(gè)較低的水平,與CVT算法拉開(kāi)了比較大的差距.在路徑長(zhǎng)度方面,VBIT算法在三種目標(biāo)配置下也基本保持著增長(zhǎng)的趨勢(shì),但增長(zhǎng)幅度較小,整體基本小于CVT算法.

4.2 結(jié)果分析

通過(guò)VBIT與CVT不同誤差容限的對(duì)比情況來(lái)看,無(wú)論是在時(shí)間損耗還是路徑長(zhǎng)度上,VBIT算法的耗時(shí)更短、平均路徑更短,并實(shí)現(xiàn)了CVT算法所不能實(shí)現(xiàn)的更為復(fù)雜的目標(biāo)配置,VBIT算法在高維情況下的表現(xiàn)同樣優(yōu)秀,時(shí)間和路徑長(zhǎng)度上并沒(méi)有因?yàn)闄C(jī)器人數(shù)目的增加而出現(xiàn)大幅度的增長(zhǎng).總體而言,VBIT算法達(dá)到了群組機(jī)器人路徑規(guī)劃的要求,并與CVT算法相比體現(xiàn)出了其優(yōu)越性,實(shí)現(xiàn)了對(duì)群組機(jī)器人自組裝過(guò)程所消耗的時(shí)間縮減和路徑縮短(能量消耗).VBIT算法在高維情況下所表現(xiàn)出來(lái)的自組裝能力達(dá)到預(yù)期要求,解決了CVT算法在高維求解能力上的不足.

5 結(jié) 論

本文提出的基于voronoi圖劃分的VBIT算法,并將其應(yīng)用于群組機(jī)器人的自組裝路徑規(guī)劃方面,通過(guò)matlab仿真實(shí)現(xiàn)了4種典型的目標(biāo)裝配,并與傳統(tǒng)CVT算法在耗時(shí)以及路徑長(zhǎng)度上,分別在不同的機(jī)器人個(gè)數(shù)下進(jìn)行了對(duì)比試驗(yàn),VBIT算法是具有主動(dòng)性、全局性、通用性等特點(diǎn)的改進(jìn)算法,在自組裝的過(guò)程中,各個(gè)機(jī)器人沒(méi)有優(yōu)先級(jí)關(guān)系,VBIT算法將為它們統(tǒng)一規(guī)劃路徑,由于采用了邊界點(diǎn)作為機(jī)器人下一步的運(yùn)動(dòng)位置,在保證了不碰撞的前提下,每個(gè)機(jī)器人在自己的cell內(nèi)做最大程度的有目的性移動(dòng).經(jīng)過(guò)VBIT規(guī)劃后的路徑均為直線,且一一分配了機(jī)器人與起始點(diǎn)之間的對(duì)應(yīng)關(guān)系,因此每個(gè)機(jī)器人從初始位置到起始點(diǎn)的距離都是較小的.由于做了最大程度上的移動(dòng),也減少了算法的迭代次數(shù),實(shí)現(xiàn)了時(shí)間以及路徑長(zhǎng)度上的雙贏.

相比于傳統(tǒng)CVT算法,VBIT算法不存在死鎖情況,本文中僅給出了典型的4種目標(biāo)配置,實(shí)際中VBIT算法 可以實(shí)現(xiàn)更多2D空間內(nèi)的任意形狀,今后工作在此算法基礎(chǔ)上進(jìn)行3D方面以及避障方面的拓展研究.