裝備野外通行路徑優(yōu)化算法研究進展

常寧東，程鵬達，馮 春，2*，王理想，李玉瓊，2*

（1.中國科學院 力學研究所，北京 100190；2.中國科學院大學 工程科學學院，北京 100049）

1 引言

隨著科技的進步與軍事力量的發(fā)展，野外路徑優(yōu)化在軍事戰(zhàn)場環(huán)境分析中的地位日益提升［1-3］。通過野外路徑優(yōu)化技術(shù)，可以對戰(zhàn)場環(huán)境進行模擬分析，以此指揮軍事裝備、機器人、智能設(shè)備和人員的行動［4］。目前，野外路徑優(yōu)化也廣泛應(yīng)用于野外災(zāi)情救援、軍事定向越野和自駕旅游等。確定高效可行的野外路徑并進行路徑優(yōu)化可以保障野外活動的準確開展，縮短軍事裝備、救災(zāi)裝備和旅游裝備的野外行駛時間，降低軍事活動和救災(zāi)避險活動中的損失［5］。

與城市道路優(yōu)化不同，野外環(huán)境下的道路不具備道路結(jié)構(gòu)化及交通規(guī)則信息；基于既有道路的路徑優(yōu)化是典型的線狀網(wǎng)絡(luò)優(yōu)化問題，而野外環(huán)境的通行路徑優(yōu)化則是典型的面狀優(yōu)化問題。同時，野外環(huán)境中具有多種阻礙裝備正常運行的障礙物和未知威脅，由于地表屬性較為復(fù)雜，會存在坑洼、泥濘的道路，因此會對裝備的行進造成多種影響或阻礙。

野外環(huán)境下路徑優(yōu)化是指在有界空間內(nèi)根據(jù)感知系統(tǒng)輸入的野外環(huán)境信息，在考慮到環(huán)境和裝備等多種約束條件的基礎(chǔ)上，生成從初始位置到達指定目標的高效安全的優(yōu)化行駛路徑。在工程裝備在野外復(fù)雜地面上行進路徑的選擇和優(yōu)化過程中，土地類型（農(nóng)業(yè)、灌木叢、森林、濕地、城市等）、地形特征（坡度、表面粗糙度、丘/溝障礙物的大小和間距、樹木/植被莖的大小和間距等）、地面力學特性（彈塑性、摩擦角、粘聚力等）以及裝備特征（編隊、重量、履帶、輪式、輪腿式、軌道、葉片和尖齒等）等直接影響裝備的通行速度，進而影響裝備在復(fù)雜地面行進的路徑選擇和路徑優(yōu)化。

目前大多數(shù)研究均圍繞既有城市道路優(yōu)化展開，針對野外環(huán)境下的路徑優(yōu)化研究相對較少［6］。鑒于此，本文對野外路徑優(yōu)化的不同算法進行綜述，對不同算法的優(yōu)勢與不足進行了闡述，并對野外環(huán)境下的路徑優(yōu)化進行了展望。

2 野外環(huán)境建模方法綜述

為對野外路徑進行合理優(yōu)化，需事先收集野外環(huán)境的相關(guān)信息，對已有的空間信息進行環(huán)境建模，因此對環(huán)境準確、合理地建模是路徑優(yōu)化的重要前提。目前常用的野外環(huán)境建模方法有可視圖法、Voronoi 圖法、拓撲法和柵格法［7-11］。

2.1 可視圖法

可視圖法由Lozano-Pérez［12］提出，該方法首先確定環(huán)境中的障礙物，將障礙物表示為多邊形連接區(qū)域，根據(jù)與各障礙物頂點之間的可視情況進行判斷［13］。對相互可視的頂點之間的連線賦予權(quán)重形成可視邊，頂點的集合與可視邊的集合共同組成了可視圖，如圖1 所示。

圖1 可視圖法示意圖［14］Fig.1 Schematic diagram of viewable method［14］

由于可視圖法原理較為簡單，該方法的實現(xiàn)較為方便，但僅適用于障礙物頂點數(shù)目較少的方法。當障礙物的頂點數(shù)目較多時，將會產(chǎn)生許多無關(guān)可視路徑，大大降低可視圖構(gòu)造的效率，同時影響搜索算法的收斂性。依據(jù)可視圖法搜索到的最短路徑往往較為粗糙，與真實最短路徑存在偏差，且缺乏靈活性，無法用于三維優(yōu)化［8，15-16］。

2.2 Voronoi 圖法

Voronoi 圖法［17］是一種避免路徑與障礙物之間碰撞的方法，該方法首先設(shè)置系列控制點，即生成元，以此生成元為核向外擴張直至與其他多邊形相碰為止，將所有生成點作為頂點形成三角形的外接圓，以此得到每個多邊形的所有邊界信息，再沿著多邊形的邊界尋找一條無碰撞的路徑，如圖2 所示。

圖2 Voronoi 圖法示意圖［9］Fig.2 Schematic diagram of Voronoi method［9］

Voronoi 圖法是一種不依賴于空間坐標的臨近模型，且其計算出的路徑安全性較高，但其計算量十分大，僅適用于簡單環(huán)境模型，且得到的路徑常常不是最優(yōu)路徑［9，18］。

2.3 拓撲法

拓撲法地圖來源于圖論，為數(shù)學的一個分支［19］。拓撲法將事物用節(jié)點來表示，節(jié)點與節(jié)點之間的關(guān)系用邊來表示，在拓撲地圖中只關(guān)心它們之間的連接關(guān)系，而不考慮長短等信息，因此忽略了大量的環(huán)境信息［20］。該方法首先將環(huán)境空間劃分并建立特征網(wǎng)，在形成的特征網(wǎng)中搜索路徑，如圖3 所示。

圖3 拓撲法示意圖［7］Fig.3 Schematic diagram of topological method［7］

拓撲法省去了直接測量環(huán)境數(shù)據(jù)的麻煩，具有建模方便、計算成本耗費較小等優(yōu)點，但拓撲法對于相似的地點難以進行區(qū)分，并且難以得到詳細信息［21-23］。

2.4 柵格法

柵格法根據(jù)野外探測的雷達數(shù)據(jù)將空間劃分為大小相同的矩形柵格，再依據(jù)傳感器得到的信息對柵格內(nèi)的情況進行實時判斷，如圖4所示。

圖4 柵格法示意圖［7］Fig.4 Schematic diagram of grid method［7］

由于柵格法實現(xiàn)簡單，在一定程度上可以保證環(huán)境信息的精度，所以得到廣泛的應(yīng)用。建立柵格地圖時，柵格的大小是一個關(guān)鍵問題。當柵格過大時，雖然數(shù)據(jù)處理量得到減少，縮短了路徑的搜索時間，但環(huán)境信息的精度會因此受到損失，最終得到的路徑常常不是最優(yōu)路徑；當柵格過小時，雖然精度得到了提高，但數(shù)據(jù)量將會提高，對于較大空間環(huán)境難以進行路徑搜索，因此需要選擇適宜的柵格數(shù)量與柵格大小。該方法可以結(jié)合其他搜索算法進行優(yōu)化，但無法對動態(tài)障礙進行處理［24-26］。

綜上所述，可視圖法與Voronoi 圖法適用于簡單的模型，可視圖法會導(dǎo)致路徑搜索時間較長，Voronoi 圖法進行路徑優(yōu)化時計算量也較大，因此對于復(fù)雜的模型將會耗費大量的成本和資源。拓撲法無法在障礙物密集的環(huán)境下進行路徑規(guī)劃，而柵格法相對建模簡單，目前得到廣泛的應(yīng)用。

3 單裝備路徑優(yōu)化算法

野外路徑優(yōu)化即基于野外環(huán)境模型，在給定起點和終點后，尋得一條最優(yōu)的無碰撞路徑。根據(jù)野外環(huán)境是否已知，可將野外路徑優(yōu)化劃分為全局優(yōu)化和局部優(yōu)化。全局優(yōu)化方法需要事先得到野外環(huán)境信息，根據(jù)起點和目的地得到一條完整的全局路線，同時可以為局部路線提供參考。局部優(yōu)化方法則是根據(jù)裝備上的傳感器等設(shè)備獲取野外信息，從而進行實時的調(diào)整。這兩種方法的區(qū)別僅在于環(huán)境信息是否已知，兩者按照優(yōu)化算法都可以大致分為圖搜索法、隨機采樣法和智能優(yōu)化算法。

3.1 圖搜索法

圖搜索法首先建立環(huán)境的柵格地圖，再將環(huán)境信息賦予每個網(wǎng)格，在此基礎(chǔ)上進行野外路徑的尋優(yōu)工作。該算法主要包括Dijkstra 算法［27］、A*算法［28］、D*算法［29］及其推廣。

3.1.1 Dijkstra 算法

Dijkstra 算法［30］由荷蘭學者Dijkstra 提出，也稱狄克斯特拉算法。該算法通過計算一個節(jié)點到其他所有節(jié)點的最小代價并不斷遞進以尋得起點與終點之間的最優(yōu)路徑［31］。

首先假設(shè)各節(jié)點為V，令連接兩節(jié)點之間的帶權(quán)矩陣Cost［i，j］代表節(jié)點Vi和Vj之間的權(quán)值。令起始點為VS，D［i］為起始點VS到每一個節(jié)點Vi的最小權(quán)值，并令S為已經(jīng)找到的起點最短路徑的各終點集合，S初始值為S=｛VS｝，具體流程如下：

（1）尋得初始最短路徑的終點Vj，即D［j］=min｛D［i］｝，此時S=S∪｛Vj｝；

（2）尋得起點VS到集合V-S的任一節(jié)點VK的最短路徑。如果D［j］+Cost［j，k］＜D［k］，則進行下一步。

（3）令D［k］=D［j］+Cost［j，k］，不斷重復(fù)上述步驟，以此得到最短路徑節(jié)點的集合。

Dijkstra 算法可以進行一個目標到多個目標的路徑尋優(yōu)，但是其具有一定的盲目性，尋優(yōu)速率較慢，不具有啟發(fā)性［32］。

3.1.2 A*算法

A*算法［33］在Dijkstra 算法的基礎(chǔ)上，在搜索過程中引入了啟發(fā)值，以此使得搜索具有一定的目標性，其中A 為這類算法的統(tǒng)稱，星號代表啟發(fā)式的功能，又稱A-Star［34］。

啟發(fā)值作為一個預(yù)估值，估計每個節(jié)點與目標之間的距離，因此具有一定的誤差。其公式為：

其中：f*（n）為起點到n點的最小代價估計，g*（n）為起點到n點的最小代價，h*（n）為啟發(fā)函數(shù)。

雖然A*算法提高了運算速度，但由于啟發(fā)值與實際代價存在差異，將會導(dǎo)致尋得的路徑并不一定為最優(yōu)路徑，同時其無法適應(yīng)快速變化的環(huán)境，不具有實時性，同時A*算法只適用于具有位置信息的地圖。鮑久圣等［35］使用指數(shù)函數(shù)加權(quán)和三次樣條插值的方法，對A*算法進行改進，并在井下巷道內(nèi)進行全局路徑優(yōu)化仿真。王洪斌等［36］通過改進A*搜索算法，實現(xiàn)了一次優(yōu)化能夠達到多個目標點。譚雁英等［37］基于A*算法的優(yōu)化，使得無人機路徑優(yōu)化可以適應(yīng)圓形、凹/凸多邊形危險/威脅區(qū)域同時存在的情形。

3.1.3 D*算法

D*算法［38］源于Dynamic A Star，是在A*算法的基礎(chǔ)上進行發(fā)展，主要克服了A*算法無法實時適用環(huán)境的缺點。D*算法將終點作為搜索起點，首先將所有未知環(huán)境假設(shè)為暢通的，隨著搜索的進行，部分自由區(qū)域被發(fā)現(xiàn)為障礙，從而該點與終點之間的代價增加，并向相鄰節(jié)點進行擴展，對權(quán)值發(fā)生變化的節(jié)點進行處理，從而減小了工作量，增加了尋優(yōu)速度［39］。

D*算法具有計算數(shù)據(jù)少、可實時更新和較為簡易的優(yōu)點，此外，學者們也對其進行了不斷改進。Koenig 等［40］提出了D*Lite 算法，進一步提高了D*算法的速率，得到了廣泛應(yīng)用。史久根等［41］基于CA 模型對D*算法進行改進，得到的路徑與障礙物保持安全距離，縮短了計算時間。黃魯?shù)龋?2］基于懶惰視線算法與距離變換相結(jié)合的方法，對D*Lite 算法進行了改進，得到了更為平滑與安全的路徑。

綜上所述，對于傳統(tǒng)主要路徑優(yōu)化算法，Diljkstra 算法和A*算法為正向搜索過程，需要預(yù)先得到全局信息，只能進行靜態(tài)優(yōu)化。D*算法在上述兩種算法基礎(chǔ)上進行改進，不需要環(huán)境所有信息，可以進行實時動態(tài)優(yōu)化，更適合具有不確定性的野外環(huán)境。

3.2 隨機采樣法

隨機采樣法首先在優(yōu)化空間內(nèi)隨機采樣以此建立空間上的連通性，該方法能夠適應(yīng)高維且較為復(fù)雜的環(huán)境，并且適用于裝備在非完整約束的環(huán)境路徑優(yōu)化問題，主要包括概率地圖法和快速搜索隨機樹法，以及一些其推廣算法。

3.2.1 概率地圖法

概率地圖法（Probabilistic Roadmap Method，PRM）將連續(xù)空間的路徑優(yōu)化問題轉(zhuǎn)化為拓撲空間的優(yōu)化問題，該方法首先根據(jù)隨機采樣的方法生成空間的概率地圖，并隨機挑選一個采樣點判斷是否發(fā)生碰撞，之后選擇局部快速優(yōu)化器，以此將新搜索的無碰撞節(jié)點與之前的路徑相連，最終形成一個從起點到終點的無碰撞路徑［43］，具體流程如圖5。

圖5 概率地圖算法流程Fig.5 Flow chart of probabilistic roadmap method

概率地圖法實現(xiàn)較為簡單，且具有很好的實用性，但由于搜索過程中采樣具有隨機性，因此最終輸出結(jié)果無法保證為最優(yōu)路徑。曾國奇等［44］基于PRM 算法提出網(wǎng)格概率地圖法，實現(xiàn)了無人機的多約束路徑優(yōu)化。馬江濤等［45］提出一種基于局部二次學習概率路徑圖算法，通過二次局部學習，提高了算法的求解效率以及路徑圖質(zhì)量。

3.2.2 快速搜索隨機樹法

快速搜索隨機樹法［46］（Rapidly-exploring Random Trees，RRT）由Lavalle 提出，該算法不需要對環(huán)境空間進行預(yù)處理，且可以考慮非完整約束、動力學約束等，可以解決復(fù)雜環(huán)境下的路徑優(yōu)化問題。

該算法首先根據(jù)初始節(jié)點qstrat構(gòu)建隨機搜索樹T，不斷迭代進行隨機采樣選擇狀態(tài)節(jié)點qrand，通過遍歷得到距離初始節(jié)點qstrat路徑最短的qnear，再輸入控制集U，根據(jù)狀態(tài)轉(zhuǎn)換方程進行積分，從而得到qnew；不斷重復(fù)上述過程，最終搜索到終點qend，再由終點qend反溯到初始節(jié)點qstrat，從而得到最終的優(yōu)化路徑。

RRT 算法由于采用均勻隨機采樣，因此會造成一定的資源浪費、收斂速度變慢，同時由于隨機性，最終生成的路徑并不平滑。在此基礎(chǔ)上產(chǎn)生了一系列衍生算法，如RRT-Connect 和RRT*等。Lavalle 和Kuffner 等［47］提出了Bi-RRF 算法，提高了搜索速率。Karaman 等［48］通過添加父節(jié)點重選機制，減小了生成路徑時的抖動。

綜上所述，基于隨機采樣的路徑優(yōu)化算法不受限于環(huán)境信息，適用于高維度空間。PRM 和RRT 算法注重尋優(yōu)的快速性，最終尋得路徑為可行路徑，但并不一定為最優(yōu)路徑。隨機采樣法生成概率地圖時可以考慮動力學約束，對于野外環(huán)境下的裝備運行，在加入動力學約束之后，路徑優(yōu)化算法將會更為平滑，更符合實際運行過程。

3.3 人工勢場法

人工勢場法是通過模擬電荷在電場中的運動實現(xiàn)尋優(yōu)，其基本思想是將裝備視為勢能場U中的一個質(zhì)點，使得障礙物與裝備帶同種電荷而產(chǎn)生斥力，終點與裝備帶異種電荷而產(chǎn)生引力，因此在某點q的總勢場U如下式所示：

其中：Uatt為引力勢，Urep為斥力勢。

該路徑優(yōu)化問題即尋找勢場全局最小值的問題，因此不需要對環(huán)境進行地圖建模。尋求全局最小值最簡單算法為梯度下降法，將勢場U的負梯度視為一個廣義力，即F=-?U，令裝備從起點開始運行，沿著梯度反方向行走，直到梯度為0 停止。該方法優(yōu)化的路徑較為平滑，但是由于算法本身的原因而存在一定的問題：（1）當引力和斥力恰好大小相等、方向相反時，裝備容易陷入局部極小值或產(chǎn)生振蕩；（2）若目標點附近存在障礙物，當裝備靠近障礙物時斥力將會無限大，導(dǎo)致裝備無法到達目標點；（3）當裝備距離目標點較遠時，引力將會特別大，障礙物造成的斥力相對較小，因此可能會在路徑上碰到障礙物。除此之外，對于野外環(huán)境下的裝備路徑優(yōu)化，傳統(tǒng)人工勢場法由于將裝備視為質(zhì)點，因此無法考慮運動學和動力學等約束。

針對上述問題，Li 等［49］為每一個點賦予隨機的力場向量，使得陷入局部極小值的設(shè)備可以擺脫局部極小點，但該方法容易導(dǎo)致裝備在極小點產(chǎn)生振蕩。Connolly 等［50］提出引入調(diào)和函數(shù)來定義勢場函數(shù)，以此保證除目標點外不會產(chǎn)生第二個極小點，解決局部最小值的問題。韓堯等［51］引入了角度與速度調(diào)節(jié)因子，得到了更為真實的無人機飛行軌跡。田洪清等［52］提出PRM 和APF算法相結(jié)合的人工勢能場-概率圖法，考慮了車輛動力學特性，提出了多目標的野外環(huán)境路徑優(yōu)化算法。

3.4 智能優(yōu)化算法

隨著人類對自然界認知的深入，受自然規(guī)律或物理現(xiàn)象的啟發(fā)，不斷衍生的多種隨機搜索算法，統(tǒng)稱為智能優(yōu)化算法，比如蟻群算法、遺傳算法和神經(jīng)網(wǎng)絡(luò)算法等。這些算法可以直接應(yīng)用于路徑優(yōu)化問題，也可以與上述傳統(tǒng)方法相結(jié)合進行應(yīng)用。

3.4.1 蟻群算法

蟻群算法［53-54］對螞蟻群的爬行行為進行模擬，螞蟻在經(jīng)過一個未知路口時，各螞蟻會根據(jù)路徑的長短釋放信息素，信息素的量隨著路徑的增加而減小，因此螞蟻群可以根據(jù)信息素的量的大小尋得最優(yōu)路徑。

對于處于節(jié)點i的螞蟻，其選擇的下一個節(jié)點是具有隨機性的，根據(jù)局部信息素和啟發(fā)值給出：

其中：l為任意可能的取值；allowed（k）表示螞蟻k可以訪問的節(jié)點集合；τij（t）為t時刻弧（i，j）的信息 素；ηij為 啟發(fā)值，ηij=1/dij；α和β為相對重 要性，均不小于0。

對于節(jié)點i上第k個螞蟻的轉(zhuǎn)移概率為：

當螞蟻群的所有螞蟻完成各自的路徑后，每個螞蟻k在其經(jīng)過的路徑上所釋放的信息素量為：

其中：T（k）（t）為t次迭代后的TSP 解；Q為參數(shù)，一般可取1；Lk（t）為求解的路徑長度。

通過式（5）更新規(guī)則對信息素進行更新，再進行不斷迭代更新，最終獲得最優(yōu)路徑。

螞蟻算法在計算規(guī)模較小的問題時具有較強的優(yōu)勢，但對于計算量較大的問題則容易陷入局部最優(yōu)解。為解決上述問題，萬旭等［55］基于最大-最小策略，降低了螞蟻算法陷入局部最小值的可能，并將其應(yīng)用于有時間窗裝備路徑問題。孫燾等［56］基于螞蟻算法，增加了變異和最優(yōu)保存的操作，提高了算法的收斂性。胡中華等［57］將導(dǎo)引因子引入到狀態(tài)轉(zhuǎn)移策略中，減少了螞蟻局部搜索的盲目性。

3.4.2 遺傳算法

遺傳算法［58］（Genetic Algorithms）基于自然界中物種的進化過程，是一種主要用于尋求最優(yōu)解的方法，通過對自然界親代與子代之間的遺傳機制和進化理論進行模擬，提出一種可以對數(shù)據(jù)進行并行計算的尋優(yōu)理論。遺傳算法不受搜索空間的限制、運算簡單、收斂速度快，適用于解決復(fù)雜和非線性等較難問題［59］。

遺傳算法是由Holland［60］提出的一種自適應(yīng)的全局優(yōu)化概率算法，該算法模擬個體組成為群體的整體學習過程。遺傳算法首先將問題轉(zhuǎn)化為遺傳中的基因編碼問題，生成任一初始群體，再根據(jù)適應(yīng)度函數(shù)對各基因序列進行優(yōu)化，進行復(fù)制、交叉、變異和選擇等操作，不斷重復(fù)迭代使得群體逐步進化，最終求得問題的最優(yōu)解，其流程圖如圖6 所示。

圖6 遺傳算法流程圖Fig.6 Flow chart of genetic algorithms

遺傳算法作為一種并行運算方法，具有較快的計算速度，且不需事先得到問題的全部信息，在全局路徑優(yōu)化中得到廣泛應(yīng)用。雖然其具有較強的全局搜索能力，但是在局部搜索中存在缺陷，容易陷入局部最小值［61］，且計算速度較慢，容易產(chǎn)生“早熟”現(xiàn)象。郎茂祥等［62］將爬山算法和遺傳算法結(jié)合，在一定程度上克服了遺傳算法局部搜索能力不足的問題。張潛等［63］構(gòu)造了一種隨機開關(guān)，以此控制遺傳算法中的變異操作，避免陷入局部最小值的問題。歐麗珍等［31］基于Dijkstra 對遺傳算法進行改進，實現(xiàn)了定向野外中的多目標路徑尋優(yōu)過程。

3.4.3 神經(jīng)網(wǎng)絡(luò)算法

人工神經(jīng)網(wǎng)絡(luò)［64］（Artificial Neural Network）是一種基于人腦和神經(jīng)系統(tǒng)處理方法的數(shù)學模型，通過模擬神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元信息輸入、傳遞和處理的方式，形成具有自適應(yīng)能力的體系，通過建立網(wǎng)格之間的映射關(guān)系，結(jié)合生物學的神經(jīng)網(wǎng)絡(luò)相關(guān)理論，如圖7 所示。人工神經(jīng)網(wǎng)絡(luò)在對數(shù)據(jù)進行分類、識別、回歸、預(yù)測和組織等方面［65］具有強大優(yōu)勢，其主要優(yōu)點如下：

圖7 人工神經(jīng)網(wǎng)絡(luò)算法網(wǎng)格圖Fig.7 Grid diagram of artificial neural network algorithm

（1）人工神經(jīng)網(wǎng)絡(luò)采用并行計算的信息處理方式，在大量的神經(jīng)元信息并行處理時具有速度快、效率高的優(yōu)點；

（2）人工神經(jīng)網(wǎng)絡(luò)每一個神經(jīng)元可以接受其他神經(jīng)元大量的輸入，進而處理信息并輸出信息，實現(xiàn)對下一個神經(jīng)元的信息傳遞，網(wǎng)絡(luò)之間的相互影響可以實現(xiàn)從輸入狀態(tài)到輸出狀態(tài)的非線性映射，因此可以處理非線性問題，同時具有容錯性和魯棒性；

（3）人工神經(jīng)網(wǎng)絡(luò)以權(quán)值的形式將處理的數(shù)據(jù)信息儲存下來，因此具有較高的記憶能力；

（4）人工神經(jīng)網(wǎng)絡(luò)通過學習和訓練得到網(wǎng)格中的權(quán)值和閾值，因此具有極強的學習能力和自適應(yīng)能力；

（5）人工神經(jīng)網(wǎng)絡(luò)采用分布式存儲知識，信息分布在整個系統(tǒng)當中，因此具有聯(lián)想功能。

在路徑優(yōu)化中，神經(jīng)網(wǎng)絡(luò)算法可以通過分類結(jié)果對優(yōu)化算法進行引導(dǎo)，大大提高了計算速度，并且在局部優(yōu)化中，可以通過神經(jīng)網(wǎng)絡(luò)的映射關(guān)系對動態(tài)環(huán)境做出快速反應(yīng)，但其也存在易陷入局部最小值的問題［66］，且只適用于環(huán)境條件已知的情況，無法處理動態(tài)障礙物。Araujo 等［67］提出一種可裁剪的模糊自適應(yīng)共振理論神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，以此實現(xiàn)了動態(tài)更新和局部優(yōu)化。禹建麗等［68］基于人工神經(jīng)網(wǎng)絡(luò)算法和模擬退火溫度定義路徑能量函數(shù)，實現(xiàn)了機器人路徑的優(yōu)化。狄勇等［69］提出一種模糊神經(jīng)網(wǎng)絡(luò)的避障策略，通過模糊神經(jīng)網(wǎng)絡(luò)搜索可行節(jié)點來實現(xiàn)避障功能。

綜上所述，智能優(yōu)化算法大多具有并行運算的優(yōu)勢，提高了計算時間，具有較高的自適應(yīng)性和魯棒性，因此具有良好的實時性。

3.5 考慮動力學約束的優(yōu)化算法

目前大多傳統(tǒng)路徑優(yōu)化算法大多僅考慮了運動學約束，而很少考慮動力學約束。野外存在復(fù)雜的地形條件，同時野外環(huán)境下的裝備將面臨高度非線性的約束，相對于城市道路，野外裝備將會面臨傾倒、滑移和顛簸等問題，因此在路徑優(yōu)化中考慮動力學約束至關(guān)重要。

在野外路徑優(yōu)化前，需要考慮復(fù)雜場景數(shù)據(jù)，如積雪深度和密度、凍結(jié)或解凍深度、最大制動加速度、駕駛員反應(yīng)時間、安全系數(shù)、可視度、障礙物幾何參數(shù)和有無沙子等。對于地形數(shù)據(jù)，需要考慮地面狀況、土體類型、土體濕度、土體強度、基巖埋深、表面粗糙度、障礙物的幾何特性和植被分布情況等。對于裝備數(shù)據(jù)，需要考慮裝備尺寸、軸或轉(zhuǎn)向架等組件、駕駛員的位置、中心、懸架、輪胎的尺寸、履帶、傳動系統(tǒng)和雪鏈等。在此基礎(chǔ)上，對于任意給定的區(qū)域，首先對道路和野外環(huán)境分別進行建模，之后采用單獨的地形數(shù)據(jù)定義機動特性。對于復(fù)雜地形力學建模需有效的模擬裝備與土壤之間的力學交互特性，現(xiàn)對于復(fù)雜地形力學建模方法［70］包括連續(xù)介質(zhì)模型，如有限元法（Finite Element Method，F(xiàn)EM）；粒子模型，如離散元法（Discrete Element Method，DEM）、光滑粒子流體力學法（Smoothed Particle Hydrodynamics，SPH）和物質(zhì)點法（Material Point Method，MPM）。

目前國內(nèi)對裝備在野外環(huán)境中通行的動力學效應(yīng)研究較少，王學寧［71］基于Bekker 理論，考慮了坦克履帶的滑動與橫擺，建立了坦克的動力學仿真模型。李佳圣等［72］考慮了底盤懸架和輪胎結(jié)構(gòu)，建立了越野車輛底盤的動力學模型，但僅考慮了車輛的俯仰角速度。劉凱等［73］建立了考慮道路傾角的動力學模型，并提出了基于零力矩點的車輛側(cè)傾的約束，可以有效地防止車輛發(fā)生傾倒側(cè)翻。

國外考慮裝備動力學的路徑優(yōu)化方法中，最具有代表性的為北約參考機動模型（NATO Reference Mobility Model，NRMM），早期模型以經(jīng)驗公式為基礎(chǔ)，且只考慮了仰俯角，未考慮轉(zhuǎn)向/轉(zhuǎn)彎、胎面/粗面和左右兩側(cè)地形不對稱等對裝備穩(wěn)定性的影響，無法滿足現(xiàn)代裝備仿真的要求［74］。在此基礎(chǔ)上研發(fā)的下一代北約機動參考模型（Next Generation NATO Reference Mobility Model，NG-NRMM）通過將地理信息系統(tǒng)（Geograpic Information System，GIS）軟件和多體、基于物理學車輛動態(tài)建模和仿真軟件進行融合，利用地面力學來適當評估裝備-地形間的軟土（可變形的土地）交互，可獲取軟土對裝備機動性的影響效應(yīng)［75］。

綜上所述，路徑優(yōu)化算法逐漸趨于成熟，不同的算法具有不同的優(yōu)點和缺點，應(yīng)針對不同問題選擇適宜的算法，以此來提高路徑優(yōu)化的效率。對于圖搜索法，Diljkstra 算法和A*算法雖然搜索效率較高，但是容易得到非最優(yōu)解，同時僅適用于靜態(tài)環(huán)境的優(yōu)化，D*算法基于上述兩種算法，實現(xiàn)了實時動態(tài)優(yōu)化，可以在充滿不確定性的野外環(huán)境進行適時調(diào)整。相對于圖搜索法，隨機采樣法不受限于環(huán)境信息，可以處理更復(fù)雜的環(huán)境模型，同時可以考慮裝備的動力學約束，但也存在尋得路徑為非最優(yōu)路徑的問題。對于智能優(yōu)化算法，大多具有較好的魯棒性和穩(wěn)定性，具有并行處理問題的功能，但容易陷入局部最優(yōu)解從而無法收斂。智能優(yōu)化算法適用較為廣泛，現(xiàn)在受到學者們廣泛的研究和應(yīng)用。

4 多裝備的路徑優(yōu)化算法

目前針對野外環(huán)境下多裝備路徑優(yōu)化算法的研究較少，但對于既有道路環(huán)境下多車輛路徑優(yōu)化算法較為成熟，因此可以參考VRP 問題中的相關(guān)優(yōu)化算法。按照多裝備的路徑特點可大致分為四類：多目標裝備路徑優(yōu)化算法、多基地裝備路徑優(yōu)化算法、多類型裝備路徑優(yōu)化算法和帶時間窗的路徑優(yōu)化算法［76］。

4.1 多目標裝備路徑優(yōu)化算法

在多目標路徑優(yōu)化算法中各個子目標之間是相互矛盾的，無法令多個子目標同時得到最優(yōu)解，往往一個子目標的改善會引起其他子目標的惡化，因此只能尋得一個中間值，使得每一個子目標盡可能達到最優(yōu)。目前的研究方法主要可以分為兩類：精確算法和啟發(fā)式算法。

4.1.1 精確算法

精確算法指整數(shù)優(yōu)化法和動態(tài)優(yōu)化算法等數(shù)學優(yōu)化算法。整數(shù)優(yōu)化法［77］通過構(gòu)造問題對應(yīng)的整數(shù)優(yōu)化模型，再利用MATLAB 等數(shù)學軟件進行求解，但該方法只能得到一個精確解，主要應(yīng)用于規(guī)模較小的多目標路徑優(yōu)化問題。動態(tài)優(yōu)化算法［78］是一種在不同階段求得最優(yōu)解的一種算法，按照路徑的方向可分為下降路徑和上升路徑。下降路徑將問題分為多個子問題，再分別求解這些子問題；上升路徑先求解可能用到的所有子問題，基于求解結(jié)果構(gòu)造上級更大問題的解。

Hu［79］將多個目標整合為單個目標，采用整數(shù)線性優(yōu)化實現(xiàn)了多目標集裝箱供應(yīng)鏈的路徑優(yōu)化。李媛媛等［80］在動態(tài)優(yōu)化算法中引入了懲罰函數(shù)，實現(xiàn)了機器人的動態(tài)路徑優(yōu)化。周睿慜等［81］提出上升路徑和下降路徑相結(jié)合的動態(tài)優(yōu)化算法，提高了機器人路徑優(yōu)化的效率。雖然精確算法耗費時間較少，但由于精確算法原理的局限性，無法解決較為復(fù)雜和規(guī)模較大的多目標路線優(yōu)化問題，因此啟發(fā)式優(yōu)化算法應(yīng)用更為廣泛。

4.1.2 啟發(fā)式優(yōu)化算法

由于多目標路徑優(yōu)化問題的目標函數(shù)和約束函數(shù)常常為非線性的，并且一些問題規(guī)模較大，其復(fù)雜程度也隨之增加，一般的最優(yōu)算法無法進行求解，而啟發(fā)式算法針對此類問題求解效率較高。

元啟發(fā)式算法作為一種通用的啟發(fā)式算法，在啟發(fā)式算法的基礎(chǔ)上結(jié)合了隨機方法和搜索算法等。主要包括遺傳算法、蟻群算法、禁忌搜索算法、模擬退火算法和粒子群算法等。

Long 等［82］基于遺傳算法實現(xiàn)了多目標的車輛分配和訪問順序，并考慮了客戶預(yù)定等因素。張濤等［83］將啟發(fā)式規(guī)則和遺傳算法相結(jié)合，實現(xiàn)了多目標的地震救援路徑優(yōu)化。陳治亞等［84］以路徑最短和均衡度為目標，采用非支配排序策略，實現(xiàn)了考慮隨機需求的多目標路徑優(yōu)化。裴小兵等［85］基于模擬退火算法，結(jié)合記憶函數(shù)，并利用聚類分析初始化狀態(tài)種群，實現(xiàn)了城市物流車輛多目標路徑優(yōu)化。蒲興成等［86］將蟻群算法和粒子群算法相結(jié)合，引入反向?qū)W習策略，并對算法的權(quán)重和學習因子進行改進，避免了早熟現(xiàn)象。

4.2 多基地裝備路徑優(yōu)化算法

多基地裝備路徑問題指有多個裝備基地可以為目標服務(wù)，因此要求對各個基地發(fā)配的裝備和行駛路線進行合理安排。對于多基地裝備路徑優(yōu)化問題，需要在滿足約束的條件下，使得路程成本降為最低，同時還需要進行基地的選擇和優(yōu)化處理，因此求解存在一定的難度。

目前針對多基地的裝備路徑優(yōu)化研究較少，大多聚焦于單個出發(fā)點的問題。雷坤等［87］采用End-to-End 深度強化學習的方法，利用改進圖注意力網(wǎng)格作為編碼器，實現(xiàn)了任意數(shù)目車場的車輛路徑優(yōu)化問題。Alinaghian 等［88］提出一種自適應(yīng)大鄰域和變鄰域搜索相結(jié)合的混合算法，以降低車輛數(shù)和運輸成本為目標，實現(xiàn)了多車場多隔間的路徑優(yōu)化問題。杜茂康等［89］通過改進的多染色體遺傳算法，實現(xiàn)了車載無人機起飛、降落等任務(wù)。戚遠航等［90］以離散蝙蝠算法為核心，結(jié)合泰森多邊形的初始化策略加快算法，加快了多車場車輛路徑問題的計算速度。

4.3 多類型裝備路徑優(yōu)化算法

在軍事活動中往往需要多種裝備的運行，確定裝備的類型、尺寸和數(shù)量是節(jié)約時間和成本的關(guān)鍵。按照裝備的類型，可以將裝備路徑優(yōu)化問題分為單類型裝備和多類型裝備，單類型裝備問題需要假定裝備的類型、尺寸、最大載重、最大行駛距離和成本等都相同，而多類型裝備問題裝備類型和成本等往往都不同，如軍事活動中往往需要裝甲車和坦克車等共同運作。

針對多類型裝備的路徑優(yōu)化問題，國內(nèi)外學者開展了一定的研究。柳伍生等［91］提出無人機與車輛相聯(lián)合的模型，基于帶末端優(yōu)化的模擬退火算法求解了路徑優(yōu)化問題。Ostermeier 等［92］發(fā)現(xiàn)采用單隔間和多隔間混合車隊進行雜貨配送時，可以有效地降低成本。姚竟發(fā)等［93］提出聯(lián)合收割機多機無沖突協(xié)同作業(yè)路徑優(yōu)化算法，實現(xiàn)了收割機的多機協(xié)同作業(yè)。阮貴航等［94］基于滾動優(yōu)化和分散捕食者獵物模型算法，結(jié)合鯨魚優(yōu)化算法實現(xiàn)了多機器人全覆蓋路徑優(yōu)化算法，減少了機器人行走路徑。

4.4 帶時間窗的路徑優(yōu)化算法

在野外環(huán)境下進行物資運輸、軍事演習和救援救災(zāi)等活動時，往往需要在特定時間段內(nèi)完成任務(wù)，因此需要多個裝備同時運行。帶時間窗的路徑優(yōu)化算法即在裝備路徑優(yōu)化算法中施加時間窗約束，時間窗為任務(wù)要求的一個時間區(qū)間，因此對于帶時間窗的路徑優(yōu)化算法，在對裝備進行空間上的路徑優(yōu)化基礎(chǔ)上，還需要對各個時間段進行合理的安排與分配。

參照多隔間車輛路徑問題（Multi-compartment VRP，MCVRP）劃分的原則，根據(jù)是否必須嚴格按照時間窗的規(guī)定，可以將帶時間窗的路徑優(yōu)化算法劃分為帶有硬時間窗的路徑優(yōu)化算法和帶有軟時間窗的路徑優(yōu)化算法［76］。對于帶有硬時間窗的路徑優(yōu)化算法必須嚴格按照規(guī)定時間段進行優(yōu)化，而帶有軟時間窗的路徑優(yōu)化算法允許早于或晚于規(guī)定的時間段，但需要承擔相應(yīng)的時間窗懲罰成本。Cordeau 等［95］利用禁忌搜索算法實現(xiàn)了帶時間窗的車輛路徑優(yōu)化。王超等［96］基于回溯搜索優(yōu)化算法，實現(xiàn)了帶時間窗和同時送取貨的路徑優(yōu)化。柴獲等［97］基于蟻群算法，提出了綜合考慮目標、時間窗和信息素等信息的狀態(tài)轉(zhuǎn)移概率公式，實現(xiàn)了雙目標帶時間窗的路徑優(yōu)化問題。

綜上所述，由于軍事活動和救災(zāi)活動等要求，需要多裝備同時在野外環(huán)境下進行運作，因此針對其路徑特點進行相應(yīng)的路徑優(yōu)化，可以保證高效的完成目標，但目前針對多裝備的路徑優(yōu)化問題研究相對不足。多裝備在野外環(huán)境進行運作時，勢必會遇到動力學約束改變等問題，如前車經(jīng)過后土壤更為夯實、相鄰車輛在轉(zhuǎn)彎時的相互影響和前車行駛速度等影響，當前對于多裝備的動力學研究較少，但其是多種裝備共同行駛時亟待解決的問題。

5 結(jié)論與展望

復(fù)雜野外環(huán)境下的路徑優(yōu)化是開展軍事活動、實現(xiàn)軍事裝備運行的關(guān)鍵技術(shù)。野外環(huán)境不同于既有道路路徑優(yōu)化，其存在多種影響裝備運行的障礙物、威脅物和野外坑洼。本文就野外環(huán)境下的建模方法和路徑優(yōu)化方法進行了調(diào)研與總結(jié)，對各方法的適用環(huán)境與利弊進行了闡述，針對野外路徑的路徑優(yōu)化提出以下幾點展望：

（1）智能性。目前人工智能方法在其他領(lǐng)域受到學者們的廣泛應(yīng)用，是今后路徑優(yōu)化算法的研究方向之一。由于人工智能方法需要大量的數(shù)據(jù)樣本支撐，在野外環(huán)境中應(yīng)用存在一定的難度，因此需要建立開源的野外環(huán)境的數(shù)據(jù)集。

（2）動力學耦合。對于在野外環(huán)境運行的裝備，其受到多方面因素的影響，如地面平整度、土壤質(zhì)地和氣候天氣等，環(huán)境較城市道路更為復(fù)雜，裝備在行駛過程中可能會發(fā)生顛覆、傾倒等現(xiàn)象，因此需要將動力學約束納入路徑優(yōu)化模型，在路徑優(yōu)化過程中需要保證裝備的正常行駛，可以通過建立路徑優(yōu)化與地形力學相耦合的平臺，進一步對路徑進行優(yōu)化評估。

（3）協(xié)同性和異構(gòu)性。為完成特定的軍事任務(wù)或生產(chǎn)任務(wù)等，往往需要多個裝備協(xié)同運行，同時需要多種類型裝備，如戰(zhàn)斗車輛與運輸車輛共同運行。目前對于野外環(huán)境下多裝備路徑優(yōu)化研究較少，同時多裝備的路徑優(yōu)化約束更多，問題更為復(fù)雜，會產(chǎn)生相應(yīng)動力學問題，因此需要深入開展多裝備路徑優(yōu)化問題研究。