周蘭鳳 楊麗娜 方 華 湯漢偉

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

0 引 言

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

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

1 地形通過性代價函數

1.1 滑移預測算法

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

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

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

圖1 滑移預測算法模塊

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

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

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

綜合ftrav(p,n)、frisky(p,n)、fguide(p,n)、fsmooth(p,n)四個函數，得到從節(jié)點p到節(jié)點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)為從節(jié)點p到節(jié)點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)嵌入到遺傳算法中，得到基于知識的改進遺傳算法，利用基于知識的改進遺傳算法進行月球車路徑規(guī)劃，具體步驟如下：

步驟1環(huán)境建模。采用三維網格進行三維建模。

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

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

(2)

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

步驟4判斷環(huán)境改變，若環(huán)境改變執(zhí)行步驟5，否則轉到步驟6。

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

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

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

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

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

步驟10判斷環(huán)境動靜。如果是動態(tài)環(huán)境，轉步驟4，否則執(zhí)行步驟11。

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

3 實驗結果與分析

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

圖2 技術路線

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

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

4 結 語

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