復雜地貌下基于地形坡度的滑移預測路徑規劃研究與實現

周蘭鳳 楊麗娜 方 華 湯漢偉

(上海應用技術大學計算機科學與信息工程學院 上海 201418)

0 引 言

路徑規劃問題主要解決點對點的問題，給定目標起點和終點，按照一定的搜索標準，尋找出最優化路徑[1-2]。除了一點對一點尋找路徑，還有更復雜的一點對多點、多點對多點的路徑規劃。在復雜地形環境中給定一系列目的地的情況下，多個起點被搜索，規劃器得出到達一個目的地的評價值。該評價值是對路徑規劃問題的一般性描述，可以適用于許多領域，包括礦井的探測[3]、在公路網驅車的最短路線[4-5]、航空氣球的導航[6]以及火星車的長距離導航[7]等。復雜地形環境下的路徑規劃問題是近年來廣泛關注的熱點問題。以往的研究中，對二維地形環境研究得較多，對三維地形環境研究得較少；對簡單化的地形研究得較多，對復雜的自然地形環境研究得較少。目前，月表地形環境下常用的機器人路徑規劃方法主要有三種：Tangent Bug算法[8]、D*算法[9-10]和遺傳算法[11-12]。上述算法均是在簡單化的地形環境(如柵格地圖)下進行路徑規劃，滑移對路徑規劃的影響已經引起了國內外學者的高度重視。

綜合上述分析，盡管有很多研究人員對滑移問題進行了研究，但沒有考慮將滑移算法與路徑規劃算法結合。因此，針對月球車行進過程中的滑移預測問題，分析地形綜合因素得到地形通過性代價函數。通過將地形通過性代價函數與路徑規劃算法有效結合，研究一種基于地形坡度、地形粗糙程度、地形松軟程度進行滑移預測的路徑規劃算法，并分析地形通過性函數對基于知識的改進遺傳算法路徑長度、收斂速度、時間復雜度和進化代數的影響。

1 地形通過性代價函數

1.1 滑移預測算法

滑移是基于給定地形中月球車偏移給定目標位置的偏移程度，其定義為以給定速度、方向為標準，月球車的實際速度、方向與給定速度、方向之差。

月表地形的多樣性增加了路徑規劃的難度，地形的坡度、粗糙程度、松軟程度、坐標位置均存在差異。本文將地形的坡度、粗糙程度、松軟度、坐標位置統稱為地形綜合因素。地形綜合因素不同滑移特質不同，將月球地形分成N種類型，不同的地形有不同的模型。地形坡度的參數差異，使得映射到滑移的非線性近似函數不同。地圖中每個柵格的滑移代價不同，輸入到地形通過性代價函數的初始值也不同。

首先，使用地形分類算法將已有的月表真實地圖分成9大類。然后，采用基于分析窗口的鄰域分析法，提取地形綜合因素。根據分類后的地形得到相應的滑移模型，即S=S(xlongit,xlateral)，xlongit、xlateral分別表示地形基于月球車方向的水平和垂直坡度。滑移預測算法模塊如圖1所示。

圖1 滑移預測算法模塊

1.2 基于滑移地圖的地形通過性代價函數

將已知的地形綜合因素轉換為數學函數，得到用來評價地形可通過性的工具——地形通過性代價函數。本文將滑移代價函數嵌入到地形通過性代價函數中，得到了基于滑移地圖的地形通過性代價函數f(p,n)，利用該函數可以判定兩點之間路徑通過性。

2 基于地形坡度的滑移預測路徑規劃算法

綜合ftrav(p,n)、frisky(p,n)、fguide(p,n)、fsmooth(p,n)四個函數，得到從節點p到節點n綜合代價函數f(p,n):

f(p,n)=f1·ftrav(p,n)+f2·frisky(p,n)+

f3·fguide(p,n)+f4·fsmooth(p,n)

(1)

式中：ftrav(p,n)為從節點p到節點n的可通行性代價函數;frisky(p,n)為潛在危險性代價函數;fguide(p,n)為路徑導引性代價函數(其代價值為負);fsmooth(p,n)為路徑平滑性代價函數；f1、f2、f3和f4分別為ftrav(p,n)、frisky(p,n)、fguide(p,n)和fsmooth(p,n)的權值。

將綜合代價函數f(p,n)嵌入到遺傳算法中，得到基于知識的改進遺傳算法，利用基于知識的改進遺傳算法進行月球車路徑規劃，具體步驟如下：

步驟1環境建模。采用三維網格進行三維建模。

步驟2可行路徑編碼。設置進化代數計數器t、進化代數上限T,隨機生成n個個體作為初始種群P(0)。

步驟3利用式(2)進行個體評價：

(2)

式中：L(an)為路徑長度；di為路徑節點i與另一節點間的距離；N為路徑an中線段的個數；fi為適應度函數；βi為節點深度的系數；C為常數。

步驟4判斷環境改變，若環境改變執行步驟5，否則轉到步驟6。

步驟5重新評價種群P(t)。

步驟6選擇運算。采取優勝劣汰的選擇機制，選擇最佳個體。

步驟7交叉運算。根據設定交叉概率pc進行交叉運算。

步驟8變異運算。根據設定變異概率pm進行變異運算。

步驟9其他運算。根據設定的選擇機制、交叉算子和變異算子，進行下一代繁衍。

步驟10判斷環境動靜。如果是動態環境，轉步驟4，否則執行步驟11。

步驟11結束條件。假如進化代數沒有達到最大進化代數上限，則代數加一，繼續執行步驟3；假如進化代數大于或者等于最大進化代數上限，則停止程序，輸出最小適應值作為最優路徑。

3 實驗結果與分析

本文對地形中可能存在的滑移進行預測，給出了滑移預測的方法以及算法流程圖，對地形的可通行性進行了分析，加入了綜合代價函數，使得路徑規劃算法的安全性和可執行性得到提高。技術路線如圖2所示。

圖2 技術路線

為了驗證基于知識的改進遺傳算法在路徑規劃的有效性，本文進行了大量的仿真實驗。實驗參數設置如下：最大進化代數T=500，群體規模M=40，交叉概率pc=1.0，變異概率pm=0.05。實驗結果如圖3所示。

基于知識的改進遺傳算法路徑規劃能夠有效地預測地形的可通行性、系統的不確定性和運動的平穩性。實驗中通過設置相同的最大進化代數、遺傳概率、群體規模，調整地形通過性函數參數，得到綜合地形參數的最優路徑長度和較小進化代數，從而提高了路徑規劃的安全性和可執行性，為路徑規劃研究提供了有效幫助。

4 結 語

本文對三維路徑的規劃問題進行了初步的探索，在基本的遺傳算法的路徑規劃的基礎上進行研究。針對基本遺傳算法在路徑規劃的過程中，存在搜索時間較長、得到的路徑質量一般等缺點，考慮在三維地形中存在節點間的地形坡度和機器人移動過程中產生的滑移問題，本文將地形通過性代價函數嵌入遺傳算法，更好地選擇路徑，有效地避開高度滑移地區，提高了復雜地形環境下路徑規劃的有效性、安全性，為月球車自主導航的研究奠定了重要的理論基礎。