周蘭鳳 楊麗娜 方 華 湯漢偉

(上海應(yīng)用技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院 上海 201418)

0 引 言

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

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

1 地形通過性代價(jià)函數(shù)

1.1 滑移預(yù)測(cè)算法

滑移是基于給定地形中月球車偏移給定目標(biāo)位置的偏移程度，其定義為以給定速度、方向?yàn)闃?biāo)準(zhǔn)，月球車的實(shí)際速度、方向與給定速度、方向之差。

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

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

圖1 滑移預(yù)測(cè)算法模塊

1.2 基于滑移地圖的地形通過性代價(jià)函數(shù)

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

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

綜合ftrav(p,n)、frisky(p,n)、fguide(p,n)、fsmooth(p,n)四個(gè)函數(shù)，得到從節(jié)點(diǎn)p到節(jié)點(diǎn)n綜合代價(jià)函數(shù)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é)點(diǎn)p到節(jié)點(diǎn)n的可通行性代價(jià)函數(shù);frisky(p,n)為潛在危險(xiǎn)性代價(jià)函數(shù);fguide(p,n)為路徑導(dǎo)引性代價(jià)函數(shù)(其代價(jià)值為負(fù));fsmooth(p,n)為路徑平滑性代價(jià)函數(shù)；f1、f2、f3和f4分別為ftrav(p,n)、frisky(p,n)、fguide(p,n)和fsmooth(p,n)的權(quán)值。

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

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

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

步驟3利用式(2)進(jìn)行個(gè)體評(píng)價(jià)：

(2)

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

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

步驟5重新評(píng)價(jià)種群P(t)。

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

步驟7交叉運(yùn)算。根據(jù)設(shè)定交叉概率pc進(jìn)行交叉運(yùn)算。

步驟8變異運(yùn)算。根據(jù)設(shè)定變異概率pm進(jìn)行變異運(yùn)算。

步驟9其他運(yùn)算。根據(jù)設(shè)定的選擇機(jī)制、交叉算子和變異算子，進(jìn)行下一代繁衍。

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

圖2 技術(shù)路線

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

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

4 結(jié) 語

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