基于Bekker 理論改進遺傳算法的野外路徑優化方法研究

常寧東，馮 春，2*，程鵬達，朱心廣，李玉瓊，2*

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

1 引言

由于野外環境中充滿未知因素，野外行駛的裝備往往會受到地面土壤特性、地面起伏和障礙物等的影響，復雜的環境給裝備的行駛和安全帶來威脅［1］。野外環境下路徑優化需要根據預先得到的野外環境信息，考慮環境對于裝備的約束等，最終得到一條從起點到終點的安全、高速的優化路徑［2］。

目前對于既有道路的路徑優化算法已較為成熟，但野外環境下存在著多種未知因素，相對于城市道路，在野外環境行駛的裝備往往受到土壤力學特性的影響［3］。在較為泥濘的道路上，車輛容易發生侵陷和側滑等危險，因此路徑規劃是裝備在野外環境下進行軍事活動的重要前提。

近些年來路徑優化算法高速發展，目前較為成熟的路徑優化算法主要有圖搜索法、隨機采樣法、人工勢場法和智能優化算法［4］。基于圖搜索法的優化算法需要事先建立好環境柵格圖，目前經典的圖搜 索法主要有Dijkstra 算 法［5］、A*算法［6］、D*算法［7］及其推廣。隨機采樣法在優化空間模型的基礎上進行隨機選樣，能夠適用于較為復雜的環境，目前主要包括概率地圖法（Probabilistic Roadmap Method，PRM）［8］、快速搜索隨機樹 法（Rapidly-exploring Random Trees，RRT）［9］以及其推廣算法。人工勢場法（Artifical Potential Field，APF）［10］基于電荷在電場中的運動原理，將車輛視為勢能場中的質點，車輛和障礙物帶相同電荷相斥，與終點帶異種電荷而相吸。智能優化算法是基于一些自然規律而衍生的隨機搜索算法，如蟻群算法［11］、遺傳算法［12］和神經網絡算法［13］等。

目前的路徑算法較少考慮土壤與車輛的相互作用，最具有代表性的為北約參考機動模型［14］（NATO Reference Mobility Model，NRMM）以及下一代北約機動參考模型［15］（Next Generation NATO Reference Mobility Model，NGNRMM），利用地面力學對裝備與地形軟土之間的交互進行評估，從而得到軟土對裝備機動性的影響。本文基于Bekker 地形力學理論［16］，對遺傳算法進行優化，提出了一種以時間成本為代價的高效路徑優化算法，以滿足車輛在野外復雜環境下的高速、安全和穩定行駛的要求。該算法綜合考慮了障礙物、野外土壤和環境威脅等約束條件，同時考慮了車輛的行駛性能和運動特性等，具有計算結果準確和計算速度快的特點，能夠為野外環境下的車輛提供安全可靠的行駛路徑。

2 輪胎地面力學模型及運動學分析

在野外行駛的輪式車輛，往往因需要克服土壤的塑性變形而受到土壤帶來的阻力。除此之外，行駛過程中還需克服外界環境和車輛內部帶來的阻力，外部阻力主要包括轉向阻力、坡度阻力和風阻力等；內部阻力主要包括車輛內部軸承等零件轉動產生的摩擦阻力。

2.1 輪式車輛行駛滾動阻力

輪式車輛在野外行駛過程中產生的土壤阻力主要是由于土壤在豎向產生了變形，圖1 為車輛輪胎在行駛過程中與土壤相接觸時的計算簡圖，其中z代表車輛在土壤當中的沉陷量，D為輪胎的直徑，FT為車輛牽引力，a為車輪與土壤接觸長度的水平投影。

圖1 輪胎與土壤相接觸時計算簡圖Fig.1 Calculation diagram of tire in contact with soil

由于輪胎和土壤之間相互擠壓，土壤將會對輪胎產生壓力，在輪胎外緣一微小面積上受到的作用力大小dFQ為：

其中：p為土壤受到輪胎支撐面積上的壓力，b為輪胎的寬度，ds為輪胎外緣上微小部分的面積，dFQ為此輪胎微小部分受到土壤給予的作用力。

由于輪胎所受到的徑向荷載W與輪胎所受到的土壤作用力合力相平衡，同時聯立式（1），則有：

在水平方向上，輪胎所受到的滾動摩擦力為：

基于Bekker 地形力學理論［17］，土壤受到輪胎支撐面積上的壓力p與沉陷量z之間有：

其中：Kc為土體粘聚模量，Kφ為摩擦角模量。

將式（4）代入式（2），則此時輪胎所受到的徑向荷載W為：

根據圖1 中相似關系可以得到：

將式（5）～（7）聯立，可得：

根據式（9）可得，沉陷深度z為：

同時，結合式（3）和式（4）可得：

結合式（10）和式（11）可得車輛所受滾動摩擦力為：

2.2 輪式車輛行駛內部阻力

車輛內部行駛阻力與車輛重力之比為內部阻力系數，此系數由車輛自身屬性所決定，與土壤特性無關，則有：

其中：Ffn為內部阻力，fg為內部阻力系數，G為車身自重。

2.3 輪式車輛行駛風阻力

由于野外環境較為空曠，且軍事車輛往往迎風面積較大，因此會受到一定的風阻力，其大小為：

其中：kh為迎風系數，ph為動態風壓，Ah為迎風面面積，v為車速。

2.4 輪式車輛行駛爬坡阻力

對于路面有起伏的野外環境，車輛行駛過程中往往還會受到爬坡阻力的影響，其大小為：

其中，α為坡面角度。

2.5 輪式車輛行駛加速度

對于半徑為r的車輪，其受到發動機給予的扭矩為Tt，則其驅動力Ft為：

由于驅動扭矩受到車輛內部傳動系統的傳動比和傳動效率的影響，因此依據機械原理，可得：

其中：Ttq為發動機的轉矩，ig為變速器的傳動比值，i0為主減速器的傳動比值，ηT為傳動系統的機械效率。

聯立式（16）和式（17）可得：

由于牽引力為土壤給予輪胎的切向作用力，依據摩爾庫倫準則，牽引力最大值不能超過土壤最大剪切強度。

其中：c為土壤粘聚力，φ為土壤內摩擦角，σ為土壤受到正應力。

根據上述求得車輛牽引力和行駛阻力，可以得到車輛行駛過程中受到合力F合，結合牛頓第二定律，可得車輛行駛時加速度為：

其中：F合為車輛行駛過程中所受合力，m為車輛質量，a為車輛加速度。

3 基于改進遺傳算法的路徑優化方法

3.1 遺傳算法概述

遺傳算法［18］是由J Holland 提出的一種模擬自然界遺傳和進化的全局優化算法，該算法運算較為簡單且收斂速度快，不受搜索空間的限制，可以解決多種復雜、非線性的問題。該算法模擬基因的遺傳，首先需要把問題轉化為基因的編碼問題，之后隨機生成一定規模的初始種群，再結合適應度函數對種群中的基因序列進行選擇、交叉、變異等操作，從而對種群中的基因序列進行優化，之后不斷迭代使得種群中的個體不斷進化，最終得到適應度最高的基因編碼，其流程圖如圖2。

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

3.2 基因編碼與種群初始化

本文采用整數編碼的形式構造初始染色體，組成染色體的基因為網格的各節點，因此生成的染色體編碼代表所經過的節點編號。假設生成尺寸為n×n的柵格地圖，節點編號則為1～n2，根據隨機方法生成一系列初始種群編碼，假定起點編號為1，終點編號為n2，則種群編碼為［1，…，Ni，Nj，…，n2］。

由于隨機生成的種群具有一定的離散性，會存在許多實際無法通過的路徑，從而浪費許多計算資源，耗費大量時間。因此本文在種群初始化時為其施加約束，在對下一個節點進行編碼時，此節點與上一個節點之間的路徑必須為可通行的。在生成節點i的下一個隨機節點i+1 時，判斷此時節點i與i+1 的連接情況，如果此時兩者路徑無法通行，則繼續進行循環，直到生成可以通行的節點為止，且保證經過節點不能重復。對于此約束共分為三種情況：

（1）當節點處于交點時，假設此時節點編號為i，則與其相連節點有兩個，為i-1/i+1 和i+n/i-n；

（2）當節點處于網格最外部的邊上時，假設此時節點編號為i，則與其相連節點有三個，為i-1、i+1 和i-n/i+n；

（3）當節點處于網格內部時，假設此時節點編號為i，則與其相連節點有四個，為i-1、i+1、i-n和i+n。

3.3 適應度函數與選擇操作

在生成初始種群后，首先計算各路徑通行所需要的時間，由于車輛行駛時會有加速運動，假設加速時為勻加速運動，因此在第i節點到第i+1 節點所需時間為：

其中：vi+1為行駛到節點i+1 的速度，vi為行駛到節點i的速度，ai+1為節點i+1 處的加速度，ti+1為從第i節點到第i+1 節點所需時間。

其中，xi+1為從第i節點到第i+1 節點所需距離。

聯立式（21）和式（22）可得：

為求得通行時間最短的路徑，此次適應度函數選取通行時間的倒數，當進行選擇后保留下適應度較大的染色體，此時即通行時間最短的路徑，適應度如下所示。

其中：Fj為第j個染色體的適應度；ti為通行各段路徑所需時間；e為一較小常量，以保證分母不為0，此次選取1×10-6。

該染色體在整個種群中的相對適應度為：

選擇方式采用輪盤賭選擇法［19］，當相對適應度大于選擇概率時，則保留當前個體進入下一代；當相對適應度小于選擇概率時，則淘汰當前個體。

3.4 交叉與變異操作

交叉操作［20］為遺傳算法中的重要操作，即將種群中的個體進行隨機配對，從而組合成一個新個體再進行有效搜索。本文采用雙點交叉的方式，即在兩個個體中隨機設置兩個交叉點，再根據交叉概率將兩個交叉點的部分進行交換，如圖3 所示。

圖3 雙點交叉Fig.3 Double dot cross

變異操作可以避免算法在尋優過程中過早收斂而得到局部最優解的弊端，可以為種群提供多樣性。在進行變異操作時，由于此時每個個體的編碼都為不重復的節點，無法采用傳統的生成一個隨機數進行替換，因此采用生成兩個隨機數，再隨機交換個體編碼中兩個節點順序的方式。

4 試驗與結果分析

4.1 區域土壤特性

土壤為一種土體顆粒、氣體和孔隙水三相組成的介質，但通常由于研究區域較大，對其微觀結構進行忽略，將土壤在宏觀上視為連續介質，并對其進行均勻化處理［21］。但實際上一片區域不同地點的土壤特性往往不相同，為更真實地模擬現場情況，此次計算時采用正態分布的形式對土壤性質進行考慮。

土壤的力學特性往往會對車輪侵入深度造成影響，因此當車輛在不同的土壤上行駛時，車輛會產生不同的加速度，本文選取黏土進行計算，如表1 所示，此試驗中選用平坦路面，因此忽略爬坡阻力的影響，根據土壤性質從而計算出車輛的加速度。

表1 土壤材料屬性Tab.1 Soil material properties

4.2 含障礙物的野外環境路徑優化

采用上述的基于Bekker 理論的優化遺傳算法對含障礙物的環境進行路徑優化，此次環境空間劃分網格數量為20×20，共設置兩障礙物，對于處于障礙物上的節點，采用時間取值為無窮大的方式進行權重賦值，改進遺傳算法的初始種群規模為1 000，最大迭代次數為1 000，最終路徑優化結果如圖4 所示，最終計算所得通行時間為7.647 3s。

由圖4 可知，該算法可以較好地避開障礙物，同時可以計算出車輛在變加速運動時行駛所需時間，該算法的優勢在于：（1）減少了計算規模，僅需要較小的初始種群規模；（2）通過對行駛時間的計算，能夠有效地避開障礙物的邊緣，從而達到安全行駛的目的；（3）考慮了土壤力學特性，能夠根據土壤特性進行較為精確的路徑優化。

圖4 含障礙物路徑優化Fig.4 Path optimization diagram with obstacle

4.3 含障礙物多屬性土壤的野外環境路徑優化

依據上述算法對含不同屬性土壤進行路徑優化，此次環境空間劃分網格數量為50×50，在路徑中設置障礙物，采用較大距離的方式實現障礙物的布置，取1×106m。環境大部分仍為黏土，在部分區域存在力學性能較差的砂土，材料屬性如表2 所示，由于設置為圓形區域，存在覆蓋一部分路徑的現象，對于覆蓋路徑大于網格長度一半的情況，即Lr＞認為此時節點i與i+1之間路徑為砂土；當覆蓋路徑小于網格長度一半，即，認為此時節 點i與i+1 之間路徑為黏土。

表2 軟土材料屬性Tab.2 Soft soil material properties

本次試驗選擇某小型國產車進行計算，車輛發動機排量為1 096 mL，最大轉矩取89 N·m，轉速為800～500 r/min，滿載總質量為1 000 kg，車輪滾動半徑為0.272 m，傳動系統的機械效率取90%，變速器的傳動比值取3.416，主減速器的傳動比值取4.388，迎風系數取0.3，迎風面積為2.5 m2。

最終路徑優化圖如圖5 所示，此最優路徑行駛所需時間為15.898 s。由于軟土部分力學性質較差，該區域的加速度相對正常土的加速度更小，最終求得的路徑避開了軟土區域。由結果可知，該算法模擬了野外環境下存在部分砂土的情況，同時考慮了土壤分布的非均勻性，較為真實地計算了野外環境下輪式車輛行駛的最優路徑。

圖5 含障礙物和軟土的路徑優化Fig.5 Path optimization with obstacles and soft soil

5 結論與展望

復雜野外環境下的路徑優化是高效開展軍事活動的重要前提，野外環境下的路徑優化區別于城市道路環境，其道路環境惡劣，存在多種影響車輛通行的障礙物、坑洼和坡度等，同時土壤特性會對車輛行駛速度產生影響。因此，本文基于Bekker 地形力學理論，考慮了土壤地面力學特性，提出了一種改進的遺傳算法路徑優化算法，滿足野外環境下車輛安全、高效行駛的要求，本文得到主要結論如下：

（1）本文基于Bekker 理論，建立了輪式車輛在野外環境行駛的運動學理論。通過對輪胎進行受力分析，得到了輪式車輛在野外環境下所受行駛阻力，建立了土壤特性與車輪受力的聯系，基于運動學分析，建立了土壤特性影響下的輪式車輛運動學方程，為野外環境路徑優化提供理論基礎。

（2）本文提出了一種高效的改進遺傳算法。考慮了節點之間的聯通性，建立了帶有約束的初始種群、以車輛行駛時間作為優化函數、結合土壤特性影響的輪式車輛運動學方程，得到了一種考慮了野外環境特征，保障車輛安全行駛的最優路徑。

（3）本文實現了障礙物和不同土壤特性影響下的野外車輛路徑優化。試驗結果表明，該算法考慮了野外環境下多種影響因素和車輛自身性能的影響，實現了受野外環境威脅的輪式車輛路徑優化，為野外環境下存在泥濘、坑洼和土坡等因素的路徑優化方法提供參考。

（4）軍事裝備存在多種履帶式車輛，本文建立的野外環境下輪式車輛路徑優化算法可以為履帶式車輛路徑優化提供參考。針對土壤力學特性對車輛的影響，后續研究可以采用數值模擬等方法得到更為精確的結果。本文實現了存在多種土壤的路徑優化，后續可以開展考慮降雨條件下的野外路徑優化算法研究。