基于改進(jìn)蜂群算法的橋式起重機(jī)吊裝路徑規(guī)劃*

陳志梅 李孟笑 邵雪卷

太原科技大學(xué)電子信息工程學(xué)院 太原 030024

0 引言

橋式起重機(jī)因其操作靈活、占地資源少和負(fù)載能力強(qiáng)的優(yōu)勢而被廣泛應(yīng)用于工廠倉庫、港口碼頭等地，但惡劣的工作環(huán)境以及部分不規(guī)范的人工操作，使橋式起重機(jī)在三維環(huán)境中的吊裝存在安全隱患。為使橋式起重機(jī)能在各種復(fù)雜環(huán)境完成自動運(yùn)行，完成吊裝任務(wù)，路徑規(guī)劃也被逐漸應(yīng)用到橋式起重機(jī)自動運(yùn)移課題中，故研究橋式起重機(jī)三維吊裝路徑規(guī)劃具有重要意義[1]。

路徑規(guī)劃是指在存在障礙物的空間中，按照一定評價標(biāo)準(zhǔn)在起始點(diǎn)和終點(diǎn)之間找到一條安全碰撞且最符合評價標(biāo)準(zhǔn)的路徑[2]，路徑規(guī)劃算法被應(yīng)用到機(jī)器人、車輛、無人機(jī)、起重機(jī)等各領(lǐng)域，算法主要有快速擴(kuò)展隨機(jī)樹(Rapidly—exploring Random Tree，RRT)算法、蟻群算法、遺傳算法等。Zhao Y T等[3]對起重機(jī)在板庫中的路徑規(guī)劃，用網(wǎng)格法對環(huán)境建模，通過整合轉(zhuǎn)折點(diǎn)、篩選候選解、動態(tài)揮發(fā)信息素等對蟻群算法改進(jìn)，得到起重機(jī)安全吊裝路徑。Cai P P等[4]將起重機(jī)路徑規(guī)劃問題轉(zhuǎn)化為包含隱式約束的多目標(biāo)非線性整數(shù)優(yōu)化問題，設(shè)計(jì)主從并行遺傳算法，優(yōu)化提升路徑的能量成本、時間成本，在復(fù)雜環(huán)境下生成高質(zhì)量路徑。陳志梅等[5]對橋式起重機(jī)在三維復(fù)雜環(huán)境下的路徑規(guī)劃問題，將RRT算法和粒子群算法相結(jié)合，得到符合橋式起重機(jī)運(yùn)行條件的安全路徑。Dutta S等[6]基于并行化方法進(jìn)行碰撞檢測和路徑規(guī)劃，并提出路徑重新規(guī)劃策略，解決塔式起重機(jī)在含有動態(tài)障礙物環(huán)境下的路徑規(guī)劃。Lin Y S等[7]對履帶起重機(jī)進(jìn)行路徑規(guī)劃，改進(jìn)RRT算法，從采樣池和未開發(fā)空間選取樣本，引導(dǎo)樹向無障礙空間移動，改進(jìn)樹擴(kuò)展策略，在較短時間內(nèi)生成無碰撞路徑。魏云平等[8]在柵格地圖中，將路徑拐點(diǎn)數(shù)轉(zhuǎn)化為長度，使用遺傳算法得到用時較短的二維空間路徑。馬向華等[9]在傳統(tǒng)A*算法中引入節(jié)點(diǎn)方向信息啟發(fā)函數(shù)，并加入轉(zhuǎn)向代價函數(shù)，規(guī)劃出的路徑拐點(diǎn)少，使之符合橋式起重機(jī)運(yùn)行約束條件。

上述文獻(xiàn)對起重機(jī)路徑規(guī)劃的研究中所規(guī)劃出的路徑是在固定起重機(jī)吊裝高度的基礎(chǔ)上得到的，忽視障礙物高度而進(jìn)行路徑規(guī)劃，對所有障礙選擇繞行，既浪費(fèi)吊裝時間，所得路徑也并非最短，路徑拐點(diǎn)也較多。由于實(shí)際中障礙物形狀、大小、高度不一，起重機(jī)吊裝高度選擇不易確定，且如果每次吊裝高度選擇最高值并不符合實(shí)際吊裝。因此，本文在不固定起重機(jī)吊裝高度的基礎(chǔ)上，在三維已知環(huán)境中對橋式起重機(jī)的智能吊裝避障進(jìn)行研究。

采用空間等分網(wǎng)格法建立三維環(huán)境，對環(huán)境中凹形障礙作虛擬填充處理，防止規(guī)劃的路徑穿越凹形障礙物。由于人工蜂群算法具有控制參數(shù)少、通用性強(qiáng)、易與實(shí)際問題結(jié)合的特點(diǎn)，已廣泛應(yīng)用于路徑規(guī)劃領(lǐng)域[10，11]、函數(shù)優(yōu)化、信號處理等方面，故選用人工蜂群算法進(jìn)行已知環(huán)境下的起重機(jī)路徑規(guī)劃。并對算法進(jìn)行改進(jìn)，在觀察蜂階段引入輪盤賭與反輪盤賭并行選擇機(jī)制，防止算法陷入局部最優(yōu)，加入節(jié)點(diǎn)篩選規(guī)則，剔除冗余節(jié)點(diǎn)。最后以剩余節(jié)點(diǎn)和起始點(diǎn)、目標(biāo)點(diǎn)為控制點(diǎn)，以不與障礙物碰撞為約束，使用多段Bezier曲線進(jìn)行平滑優(yōu)化。為符合實(shí)際安全吊裝，在算法中還加入障礙物高度判斷策略，使算法智能選擇繞行或跨越障礙，規(guī)劃出的路徑與障礙物留有間隔裕量，使橋式起重機(jī)能安全運(yùn)行，然后通過仿真驗(yàn)證該方法在橋式起重機(jī)安全吊裝路徑規(guī)劃上的可行性。

1 三維空間地圖建立

在實(shí)際中，進(jìn)行路徑規(guī)劃前要求計(jì)算機(jī)獲得障礙物先驗(yàn)信息，然后使用算法進(jìn)行路徑規(guī)劃。為模擬三維環(huán)境，采用空間等分網(wǎng)格方法，在規(guī)劃空間建立三維坐標(biāo)系，并沿x軸、y軸、z軸等分，使空間中任意障礙物都可由三維點(diǎn)集合表示，算法規(guī)劃出的路徑也可由點(diǎn)集合表示出來。為便于仿真，假設(shè)x軸、y軸跨度為50 m，z軸高度設(shè)置為15 m，設(shè)置起始點(diǎn)坐標(biāo)為(25，0，5)，目標(biāo)點(diǎn)為(25，50，5)，所建環(huán)境如圖1所示。

圖1 橋式起重機(jī)安全吊裝規(guī)劃空間

2 ABC算法

ABC算法是國外學(xué)者在2005年提出的基于蜜蜂采蜜行為的啟發(fā)式算法。算法應(yīng)用于路徑規(guī)劃領(lǐng)域，其蜂群采蜜行為與路徑優(yōu)化關(guān)系對應(yīng)；蜜蜂采蜜行為對應(yīng)路徑規(guī)劃問題，蜜源的位置對應(yīng)可行路徑，蜜源的花蜜量對應(yīng)可行路徑質(zhì)量，尋找花蜜速度對應(yīng)可行路徑優(yōu)化速度，最大花蜜量對應(yīng)最優(yōu)路徑。使用人工蜂群算法進(jìn)行路徑規(guī)劃的基本步驟為：

1）初始化算法參數(shù)，設(shè)置適應(yīng)度函數(shù)。初始蜜源數(shù)N、算法最大迭代次數(shù)maxcycle及最大限制次數(shù)limit。初始迭代次數(shù)iter=1，初始蜜源適應(yīng)值不變時的限制次數(shù)trial=0。計(jì)算各蜜源適應(yīng)度值，并記錄最優(yōu)值，即有

式中：j為D維解向量的某個分量，j={1，2，…，D}；為第j維的上下限；rand(0，1)為[0，1]之間隨機(jī)數(shù)。

2）采蜜蜂搜索方式為每只采蜜蜂按式(2)到蜜源附近搜索，并計(jì)算蜜源新適應(yīng)度值，若優(yōu)于當(dāng)前蜜源，依貪婪準(zhǔn)則，更新當(dāng)前蜜源。否則令trial=trial+1。若trial＞limit，該采蜜蜂放棄此蜜源，并轉(zhuǎn)化為偵查蜂，在全局范圍內(nèi)搜索新蜜源。

3）各觀察蜂按式(3)選擇要跟隨的采蜜蜂，選擇后觀察蜂轉(zhuǎn)化為采蜜蜂繼續(xù)按式(2)在蜜源附近搜索，若新蜜源優(yōu)于當(dāng)前蜜源，依貪婪準(zhǔn)則更新當(dāng)前蜜源，否則令trial=trial+1。若trial＞limit，該采蜜蜂放棄此蜜源，并轉(zhuǎn)化為偵查蜂，在全局范圍內(nèi)按式(4)搜索新蜜源。

式中：f iti為第i個解對應(yīng)的適應(yīng)度值，為所有解適應(yīng)值的和。

4）記錄蜂群找到的最優(yōu)蜜源，保存最優(yōu)解。

5）迭代次數(shù)增加：iter=iter+1，若iter＞maxcycle，記錄最優(yōu)蜜源代表的路徑節(jié)點(diǎn)，并跳轉(zhuǎn)到Step6，否則跳轉(zhuǎn)到步驟2）。

6）在三維空間表示出最佳路徑。

3 改進(jìn)ABC算法

1) 在標(biāo)準(zhǔn)ABC算法中，在觀察蜂選擇要跟隨的采蜜蜂時，依式(3)選擇要跟隨的采蜜蜂，這易使算法陷入局部最優(yōu)。本文在觀察蜂選擇階段，以輪盤賭與反輪盤賭并行選擇機(jī)制代替觀察蜂選擇方式。首先得出每個采蜜蜂的適應(yīng)度值占總適應(yīng)值的概率值，將這些值從0開始依次累加，每累加一次即記錄一次值，并將值記錄在一個矩陣中，即并隨機(jī)產(chǎn)生一個[0，1]內(nèi)的隨機(jī)數(shù)rand1，隨機(jī)數(shù)值落在Q的區(qū)間，觀察蜂就跟隨此區(qū)間對應(yīng)的采蜜蜂進(jìn)行鄰域搜索，得到新適應(yīng)值并記錄。接著計(jì)算每個采蜜蜂適應(yīng)值倒數(shù)占采蜜蜂適應(yīng)度值倒數(shù)之和的概率值，依次累加并記錄，得到隨機(jī)產(chǎn)生[0，1]的隨機(jī)數(shù)rand2，記錄數(shù)值落在哪個區(qū)間，觀察蜂跟隨對應(yīng)的采蜜蜂進(jìn)行鄰域搜索，得到適應(yīng)值并記錄，得到的2次新適應(yīng)值與原適應(yīng)值互相比較，保留適應(yīng)值最小的。

此機(jī)制以并行選擇優(yōu)勢，既避免了原算法陷入局部最優(yōu)，又能以更少的迭代次數(shù)找到全局最優(yōu)解。

2) ABC算法在規(guī)劃路徑時，一個蜜源代表一條路徑，每條路徑由若干路徑節(jié)點(diǎn)有序連接組成，節(jié)點(diǎn)過多則路徑拐點(diǎn)會較多，節(jié)點(diǎn)過少則路徑會穿越障礙，兩者均不符合規(guī)劃要求。因此，在算法中加入節(jié)點(diǎn)篩選規(guī)則，使算法能智能排除冗余節(jié)點(diǎn)，優(yōu)化路徑。

節(jié)點(diǎn)選取規(guī)則為：定義距離d，從起點(diǎn)開始計(jì)算當(dāng)前點(diǎn)到下一點(diǎn)的距離與下一點(diǎn)到終點(diǎn)的距離，當(dāng)前點(diǎn)為(xa,ya,za),下一點(diǎn)為(xb,yb,zb),終點(diǎn)為(xc,yc,zc)。滿足式(5)時，再計(jì)算式(6)，式(6)確保下一點(diǎn)位于當(dāng)前點(diǎn)前方且靠近終點(diǎn)。在前點(diǎn)d的范圍內(nèi)，所有優(yōu)化點(diǎn)均可作為下一點(diǎn)的可行解，此時取Dn值小的點(diǎn)作為下一點(diǎn)，Dn值越小，該點(diǎn)到當(dāng)前點(diǎn)和終點(diǎn)加權(quán)最優(yōu)。以此規(guī)則控制節(jié)點(diǎn)的選取，進(jìn)行二次路徑優(yōu)化。

3)二次路徑優(yōu)化后，節(jié)點(diǎn)數(shù)減少，但路徑仍存在較多拐點(diǎn)，需對優(yōu)化后的路徑進(jìn)行平滑處理，進(jìn)行第三次優(yōu)化。本文將蜂群算法與三次Bezier曲線結(jié)合，將算法生成并二次優(yōu)化的路徑節(jié)點(diǎn)作為Bezier曲線的控制點(diǎn)，利用多段三次Bezier曲線將節(jié)點(diǎn)組成的路線轉(zhuǎn)換成光滑曲線，并以不與障礙物碰撞為約束條件，對路徑進(jìn)行三次優(yōu)化。

三次Bezier曲線的定義為

式中：pi為第i個控制點(diǎn)坐標(biāo)。

多段三次Bezier優(yōu)化路徑時，曲線方程為

4 橋式起重機(jī)路徑規(guī)劃

本文針對橋式起重機(jī)智能安全吊裝進(jìn)行路徑規(guī)劃，首先建立三維空間模型，然后使用改進(jìn)ABC算法進(jìn)行路徑規(guī)劃。考慮到人為吊裝時不能每次都將重物起升到最高處再進(jìn)行吊裝運(yùn)行，或通過固定起重高度的方式來運(yùn)行起重機(jī)，應(yīng)在算法中加入障礙高度判斷策略，針對障礙物不同高度，起重機(jī)可智能選擇跨越或繞行。在吊裝高度高于障礙物時，留有安全裕量情況下的起重物將直接越過障礙；在吊裝高度低于障礙物時，為安全起見起重機(jī)設(shè)置上升高度閾值，在高度閾值內(nèi)，若起重機(jī)上升能高于障礙物并留有安全裕量，則跨過障礙物，否則選擇繞過障礙物。加入障礙高度判斷策略規(guī)劃出的路徑，存在高度維度變化，能解決因固定吊裝高度而多次繞行障礙物，導(dǎo)致規(guī)劃的路徑不是最短路徑的問題。

由于橋式起重機(jī)吊裝是由大小車協(xié)同吊裝，路徑若存在過多拐點(diǎn)，大小車需頻繁制動，這對橋式起重機(jī)壽命影響較大，所以要求規(guī)劃出的路徑平滑，本文將ABC算法和Bezier曲線結(jié)合，使得到的路徑平滑，滿足橋式起重機(jī)吊裝路徑要求。規(guī)劃出路徑后，起重機(jī)根據(jù)路徑進(jìn)行軌跡跟蹤，到達(dá)目標(biāo)點(diǎn)。

本文算法所選擇的適應(yīng)度評價值為路徑長度，即

式（9）為相鄰2個三維坐標(biāo)間的距離，式（10）為所有路徑節(jié)點(diǎn)間距離之和。改進(jìn)ABC算法流程圖如圖2所示。

圖2 改進(jìn)ABC算法流程

由于環(huán)境地圖中存在凹形障礙物，且本文算法中一個蜜源代表一條可行路徑，凹形障礙會導(dǎo)致規(guī)劃路徑穿越障礙物，導(dǎo)致路徑規(guī)劃失敗。本文對凹形障礙作虛擬填充處理，算法在判斷時將凹形障礙可行空間視作障礙空間處理，使規(guī)劃路徑不會穿過此凹形障礙物，如圖3所示。

圖3 凹形障礙處理前后路徑

5 仿真研究

設(shè)置三維地圖x軸、y軸、z軸跨度分別為[0，50]、[0，50]、[0，15]。地圖中障礙物包含1個三棱錐、2個三棱柱、1個五棱柱、1個六棱柱、1個長方體、4個圓柱、1個球體、3個凹形障礙。

在算法中，經(jīng)過多次參數(shù)調(diào)整，參數(shù)設(shè)置為：蜜源數(shù)N=20，采蜜蜂和觀察蜂各為20只；算法最大迭代次數(shù)maxcycle=200，采蜜蜂在同一蜜源處最大搜索次數(shù)limit=10，初始路徑節(jié)點(diǎn)數(shù)m=49（不包括起點(diǎn)和終點(diǎn)），經(jīng)過多次仿真測試，設(shè)置d=7.1，且為了起重機(jī)吊裝安全，要求規(guī)劃的路徑與障礙物之間留有間隔，起重機(jī)跨越障礙時的高度不能大于9 m。

標(biāo)準(zhǔn)ABC算法所規(guī)劃路徑如圖4所示。路徑是由包含起點(diǎn)和終點(diǎn)在內(nèi)的51個節(jié)點(diǎn)有序連接組成，路徑長度為75.22 m，且路徑拐點(diǎn)多，不平滑。

圖4 標(biāo)準(zhǔn)算法路徑

本文將粒子群算法應(yīng)用到此三維復(fù)雜環(huán)境中進(jìn)行路徑規(guī)劃，作為比較。其中粒子群算法的參數(shù)經(jīng)過多次仿真測試，選擇加速因子c1和c2分別為2，粒子數(shù)為200，權(quán)重系數(shù)w為0.4，評價函數(shù)和節(jié)點(diǎn)數(shù)、迭代次數(shù)與標(biāo)準(zhǔn)蜂群算法一樣，仿真得到路徑如圖5所示。

圖5 粒子群算法路徑

圖5中，路徑由包含起點(diǎn)和目標(biāo)點(diǎn)在內(nèi)的51個節(jié)點(diǎn)構(gòu)成，路徑長度為79.24 m，規(guī)劃路徑與障礙物無碰撞，但路徑拐點(diǎn)多，與標(biāo)準(zhǔn)蜂群算法一樣有冗余節(jié)點(diǎn)。

改進(jìn)ABC算法路徑規(guī)劃一次優(yōu)化后如圖6所示，首先得到節(jié)點(diǎn)數(shù)為51的路徑，其長度為67.09 m，二次優(yōu)化后剩余16個路徑節(jié)點(diǎn)，對這16個路徑節(jié)點(diǎn)組成的路徑，以不與障礙物碰撞為條件，經(jīng)過7段三次Bezier曲線的第三次優(yōu)化，路徑更為平滑，最終所得到的路徑長度為58.79m，圖7為最終規(guī)劃路徑。圖8為標(biāo)準(zhǔn)算法、粒子群算法與本文算法的路徑節(jié)點(diǎn)都為51時的路徑長度變化值。

圖6 改進(jìn)算法初始路徑

圖7 改進(jìn)算法最終路徑

圖8 路徑長度曲線變化圖

圖8比較了粒子群算法、標(biāo)準(zhǔn)蜂群算法、本文算法路徑節(jié)點(diǎn)均為51、迭代次數(shù)均為200時的路徑長度變化值，粒子群算法達(dá)到最短路徑時的迭代次數(shù)為127次，標(biāo)準(zhǔn)蜂群算法迭代次數(shù)為115次，本文算法迭代次數(shù)為57次，且路徑更短。改進(jìn)后的算法能更快收斂。

為驗(yàn)證算法的穩(wěn)定性，將標(biāo)準(zhǔn)ABC算法、粒子群算法和本文算法各運(yùn)行數(shù)次，從中挑選10組路徑長度數(shù)據(jù)對比，如表2所示。表2數(shù)據(jù)表明，改進(jìn)的蜂群算法比原算法和粒子群算法規(guī)劃的路徑更短，且算法更加穩(wěn)定。

表2 路徑長度對比表 m

6 結(jié)論

本文給出一種適合橋式起重機(jī)在三維已知靜態(tài)環(huán)境下的路徑規(guī)劃新方法。在建立的三維地圖模型基礎(chǔ)上使用改進(jìn)人工蜂群算法進(jìn)行路徑規(guī)劃。改進(jìn)后的蜂群算法避免了算法易早熟收斂的問題，也改善算法應(yīng)用于路徑規(guī)劃領(lǐng)域的節(jié)點(diǎn)冗余導(dǎo)致的拐點(diǎn)較多的問題，算法還與Bezier曲線結(jié)合，使路徑更加平滑，仿真證明了改進(jìn)算法應(yīng)用于起重機(jī)路徑規(guī)劃領(lǐng)域的優(yōu)越性。算法不僅可以應(yīng)用于起重機(jī)路徑規(guī)劃，還可以用于無人機(jī)、車輛、機(jī)器人等路徑規(guī)劃。本文改進(jìn)算法僅適用于已知環(huán)境，并不適用于存在動態(tài)障礙物的環(huán)境中，未來研究方向是把蜂群算法擴(kuò)展求解更加復(fù)雜環(huán)境下的路徑規(guī)劃問題。