面向群組機(jī)器人路徑規(guī)劃的Voronoi-APF算法研究

蔡鑫偉，侯向輝，莫清宇，張美玉，簡(jiǎn)琤峰

(浙江工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院 數(shù)字媒體技術(shù)研究所，杭州 310023) E-mail：hxh@zjut.edu.cn

1 引 言

群組機(jī)器人是受啟發(fā)于群居動(dòng)物的多機(jī)器人系統(tǒng)，該機(jī)器人群體由大量能力有限的機(jī)器人組成.相對(duì)于單機(jī)器人，其在成本、靈活性、穩(wěn)定性上具有巨大優(yōu)勢(shì)，并具有聚集、空間覆蓋、編隊(duì)移動(dòng)、自組裝等單機(jī)器人所不具備的群體工作能力.在相關(guān)的論文中，群組機(jī)器人已被運(yùn)用到移民保護(hù)[1]、火災(zāi)救援[2,3]、水下工作[4]，除此以外，群組機(jī)器人在其他復(fù)雜環(huán)境下也正發(fā)揮著其獨(dú)特作用.

自組裝作為群組機(jī)器人的重要應(yīng)用方向，有著重要的研究意義.為了達(dá)成目標(biāo)配置，路徑規(guī)劃尤為關(guān)鍵.而在復(fù)雜的實(shí)際應(yīng)用環(huán)境中，保證機(jī)器人之間的碰撞避免和躲避地圖障礙物問(wèn)題則越來(lái)越受重視.近幾年，越來(lái)越多的研究工作將人工勢(shì)場(chǎng)[5]，粒子群優(yōu)化算法[6]，蟻群算法[7]，遺傳算法[8]等算法優(yōu)化、結(jié)合并運(yùn)用到該領(lǐng)域中，取得了一定成果.Wang W等人利用線性遞減慣性權(quán)重粒子群算法進(jìn)行路徑規(guī)劃，同時(shí)使用刪除冗余結(jié)點(diǎn)方法和混沌理論進(jìn)行優(yōu)化，使得算法在復(fù)雜環(huán)境下依舊能有優(yōu)秀的路徑規(guī)劃表現(xiàn)[9]；Yang J等人提出基于約束粒子群優(yōu)化的協(xié)同搜索算法以應(yīng)對(duì)多機(jī)器人在受限環(huán)境下的協(xié)同搜索任務(wù)[10]；Hu L等人將蟻群算法的評(píng)價(jià)函數(shù)引入到D*算法中，并改進(jìn)了D*算法中的子節(jié)點(diǎn)擴(kuò)展方式和啟發(fā)函數(shù)，提出了一種高效率、高適應(yīng)性的融合算法[11]；Nazarahari M等人提出以創(chuàng)新人工勢(shì)場(chǎng)搜索所有可行路徑，然后使用增強(qiáng)遺傳算法找到最優(yōu)路徑，在多機(jī)器人在連續(xù)環(huán)境中的應(yīng)用取得顯著效果[12]；Pan Z等人提出了一種基于改進(jìn)人工勢(shì)場(chǎng)和PID自適應(yīng)跟蹤控制算法的避障方法，該算法利用旋轉(zhuǎn)勢(shì)場(chǎng)來(lái)解決局部極小值和振蕩，并且建立了機(jī)器人之間的排斥勢(shì)函數(shù)和優(yōu)先級(jí)模型，成功地解決了避障和防撞問(wèn)題[13]；Matoui F等人采用了人工勢(shì)場(chǎng)、鄰里系統(tǒng)、機(jī)器人之間的優(yōu)先級(jí)概念3種技術(shù)的混合方法，使得分布式體系中的機(jī)器人能有效地躲避靜態(tài)和動(dòng)態(tài)的障礙物[14].

本文提出的基于Voronoi約束[15]的人工勢(shì)場(chǎng)算法(VAPF)，首先使用匈牙利算法[16,17]和替換策略為各機(jī)器人指定目標(biāo)點(diǎn)，然后通過(guò)群組機(jī)器人的實(shí)時(shí)位置構(gòu)建Voronoi圖，各機(jī)器人各自使用人工勢(shì)場(chǎng)算法進(jìn)行路徑規(guī)劃，限制其路徑在構(gòu)建的Voronoi圖的對(duì)應(yīng)分割空間中，即機(jī)器人單次運(yùn)動(dòng)到終點(diǎn)或分隔空間的邊界便停止.重復(fù)以上步驟，直到所有機(jī)器人到達(dá)指定終點(diǎn).VAPF算法既保留人工勢(shì)場(chǎng)算法的優(yōu)勢(shì)，又實(shí)現(xiàn)了機(jī)器人間的碰撞避免，通過(guò)matlab仿真對(duì)比實(shí)驗(yàn)證明了其在時(shí)間消耗和路徑長(zhǎng)度上的改進(jìn)效果.

2 相關(guān)工作

2017年，Sun J等人提出了APF的改進(jìn)算法(為方便表述，將其稱之為OAPF)，該算法在人工勢(shì)場(chǎng)算法中引入了距離因子，并將自身以外的個(gè)體視作障礙物，既解決了人工勢(shì)場(chǎng)算法容易陷入局部極小值、無(wú)法達(dá)到終點(diǎn)的問(wèn)題，又解決了人工勢(shì)場(chǎng)無(wú)法實(shí)現(xiàn)碰撞避免的問(wèn)題[18].

人工勢(shì)場(chǎng)算法在二維空間下的算法模型如式(1)-式(3)所示:

(1)

(2)

(3)

OAPF算法改進(jìn)了其中的斥力勢(shì)公式，如式(4)所示:

(4)

其中，(X-Xtarg)n=|(x-xtarg)n|+|(y-ytarg)n|表示距離因子，保證了斥力勢(shì)的引入不影響機(jī)器人到達(dá)終點(diǎn).

考慮到機(jī)器人在單次迭代中相對(duì)靜止，且安全距離通常大于機(jī)器人的體積，所以O(shè)APF算法將其他機(jī)器人當(dāng)作障礙物的假設(shè)是可行的.因?yàn)闄C(jī)器人間斥力同樣存在局部最小問(wèn)題，所以也引入距離因子，如式(5)所示:

(5)

其中，θ為機(jī)器人之間的斥力增益，ρ(ij)表示機(jī)器人i,j之間的最小距離.

最終，機(jī)器人在3個(gè)疊加勢(shì)力場(chǎng)的影響下運(yùn)動(dòng).

在OAPF算法中，距離因子即指在原人工勢(shì)場(chǎng)算法的斥力計(jì)算公式中添加距離要素，該方法的引入導(dǎo)致機(jī)器人路徑規(guī)劃與機(jī)器人運(yùn)動(dòng)終點(diǎn)高度緊密聯(lián)系.而在復(fù)雜地圖中單純考慮距離要素并不一定達(dá)成最優(yōu)規(guī)劃.例如外圍的機(jī)器人優(yōu)先到達(dá)終點(diǎn)將導(dǎo)致內(nèi)圍機(jī)器人無(wú)法進(jìn)入.當(dāng)機(jī)器人在越過(guò)復(fù)雜地形后需要交換目標(biāo)點(diǎn)時(shí)，若不考慮動(dòng)態(tài)指派策略，勢(shì)必會(huì)影響算法的魯棒性和收斂性.

在碰撞避免問(wèn)題上，雖然OAPF算法將機(jī)器人自身以外的個(gè)體視作障礙物，很好地解決了碰撞問(wèn)題.但是，這意味著在每一次迭代過(guò)程中，每個(gè)機(jī)器人都需要知道其他所有機(jī)器人當(dāng)前位置以構(gòu)建斥力場(chǎng)，考慮實(shí)際情況下的機(jī)器人通訊問(wèn)題，這個(gè)問(wèn)題極大程度地限制了模型的效率與實(shí)際應(yīng)用.

在OAPF算法中，通過(guò)限制機(jī)器人單次迭代中運(yùn)動(dòng)的步長(zhǎng)來(lái)避免機(jī)器人同時(shí)運(yùn)動(dòng)時(shí)發(fā)生碰撞，大大增加算法復(fù)雜度，所以導(dǎo)致完成目標(biāo)配置的時(shí)間開(kāi)銷提升同時(shí)群組機(jī)器人逐漸聚集導(dǎo)致機(jī)器人之間的斥力勢(shì)增大，機(jī)器人則越不容易接近目標(biāo)點(diǎn)，路程方面的開(kāi)銷勢(shì)必增加.

3 VAPF算法

通過(guò)以上分析可知，人工勢(shì)場(chǎng)改進(jìn)算法OAPF不適應(yīng)動(dòng)態(tài)的目標(biāo)指派策略，在該方面有較大的改進(jìn)空間，其次，機(jī)器人之間的斥力勢(shì)，雖然解決了機(jī)器人間的碰撞問(wèn)題，但大大降低了算法的性能和實(shí)際應(yīng)用的可行性.針對(duì)以上缺陷，本文提出的VAPF算法通過(guò)以下方法進(jìn)行改進(jìn)優(yōu)化：

1)引入了動(dòng)態(tài)的目標(biāo)指派策略.

通過(guò)群組機(jī)器人實(shí)時(shí)位置和目標(biāo)之間的對(duì)角距離構(gòu)建成本矩陣，使用匈牙利算法進(jìn)行最優(yōu)指派，針對(duì)多最優(yōu)解的情況，使用替換策略優(yōu)化目標(biāo)指派.

2)引入了Voronoi 約束保證機(jī)器人間的碰撞避免.

通過(guò)群組機(jī)器人實(shí)時(shí)位置構(gòu)建Voronoi圖，限制單機(jī)器人的單次迭代運(yùn)動(dòng)范圍在Voronoi圖對(duì)應(yīng)的cell中.該方法既保證了機(jī)器人之間的避免，又極大程度提升了機(jī)器人的單次迭代運(yùn)動(dòng)范圍.

3)引入了運(yùn)動(dòng)控制方法解決機(jī)器人抖動(dòng)問(wèn)題.

通過(guò)機(jī)器人改變運(yùn)動(dòng)角度的大小劃分運(yùn)動(dòng)策略，當(dāng)角度過(guò)大發(fā)生抖動(dòng)現(xiàn)象時(shí)，限制運(yùn)動(dòng)角度，并縮小運(yùn)動(dòng)步長(zhǎng).

VAPF算法流程如下：

1.導(dǎo)入地圖.

2.獲得目標(biāo)配置.

3.設(shè)置初始參數(shù).

4.匈牙利算法為機(jī)器人指派目標(biāo)點(diǎn).

5.替換策略優(yōu)化目標(biāo)指派.

6.根據(jù)機(jī)器人位置，構(gòu)建Voronoi圖.

7.機(jī)器人在分配活動(dòng)范圍內(nèi)使用人工勢(shì)場(chǎng)算法進(jìn)行路徑規(guī)劃.

8.當(dāng)所有機(jī)器人到達(dá)終點(diǎn)，算法結(jié)束.若存在機(jī)器人未到達(dá)終點(diǎn)，當(dāng)時(shí)間大于設(shè)定閾值，轉(zhuǎn)4，否則，轉(zhuǎn)6.

在上述過(guò)程中匈牙利算法指派目標(biāo)點(diǎn)、替換策略、限定活動(dòng)范圍內(nèi)的路徑規(guī)劃等算法細(xì)節(jié)將在后續(xù)詳細(xì)描述.

3.1 環(huán)境建模和障礙物預(yù)處理

機(jī)器人在2D空間運(yùn)動(dòng)，已知：①所有機(jī)器人起點(diǎn)；②目標(biāo)配置要求；③障礙物信息.則機(jī)器人自組裝環(huán)境可以用有限空間存儲(chǔ)以及表達(dá)，本文采用柵格法進(jìn)行環(huán)境建模.

選取適當(dāng)?shù)木匦慰臻g，滿足空間包含上述①②位置，再將環(huán)境劃分成u×v個(gè)柵格.最后采用直角坐標(biāo)法表示柵格位置，則任意柵格均可用數(shù)據(jù)對(duì){x,y}表示坐標(biāo).

為了簡(jiǎn)化問(wèn)題，本文將機(jī)器人視作質(zhì)點(diǎn)，那么為了保證機(jī)器人和障礙之間的碰撞避免，需要對(duì)障礙物進(jìn)行膨脹化處理，即保持障礙物形狀不變，障礙物外圍輪廓向外偏移一定距離.考慮到障礙物的不可預(yù)估性，膨脹化處理有助于機(jī)器人與障礙物保持安全距離，能及時(shí)規(guī)避風(fēng)險(xiǎn).

其次，障礙物無(wú)法跨越，且機(jī)器人初始位置不在障礙物中，那么障礙物只有外圍輪廓信息是機(jī)器人路徑規(guī)劃的必要信息.所以本文對(duì)障礙物進(jìn)行了上述的膨脹化處理后，只保留膨脹后增加部分的障礙物信息，舍棄原障礙物信息.大大減少了環(huán)境信息的數(shù)據(jù)量，有利于機(jī)器人進(jìn)行更高效的路徑規(guī)劃.對(duì)障礙物處理示例如圖1所示.

圖1 障礙物預(yù)處理Fig.1 Obstacle pretreatment

基于上述環(huán)境建模和障礙物處理，后續(xù)工作將基于如下4種假設(shè)展開(kāi)：2D平面除障礙物外均勻光滑；機(jī)器人可確定自身坐標(biāo)與運(yùn)動(dòng)方向；機(jī)器人有足夠能力完成任務(wù)；自組裝任務(wù)可完成.

3.2 目標(biāo)指派

假設(shè)群組機(jī)器人中有N個(gè)機(jī)器人，其位置集合為S={S1,S2,…,SN}，假設(shè)目標(biāo)配置集合為T={T1,T2,…,TN}，為了獲得最小代價(jià)完成一一對(duì)應(yīng)的目標(biāo)配置，則問(wèn)題轉(zhuǎn)化為指派問(wèn)題.

(6)

(7)

根據(jù)康尼格定理：系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最小直線數(shù)，本文采用匈牙利算法計(jì)算指派矩陣流程如下：

步驟1.成本矩陣C各行所有元素減去該行最小值，各列所有元素減去該列最小值.

步驟2.若能找到N個(gè)獨(dú)立的0元素，則可以進(jìn)行指派，0元素對(duì)應(yīng)位置的Xi,j=1，其他位置Xi,j=0.指派結(jié)束.

步驟3.對(duì)于K(K

考慮到代價(jià)矩陣無(wú)法在復(fù)雜環(huán)境下精準(zhǔn)得出，本文算法設(shè)定了更新目標(biāo)指派的時(shí)間閾值Δt，若當(dāng)前時(shí)間距離上次目標(biāo)指派時(shí)間超過(guò)閾值Δt，則重新進(jìn)行目標(biāo)指派.其次，傳統(tǒng)的代價(jià)矩陣一般采用歐式距離或曼哈頓距離，如式(8)、式(9)所示：

(8)

hm=dx+dy

(9)

其中，ho代表歐式距離，hm代表曼哈頓距離，dx,dy分別代表起點(diǎn)與終點(diǎn)的橫坐標(biāo)、縱坐標(biāo)之差.歐式距離表示兩點(diǎn)之間的直線距離，未考慮障礙物的影響，且平方根運(yùn)算增大了計(jì)算量.曼哈頓距離則只考慮了4個(gè)方向的運(yùn)動(dòng)，未考慮對(duì)角運(yùn)動(dòng)，脫離實(shí)際，不利于目標(biāo)指派.為了更為貼近實(shí)際情況，同時(shí)保證運(yùn)算的簡(jiǎn)單高效，本文采用對(duì)角距離，如式(10)所示：

hd=D(dx+dy)+(D2-2×D)×min(dx,dy)

(10)

其中，D表示機(jī)器人進(jìn)行平行移動(dòng)的移動(dòng)代價(jià)，D2表示機(jī)器人進(jìn)行對(duì)角移動(dòng)的移動(dòng)代價(jià).

圖2 目標(biāo)指派的特殊情況Fig.2 Special case of target assignment

若選擇指派矩陣X2，機(jī)器人S2將會(huì)阻擋機(jī)器人S1.考慮自組裝的實(shí)際需求，應(yīng)當(dāng)選擇指派矩陣X1，即S1→T1，S2→T2.類似情況下，匈牙利算法生成結(jié)果可能有多個(gè)相同最優(yōu)解結(jié)果，所以本文提出了替換策略.

當(dāng)匈牙利算法運(yùn)行結(jié)束后，若存在兩對(duì)目標(biāo)指派Sα→Ty,Sb→T2，同時(shí)滿足式(11)、式(12)，則交換兩機(jī)器人的目標(biāo)點(diǎn)，即修改指派矩陣.

Ca,y+Cb,z=Ca,z+Cy,b

(11)

abs(Ca,z-Cy,b)

(12)

通過(guò)以上策略，可以有效地均衡各機(jī)器人的運(yùn)行距離，并解決上述特殊情況產(chǎn)生的問(wèn)題.

3.3 運(yùn)動(dòng)空間劃分與路徑規(guī)劃

通過(guò)機(jī)器人當(dāng)前位置集合S，使用Delaunay三角剖分法構(gòu)建Voronoi圖，將全空間U劃分為N個(gè)單元V={V1,V2,…，Vn}，其與集合S元素一一對(duì)應(yīng)，滿足式(13)：

Vi={p∈U|d(p,Xi)≤d(p,Xj)for allj≠i}

(13)

對(duì)于每個(gè)單元Vi，其均為凸多邊形.因?yàn)閱卧猇i為凸多邊形，所以可以用一組離散結(jié)點(diǎn)p={p1，p2，…，pk}表示.假設(shè)該離散點(diǎn)集合按順時(shí)針排序，對(duì)于單元內(nèi)的任意一點(diǎn)Q，恒滿足式(14)，則該點(diǎn)位于Vi中.

(14)

將群組中單個(gè)機(jī)器人看作節(jié)點(diǎn)，那基于機(jī)器人節(jié)點(diǎn)位置構(gòu)建Voronoi圖具有以下性質(zhì)：Voronoi單元中任意一點(diǎn)到該單元機(jī)器人節(jié)點(diǎn)的距離均小于或等于該點(diǎn)到相鄰單元機(jī)器人節(jié)點(diǎn)的距離，同時(shí)基于單個(gè)機(jī)器人節(jié)點(diǎn)的位置對(duì)空間平面進(jìn)行剖分，所以生成Voronoi單元中有且僅有一個(gè)機(jī)器人節(jié)點(diǎn).因此可以利用Voronoi圖中各個(gè)節(jié)點(diǎn)關(guān)系或者單元之間的幾何特征來(lái)約束群組機(jī)器人路徑規(guī)劃中碰撞避免.

每個(gè)機(jī)器人在對(duì)應(yīng)單元中，使用人工勢(shì)場(chǎng)算法進(jìn)行路徑規(guī)劃，當(dāng)機(jī)器人到達(dá)對(duì)應(yīng)的終點(diǎn)或超出運(yùn)動(dòng)范圍時(shí)，則機(jī)器人單次迭代運(yùn)動(dòng)結(jié)束.人工勢(shì)場(chǎng)算法通過(guò)式(1)-式(3)計(jì)算可得,算法如下所示：

算法:機(jī)器人Xi單次迭代運(yùn)動(dòng)偽代碼if(已經(jīng)到達(dá)指派目標(biāo)) returnendif通過(guò)人工勢(shì)場(chǎng)算法計(jì)算下一個(gè)運(yùn)動(dòng)點(diǎn)Xnextwhile(XnextinVi)do 把Xnext加入路徑 更新當(dāng)前位置 if(到達(dá)指派目標(biāo)) break endif 通過(guò)人工勢(shì)場(chǎng)算法計(jì)算下一個(gè)運(yùn)動(dòng)點(diǎn)Xnextendwhile

需要注意的是，機(jī)器人同時(shí)向Voronoi圖中的邊界運(yùn)動(dòng)時(shí)，有極小概率在邊界上發(fā)生碰撞，此時(shí)機(jī)器人可采取少量回退操作，避免碰撞發(fā)生.

3.4 群組機(jī)器人的運(yùn)動(dòng)控制

在完成碰撞避免和障礙躲避后，本文對(duì)群組機(jī)器人的運(yùn)動(dòng)控制進(jìn)行了研究.人工勢(shì)場(chǎng)算法中，當(dāng)機(jī)器人受到力的方向和運(yùn)動(dòng)方向一直成鈍角時(shí)，會(huì)發(fā)生抖動(dòng)現(xiàn)象，尤其是在機(jī)器人與目標(biāo)點(diǎn)之間存在障礙物的情況下.在實(shí)際應(yīng)用中，機(jī)器人期望有一條相對(duì)平滑的路徑，抖動(dòng)現(xiàn)象并不利于機(jī)器人運(yùn)動(dòng).本文提出如式(15)、式(16)所示運(yùn)動(dòng)控制方法以解決抖動(dòng)問(wèn)題.

(15)

(16)

其中，x(t),y(t)表示機(jī)器人現(xiàn)在所在位置，x(t+1),y(t+1)表示機(jī)器人所要到達(dá)的位置；θ(t)表示機(jī)器人當(dāng)前的運(yùn)動(dòng)方向，Δθ表示機(jī)器人到達(dá)下一步位置所要改變多少運(yùn)動(dòng)方向，l表示機(jī)器人的運(yùn)動(dòng)距離；當(dāng)機(jī)器人改變運(yùn)動(dòng)方向?yàn)殇J角時(shí)，不改變運(yùn)動(dòng)規(guī)則，當(dāng)機(jī)器人改變運(yùn)動(dòng)方向?yàn)殁g角時(shí)，限制改變方向至多為直角；τ表示調(diào)整參數(shù)，當(dāng)機(jī)器人可能發(fā)生抖動(dòng)時(shí)，限制機(jī)器人運(yùn)動(dòng)步長(zhǎng)，可以有效地緩解抖動(dòng)現(xiàn)象.

基于上述運(yùn)動(dòng)規(guī)則，機(jī)器人采用兩步法進(jìn)行運(yùn)動(dòng)：先通過(guò)旋轉(zhuǎn)滿足方向要求，再通過(guò)直線運(yùn)動(dòng)滿足位移要求.采用此方法進(jìn)行控制，不僅能有效降低機(jī)器人控制難度，還能控制單個(gè)機(jī)器人成本.

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

4.1 VAPF算法測(cè)試

為了測(cè)試VAPF算法的性能，本文在matlab平臺(tái)上進(jìn)行了仿真實(shí)驗(yàn).實(shí)驗(yàn)保證算法運(yùn)行環(huán)境不變，且設(shè)置了良好的參數(shù).表1展示了VAPF算法的參數(shù)列表.

表1 參數(shù)列表Table 1 List of parameters

機(jī)器人自組裝環(huán)境設(shè)定為500×500的柵格圖，圖中不規(guī)則地分布著若干個(gè)圓形代表地圖上的障礙物.機(jī)器人的初始位置為隨機(jī)分布，但保證機(jī)器人不在障礙物內(nèi)部，且目標(biāo)點(diǎn)數(shù)量與機(jī)器人數(shù)量相同.

本實(shí)驗(yàn)采用自組裝問(wèn)題中的直線型、H型和不規(guī)則型進(jìn)行對(duì)比實(shí)驗(yàn).其中，直線型和H型是最為簡(jiǎn)單常規(guī)的模型，能有效測(cè)試算法正確性、穩(wěn)定性與性能，且這類簡(jiǎn)單模型的復(fù)合可以模仿動(dòng)物的運(yùn)動(dòng)方式，有廣泛的應(yīng)用前景.本實(shí)驗(yàn)設(shè)計(jì)的直線型和H型模型分布均勻，而不規(guī)則型的目標(biāo)點(diǎn)分布不均，但在一定程度上為包圍型自組裝配置，能有效考驗(yàn)算法在目標(biāo)指派問(wèn)題上的性能.上述3種模型實(shí)驗(yàn)如圖3-圖5所示.

圖3 VAPF算法實(shí)現(xiàn)直線型自組裝Fig.3 VAPF algorithm in linear self-assembly

圖4 VAPF算法實(shí)現(xiàn)H型自組裝Fig.4 VAPF algorithm in H-type self-assembly

圖5 VAPF算法實(shí)現(xiàn)不規(guī)則型自組裝Fig.5 VAPF algorithm in irregular self-assembly

其中，黑色的圓圈代表預(yù)處理后的障礙物；黑色實(shí)線代表機(jī)器人各自規(guī)劃的路徑；實(shí)線終點(diǎn)的標(biāo)記代表實(shí)驗(yàn)設(shè)定的目標(biāo)點(diǎn)；不同的色塊由Voronoi圖構(gòu)建，其代表機(jī)器人各自的運(yùn)動(dòng)范圍，能有效地幫助機(jī)器人實(shí)現(xiàn)碰撞避免.

通過(guò)上述結(jié)果可見(jiàn)，使用VAPF算法，機(jī)器人在不同自組裝模型下均能高效、安全地到達(dá)各自的目標(biāo)點(diǎn).目標(biāo)指派策略使得機(jī)器人各自到達(dá)目標(biāo)點(diǎn)的消耗實(shí)現(xiàn)了最大程度上的均衡；運(yùn)動(dòng)空間劃分能有效避免碰撞；運(yùn)動(dòng)控制方法能有效地抑制機(jī)器人在進(jìn)行路徑規(guī)劃時(shí)發(fā)生抖動(dòng)現(xiàn)象.

4.2 對(duì)比實(shí)驗(yàn)分析

針對(duì)上述實(shí)驗(yàn)?zāi)Ｐ?，本?shí)驗(yàn)通過(guò)不斷增加機(jī)器人數(shù)量來(lái)對(duì)比VAPF算法和OAPF算法在時(shí)間和路程方面的表現(xiàn).實(shí)驗(yàn)結(jié)果數(shù)據(jù)如圖6和圖7所示.

圖6 算法時(shí)間消耗對(duì)比圖Fig.6 Algorithm time consumption comparison chart

圖7 算法路程消耗對(duì)比圖Fig.7 Algorithmic distance consumption comparison chart

從多組對(duì)比實(shí)驗(yàn)可以看出，時(shí)間消耗方面：兩種算法的時(shí)間消耗均隨著機(jī)器人數(shù)量的增加而增加，OAPF算法時(shí)間消耗呈近似指數(shù)增長(zhǎng)趨勢(shì)，而VAPF算法的時(shí)間消耗增速遠(yuǎn)低于OAPF算法.在機(jī)器人數(shù)量相對(duì)較少時(shí)，兩種算法的性能差別尤為明顯.VAPF通過(guò)Voronoi圖劃分運(yùn)動(dòng)空間，機(jī)器人數(shù)量相對(duì)較少意味著其分布也相對(duì)稀疏，則每個(gè)機(jī)器人在單次迭代中有更大的獨(dú)立運(yùn)動(dòng)空間.高效的迭代性能使得少量群組機(jī)器人的加入對(duì)VAPF算法性能影響極小，所以在圖6中，當(dāng)機(jī)器人數(shù)量不足20個(gè)時(shí)，時(shí)間消耗基本沒(méi)有變化.而OAPF算法每次迭代要考慮機(jī)器人之間斥力，且單次迭代運(yùn)動(dòng)空間極小，即使是少量群組機(jī)器人的加入也會(huì)嚴(yán)重加劇算法的時(shí)間消耗.H型自組裝相對(duì)于直線型自組裝更為復(fù)雜，不規(guī)則型自組裝更甚之，復(fù)雜的自組裝要求會(huì)大大增加OAPF算法的時(shí)間消耗，而VAPF算法在不同自組裝要求下性能穩(wěn)定，且遠(yuǎn)優(yōu)于OAPF算法.平均路程長(zhǎng)度方面：機(jī)器人的分布對(duì)結(jié)果有著相對(duì)重要的影響，隨著機(jī)器人數(shù)量的增加，隨機(jī)且均勻的分布會(huì)使得機(jī)器人平均路程愈發(fā)穩(wěn)定.由于OAPF算法中機(jī)器人之間存在斥力，OAPF算法的平均路程長(zhǎng)度均多于VAPF算法，在復(fù)雜類型的自組裝實(shí)驗(yàn)中尤為明顯.

通過(guò)上述實(shí)驗(yàn)對(duì)比分析，VAPF算法無(wú)論是在時(shí)間消耗方面還是路程長(zhǎng)度方面都有著顯著的優(yōu)勢(shì)，且對(duì)不同的自組裝要求以及群組機(jī)器人規(guī)模均有著良好的適應(yīng)性.總的來(lái)說(shuō)，VAPF算法達(dá)成了自組裝過(guò)程中的碰撞避免和障礙躲避要求，在性能方面有著顯著的優(yōu)越性，有著一定的應(yīng)用前景.

5 總 結(jié)

本文提出的基于Voronoi約束的人工勢(shì)場(chǎng)算法，并將其應(yīng)用到群組機(jī)器人的自組裝路徑規(guī)劃方面，通過(guò)matlab仿真實(shí)驗(yàn)證明了該算法在碰撞避免和障礙躲避方面的可靠性、安全性.在該算法中，群組機(jī)器人均為無(wú)差異個(gè)體，且能自主運(yùn)動(dòng)，只要通過(guò)有限且少量次數(shù)的信息交互，就能達(dá)成自組裝配置，具有良好的通用性和穩(wěn)定性.其中，匈牙利算法和替換策略，為機(jī)器人提供理想的目標(biāo)規(guī)劃；單機(jī)器人在Voronoi圖的單元中運(yùn)動(dòng)，保證了機(jī)器人間的碰撞避免；機(jī)器人在單元中使用人工勢(shì)場(chǎng)進(jìn)行路徑規(guī)劃，既使得機(jī)器人可以自主避障，又去除了其他機(jī)器人的干擾，機(jī)器人能在自己的cell中最大程度地移動(dòng)，大大減少了算法迭代次數(shù)和機(jī)器人之間的信息交互，實(shí)現(xiàn)了時(shí)間和路程的雙贏.

除此以外，本文提出的算法及仿真實(shí)驗(yàn)都建立在2D空間中，考察方面有限.未來(lái)工作將考慮運(yùn)動(dòng)學(xué)約束，并將該算法運(yùn)用到3D空間中，與真實(shí)自然環(huán)境結(jié)合，在實(shí)際應(yīng)用方向作擴(kuò)展研究.