非平坦環境下履帶機器人多目標路徑規劃方法研究

摘要：為實現非平坦環境下履帶機器人路徑規劃高效、安全、節能等運行目標，提出了一種改進的快速精英多目標遺傳算法（NSGA-Ⅱ）多目標路徑規劃方法。首先綜合分析非平坦環境下履帶機器人的作業需求，建立2.5D柵格環境模型簡化復雜的環境地圖；然后選取路徑長度短、能量消耗低和安全性高作為機器人路徑規劃子目標指標；最后通過8鄰域曼哈頓防碰撞算法改進柵格選擇方式避免機器人與障礙物柵格頂點碰撞，并在NSGA-Ⅱ算法中引入精英替換策略擴大種群規模，防止優良路徑基因流失，加速算法收斂。相較于多目標可變鄰域搜索（MOVNS）算法，所提方法規劃出的路徑在路徑長度上平均縮短9.02%、能耗上平均節省18.36%、危險率上平均降低7.28%，有助于提高非平坦環境下的路徑規劃質量。

關鍵詞：路徑規劃；非平坦環境；能量消耗；防碰撞；多目標優化

中圖分類號：TP242.6

Research on Multi-objective Path Planning Method for Tracked Robots under Non-flat Environments

ZHANG Daode LU Zijian ZHAO Kun YANG Zhiyong*

School of Mechanical Engineering，Hubei University of Technology，Wuhan，430068

Abstract： To achieve efficient， safe， and energy-saving operations of tracked robots under non-flat environments， an improved non-dominated sorting genetic algorithm Ⅱ（NSGA-Ⅱ） multi-objective path planning method was presented. Firstly， comprehensively analyzing the operational requirements of tracked robots under non-flat environments， a 2.5D grid environmental model was established. Secondly， short path length， low energy consumption， and high safety were selected as sub-objective criteria for path planning. Finally， the 8-domain Manhattan collision avoidance algorithm was employed to improve the grid selection method， avoiding collisions between robots and vertices. Additionally， the NSGA-Ⅱ algorithm introduced an elite replacement strategy to expand the population size， preventing the loss of excellent path genes and accelerating algorithm convergence. Compared to the multi-objective variable neighborhood search（MOVNS） algorithm， the proposed method plans paths with an average reduction of 9.02% in path length， an average energy savings of 18.36%， and an average decrease of 7.28% in danger rate， contributing to the enhancement of path quality under non-flat environments.

Key words： path planning; non-flat environment; energy consumption; collision-free; multi-objective optimization

0 引言

履帶機器人的履帶與地面接觸面積大、跨度長，相較于一般輪式機器人，具有越障能力強、運動平穩、不易打滑、爬坡能力強、不易傾翻及負載高等優勢，在礦道勘探、搜索救援、地質測繪和戰場偵察等領域具有廣闊的應用前景。但履帶機器人運動過程中將產生更大能耗，若與障礙物發生碰撞亦將產生更大的危害，因此，如何快速規劃一條安全有效、節能的路徑具有重要研究意義和實際應用價值。

路徑規劃質量的評價標準一般包括距離、能耗、安全性等因素。目前，關于最短距離路徑規劃的研究日趨完善，如Dijkstra、A*、蟻群等算法已經得到了廣泛應用，但是在非平坦環境下，最短距離的代價往往是高能耗，故低能耗路徑規劃逐漸成為研究熱點。SAAD等^［1］采用復合路由法改進貪心規劃算法，考慮地形土壤力學下的輪胎下沉效應，實現了非公路環境下的節能最短路徑。ZHANG等^［2］采用阿克曼轉向約束改進的A*算法，完成了離線狀態下的低能耗路徑規劃，但該算法存在實時性不足的問題。AHMAD等^［3］采用3D可見圖搜索法，完成了無人機在無人工廠場景下的無碰撞、低能耗路徑規劃。CONTRERAS等^［4］采用可見圖搜索法結合A*算法，實現了移動機器人在無人工廠環境下的低能耗路徑規劃，但其應用場景較為固定，在非平坦環境下的魯棒性不足。

為將固定環境下的低能耗路徑規劃推廣至普適環境下，部分學者基于路徑代價對低能耗路徑規劃開展研究。JONES等^［5］對當前最優路徑進行光滑變形采樣，更新自主船能耗代價函數，實現無碰撞、低能耗路徑規劃。WU等^［6］采用高度感知費馬螺旋的設計模式，利用精確的邊界源檢測地線距離，降低重力能耗代價函數，完成了三維自由曲面下的無碰節能路徑規劃。KYAW等^［7］通過改進的RRT*抽樣技術重構最大可接受估計代價狀態函數，規劃出一條無碰撞低能耗路徑。YOU等^［8］采用對偶協變哈密頓優化運動方法處理非凸代價函數，解決了蟻群算法易陷入局部收斂的問題，最終生成兼具時間短、能耗低的平滑路徑。LIU等^［9］引入能量鄰接矩陣作為代價函數，配合鄰接矩陣能耗準則，實現了低能耗路徑規劃，但該方法更新過程中存儲的數據容量較大，且運行過程繁瑣，效率不高。

此外，機器人完成運行任務過程中的安全性同樣是影響路徑規劃質量的重要指標。LIU等^［10］通過計算動能轉換和克服牽引力的能耗模型，結合A*算法控制機器人運行時間和速度，達到降低能耗的目的，但犧牲了機器人運行效率。MEJRI等^［11］設計了一款節能路徑規劃器，使得機器人在低速、不延長路徑的前提下規劃出低能耗路徑。SUN等^［12］引入限制功率與地形邊界約束方法，解決了復雜地形環境下機器人易發生傾覆的問題，確定最優的低能耗安全路徑。通過增加速度約束的能耗模型^［13-14］能夠實現低能耗路徑規劃，但限制速度的同時也增加了完成任務的時間成本，如何解決能耗與運行時間的平衡問題迫在眉睫。WEI等^［15］提出了一種在平坦環境下考慮能耗與運行時間的目標權重實時分配禁忌搜索法，實現了靜態場景下的最優路徑規劃，但動態場景下既定路徑會失效。SANGEETHA等^［16］針對實時場景動態目標，利用蟻群信息增強機制改進的動態綠色蟻群算法與優化元啟發算法，獲得了兼具路徑長度短、能耗低和時間短的目標路徑。DAS等^［17］采用改進EOPs進化算子增強改進的粒子群優化（improved particle swarm optimization， IPSO）算法的優化能力，使得無碰撞和路徑長度目標在集約化和多樣化間取得平衡，但該方法屬于單目標算法優化多目標問題，易產生權重分配不均或陷入局部最優的狀況。

在復雜多變的非平坦環境中，路徑規劃需要考慮路徑長度、能耗、安全性等多個目標指標，多目標算法相較于傳統單目標算法具備一定的優勢。SURESH等^［18］采用多目標遺傳算法—基于改進隨機優先搜索的多目標遺傳算法（multi-objective genetic algorithm based on modified random priority search， MRPS-MOGA）處理機器人規劃路徑運行安全性、距離與行駛時間長短、路徑平滑度和無碰撞五個子目標，求取最優路徑。在無人機領域，JUNG等^［19］考慮巡航節點間距、無人機速度、整機質量、航向角四個目標實現了無碰路徑規劃。AJEIL等^［20］引入局部搜索LS的混合多目標具有多功能行為的粒子群優化（particle swarm optimization with multi-functional behavior， PSO-MFB）算法對路徑長度、無碰撞和路徑平滑度三個目標進行優化，獲取最優無碰平滑路徑。上述研究均集中于路徑距離最短、安全性高、行駛時間短、路徑平滑等目標參數指標，但并未涉及機器人能耗指標。

為保證履帶機器人運行效率，需綜合考慮路面材質、粗糙程度、坡度變化以及動態障礙物的影響，建立以距離短、能耗低以及安全性高作為履帶機器人路徑規劃的目標準則，實現履帶機器人在多個目標指標共同作用下的最優路徑規劃。本文針對非平坦環境中不同路面粗糙程度、坡度變化以及動態障礙物，建立2.5D柵格地圖模型；選取路徑長度、能耗、安全性作為履帶機器人路徑規劃目標準則，建立多目標路徑規劃模型；提出一種基于8鄰域曼哈頓防碰撞搜索算法結合精英替換策略改進的NSGA-Ⅱ多目標優化算法對最優路徑進行求解，最后進行了軟件仿真與樣機實驗驗證。

1 目標函數建模

1.1 多信息2.5D柵格地圖

傳統柵格地圖是常見的地圖類型，具有易構建、表示、保存、計算以及位置唯一性的優勢。本文提出一種含有多信息的2.5D柵格地圖，如圖1所示，將復雜環境內的障礙物信息、路面材質以及坡度信息反映在地圖上，以優化傳統柵格地圖無法準確反映環境復雜程度的問題。

1.2 路徑規劃目標函數建模

1.2.1 路徑長度目標

傳統路徑規劃問題偏重于考慮最短距離，在柵格地圖上表示為最短幾何距離。路徑幾何長度Lpath如下：

Lpath=∑n－1i=1L（i，i+1）=∑n－1i=1（xi－xi+1）2+（yi－yi+1）2（1）

式中：n為路徑從起點至終點經過的總節點數；i為路徑中由起點至終點的任意一點，i=1，2，…，n；xi、yi分別為i點的橫縱坐標；L（i，i+1）為第i點至第i+1點間的距離。

但在非平坦實際環境中，機器人實際移動的路徑長度不能單純計算幾何距離，也需要考慮坡度θi對實際路徑長度產生的影響，如圖2所示。以圖2中第i+1柵格為例，機器人運行的幾何距離為

Li+1=（L（i，i+1）+L（i+1，i+2））/2（2）

由幾何關系知，幾何路徑長度與坡度角的余弦值之比為實際路徑長度，即第i+1點內的實際路徑長度fi+1為

fi+1=Li+1cos θi=L（i，i+1）+L（i+1，i+2）2cos θi（3）

由式（3）可知，機器人實際路徑應由三部分組成：

1）當機器人位于起點柵格內，實際路徑長度為

f1=L（1，2）2cos θ1

2）由第2點至第n-2點內的實際路徑長度為

∑n－2i=2fi=∑n－2i=2L（i，i+1）+L（i+1，i+2）2cos θi

3）當機器人位于目標柵格點內，實際路徑長度為

fn=L（n－1，n）2cos θn

綜上所述，路徑長度目標函數fL如下：

fL=∑ni=1fi=L（1，2）2cos θ1+L（n－1，n）2cos θn+

∑n－2i=2L（i，i+1）+L（i+1，i+2）2cos θi （4）

1.2.2 能耗目標

對履帶機器人進行受力分析，如圖3所示。

假設機器人勻速行駛，則由牛頓第二定律知

∑F=Ft－Ff－Fg－Fb－Fin=0（5）

其中，∑F為履帶機器人在平緩斜坡上勻速前進時所受的合力；Ff為機器人所受摩擦力；Fg為機器人所受重力分量；Fin為機器人內部傳動阻力，在機器人運動過程中一般為定值。機器人電機提供的總動力Fe為牽引力Ft與剎車制動力Fb之差，則有

Fe=Ft－Fb（6）

Fe=Ff+Fg+Fin=μimgcos θi+mgsin θi+Fin（7）

式中：m為履帶機器人總質量；g為重力加速度系數；μi、θi分別為第i柵格內相應的地面摩擦因數和坡度。

履帶機器人在運動過程產生的總能耗fE為

fE=FefL=（Ff+Fg+Fin）fL（8）

1.2.3 安全性目標

履帶機器人通過車載超聲波和激光雷達等傳感器實時定位與感知周圍環境，當機器人距離障礙物越近時越危險。通過危險率指標評價機器人的安全性，危險率越大的路徑安全性越低，則安全性目標函數fD為

fD=∑ni=1φ（i）=

∑ni=1∞""""""" L（i，obj）≤df

ds－dfL（i，obj）－dfdflt;L（i，obj）≤ds

0L（i，obj）gt;ds（9）

式中：φ（i）為危險率；L（i，obj） 為當前第i點與最近障礙物間的距離；df為機器人寬度的1/2；ds為機器人實現無碰撞的安全距離。

當機器人與障礙物間距小于機器人寬度的1/2，即L（i，obj）≤ df時，表示禁止通行，危險率為∞；當機器人與障礙物間距大于機器人寬度的1/2但小于預設的安全距離，即dflt; L（i，obj）≤ds時，表示存在通行危險，且隨著L（i，obj）的增大而逐漸減小，危險率取值范圍為［1， + ∞）；當機器人與障礙物間距大于預設安全距離，即L（i，obj）gt; ds時，表示機器人允許通行，危險率φ（i）=0。

1.2.4 多目標函數

本文采用最小評價函數，將三個子目標集成為多目標模型進行求解，如下：

minx∈ΩF（x）=（fL（x），fE（x），fD（x））T（10）

式中：fL為路徑長度子目標；fE為能量消耗子目標；fD為安全性子目標；x為決策路徑；F（x）為目標路徑矩陣。當且僅當決策路徑x*不被其他任何解支配，稱x*為Pareto最優路徑，由所有Pareto最優解構成Pareto解集。

2 改進的NSGA-Ⅱ多目標算法

非平坦環境中履帶機器人進行路徑規劃時，既要滿足運行距離短、能耗少的要求，又要求安全性高。針對多目標優化問題，本文采用改進的多目標優化算法NSGA-Ⅱ進行求解。

2.1 基于8鄰域曼哈頓防碰撞搜索算法

本文將8鄰域搜索機制與曼哈頓思想結合，提出8鄰域曼哈頓防碰撞搜索算法，其柵格選擇流程如下：當障礙物處于偶數柵格且機器人與障礙物距離為1單位柵格時，將起點 start 到該柵格的路徑長度為2單元柵格且與障礙物柵格相鄰的柵格標記為不可通行區域，如圖4中柵格3、5為不可通行柵格，編號1、2、6、7、8的柵格標記為可通行區域；當障礙物處于奇數柵格時，將該奇數柵格標記為不可通行區域，其余柵格記為可通行區域。當運動到下一柵格時，重新進行機器人是否可通行判斷。當機器人以圖4中start柵格中心位置前往5號柵格中心位置時，若直接由start斜向運行至5號柵格，則存在與右側障礙物柵格頂點發生碰撞的可能；若用本文所提8鄰域曼哈頓防碰撞搜索算法，由start先向下運行至6號柵格，再向右運行抵達 5號柵格，則能夠有效規避頂點碰撞的問題。圖5為8鄰域曼哈頓防碰撞搜索算法流程圖。

2.2 基于精英替換策略的迭代機制

在多目標優化算法中，將可通行柵格視為基因，將每條由可通行柵格連接而成的路徑視為種群個體。對種群執行遺傳操作能持續生成新個體，但新個體中存在摻雜劣質個體的問題，需要對優秀個體實施保護措施，使得優秀的基因在進化過程中保持迭代，同時擴大初始種群規模以避免種群初始化不充分、隨機性不足而導致算法陷入局部最優解的問題。如圖6所示，精英替換策略先擴大原種群規模，再通過非支配排序從父代種群中篩選出K個最優解，通過擁擠度排序替換子代中的K個劣質解，最后淘汰剩余個體，直至種群規模達到與原種群規模一致。

2.3 算法流程

本文設計的改進多目標優化算法NSGA-Ⅱ路徑規劃方法流程如下：

1）采用2.5D柵格法進行非平坦環境建模，確定子目標函數，初始化參數，獲取初始化種群Pt及最優路徑集合U。

2）開始柵格選擇，依據輪盤對賭法結合8鄰域曼哈頓防碰撞搜索算法選定可行柵格，直至終點或路徑不通。

3）對當前種群Pt執行交叉、變異操作，產生與其個數相同的子代種群Qt，將當前種群Pt與子代種群Qt合并，記為Rt。

4）對Rt進行快速非支配排序，通過式（4）、式（8）、式（9）計算個體的子目標函數值，根據非支配排序等級，依次將各等級個體加入下一種群Pt+1中，直到當前等級個體不能全部放入時對當前等級進行擁擠度排序，并將擁擠距離較大的個體加入下一種群Pt+1中，直到種群規模達到與Pt一致時停止。淘汰剩余解。

5）將父代種群Pt第一層的K個優質解，替換子代種群Pt+1中最后一層的K個劣質解。更新最優路徑集合U。對于排序后的第一層路徑u，如果u對集合U來說是非支配的，則加入集合U，并刪除U中被u所支配的路徑。

6）更新迭代次數，t←t+1，當達到最大迭代次數時結束迭代，否則返回步驟2）。

7）輸出最終路徑集合。依據式（6）計算路徑評價函數值，綜合各子目標，取最小評價函數輸出為最終路徑集。

3 實驗結果與分析

為驗證本文方法的有效性，采用軟件仿真與樣機實驗相結合的方式進行實驗驗證，編程環境為MATLAB 2022a。

3.1 仿真實驗

多目標NSGA-Ⅱ優化算法是一種依賴先驗參數設置的算法。設置合理的種群初始化、交叉變異概率能夠提高算法性能和收斂能力，同時避免陷入局部最優解的問題。本文將初始種群Pt設置為50、交叉概率Pc設置為0.75、變異概率Pm設置為0.05、迭代次數設置為50。

3.1.1 不同規格靜態環境地圖

設置柵格地圖規格分別為10 m×10 m、20 m×20 m、30 m×30 m，地圖中隨機生成黑色柵格障礙物，設置環境復雜度均為4×5（即摩擦因數共4種：0.2、0.4、0.6、0.8；坡度等級共5種：-45°、-30°、0°、30°、45°，對應圖1中顏色由深藍到深綠），分別采用改進的NSGA-Ⅱ多目標算法與MOVNS多目標搜索算法^［21］進行對比實驗。

每種算法分別進行3次獨立重復實驗，圖7中紅色（R1）、粉色（R2）、黃色（R3）三條路徑均為Pareto解集U中的最優路徑。以圖7a為例，R1每個節點的8鄰域內累積出現障礙物11次，均低于R2（13次）、R3（14次），由式（9）計算可知R1為解集U中安全性最高的路徑；粉色路徑（R2）經過代表下坡的藍色柵格6次，R1與R3均為5次，由式（8）計算可知R2為解集U中能耗最低的路徑；R3經過5次代表平地的白色柵格均高于R1（2次）、R2（4次），由式（4）計算可知，R3為解集U中路徑長度最短的路徑；棕色路徑為MOVNS算法所得路徑。結合圖8a～圖8c中的路徑規劃實驗數據可知，相較于R1、R2路徑，R3路徑長度最短但能耗最高，其中R2能耗最低但長度最長，R1則較為均衡。由表1知，本文算法隨著地圖規格的擴大，Pareto最優解集U中最優路徑長度由56.5977 m漲至751.1845 m；能耗由861.4774 J漲至1 581 435 J；危險率由98.67%漲至131%。

考慮本實驗有3種地圖規格以及3個子目標指標，為便于說明，本節重點討論最優路徑集U中具有代表性的極值路徑相較于MOVNS算法的提升率，驗證本文算法所得最優路徑集合U相較于MOVNS算法在整體性能上的優越性。以10 m×10 m地圖規格為例，最優路徑集合U中路徑R3具有最短路徑長度54.6415 m、最高能耗888.7501 J；R2具有最長路徑長度58.9240 m、最低能耗842.4329 J；MOVNS算法所得路徑長度為57.2912 m、能耗為1105.9536 J。由于R2路徑長度相較于MOVNS算法延長了1.6328 m，可知相較于MOVNS算法，路徑長度最小提升率為-2.85%，R2路徑的能耗相較于MOVNS減少了263.5207 J，可知能耗最大提升率為23.83%；由路徑R3知，相較于MOVNS算法，路徑長度縮短了2.6497 m，能耗減少了217.2035 J，故路徑長度最大提升率為4.62%，能耗最小提升率為19.64%。依次對三種地圖規格下的路徑長度、能耗、危險率三個目標分別進行量化計算，得到圖8d、圖8 e所示提升率曲線，分析后可得以下結論：在同一最優路徑集合U中，本文算法路徑長度與能耗成反比，即縮短路徑長度將消耗更多能量、降低能耗將導致路徑長度增加；在不同地圖規格下，本文算法相較于MOVNS算法的優化能力隨著地圖規格的擴大而提升，路徑長度最多縮短9.27%、能耗最多節省30.87%、危險率降低15.28%。

3.1.2 不同復雜程度的環境地圖

為了進一步驗證本文算法在具有多級摩擦因數和坡度的復雜環境下的適應性，在上節中靜態20 m×20 m地圖規格的4×5環境復雜度下，增加5×7環境（五級摩擦因數：0.2、0.4、0.6、0.8、1.0；七級坡度：-45°、-30°、-15°、0°、15°、30°、45°）以及10×9環境（十級摩擦因數：0.1、0.2、0.3、0，4、0.5、0.6、0.7、0.8、0.9、1.0；九級坡度：-60°、-45°、-30°、-15°、0°、15°、30°、45°、60°）。在上節的基礎上增設不同復雜度的環境，以驗證本文算法在更高復雜度環境下的適應性與有效性。

圖9a中球體代表不同環境復雜度下，本文算法所得最優路徑集U中的路徑（X軸表示路徑長度，Y軸表示能量消耗，Z軸表示危險率）。圖9b～圖9d分別為圖9a在三個坐標面上的投影。

由表2可知：隨著環境復雜度的提升，本文Pareto最優路徑集合U中路徑各子目標指標均值呈現長度遞增、能耗遞減、危險率遞減的趨勢。

綜合分析圖9以及表2，可得到以下結論：①隨著環境復雜度的提升，本文最優路徑集合U在距離目標上由4×5環境下的235.37 m提高至10×9環境下的244 m；但在能耗目標上由4×5環境下的489.29 kJ減至10×9環境下的141.69 kJ，證明了本文算法的能耗模型以及精英替換策略改進的有效性；②本文算法在危險率目標上體現為路徑長度越長，伴隨能耗降低的同時，危險率也將降低，且隨著環境復雜度的提升，危險率進一步降低，由125.4降低至120.55，證明了本文曼哈頓防碰撞搜索機制的有效性。

綜上所述，本文算法能夠在不同環境復雜度的地圖中規劃出最優路徑。

3.1.3 多種障礙物占比仿真結果分析

為了進一步驗證本文算法在安全性問題上的有效性，在3.1.2節中10×9地圖環境的基礎上，設置不同數量障礙物占全地圖比例分別為15%、20%、25%、30%、35%、40%的環境，將本文算法所得最優路徑解集U中的均值與MOVNS以及改進的A*算法^［22］進行對比。

隨著障礙物密度由占環境總柵格數的15%增長到40%，本文算法所得路徑長度增加了23.11%，能耗增加了32.58%，危險率增加了24.07%。但由圖10可知，本文算法的增長幅度遠小于MOVNS算法和改進A*算法的增幅，說明本文算法能夠有效地規避障礙物，適應障礙物密集的環境。

3.2 樣機實驗與分析

3.2.1 履帶機器人平臺介紹

本文使用的履帶機器人兩側履帶由獨立電機驅動，通過速差進行轉向，履帶機器人移動平臺如圖11所示。機器人通過激光傳感器提取包含坡度信息的點云地圖，視覺傳感器識別地面材質的摩擦因數，傳入履帶機器人控制系統。履帶機器人控制系統由NVIDIA TX2主板接受傳感器數據并進行配準、柵格化處理，完成2.5D柵格地圖構建、定位和路徑規劃任務，并向控制執行部分的控制器下達運動指令；控制執行部分的控制器為TrongLong M8控制板，主要負責接受運動指令并完成具體運動任務。

前文中進行了多個仿真實驗，其中摩擦因數與坡度角均為主觀設置的理想值。為更好地證明所提算法的有效性，本文將履帶機器人樣機在兩種不同復雜度、不同規模的實驗場景下進行測試。

在實驗測試場景中，通過8鄰域曼哈頓防碰撞算法選擇可通行柵格節點，并結合相應柵格的路面摩擦因數和坡度系數，由式（4）計算路徑長度目標；在所得長度目標的基礎上，通過式（8）計算實際運動過程中產生的能耗值；通過激光傳感器得到與障礙物之間的距離信息，并由式（9）計算危險率目標。最后通過改進的NSGA-Ⅱ算法進行50次迭代輸出Pareto最優路徑。將最優路徑的長度目標值、能耗目標值、危險率目標值分別與MOVNS算法和改進的A*算法進行比較。

3.2.2 實驗場景一下的算法有效性驗證

圖12所示為測試履帶機器人多目標路徑規劃實驗場景一，由4片地勢顛簸的草地和若干不同材質的道路組成，場景規模為80 m×80 m，場景中的雕塑、自行車以及路障組成不可跨越的障礙物。障礙物信息、路面信息（路面摩擦因數μ為實際測量值，地面坡度θ為測量值的均值）以及場景中起點位置與終點位置均預先已知。

履帶機器人分別采用MOVNS算法、改進的A*算法及本文改進的NSGA-Ⅱ算法進行路徑規劃，如圖13所示。

由圖13可知，三種規劃算法均能夠成功規劃出一條從起點至終點的安全無碰路徑。本文算法相較于MOVNS算法和改進的A*算法具有更短的路徑長度、更低的能耗、更低的危險率。為了提高實驗的準確性，進行10次獨立重復實驗并分別記錄三種算法的三個子目標參數，均值見表3。

根據表3中數據對實驗結果進行定量分析，本文算法與MOVNS算法相比，平均路徑長度縮短了8.26%，平均能耗降低了16.67%，平均危險率降低了6.61%；與改進的A*算法相比，平均路徑長度縮短了6.88%，平均能耗降低了18.03%，平均危險率降低了13.04%。這說明本文改進的NSGA-Ⅱ算法在環境信息已知的靜態環境中能夠高效完成多目標路徑規劃任務，且所規劃路徑優于MOVNS算法與改進的A*算法。

3.2.3 實驗場景二下的算法有效性驗證

履帶機器人多目標路徑規劃實驗場景二為某塊尚未開發的荒地（100 m×100 m），由石塊、草地以及土壤組成的地形，石塊為不可跨越的障礙物，土壤地形中存在坡度分布不均以及摩擦因數不同的問題，本文經過測試得到坡度值與地形摩擦因數，如圖14a所示，圖14b為簡化信息圖。

圖15為采用MOVNS算法、改進的A*算法以及本文算法分別進行路徑規劃的實驗對比圖，分別進行10次獨立重復實驗所得的路徑規劃實驗數據見表4。

根據表4中數據對實驗結果進行定量分析，本文改進的NSGA-Ⅱ算法與MOVNS算法相比，平均路徑長度縮短了9.02%，平均能耗降低了18.36%，平均運行時間減少了8.25%，平均危險率降低了7.28%；與改進的A*算法相比，平均路徑長度縮短了7.05%，平均能耗降低了20.04%，平均危險率降低了15.71%。這說明本文算法在坡度分布不均的復雜環境下，相較于MOVNS算法與改進的A*算法，具有更好的適應能力。

3.2.4 結果分析

在實驗場景一中，場景規模為80 m×80 m，且地形相對規整、坡度變化較緩，實驗場景二規模為100 m×100 m，且地形更復雜、坡度以及路面摩擦因數變化較大，兩個場景中本文算法分別相較于MOVNS算法以及A*算法的提升率如圖16所示。

由圖16可知，實驗場景二相較于實驗場景一具有更大的地圖規模、更復雜的路面材質以及更多的坡度變化，相較于MOVNS算法與改進的A*算法，實驗場景二的提升率高于實驗場景一，這一結論驗證了仿真實驗（3.1.1節與3.1.2節）結論的有效性，即本文算法在面對更大地圖規格以及更大環境復雜程度的應用場景時具有較好的適應性。

4 結語

本文提出的基于精英替換策略改進的NSGA-Ⅱ多目標算法能通過迭代完成路徑長度、能量消耗、危險率三個子目標指標綜合考慮的多目標路徑規劃，結合最小化目標模型求得Pareto最優路徑集合和Pareto最優解。通過2.5D柵格模型簡化了復雜環境地圖，并減小計算量；通過8鄰域曼哈頓防碰撞算法改進柵格選取機制，強化規避障礙物的能力，降低危險率；利用精英替換策略擴大種群規模，防止優秀的路徑基因的遺失，加速算法收斂。實驗結果表明，與MOVNS算法和改進的A*算法相比，本文算法在不同地圖規模、不同復雜程度環境以及不同障礙物占比環境中具有更好的性能。

參考文獻：

［1］ SAAD M， SALAMEH A I， ABDALLAH S， et al. A Composite Metric Routing Approach for Energy-efficient Shortest Path Planning on Natural Terrains［J］. Applied Sciences， 2021， 11（15）：6939.

［2］ ZHANG Haojie， ZHANG Yudong， LIU Chuankai， et al. Energy Efficient Path Planning for Autonomous Ground Vehicles with Ackermann Steering［J］. Robotics and Autonomous Systems， 2023， 162：104366.

［3］ AHMAD Z， ULLAH F， TRAN C， et al. Efficient Energy Flight Path Planning Algorithm Using 3-D Visibility Roadmap for Small Unmanned Aerial Vehicle［J］. International Journal of Aerospace Engineering， 2017， 2017（1）：2849745.

［4］ CONTRERAS J D， MARTNEZ F S， FREDY H M S. Path Planning for Mobile Robots Based on Visibility Graphs and A* Algorithm［C］∥Seventh International Conference on Digital Image Processing（ICDIP 2015）. Los Angeles， 2015：96311J.

［5］ JONES D， HOLLINGER G A. Planning Energy-efficient Trajectories in Strong Disturbances［J］. IEEE Robotics and Automation Letters， 2017， 2（4）：2080-2087.

［6］ WU Chenming， DAI Chengkai， GONG Xiaoxi， et al. Energy-efficient Coverage Path Planning for General Terrain Surfaces［J］. IEEE Robotics and Automation Letters， 2019， 4（3）：2584-2591.

［7］ KYAW P T， LE A V， VEERAJAGADHESWAR P， et al. Energy-efficient Path Planning of Reconfigurable Robots in Complex Environments［J］. IEEE Transactions on Robotics， 2022， 38（4）：2481-2494.

［8］ YOU Bo， LI Zhi， DING Liang， et al. A New Optimization-driven Path Planning Method with Probabilistic Completeness for Wheeled Mobile Robots［J］. Measurement and Control， 2019， 52（5/6）：317-325.

［9］ LIU Jing， LI Zhaojun， HE Liping， et al. Energy Efficient Path Planning for Indoor Wheeled Mobile Robots［C］∥2020 Global Reliability and Prognostics and Health Management. Shanghai， 2020：1-7.

［10］ LIU Shuang， SUN Dong. Minimizing Energy Consumption of Wheeled Mobile Robots via Optimal Motion Planning［J］. IEEE/ASME Transactions on Mechatronics， 2014， 19（2）：401-411.

［11］ MEJRI E， KELOUWANI S， DUBE Y， et al. Energy Efficient Path Planning for Low Speed Autonomous Electric Vehicle［C］∥2017 IEEE Vehicle Power and Propulsion Conference（VPPC）. Belfort， 2017：1-6.

［12］ SUN Zheng， REIF J H. On Finding Energy-minimizing Paths on Terrains［J］. IEEE Transactions on Robotics， 2005， 21（1）：102-114.

［13］ MEI Yongguo， LU Y H， HU Y C， et al. Energy-efficient Motion Planning for Mobile Robots［C］∥IEEE International Conference on Robotics and Automation. New Orleans， 2004：4344-4349.

［14］ TOKEKAR P， KARNAD N， ISLER V. Energy-optimal Trajectory Planning for Car-like Robots［J］. Autonomous Robots， 2014， 37（3）：279-300.

［15］ WEI Hongxing， WANG Bin， WANG Yi， et al. Staying-alive Path Planning with Energy Optimization for Mobile Robots［J］. Expert Systems with Applications， 2012， 39（3）：3559-3571.

［16］ SANGEETHA V， KRISHANKUMAR R， RAVICHANDRAN K S， et al. Energy-efficient Green Ant Colony Optimization for Path Planning in Dynamic 3D Environments［J］. Soft Computing， 2021， 25（6）：4749-4769.

［17］ DAS P K， JENA P K. Multi-robot Path Planning Using Improved Particle Swarm Optimization Algorithm through Novel Evolutionary Operators［J］. Applied Soft Computing， 2020， 92：106312.

［18］ SURESH K S， VENKATESAN R， VENUGOPAL S. Mobile Robot Path Planning Using Multi-objective Genetic Algorithm in Industrial Automation［J］. Soft Computing， 2022， 26（15）：7387-7400.

［19］ JUNG S. Development of Path Planning Tool for Unmanned System Considering Energy Consumption［J］. Applied Sciences， 2019， 9（16）：3341.

［20］ AJEIL F H， IBRAHEEM I K， SAHIB M A， et al. Multi-objective Path Planning of an Autonomous Mobile Robot Using Hybrid PSO-MFB Optimization Algorithm［J］. Applied Soft Computing， 2020， 89：106076.

［21］ HIDALGO-PANIAGUA A， VEGA-RODRGUEZ M A， FERRUZ J. Applying the MOVNS（Multi-objective Variable Neighborhood Search） Algorithm to Solve the Path Planning Problem in Mobile Robotics［J］. Expert Systems with Applications， 2016， 58：20-35.

［22］ 趙江， 張巖， 馬澤文， 等. 對AGV路徑規劃A星算法的改進與驗證［J］. 計算機工程與應用， 2018， 54（21）：217-223.

ZHAO Jiang， ZHANG Yan， MA Zewen， et al. Improvement and Verification of A-star Algorithm for AGV Path Planning［J］. Computer Engineering and Applications， 2018， 54（21）：217-223.

（編輯 陳 勇）

作者簡介：張道德，男，1973 年生，教授、博士研究生導師。研究方向為智能控制系統。E-mail：hgzdd@126.com。

楊智勇*（通信作者），男，1987 年生，副教授。 研究方向為機器人技術。E-mail：yzy017@126.com。

本文引用格式：張道德，盧子健，趙坤，等.非平坦環境下履帶機器人多目標路徑規劃方法研究［J］. 中國機械工程，2025，36（2）：305-314.

ZHANG Daode， LU Zijian， ZHAO Kun， et al. Research on Multi-objective Path Planning Method for Tracked Robots under Non-flat Environments［J］. China Mechanical Engineering， 2025， 36（2）：305-314.

基金項目：國家自然科學基金（51907055，52075152）；湖北省農機購置與應用補貼資金（HBSNYT202213）