渦流人工勢(shì)場(chǎng)引導(dǎo)下的RRT*移動(dòng)機(jī)器人路徑規(guī)劃

曹 凱，陳陽泉，高 嵩，高佳佳

1.西安工業(yè)大學(xué)機(jī)電工程學(xué)院，西安 710021

2.西安工業(yè)大學(xué)電子信息工程學(xué)院，西安 710021

3.加州大學(xué)默塞德分校工程學(xué)院，美國(guó)默塞德95343

近年來智能移動(dòng)機(jī)器人在軍事國(guó)防、航空航天以及星球探索方面起到了重要的作用[1-4]，因而成為學(xué)術(shù)界研究和關(guān)注的熱點(diǎn)問題。移動(dòng)機(jī)器人在任務(wù)空間自由活動(dòng)的過程中，首先需要解決路徑規(guī)劃問題。路徑規(guī)劃是在靜態(tài)和動(dòng)態(tài)環(huán)境、模型約束以及不確定性的情況下，自動(dòng)生成到達(dá)預(yù)定目標(biāo)點(diǎn)的可行和最佳路徑的過程。目前已有許多路徑規(guī)劃算法用于解決靜態(tài)和動(dòng)態(tài)環(huán)境中的運(yùn)動(dòng)規(guī)劃問題[5]，例如人工勢(shì)場(chǎng)[6-7]、基于網(wǎng)格的方法[8-9]、神經(jīng)網(wǎng)絡(luò)[10]、進(jìn)化仿生的方法[11-13]和基于采樣的規(guī)劃[14-15]。

人工勢(shì)場(chǎng)（artificial potential fields，APF）包括目標(biāo)點(diǎn)周圍的吸引勢(shì)場(chǎng)和障礙物周圍的排斥勢(shì)場(chǎng)。吸引勢(shì)場(chǎng)使機(jī)器人朝向目標(biāo)移動(dòng)，斥力勢(shì)場(chǎng)使機(jī)器人遠(yuǎn)離障礙物，最終機(jī)器人將朝著吸引和排斥合力的方向移動(dòng)。雖然APF 具有簡(jiǎn)單的數(shù)學(xué)表達(dá)式和較高的計(jì)算效率，但也存在一些固有問題：

（1）容易陷入局部最??；

（2）障礙物密集且間隔較小的環(huán)境中找不到可行路徑；

（3）在狹窄通道和目標(biāo)點(diǎn)附近存在障礙物導(dǎo)致無法到達(dá)的情況下出現(xiàn)機(jī)器人振蕩。

以往的研究大多假設(shè)障礙物遠(yuǎn)離目標(biāo)點(diǎn)，在這種情況下，當(dāng)機(jī)器人接近目標(biāo)位置時(shí)，由于障礙物引起的排斥力可以忽略不計(jì)，機(jī)器人會(huì)被吸引力吸引到目標(biāo)位置。然而，在實(shí)際環(huán)境中目標(biāo)位置或許會(huì)非常接近障礙物，導(dǎo)致當(dāng)機(jī)器人靠近目標(biāo)時(shí)，也會(huì)接近附近的障礙物，而排斥力將遠(yuǎn)大于吸引力，并且目標(biāo)位置不是總勢(shì)能的全局最小值。因此，由于附近的障礙物，機(jī)器人無法到達(dá)目標(biāo)。針對(duì)這一問題，考慮到機(jī)器人與目標(biāo)之間的相對(duì)距離，對(duì)路徑規(guī)劃中的排斥勢(shì)函數(shù)進(jìn)行了修正，從而確?？倓?shì)在目標(biāo)位置有一個(gè)全局最小值，機(jī)器人最終會(huì)達(dá)到目標(biāo)[16]。

基于采樣的規(guī)劃（sampling-based planning，SBP）算法對(duì)配置空間進(jìn)行純粹的探索，以保證算法的概率完備性。其中Kavraki 等人于1994 年提出的概率路線圖（probabilistic roadmap，PRM）[17]和Lavalle 于1998 年提出的快速隨機(jī)探索樹（rapidly-exploring random tree，RRT）[18]是最有效的SBP 算法。然而，PRM對(duì)障礙物信息的依賴使得它只適用于靜態(tài)環(huán)境。相比之下，RRT 更適合動(dòng)態(tài)環(huán)境和未知場(chǎng)景，并且可以包含非完整約束條件。

RRT 算法是從根（起始點(diǎn)）開始向未探索的區(qū)域隨機(jī)生成一棵可行軌跡樹，當(dāng)其中一條無碰撞軌跡到達(dá)目標(biāo)區(qū)域時(shí)產(chǎn)生一條可行路徑。而路徑間隙、路徑長(zhǎng)度以及規(guī)劃時(shí)間都取決于節(jié)點(diǎn)產(chǎn)生的隨機(jī)性。因此，RRT 算法主要問題有：

（1）在初始迭代期間，目標(biāo)區(qū)域附近的有用樣本無法最快做出貢獻(xiàn)，增加了規(guī)劃時(shí)間；

（2）在整個(gè)探索空間中進(jìn)行探索采樣，產(chǎn)生較多節(jié)點(diǎn)，擴(kuò)大了內(nèi)存需求；

（3）尋找到的路徑往往不是最優(yōu)的，路徑成本較高，且向最優(yōu)路徑收斂緩慢；

（4）車輛與障礙物之間的距離，會(huì)改變生成路徑的間隙，從而影響路徑安全。

目前，有大量文獻(xiàn)關(guān)于RRT 算法以及RRT*算法存在的問題提出了一些解決方案，例如文獻(xiàn)[19]提出RRT-Connect 方法，它從起始點(diǎn)和目標(biāo)點(diǎn)生長(zhǎng)兩棵不同的樹，同時(shí)不斷嘗試用貪婪的啟發(fā)式方法連接它們，以改善規(guī)劃時(shí)間。在文獻(xiàn)[20]中，限制節(jié)點(diǎn)擴(kuò)展的最大數(shù)量，并通過刪除無效節(jié)點(diǎn)，添加高性能節(jié)點(diǎn)，保證了完整節(jié)點(diǎn)重新布線后的路徑長(zhǎng)度最短，但是收斂速度比RRT*慢。RRT*算法作為RRT 的一種重要變體。文獻(xiàn)[21]中的RRT*算法通過配置路徑成本函數(shù)來連接樹中的節(jié)點(diǎn)，從而降低路徑長(zhǎng)度。文獻(xiàn)[22]和文獻(xiàn)[23]提出在找到可行路徑之后，對(duì)路徑再進(jìn)行優(yōu)化以得到較短的路徑。文獻(xiàn)[24]使用啟發(fā)式滑動(dòng)窗口采樣減少B-RRT*算法隨機(jī)采樣所帶來的誤差，并將車輛運(yùn)動(dòng)學(xué)約束加入到重選父節(jié)點(diǎn)和重布隨機(jī)樹的過程，使用貝塞爾曲線對(duì)所規(guī)劃的路徑進(jìn)行平滑處理。文獻(xiàn)[25]采用目標(biāo)偏向策略和氣味擴(kuò)散法來改善擴(kuò)展節(jié)點(diǎn)的選取，使得隨機(jī)樹的生長(zhǎng)趨向于目標(biāo)點(diǎn)，并提出一種基于三次B 樣條曲線的路徑平滑方法，極大地提升了搜索效率和路徑質(zhì)量。

本研究在APF 中加入渦流的引導(dǎo)，并與RRT*采樣的方法相結(jié)合來解決RRT*存在的一些問題。該方法利用渦流人工勢(shì)場(chǎng)（vortex-APF，VAPF）引導(dǎo)探索更有前途的配置空間，減少了得到最優(yōu)路徑的迭代次數(shù)，從而降低執(zhí)行時(shí)間，加快收斂速度。在軌跡樹中拒絕插入無效節(jié)點(diǎn)和高成本節(jié)點(diǎn)，以降低內(nèi)存需求。然后對(duì)可行路徑進(jìn)行修剪和平滑處理，在無障礙區(qū)域連接盡可能少的節(jié)點(diǎn)得到一條長(zhǎng)度較短、更為平滑的最優(yōu)或次優(yōu)路徑。仿真結(jié)果表明，該方法在內(nèi)存需求、執(zhí)行時(shí)間和路徑復(fù)雜性方面均具有有效性。

1 相關(guān)工作

1.1 RRT*算法

RRT 算法是通過隨機(jī)探索自由空間，并構(gòu)建一棵從起始點(diǎn)（zstart）開始尋找朝向目標(biāo)狀態(tài)的可行路徑的樹。在迭代的過程中，創(chuàng)建隨機(jī)點(diǎn)并搜索距離該點(diǎn)最近的頂點(diǎn)，然后以固定步長(zhǎng)得到該方向上的新節(jié)點(diǎn)，并檢查其是否屬于自由空間，直至達(dá)到目標(biāo)（zgoal）。

RRT*算法使用了三個(gè)新的概念對(duì)RRT 進(jìn)行了改進(jìn)：第一個(gè)是新增節(jié)點(diǎn)的本地鄰域；第二個(gè)是成本函數(shù)，它計(jì)算了從初始狀態(tài)到樹中節(jié)點(diǎn)的總成本；第三個(gè)是重新布線，它利用路徑成本函數(shù)在新增節(jié)點(diǎn)的本地鄰域中重新布線，從而降低路徑成本。RRT*算法的流程與RRT 算法類似，在迭代的過程中，創(chuàng)建隨機(jī)采樣節(jié)點(diǎn)，搜索到該點(diǎn)的最近節(jié)點(diǎn)znearest，根據(jù)固定步長(zhǎng)連接到最近的節(jié)點(diǎn)，就形成探索樹中的新節(jié)點(diǎn)。新節(jié)點(diǎn)領(lǐng)域中的點(diǎn)znear由新節(jié)點(diǎn)為中心半徑為r的區(qū)域來確定，如果通過新節(jié)點(diǎn)的路徑比通過當(dāng)前父節(jié)點(diǎn)的路徑具有更低的成本并且兩點(diǎn)之間是無障礙區(qū)域，那么新節(jié)點(diǎn)被設(shè)置為最佳父節(jié)點(diǎn)以保持樹的結(jié)構(gòu)，如圖1 所示。

重復(fù)上述過程來維護(hù)節(jié)點(diǎn)樹的增長(zhǎng)，直到達(dá)到目標(biāo)。如果目標(biāo)狀態(tài)位于障礙物空間中，則迭代過程被中止或者尋找路徑失敗，稱為陷阱狀態(tài)。RRT*算法的基本流程如下所示。

Fig.1 RRT*node extension process圖1 RRT*節(jié)點(diǎn)擴(kuò)展過程

算法1T=(V,E)←RRT*(zstart,zgoal)

1.2 人工勢(shì)場(chǎng)法

1986 年，Khatib 提出利用勢(shì)場(chǎng)進(jìn)行避障和路徑規(guī)劃的思想[26]，即人工勢(shì)場(chǎng)法APF。它來自物理學(xué)中場(chǎng)的概念，它將物體的運(yùn)動(dòng)視為兩種力相互作用的結(jié)果。因此在該方法中，機(jī)器人被建模為受吸引力和排斥力影響的粒子。障礙物表示為斥力場(chǎng)Urep，目標(biāo)則是吸引場(chǎng)Uatt。在吸引力和排斥力的共同作用下，機(jī)器人沿著合力的方向移動(dòng)，安全地到達(dá)目標(biāo)區(qū)域，即不發(fā)生任何碰撞。目標(biāo)點(diǎn)對(duì)于機(jī)器人的引力場(chǎng)和斥力場(chǎng)如式（1）和式（2）所示，目標(biāo)對(duì)于機(jī)器人的吸引力Fatt和排斥力Frep分別為吸引勢(shì)場(chǎng)和排斥勢(shì)場(chǎng)的負(fù)梯度，如式（3）和式（4）所示。吸引勢(shì)場(chǎng)和排斥勢(shì)場(chǎng)的矢量和是勢(shì)場(chǎng)的總和Ftotal，其計(jì)算公式如式（5）所示。

式（1）～（5）中，x是機(jī)器人當(dāng)前的位置，xg為目標(biāo)點(diǎn)，機(jī)器人與障礙物之間的最短距離用ρ表示，ρ0表示勢(shì)場(chǎng)的最小影響距離，Ka和Kr分別表示吸引場(chǎng)和斥力場(chǎng)的縮放因子。

2 路徑規(guī)劃混合優(yōu)化方法

2.1 改進(jìn)的RRT*算法（Improved RRT*）

在RRT*算法中遠(yuǎn)離生成路徑的擴(kuò)展節(jié)點(diǎn)重復(fù)連線，通常這些節(jié)點(diǎn)不僅沒有降低路徑成本，還因?yàn)闊o效節(jié)點(diǎn)間的重新布線增加了時(shí)間成本。因此，在生成路徑的節(jié)點(diǎn)附近進(jìn)行有意義的重新布線操作，可以有效地改善路徑成本。

改進(jìn)RRT*算法僅在有前途的區(qū)域中探索，生成更有前景的樹T，從而以更少的時(shí)間和更小的內(nèi)存需求找到最佳路徑。它以zstart為根來初始化探索樹T，先確定zstart和zgoal之間的偏向區(qū)域BRegion，然后隨機(jī)選擇BRegion中的節(jié)點(diǎn)進(jìn)行采樣，找到可行的初始路徑。同時(shí)對(duì)初始路徑使用節(jié)點(diǎn)拒絕技術(shù)，去除高成本節(jié)點(diǎn)和無效節(jié)點(diǎn)，然后進(jìn)行原始路徑修剪，獲得一條長(zhǎng)度更小，節(jié)點(diǎn)更少的優(yōu)化路徑，如圖2 所示。

首先，確定探索區(qū)域，使用偏向采樣探索區(qū)域，并對(duì)采樣產(chǎn)生的節(jié)點(diǎn)頻繁地進(jìn)行重新布線操作，這有利于迅速地降低當(dāng)前探索路徑的成本。當(dāng)發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)或目標(biāo)區(qū)域內(nèi)（最小步長(zhǎng)范圍內(nèi)）的節(jié)點(diǎn)時(shí)，找到一條從起始位置到目標(biāo)位置的初始路徑，如圖2（a）所示。如果當(dāng)前區(qū)域探索完成后未找到可行路徑，則重新改變區(qū)域的大小，直到找到目標(biāo)位置，如圖2（c）所示。

傾向得分匹配法可以控制處理組與對(duì)照組之間不可觀測(cè)且不隨時(shí)間變化的組間差異（Heckman，LaLonde & Smith，1999）。此方法的核心邏輯是針對(duì)樣本數(shù)據(jù)中不存在實(shí)施過境免簽政策地區(qū)在沒有實(shí)施此項(xiàng)政策情況下的入境旅游績(jī)效的“反事實(shí)情形”，采用半?yún)?shù)估計(jì)方法估計(jì)實(shí)施地區(qū)未實(shí)施該項(xiàng)政策的傾向得分值，進(jìn)而為實(shí)施地區(qū)選擇匹配特征盡可能接近的未實(shí)施地區(qū)，保證處理組與對(duì)照組在政策實(shí)施前的發(fā)展軌跡基本“平行”。

Fig.2 Improved RRT*processing flow圖2 改進(jìn)的RRT*算法處理流程

探索區(qū)域的確定主要是利用起始點(diǎn)和目標(biāo)點(diǎn)之間的連線的斜率，計(jì)算出延長(zhǎng)線與地圖邊界之間的交點(diǎn)P和Q，然后對(duì)P和Q分別加減100 單位（可根據(jù)地圖比例調(diào)節(jié)），得到與地圖相交的新交點(diǎn)P1、P2、Q1 和Q2，并連接P1 和Q1，P2 和Q2，得到新的直線方程。如果這些新交點(diǎn)超出地圖范圍，則以地圖頂點(diǎn)和直線方程重新計(jì)算得到交點(diǎn)P3 和Q3，P3、P2、Q1 和Q3 形成連通區(qū)域，如圖3 所示。

Fig.3 Determining biased region圖3 偏向區(qū)域確定的方法

其次，節(jié)點(diǎn)拒絕的工作是去除高成本節(jié)點(diǎn)和無效節(jié)點(diǎn)。如果新的節(jié)點(diǎn)和目標(biāo)之間的距離成本大于當(dāng)前路徑的距離成本，那么新采樣的節(jié)點(diǎn)就被拒絕插入樹中。此外，如果某一個(gè)節(jié)點(diǎn)不能被擴(kuò)展（沒有子節(jié)點(diǎn)或者僅有一個(gè)子節(jié)點(diǎn)），這也意味著它不在達(dá)到目標(biāo)狀態(tài)的路徑上，這樣的節(jié)點(diǎn)也會(huì)從樹杈中被刪除掉。因此，只通過有用節(jié)點(diǎn)來擴(kuò)展樹，不僅可以維持樹的成本，還可以快速地尋找到一條路徑成本較小、收斂時(shí)間最短、內(nèi)存需求最少的可行路徑，如圖2（c）所示。

最后，對(duì)先前得到的路徑進(jìn)行修剪（類似于樹木生長(zhǎng)過程中需要將多余的樹枝修剪掉，以保證樹主干的營(yíng)養(yǎng)吸收）。因?yàn)镽RT*算法是概率完備的，它傾向于隨機(jī)點(diǎn)方向構(gòu)建可行軌跡樹，所以大多數(shù)解決方案不是最優(yōu)的。因此，需要采用修剪算法以獲得路程更短，噪聲更少的路徑，如圖2（d）所示。

路徑修剪的原理如圖4 所示，獲得初始路徑后，從起點(diǎn)開始遍歷每一個(gè)路徑節(jié)點(diǎn)并相互連線，如果起點(diǎn)和其中的一個(gè)節(jié)點(diǎn)Zp1之間存在障礙物（藍(lán)色虛線），則退回Zp1的上一個(gè)節(jié)點(diǎn)Zp1-1，而起點(diǎn)到Zp1-1之間的線段就是一段平滑路徑。同時(shí)，Zp1-1作為新的起點(diǎn)遍歷剩余的路徑節(jié)點(diǎn)。以此類推，直到遍歷到目標(biāo)點(diǎn)形成一條優(yōu)化后的低成本路徑（橙色虛線）。

Fig.4 Path pruning圖4 路徑修剪

2.2 改進(jìn)的APF 方法

APF 方法將障礙物作為移動(dòng)機(jī)器人的斥力場(chǎng)，斥力場(chǎng)是以障礙物為中心產(chǎn)生向外發(fā)散的排斥力，從而使機(jī)器人遠(yuǎn)離障礙物，如圖5 所示。圖5 中的紅色線條表示3 個(gè)圓形障礙物向外產(chǎn)生的發(fā)散的排斥力。雖然在吸引力的作用下可以到達(dá)目標(biāo)點(diǎn)，往往難以遵循能量最小、時(shí)間和路徑最優(yōu)等優(yōu)化準(zhǔn)則。

Fig.5 Repulsive field distribution圖5 斥力場(chǎng)分布

本研究在APF 的基礎(chǔ)上將渦流引入勢(shì)場(chǎng)，從而形成渦流場(chǎng)。渦流場(chǎng)可以產(chǎn)生切向梯度，利用迫使機(jī)器人繞過每個(gè)障礙物的動(dòng)作來代替原本的排斥動(dòng)作，從而引導(dǎo)機(jī)器人避開指向自然運(yùn)動(dòng)方向的有害或不利梯度，如圖6 所示。

通過對(duì)機(jī)器人與障礙物之間位置關(guān)系進(jìn)行反切運(yùn)算可以得到渦流場(chǎng)的方向。同時(shí)，在原有的斥力場(chǎng)計(jì)算中加入了梯度信息和機(jī)器人與障礙物之間的距離可以得到渦流斥力場(chǎng)。渦流人工勢(shì)場(chǎng)（VAPF）的引入，能夠使機(jī)器人的路徑更加平滑。

Fig.6 Vortex repulsive field distribution圖6 渦流斥力場(chǎng)分布

2.3 VAPF 與改進(jìn)的RRT*混合優(yōu)化方法

首先利用RRT*算法在偏向區(qū)域中進(jìn)行隨機(jī)采樣，然后根據(jù)機(jī)器人的位置和障礙物的影響范圍，計(jì)算了作用于機(jī)器人的渦流場(chǎng)，并利用隨機(jī)吸引場(chǎng)梯度下降對(duì)隨機(jī)采樣點(diǎn)zrand進(jìn)行改造，得到一個(gè)引導(dǎo)采樣點(diǎn)zprand，同時(shí)利用節(jié)點(diǎn)拒絕技術(shù)將路徑中無效的節(jié)點(diǎn)（不在主路徑中的節(jié)點(diǎn)）進(jìn)行剔除，通過節(jié)點(diǎn)擴(kuò)展的迭代得到一條初始路徑，然后進(jìn)行路徑修剪和路徑平滑處理，最終可以得到一條最優(yōu)路徑。VAPFRRT*混合優(yōu)化方法的基本流程如下所示：

算法2T=(V,E)←VAPF-RRT*(zstart,zgoal)

算法第6 行中的隨機(jī)梯度下降（randomized gradient descent，RGD）子函數(shù)表示隨機(jī)吸引場(chǎng)梯度下降，它用吸引勢(shì)場(chǎng)對(duì)隨機(jī)采樣點(diǎn)zrand進(jìn)行擴(kuò)展，得到一個(gè)改進(jìn)的采樣點(diǎn)xprand，并將xprand作為后續(xù)算法的隨機(jī)采樣點(diǎn)。算法流程偽代碼如下所示：

函數(shù)1RGD(zrand)

3 算法仿真與結(jié)果分析

本研究在Matlab2016 中設(shè)計(jì)仿真場(chǎng)景，分別使用RRT、改進(jìn)RRT*和VAPF-RRT*方法進(jìn)行路徑規(guī)劃，考慮到RRT 類算法具有概率隨機(jī)性，因此每種方法進(jìn)行了32 次實(shí)驗(yàn)，取平均路徑長(zhǎng)度、執(zhí)行時(shí)間和采樣節(jié)點(diǎn)用來分析路徑規(guī)劃方法的性能。為了將執(zhí)行時(shí)間限制在合理范圍，迭代次數(shù)設(shè)定為2 000 次。

仿真場(chǎng)景由多個(gè)不同半徑的圓形障礙物組成，使用RRT 和改進(jìn)RRT*方法完成路徑規(guī)劃的效果圖，如圖7 所示。使用VAPF-RRT*方法對(duì)障礙物產(chǎn)生的渦流場(chǎng)和路徑規(guī)劃效果圖，如圖8 所示。

使用3 種算法在上述場(chǎng)景分別進(jìn)行32 次仿真實(shí)驗(yàn)，表1 給出了每種算法用于達(dá)到最優(yōu)路徑解的平均執(zhí)行時(shí)間、采樣節(jié)點(diǎn)和路徑成本。

Fig.7 RRT and improved RRT*path planning圖7 RRT 與改進(jìn)的RRT*方法路徑規(guī)劃

Fig.8 VAPF-RRT*vortex and path planning圖8 VAPF-RRT*方法產(chǎn)生的渦流場(chǎng)和路徑規(guī)劃

Table 1 Simulation results for calculating optimal or approximate optimal path表1 計(jì)算最優(yōu)或近似最優(yōu)路徑的仿真結(jié)果

從圖7 中可以直觀地看出，改進(jìn)RRT*方法不論從擴(kuò)展節(jié)點(diǎn)數(shù)量還是路徑成本都要優(yōu)于RRT 算法，而圖8 顯示了VAPF-RRT*算法沒有擴(kuò)展多余的節(jié)點(diǎn)，形成的路徑更加平滑，而且斥力場(chǎng)的存在使機(jī)器人與障礙物之間保持相對(duì)距離，從而保證了機(jī)器人在運(yùn)動(dòng)過程中的安全性。通過表1 可以得到，改進(jìn)RRT*算法的平均執(zhí)行時(shí)間和路徑成本是3 種方法中最優(yōu)的，相對(duì)于RRT 算法和VAPF-RRT*算法，執(zhí)行時(shí)間分別減少了12.1%和33.1%，路徑成本分別縮短了21.1%和10.3%，說明偏向區(qū)域搜索可以明確搜索方向，加快收斂速度，降低執(zhí)行時(shí)間；路徑修剪可以修剪多余節(jié)點(diǎn)，達(dá)到優(yōu)化路徑的效果。在擴(kuò)展節(jié)點(diǎn)方面，VAPF-RRT*方法的節(jié)點(diǎn)數(shù)量要優(yōu)于另外兩種方法，因?yàn)閂APF 的渦流場(chǎng)引導(dǎo)RRT*的隨機(jī)采樣節(jié)點(diǎn)，并將引導(dǎo)節(jié)點(diǎn)作為路徑形成的導(dǎo)航點(diǎn)，從而降低擴(kuò)展節(jié)點(diǎn)的數(shù)量。改進(jìn)RRT*方法在偏向區(qū)域中隨機(jī)采樣再進(jìn)行節(jié)點(diǎn)拒絕，收斂速度要優(yōu)于使用渦流場(chǎng)來引導(dǎo)采樣節(jié)點(diǎn)。雖然路徑修剪使路徑成本有明顯的下降，但是容易出現(xiàn)優(yōu)化路徑貼著障礙物的情況，而且折線路徑在實(shí)際應(yīng)用中也存在較多問題。

從子函數(shù)RGD 流程中可以看出，障礙物勢(shì)場(chǎng)的影響距離ρ0會(huì)影響引導(dǎo)節(jié)點(diǎn)的選取，從而影響執(zhí)行時(shí)間、擴(kuò)展節(jié)點(diǎn)和路徑成本。本研究在實(shí)驗(yàn)過程中分別選取圓形障礙物半徑的1.0、1.5、2.0 和3.0 倍作為障礙物勢(shì)場(chǎng)的影響距離，圖9 顯示了選取不同影響距離對(duì)于最終路徑形成產(chǎn)生的影響，其中黑色圓圈為障礙物，包圍障礙物的青色圓圈為最小影響距離，綠色圓圈和深藍(lán)色圓圈分別為起始點(diǎn)和目標(biāo)點(diǎn)。

Fig.9 Path planning under different influence radii圖9 不同影響距離下的路徑規(guī)劃

從圖9（a）和圖9（b）中可以看出，選取1.0 倍和1.5 倍障礙物半徑作為勢(shì)場(chǎng)的影響距離，通過VAPFRRT*算法形成的路徑與障礙物之間保持的距離較小，甚至出現(xiàn)了貼著障礙物運(yùn)動(dòng)的情況，這不僅增加了執(zhí)行時(shí)間和路徑成本，也無法保證機(jī)器人在運(yùn)動(dòng)過程中的安全性。而對(duì)2.0 倍半徑的影響距離而言，規(guī)劃出的路徑不僅相對(duì)平滑，而且可以和障礙物之間保持相對(duì)安全的距離。對(duì)比圖9（c）和圖9（d）可以發(fā)現(xiàn)，路徑與障礙物之間的距離雖然稍有擴(kuò)大，但后半段的路徑卻出現(xiàn)了波動(dòng)。通過仿真實(shí)驗(yàn)發(fā)現(xiàn)，影響距離在大于2.0 倍障礙物半徑后，逐漸增加影響距離對(duì)路徑規(guī)劃已無明顯的改變。

綜上所述，仿真結(jié)果證明了VAPF-RRT*算法在執(zhí)行時(shí)間、采樣節(jié)點(diǎn)、路徑成本方面優(yōu)化的有效性，如：

（1）在偏向區(qū)域內(nèi)探索，加快了收斂到可行軌跡的速度，減少了規(guī)劃時(shí)間；

（2）VAPF 算法的渦流場(chǎng)效應(yīng)使節(jié)點(diǎn)產(chǎn)生的方向性增強(qiáng)，從而生長(zhǎng)軌跡更為集中的擴(kuò)展樹；

（3）降低了內(nèi)存需求，使RRT*算法也可以應(yīng)用于內(nèi)存有限的嵌入式系統(tǒng)；

（4）路徑修剪和路徑平滑，可以得到路徑長(zhǎng)度相對(duì)較短且平滑的路徑；

（5）RRT*算法的隨機(jī)性可以克服APF 算法容易陷入局部最優(yōu)的問題。

4 結(jié)束語

在本研究中，提出了一種渦流人工勢(shì)場(chǎng)引導(dǎo)下的RRT*算法來解決路徑規(guī)劃中存在的一些問題。通過多次仿真實(shí)驗(yàn)，其仿真結(jié)果可以定量分析改進(jìn)算法的優(yōu)越性、高效性和實(shí)用性。實(shí)驗(yàn)結(jié)果表明：本文方法可以有效地減少采樣節(jié)點(diǎn)，降低規(guī)劃時(shí)間并優(yōu)化得到一條相對(duì)較短且平滑的路徑。同時(shí)，RRT*算法的隨機(jī)性又克服了APF 算法容易陷入局部最優(yōu)的問題。

重復(fù)進(jìn)行實(shí)驗(yàn)后發(fā)現(xiàn)，雖然本研究中的方法可以使用較少的時(shí)間和較小的內(nèi)存，但是得到的路徑并非全局最優(yōu)路徑。此外，也沒有考慮實(shí)際場(chǎng)景中工業(yè)機(jī)器人和移動(dòng)機(jī)器人的運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)約束條件下的安全問題。未來研究工作中希望可以根據(jù)搜索的初始路徑擬合空間貝塞爾曲線，并通過優(yōu)化曲線控制點(diǎn)使行駛軌跡滿足各類約束的同時(shí)，提高路徑的平順性與安全性。最后希望本研究將可以應(yīng)用于自主無人車輛和工業(yè)生產(chǎn)加工的高維運(yùn)動(dòng)規(guī)劃研究領(lǐng)域。