徐 煒 周蘭鳳* 章民融

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

0 引 言

路徑規(guī)劃問題，即按一項(xiàng)或多項(xiàng)優(yōu)化規(guī)則，如最小工作代價(jià)、最短行走路程、最短行走時(shí)間等，尋找一條從起始狀態(tài)到達(dá)目標(biāo)狀態(tài)的最優(yōu)無碰路徑[1]。復(fù)雜地形下的路徑規(guī)劃是近幾年研究的熱點(diǎn)問題。目前，研究路徑規(guī)劃的算法主要有D*算法[2-3]、遺傳算法等，這些算法相對來說單一且僅針對于簡單的地形，在復(fù)雜的三維地形中無法適用。神經(jīng)網(wǎng)絡(luò)算法在最近幾年的研究中逐漸迅速并且適用于解決復(fù)雜的地形輸入問題[4]，禹建麗等[5]通過對神經(jīng)網(wǎng)絡(luò)在路徑規(guī)劃上的應(yīng)用，解決了最短路徑規(guī)劃問題。但這些算法對于起伏地勢較大的三維特殊地形中，依舊缺少對起伏地勢以及障礙物的考慮。

綜上所述，雖然很多人都對路徑規(guī)劃問題有所研究，但是，并沒有考慮在復(fù)雜地形下的起伏地勢以及障礙物對路徑規(guī)劃的影響[6-7]。也就是說，諸多的路徑規(guī)劃算法與具體的真實(shí)復(fù)雜地形存有脫節(jié)的現(xiàn)象[8]。本文利用了當(dāng)下研究較為流行的神經(jīng)網(wǎng)絡(luò)算法，并且考慮到復(fù)雜的三維地形環(huán)境中地形以及障礙物等問題，將神經(jīng)網(wǎng)絡(luò)與地形函數(shù)模型相結(jié)合，為自主導(dǎo)航研究奠定了基礎(chǔ)。

1 地形函數(shù)模型

1.1 地形預(yù)處理

導(dǎo)航車在復(fù)雜的三維地形行進(jìn)過程中，要避開障礙物以及起伏變化較大的地勢，以達(dá)到最優(yōu)的路徑[9-10]。由于地勢的復(fù)雜性，無法對其直接進(jìn)行計(jì)算，故地形的預(yù)處理是進(jìn)行建模的第一步。

為此，本文在研究中將高低起伏的地勢轉(zhuǎn)化為規(guī)則的圓柱體，將障礙物轉(zhuǎn)化為球體，便于導(dǎo)航車在行進(jìn)過程中避開這些障礙物，尋找到一條最優(yōu)的路徑。規(guī)則幾何體的函數(shù)形式如下：

(1)

式中：x0、y0和z0表示地勢起伏以及障礙物的中心點(diǎn)坐標(biāo)；a、b和c是常數(shù)用來控制障礙物的大??；x、y和z用來表示地形的三維坐標(biāo)值。式(1)可以根據(jù)不同的p、q和r值來描述不同的幾何圖形。當(dāng)p=q=r=1時(shí)，表示的是一個(gè)球體，即此時(shí)的路徑需要避開的是障礙物；當(dāng)p=q=1且r>1時(shí)，表示的是一個(gè)圓柱體，即此時(shí)的路徑需要避開的是高低起伏的地勢。

1.2 地形函數(shù)

地形函數(shù)模型旨在導(dǎo)航車行進(jìn)的過程中，為避開高低起伏的地勢以及障礙物而建立的一種易于處理的模型。不同的地勢一定具有不同的函數(shù)模型。本文主要運(yùn)用流函數(shù)的基本思想，即將從障礙物周圍的流動現(xiàn)象中學(xué)習(xí)，地形被視為邊界條件，通過使用流體力學(xué)計(jì)算規(guī)劃區(qū)域中的流場分布來建立。流動控制方程如下：

▽2Φ=0

(2)

式中：▽是微分符號，此方程式為拉普拉斯方程式，Φ為規(guī)則幾何體的函數(shù)形式，即式(1)。

流動控制方程的邊界條件之一是在障礙物表面即：

(3)

式中：n表示障礙物表面向外的單位法向量。

邊界條件之二是在無限遠(yuǎn)處：

▽Φ=μ∞

(4)

式中：μ∞表示導(dǎo)航車在行進(jìn)過程中的速度。將式(1)的規(guī)則幾何體的函數(shù)形式分別代入式(2)、式(3)和式(4)求解，將得到一個(gè)適用于避開障礙物和起伏地勢的地形函數(shù)模型。

2 連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)

Hopfield神經(jīng)網(wǎng)絡(luò)是一種遞歸型、結(jié)合存儲系統(tǒng)和二元系統(tǒng)的神經(jīng)網(wǎng)絡(luò)，由Hopfield等采用模擬電子線路實(shí)現(xiàn)，并成功地求解了優(yōu)化組合問題中一些最具有代表性的問題，也開啟了信息處理中運(yùn)用人工智能技術(shù)的新方法。該網(wǎng)絡(luò)中神經(jīng)元的激活函數(shù)為連續(xù)函數(shù)，因此，也被稱為連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)[11-12]。在連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)中，各神經(jīng)元一般采用并行工作方式，輸入和輸出均為模擬量。

在生物系統(tǒng)中，由于神經(jīng)元i的細(xì)胞膜輸入電容ci、跨膜電阻Ri和確定阻抗Rij=Wij-1,Wij為i與j之間的權(quán)重，狀態(tài)Ui會滯后于其他神經(jīng)元的瞬時(shí)輸出Vi，所以神經(jīng)元的輸出將是0、1之間的連續(xù)值，而不是離散模型的二值。連續(xù)性Hopfield神經(jīng)網(wǎng)絡(luò)中，組成電路的基本器件如圖1所示。

圖1 Hopfield神經(jīng)網(wǎng)絡(luò)的電路基本器件圖

其主要由以下幾部分組成：

(1) 帶有同向和反向輸出端的運(yùn)算放大器，且具有飽和非線性特性的S型輸入輸出關(guān)系，即：

(5)

式中：U0相當(dāng)于輸入信號的放大倍數(shù)，也控制激活函數(shù)的斜率，當(dāng)U0趨近于0時(shí)，f就成為二值閾值函數(shù)。

(2) 放大器的輸入電容Ci和輸入電阻Ri的乘積為神經(jīng)元的時(shí)間常數(shù)，該時(shí)間常數(shù)表示了神經(jīng)元的動態(tài)特性。

(3) 網(wǎng)絡(luò)神經(jīng)元連接的權(quán)值：

(6)

式中：Rij為連接電阻。

(4) 外加偏置電流Ii相當(dāng)于神經(jīng)元的閾值θi，整個(gè)電路系統(tǒng)的動態(tài)方程式為：

(7)

若式(7)有解，那么系統(tǒng)狀態(tài)的變化最終會無限接近穩(wěn)定。在對稱連接和無自反饋的狀態(tài)下，可定義系統(tǒng)的能量函數(shù)為：

(8)

式中：T代表網(wǎng)絡(luò)神經(jīng)元連接的權(quán)值；V和I分別表示某個(gè)神經(jīng)元的電壓和電流；f常取雙曲線正切函數(shù)。穩(wěn)態(tài)時(shí)，可忽略最后的積分項(xiàng)得到：

(9)

至此，有了Hopfield神經(jīng)網(wǎng)絡(luò)的模型的狀態(tài)方程和能量函數(shù)，可以來嘗試解決三維地形下的路徑規(guī)劃問題。

3 三維地形建模

為有效地建立三維地形的模型，本文在研究中引入高度圖作為輸入數(shù)據(jù)的方法。高度圖是創(chuàng)建三維地形的標(biāo)準(zhǔn)方法，它是一個(gè)二維數(shù)組值[13]。數(shù)組中的每個(gè)值表示該值位置處的地形高度[14]。例如，圖2顯示了高度圖的單元格和每個(gè)單元格的值，而圖3顯示了該地圖生成的地形線框視圖。

圖2 高度圖的單元格和值

圖3 生成的地形的線框視圖

三維地形的建立需要基于高度圖并且迭代地使用不同的算法。本文選擇山丘算法構(gòu)建三維地形模型。其基本算法步驟如下：

步驟1將所有高度值初始化為零；

步驟2在地形上或附近選擇隨機(jī)點(diǎn)，以及在某個(gè)預(yù)定的最小值和最大值之間的隨機(jī)半徑，選擇這個(gè)最小值和最大值將使地形變得粗糙或者光滑；

步驟3在具有給定半徑的點(diǎn)的中心上升起山丘；

(一)離合詞“A了個(gè)B”的概念重組之后表示的是動詞的量，表次數(shù)；而網(wǎng)絡(luò)詞“A了(嘞)個(gè)B”則是純形式，概念重組之后仍繼承的是指向決定體的意義，只是因?yàn)橐艄?jié)的增多而使得語氣緩和，風(fēng)格幽默。如“出了個(gè)丑”表示的是出丑的量，一次。又如：

步驟4返回步驟2，并根據(jù)需要重復(fù)迭代多次，選擇的迭代次數(shù)將影響地形的外觀；

步驟5規(guī)范地形。

至此，三維地形的模型建立完成。將運(yùn)用此三維地形進(jìn)行路徑規(guī)劃算法的研究。

4 三維地形下路徑規(guī)劃算法

連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)在處理數(shù)據(jù)時(shí)是同步進(jìn)行的。若將一個(gè)路徑規(guī)劃問題的目標(biāo)函數(shù)轉(zhuǎn)換成連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)的能量函數(shù)，把問題的變量對應(yīng)于網(wǎng)絡(luò)中神經(jīng)元的狀態(tài)，那么，連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)就能夠很好地應(yīng)用于路徑規(guī)劃問題。并且，將地形函數(shù)模型考慮進(jìn)能量函數(shù)內(nèi)，那么，Hopfield神經(jīng)網(wǎng)絡(luò)就能夠更好地處理三維地形的障礙物以及起伏地勢的問題。當(dāng)網(wǎng)絡(luò)的神經(jīng)元狀態(tài)趨于平衡點(diǎn)時(shí)，網(wǎng)絡(luò)的能量函數(shù)也趨于最小值，網(wǎng)絡(luò)由初狀態(tài)向穩(wěn)態(tài)收斂的過程就是路徑的最優(yōu)解過程。

本文設(shè)計(jì)了Hopfield神經(jīng)網(wǎng)絡(luò)的能量函數(shù)與目標(biāo)函數(shù)相對應(yīng)，因此網(wǎng)絡(luò)的能量函數(shù)包含目標(biāo)項(xiàng)及約束項(xiàng)兩部分，將網(wǎng)絡(luò)的能量函數(shù)定義為：

(10)

式中：V表示神經(jīng)元的輸出；N表示神經(jīng)元數(shù)量；A、B、C和D為權(quán)值。

除此之外，為了能夠更好地處理三維地形中的障礙物以及起伏地勢的問題，必須加入地形函數(shù)模型信息：

(11)

由式(11)和式(12)兩部分的結(jié)合可以得到路徑規(guī)劃問題的網(wǎng)絡(luò)能量函數(shù)：

(12)

具體的算法步驟如下：

步驟1創(chuàng)建三維地形圖；

步驟2初始化網(wǎng)絡(luò)；

計(jì)算Vxi(t)；

步驟5計(jì)算網(wǎng)絡(luò)能量函數(shù)E；

步驟6若迭代次數(shù)p>10 000，則結(jié)束程序,否則,p=p+1,返回步驟3。

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

實(shí)驗(yàn)在Unity 2018中進(jìn)行。首先使用山丘算法建立三維地形圖，如圖4所示。其中，規(guī)則幾何形狀代表行進(jìn)路徑中的障礙物，其余部分是起伏地形。未對起伏的地形和障礙物進(jìn)行處理之前，使用Hopfield神經(jīng)網(wǎng)絡(luò)的路徑如圖5所示，可以看出此路徑不能避開起伏的地形和障礙物。然后，利用地形函數(shù)模型對起伏的地形和障礙物進(jìn)行處理，且并入Hopfield神經(jīng)網(wǎng)絡(luò)算法中進(jìn)行路徑規(guī)劃的路徑如圖6所示，可以看出該路徑有效地避開了起伏的地形和障礙物。

圖6 加入地形函數(shù)模型的路徑圖

6 結(jié) 語

本文以Hopfield神經(jīng)網(wǎng)絡(luò)為背景，研究三維地形下的一種有效的路徑規(guī)劃問題。利用山丘算法建立三維地形模型，在這個(gè)三維地形中，首先對起伏的地形以及障礙物進(jìn)行處理,得到地形模型函數(shù)，然后在Hopfield神經(jīng)網(wǎng)絡(luò)算法中集成此地形函數(shù)模型。實(shí)驗(yàn)表明，在復(fù)雜的三維地形中該算法可以避開起伏的地形和障礙物，尋找到一條有效路徑。本文研究也為無人駕駛的自主導(dǎo)航奠定了基礎(chǔ)。