基于滑移預(yù)測(cè)的月球車(chē)路徑規(guī)劃研究

周蘭鳳 楊麗娜 方 華

(上海應(yīng)用技術(shù)大學(xué) 上海 201418)

0 引 言

月球車(chē)作為探測(cè)月球的主要工具之一，它最重要的任務(wù)就是月球路徑規(guī)劃[1]。月球環(huán)境復(fù)雜多樣使月球車(chē)路徑規(guī)劃十分困難，有效地避免陷入危險(xiǎn)地形、縮短最優(yōu)路徑長(zhǎng)度和節(jié)約路徑規(guī)劃時(shí)間是月球路徑規(guī)劃研究的重點(diǎn)。月球地形的濕度和坡度的不同，產(chǎn)生的滑移率不同，一定程度使路徑規(guī)劃產(chǎn)生偏移，有效的預(yù)測(cè)滑移有利于找到最短最優(yōu)路徑。既包含傳統(tǒng)的算法(A*算法[2]，遺傳算法[3])，也帶有一些新型的智能算法(蟻群算法[4]，神經(jīng)網(wǎng)絡(luò)算法[5]，粒子群算法[6])，經(jīng)典遺傳算法存在搜索時(shí)間長(zhǎng)、易陷入僵局、算法復(fù)雜度高的不足，無(wú)法求得最優(yōu)化路徑。

本文針對(duì)現(xiàn)有的遺傳算法容易陷入局部最優(yōu)解的問(wèn)題，綜合考慮月球地形環(huán)境信息，通過(guò)加入地形因素的滑移預(yù)測(cè)綜合通過(guò)性代價(jià)函數(shù)。使用MATLAB仿真實(shí)驗(yàn)，保持地形參數(shù)不變，調(diào)整滑移通過(guò)性函數(shù)參數(shù)，對(duì)比100次實(shí)驗(yàn)仿真結(jié)果，綜合遺傳算法進(jìn)化代數(shù)少于傳統(tǒng)遺傳算法。改進(jìn)后的遺傳算法提高了月球車(chē)路徑規(guī)劃的平滑性，縮短了路徑的長(zhǎng)度，節(jié)省了路徑規(guī)劃的時(shí)間和進(jìn)化次數(shù)。

1 綜合遺傳算法

1.1 遺傳算法路徑規(guī)劃模型建立

本文遺傳編碼采用實(shí)數(shù)編碼，遺傳算法中每1個(gè)染色體對(duì)應(yīng)1個(gè)解決方案，在路徑規(guī)劃過(guò)程中，基因是由起點(diǎn)、終點(diǎn)和路徑規(guī)劃經(jīng)過(guò)的若干中間點(diǎn)組成。如圖1所示，起點(diǎn)(X1,Y1,Z1)、終點(diǎn)(Xn,Yn,Zn)和n-2個(gè)中間點(diǎn)構(gòu)成1條攜帶從起點(diǎn)到目標(biāo)點(diǎn)的路徑規(guī)劃信息的染色體。

圖1 路徑規(guī)劃中有n個(gè)基因的1條染色體

因此，一條完整的機(jī)器人路徑(P)就可以表示為若干條線(xiàn)段的有序組合，如下式所示：

P=∑Pi

(1)

式中：Pi表示第i段直線(xiàn)段的矢量表示。

1.2 初始種群的生成

本文中一條染色體由n個(gè)坐標(biāo)點(diǎn)組成，即一條可通過(guò)性的路徑，也稱(chēng)這個(gè)路徑為一條染色體。從起點(diǎn)出發(fā)，隨機(jī)選擇可通過(guò)性的鄰節(jié)點(diǎn)，取其坐標(biāo)加入染色體中，依次循環(huán)，直到找到終點(diǎn)結(jié)束。重復(fù)上面操作，達(dá)到初始目標(biāo)種群數(shù)量，終止循環(huán)。

1.3 遺傳操作

遺傳算法是一種仿生的全局優(yōu)化概率搜索的自適應(yīng)算法[7]。其算法結(jié)構(gòu)設(shè)計(jì)需要預(yù)設(shè)的參數(shù)有：初始種群數(shù)量、最大進(jìn)化迭代數(shù)、交叉概率和變異概率等。 算法過(guò)程包括選擇、交叉、變異三個(gè)階段。將遺傳算法應(yīng)用到路徑規(guī)劃規(guī)程的問(wèn)題中，固定參數(shù)的交叉概率和變異概率適應(yīng)算法可以更好地找到最優(yōu)路徑[8]，通過(guò)不斷的迭代，最終得到問(wèn)題最優(yōu)解。

本算法采用優(yōu)勝劣汰選擇策略，即用部分優(yōu)秀個(gè)體，根據(jù)一定策略實(shí)時(shí)替換部分低劣個(gè)體[9]，保持個(gè)體的最優(yōu)化。

(1) 交叉操作是遺傳學(xué)中基因重組的重要過(guò)程，也是遺傳算法產(chǎn)生新個(gè)體的重要途徑[10]。本文采用部分映射方式進(jìn)行染色體的交叉操作，生成兩個(gè)隨機(jī)數(shù)m、n，將x、y染色體位于m和n之間的基因片段互換。交叉概率公式為：

(2)

式中：Pc表示動(dòng)態(tài)路徑規(guī)劃中交叉概率；Pcmax表示交叉概率的最大值；Pcmin表示交叉概率的最小值；Fmax表示最大適應(yīng)度值；Fmin表示最小適應(yīng)度值；Fc表示兩個(gè)要交叉?zhèn)€體中較大的適應(yīng)度值。

(2) 變異操作類(lèi)似遺傳學(xué)中的基因突變，更新過(guò)程中一條染色體上的點(diǎn)坐標(biāo)發(fā)生隨機(jī)變化，即產(chǎn)生變異個(gè)體。變異概率公式為：

(3)

式中：Pm表示動(dòng)態(tài)路徑規(guī)劃中變異概率；Pmmax表示變異率的最大值；Pmmin表示變異概率的最小值；Fmax表示最大適應(yīng)度值；Fmin表示最小適應(yīng)度值；Fm表示要變異個(gè)體的適應(yīng)度值。

2 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)作為評(píng)判種群中個(gè)體的存活率的標(biāo)準(zhǔn)之一，依據(jù)目標(biāo)函數(shù)而確定，路徑規(guī)劃過(guò)程中，適應(yīng)度函數(shù)的值越大越好。在本文路徑規(guī)劃中路徑最短和進(jìn)化代數(shù)最小是首要目標(biāo)。除此之外，本文還加入了地形評(píng)估綜合通過(guò)性代價(jià)函數(shù)。地形評(píng)估綜合通過(guò)性代價(jià)函數(shù)是綜合了地形的一些主要因素，如階梯障礙、地形粗糙程度、坡度等，同時(shí)還加入了最主要的滑移因素，從而在滑移預(yù)測(cè)的基礎(chǔ)上形成了地形評(píng)估綜合通過(guò)性代價(jià)函數(shù)。該函數(shù)可以準(zhǔn)確描述地形上兩點(diǎn)之間的綜合通過(guò)能力。這里將上述地形評(píng)估綜合通過(guò)性代價(jià)函數(shù)f(p,n)，并入遺傳算法的適應(yīng)度函數(shù)，采用綜合遺傳算法進(jìn)行路徑規(guī)劃。

設(shè)置節(jié)點(diǎn)p到節(jié)點(diǎn)n的基因片段的地形綜合代價(jià)函數(shù)如下：

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

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

(4)

式中：ftrav(p,n)為從節(jié)點(diǎn)p到節(jié)點(diǎn)n的可通過(guò)性代價(jià)函數(shù)(一般取值為0或1)；frisky(p,n)為潛在危險(xiǎn)性代價(jià)函數(shù)；fguide(p,n)為綜合考慮了地形的角度和坡度等因素的指導(dǎo)性路徑代價(jià)函數(shù)，它與地形的坡度角度有關(guān)；fsmooth(p,n)是描述路徑平滑程度的代價(jià)函數(shù)，取值為固定常數(shù)值f1、f2、f3、f4分別為ftrav(p,n)、frisky(p,n)、fguide(p,n)和fsmooth(p,n)的權(quán)值，一般將它們?nèi)橥还潭ǖ某?shù)值。

綜上，在滑移預(yù)測(cè)的基礎(chǔ)上形成了地形評(píng)估綜合通過(guò)性代價(jià)函數(shù)f(p,n)，將它與遺傳算法融合，改變其適應(yīng)度函數(shù)，構(gòu)造成一個(gè)具有滑移預(yù)測(cè)地形評(píng)估綜合通過(guò)性代價(jià)的適應(yīng)度函數(shù)f′(p,n)，本文稱(chēng)為綜合適應(yīng)度函數(shù)，公式如下：

f′(p,n)=f(p,n)+f0(p,n)

(5)

式中：f′(p,n)為綜合遺傳算法的函數(shù)的適應(yīng)度函數(shù)；f(p,n)地形綜合代價(jià)函數(shù)；f0(p,n)基于遺傳算法適應(yīng)度函數(shù)。

3 仿真實(shí)驗(yàn)

基于MATLAB 2014環(huán)境下建立虛擬三維地形環(huán)境，虛擬三維空間抽象為網(wǎng)格或柵格，然后設(shè)置參數(shù)，如路徑中的起點(diǎn)、終點(diǎn)、高度以及初始種群的數(shù)量。本次實(shí)驗(yàn)設(shè)置種群個(gè)數(shù)30，最大進(jìn)化迭代次數(shù)200。從圖2可以看出，該三維遺傳算法路徑規(guī)劃，比二維的柵格模型更直觀有效。

圖2 基于遺傳算法的三維模型路徑規(guī)劃圖

3.1 遺傳算法與綜合遺傳算法實(shí)驗(yàn)對(duì)比

本文遺傳算法和綜合遺傳算法(簡(jiǎn)稱(chēng)IGA)一次進(jìn)化代數(shù)及綜合適應(yīng)度變化圖如圖3、圖4所示。從圖3可以看出，基本遺傳算法進(jìn)化到10代左右就進(jìn)入了局部最優(yōu)解，50代之后更新最優(yōu)解，140代得到1次實(shí)驗(yàn)最優(yōu)解，綜合適應(yīng)度值為130。從圖4可以看出，進(jìn)化代數(shù)20次時(shí)得到1次試驗(yàn)最優(yōu)解，綜合適應(yīng)度值為125，一定程度上縮短了路徑規(guī)劃時(shí)間，提高了工作效率。

圖3 遺傳算法

圖4 綜合遺傳算法

為了進(jìn)一步證明算法的合理性，規(guī)避偶然因素對(duì)算法的影響，對(duì)兩種路徑規(guī)劃算法分別實(shí)驗(yàn)100次，統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果如表1所示?？梢钥闯?，綜合遺傳算法的平均最大路徑比遺傳算法最大路徑縮短了34.7%、平均適應(yīng)度值提高了12.4%、平均進(jìn)化代數(shù)縮小了49.2%。

3.2 改進(jìn)蟻群算法與綜合遺傳算法對(duì)比

通過(guò)設(shè)置相同參數(shù)的滑移預(yù)測(cè)函數(shù)和地形通過(guò)性代價(jià)函數(shù)，使用改進(jìn)蟻群算法和綜合遺傳算法各實(shí)驗(yàn)n次，各隨機(jī)抽取兩種算法的6次試驗(yàn)進(jìn)行對(duì)比，結(jié)果如表2所示。

表2 兩種算法的最大路徑長(zhǎng)度比較 km

可以看出，綜合遺傳算法比改進(jìn)蟻群算法在最大路徑長(zhǎng)度性能更加優(yōu)化。

綜合兩個(gè)實(shí)驗(yàn)得知，通過(guò)引入帶有滑移預(yù)測(cè)函數(shù)可通過(guò)性的代價(jià)函數(shù)，使得算法在尋找路徑的過(guò)程中，更加注重路徑的曲折性且避免機(jī)器人搜索產(chǎn)生無(wú)效的移動(dòng)距離。由表1可以看出，綜合遺傳算法在找到最優(yōu)的路徑的時(shí)間效率上也得到了一定的改善。因?yàn)樵诳紤]了滑移預(yù)測(cè)的地形可通過(guò)性函數(shù)的基礎(chǔ)上，綜合遺傳算法路徑規(guī)劃的搜索能力更加優(yōu)化，不會(huì)在一些不合理的路徑上繼續(xù)進(jìn)行后續(xù)的搜索。

4 結(jié) 語(yǔ)

由于遺傳算法應(yīng)用在路徑規(guī)劃問(wèn)題上，存在諸多問(wèn)題，如收斂效率低、陷入局部最優(yōu)解、復(fù)雜度高等，引入了地形綜合代價(jià)函數(shù)進(jìn)行適應(yīng)度函數(shù)設(shè)計(jì)，根據(jù)綜合適應(yīng)度值動(dòng)態(tài)獲得交叉算子和變異算子值，提出了一種綜合遺傳算法路徑規(guī)劃算法。通過(guò)實(shí)驗(yàn)仿真得知, 改進(jìn)的綜合遺傳算法在搜索最優(yōu)路徑、時(shí)間復(fù)雜度上比傳統(tǒng)遺傳算法都有了更好的優(yōu)化。這也說(shuō)明本文在算法上的創(chuàng)新應(yīng)用，在某種程度上彌補(bǔ)了傳統(tǒng)遺傳算法的缺點(diǎn)。加入可通過(guò)性滑移預(yù)測(cè)算法的遺傳算法，為月球車(chē)避障提供有效方法，一定程度上提高了路徑搜索的效率、節(jié)約了時(shí)間成本、規(guī)避了地形風(fēng)險(xiǎn)。