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

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

中圖分類號(hào)：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 引言

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

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

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

此外，機(jī)器人完成運(yùn)行任務(wù)過程中的安全性同樣是影響路徑規(guī)劃質(zhì)量的重要指標(biāo)。LIU等^［10］通過計(jì)算動(dòng)能轉(zhuǎn)換和克服牽引力的能耗模型，結(jié)合A*算法控制機(jī)器人運(yùn)行時(shí)間和速度，達(dá)到降低能耗的目的，但犧牲了機(jī)器人運(yùn)行效率。MEJRI等^［11］設(shè)計(jì)了一款節(jié)能路徑規(guī)劃器，使得機(jī)器人在低速、不延長路徑的前提下規(guī)劃出低能耗路徑。SUN等^［12］引入限制功率與地形邊界約束方法，解決了復(fù)雜地形環(huán)境下機(jī)器人易發(fā)生傾覆的問題，確定最優(yōu)的低能耗安全路徑。通過增加速度約束的能耗模型^［13-14］能夠?qū)崿F(xiàn)低能耗路徑規(guī)劃，但限制速度的同時(shí)也增加了完成任務(wù)的時(shí)間成本，如何解決能耗與運(yùn)行時(shí)間的平衡問題迫在眉睫。WEI等^［15］提出了一種在平坦環(huán)境下考慮能耗與運(yùn)行時(shí)間的目標(biāo)權(quán)重實(shí)時(shí)分配禁忌搜索法，實(shí)現(xiàn)了靜態(tài)場(chǎng)景下的最優(yōu)路徑規(guī)劃，但動(dòng)態(tài)場(chǎng)景下既定路徑會(huì)失效。SANGEETHA等^［16］針對(duì)實(shí)時(shí)場(chǎng)景動(dòng)態(tài)目標(biāo)，利用蟻群信息增強(qiáng)機(jī)制改進(jìn)的動(dòng)態(tài)綠色蟻群算法與優(yōu)化元啟發(fā)算法，獲得了兼具路徑長度短、能耗低和時(shí)間短的目標(biāo)路徑。DAS等^［17］采用改進(jìn)EOPs進(jìn)化算子增強(qiáng)改進(jìn)的粒子群優(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ī)劃需要考慮路徑長度、能耗、安全性等多個(gè)目標(biāo)指標(biāo)，多目標(biāo)算法相較于傳統(tǒng)單目標(biāo)算法具備一定的優(yōu)勢(shì)。SURESH等^［18］采用多目標(biāo)遺傳算法—基于改進(jìn)隨機(jī)優(yōu)先搜索的多目標(biāo)遺傳算法（multi-objective genetic algorithm based on modified random priority search， MRPS-MOGA）處理機(jī)器人規(guī)劃路徑運(yùn)行安全性、距離與行駛時(shí)間長短、路徑平滑度和無碰撞五個(gè)子目標(biāo)，求取最優(yōu)路徑。在無人機(jī)領(lǐng)域，JUNG等^［19］考慮巡航節(jié)點(diǎn)間距、無人機(jī)速度、整機(jī)質(zhì)量、航向角四個(gè)目標(biāo)實(shí)現(xiàn)了無碰路徑規(guī)劃。AJEIL等^［20］引入局部搜索LS的混合多目標(biāo)具有多功能行為的粒子群優(yōu)化（particle swarm optimization with multi-functional behavior， PSO-MFB）算法對(duì)路徑長度、無碰撞和路徑平滑度三個(gè)目標(biāo)進(jìn)行優(yōu)化，獲取最優(yōu)無碰平滑路徑。上述研究均集中于路徑距離最短、安全性高、行駛時(shí)間短、路徑平滑等目標(biāo)參數(shù)指標(biāo)，但并未涉及機(jī)器人能耗指標(biāo)。

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

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

1.1 多信息2.5D柵格地圖

傳統(tǒng)柵格地圖是常見的地圖類型，具有易構(gòu)建、表示、保存、計(jì)算以及位置唯一性的優(yōu)勢(shì)。本文提出一種含有多信息的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為路徑從起點(diǎn)至終點(diǎn)經(jīng)過的總節(jié)點(diǎn)數(shù)；i為路徑中由起點(diǎn)至終點(diǎn)的任意一點(diǎn)，i=1，2，…，n；xi、yi分別為i點(diǎn)的橫縱坐標(biāo)；L（i，i+1）為第i點(diǎn)至第i+1點(diǎn)間的距離。

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

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

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

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

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

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

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

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

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

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

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)

對(duì)履帶機(jī)器人進(jìn)行受力分析，如圖3所示。

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

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

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

Fe=Ft－Fb（6）

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

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

履帶機(jī)器人在運(yùn)動(dòng)過程產(chǎn)生的總能耗fE為

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

1.2.3 安全性目標(biāo)

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

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

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

本文采用最小評(píng)價(jià)函數(shù)，將三個(gè)子目標(biāo)集成為多目標(biāo)模型進(jìn)行求解，如下：

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 改進(jìn)的NSGA-Ⅱ多目標(biāo)算法

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

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

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

2.2 基于精英替換策略的迭代機(jī)制

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

2.3 算法流程

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 仿真實(shí)驗(yàn)

多目標(biāo)NSGA-Ⅱ優(yōu)化算法是一種依賴先驗(yàn)參數(shù)設(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，地圖中隨機(jī)生成黑色柵格障礙物，設(shè)置環(huán)境復(fù)雜度均為4×5（即摩擦因數(shù)共4種：0.2、0.4、0.6、0.8；坡度等級(jí)共5種：-45°、-30°、0°、30°、45°，對(duì)應(yīng)圖1中顏色由深藍(lán)到深綠），分別采用改進(jìn)的NSGA-Ⅱ多目標(biāo)算法與MOVNS多目標(biāo)搜索算法^［21］進(jìn)行對(duì)比實(shí)驗(yàn)。

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

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

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

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

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

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

綜合分析圖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，證明了本文算法的能耗模型以及精英替換策略改進(jìn)的有效性；②本文算法在危險(xiǎn)率目標(biāo)上體現(xiàn)為路徑長度越長，伴隨能耗降低的同時(shí)，危險(xiǎn)率也將降低，且隨著環(huán)境復(fù)雜度的提升，危險(xiǎn)率進(jìn)一步降低，由125.4降低至120.55，證明了本文曼哈頓防碰撞搜索機(jī)制的有效性。

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

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

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

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

3.2 樣機(jī)實(shí)驗(yàn)與分析

3.2.1 履帶機(jī)器人平臺(tái)介紹

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

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

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

3.2.2 實(shí)驗(yàn)場(chǎng)景一下的算法有效性驗(yàn)證

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

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

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

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

3.2.3 實(shí)驗(yàn)場(chǎng)景二下的算法有效性驗(yàn)證

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

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

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

3.2.4 結(jié)果分析

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

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

4 結(jié)語

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

參考文獻(xià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］ 趙江， 張巖， 馬澤文， 等. 對(duì)AGV路徑規(guī)劃A星算法的改進(jìn)與驗(yàn)證［J］. 計(jì)算機(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.

（編輯 陳 勇）

作者簡(jiǎn)介：張道德，男，1973 年生，教授、博士研究生導(dǎo)師。研究方向?yàn)橹悄芸刂葡到y(tǒng)。E-mail：hgzdd@126.com。

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

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

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