摘" 要： 針對(duì)目前深海鈷結(jié)殼采礦車在采礦時(shí)無法達(dá)到規(guī)劃時(shí)間和路程代價(jià)綜合最優(yōu)，提出一種改進(jìn)的跳點(diǎn)搜索算法作為全局路徑規(guī)劃算法。首先，基于對(duì)采礦車越坡動(dòng)力學(xué)的分析，模擬了具有不同坡度的結(jié)核礦區(qū)柵格地圖，并利用動(dòng)態(tài)跳點(diǎn)搜索算法完成路徑規(guī)劃；其次，采用貝塞爾曲線來平滑路徑以減少和優(yōu)化轉(zhuǎn)彎角度，并設(shè)定了最小轉(zhuǎn)彎半徑約束以減小采礦車的轉(zhuǎn)彎頻率；最后，通過仿真結(jié)果表明，改進(jìn)后的跳點(diǎn)搜索算法相較于其他4種算法，在規(guī)劃時(shí)間上縮短了40%，在規(guī)劃路徑長(zhǎng)度和平滑度方面得到5%和10%的提升，相較于單向跳點(diǎn)搜索算法在探索效率上得到較大提升，最終證明了該算法在路徑規(guī)劃時(shí)的實(shí)時(shí)性和路徑規(guī)劃能力的優(yōu)異性。

關(guān)鍵詞： 深海作業(yè)； 采礦車； 動(dòng)力學(xué)； 路徑規(guī)劃； 跳點(diǎn)搜索算法； 平滑度優(yōu)化

中圖分類號(hào)： TN99?34" " " " " " " " " " " " " "文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " " " " 文章編號(hào)： 1004?373X（2024）11?0113?05

Research on path planning method based on deep?sea cobalt crust mining vehicle

YANG Changbing

（Lianyungang Center， Taihu Laboratory of Deepsea Technological Science， Lianyungang 222000， China）

Abstract： In view of the fact that the current deep?sea cobalt crust mining vehicle fails to achieve the comprehensive optimal of planning time and distance cost during mining， an improved jump point search （JPS） algorithm is proposed as a global path planning algorithm. On the basis of the analysis of the slope?crossing dynamics of mining vehicles， the raster maps of nodule mining areas with different slopes are simulated， and the dynamic JPS algorithm is used to complete the path planning. The Bezier curve is used to smooth the path to reduce and optimize the turning angle， and the minimum turning radius constraint is set to reduce the turning frequency of the mining vehicle. Finally， the simulation results show that， in comparison with the other four algorithms， the improved JPS algorithm reduces the planning time by 40%， and improves the planning path length and smoothness by 5% and 10%， respectively. Its exploration efficiency has been improved greatly in comparison with that of the one?way JPS algorithm. It is proved that the proposed algorithm is of real?time property and excellence in path planning ability.

Keywords： deep?sea operation; mining vehicle; dynamics; path planning; JPS algorithm; smoothness optimization

0" 引" 言

深海固體礦產(chǎn)資源中已知有深海多金屬結(jié)核、富鈷結(jié)殼和多金屬硫化物等類型。其中，海洋富鈷結(jié)殼是現(xiàn)今所探索到的最具戰(zhàn)略發(fā)展意義和潛在經(jīng)濟(jì)價(jià)值的海洋礦產(chǎn)資源之一，礦體富含鈷、鈦、鈰、鉑和鎳等多種稀有金屬[1?2]。富鈷結(jié)殼和多金屬硫化物礦床在分布和地形方面存在差異，富鈷結(jié)殼主要分布于海洋山體斜坡表面處，開采環(huán)境惡劣復(fù)雜[3]。在執(zhí)行海底自主開采作業(yè)時(shí)，采礦車需要面對(duì)不同的坡度和地形，行動(dòng)具有多約束性和多目標(biāo)性，因此采礦車的路徑規(guī)劃和導(dǎo)航跟蹤定位成為海底采礦車發(fā)展的核心[4?6]。

文獻(xiàn)[7]通過研究深海采礦整體系統(tǒng)的動(dòng)力學(xué)，搭建采礦車聯(lián)動(dòng)作業(yè)模型，奠定了采礦車路徑規(guī)劃、導(dǎo)航定位和軌跡控制的基礎(chǔ)。文獻(xiàn)[8]研究深海采礦系統(tǒng)的整體運(yùn)動(dòng)特性，考慮避障環(huán)境、禁行區(qū)域和行動(dòng)速度的影響，為深海鈷結(jié)殼采礦車的路徑規(guī)劃提供理論支持。A*算法[9]是一種運(yùn)算時(shí)間快的全局路徑規(guī)劃算法，但也存在折轉(zhuǎn)次數(shù)較多、路徑平滑度較低的缺陷。文獻(xiàn)[10]通過結(jié)合跳點(diǎn)搜索算法和A*算法，刪除路徑冗余點(diǎn)，降低路徑折轉(zhuǎn)次數(shù)來提高路徑平滑度。文獻(xiàn)[11]基于采礦車越坡的動(dòng)力學(xué)特性，利用越坡時(shí)間來優(yōu)化代價(jià)函數(shù)并引入A*算法，同時(shí)利用算法平滑路徑規(guī)劃出綜合最優(yōu)的平滑路徑。文獻(xiàn)[12]提出了RRT*算法，考慮海底地形和采樣點(diǎn)的通行性，改進(jìn)目標(biāo)導(dǎo)向并對(duì)生成的路徑進(jìn)行剪枝優(yōu)化，提高生成路徑的安全性能。本文使用跳點(diǎn)搜索算法[13?15]，其在保留A*算法框架的同時(shí)，通過優(yōu)化搜索策略提高了路徑的探索效率，但是在復(fù)雜地圖中存在跳點(diǎn)多且混亂的缺陷，因此在深海采礦車的路徑規(guī)劃中需要重新改進(jìn)跳點(diǎn)搜索算法。

綜上所示，通過結(jié)合采礦車爬坡動(dòng)力學(xué)和改進(jìn)跳點(diǎn)搜索（Jump Point Search， JPS）算法，本文提出一種全新的深海采礦車路徑規(guī)劃算法，其在深海采礦車路徑規(guī)劃效率和性能方面具有一定的優(yōu)勢(shì)，為深海礦產(chǎn)開采提供了重要的技術(shù)支持。

1" 深海采礦車爬坡動(dòng)力學(xué)分析

1.1" 牽引力分析

在富鈷結(jié)殼礦區(qū)的底質(zhì)環(huán)境中，分析鈷結(jié)殼采礦車在越坡過程的動(dòng)力學(xué)?；诮拥貕毫Ψ植家?guī)律，考慮履帶高度、履帶板特性及齒間底質(zhì)的黏附特性等因素，研究其對(duì)牽引性能的影響。

采礦車接地壓力的分布規(guī)律如式（1）所示：

[p0=G2BLcosα] （1）

式中：[G]為采礦車的水下重量，單位為kN；[B]為履帶寬度，單位為m；[L]為履帶長(zhǎng)度，單位為m；[P0]為接地壓力，單位為kPa；[α]為斜坡傾角。

理論牽引力如式（2）所示：

[P理=2BCb+p0tanφ?" " λL-ω-2λkm2i+kmie-iLkmω2e-iLkm-ω-λ] （2）

式中：[P]為忽略履齒效應(yīng)的驅(qū)動(dòng)力，單位為kN；[Cb]為底質(zhì)黏聚力，單位為kPa；[φ]為底質(zhì)內(nèi)摩擦角；[km]為底層剪切模量，單位為cm。

實(shí)際驅(qū)動(dòng)力與理論驅(qū)動(dòng)力的差值[ΔP]計(jì)算公式如下：

[ΔP=2Bm-p0tanφλL-ω-2Lkm2i+kmie-iLkmω2e-iLkm-ω+L+BnλL2-2ω-λkmi1+kmie-iLkm-kmi-Bnωkmi1+km2ie-iLkm-km2i" " " " " " " " " " " " " " " " " " " （3）]

式中：[m]、[n]為非0常數(shù)。

因此，最終實(shí)際驅(qū)動(dòng)力[P1]如式（4）所示：

[P1=P理+ΔP] （4）

1.2" 阻力分析

采礦車爬坡的行駛阻力主要分為路面擠壓阻力和水重力分力。其中，路面擠壓阻力計(jì)算公式如式（5）所示：

[FR=12kc+BkφGcosα2BL1+6e0L2] （5）

式中：[kc]為內(nèi)聚變形模量，單位為kN/m2；[kφ]為摩擦變形模量，單位為kN/m2；[e0]為縱向偏心距，默認(rèn)為0。

水重力分力計(jì)算公式如式（6）所示：

[FG=Gsinα] （6）

海底采礦車迎水面積較大，且海水的密度較高，因此采礦車行駛時(shí)需要考慮水動(dòng)力與水阻力，其和如式（7）所示：

[Fh=-12CdρωAmvm-vwvm-vw-CmρωVmvm-vw] （7）

式中：[Cd]為水阻力系數(shù)；[ρω]為海水密度，單位為kN/m3；[Am]為采礦車正面迎水面積，單位為m2；[vw]為海底水流速度，單位為m/s；[vm]為采礦車行駛速度，單位為m/s；[Vm]為采礦車體積，單位為m3；[Cm]為附加質(zhì)量系數(shù)。

1.3" 越坡時(shí)間分析

基于上述牽引力公式和阻力公式，動(dòng)力學(xué)分析的具體參數(shù)如表１所示。

由牛頓第二定律，可得式（8）：

[F=Gga] （8）

利用坡度模型計(jì)算不同坡度的越坡時(shí)間，如式（9）所示：

[hsinα=0tvmdt] （9）

利用采礦車越坡時(shí)間與橫越時(shí)間比值[ε]來評(píng)價(jià)越坡難度。

[ε=t1t2] （10）

式中：[t1]代表越坡的時(shí)間；[t2]代表采礦車橫跨[xm]的時(shí)間。

當(dāng)海底坡度小于5°時(shí)，采礦車越坡的消耗時(shí)間約等于通過橫跨坡距離的時(shí)間，即大約為1 s。當(dāng)海底坡度大于10°時(shí)，采礦車的行動(dòng)存在危險(xiǎn)性且越坡時(shí)間長(zhǎng)，即視為禁行區(qū)域。在后續(xù)的柵格賦值中，將坡度小于5°的區(qū)域視為可行區(qū)域，將坡度大于10°的視為為禁行區(qū)域，即障礙物區(qū)域。

基于深海采礦車爬坡動(dòng)力學(xué)分析的結(jié)果，生成了以坡度為自變量的時(shí)間比值[ε?α]曲線，該曲線如圖1所示。

根據(jù)深海采礦車的動(dòng)力學(xué)特性，通過計(jì)算越坡時(shí)間與正常行駛時(shí)間的比值為柵格地圖賦予不同數(shù)值，方便更準(zhǔn)確地反映采礦車在海底的行駛難度，并為路徑規(guī)劃算法提供更準(zhǔn)確的地圖信息。

2" 改進(jìn)路徑規(guī)劃算法

2.1" A*尋路搜索算法

在眾多全局路徑規(guī)劃算法中，A*尋路算法是一種高效的直接搜索算法，被廣泛應(yīng)用于求解最優(yōu)路徑問題。該算法融合了Dijkstra算法和最佳優(yōu)先搜索算法的思想，通過設(shè)置啟發(fā)函數(shù)來引導(dǎo)搜索方向，并在保證規(guī)劃路徑最優(yōu)或次優(yōu)的情況下進(jìn)行路徑搜索。A*算法包含兩個(gè)狀態(tài)表，即Open List和Close List。Open List包含待搜索的節(jié)點(diǎn)，Close List則包含已搜索的節(jié)點(diǎn)。在每次搜索中，將Open List中的最優(yōu)節(jié)點(diǎn)添加到Close List，并將該節(jié)點(diǎn)的子節(jié)點(diǎn)加入Open List中。不斷迭代，直到終點(diǎn)被添加到Open List中，即可完成尋路任務(wù)。A*算法通過代價(jià)函數(shù)來評(píng)估節(jié)點(diǎn)的優(yōu)劣，其中代價(jià)函數(shù)的計(jì)算公式如下：

[f（p）=g（p）+h（p）] （11）

式中：[f（p）]是從起點(diǎn)經(jīng)過節(jié)點(diǎn)[p]到達(dá)終點(diǎn)的代價(jià)估計(jì)；[g（p）]為實(shí)際代價(jià)，即從起點(diǎn)到節(jié)點(diǎn)[p]的實(shí)際距離；[h（p）]為估計(jì)代價(jià)，即節(jié)點(diǎn)[p]到終點(diǎn)之間的估計(jì)距離。

A*算法在保證路徑較優(yōu)的前提下，具有較高的搜索效率，與JPS算法相比仍存在浪費(fèi)探索節(jié)點(diǎn)的缺點(diǎn)，不適用于在復(fù)雜環(huán)境中進(jìn)行采礦車路徑規(guī)劃任務(wù)。

2.2" 雙向跳點(diǎn)搜索算法

在復(fù)雜地圖環(huán)境中，A*算法需要對(duì)每個(gè)柵格點(diǎn)進(jìn)行檢測(cè)，導(dǎo)致大量冗余節(jié)點(diǎn)的檢測(cè)，從而降低了搜索速率。為了提高算法的探索速度，基于A*算法的跳點(diǎn)搜索算法被提出，它通過搜索跳點(diǎn)來代替向周圍擴(kuò)展節(jié)點(diǎn)的方式，減少計(jì)算節(jié)點(diǎn)的數(shù)量。但它仍存在一些缺陷，在障礙物密集的環(huán)境中，JPS算法可能會(huì)找到過多的不必要的跳點(diǎn)，增加了內(nèi)存消耗并降低了算法的效率。

為解決上述問題，提出了雙向跳點(diǎn)搜索算法，流程如圖2所示，使用正向和反向跳點(diǎn)的父節(jié)點(diǎn)作為目標(biāo)點(diǎn)進(jìn)行搜索，并利用啟發(fā)式函數(shù)保證跳點(diǎn)更新，當(dāng)目標(biāo)點(diǎn)相遇或出現(xiàn)在同一個(gè)Closed List時(shí)結(jié)束路徑規(guī)劃任務(wù)。雙向跳點(diǎn)搜索算法加速了算法的收斂，提高了算法的效率。

在柵格地圖中，基于雙向跳點(diǎn)搜索算法尋找最短路徑，可以更精準(zhǔn)地確定采礦車的最優(yōu)行駛路徑，同時(shí)減少規(guī)劃時(shí)間、行駛時(shí)間以及能量消耗。

2.3" 路徑平滑度優(yōu)化

在仿真實(shí)驗(yàn)中，通常對(duì)動(dòng)作進(jìn)行簡(jiǎn)化處理，保證仿真的順利和時(shí)效。但是，動(dòng)作簡(jiǎn)化會(huì)導(dǎo)致路徑存在轉(zhuǎn)折次數(shù)多與路徑不平滑等問題。因此，在路徑規(guī)劃完成后可以進(jìn)行平滑度優(yōu)化，其中貝塞爾曲線（Bezier）被廣泛使用。貝塞爾曲線具有簡(jiǎn)單的控制和強(qiáng)大的圖形描述能力的優(yōu)點(diǎn)，能夠平滑地連接節(jié)點(diǎn)。貝塞爾曲線公式如下：

[Pu=i=0nPiBi，nu，" " u∈0，1] （12）

[Bi，nu=n！n-i！i！ui1-un-i，" " i=0，1，2，…，n] （13）

式中：[Pu]為運(yùn)動(dòng)控制點(diǎn)，[u]是自變量；[Pi]代表位置點(diǎn)；[P0]、[P]（1）表示起點(diǎn)和終點(diǎn)的位置；[Bi，nu]是[n]次伯恩斯坦多項(xiàng)式。

對(duì)貝塞爾曲線公式求導(dǎo)：

[Pu=di=0nPiBi，nudu=ni=0nBi，n-1uPi+1-Pi] （14）

依據(jù)圖3可以觀察到貝塞爾曲線能夠有效解決路徑規(guī)劃中平滑度低的問題，將銳角或折線段轉(zhuǎn)化為流暢的曲線，能夠減少采礦車在路徑規(guī)劃中的轉(zhuǎn)向頻率，降低采礦車能耗和磨損，提高航行效率和安全性。此外，路徑的精度和可靠性也得到提高，使生成的路徑更加符合真實(shí)采礦車路徑的實(shí)際要求。

3" 仿真實(shí)驗(yàn)及結(jié)果分析

3.1" 鈷結(jié)殼礦區(qū)仿真地圖

本文建立了一幅30×30格尺寸的鈷結(jié)殼礦區(qū)海底二維柵格地圖，如圖4所示。其中，五角星用以標(biāo)識(shí)終點(diǎn)位置，圓形標(biāo)記作為起點(diǎn)位置，三角形代表可采取礦石的特定區(qū)域，黑色區(qū)域表示不可通行區(qū)域，白色區(qū)域表示可通行區(qū)域。

3.2" 仿真對(duì)比實(shí)驗(yàn)

通過設(shè)計(jì)虛擬仿真場(chǎng)景，本研究對(duì)比了幾種不同的路徑規(guī)劃算法的能力，包括JPS算法、迪杰斯特拉算法（Dijkstra）、A*算法（ASTAR）、人工勢(shì)場(chǎng)法（APF）、隨機(jī)樹搜索算法（RRT?Star）和雙向JPS算法。在相同的環(huán)境下，完成了相同的路徑規(guī)劃任務(wù)，并使用貝塞爾曲線進(jìn)行平滑度優(yōu)化，最終各類算法的整體路徑規(guī)劃效果如圖5所示。

為驗(yàn)證雙向JPS算法在路徑規(guī)劃方面的優(yōu)越性，選擇了時(shí)間、長(zhǎng)度和平滑度三個(gè)參數(shù)指標(biāo)作為評(píng)價(jià)標(biāo)準(zhǔn)。在相同環(huán)境下，完成不同算法的路徑規(guī)劃仿真實(shí)驗(yàn)，并獲取具體的規(guī)劃能力評(píng)價(jià)參數(shù)，各算法的路徑規(guī)劃效果參數(shù)對(duì)比如圖6所示。

為驗(yàn)證深海鈷結(jié)殼采礦車在實(shí)際工作場(chǎng)景中的路徑規(guī)劃能力，在仿真環(huán)境中增加了可采取礦石區(qū)域。在場(chǎng)景二中，采礦車將會(huì)自動(dòng)規(guī)劃采礦路徑并避開障礙物，最終路徑規(guī)劃效果對(duì)比如圖7所示。

改進(jìn)跳點(diǎn)搜索算法相較于A*算法和JPS算法的提升效果如表2所示。

3.3" 仿真結(jié)果分析

經(jīng)過對(duì)不同算法進(jìn)行仿真實(shí)驗(yàn)并對(duì)最終結(jié)果進(jìn)行分析，本文得出了以下結(jié)論：首先，相較于單向JPS算法，雙向JPS算法通過雙向跳點(diǎn)搜索策略減少了搜索的節(jié)點(diǎn)數(shù)，從而提高了搜索效率，更加適合于大規(guī)模搜索；其次，增加了啟發(fā)式函數(shù)導(dǎo)向，促使采礦車更快趨近于目標(biāo)點(diǎn)；最后，通過對(duì)路徑應(yīng)用貝塞爾曲線平滑優(yōu)化處理，將銳角或直線段轉(zhuǎn)化為流暢的曲線，進(jìn)一步降低采礦車在路徑規(guī)劃中的轉(zhuǎn)向率，從而減少能耗和磨損，提高航行效率和安全性。

綜上所述，雙向JPS算法能夠快速找到最優(yōu)路徑，生成較短的路徑，在大規(guī)模搜索中效率顯著提高，通過貝塞爾曲線的平滑優(yōu)化處理提高路徑的平滑度，降低了能耗和磨損，提高了航行效率和安全性。

4" 結(jié)" 論

根據(jù)鈷結(jié)殼采礦車在海底爬坡作業(yè)的復(fù)雜性，對(duì)深海采礦車進(jìn)行動(dòng)力學(xué)分析，確定了大于10°的坡為禁行區(qū)域，小于5°的坡為可行區(qū)域，保證隨機(jī)產(chǎn)生的海底環(huán)境在柵格化時(shí)的相對(duì)真實(shí)性。針對(duì)傳統(tǒng)路徑規(guī)劃算法在復(fù)雜的采礦場(chǎng)景下存在計(jì)算量大、搜索效率低等問題，采用雙向跳點(diǎn)搜索算法，并完成對(duì)路徑的平滑度優(yōu)化。文中將五種路徑規(guī)劃算法與雙向JPS算法進(jìn)行了仿真對(duì)比分析，通過對(duì)比規(guī)劃路線和關(guān)鍵參數(shù)，得出了雙向JPS算法在實(shí)際采礦車路徑規(guī)劃的應(yīng)用中能夠降低能耗和磨損，提高航行效率和安全性的結(jié)論，同時(shí)證明改進(jìn)的JPS算法相較于單向JPS算法具有更加優(yōu)異的性能。因此，提出的雙向JPS算法模型在深海鈷結(jié)殼采礦車路徑規(guī)劃的實(shí)際應(yīng)用具有一定的指導(dǎo)意義，可為進(jìn)一步研究提供參考價(jià)值。

參考文獻(xiàn)

[1] 李家彪，王葉劍，劉磊，等.深海礦產(chǎn)資源開發(fā)技術(shù)發(fā)展現(xiàn)狀與展望[J].前瞻科技，2022，1（2）：92?102.

[2] 陳波.基于遺傳算法的鈷結(jié)殼采礦車行走路徑規(guī)劃研究[J].長(zhǎng)沙航空職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2014，14（4）：46?52.

[3] 于全虎.海洋采礦技術(shù)及采礦船舶發(fā)展綜述[J].北部灣大學(xué)學(xué)報(bào)，2020，35（10）：1?6.

[4] 王國(guó)榮，黃澤奇，周守為，等.深海礦產(chǎn)資源開發(fā)裝備現(xiàn)狀及發(fā)展方向[J].中國(guó)工程科學(xué)，2023，25（3）：1?12.

[5] 彭建平.中國(guó)深海多金屬結(jié)核采礦車研究的發(fā)展[J].礦山機(jī)械，2020，48（3）：8?11.

[6] 史春雪，卜英勇，羅柏文，等.基于蟻群算法深海采礦機(jī)器人工作路徑規(guī)劃[J].海洋工程，2008（2）：119?123.

[7] 戴瑜，張健，張?zhí)希?基于多體動(dòng)力學(xué)模型集成的深海采礦系統(tǒng)聯(lián)動(dòng)仿真[J].機(jī)械工程學(xué)報(bào)，2017，53（4）：155?160.

[8] 徐海良，彭能，楊放瓊.避障模式下深海采礦系統(tǒng)動(dòng)力學(xué)分析[J].中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，51（3）：641?649.

[9] 劉志軍，蘇亮，吳少雄.基于AStar算法的避障路徑局部規(guī)劃方法開發(fā)[J].客車技術(shù)與研究，2023，45（3）：6?9.

[10] 殷祥釗.基于跳點(diǎn)搜索改進(jìn)A*算法的移動(dòng)機(jī)器人導(dǎo)航控制[D].南昌：南昌大學(xué)，2020.

[11] 陳昱衡，吳鴻云，郭旭，等.基于采礦車動(dòng)力學(xué)分析的改進(jìn)A*算法全局路徑規(guī)劃[J].礦業(yè)研究與開發(fā)，2021，41（2）：170?177.

[12] 郭玲玲，樊蓓蓓.基于改進(jìn)RRT*算法的深海采礦車局部路徑規(guī)劃算法[J].工業(yè)控制計(jì)算機(jī)，2023，36（1）：97?99.

[13] 馬小陸，梅宏.雙向跳點(diǎn)搜索算法的移動(dòng)機(jī)器人全局路徑規(guī)劃研究[J].機(jī)械科學(xué)與技術(shù)，2020，39（10）：1624?1631.

[14] 黃智榜，胡立坤，張宇，等.基于改進(jìn)跳點(diǎn)搜索策略的安全路徑研究[J].計(jì)算機(jī)工程與應(yīng)用，2021，57（1）：56?61.

[15] 秦齊，萬熠，侯嘉瑞，等.基于雙向動(dòng)態(tài)跳點(diǎn)搜索算法的AGV路徑規(guī)劃研究[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2021，21（8）：55?58.

作者簡(jiǎn)介：楊長(zhǎng)兵（1997—），男，山東菏澤人，助理工程師，研究方向?yàn)橐苿?dòng)機(jī)器人路徑規(guī)劃、智能控制。