染色體重組魚群算法的機器人導航路徑規劃

畢 桂

1 引言

機器人精確導航是機器人從事一切生產活動的基礎，路徑規劃是導航的首要工作[1]。合理的路徑不僅能夠提高生產效率，而且可以減少能量消耗，因此研究機器人路徑規劃具有重要的經濟意義。

機器人導航路徑規劃包括三個方面的問題：環境建模、機器人定位、路徑規劃，主要研究了環境建模和路徑規劃兩個方面的內容。機器人工作環境建模，包括柵格法[2]、矢量法等，這兩種方法存在一個共性的問題，三維向二維降維時沒有明確具體方法，所以都存在工作空間浪費的問題；機器人導航路徑規劃，當前研究熱點是使用群智能算法進行規劃，包括人工魚群算法[3]、粒子群算法[4]、人工蜂群算法[5]等，主要問題包括兩個兩面，一是算法自身性能缺陷，二是算法與導航環境模型的吻合問題。

研究了機器人導航路徑規劃問題，在環境建模方面，以機器人尺寸和障礙物三維分布為依據，提出了邊探索邊建模的方法，達到了最大程度保存工作空間的目的；在路徑規劃方面，以人工魚群算法為基礎，從參數和機理兩個方面對算法進行了改進，提高了路徑質量和規劃實時性。

2 機器人導航路徑規劃建模

2.1 環境建模

機器人工作空間由三維降為二維時，現有的柵格法、矢量法都沒有明確具體方法，為了保證機器人的絕對安全，建模時大都比較保守，浪費了工作空間。為了解決這一問題，以機器人尺寸、障礙物三維分布為依據，提出了機器人邊探索邊建模的環境建模方法。

為了對這一方法進行描述，以圓臺形障礙物為例，如圖1所示。為了保證機器人轉彎時的安全，將機器人簡化為圓柱模型，圓柱半徑為機器人最大外徑。記機器人高度為h，設置高度裕度為δ，則機器人在行走過程中使用激光探測器探測距離地面(h+δ)范圍內的障礙物，計算障礙物邊沿與圓柱中心點的平面距離，距離最小的點為障礙物投影點。如圖1所示，若使用傳統投影方法，為保證機器人的絕對安全，使用障礙物與天花板接觸面作為投影面，這明顯會造成工作空間的浪費，而使用這里方法則投影面，如圖1所示。在保證機器人安全的同時最大限度地設置了工作空間。

圖1 工作空間降維示意圖Fig.1 Workspace Dimensionality Reduction Sketch

三維空間投影為二維后，使用矢量法按照障礙物的投影形狀建立機器人工作環境模型，某一環境的建模結果，如圖2所示。

圖2 環境模型Fig.2 Environment Model

圖中：S—路徑出發點；T—目標點；P—中間點。

2.2 路徑表示與適應度函數

在二維環境中，機器人路徑由一系列二維點組成，為了簡化計算，在起始點與目標點之間作民n-1條平行于Y軸的平行線，將ST分成了n段，規劃出每條平行線的縱坐標Pi，而后將Pi點依次連接，再進行平滑處理就得到了規劃路徑，因此機器人路徑可以表示為點序列{S，P1，…，Pn-1，T}。

將路徑長度與路徑光滑度作為評價路徑優劣的指標，用于構建適應度函數。

(1)路徑長度d(p)的建立。路徑長度為各段路徑的累加和，即：

式中：yi-機器人每一步的縱坐標，Δ=dST n-平行線間的距離。

(2)路徑光滑性h(p)的建立。使用兩段相鄰路徑的夾角來評價路徑光滑性，即：

式中：β(li，li+1)—第i段路徑與第i+1段路徑的夾角。

(3)適應度函數的建立。結合以上分析，將路徑長度、路徑光滑性融合到適應度函數中，為：

式中：wd、δ—路徑長度、路徑光滑性的權值，此參數的設立一是為了調節不同優化目標在適應度函數中的重要性，二是使不同性能指標實現量級上的統一。適應度值越大說明路徑越優化。

2.3 碰撞檢測

將障礙物區分為多邊形和圓形兩種情況進行碰撞檢測：

(1)當障礙物為多邊形時，對于規劃出的某段路徑，首先判斷多邊形各頂點與路徑端點橫坐標關系，若障礙物各端點處于路徑端點之外則障礙物對此段路徑無影響；若多邊形各頂點在路徑端點內，則判斷障礙物各頂點在路徑同側還是兩側，若處于路徑同側則不發生碰撞，若處于路徑兩側則發生碰撞。

(2)當障礙物為圓形障礙物時，計算路徑上任意一點到圓心的距離，若距離大于圓半徑則路徑安全，否則路徑發生碰撞。

3 權值可調整染色體重組魚群算法

3.1 人工魚群算法基本原理

人工魚的覓食行為、聚群行為、追尾行為和隨機行為是人工魚算法的核心[6]。記人工魚最大視野為Visual，一步最大步長為Step，種群規模為N，搜索空間維度為d，人工魚擁擠度因子記為δ，位置X處的食物濃度記為Y=f(X)。

(1)覓食行為。人工魚的覓食行為是指魚群自動游向食物濃度高的區域，人工魚i在t時刻的位置記為，在其視覺范圍內隨機選擇一個位置Xj=+Visual·Ramd，式中Rand為(0，1)間的隨機數，若f(Xj)＞則人工魚朝著Xj的方向前進一步[7]，即：

若f(Xj)≤則重新選擇Xj，直到選擇次數大于最大試驗次數try_num時，仍未找到食物濃度更高點，則人工魚執行隨機行為。

(2)聚群行為。魚群的群聚行為是為了提高生存能力和覓食效率，也是一種先天行為。人工魚i在視野范圍內統計其他人工魚數目nf，計算視野范圍內人工魚中心位置，即：

式中：Xi—視野范圍內人工魚的位置。記中心處食物濃度為Yc，人工魚i處食物濃度為Yi，若Yc nf＞δ·Yi，說明中心處食物濃度高且不擁擠，則人工魚i向Xc前進一步，前進公式與式(4)一致，否則執行覓食行為。

(3)追尾行為。追尾行為是魚群在覓食過程中特有的行為，有利于人工魚朝著最優點聚集。人工魚i在視野范圍內找出適應度值最大的人工魚j，其適應度值記為Yj，若Yj nf＞δ·Yi，則說明Xj處的食物濃度高且不擁擠，則人工魚i向著人工魚j的方向前進一步，前進公式與式(1)一致，否則人工魚i執行覓食行為。

(4)隨機行為。隨機行為有利于人工魚跳出局部最優[8]，當人工魚i嘗試次數達到try_num時，在其視野內仍未找到適應度更大的點，則執行隨機行為，即：

3.2 視覺范圍和步長同步自適應方法

人工魚群算法中影響算法性能的參數包括種群規模N、擁擠度因子δ、覓食行為最大嘗試次數try_num、最大步長Step、視覺范圍Visual等。選擇對算法精度和收斂速度影響最大的視覺范圍和最大步長作為分析對象。

人工魚的視野范圍體現人工魚對環境的感知能力，最大步長體現人工魚的移動和搜索能力。大的視覺范圍使人工魚對周圍環境充分了解，若再配以較大步長就能夠使人工魚快速向較優點聚集，有利于算法收斂。算法后期，人工魚聚集在最優點附近，若仍以大的視覺范圍感知和移動，會使人工魚在最優點附近來回震蕩，而降低算法尋優精度。因此算法前期應使用較大的視覺范圍并輔以較大的步長，使算法迅速向最優點附近聚集，提高收斂速度；算法后期，應使用較小的視覺范圍并輔以較小的步長，使算法在最優點區域細致搜索，提高尋優精度。

基于以上分析，提出了視覺范圍與步長同步自適應方法，即：

式中：Visual_ada、Step_ada—自適應視覺范圍和自適應步長；fV(iter)、fS(iter)—各自的自適應函數；iter—迭代次數。指數型函數的衰減速度位于冪函數與線性函數之間，在算法初期，參數衰減速度低于冪函數，能夠保持較好的搜索能力，算法后期衰減速度低于線性函數，能夠保持較好的細致搜索能力，是一種較理想的衰減函數。因此選擇指數型函數構建參數自適應函數，為：

定義式(7)的值域為(ymin，ymax)，算法最大迭代次數為maxgen，則式(7)中的參數為：

自適應函數fs(iter)的表達式與fV(iter)完全一致，這種視覺范圍和步長同步自適應調整的方法，可以使人工魚探索能力和運動能力相互吻合，滿足算法快速收斂和細致搜索的需求。

3.3 權值可調整染色體重組方法

本節從算法機理層面進行改進。在算法執行過程中，人工魚在尋優空間密度越高，則對空間了解越充分，解的精度越高，但是人工魚密度越高，算法越復雜，對運算存儲空間的要求就越高。因此在保持人工魚種群規模不變的情況下，如何提高人工魚在最優解鄰域的密集度，同時保持種群多樣性，是從機理層面需要解決的關鍵問題。

首先提出有效人工魚的概念，將全局最優鄰域一定范圍內的人工魚定義為有效人工魚，這部分人工魚的適應度高。人工魚由初始分散狀態，通過四種行為向較優處聚集，聚集地可能為局部極值處，也可能為全局最優處，算法機理改進的目標是提高有效人工魚的密度。為了實現這一目標，提出了權值可調整染色體重組法，具體方法為：

(1)父代的選擇。記每次淘汰的人工魚數為j，每一次迭代完成后對人工魚依據適應度排序，選擇適應度最高的j條人工魚作為一組父代Xi，另外一組父Yi代在其余人工魚中隨機選取，這樣既能夠遺傳高適應度個體的優勢，又能通過隨機選擇增加種群多樣性。

(2)染色體的構造。使用十進制方法構造染色體，每條染色體由向量X與σ組成，X由尋優變量參數組成，記其維數為L，則X=(x1，x2，…，xL)，σ由各參數相應的高斯變異標準差組成，記為σ=(σ1，σ2，…，σL)。

(3)染色體重組。有性生殖通過父代基因重組產生下一代，傳統的重組方法有離散重組、中間重組、混雜重組[9，10]等，在中間重組基礎上改進，提出了權值可調節重組法。記父代染色體分別為(Xi，σi)與(Xj，σj)，權值可調整重組法為

式中：α、β—兩個父代的權重，權值可以根據問題特點和父代的適應度進行設置，使子代進化具有針對性和方向性；權值也可以隨機設置，增強進化的隨機性和突現性，增加物種多樣性。

(4)選擇與淘汰機制。依據個體適應度，從子代中選擇適應度最高的j個個體，替換父代種群中適應度最低的j個個體，模擬適者生存現象。

3.4 權值可調整染色體重組魚群算法步驟

基于以上改進，給出權值可調整染色體重組魚群算法步驟為：

(1)初始化參數，包括種群規模N、擁擠度因子δ、覓食行為最大嘗試次數try_num、最大步長Step、視覺范圍Visual、淘汰比例等；

(2)根據自適應參數調整方法計算參數，人工魚按照四種行為邏輯進行尋優，選擇適應度最高的人工魚作為更新狀態；

(3)對魚群進行適應度排序，選擇父代個體，而后進行染色體重組和自然選擇，更新魚群；

(4)當前適應度最優個體是否高于公告牌，若是則更新公告牌，否則進行下一步；

(5)判斷算法是否達到最大迭代次數或其他停止條件，若是則算法停止，否則iter=iter+1，轉入(2)。

4 算法性能驗證及機器人導航規劃

4.1 改進算法性能驗證

為了對權值可調整染色體重組魚群算法進行性能驗證，分別使用傳統魚群算法和改進魚群算法對式(8)給出的函數F1進行尋優。魚群規模N=50，視野Visual=2，最大步長Step=0.5，覓食嘗試次數try_num=10，自適應衰減函數參數ymax=2，ymin=0.01，maxgen=50，種群淘汰比例設置為20%。

函數F1曲面圖，如圖3所示。此函數在(0，0)處取得唯一極值為1，在取值范圍內還存在若干個極值點。

圖3 測試函數F1曲面圖Fig.3 Surface Plot of Measuring Function F1

圖4 迭代過程中魚群分布情況Fig.4 Fish Distribution Condition of Iteration Process

使用傳統魚群算法和改進魚群算法分別進行尋優，在過程中魚的分布情況如圖4所示。由圖4(a)可以看出，初始時刻人工魚在工作區域內分布均勻，有利于魚群充分了解此區域；當算法迭代4次時，改進魚群算法的有效人工魚數量明顯高于傳統魚群算法；當算法迭代10次時，傳統魚群算法的魚主要集中在最優值附近，但是也有相當數量的魚陷入了局部極值，圖中已使用“紅圈”標出，而改進魚群算法所有魚均集中在最優值區域，沒有陷入局部極值，以上分析充分證明了改進魚群算法的性能優勢。

4.2 機器人導航路徑規劃結果及分析

對于某(200×200)m的車間環境，使用邊探索邊建模方法，將三維空間投影到二維空間，將機器人起點設置為S(10m，10m)，目標點設置為G(190m，190m)，為了驗證參數可調整染色體重組魚群算法在機器人路徑規劃中的改進效果，分別使用改進算法與傳統魚群算法進行路徑規劃。參數設置為：魚群規模N=100，視野Visual=2，最大步長Step=0.5，覓食嘗試次數try_num=10，擁擠度δ=0.618，自適應衰減函數參數maxgen=50，淘汰比例為20%。每種算法都進行100次路徑規劃，兩種魚群算法規劃的最優路徑，如圖5所示。統計100次規劃路徑的最大值、最小值、平均值、標準差及算法耗時，結果如表1所示。

圖5 改進魚群算法與傳統算法規劃結果Fig.5 Planning Result of Improved and Traditional Algorithm

表1 兩算法規劃路徑結果對比Tab.1 Path Planning Result Comparison of the Two Algorithms

由圖5可以看出，改進魚群算法規劃的最優路徑明顯短于傳統魚群算法規劃的最優路徑，且改進算法規劃的路徑更加平滑，使機器人容易跟蹤；而傳統魚群算法規劃出的路徑為次優路徑，說明此算法陷入了局部極值而無法跳出。由表1可以看出，改進算法規劃的路徑最優值比傳統算法減少了5.01%，路徑平均值減少了7.76%，算法耗時減少了約一倍；且改進算法規劃路徑的標準差遠遠小于傳統算法，說明改進算法在路徑規劃中穩定性好。這是因為改進魚群算法引入了兩點改進，一是視覺范圍與步長同步自適應調整，兩者能夠根據算法需求同步吻合調整，既實現了快速收斂又提高了尋優精度；二是使用參數可調整染色體重組方法，在魚群尋優過程中，能夠促進魚群跳出局部極值，向全局最優區域靠近，不斷提高有效魚數量，達到提高尋優精度的目的。

5 結論

研究了機器人導航的兩個關鍵問題：環境建模與路徑規劃。在環境建模方法，提出了邊探索邊建模方法，有效保存了機器人工作區域。在路徑規劃方面，在傳統魚群算法基礎上，提出了兩點改進，一是視覺范圍與步長同步自適應調整，保證了兩者相互吻合，滿足了算法收斂和尋優需求；二是使用參數可調整染色體重組方法，使算法可以跳出局部極值，且不斷向最優值區域靠近，提高了尋優精度。