基于改進(jìn)RRT*算法的井下巷道漫游路徑規(guī)劃方法

摘" 要： 針對(duì)目前井下巷道作業(yè)人員行動(dòng)軌跡重現(xiàn)，以及巷道漫游等三維可視化巷道虛擬現(xiàn)實(shí)過程中的碰撞檢測(cè)和路徑規(guī)劃問題，提出一種將改進(jìn)快速探索隨機(jī)樹（RRT*）算法和貪心算法相結(jié)合，解決井下巷道復(fù)雜環(huán)境和高維空間尋求最優(yōu)路徑的方法。這一改進(jìn)方法使用優(yōu)先探索策略和貪心策略，解決了RRT算法難以求解最優(yōu)的可行路徑和RRT*算法運(yùn)動(dòng)路徑振蕩的問題。通過Matlab仿真實(shí)驗(yàn)平臺(tái)進(jìn)行驗(yàn)證，結(jié)果表明：所提出的規(guī)劃方法可得到滿意的避障規(guī)劃路徑；且相較于RRT*算法，該方法減少了大部分的無用路徑搜索和路徑邊徑的內(nèi)存存儲(chǔ)，提高了路徑規(guī)劃的效率，有效解決了虛擬現(xiàn)實(shí)過程中運(yùn)動(dòng)路徑的振蕩問題，實(shí)現(xiàn)了平滑的路徑規(guī)劃。

關(guān)鍵詞： 巷道漫游； 改進(jìn)RRT*算法； 貪心策略； 路徑規(guī)劃； 碰撞檢測(cè)； 最優(yōu)路徑

中圖分類號(hào)： TN957.52+4?34； TD67" " " " " " " " " "文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " "文章編號(hào)： 1004?373X（2024）12?0062?07

Method of mine lane roaming path planning based on improved RRT* algorithm

WANG Lili1， 2

（1. CCTEG Changzhou Research Institute， Changzhou 213000， China; 2. Tiandi （Changzhou） Automation Co.， Ltd.， Changzhou 213000， China）

Abstract： In allusion to the problem of collision detection and path planning in the mine lane virtual reality process of 3D visualization mine lane， such as the action trajectory reproduction of underground coal mine lane operators and coal mine lane roaming， an improved method is proposed to solve the problem of seeking the optimal path in the complex environment and high?dimensional space of underground coal mine lane by combining the improved rapidly?exploring random tree star （RRT*） algorithm with the greedy algorithm. In the improved method， the first exploration strategy and greedy strategy are used to solve the problem that RRT algorithm is difficult to solve the optimal feasible path and the problem of RRT* algorithm motion path oscillation. The Matlab simulation experiment platform verifies that the proposed planning method can obtain satisfactory obstacle avoidance planning path， and in comparison with RRT* algorithm， this method can reduce most useless path search and memory storage of path edge path， improve the efficiency of path planning， effectively solve the problem of motion path oscillation in the process of virtual reality， and realize smooth path planning.

Keywords： mine lane roaming; improved RRT* algorithm; greedy strategy; path planning; collision detection; optimal path

0" 引" 言

隨著礦山智能化的發(fā)展，在建立數(shù)字化、信息化、虛擬化方面，透明礦井等三維可視化技術(shù)的重要程度越來越高，應(yīng)用也日漸廣泛。對(duì)煤礦地面和井下使用實(shí)際地理空間信息數(shù)據(jù)進(jìn)行精細(xì)化三維建模，與礦井三維地質(zhì)模型相疊加，實(shí)現(xiàn)地下作業(yè)環(huán)境及設(shè)備的可視化管理和位置數(shù)據(jù)支持，在井下動(dòng)目標(biāo)定位、智能巡檢機(jī)器人、車輛無人駕駛等應(yīng)用領(lǐng)域的運(yùn)動(dòng)路徑規(guī)劃及導(dǎo)航中發(fā)揮重要的“地圖大腦”作用。

目前大多數(shù)煤礦均已建立井下真三維透明礦井的應(yīng)用，但在某些實(shí)際應(yīng)用場(chǎng)景中仍存在問題，如：井下人員根據(jù)定位系統(tǒng)計(jì)算出行走的運(yùn)動(dòng)軌跡在進(jìn)行虛擬現(xiàn)實(shí)軌跡重現(xiàn)演示時(shí)，會(huì)出現(xiàn)穿越巷道墻壁或者碰撞安裝在巷道內(nèi)的各類設(shè)備等情況，與實(shí)際運(yùn)動(dòng)情況不符。在地面定位時(shí)GPS信號(hào)和實(shí)際的人員軌跡存在距離誤差，如果不對(duì)GPS定位數(shù)據(jù)進(jìn)行處理而直接定位，人員位置會(huì)被定位到非道路的建筑、湖泊、公園中，屬于不合理情況，應(yīng)對(duì)GPS定位路徑數(shù)據(jù)進(jìn)行處理，使得其能準(zhǔn)確地匹配到路網(wǎng)上。

在井下巷道漫游的路徑規(guī)劃過程中，同樣存在類似的路徑匹配和躲避障礙物的求解最優(yōu)路徑問題。由于井下巷道狹窄，不同區(qū)域的地面高度存在較大差異，各種設(shè)備安裝在巷道內(nèi)，定位運(yùn)動(dòng)軌跡與動(dòng)目標(biāo)在實(shí)際巷道內(nèi)運(yùn)動(dòng)軌跡存在誤差，其中既有地測(cè)的測(cè)量誤差，也有采用不同定位技術(shù)由定位精度導(dǎo)致的疊加誤差。在虛擬現(xiàn)實(shí)過程中不可避免地導(dǎo)致人員運(yùn)動(dòng)軌跡重現(xiàn)演示時(shí)，穿越巷道墻壁或者巷道內(nèi)漫游運(yùn)動(dòng)過程中碰撞安裝在巷道內(nèi)的各類設(shè)備等失真失實(shí)情況發(fā)生。

大部分文獻(xiàn)均針對(duì)不同應(yīng)用場(chǎng)景的路徑規(guī)劃尋優(yōu)效率問題以及路徑平滑問題，進(jìn)行不同程度的算法改進(jìn)，均符合文獻(xiàn)[1]指出的全局路徑規(guī)劃算法將向優(yōu)化已有常規(guī)算法路徑規(guī)劃的性能、多種算法優(yōu)勢(shì)融合、復(fù)雜環(huán)境中動(dòng)態(tài)避障、適應(yīng)多樣化環(huán)境的地圖表示方法這四方面發(fā)展的綜述。

路徑規(guī)劃問題的根本任務(wù)是在已知環(huán)境和障礙物的情況下，找到一條從起點(diǎn)到終點(diǎn)的無碰撞運(yùn)動(dòng)路徑。路徑規(guī)劃算法主要有基于圖的搜索算法、人工勢(shì)場(chǎng)法、基于采樣的規(guī)劃方法等[1?2]。各類動(dòng)目標(biāo)的運(yùn)動(dòng)路徑規(guī)劃本質(zhì)為從開始位置到目標(biāo)位置的路徑尋優(yōu)問題，主要有兩個(gè)方面的難點(diǎn)問題需要解決：一是躲避障礙物，二是滿足動(dòng)目標(biāo)本身運(yùn)動(dòng)特性。前者是全局約束條件，后者是具備運(yùn)動(dòng)特征的微分約束條件。解決全局約束問題的重要方法是采用抽樣規(guī)劃，不同的是RRT算法比較容易處理包含障礙物等全局約束和差分運(yùn)動(dòng)約束的情況，因而在各種動(dòng)目標(biāo)的運(yùn)動(dòng)規(guī)劃場(chǎng)景中應(yīng)用廣泛[3?4]。

上述情況均需要解決障礙物躲避的最優(yōu)路徑規(guī)劃以及路徑平滑防振蕩問題。本文采用RRT*算法并融合貪心算法來解決三維透明礦井虛擬現(xiàn)實(shí)場(chǎng)景中的路徑規(guī)劃問題。與大部分文獻(xiàn)所提及的方法相比，本文方法不需要依賴于傳感器或定位設(shè)備等硬件條件作運(yùn)動(dòng)規(guī)劃，而是在透明礦井三維可視化地測(cè)模型的已知環(huán)境約束情況下進(jìn)行巷道內(nèi)的避障路徑規(guī)劃。經(jīng)貪心算法優(yōu)化后的路徑更符合該透明礦井?dāng)?shù)字孿生場(chǎng)景的應(yīng)用，在一定程度上能糾偏上述失真失實(shí)的情況，更能滿足智能化透明礦井的現(xiàn)實(shí)需求。

1" 路徑規(guī)劃算法

1.1" 隨機(jī)樹快速擴(kuò)展算法

隨機(jī)樹快速擴(kuò)展算法（Rapidly?exploring Random Tree， RRT）是一種通過隨機(jī)構(gòu)建Space Filling Tree實(shí)現(xiàn)對(duì)非凸高維空間快速搜索的算法，也是一種典型的在完全已知的環(huán)境中通過采樣擴(kuò)展搜索的算法[5]。該算法通過在環(huán)境中隨機(jī)采樣，快速探索整個(gè)環(huán)境，并以樹結(jié)構(gòu)存儲(chǔ)每個(gè)被搜索的位置節(jié)點(diǎn)來實(shí)現(xiàn)路徑尋優(yōu)過程，完成搜索的路徑通常是從樹的根節(jié)點(diǎn)到一個(gè)葉節(jié)點(diǎn)的完整路徑[6]。RRT與基于圖的搜索算法相比，其最主要的優(yōu)點(diǎn)就是速度快。RRT也有比較明顯的缺點(diǎn)，即它雖然是概率完備的，但是存在限制條件。RRT尋找的路徑通常不是最優(yōu)路徑，同時(shí)存在規(guī)劃的路徑非常不平滑等問題[7]。

1.2" 改進(jìn)隨機(jī)樹快速搜索算法

RRT算法不是最優(yōu)的，但能夠?qū)崿F(xiàn)遞進(jìn)優(yōu)化。RRT*（Rapidly?exploring Random Tree Star）算法是RRT算法的改進(jìn)版本，它通過引入重新連接和優(yōu)化步驟，可找到更優(yōu)的路徑，改善路徑的質(zhì)量和長(zhǎng)度，提高了路徑規(guī)劃的質(zhì)量和效率[6?9]。RRT*算法具有高效、快速搜索、易于實(shí)現(xiàn)等優(yōu)點(diǎn)，通過合理地調(diào)整算法參數(shù)，可以平衡探索和利用，獲得較RRT算法更為高效和較平滑的路徑規(guī)劃結(jié)果，能夠有效地解決復(fù)雜環(huán)境下的路徑規(guī)劃問題。

2" 巷道漫游避障路徑規(guī)劃改進(jìn)方法

本文僅針對(duì)在井下巷道復(fù)雜環(huán)境和高維空間中，井下作業(yè)人員運(yùn)動(dòng)軌跡重現(xiàn)的避障以及巷道漫游的避障路徑規(guī)劃問題提出改進(jìn)方法和實(shí)現(xiàn)步驟。

采用RRT*算法來解決井下作業(yè)人員軌跡重現(xiàn)的避障以及巷道漫游的路徑規(guī)劃問題時(shí)，雖然路徑可以實(shí)現(xiàn)漸近最優(yōu)，但是生成的路徑不夠光滑，從而使得軌跡重現(xiàn)或巷道漫游按照這種路徑運(yùn)動(dòng)時(shí)會(huì)出現(xiàn)振蕩問題，形成運(yùn)動(dòng)路徑不平滑的問題[10?17]。

為了解決上述問題，本文在RRT*算法的基礎(chǔ)上引入貪心算法，采用貪心策略尋求最優(yōu)路徑，實(shí)現(xiàn)從起始位置到目標(biāo)位置平滑的運(yùn)動(dòng)路徑規(guī)劃。貪心算法（Greedy Algorithm）通常解決的問題是在做決策時(shí)，只考慮當(dāng)前局部最優(yōu)策略[18?19]。由于動(dòng)態(tài)規(guī)劃整體路徑尋優(yōu)問題本身具備貪心策略的局部性，保證了通過局部獲得的最優(yōu)解，最終可以得到全局的最優(yōu)解。

2.1" RRT*算法原理及收斂性分析

本節(jié)主要介紹了該改進(jìn)路徑規(guī)劃方法的算法原理和理論特性。

給定已知的空間區(qū)域[X]，障礙物集合區(qū)域[Xobs]，目標(biāo)區(qū)域[Xgoal]，時(shí)間界限T，運(yùn)動(dòng)規(guī)劃的任務(wù)就是在時(shí)間域[0，T]之間找到一個(gè)控制量[x∈U]（集合U代表輸入控制量），使得相應(yīng)的軌跡[x∈X] （集合[X]代表軌跡），在躲避障礙物的同時(shí)能到達(dá)目標(biāo)區(qū)域，即滿足：

[xt=fxt，ut，" t∈[0，T]] （1）

并滿足以下要求：

1） 躲避障礙物，[x（t）∈Xfree]，[t∈[0，T]]，[Xfree=X-Xobs]；

2） 到達(dá)目標(biāo)區(qū)域，[x（t）∈Xgoal]；

3） 最小化代價(jià)函數(shù)[Jx=0Tgxtdt]，定積分。

漸進(jìn)最優(yōu)的RRT*算法在RRT算法的基礎(chǔ)上，采用代價(jià)函數(shù)來選取鄰近拓展節(jié)點(diǎn)內(nèi)最小代價(jià)的節(jié)點(diǎn)作為父節(jié)點(diǎn)，改變了RRT算法選擇最近節(jié)點(diǎn)作為父節(jié)點(diǎn)的選擇方式，并在每次迭代后重新連接現(xiàn)有樹上的節(jié)點(diǎn)，進(jìn)行優(yōu)化重布線，以實(shí)現(xiàn)改進(jìn)并滿足漸進(jìn)最優(yōu)。本文所涉及的最小代價(jià)不考慮路徑擁堵時(shí)間或其他成本等路徑規(guī)劃需考慮的代價(jià)，僅以歐氏距離作為最小代價(jià)優(yōu)化路徑。

RRT*算法在未達(dá)到終止條件之前是在不斷進(jìn)行迭代的，要在有限的時(shí)間中得出相對(duì)滿意的優(yōu)化路徑，因此RRT*算法的收斂時(shí)間是需要考慮的問題。在設(shè)計(jì)實(shí)現(xiàn)過程中，需要根據(jù)隨機(jī)采樣概率、生長(zhǎng)步長(zhǎng)、目標(biāo)點(diǎn)閾值、最大迭代步數(shù)等參數(shù)的合理設(shè)置和調(diào)整，確保概率完備和收斂速度。

2.2" 碰撞檢測(cè)策略

三維空間中動(dòng)目標(biāo)與障礙物間的碰撞檢測(cè)是動(dòng)目標(biāo)運(yùn)動(dòng)規(guī)劃和反映真實(shí)避免碰撞的基礎(chǔ)。一般將虛擬環(huán)境中的碰撞檢測(cè)采用幾何領(lǐng)域理論解決，算法分為空間剖分法和層次包圍盒樹方法[20?24]。

球包圍盒是能夠包含對(duì)象的最小包圍球，對(duì)于給定的障礙物對(duì)象，首先需分別計(jì)算對(duì)象中所有頂點(diǎn)的X坐標(biāo)、Y坐標(biāo)和Z坐標(biāo)均值以確定包圍球的球心，再由球心與三個(gè)最大值坐標(biāo)所確定點(diǎn)間的距離計(jì)算半徑。對(duì)于兩個(gè)包圍球[x1，y1，z1，r1]和[（x2，y2，z2，r2）]，如果球心距離小于半徑之和，即：

[x1-x22+y1-y22+z1-z22≤r1+r2]

則兩包圍球相交，即發(fā)生碰撞。

本文側(cè)重描述路徑規(guī)劃改進(jìn)算法，針對(duì)路徑規(guī)劃算法中的碰撞檢測(cè)問題，采用層次包圍盒樹方法中的球包圍盒（Sphere）以簡(jiǎn)化碰撞檢測(cè)計(jì)算過程，進(jìn)行井下巷道漫游路徑規(guī)劃算法仿真，且暫不考慮動(dòng)目標(biāo)本身的體積大小，以近似點(diǎn)描述動(dòng)目標(biāo)對(duì)象，快速驗(yàn)證本文提出的改進(jìn)路徑規(guī)劃算法的特征和尋優(yōu)效果。首先，提出將路徑規(guī)劃上的新增長(zhǎng)路徑，以一定數(shù)值的步長(zhǎng)距離等比均分為無數(shù)個(gè)檢測(cè)點(diǎn)（每個(gè)點(diǎn)可以看成一個(gè)半徑為0的球心）；然后，依次檢測(cè)路徑上的每個(gè)檢測(cè)點(diǎn)是否與其他球包圍盒包圍的障礙物發(fā)生碰撞的策略，實(shí)現(xiàn)三維場(chǎng)景中尋找無碰撞路徑的碰撞檢測(cè)過程。

2.3" 改進(jìn)方法設(shè)計(jì)與實(shí)現(xiàn)

RRT*算法要在有限的時(shí)間中得出相對(duì)滿意的優(yōu)化路徑。設(shè)計(jì)實(shí)現(xiàn)過程中，需要根據(jù)隨機(jī)采樣概率、生長(zhǎng)步長(zhǎng)、目標(biāo)點(diǎn)閾值、最大迭代步數(shù)等參數(shù)的合理設(shè)置和調(diào)整，以保證概率完備和收斂速度。

為了提高RRT*擴(kuò)展的導(dǎo)向性，本文以50%的概率在空間中隨機(jī)生成新的隨機(jī)點(diǎn)。50%的概率以逼近目標(biāo)點(diǎn)為新的隨機(jī)點(diǎn)，并根據(jù)已知環(huán)境空間實(shí)際情況配置隨機(jī)樹生長(zhǎng)步長(zhǎng)、最大迭代步數(shù)和目標(biāo)點(diǎn)閾值。

2.3.1" 重新選擇父節(jié)點(diǎn)和隨機(jī)樹重布線的過程

RRT*算法的詳細(xì)步驟如下。

1） 初始化樹結(jié)構(gòu)：設(shè)定起始點(diǎn)[xstart]和目標(biāo)點(diǎn)[xgoal]，創(chuàng)建一個(gè)包含起始節(jié)點(diǎn)的樹結(jié)構(gòu)Tree；

2） 隨機(jī)采樣：隨機(jī)生成一個(gè)節(jié)點(diǎn)[xrand]，作為目標(biāo)節(jié)點(diǎn)；

3） 最近鄰節(jié)點(diǎn)：從樹結(jié)構(gòu)中找到最近鄰的節(jié)點(diǎn)[xnear]，即距離目標(biāo)節(jié)點(diǎn)最近的節(jié)點(diǎn)；

4） 擴(kuò)展節(jié)點(diǎn)：從最近鄰節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)方向根據(jù)步長(zhǎng)擴(kuò)展一定距離，并在路徑上插入新的節(jié)點(diǎn)[xnew]；

5） 碰撞檢測(cè)：檢測(cè)路徑[xnear]到[xnew]之間是否與障礙物發(fā)生碰撞，如果發(fā)生碰撞，則返回步驟2）繼續(xù)下一次迭代；

6） 連接節(jié)點(diǎn)：將[xnew]節(jié)點(diǎn)與樹結(jié)構(gòu)中的最近鄰節(jié)點(diǎn)[xnear]連接起來，形成一條路徑，并更新節(jié)點(diǎn)間的連接關(guān)系；

7） 優(yōu)化路徑：對(duì)于新生成的路徑，檢查是否存在更短的路徑，如果存在，則更新路徑；

8） 判斷終止條件：重復(fù)步驟2）～步驟6），直到找到一條到達(dá)目標(biāo)點(diǎn)[xgoal]的路徑或達(dá)到最大迭代次數(shù)。

RRT*算法與RRT算法不同之處在于重新選擇父節(jié)點(diǎn)步驟6）和優(yōu)化路徑步驟7）。不同于RRT算法中直接選擇[xnearest]作為[xnew]的父節(jié)點(diǎn)，RRT*算法需要重新為[xnew]選擇父節(jié)點(diǎn)，使得[xnew]到起點(diǎn)的代價(jià)Cost能夠最小，本文Cost的定義為路徑的長(zhǎng)度。以新產(chǎn)生的節(jié)點(diǎn)[xnew]為圓心，在r為半徑的圓形范圍內(nèi)尋找所有的樹上鄰近節(jié)點(diǎn)[xnear]的集合，在[xnear]的集合中遍歷以重新選擇父節(jié)點(diǎn)，替換[xnew]原始父節(jié)點(diǎn)[xnearest]。依次計(jì)算起點(diǎn)到每個(gè)鄰近節(jié)點(diǎn)[xnear]的路徑代價(jià)加上近鄰節(jié)點(diǎn)[xnear]到[xnew]的路徑代價(jià)，并作碰撞檢測(cè)判斷，取無碰撞且路徑代價(jià)最小的近鄰節(jié)點(diǎn)[xmin]作為[xnew]新的父節(jié)點(diǎn)。

其次就是在重新選完父節(jié)點(diǎn)后，為該節(jié)點(diǎn)的所有近鄰節(jié)點(diǎn)重新布線即Rewrite過程，布線的原則是使所有節(jié)點(diǎn)到起點(diǎn)的Cost最小，尋優(yōu)過程示意圖如圖1所示。

RRT*加入路徑代價(jià)具備漸進(jìn)優(yōu)化的特性，通過上述重新選擇父節(jié)點(diǎn)和隨機(jī)樹重布線的優(yōu)化步驟，減少了大部分的無用路徑搜索和路徑邊徑的內(nèi)存存儲(chǔ)，提高了路徑規(guī)劃的效率，并且是概率完備和收斂的。

2.3.2" 貪心策略優(yōu)化過程

在經(jīng)過RRT*算法規(guī)劃出路徑的基礎(chǔ)上引入貪心算法，采用貪心策略優(yōu)化路徑，實(shí)現(xiàn)從起始位置到目標(biāo)位置平滑的運(yùn)動(dòng)路徑規(guī)劃。所求平滑路徑的整體最優(yōu)解可以通過一系列的局部最優(yōu)選擇來達(dá)到，貪心策略優(yōu)化步驟如下。

1） 連接目標(biāo)點(diǎn)和初始點(diǎn)。

2） 檢測(cè)是否發(fā)生碰撞，若是，表明從初始點(diǎn)到該點(diǎn)中間不能被省略，沿目標(biāo)點(diǎn)往上回溯到上一級(jí)父節(jié)點(diǎn)，上一級(jí)父節(jié)點(diǎn)更新為新的目標(biāo)點(diǎn)，回到步驟1）；若否，表明從初始點(diǎn)到該點(diǎn)中間的所有節(jié)點(diǎn)均可被省略，將該點(diǎn)添加到新的隨機(jī)樹中，并將該點(diǎn)更新為新的初始點(diǎn)，目標(biāo)點(diǎn)復(fù)位到最后一個(gè)節(jié)點(diǎn)，回到步驟1）。

3） 檢測(cè)直到路徑更新從[xstart]至[xgoal]結(jié)束。

經(jīng)過貪心算法優(yōu)化后的路徑如圖2所示。

貪心算法優(yōu)化路徑減少了很多因?yàn)镽RT*算法固定步長(zhǎng)擴(kuò)展搜索樹時(shí)產(chǎn)生的許多可被省略的無碰撞節(jié)點(diǎn)，使得規(guī)劃的路徑轉(zhuǎn)折少且路徑代價(jià)更?。W氏距離更短），并達(dá)到平滑路徑的效果，解決了規(guī)劃路徑的振蕩問題，更符合煤礦井下巷道中動(dòng)目標(biāo)的運(yùn)動(dòng)特性和實(shí)際運(yùn)動(dòng)路徑。

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

3.1" RRT*算法效果

在已知的40×40二維空間和三個(gè)不規(guī)則多邊形障礙物環(huán)境中，通過Matlab仿真試驗(yàn)，分別模擬RRT算法和RRT*算法從已知起點(diǎn)到終點(diǎn)的無碰撞路徑規(guī)劃過程，規(guī)劃效果如圖3、圖4所示。

根據(jù)20次的仿真結(jié)果均可以直觀地看出，RRT*算法路徑規(guī)劃的結(jié)果優(yōu)于RRT算法，具體如：搜索樹探索的區(qū)域和樹分支更少，存儲(chǔ)空間更小，路徑節(jié)點(diǎn)數(shù)量更少，路徑代價(jià)更小，路徑收斂速度更快且較平滑。

同時(shí)通過Matlab仿真試驗(yàn)，建立井下三維巷道，并在巷道內(nèi)設(shè)置大小各異的球形障礙物模擬井下巷道安裝的各類設(shè)備。在三維空間中模擬基于RRT*算法的從已知起點(diǎn)到終點(diǎn)的無碰撞路徑規(guī)劃過程，以50%的概率在空間中隨機(jī)生成新的隨機(jī)點(diǎn)，以50%的概率將目標(biāo)點(diǎn)作為新的隨機(jī)點(diǎn)，引導(dǎo)隨機(jī)點(diǎn)向目標(biāo)點(diǎn)逼近，并根據(jù)已知三維空間的實(shí)際環(huán)境約束情況做50次試驗(yàn)。依據(jù)每次的仿真效果，逐步調(diào)整并合理配置生長(zhǎng)步長(zhǎng)、最大迭代步數(shù)和目標(biāo)點(diǎn)閾值。

隨著迭代次數(shù)和采樣點(diǎn)的增加，得到的路徑越來越優(yōu)化，迭代的時(shí)間越久，就可以得到相對(duì)滿意的規(guī)劃路徑。算法仿真試驗(yàn)效果如圖5、圖6所示。

3.2" 引入貪心算法效果

在上述RRT*算法50次路徑規(guī)劃仿真試驗(yàn)結(jié)果中獲得漸進(jìn)最優(yōu)路徑的合理生長(zhǎng)步長(zhǎng)、最大迭代步數(shù)、目標(biāo)點(diǎn)閾值的基礎(chǔ)上，引入貪心算法進(jìn)一步優(yōu)化路徑以改進(jìn)路徑規(guī)劃方法。并再次通過Matlab在上述已知的井下三維巷道中進(jìn)行RRT*算法與改進(jìn)方法的50次對(duì)比仿真試驗(yàn)。改進(jìn)路徑規(guī)劃方法較RRT*算法進(jìn)一步優(yōu)化路徑的仿真試驗(yàn)效果如圖7所示。

通過Matlab在三維可視化巷道模擬RRT算法、RRT*算法和本文所提的改進(jìn)方法從已知起點(diǎn)到終點(diǎn)的路徑尋優(yōu)過程試驗(yàn)，獲得仿真對(duì)比數(shù)據(jù)，見表1。

通過仿真效果與數(shù)據(jù)對(duì)比分析，本文提出的改進(jìn)方法引入貪心算法進(jìn)一步優(yōu)化RRT*算法尋求的路徑后，由于增加了算法優(yōu)化步驟，雖然路徑規(guī)劃總體計(jì)算時(shí)間上比RRT*算法略有增加，但是在路徑規(guī)劃的路徑長(zhǎng)度、路徑轉(zhuǎn)折次數(shù)上均有明顯的提高，減少了大部分的無用路徑搜索和路徑邊徑的內(nèi)存存儲(chǔ)，提高了路徑規(guī)劃的效率，且得到了更為平滑防抖的路徑，符合現(xiàn)實(shí)中人在行走避障時(shí)的尋求最優(yōu)路徑的運(yùn)動(dòng)特點(diǎn)，解決了避障路徑的振蕩問題，使得在三維巷道約束環(huán)境中進(jìn)行人員運(yùn)動(dòng)軌跡重現(xiàn)和巷道漫游時(shí)，更符合實(shí)際運(yùn)動(dòng)情況。運(yùn)動(dòng)避障過程如圖8所示。

4" 結(jié)" 論

本文提出了一種采用改進(jìn)快速探索隨機(jī)樹（RRT*）算法和貪心算法相融合來解決井下巷道復(fù)雜環(huán)境和高維空間尋求最優(yōu)路徑的方法。這一改進(jìn)方法使用優(yōu)先探索策略和貪心策略，可以更加有效地探索到相對(duì)滿意的避障規(guī)劃路徑，同時(shí)解決了RRT*算法生成的路徑不夠光滑導(dǎo)致運(yùn)動(dòng)時(shí)會(huì)發(fā)生振蕩的問題，使得煤礦井下作業(yè)人員在三維可視化巷道內(nèi)漫游、運(yùn)動(dòng)軌跡重現(xiàn)等虛擬現(xiàn)實(shí)過程中的避障路徑規(guī)劃問題更符合井下人員實(shí)際運(yùn)動(dòng)情況，更能滿足透明礦井?dāng)?shù)字孿生場(chǎng)景等三維可視化技術(shù)的進(jìn)一步智能化發(fā)展需求。通過Matlab仿真實(shí)驗(yàn)平臺(tái)進(jìn)行驗(yàn)證，結(jié)果表明：所提出的改進(jìn)方法可得到滿意的避障規(guī)劃路徑；且相較于RRT*算法，該方法減少了大部分的無用路徑搜索和路徑邊徑的內(nèi)存存儲(chǔ)，提高了路徑規(guī)劃的效率，有效解決了虛擬現(xiàn)實(shí)過程中運(yùn)動(dòng)路徑振蕩問題，實(shí)現(xiàn)了平滑的路徑規(guī)劃。

參考文獻(xiàn)

[1] 王梓強(qiáng)，胡曉光，李曉筱，等.移動(dòng)機(jī)器人全局路徑規(guī)劃算法綜述[J].計(jì)算機(jī)科學(xué)，2021，48（10）：19?29.

[2] 陶德俊，姜媛媛，劉延彬，等.煤礦救援機(jī)器人路徑平滑算法研究[J].工礦自動(dòng)化，2019，45（10）：49?54.

[3] 黃金彪，白潤(rùn)才，劉威，等.基于改進(jìn)RRT算法的露天礦路徑優(yōu)化模型[J].煤炭學(xué)報(bào)，2021，46（12）：3846?3854.

[4] 陳都，侯明，張學(xué)東.改進(jìn)RRT結(jié)合B樣條的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].電子測(cè)量技術(shù)，2022，45（23）：38?44.

[5] 中國(guó)工商銀行股份有限公司.跨區(qū)巡檢機(jī)器人的路徑規(guī)劃方法、裝置和存儲(chǔ)介質(zhì)：CN202110542945.6[P].2021?08?13.

[6] 張婷婷，柳林燕，汪惠芬.基于改進(jìn)RRT的關(guān)節(jié)機(jī)械臂路徑規(guī)劃[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2022（5）：11?14.

[7] MENINI Laura.Algebraic geometry for robotics and control theory [M]. Singapore： World Scientific Publishing， 2021.

[8] 黃友銳，李靜，韓濤，等.基于膜計(jì)算的煤礦井下機(jī)器人路徑規(guī)劃算法[J].工礦自動(dòng)化，2021，47（11）：22?29.

[9] 楊煒，譚亮，孫雪，等.基于優(yōu)化快速搜索隨機(jī)樹算法的全局路徑規(guī)劃[J].汽車技術(shù)，2024（3）：31?36.

[10] 彭君.改進(jìn)RRT算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用研究[D].南京：南京郵電大學(xué)，2022.

[11] 王碩，段蓉凱，廖與禾.機(jī)器人路徑規(guī)劃中快速擴(kuò)展隨機(jī)樹算法的改進(jìn)研究[J].西安交通大學(xué)學(xué)報(bào)，2022，56（7）：1?8.

[12] 王道斌，嚴(yán)之偉，李駿敏，等.一種基于RRT*算法改進(jìn)的無人車路徑規(guī)劃方法及系統(tǒng)：CN202310334531.3[P].2023?07?25.

[13] 張衛(wèi)波，肖繼亮.改進(jìn)RRT算法在復(fù)雜環(huán)境下智能車路徑規(guī)劃中的應(yīng)用[J].中國(guó)公路學(xué)報(bào)，2021，34（3）：225?234.

[14] 袁曉明，郝明銳.煤礦輔助運(yùn)輸機(jī)器人關(guān)鍵技術(shù)研究[J].工礦自動(dòng)化，2020，46（8）：8?14.

[15] 朱子祺，李創(chuàng)業(yè)，代偉.基于G?RRT*算法的煤矸石分揀機(jī)器人路徑規(guī)劃[J].工礦自動(dòng)化，2022，48（3）：55?62.

[16] 薛光輝，劉爽，王梓杰，等.基于改進(jìn)概率路線圖算法的煤礦機(jī)器人路徑規(guī)劃方法[J].工礦自動(dòng)化，2023，49（6）：175?181.

[17] 金祖進(jìn)，程剛，郭鋒，等.煤礦搜救機(jī)器人最優(yōu)路徑規(guī)劃算法[J].工礦自動(dòng)化，2018，44（10）：24?28.

[18] 蒂姆·拉夫加登.算法詳解（卷3）：貪心算法和動(dòng)態(tài)規(guī)劃[M].徐波，譯.北京：人民郵電出版社，2023.

[19] WANG Tengda， WU Wenjun， YANG Feng， et al. A greedy path planning algorithm based on pre?path?planning and real?time?conflict for multiple automated guided vehicles in large?scale outdoor scenarios [J]. High technology letters， 2023， 29（3）： 279?287.

[20] 劉超.虛擬環(huán)境中碰撞檢測(cè)算法的研究和實(shí)現(xiàn)[D].南京：南京航空航天大學(xué)，2018.

[21] 陳善言，關(guān)永，施智平，等.機(jī)器人碰撞檢測(cè)方法形式化[J].軟件學(xué)報(bào)，2022，33（6）：2246?2263.

[22] 董晶晶，夏青，游雄，等.利用拾取技術(shù)實(shí)現(xiàn)虛擬場(chǎng)景漫游中的碰撞檢測(cè)[J].測(cè)繪科學(xué)，2009，34（4）：74?76.

[23] 王麗麗.基于二進(jìn)制空間分區(qū)樹的井下巷道相交建模方法[J].煤礦安全，2022，53（12）：138?143.

[24] 楊帆.基于B+樹存儲(chǔ)的AABB包圍盒碰撞檢測(cè)算法[J].計(jì)算機(jī)科學(xué)，2021，48（z1）：331?333.