非平坦環(huán)境下履帶機器人多目標(biāo)路徑規(guī)劃方法研究

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

關(guān)鍵詞：路徑規(guī)劃；非平坦環(huán)境；能量消耗；防碰撞；多目標(biāo)優(yōu)化

中圖分類號：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 引言

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

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

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

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

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

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

1 目標(biāo)函數(shù)建模

1.1 多信息2.5D柵格地圖

傳統(tǒng)柵格地圖是常見的地圖類型，具有易構(gòu)建、表示、保存、計算以及位置唯一性的優(yōu)勢。本文提出一種含有多信息的2.5D柵格地圖，如圖1所示，將復(fù)雜環(huán)境內(nèi)的障礙物信息、路面材質(zhì)以及坡度信息反映在地圖上，以優(yōu)化傳統(tǒng)柵格地圖無法準(zhǔn)確反映環(huán)境復(fù)雜程度的問題。

1.2 路徑規(guī)劃目標(biāo)函數(shù)建模

1.2.1 路徑長度目標(biāo)

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

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

式中：n為路徑從起點至終點經(jīng)過的總節(jié)點數(shù)；i為路徑中由起點至終點的任意一點，i=1，2，…，n；xi、yi分別為i點的橫縱坐標(biāo)；L（i，i+1）為第i點至第i+1點間的距離。

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

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

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

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

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

1）當(dāng)機器人位于起點柵格內(nèi)，實際路徑長度為

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

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

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

3）當(dāng)機器人位于目標(biāo)柵格點內(nèi)，實際路徑長度為

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

綜上所述，路徑長度目標(biāo)函數(shù)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 能耗目標(biāo)

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

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

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

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

Fe=Ft－Fb（6）

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

式中：m為履帶機器人總質(zhì)量；g為重力加速度系數(shù)；μi、θi分別為第i柵格內(nèi)相應(yīng)的地面摩擦因數(shù)和坡度。

履帶機器人在運動過程產(chǎn)生的總能耗fE為

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

1.2.3 安全性目標(biāo)

履帶機器人通過車載超聲波和激光雷達等傳感器實時定位與感知周圍環(huán)境，當(dāng)機器人距離障礙物越近時越危險。通過危險率指標(biāo)評價機器人的安全性，危險率越大的路徑安全性越低，則安全性目標(biāo)函數(shù)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） 為當(dāng)前第i點與最近障礙物間的距離；df為機器人寬度的1/2；ds為機器人實現(xiàn)無碰撞的安全距離。

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

1.2.4 多目標(biāo)函數(shù)

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

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

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

2 改進的NSGA-Ⅱ多目標(biāo)算法

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

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

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

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

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

2.3 算法流程

本文設(shè)計的改進多目標(biāo)優(yōu)化算法NSGA-Ⅱ路徑規(guī)劃方法流程如下：

1）采用2.5D柵格法進行非平坦環(huán)境建模，確定子目標(biāo)函數(shù)，初始化參數(shù)，獲取初始化種群Pt及最優(yōu)路徑集合U。

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

3）對當(dāng)前種群Pt執(zhí)行交叉、變異操作，產(chǎn)生與其個數(shù)相同的子代種群Qt，將當(dāng)前種群Pt與子代種群Qt合并，記為Rt。

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

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

6）更新迭代次數(shù)，t←t+1，當(dāng)達到最大迭代次數(shù)時結(jié)束迭代，否則返回步驟2）。

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

3 實驗結(jié)果與分析

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

3.1 仿真實驗

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

3.1.1 不同規(guī)格靜態(tài)環(huán)境地圖

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

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

考慮本實驗有3種地圖規(guī)格以及3個子目標(biāo)指標(biāo)，為便于說明，本節(jié)重點討論最優(yōu)路徑集U中具有代表性的極值路徑相較于MOVNS算法的提升率，驗證本文算法所得最優(yōu)路徑集合U相較于MOVNS算法在整體性能上的優(yōu)越性。以10 m×10 m地圖規(guī)格為例，最優(yōu)路徑集合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%。依次對三種地圖規(guī)格下的路徑長度、能耗、危險率三個目標(biāo)分別進行量化計算，得到圖8d、圖8 e所示提升率曲線，分析后可得以下結(jié)論：在同一最優(yōu)路徑集合U中，本文算法路徑長度與能耗成反比，即縮短路徑長度將消耗更多能量、降低能耗將導(dǎo)致路徑長度增加；在不同地圖規(guī)格下，本文算法相較于MOVNS算法的優(yōu)化能力隨著地圖規(guī)格的擴大而提升，路徑長度最多縮短9.27%、能耗最多節(jié)省30.87%、危險率降低15.28%。

3.1.2 不同復(fù)雜程度的環(huán)境地圖

為了進一步驗證本文算法在具有多級摩擦因數(shù)和坡度的復(fù)雜環(huán)境下的適應(yīng)性，在上節(jié)中靜態(tài)20 m×20 m地圖規(guī)格的4×5環(huán)境復(fù)雜度下，增加5×7環(huán)境（五級摩擦因數(shù)：0.2、0.4、0.6、0.8、1.0；七級坡度：-45°、-30°、-15°、0°、15°、30°、45°）以及10×9環(huán)境（十級摩擦因數(shù)：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°）。在上節(jié)的基礎(chǔ)上增設(shè)不同復(fù)雜度的環(huán)境，以驗證本文算法在更高復(fù)雜度環(huán)境下的適應(yīng)性與有效性。

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

由表2可知：隨著環(huán)境復(fù)雜度的提升，本文Pareto最優(yōu)路徑集合U中路徑各子目標(biāo)指標(biāo)均值呈現(xiàn)長度遞增、能耗遞減、危險率遞減的趨勢。

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

綜上所述，本文算法能夠在不同環(huán)境復(fù)雜度的地圖中規(guī)劃出最優(yōu)路徑。

3.1.3 多種障礙物占比仿真結(jié)果分析

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

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

3.2 樣機實驗與分析

3.2.1 履帶機器人平臺介紹

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

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

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

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

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

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

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

根據(jù)表3中數(shù)據(jù)對實驗結(jié)果進行定量分析，本文算法與MOVNS算法相比，平均路徑長度縮短了8.26%，平均能耗降低了16.67%，平均危險率降低了6.61%；與改進的A*算法相比，平均路徑長度縮短了6.88%，平均能耗降低了18.03%，平均危險率降低了13.04%。這說明本文改進的NSGA-Ⅱ算法在環(huán)境信息已知的靜態(tài)環(huán)境中能夠高效完成多目標(biāo)路徑規(guī)劃任務(wù)，且所規(guī)劃路徑優(yōu)于MOVNS算法與改進的A*算法。

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

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

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

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

3.2.4 結(jié)果分析

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

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

4 結(jié)語

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

參考文獻：

［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路徑規(guī)劃A星算法的改進與驗證［J］. 計算機工程與應(yīng)用， 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 年生，教授、博士研究生導(dǎo)師。研究方向為智能控制系統(tǒng)。E-mail：hgzdd@126.com。

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

本文引用格式：張道德，盧子健，趙坤，等.非平坦環(huán)境下履帶機器人多目標(biāo)路徑規(guī)劃方法研究［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.

基金項目：國家自然科學(xué)基金（51907055，52075152）；湖北省農(nóng)機購置與應(yīng)用補貼資金（HBSNYT202213）