具有修正策略的改進NSGA－II 三維路徑規劃

封建湖，鄭寶娟，封 碩，張婷宇

（1.長安大學理學院，陜西 西安 710064；2.長安大學工程機械學院，陜西 西安 710064）

1 引言

路徑規劃是機器人定位與導航領域研究的熱點問題之一，目前的路徑規劃方法如蟻群算法，粒子群算法，蜂群算法，螢火蟲算法及混合算法等[1-3]多用于二維平面空間規劃。在復雜環境下三維空間的機器人路徑避障問題越來越受到學者們的關注。例如，文獻[4]提出了一種結合人工勢場思想的改進蟻群算法并用于三維路徑規劃，并將路徑的長度作為優化準則，但是只優化了路徑長度，實用性不高。文獻[5]提出在偏微分高程建模下蟻群算法的三維路徑規劃方法，但計算結果容易陷入局部最優。

遺傳算法根據生物進化過程的自然遺傳理論構造的隨機搜索算法，其優點是并行計算能力強，魯棒性和全局收斂性好，已經成功地應用于機器人的路徑規劃問題。對多目標的遺傳算法，文獻[6]改進了非支配排序遺傳算法（NSGA），提出了復雜度更低，更能保持種群多樣性，具有Pareto 占優的NSGA-II 算法。文獻[7]考慮路徑長度和難度，加入修正算子減少冗余路徑，從而改進NSGA-II 算法并成功應用于二維路徑規劃，取得了很好的效果。文獻[8]在二維空間中優化了路徑長度、路徑安全性和路徑平滑度，在NSGA-II 算法的基礎上加入輔助選擇算子，并證明了輔助選擇算子使算法得到的Pareto 解更優，但對冗余路徑情況和路徑能耗未做考慮。

針對以上算法的優勢和不足，嘗試基于NSGA-II 算法研究三維多目標路徑規劃，首先，構造復雜的三維曲面空間并柵格化；其次考慮路徑長度，能耗，路徑起伏等優化因子，建立多目標優化函數；最后基于文獻[7-8]的改進成果，對NSGA-II 算法進行改進，在選擇算子中加入輔助選擇算子，得到更優的Pareto 前沿解集，設計多種路徑優化的遺傳算子，加快搜索能力，使其更好地應用到路徑規劃問題上。

2 規劃空間的構造

2.1 地形構建及柵格化處理

使用柵格表示的方法，根據機器人的尺寸，將三維曲面空間離散成若干的柵格，建立笛卡爾坐標系，每個柵格都對應一個點坐標（xi，yi，zi），如圖1（a）所示。xy 代表水平地理坐標位置，z 代表地形地貌的高度（在柵格化的過程中對z 進行取整），實際應用中如果細化網格，將能逼近三維地形地貌。采取降維的思想，將三維地形表面分解為二維平面和高度變化的集合，從而簡化三維空間的搜索難度，加快搜索能力。灰色代表有高度信息的自由柵格，黑色代表障礙柵格，障礙物數目，位置，大小已知，離散化后將高度信息z 標注于相應柵格上，反應機器人在經過不同柵格時的高度變化，如圖1（b）所示。

圖1 建立的三維規劃空間Fig.1 The Established Three-Dimensional Planning Space

2.2 適應度函數的建立

文獻[9]用柵格高度值代表能耗，對上下坡能耗變化不同未分類討論，有一定缺陷。在三維路徑規劃中實現的目標有：在環境靜態、地圖有界、障礙物已知、起點和終點已知的條件下，機器人行走路徑長度最短，上下坡總能耗最小，減少上下坡的起伏，且每條路徑都規避障礙物。

其中，gi路徑中第i 段相鄰兩點的能耗值，為了更加貼近真實設備上下坡所耗能量不同的狀況，將上坡和下坡進行差異化分析，簡單起見，文中只對上坡動作和下坡動作乘以不同的權重系數，考慮到下坡省力，上坡費力，對上坡和下坡分段處理：

（4）障礙物的規避采用約束條件來表達，將障礙物點的集合記為O=（o1，o2，…ok）則規劃的路徑點pi不能取集合O 中的點，且線段pipi+1不能穿過點集O。

3 改進NSGA-II 的多目標路徑規劃

3.1 傳統多目標遺傳算法

針對以上規劃空間及優化目標函數，選擇NSGA-II 算法來解決多目標函數路徑優化問題，對多目標函數的優化，傳統的遺傳算法是將多目標函數加權組合成單目標函數來處理，需要不斷調整權重參數來得到近似最優解，往往不能很好地解決實際問題。智能的多目標優化算法是找到Pareto 占優解，NSGA-II 算法是目前解決多目標遺傳算法影響大，應用范圍廣的優化算法之一[10]，突出優點是快速非支配排序的方法，且得到的解具有多樣性和均勻性。文獻[7-8]將NSGA-II 算法成功地應用到了二維路徑規劃問題上，然而對三維柵格路徑規劃問題的應用比較少。基于文獻[7-8]的研究成果，考慮路徑規劃結果的連續性，快速收斂性和Pareto 最優，對NSGA-II 算法進行改進，改進的遺傳算法包括以下編碼方式和遺傳算子的設計，其中在具有非支配排序的選擇算子中加入輔助決策算子及修正算子的設計頗為關鍵。

3.2 改進NSGA-II 算法

3.2.1 編碼及初始種群的產生

m×m×m 規格地圖下，采用柵格序號編碼，并與坐標法相結合。每一個柵格降維后分解為（xi，yi）和高度zi的集合。對降維后的空間從左到右，從下到上為每個柵格編號，每個坐標（xi，yi）對應一個編號N。

在初始種群生成時，對當前柵格，有8 種可選擇的方向，當柵格位于四頂角或者邊界時，可選擇的柵格分別為3 個和5 個。根據當前點和目標點的位置關系，對可供選擇的柵格，以概率隨機選擇一個自由柵格作為下個路徑點，以此直到到達路徑終點。用這種方式產生的初始種群保持了有效性，連續性和多樣性，而且避免了路徑反復出現和原地轉圈。

3.2.2 選擇算子

NSGA-II 算法的選擇算子采用精英策略，能很好地保持種群的多樣性，但存在如文獻[8]所證明的缺陷。當有三個優化目標時，若第三個目標函數不是絕對重要，將其中兩個目標作為優化函數，第三個目標作為輔助選擇算子，所得到的優化結果更能保持種群的多樣性，比三個目標所得到的Pareto 前沿分布更優[8]。建立的第二個目標函數能耗最小可間接反映路徑的起伏，所以路徑起伏的優化不是絕對重要的，對NSGA-II 選擇策略進行了一定的修改：對于在選擇算子中比較的兩條路徑的優先級時，先檢查相同級別的路徑對應的高度值f3，其次再比較擁擠距離值。這樣得到的路徑既能保持路徑最短，又能減少爬坡起伏及控制爬坡高度。具體選擇關鍵過程為：

（1）種群Rt進行非支配排序，求解出一系列非支配集Zi，計算個體擁擠度及適應度f3；

（2）經過非支配排序后的非支配集Z1所包含的個體是整個Rt中最好的個體，將Z1放到新的父代種群Pt+1中；

（3）判斷種群Pt+1的規模是否小于N，若是，則繼續向Pt+1中添加下一級的非支配集Z2，直到添加到非支配集Zn時，種群規模超出N，則對Zn中每個個體比較f3，使f3值小的優先選擇，如果f3相等，再對Zn中每個個體比較擁擠度距離，使擁擠度距離高的種群獲勝，取前｛num（Zn）-（num（Pt+1）-N）｝個個體，使種群Pt+1規模達到N。

3.2.3 交叉、變異、刪除算子

選擇一點交叉方法，隨機選擇一個交叉點，交換掉兩個父代交叉點之后的路徑結點，產生新的子代。

在移動機器人的路徑規劃中，產生的路徑均為連續路徑，出于防止高變異概率造成個體優越性破壞和種群退化的目的，選擇很小的突變概率進行擾動，取pm=0.01。變異的過程為：隨機選擇一個變異位置，隨機產生一個無障礙柵格的編號，代替原來位置的編號。

刪除算子的作用是用來判斷所產生的路徑是否有環路，如果路徑產生的序號有重復的點，則刪除兩個重復點之間的所有路徑段及一個重復點。

3.2.4 修正算子

在NSGA-II 算法的基礎上，提出對路徑中對角，水平，垂直方向的修正算子，考慮生成的路徑產生如圖2 圈黑的非環路冗余，為了避免機器人繞路和能量的消耗，可用箭頭所指的兩個對角路徑點來代替。現僅對對角修正算子作出說明。

圖2 對角冗余的修正算子示例Fig.2 An Example of a Modified Operator for Diagonal Redundancy

（1）路徑中隨機選擇一個狀態點pi；

（2）將pi的所有斜對角點記為Dpi；

（3）遍歷路徑中的點S；

（4）若S 在Dpi中，則移除S 和pii中所有的路徑點。

整個進化過程，如圖3 所示。

圖3 算法流程圖Fig.3 The Flowchart of Algorithm

4 仿真分析

采用MATLAB 對上述算法進行仿真測試，實驗分別在柵格（10×10）規格，（20×20）規格環境測試，各個參數設定，如表1 所示。

表1 參數設置Tab.1 Preferences

4.1 修正算子有效性驗證

實驗在10×10 規格柵格環境下，忽略高度信息，只考慮路徑最短，建立二維路徑規劃問題來驗證修正算子的有效性，參數設置如表1 中10×10 規格環境。兩種算法最優路徑的收斂曲線對比，如圖4（a）所示。圖4（b）為兩種算法尋得的最優路徑結果，不加入修正算子時在進化第27 代達到收斂，而加入修正算子使算法在進化第10 代達到了收斂，相比之下修正算子使迭代次數減少了約63%，加入修正算子能明顯提高算法的收斂性，驗證了修正算子的有效性。

圖4 修正算子驗證結果Fig.4 Results of Modify Operator Validation

4.2 10×10 規格地圖

加入高度信息，為了驗證所提出改進遺傳算法的有效性，與文獻[9]選擇相同的機器人工作環境。用提出的改進的NSGA-II 算法來解決文獻[9]所構造的規劃問題，參數設置如表1 中10×10 規格環境。改進算法所得到的Pareto 前沿分布集，如圖5 所示。可以看出，改進算法具有不同的Pareto 前沿解集。前沿集中的一個路徑和文獻[9]所得的最優路徑結果對比，如圖6 所示。兩種算法所得到的最優路徑信息對比，如表2 所示。兩種算法所得到的路徑長度值相等時路徑所消耗的能量明顯低于文獻[9]，且得到的前沿路徑所有的能耗值均低于文獻[9]的最優路徑能耗，如圖6 所示。可見將多目標加權處理成單目標所得到的結果往往不能Pareto 占優，且無法衡量結果是否最好。通過表2 發現得到的Pareto 前沿路徑在權衡能耗最小和路徑最短的條件下做出了很好的折中。

圖5 Pareto 前沿分布1Fig.5 Pareto Optimal Fronts Distribution 1

圖6 路徑結果對比Fig.6 Comparison of Routs

表2 兩種算法最優解對比Tab.2 Comparison of Optimal Solutions Between Two Algorithms

4.3 20×20 規格地圖

在（2）的基礎上加大柵格環境和障礙物個數進行仿真測試，參數設置如表1 中20×20 規格環境。結果顯示當加大柵格數目時，算法依然能找到Pareto 最優路徑，而且具有多個Pareto 前沿分布解，如圖7 所示。具有很好的實際應用價值。前沿解集中的其中一個路徑結果，如圖8 所示。

圖7 Pareto 前沿分布2Fig.7 Pareto Optimal Fronts Distribution 2

圖8 路徑尋優結果Fig.8 Result of Path Optimization

5 結論

針對有障礙的三維空間機器人路徑規劃問題考慮路徑最短，能耗最小，起伏最少，構建了多目標優化函數，提出了一種改進的NSGA-II 算法，對算例進行優化分析，結果表明：（1）修正算子的加入能有效提高最優路徑的收斂代數，使迭代次數減少了約63%。（2）多目標加權處理成單目標得到的結果往往不能Pareto 占優，且需要人為不斷調整權重，實用性不高。改進的NSGA-II 算法具有多個Pareto 前沿分布解，且分布均勻，比傳統算法結果更占優。（3）加大規劃空間規模和障礙物時改進的算法依然能找到多個Pareto 最優路徑，驗證了算法在不同復雜度的環境均具有較好的適應能力。