改進(jìn)人工魚群法的機(jī)器人路徑規(guī)劃方法

張 寧，陳茜茜，李 微，張秀峰*

(1.國(guó)家康復(fù)輔具研究中心，北京 100176；2.天津理工大學(xué) 電氣電子工程學(xué)院，天津 300384)

0 引 言

機(jī)器人是將電子技術(shù)、控制技術(shù)、機(jī)械技術(shù)以及通信技術(shù)等技術(shù)融合為一體的高科技學(xué)科[1]，機(jī)器人的誕生節(jié)省人類大量財(cái)力、物力，提升社會(huì)生產(chǎn)效率，人類無(wú)法完成的高危任務(wù)通過(guò)機(jī)器人可順利完成。導(dǎo)航機(jī)器人是機(jī)器人領(lǐng)域的重要課題。依據(jù)機(jī)器人規(guī)劃目標(biāo)存在的差異，可將機(jī)器人路徑規(guī)劃分為全區(qū)域遍歷路徑規(guī)劃以及點(diǎn)對(duì)點(diǎn)路徑規(guī)劃兩部分[2-3]。可視圖法、柵格法等方法可應(yīng)用于環(huán)境已知情況下的路徑規(guī)劃，粒子群算法、遺傳算法等機(jī)器學(xué)習(xí)算法可應(yīng)用于未知環(huán)境以及僅明確部分環(huán)境情況下的路徑規(guī)劃。

目前針對(duì)機(jī)器人路徑規(guī)劃的研究較多，徐小強(qiáng)等人分別利用改進(jìn)人工勢(shì)場(chǎng)法以及螢火蟲算法實(shí)現(xiàn)機(jī)器人路徑規(guī)劃[4-5]，但對(duì)于障礙物過(guò)多以及動(dòng)態(tài)環(huán)境下，規(guī)劃性能較差。人工魚群法是依據(jù)動(dòng)物行為而來(lái)的全局尋優(yōu)的重要方法，人工魚群法依據(jù)動(dòng)物的局部尋優(yōu)行為獲取群體的全局最優(yōu)值，該算法具有較高的全局收斂能力，可有效避免計(jì)算過(guò)程中陷入局部最優(yōu)，自適應(yīng)搜索能力強(qiáng)，無(wú)需設(shè)置目標(biāo)函數(shù)梯度值即可實(shí)現(xiàn)算法快速收斂[6]。針對(duì)機(jī)器人路徑規(guī)劃問(wèn)題對(duì)人工魚群法實(shí)施改進(jìn)，為提升機(jī)器人路徑規(guī)劃性能，獲取最佳全局極值能力，改善傳統(tǒng)人工魚群法對(duì)啟發(fā)式函數(shù)起始點(diǎn)要求過(guò)于遲鈍的缺陷，利用自適應(yīng)擁擠度因子以及自適應(yīng)視覺(jué)范圍對(duì)人工魚群法實(shí)施改進(jìn)，提升機(jī)器人路徑規(guī)劃有效性。通過(guò)實(shí)驗(yàn)驗(yàn)證采用改進(jìn)人工魚群法規(guī)劃?rùn)C(jī)器人路徑具有較高有效性。

1 改進(jìn)人工魚群法的機(jī)器人路徑規(guī)劃方法

1.1 建立環(huán)境模型與路徑表示

選取多面模型表示法建立機(jī)器人行駛路徑的環(huán)境空間模型。設(shè)所建立的環(huán)境空間未考慮高度信息，機(jī)器人移動(dòng)范圍為二維有限空間，將機(jī)器人半徑的一半向外擴(kuò)展設(shè)置為障礙物邊界[7]，保障障礙物與機(jī)器人間存在一定距離，將機(jī)器人視為移動(dòng)質(zhì)點(diǎn)。

在直角坐標(biāo)系XOY內(nèi)建立全局環(huán)境場(chǎng)景，利用圓或?qū)嵭亩噙呅伪硎菊系K物，用Z(xz,yz)與T(xt,yt)分別表示起始點(diǎn)以及目標(biāo)點(diǎn)，利用x軸以及y軸設(shè)置為連接Z與T的直線以及垂直于x軸且經(jīng)過(guò)Z的直線，獲取新的環(huán)境坐標(biāo)系xoy。坐標(biāo)變換直角坐標(biāo)系XOY內(nèi)隨機(jī)點(diǎn)Q(X,Y)可得該點(diǎn)在坐標(biāo)系xoy內(nèi)的坐標(biāo)為：

(1)

(2)

式中，λ與(x,y)分別表示初始x軸與ZT間的夾角以及點(diǎn)Q在坐標(biāo)系xoy內(nèi)的坐標(biāo)。

n等分線段ZT，用{L1,L2,…,Ln-1}表示沿各等分點(diǎn)所獲取的與ZT垂線段垂直的柵欄線。隨機(jī)選取柵欄線中點(diǎn)設(shè)置為路徑節(jié)點(diǎn)，可得y={ys,y1,y2,…,yn-1,yt}即不同路徑節(jié)點(diǎn)縱坐標(biāo)向量建立的環(huán)境空間路徑。

機(jī)器人路徑規(guī)劃結(jié)果由所建立目標(biāo)函數(shù)決定，選取機(jī)器人行駛路徑總長(zhǎng)度最短以及路徑安全度最高作為優(yōu)化目標(biāo)[8]，將機(jī)器人行駛路徑依據(jù)障礙物碰撞情況分為不可行路徑以及可行路徑兩部分。利用懲罰函數(shù)法獲取目標(biāo)函數(shù)值極小的個(gè)體，利用施加懲罰項(xiàng)在評(píng)價(jià)不可行路徑時(shí)提升目標(biāo)函數(shù)值。設(shè)包含起始點(diǎn)以及目標(biāo)點(diǎn)的路徑節(jié)點(diǎn)數(shù)量為n，該路徑中包含路徑段數(shù)量為n-1，用Q={Q1,Q2,…,Qn}與Qi(i=1,2,…,n)分別表示路徑以及路徑節(jié)點(diǎn)。建立優(yōu)化目標(biāo)如下：

(1)路徑總長(zhǎng)度最短。

(3)

式中，|qiqi+1|與num分別表示路徑段qiqi+1長(zhǎng)度以及路徑Q內(nèi)相交于障礙物的路徑段數(shù)量；inf1表示路徑Q為不可行路徑時(shí)所需施加的懲罰項(xiàng)。

(2)路徑安全度。路徑安全度指機(jī)器人行駛過(guò)程中需躲避障礙物，避免碰撞障礙物，設(shè)置機(jī)器人路徑規(guī)劃路徑安全度目標(biāo)函數(shù)如下：

(4)

式中，g與μ分別表示路徑Q與全部障礙物的最短距離以及保障路徑安全度有界的合適正數(shù)；num與inf2分別表示與障礙物相交的路徑Q內(nèi)路徑段數(shù)量以及路徑Q為不可行路徑時(shí)所需施加的正數(shù)懲罰項(xiàng)。

選取權(quán)重系數(shù)法建立多目標(biāo)機(jī)器人路徑規(guī)劃的目標(biāo)函數(shù)，將總目標(biāo)函數(shù)值分配權(quán)值至各目標(biāo)函數(shù)值[9]，建立機(jī)器人路徑規(guī)劃總目標(biāo)函數(shù)表達(dá)式如下：

f(Q)=ω1·f1(Q)+ω2·f2(Q)

(5)

式中，ω1表示路徑長(zhǎng)度的權(quán)值系數(shù)，ω2表示路徑安全度的權(quán)值系數(shù)。

可依據(jù)機(jī)器人行駛場(chǎng)景以及路徑規(guī)劃需求實(shí)時(shí)調(diào)整權(quán)值系數(shù)[10]，獲取最優(yōu)機(jī)器人路徑規(guī)劃結(jié)果。利用改進(jìn)人工魚群法求解所建立總目標(biāo)函數(shù)，規(guī)劃?rùn)C(jī)器人最佳行駛路徑。

1.2 人工魚群法

令向量X={x1,x2,…,xn}表示人工魚群法中個(gè)體狀態(tài)，xi為待尋優(yōu)變量。Y=f(x)與di,j=‖Xi-Xj‖分別表示人工魚個(gè)體當(dāng)前位置的食物濃度以及不同個(gè)體間距；Y與Visual分別表示目標(biāo)函數(shù)值以及人工魚感知距離；step與δ(0<δ<1)分別為人工魚移動(dòng)步長(zhǎng)以及擁擠度因子。

人工魚群法主要包括以下操作：

(1)覓食操作。Xi表示人工魚個(gè)體此時(shí)狀態(tài)，隨機(jī)選取狀態(tài)Xj于感知范圍內(nèi)，采用人工魚群法求解極小值時(shí)，當(dāng)Xi>Xj以及Xi≤Xj時(shí)，分別向Xj方向前進(jìn)以及再次隨機(jī)選擇狀態(tài)Xj，重復(fù)判斷狀態(tài)Xj是否符合移動(dòng)條件，重復(fù)迭代仍不符合移動(dòng)條件時(shí)，繼續(xù)向隨機(jī)方向移動(dòng)[11]。

(4)公告板。人工魚群內(nèi)最優(yōu)人工魚個(gè)體狀態(tài)利用公告板存儲(chǔ)。人工魚群法中人工魚個(gè)體完成尋優(yōu)操作后應(yīng)查看公告板所登記狀態(tài)與人工魚個(gè)體狀態(tài)[12]，人工魚個(gè)體狀態(tài)優(yōu)于公告板狀態(tài)時(shí)，更新公告板。

(5)操作選擇。依據(jù)機(jī)器人路徑規(guī)劃需求評(píng)價(jià)人工魚環(huán)境，依據(jù)人工魚個(gè)體環(huán)境選取相應(yīng)操作。機(jī)器人路徑規(guī)劃問(wèn)題是極小值求取問(wèn)題，需令人工魚進(jìn)行追尾操作，追尾操作無(wú)法進(jìn)步時(shí)需進(jìn)行覓食操作[13]，覓食操作無(wú)法進(jìn)步時(shí)需執(zhí)行聚群操作，以上操作仍未獲取理想結(jié)果時(shí)，令人工魚個(gè)體隨機(jī)選取操作。

1.3 改進(jìn)人工魚群法的機(jī)器人路徑規(guī)劃

利用自適應(yīng)擁擠度因子以及自適應(yīng)視覺(jué)范圍對(duì)人工魚群法實(shí)施改進(jìn)。

通過(guò)柵格法將所建立環(huán)境空間實(shí)施離散化，用(xi,yi)與h分別表示人工魚i的當(dāng)前位置以及評(píng)價(jià)函數(shù)，(xg,yg)表示待求解目標(biāo)點(diǎn)位置，可得評(píng)價(jià)函數(shù)h如下：

(6)

采用人工魚群法規(guī)劃?rùn)C(jī)器人路徑時(shí)，利用覓食、追尾、聚群操作用于尋優(yōu)以及收斂[14]，默認(rèn)人工魚群進(jìn)行覓食操作，用nra表示跳轉(zhuǎn)因子，人工魚群通過(guò)nra次覓食操作后轉(zhuǎn)化為追尾操作以及聚群操作。

1.3.1 自適應(yīng)擁擠度因子以及自適應(yīng)視覺(jué)范圍

人工魚群法的視覺(jué)范圍過(guò)大以及過(guò)小時(shí)，分別有利于全局尋優(yōu)以及局部尋優(yōu)。將視覺(jué)范圍設(shè)置為先大后小，提升人工魚群法的計(jì)算效率。利用擁擠度因子求解最小值問(wèn)題，設(shè)置擁擠度因子較小[15]，令人工魚個(gè)體較分散；計(jì)算后期時(shí)，設(shè)置較大的擁擠度因子，聚集人工魚至最優(yōu)點(diǎn)，完成擁擠度因子以及視覺(jué)范圍自適應(yīng)，可得公式如下：

(7)

式中，V(k)與μ(k)分別表示視覺(jué)范圍及其自適應(yīng)調(diào)整因子；δ(k)與β(k)分別表示擁擠度因子及其自適應(yīng)調(diào)整因子。用j表示調(diào)整次數(shù)，可得視覺(jué)范圍以及擁擠度因子自適應(yīng)調(diào)整公式如下：

(8)

(9)

利用以上公式實(shí)現(xiàn)覓食操作視覺(jué)范圍的自適應(yīng)調(diào)整，令視覺(jué)范圍在追尾操作以及聚群操作中維持不變。

1.3.2 改進(jìn)人工魚群法

利用改進(jìn)人工魚群法實(shí)現(xiàn)機(jī)器人路徑規(guī)劃具體流程如下：

(1)參數(shù)初始化。用V與N表示視覺(jué)范圍以及魚群規(guī)模，M與T表示算法迭代次數(shù)以及操作選擇嘗試次數(shù)，s=0與δ(0)分別表示人工魚個(gè)體移動(dòng)步數(shù)以及擁擠度因子初值，lengbest=∞與n=0分別表示最優(yōu)路徑長(zhǎng)度以及次數(shù)計(jì)數(shù)，nra與pathk分別表示跳轉(zhuǎn)因子以及路徑規(guī)劃表，pathbest表示所需獲取的機(jī)器人最優(yōu)行駛路徑。

(2)將路徑起點(diǎn)gbegin添加至路徑規(guī)劃表pathk內(nèi)。

(3)人工魚個(gè)體k滿足s=nra時(shí)，形成隨機(jī)數(shù)ra=rand(2)；ra=0與ra=1時(shí)，分別執(zhí)行群聚操作以及追尾操作；s≠nra時(shí)，令該人工魚個(gè)體實(shí)施覓食操作。

(4)設(shè)置k=k+1，當(dāng)k=N時(shí)，令人工魚群內(nèi)全部人工魚個(gè)體前進(jìn)。設(shè)置s=s+1，觀察目標(biāo)點(diǎn)gend處是否存在人工魚，觀察結(jié)果為存在時(shí)，設(shè)置k=0，將此時(shí)路徑長(zhǎng)度lengk輸出。輸出路徑長(zhǎng)度小于最佳路徑長(zhǎng)度時(shí)，此時(shí)所輸出路徑更新為最佳路徑，此時(shí)pathk輸出為pathbest，進(jìn)行步驟(5)；否則轉(zhuǎn)回至步驟(3)。

(5)設(shè)置n=n+1，當(dāng)?shù)螖?shù)滿足所設(shè)置次數(shù)時(shí)，終止改進(jìn)人工魚群法計(jì)算，否則轉(zhuǎn)回至步驟(2)。

2 實(shí)例分析

為驗(yàn)證所研究方法對(duì)于機(jī)器人路徑規(guī)劃的有效性，建立大小為100 m×100 m的二維環(huán)境，設(shè)置不同場(chǎng)景環(huán)境地圖共八幅作為測(cè)試環(huán)境地圖，八幅環(huán)境地圖起始點(diǎn)坐標(biāo)以及柵欄線數(shù)量如表1所示。

表1 機(jī)器人場(chǎng)景地圖設(shè)置

統(tǒng)計(jì)采用文中方法對(duì)地圖1實(shí)施機(jī)器人路徑規(guī)劃的進(jìn)化曲線，為直觀驗(yàn)證文中方法的規(guī)劃性能，選取人工勢(shì)場(chǎng)方法(參考文獻(xiàn)[4])以及螢火蟲方法(參考文獻(xiàn)[5])作為對(duì)比方法，進(jìn)化曲線對(duì)比結(jié)果如圖1所示。

圖1 進(jìn)化曲線對(duì)比

從圖1可以看出，采用文中方法規(guī)劃?rùn)C(jī)器人路徑，僅需150次左右即可實(shí)現(xiàn)穩(wěn)定收斂；采用螢火蟲方法規(guī)劃?rùn)C(jī)器人路徑，需300次左右才可實(shí)現(xiàn)穩(wěn)定收斂；采用人工勢(shì)場(chǎng)方法規(guī)劃?rùn)C(jī)器人路徑，需350次左右才可實(shí)現(xiàn)穩(wěn)定收斂。文中方法收斂速度明顯高于另兩種方法，說(shuō)明文中方法可快速獲取全局最優(yōu)解，規(guī)劃路徑所需消耗時(shí)間低于另兩種方法。

采用三種方法對(duì)地圖1實(shí)施機(jī)器人路徑規(guī)劃的規(guī)劃結(jié)果如圖2所示。

圖2 地圖1路徑規(guī)劃結(jié)果對(duì)比

從圖2可以看出，采用三種方法均可基于地圖1的環(huán)境地圖實(shí)現(xiàn)機(jī)器人行駛路徑有效規(guī)劃。

為進(jìn)一步驗(yàn)證文中方法對(duì)機(jī)器人路徑的規(guī)劃性能，統(tǒng)計(jì)采用三種方法對(duì)8幅地圖實(shí)施機(jī)器人路徑規(guī)劃，重復(fù)10次迭代的最長(zhǎng)路徑、最短路徑以及平均路徑，對(duì)比結(jié)果如表2所示。

表2 機(jī)器人路徑長(zhǎng)度規(guī)劃結(jié)果

從表2可以看出，采用文中方法對(duì)8幅地圖實(shí)施機(jī)器人路徑規(guī)劃，規(guī)劃結(jié)果的最長(zhǎng)路徑、最短路徑與平均路徑均明顯低于另兩種方法，說(shuō)明文中方法規(guī)劃?rùn)C(jī)器人行駛路徑時(shí)，可有效獲取機(jī)器人行駛的最短路徑，可滿足路徑總長(zhǎng)度最短的目標(biāo)。相比于人工勢(shì)場(chǎng)方法以及螢火蟲方法，文中方法所規(guī)劃路徑明顯優(yōu)于另兩種方法，可有效獲取機(jī)器人最優(yōu)行駛路徑，驗(yàn)證了文中方法的收斂精度較高。采用文中方法規(guī)劃?rùn)C(jī)器人行駛路徑時(shí)，可有效解決復(fù)雜路徑規(guī)劃問(wèn)題，驗(yàn)證了文中方法的機(jī)器人路徑規(guī)劃的有效性。

統(tǒng)計(jì)采用三種方法對(duì)8幅地圖實(shí)施機(jī)器人路徑規(guī)劃，所獲取規(guī)劃路徑的安全度，對(duì)比結(jié)果如圖3所示。

從圖3可以看出，采用文中方法規(guī)劃?rùn)C(jī)器人行駛路徑，規(guī)劃不同地圖的路徑安全度均明顯高于另兩種方法。采用文中方法規(guī)劃?rùn)C(jī)器人行駛路徑可滿足路徑安全度最高的目標(biāo)。文中方法可有效解決多目標(biāo)優(yōu)化問(wèn)題，路徑規(guī)劃性能較高，同時(shí)滿足路徑總長(zhǎng)度最短以及路徑安全度最高的規(guī)劃目標(biāo)。

圖3 路徑規(guī)劃安全度對(duì)比

統(tǒng)計(jì)采用文中方法規(guī)劃?rùn)C(jī)器人行駛路徑的規(guī)劃時(shí)間，統(tǒng)計(jì)結(jié)果如表3所示。

表3 不同地圖規(guī)劃時(shí)間對(duì)比

從表3可以看出，采用文中方法規(guī)劃?rùn)C(jī)器人行駛路徑的規(guī)劃時(shí)間明顯低于另兩種方法，采用文中方法規(guī)劃8幅地圖中機(jī)器人行駛路徑的規(guī)劃時(shí)間均低于400 ms，說(shuō)明文中方法不僅可以有效規(guī)劃?rùn)C(jī)器人行駛路徑，且規(guī)劃時(shí)間短，可滿足機(jī)器人路徑規(guī)劃實(shí)時(shí)性需求。文中方法在地圖存在障礙物情況時(shí)仍具有較高的規(guī)劃性能，可獲取滿足優(yōu)化目標(biāo)的最優(yōu)路徑，驗(yàn)證了文中方法具有較高的路徑規(guī)劃有效性以及可行性。

3 結(jié)束語(yǔ)

通過(guò)改進(jìn)人工魚群法實(shí)現(xiàn)機(jī)器人路徑規(guī)劃，利用自適應(yīng)視覺(jué)范圍以及擁擠度因子，提升改進(jìn)人工魚群法的全局搜索能力。將人工魚群法中的魚群歷史最優(yōu)位置利用公示牌記錄，避免由于人工魚群法中魚群游動(dòng)造成最優(yōu)點(diǎn)有所改變，無(wú)法穩(wěn)定問(wèn)題。通過(guò)實(shí)驗(yàn)驗(yàn)證該方法可在較少迭代次數(shù)快速獲取機(jī)器人全局最優(yōu)路徑。改進(jìn)人工魚群法可提升機(jī)器人路徑規(guī)劃實(shí)時(shí)性，為機(jī)器人路徑規(guī)劃提供科學(xué)、合理的理論依據(jù)。