賀 嬌，譚代倫

西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院，四川 南充 637000

路徑規(guī)劃是智能技術(shù)中的熱點(diǎn)研究問題，已在眾多領(lǐng)域有所突破并初步得以應(yīng)用，其中包括：無(wú)人機(jī)航跡規(guī)劃[1-3]、移動(dòng)機(jī)器人路徑規(guī)劃[4-6]、自主水下航行器路徑規(guī)劃[7-8]、景點(diǎn)旅游路徑規(guī)劃[9-10]、城市交通出行路徑規(guī)劃[11-12]等。路徑規(guī)劃研究在二維平面環(huán)境中取得了一定的成效，但隨著生活的發(fā)展變化，考慮到實(shí)際操作角度，更多時(shí)候的路徑規(guī)劃需要在特定的三維場(chǎng)景下完成，故如何優(yōu)化三維環(huán)境中最短路徑的研究是具有重要意義且十分必要的。

三維空間環(huán)境中的路徑規(guī)劃是NP 難問題，由于三維地形路徑規(guī)劃問題中的空間復(fù)雜度以及地形不確定性等因素往往使得規(guī)劃效果不佳，故如何對(duì)其進(jìn)行更好的規(guī)劃是極具挑戰(zhàn)的。近幾年，國(guó)內(nèi)外專家學(xué)者做了很多的研究。郝燕玲等[13]采用柵格法劃分三維空間中XY平面，以針對(duì)路徑的表示，只要求得到每一柵格里的最大地形高度，而不對(duì)實(shí)際地形環(huán)境做任何處理；禹建麗[14]、何光勤等[15]引入碰撞罰函數(shù)，結(jié)合對(duì)各個(gè)障礙物的神經(jīng)網(wǎng)絡(luò)定義各路徑點(diǎn)的碰撞罰函數(shù)，對(duì)各路徑點(diǎn)的碰撞罰函數(shù)求和得到整條路徑罰函數(shù)，以此規(guī)避不可行路徑；李玉齊[16]提出一種立方體柵格的方法來描述三維空間障礙物，通過判斷空間線與面的相交與否確定是否與障礙物發(fā)生碰撞，從而搜索三維避障路徑；袁建華等[17]在三維空間中定義長(zhǎng)方體障礙物，通過UAV 自身傳感器建立可視區(qū)域，以當(dāng)前位置為中心分別產(chǎn)生10 個(gè)同心球體，從中隨機(jī)選取代價(jià)系數(shù)最小的節(jié)點(diǎn)組成子路徑，結(jié)合滾動(dòng)策略探知周圍環(huán)境信息完成避障。

綜合已有文獻(xiàn)的研究成果，一種更接近人工智能的思路是借鑒自然界生物視覺系統(tǒng)的工作機(jī)制，為路徑規(guī)劃也定義某種視野范圍，以更有效地克服由于地形不確定性所帶來的干擾和影響，使路徑規(guī)劃過程總是沿著視野范圍內(nèi)行走，從而確保路徑總是可行的，以此避開三維地形障礙，并將這種機(jī)制結(jié)合到遺傳算法中，通過實(shí)驗(yàn)仿真求解三維地形路徑規(guī)劃問題，取得了較好效果。

1 三維地形與視野范圍

目前，三維空間環(huán)境建模通常采用柵格法，即將空間的三個(gè)維度進(jìn)行等距劃分，形成空間中的網(wǎng)格塊，并把它們看作是路徑規(guī)劃中的節(jié)點(diǎn)，以此構(gòu)造路徑。而三維空間環(huán)境的路徑規(guī)劃主要在三維地形的表面上行進(jìn)，因此只需對(duì)經(jīng)度和緯度這兩個(gè)維度作網(wǎng)格化，第三個(gè)維度可直接取地形表面的海拔高度，不需作網(wǎng)格化處理。本文選取文獻(xiàn)[18-20]中的一種隨機(jī)三維地圖，如圖1。

圖1 三維地形與視野范圍Fig.1 3D terrain and sight range

圖中三維地形的范圍為21 km×21 km×2 km，對(duì)XY平面進(jìn)行網(wǎng)格化，每個(gè)網(wǎng)格的長(zhǎng)度和寬度均為單位1。點(diǎn)S為路徑起點(diǎn)，點(diǎn)P為路徑終點(diǎn)，點(diǎn)A為路徑上任意一點(diǎn)。網(wǎng)格化后，連續(xù)變化的三維地形表面被簡(jiǎn)化為一個(gè)個(gè)的空間四邊形，這些空間四邊形在XY平面上的投影對(duì)應(yīng)于每一個(gè)正方形網(wǎng)格。

自然界中，大部分生物依靠自身的視覺系統(tǒng)在三維地形表面上行走，每一次向前行進(jìn)的距離，往往都是在根據(jù)視覺系統(tǒng)檢測(cè)到的可行走范圍內(nèi)[21]?；谶@種生物視覺仿生學(xué)原理[22]，本文將三維地形上從某點(diǎn)出發(fā)檢測(cè)到的可行走范圍定義為視野范圍。在圖1中，從點(diǎn)A發(fā)出的紅色線段，是它能直接到達(dá)的下一網(wǎng)格點(diǎn)的行走路徑，這些線段及其端點(diǎn)即可看作是從A點(diǎn)出發(fā)沿x軸正方向前進(jìn)的視野范圍。

設(shè)從路徑起點(diǎn)S到路徑終點(diǎn)P需經(jīng)過n個(gè)中間節(jié)點(diǎn)，記中間節(jié)點(diǎn)集合為V={v1,v2,…,vi,…,vn-1,vn}，那么在三維路徑規(guī)劃中建立以總路徑長(zhǎng)度D為優(yōu)化目標(biāo)的數(shù)學(xué)模型如下：

其中，dvivi+1表示節(jié)點(diǎn)vi到vi+1的兩點(diǎn)間距離。

2 視野范圍的構(gòu)建與檢測(cè)

2.1 視野范圍的構(gòu)建

在三維地形路徑規(guī)劃中，檢測(cè)出視野范圍對(duì)形成一條完全可行的路徑是非常關(guān)鍵的。對(duì)圖1的點(diǎn)A，其視野范圍可抽象為如圖2所示的空間幾何圖形。

圖2 點(diǎn)A 的視野范圍示意圖Fig.2 Spatial geometry of sight range

在圖2 中，{B1,B2,…,Bp-1,Bp,Bp+1,…,B20,B21} 為從A點(diǎn)出發(fā)，向x軸正方向前進(jìn)時(shí)所有可能的路徑節(jié)點(diǎn)?？梢钥吹?，從點(diǎn)A可以直線到達(dá)點(diǎn)Bp，而其余的節(jié)點(diǎn)，能否以直線方式到達(dá)則需要檢測(cè)和判斷。

若從A點(diǎn)出發(fā)，要到達(dá)的下一個(gè)網(wǎng)格點(diǎn)是同一個(gè)網(wǎng)格內(nèi)的對(duì)角頂點(diǎn)，如圖3。此時(shí)可能有兩種情形：一種是對(duì)角線BpC的空間位置比ABp+1低，在實(shí)際三維地形中相當(dāng)于“山谷”，如圖3（a），此時(shí)從點(diǎn)A能以直線方式到達(dá)點(diǎn)Bp+1，于是Bp+1在點(diǎn)A的視野范圍內(nèi)；另一種情形是對(duì)角線BpC的空間位置比ABp+1高，在實(shí)際三維地形中相當(dāng)于“山脊”，如圖3（b），此時(shí)從點(diǎn)A不能以直線方式到達(dá)點(diǎn)Bp+1，即BpC構(gòu)成了地形障礙，則Bp+1點(diǎn)就不在點(diǎn)A的視野范圍內(nèi)。

圖3 一個(gè)網(wǎng)格內(nèi)的視野范圍Fig.3 Sight range in a grid

由空間幾何投影知識(shí)可知，要判斷空間直線段ABp+1和BpC的位置關(guān)系，可以先找到它們?cè)赬Y平面上投影線的交點(diǎn)E，過E點(diǎn)作XY平面的垂線，與ABp+1和BpC分別交于點(diǎn)E′和E″，比較E′和E″的第三維坐標(biāo)zE′和zE″大小，即可判斷出ABp+1和BpC的空間高低關(guān)系。

通常網(wǎng)格四個(gè)頂點(diǎn)A、Bp、Bp+1、C的三維坐標(biāo)是已知的，其對(duì)角線在XY平面上投影的交點(diǎn)E的三維坐標(biāo)也是容易計(jì)算的，則zE′和zE″可按下式進(jìn)行計(jì)算：

若從A點(diǎn)出發(fā)，要到達(dá)的下一個(gè)網(wǎng)格點(diǎn)Bq需要跨越多個(gè)網(wǎng)格，則以ABp為基準(zhǔn)，在點(diǎn)A左側(cè)和右側(cè)可能形成的視野范圍投影圖如圖4（a）、（b）所示。

圖4 跨越多個(gè)網(wǎng)格時(shí)可能的視野范圍Fig.4 Possible sight range in multiple consecutive grids

對(duì)圖4（a），可按以下公式計(jì)算Fi,Gi的坐標(biāo)：

2.2 視野范圍的檢測(cè)

利用式（1）～（6）可以檢測(cè)出三維地形中從某點(diǎn)出發(fā)的視野范圍。為記錄檢測(cè)結(jié)果，定義如下0-1型變量：

根據(jù)3.1 節(jié)中視野范圍構(gòu)建過程，對(duì)三維地形上某點(diǎn)A及對(duì)應(yīng)的下一網(wǎng)格基準(zhǔn)點(diǎn)Bp，點(diǎn)A的視野范圍檢測(cè)算法步驟為：

（1）依次取點(diǎn)Bq∈{B1,…,Bp-1,Bp+1,…,B21}，計(jì)算投影點(diǎn)B′p和B′q之間的正方形網(wǎng)格個(gè)數(shù)npq。

（2）按公式（3）、（4）或（5）、（6）計(jì)算投影線A′B′q與所跨越網(wǎng)格的邊線和對(duì)角線所有交點(diǎn)Fi,Gi的坐標(biāo)。

（3）對(duì)所有交點(diǎn)Fi,Gi，按公式（1）計(jì)算其在XY平面上垂線與線段ABq的交點(diǎn)E′的海拔高度zE′。

（4）對(duì)所有交點(diǎn)Fi,Gi，按公式（2）計(jì)算其在XY平面上垂線與網(wǎng)格的邊線或?qū)蔷€的交點(diǎn)E″的海拔高度zE″。

（5）若zE′≥zE″，則TABi=1，否則TABi=0。

3 基于視野范圍的遺傳算法

三維路徑規(guī)劃是典型的組合優(yōu)化問題，其路徑節(jié)點(diǎn)較多，問題規(guī)模較大，近年來在求解方法上更多地選擇了現(xiàn)代群智能算法，既能獲得較高精度的近似最優(yōu)解，也能加快求解速度。在各種群智能算法中，遺傳算法的通用性、并行性、魯棒性[23]均較強(qiáng)，已被成功應(yīng)用于求解三維地形的路徑規(guī)劃。所提視野范圍較好地解決了遺傳算法求解三維地形的路徑規(guī)劃中回避地形障礙的問題，從而不必設(shè)計(jì)修復(fù)算子對(duì)不可行路徑進(jìn)行處理。為此，下面將結(jié)合視野范圍機(jī)制對(duì)遺傳算法進(jìn)行設(shè)計(jì)。

3.1 編碼方案

在遺傳算法中，編碼方案是將對(duì)問題的解空間轉(zhuǎn)換為有利于遺傳進(jìn)化操作的基因編碼。如圖1，對(duì)給定的起點(diǎn)S和終點(diǎn)P，其沿地形行走的路徑具有逐個(gè)網(wǎng)格依次前進(jìn)的特點(diǎn)，故只需對(duì)不確定的y坐標(biāo)進(jìn)行編碼，再利用z坐標(biāo)判斷是否避開地形障礙即可。

網(wǎng)格化后的y坐標(biāo)是用自然數(shù)表示的，因此采用不重復(fù)的自然數(shù)編碼方案。對(duì)圖1，每一個(gè)遺傳個(gè)體的基因編碼可記為：

3.2 基于視野范圍的種群初始化

遺傳算法不能直接處理問題空間的參數(shù)，需要將其編碼成為遺傳空間的染色體。在三維地形路徑規(guī)劃中，由于存在地形障礙，所產(chǎn)生個(gè)體的基因（路徑節(jié)點(diǎn)）很容易構(gòu)成不可行路徑。為此，引入視野范圍機(jī)制進(jìn)行檢測(cè)和判斷，可以很好解決這個(gè)問題。設(shè)種群規(guī)模為M，基因編碼長(zhǎng)度為N，則基于視野范圍的種群初始化步驟為：

（1）初始化一個(gè)M×N的空矩陣，設(shè)置每一個(gè)體第一個(gè)基因編碼為起點(diǎn)S的y坐標(biāo)。

（2）根據(jù)2.2節(jié)的視野范圍檢測(cè)算法，搜索起點(diǎn)S的視野范圍{v11,v12,…,v1i,…,v1k1}，并在其中隨機(jī)選取一個(gè)路徑節(jié)點(diǎn)v1i，將點(diǎn)v1i的y坐標(biāo)填入下一個(gè)基因編碼。

（3）以此類推，直至選取的最后一個(gè)基因編碼為終點(diǎn)P的y坐標(biāo)。

上述初始化中，路徑的形成過程如圖5。

圖5 基于視野范圍的路徑形成過程Fig.5 Path formation process based on sight range

3.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評(píng)估和區(qū)分種群個(gè)體的優(yōu)劣，是進(jìn)行遺傳選擇的依據(jù)[24]。根據(jù)3.2節(jié)可知種群初始化方法所產(chǎn)生的種群個(gè)體都是可行路徑，因此個(gè)體的適應(yīng)度可以直接取路徑中相鄰節(jié)點(diǎn)的歐氏距離之和，即：

經(jīng)迭代計(jì)算后，適應(yīng)度最小的個(gè)體即為最短路徑。

3.4 輪盤賭選擇策略

輪盤賭策略是遺傳算法的經(jīng)典選擇策略[25]，首先將個(gè)體適應(yīng)度f(wàn)i歸一化并取倒數(shù)得到fi′；其次，計(jì)算個(gè)體的適應(yīng)度占比pi=f′i/(∑fi)以及累積概率Pi=∑pi；最后隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)rnd∈(0,1)，選擇滿足Pi-1

3.5 重合點(diǎn)片段交叉策略

遺傳算法的交叉策略是將兩個(gè)隨機(jī)個(gè)體的部分基因進(jìn)行交換，從而生成新個(gè)體[26]。為保證被交換基因（子路徑）的有效性，引入了一種重合點(diǎn)片段交叉策略：在兩個(gè)個(gè)體中查找出兩個(gè)基因重合點(diǎn)（相同位置的基因相同），將介于兩個(gè)重合點(diǎn)之間的基因片段按交叉概率進(jìn)行交換，從而生成兩個(gè)新的子代個(gè)體。

3.6 基于視野范圍的變異策略

在遺傳算法中，變異策略有利于增加種群的多樣性，能夠盡量避免算法過快陷入局部最優(yōu)[27]。采用片段基因變異方法，即以給定的變異概率改變個(gè)體的部分基因片段?？紤]到基因變異后將會(huì)導(dǎo)致不可行路徑的產(chǎn)生，因此結(jié)合視野范圍機(jī)制進(jìn)行片段變異，其主要步驟為：

（1）隨機(jī)產(chǎn)生兩個(gè)不同的自然數(shù)R1,R2∈(1,N)，且R1

（2）對(duì)當(dāng)前個(gè)體，以第R1個(gè)基因點(diǎn)所對(duì)應(yīng)的節(jié)點(diǎn)為視野中心，確定其視野范圍，并在其中隨機(jī)選取一個(gè)節(jié)點(diǎn)，取其y坐標(biāo)作為下一個(gè)基因編碼。

（3）以此類推，直至選取節(jié)點(diǎn)的y坐標(biāo)為第R2個(gè)基因所對(duì)應(yīng)的節(jié)點(diǎn)。

例如，有以下當(dāng)前個(gè)體Yi，隨機(jī)生成兩個(gè)不同的自然數(shù)為R1=2,R2=9，經(jīng)變異得Yi′。

3.7 算法流程設(shè)計(jì)

綜合上述設(shè)計(jì)，基于視野范圍的遺傳算法流程圖如圖6。

圖6 基于視野范圍的遺傳算法流程圖Fig.6 Flow chart of genetic algorithm based on field of view

4 實(shí)驗(yàn)及仿真結(jié)果

近年來，較多文獻(xiàn)選用蟻群算法求解三維路徑規(guī)劃。為驗(yàn)證所提算法的有效性和求解性能，對(duì)圖1的三維地形圖，下面選取標(biāo)準(zhǔn)蟻群算法與本文算法分別進(jìn)行求解。圖1 中，路徑起點(diǎn)為S（1，10，0.65），路徑終點(diǎn)為P（21，8，1）。

硬軟件環(huán)境為AMD A8-45000M CPU/8 GB/Win7系統(tǒng)和Matlab R2018a。由于遺傳算法的運(yùn)行參數(shù)往往是通過先前經(jīng)驗(yàn)或者反復(fù)的調(diào)試獲得的，故設(shè)置遺傳算法的種群規(guī)模、迭代次數(shù)、交叉概率和變異概率分別為100、100、0.8、0.3。

4.1 實(shí)驗(yàn)結(jié)果

按照?qǐng)D6的算法流程和上述算法參數(shù)編程，本文算法和標(biāo)準(zhǔn)蟻群算法求解的三維路徑如圖7所示。

圖7 兩種算法求得的最優(yōu)路徑Fig.7 Optimal path obtained by two algorithms

在圖7 中，藍(lán)色路徑為標(biāo)準(zhǔn)蟻群算法所求，路徑長(zhǎng)度為27.5 km，紅色路徑為所提算法所求，路徑長(zhǎng)度為23.5 km，結(jié)果明顯更優(yōu)。

為便于更好地觀察圖7中的兩條路徑，將兩種算法求得的三維路徑投影至XY平面，如圖8。

圖8 三維最優(yōu)路徑在XY 平面的投影Fig.8 Projection of three dimensional optimal path in XY plane

結(jié)合圖7和圖8，可以看到，在路徑的后半部分節(jié)點(diǎn)上，三維地形障礙較多、變化復(fù)雜，本文算法求得的最優(yōu)路徑更優(yōu)于標(biāo)準(zhǔn)蟻群算法。

兩種算法在求解三維地形最優(yōu)路徑時(shí)適應(yīng)度的進(jìn)化曲線如圖9。在圖9中，紅色進(jìn)化曲線下降更快，很快趨于平緩，最短路徑長(zhǎng)度取值更小，因此本文算法的尋優(yōu)能力明顯強(qiáng)于標(biāo)準(zhǔn)蟻群算法，收斂速度更快，所需迭代次數(shù)更少。

圖9 兩種算法的進(jìn)化曲線Fig.9 Evolution curve of two algorithms

4.2 算法性能

為進(jìn)一步測(cè)試本文算法求解三維路徑規(guī)劃問題的性能，降低由智能算法的隨機(jī)導(dǎo)致的結(jié)果片面性，本文運(yùn)用兩種算法在相同實(shí)驗(yàn)環(huán)境中分別進(jìn)行多次實(shí)驗(yàn)，統(tǒng)計(jì)兩種算法的運(yùn)行結(jié)果，隨機(jī)選取三組實(shí)驗(yàn)結(jié)果在路徑長(zhǎng)度與迭代速度上進(jìn)行對(duì)比，如表1。

表1 兩種算法求得的最優(yōu)路徑長(zhǎng)度比較Table 1 Comparison of optimal path length obtained by two algorithms

從表1可以看到，本文算法求解的最優(yōu)路徑長(zhǎng)度均小于蟻群算法，且本文算法求得的最優(yōu)路徑長(zhǎng)度比蟻群算法平均降低18.7%。說明本文提出的視野范圍機(jī)制效果明顯，一定程度上提高了選擇下一路徑節(jié)點(diǎn)的合理性，降低了路徑長(zhǎng)度。

記錄隨機(jī)選取的三次實(shí)驗(yàn)中兩種算法求解時(shí)的進(jìn)化曲線，統(tǒng)計(jì)兩種算法尋得最優(yōu)路徑時(shí)的迭代次數(shù)，統(tǒng)計(jì)結(jié)果如表2所示。

表2 兩種算法迭代速度比較Table 2 Comparison of iterative speed of two algorithms

從表2 可以看到，在三次隨機(jī)實(shí)驗(yàn)中，本文算法均早于蟻群算法求得最優(yōu)路徑。說明本文提出的視野范圍構(gòu)建機(jī)制有效規(guī)避了不可行解的產(chǎn)生，明顯提高了路徑搜索效率，節(jié)省了尋優(yōu)時(shí)間。

5 結(jié)束語(yǔ)

針對(duì)三維路徑規(guī)劃問題，本文模擬自然界生物的視覺系統(tǒng)提出了一種視野范圍機(jī)制，利用幾何投影方法構(gòu)建了任意節(jié)點(diǎn)視野范圍，以此達(dá)到規(guī)避地形障礙的目的，從而尋得可行路徑；將視野范圍機(jī)制引入遺傳算法，提出了一種基于視野范圍的遺傳算法，通過實(shí)驗(yàn)仿真求解三維地形路徑規(guī)劃問題，不斷對(duì)種群規(guī)模個(gè)個(gè)體進(jìn)行迭代尋優(yōu)。實(shí)驗(yàn)仿真結(jié)果表明視野范圍機(jī)制求解三維地形路徑規(guī)劃問題具有良好的適用性，與蟻群算法的實(shí)驗(yàn)對(duì)比結(jié)果更加表明視野范圍機(jī)制的路徑規(guī)劃效率較高。這對(duì)未來可移動(dòng)智能設(shè)備更好地模擬自然界生物的各種實(shí)用功能提供了新的思路和方法。