基于視野范圍和遺傳算法的三維地形路徑規(guī)劃

賀 嬌，譚代倫

西華師范大學 數學與信息學院，四川 南充 637000

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

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

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

1 三維地形與視野范圍

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

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

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

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

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

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

2 視野范圍的構建與檢測

2.1 視野范圍的構建

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

圖2 點A 的視野范圍示意圖Fig.2 Spatial geometry of sight range

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

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

圖3 一個網格內的視野范圍Fig.3 Sight range in a grid

由空間幾何投影知識可知，要判斷空間直線段ABp+1和BpC的位置關系，可以先找到它們在XY平面上投影線的交點E，過E點作XY平面的垂線，與ABp+1和BpC分別交于點E′和E″，比較E′和E″的第三維坐標zE′和zE″大小，即可判斷出ABp+1和BpC的空間高低關系。

通常網格四個頂點A、Bp、Bp+1、C的三維坐標是已知的，其對角線在XY平面上投影的交點E的三維坐標也是容易計算的，則zE′和zE″可按下式進行計算：

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

圖4 跨越多個網格時可能的視野范圍Fig.4 Possible sight range in multiple consecutive grids

對圖4（a），可按以下公式計算Fi,Gi的坐標：

2.2 視野范圍的檢測

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

根據3.1 節(jié)中視野范圍構建過程，對三維地形上某點A及對應的下一網格基準點Bp，點A的視野范圍檢測算法步驟為：

（1）依次取點Bq∈{B1,…,Bp-1,Bp+1,…,B21}，計算投影點B′p和B′q之間的正方形網格個數npq。

（2）按公式（3）、（4）或（5）、（6）計算投影線A′B′q與所跨越網格的邊線和對角線所有交點Fi,Gi的坐標。

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

（4）對所有交點Fi,Gi，按公式（2）計算其在XY平面上垂線與網格的邊線或對角線的交點E″的海拔高度zE″。

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

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

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

3.1 編碼方案

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

網格化后的y坐標是用自然數表示的，因此采用不重復的自然數編碼方案。對圖1，每一個遺傳個體的基因編碼可記為：

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

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

（1）初始化一個M×N的空矩陣，設置每一個體第一個基因編碼為起點S的y坐標。

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

（3）以此類推，直至選取的最后一個基因編碼為終點P的y坐標。

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

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

3.3 適應度函數

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

經迭代計算后，適應度最小的個體即為最短路徑。

3.4 輪盤賭選擇策略

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

3.5 重合點片段交叉策略

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

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

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

（1）隨機產生兩個不同的自然數R1,R2∈(1,N)，且R1

（2）對當前個體，以第R1個基因點所對應的節(jié)點為視野中心，確定其視野范圍，并在其中隨機選取一個節(jié)點，取其y坐標作為下一個基因編碼。

（3）以此類推，直至選取節(jié)點的y坐標為第R2個基因所對應的節(jié)點。

例如，有以下當前個體Yi，隨機生成兩個不同的自然數為R1=2,R2=9，經變異得Yi′。

3.7 算法流程設計

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

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

4 實驗及仿真結果

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

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

4.1 實驗結果

按照圖6的算法流程和上述算法參數編程，本文算法和標準蟻群算法求解的三維路徑如圖7所示。

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

在圖7 中，藍色路徑為標準蟻群算法所求，路徑長度為27.5 km，紅色路徑為所提算法所求，路徑長度為23.5 km，結果明顯更優(yōu)。

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

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

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

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

圖9 兩種算法的進化曲線Fig.9 Evolution curve of two algorithms

4.2 算法性能

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

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

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

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

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

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

5 結束語

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