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

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

0 引 言

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

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

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

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

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

在直角坐標系XOY內建立全局環(huán)境場景，利用圓或實心多邊形表示障礙物，用Z(xz,yz)與T(xt,yt)分別表示起始點以及目標點，利用x軸以及y軸設置為連接Z與T的直線以及垂直于x軸且經過Z的直線，獲取新的環(huán)境坐標系xoy。坐標變換直角坐標系XOY內隨機點Q(X,Y)可得該點在坐標系xoy內的坐標為：

(1)

(2)

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

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

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

(1)路徑總長度最短。

(3)

式中，|qiqi+1|與num分別表示路徑段qiqi+1長度以及路徑Q內相交于障礙物的路徑段數量；inf1表示路徑Q為不可行路徑時所需施加的懲罰項。

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

(4)

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

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

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

(5)

式中，ω1表示路徑長度的權值系數，ω2表示路徑安全度的權值系數。

可依據機器人行駛場景以及路徑規(guī)劃需求實時調整權值系數[10]，獲取最優(yōu)機器人路徑規(guī)劃結果。利用改進人工魚群法求解所建立總目標函數，規(guī)劃機器人最佳行駛路徑。

1.2 人工魚群法

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

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

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

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

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

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

利用自適應擁擠度因子以及自適應視覺范圍對人工魚群法實施改進。

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

(6)

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

1.3.1 自適應擁擠度因子以及自適應視覺范圍

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

(7)

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

(8)

(9)

利用以上公式實現覓食操作視覺范圍的自適應調整，令視覺范圍在追尾操作以及聚群操作中維持不變。

1.3.2 改進人工魚群法

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

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

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

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

(4)設置k=k+1，當k=N時，令人工魚群內全部人工魚個體前進。設置s=s+1，觀察目標點gend處是否存在人工魚，觀察結果為存在時，設置k=0，將此時路徑長度lengk輸出。輸出路徑長度小于最佳路徑長度時，此時所輸出路徑更新為最佳路徑，此時pathk輸出為pathbest，進行步驟(5)；否則轉回至步驟(3)。

(5)設置n=n+1，當迭代次數滿足所設置次數時，終止改進人工魚群法計算，否則轉回至步驟(2)。

2 實例分析

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

表1 機器人場景地圖設置

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

圖1 進化曲線對比

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

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

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

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

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

表2 機器人路徑長度規(guī)劃結果

從表2可以看出，采用文中方法對8幅地圖實施機器人路徑規(guī)劃，規(guī)劃結果的最長路徑、最短路徑與平均路徑均明顯低于另兩種方法，說明文中方法規(guī)劃機器人行駛路徑時，可有效獲取機器人行駛的最短路徑，可滿足路徑總長度最短的目標。相比于人工勢場方法以及螢火蟲方法，文中方法所規(guī)劃路徑明顯優(yōu)于另兩種方法，可有效獲取機器人最優(yōu)行駛路徑，驗證了文中方法的收斂精度較高。采用文中方法規(guī)劃機器人行駛路徑時，可有效解決復雜路徑規(guī)劃問題，驗證了文中方法的機器人路徑規(guī)劃的有效性。

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

從圖3可以看出，采用文中方法規(guī)劃機器人行駛路徑，規(guī)劃不同地圖的路徑安全度均明顯高于另兩種方法。采用文中方法規(guī)劃機器人行駛路徑可滿足路徑安全度最高的目標。文中方法可有效解決多目標優(yōu)化問題，路徑規(guī)劃性能較高，同時滿足路徑總長度最短以及路徑安全度最高的規(guī)劃目標。

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

統(tǒng)計采用文中方法規(guī)劃機器人行駛路徑的規(guī)劃時間，統(tǒng)計結果如表3所示。

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

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

3 結束語

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