改進(jìn)概率路標(biāo)圖算法

寧新杰，崔 煒，徐照翔，李興廣，陳鵬宇

(長(zhǎng)春理工大學(xué) 電子信息工程學(xué)院，吉林 長(zhǎng)春 130022)

0 引 言

目前，常用的路徑規(guī)劃算法有遺傳算法[1]、人工勢(shì)場(chǎng)法[2]、隨機(jī)路標(biāo)圖(PRM)算法[3]等算法。當(dāng)環(huán)境中的障礙物較為復(fù)雜，或在高維空間進(jìn)行規(guī)劃時(shí)，將導(dǎo)致規(guī)劃算法計(jì)算量大大增加，算法效率大大降低?；陔S機(jī)采樣的PRM算法可以有效解決高維空間或多障礙物的復(fù)雜環(huán)境中的路徑規(guī)劃問題，因此，PRM算法廣泛應(yīng)用于在機(jī)械臂路徑規(guī)劃[4]、建筑物疏散路徑規(guī)劃、分支管路自動(dòng)布局[5]等領(lǐng)域。

為了提高PRM算法中路線圖的連通性，Mali等提出應(yīng)用多重樣本的節(jié)點(diǎn)和路線圖的有效性[6]。Janso L等將隨機(jī)采樣序列替換為某種確定性采樣序列，用以實(shí)現(xiàn)PRM算法搜索到路徑的漸進(jìn)最優(yōu)[7]。楊岱川等對(duì)帶有實(shí)際地圖障礙物的多個(gè)目標(biāo)點(diǎn)進(jìn)行先后排序和路徑搜尋，較好地解決了目前存在的移動(dòng)處理器響應(yīng)速度慢和不能一次規(guī)劃多個(gè)目標(biāo)點(diǎn)路徑的問題[8]。李敏等提出一種定量計(jì)算自由空間障礙物數(shù)量稠密度的方法來(lái)解決窄通道問題[9]。SANTIAGO等將遺傳算法與PRM算法進(jìn)行結(jié)合，用來(lái)辨別PRM算法產(chǎn)生的隨機(jī)點(diǎn)，但該混合算法規(guī)劃的航跡收斂速度慢，只適用于特定場(chǎng)景[10]。然而，大部分學(xué)者的學(xué)者未將改進(jìn)方法的計(jì)算量考慮在內(nèi)，造成時(shí)間利用率降低，延長(zhǎng)規(guī)劃到可行路徑的時(shí)間，本文使用邊集優(yōu)化方法，通過對(duì)隨機(jī)點(diǎn)施加約束，對(duì)傳統(tǒng)PRM算法進(jìn)行改進(jìn)，對(duì)搜索到的路徑進(jìn)行峰值節(jié)點(diǎn)提取，形成一條更利于機(jī)器人行走的路徑，并通過仿真實(shí)驗(yàn)驗(yàn)證改進(jìn)PRM算法的可行性。

1 傳統(tǒng)PRM算法

PRM算法全稱是概率路標(biāo)圖算法(probabilistic roadmap)，是一種基于圖論的搜索算法，包含學(xué)習(xí)階段和查詢階段兩個(gè)階段。

1.1 學(xué)習(xí)階段

在學(xué)習(xí)階段，路線圖的數(shù)據(jù)結(jié)構(gòu)是依賴概率的方式為給定場(chǎng)景構(gòu)建的，路線圖是一個(gè)無(wú)向圖R=(N,E)，N代表在自由空間Cfree上所生成隨機(jī)點(diǎn)集合，E代表連接任意兩個(gè)節(jié)點(diǎn)的可行路徑的集合。首先使用足夠的隨機(jī)點(diǎn)來(lái)提供一個(gè)相當(dāng)均勻的自由空間Cfree覆蓋，這些隨機(jī)點(diǎn)構(gòu)成點(diǎn)集N，然后從當(dāng)前的N中選擇多個(gè)節(jié)點(diǎn)ni(i=1,2,3,……)構(gòu)成鄰近集Nc。使用局部規(guī)劃器計(jì)算ni與ni+1路徑，如果路徑與障礙物碰撞，則舍去，反之，則將路徑(邊)加入到E中。學(xué)習(xí)階段構(gòu)建路線圖R供查詢階段使用。

1.2 查詢階段

在查詢階段，路線圖被用來(lái)解決輸入場(chǎng)景中的單個(gè)路徑規(guī)劃問題。嘗試將源點(diǎn)s目標(biāo)點(diǎn)g分別與N中的節(jié)點(diǎn)si,gi進(jìn)行連接，如果連接成功，在路線圖R=(N,E)中從E中搜索連接si,gi的邊。通過重復(fù)計(jì)算符合要求的局部路徑，并將它們連接起來(lái)，最終，利用搜索算法在起點(diǎn)、路線圖R=(N,E)，PRM算法的算法效率取決于查詢階段的搜索速度，也就是說(shuō)查詢階段的工作量決定算法的效率。然而，通過傳統(tǒng)學(xué)習(xí)階段構(gòu)建的路線圖較為復(fù)雜，使用尋路算法進(jìn)行搜索會(huì)耗費(fèi)大量時(shí)間，且生成的路徑含有較多冗余節(jié)點(diǎn)。

2 PRM算法的局限性及相應(yīng)的改進(jìn)方法

2.1 PRM算法的局限性

傳統(tǒng)路線圖R(N,E)中的邊集E是通過每一個(gè)隨機(jī)點(diǎn)與其余一定范圍內(nèi)隨機(jī)點(diǎn)連接后，經(jīng)過可行性邊檢測(cè)后，除去與障礙物相交的邊，最終得到的邊集放入E中。然而，通過這種方式得到的邊集，在查詢階段使用搜索算法搜索時(shí)耗費(fèi)的時(shí)間較多，從而增加了PRM算法的運(yùn)行時(shí)間[11]。某隨機(jī)點(diǎn)n周圍較小范圍內(nèi)可能存在多個(gè)隨機(jī)點(diǎn)hi，將n與hi連接后構(gòu)成邊集E后，在一定程度上，增大了后續(xù)查詢階段尋路算法的計(jì)算量，延長(zhǎng)了尋路所用時(shí)間[12]。由于這些隨機(jī)點(diǎn)與該隨機(jī)點(diǎn)的連接構(gòu)成邊集E的一部分，因此，在查詢出的路徑中可能在較短距離內(nèi)發(fā)生轉(zhuǎn)折，這會(huì)導(dǎo)致機(jī)器人在行駛過程中頻繁的轉(zhuǎn)向，不利于機(jī)器人的能耗節(jié)省。

2.2 邊集優(yōu)化方法

針對(duì)于某隨機(jī)點(diǎn)周圍較近范圍內(nèi)存在較多隨機(jī)點(diǎn)會(huì)增加計(jì)算量且搜索出來(lái)的路徑中很短距離發(fā)生轉(zhuǎn)折的問題，采用對(duì)隨機(jī)點(diǎn)進(jìn)行約束的方法，對(duì)于存在于自由空間Cfree的采樣點(diǎn)，以其位置p為圓心，半徑為r1,r2分別繪制一個(gè)圓形區(qū)域，僅將圓心與圓環(huán)內(nèi)隨機(jī)點(diǎn)進(jìn)行連接，并對(duì)連接的邊進(jìn)行障礙物檢測(cè)，判斷各邊是否與障礙物相交，如果相交，則去掉相交的邊，如果不發(fā)生碰撞，則將其加入到該點(diǎn)的邊集中。具體如圖1所示，白色區(qū)域代表自由空間Cfree，黑色的小圓代表隨機(jī)點(diǎn)(將隨機(jī)點(diǎn)作為圓心點(diǎn)后進(jìn)行適當(dāng)放大)，黑色的橢圓形區(qū)域代表障礙物，在500*500的障礙物地圖中選取某隨機(jī)點(diǎn)B(XB,YB)，并以其為圓心，以r1,r2為半徑畫圓，且僅將該圓心點(diǎn)與圓環(huán)內(nèi)的隨機(jī)點(diǎn)Xi進(jìn)行連接，進(jìn)行障礙物檢測(cè)，去除碰撞邊后加入到邊集E中。該隨機(jī)點(diǎn)B(XB,YB)的邊集應(yīng)滿足以下條件：①點(diǎn)B與點(diǎn)Xi的歐氏距離小于半徑r1，且大于r2(r1大于r2)；②點(diǎn)B，點(diǎn)Xi是位于自由空間Cfree中的點(diǎn)；③根據(jù)所需的機(jī)器人行走步長(zhǎng)設(shè)計(jì)r1與r2的大小，r1與r2的差值應(yīng)不小于30(500*500地圖上)；④當(dāng)約束外徑一定時(shí)，隨著約束內(nèi)經(jīng)的增大，算法的時(shí)間復(fù)雜度逐漸減小。當(dāng)約束內(nèi)經(jīng)一定時(shí)，隨著約束外徑的增大，算法的時(shí)間復(fù)雜度逐漸增大。

圖1 某圓心點(diǎn)的邊集E

2.3 峰值節(jié)點(diǎn)提取

傳統(tǒng)方法PRM算法查詢出的路徑容易在一定范圍內(nèi)發(fā)生多次轉(zhuǎn)折，此外，邊集優(yōu)化方法也會(huì)產(chǎn)生一些冗余節(jié)點(diǎn)，這會(huì)導(dǎo)致路徑節(jié)點(diǎn)增多，路徑長(zhǎng)度增加，機(jī)器人行駛時(shí)間延長(zhǎng)的問題。針對(duì)這些問題，文中采用道格拉斯-普克抽稀算法[13]對(duì)查詢階段搜索到的路徑提取關(guān)鍵節(jié)點(diǎn)進(jìn)行二次優(yōu)化，是用來(lái)對(duì)冗余節(jié)點(diǎn)進(jìn)行壓縮后提取必要節(jié)點(diǎn)。提取關(guān)鍵節(jié)點(diǎn)的步驟如下：連接起點(diǎn)、終點(diǎn)得到一條準(zhǔn)線，之后計(jì)算path中除起始點(diǎn)和終點(diǎn)外，剩余結(jié)點(diǎn)到準(zhǔn)線的歐式距離，選取歐式距離最大的峰值結(jié)點(diǎn)，比較其與閾值φ的大小，如果其小于閾值φ，則舍去起點(diǎn)和終點(diǎn)之間的所有點(diǎn)，如果最大距離大于φ，則保留峰值節(jié)點(diǎn)，并將原線分割成兩部分，連接起點(diǎn)和峰值節(jié)點(diǎn)及峰值節(jié)點(diǎn)和終點(diǎn)，并對(duì)起點(diǎn)和峰值節(jié)點(diǎn)及峰值節(jié)點(diǎn)和終點(diǎn)之間的節(jié)點(diǎn)重復(fù)上述方法。抽稀結(jié)果中的節(jié)點(diǎn)數(shù)目隨著選取閾值φ的增大而減小，使用時(shí)根據(jù)所需精度來(lái)選取合適的閾值，來(lái)獲得最好的結(jié)果。

以圖2中路徑將道格拉斯-普克算法總結(jié)為以下幾步：

(1)如圖2(a)所示，使用虛線連接起點(diǎn)A(x1,y1)和終點(diǎn)H(x2,y2)，形成一條基準(zhǔn)線AH，將式(1)和式(2)進(jìn)行聯(lián)立求出a和b的值(a、b值為設(shè)一次函數(shù)方程時(shí)參數(shù)，a、b為常數(shù))使用式(3)找到距基準(zhǔn)線最大距離Dmax的峰值節(jié)點(diǎn)C(x0,y0)。

(2)如圖2(a)所示，過點(diǎn)C向基準(zhǔn)線做垂線交AH于點(diǎn)M，使用式(3)求出CM長(zhǎng)度為d，如果φ大于d，則舍去B,C,D,E,F等點(diǎn)。如果φ小于d，則用虛線連接AC，HC。

(3)對(duì)AC，HC這兩條新的基準(zhǔn)線重復(fù)步驟(1)，步驟(2)的操作。

(4)如圖2(c)將路徑起點(diǎn)、每次找到的峰值節(jié)點(diǎn)和終點(diǎn)連接起來(lái)，最終路徑為ACEH

圖2 道格拉斯-普克算法提取峰值節(jié)點(diǎn)

ax1+y1+b=0

(1)

ax2+y2+b=0

(2)

(3)

改進(jìn)后的PRM算法，在學(xué)習(xí)階段構(gòu)建線圖時(shí)，選擇合適的約束半徑r1=120，r2=50，僅將圓心處的隨機(jī)點(diǎn)與半徑為r1和半徑為r2的兩個(gè)圓形成的圓環(huán)內(nèi)的隨機(jī)點(diǎn)連接起來(lái)如圖1所示，然后通過障礙物檢測(cè)將無(wú)碰撞邊加入到E中，通過這種方式建立好路線圖后通過A*算法在路線圖中搜索到一條連接起點(diǎn)和目標(biāo)點(diǎn)的無(wú)碰撞路徑，使用道格拉斯普克算法對(duì)無(wú)碰撞路徑進(jìn)行峰值節(jié)點(diǎn)提取操作，形成一條更優(yōu)路徑，易于滿足機(jī)器人行駛需求。

改進(jìn)后的PRM算法的優(yōu)點(diǎn)：①在學(xué)習(xí)階段使用約束圓環(huán)，會(huì)大幅度的簡(jiǎn)化查詢階段搜索集合E中邊的數(shù)量，構(gòu)造的路線圖R較傳統(tǒng)方法構(gòu)建簡(jiǎn)單，一定程度上降低后續(xù)查詢階段搜索算法搜索到路徑所用時(shí)間；②增加了查詢階段判斷搜索是否會(huì)成功，決定PRM搜索是否成功在于起點(diǎn)和目標(biāo)點(diǎn)能否在一個(gè)路線圖中。增加這個(gè)判斷是為了減少規(guī)劃失敗時(shí)浪費(fèi)在查詢階段的時(shí)間；③使用道格拉斯-普克算法對(duì)PRM算法查詢階段得到的無(wú)碰撞路徑進(jìn)行峰值節(jié)點(diǎn)提取，有效去除冗余節(jié)點(diǎn)。

改進(jìn)后的PRM算法流程如圖3所示。

圖3 改進(jìn)后的PRM算法流程

改進(jìn)后的PRM算法的偽代碼：

Input:

n:the number of nodes to put in the roadmap

r1,r2: the radius of two circles

Output:

a roadmap R=(N,E)

(1)N←?,E←?

(2)while |N| < n do

(3)loop

(4)c← a randomly chosen free configuration

(5)if c is collision then

(6)b = RandomNode (c,r)

V←V ∪ { b }

(7)else V← V ∪ { c }

(8)end if

(9)end while

(10)for all c ∈ V do

(11)Nc← a set of candidate neighbors of c chosen

from N

for all v ∈ Nc， in order of increasing D (c,v ) do

(c,v) then

(13) if D(c,n)r2, E←E∪{(c,v) } %%設(shè)置約束

(14) update Rs connected components %%更新

(15) end if

(16) end for

(17)end for

(18)R = (N,E)

(19)path=AStaP(E) %%搜索路徑

(20) path=ARrecurisionF(pointsTab,path,Thres-hold) %%設(shè)定閾值，加入起點(diǎn)，目標(biāo)點(diǎn)后進(jìn)行峰值節(jié)點(diǎn)提取

(21)return path

3 仿真驗(yàn)證

仿真實(shí)驗(yàn)在電腦處理器為Intel(R) Core(TM) i5-5200U，安裝內(nèi)存為8 GB，64位操作系統(tǒng)Windows 8.1上的matlab2016b中進(jìn)行。通過對(duì)比了傳統(tǒng)的PRM算法和改進(jìn)后的PRM算法在簡(jiǎn)單地圖與復(fù)雜地圖下的時(shí)間特性和對(duì)應(yīng)的路徑節(jié)點(diǎn)個(gè)數(shù)來(lái)驗(yàn)證改進(jìn)方法的可行性和有效性。

在500*500的障礙物地圖中，設(shè)定機(jī)器人起點(diǎn)為(10,10)，目標(biāo)點(diǎn)為(490,490)，黑色橢圓圖形代表障礙物，線條代表可行性邊，白色空間代表自由空間Cfree，原點(diǎn)(0,0)在圖像左上角，豎直向下為x軸正方向，水平向右為y軸正方向。隨機(jī)選取100個(gè)隨機(jī)點(diǎn)構(gòu)成點(diǎn)集N，加入起點(diǎn)和終點(diǎn)，并將其與路線圖在約束條件下連接起來(lái)，圖4(a)中約束半徑為210，圖4(b)中采用邊集優(yōu)化方法設(shè)定約束外徑為r1=210，約束內(nèi)經(jīng)r2=140。

圖4 簡(jiǎn)單地圖中傳統(tǒng)PRM算法和 改進(jìn)PRM算法路線對(duì)比

當(dāng)隨機(jī)點(diǎn)為100個(gè)或200個(gè)時(shí)，設(shè)定簡(jiǎn)單地圖中約束內(nèi)徑為140，約束外徑為210，復(fù)雜地圖圖中約束內(nèi)經(jīng)為80，約束外徑為120。由圖4可知，在障礙物已知環(huán)境中，使用邊集約束方法對(duì)隨機(jī)點(diǎn)的邊集施加約束，較傳統(tǒng)PRM算法得到的路線圖，改進(jìn)后的PRM算法得到的路線圖更加簡(jiǎn)單，使得PRM算法在查詢階段用時(shí)更少。實(shí)驗(yàn)數(shù)據(jù)見表1，傳統(tǒng)PRM算法和改進(jìn)后的PRM算法在不同隨機(jī)點(diǎn)數(shù)情況下在簡(jiǎn)單地圖和復(fù)雜地圖上的運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果表明，當(dāng)隨機(jī)點(diǎn)個(gè)數(shù)為100時(shí)，在簡(jiǎn)單地圖和復(fù)雜地圖中，改進(jìn)后的PRM算法運(yùn)行時(shí)間較傳統(tǒng)PRM算法分別減少約10.64%、6.75%。當(dāng)隨機(jī)點(diǎn)個(gè)數(shù)為200時(shí)，在簡(jiǎn)單地圖和復(fù)雜地圖中，改進(jìn)后的PRM算法運(yùn)行時(shí)間較傳統(tǒng)PRM算法分別減少約9.68%、7.17%。改進(jìn)后的PRM算法能在已知障礙物的環(huán)境中更加快速規(guī)劃出一條無(wú)碰撞路徑，減少規(guī)劃所用時(shí)間，對(duì)機(jī)器人的實(shí)時(shí)性有所提高。

為驗(yàn)證相同約束外徑，不同約束內(nèi)經(jīng)時(shí)，改進(jìn)PRM算法的時(shí)間特性。首先，設(shè)定相同的約束外徑r1=150，同時(shí)設(shè)定約束內(nèi)經(jīng)r2從20至120逐漸變化，使用該邊集約束方法對(duì)PRM算法進(jìn)行改進(jìn)后運(yùn)行在簡(jiǎn)單地圖上的運(yùn)行時(shí)間數(shù)據(jù)見表2，運(yùn)行時(shí)間數(shù)據(jù)是通過運(yùn)行5次程序取中位數(shù)的方法得到的，從表2中數(shù)據(jù)可以看出，隨著約束內(nèi)徑的不斷增大，算法的運(yùn)行時(shí)間在不斷減少。這說(shuō)明邊集約束方法是切實(shí)可行的，對(duì)減少算法的運(yùn)行時(shí)間是有效的。改進(jìn)后 的PRM算法較傳統(tǒng)的PRM算法運(yùn)行時(shí)間大大降低，在保證一定路徑搜索成功率的情況下，選擇合適內(nèi)外約束半徑，表1中改進(jìn)算法的時(shí)間特性還可以繼續(xù)提升。

表1 成功規(guī)劃到路徑時(shí)間對(duì)比

表2 簡(jiǎn)單地圖相同約束外徑，不同約束內(nèi)徑運(yùn)行時(shí)間對(duì)比(隨機(jī)點(diǎn)為100個(gè))

選取同一組隨機(jī)點(diǎn)，且隨機(jī)點(diǎn)數(shù)目為100個(gè)的簡(jiǎn)單地圖上，圖5(a)表示在傳統(tǒng)的PRM學(xué)習(xí)階段構(gòu)建的路線搜索出來(lái)的無(wú)碰撞路徑，圖5(b)表示使用邊集優(yōu)化方法對(duì)PRM學(xué)習(xí)階段構(gòu)建的路線進(jìn)行簡(jiǎn)化后，使用峰值節(jié)點(diǎn)提取對(duì)路徑進(jìn)行再優(yōu)化后查詢出一條無(wú)碰撞路徑如圖5(b)所示。從簡(jiǎn)單地圖 中可以看出，采用傳統(tǒng)方法查詢出的路徑中，有的節(jié)點(diǎn)之間在較短距離內(nèi)發(fā)生多次轉(zhuǎn)折，如果機(jī)器人沿著該路徑進(jìn)行前進(jìn)會(huì)發(fā)生頻繁轉(zhuǎn)向，不利于機(jī)器人的控制，采用改進(jìn)方法的PRM算法查詢出的路徑中節(jié)點(diǎn)數(shù)目較少，機(jī)器人行駛時(shí)轉(zhuǎn)向次數(shù)較少，更利于機(jī)器人的控制及能量節(jié)省。

圖5 簡(jiǎn)單地圖傳統(tǒng)PRM算法和改進(jìn)PRM算法路徑對(duì)比

選取同一組隨機(jī)點(diǎn)，且隨機(jī)點(diǎn)數(shù)目為100個(gè)的復(fù)雜地圖上，圖6(a)表示在傳統(tǒng)的PRM學(xué)習(xí)階段構(gòu)建的路線搜索出來(lái)的無(wú)碰撞路徑，圖6(b)表示使用邊集優(yōu)化方法對(duì)PRM學(xué)習(xí)階段構(gòu)建的路線進(jìn)行簡(jiǎn)化后，先查詢出一條無(wú)碰撞路徑，再使用峰值節(jié)點(diǎn)提取對(duì)路徑進(jìn)行再優(yōu)化。從復(fù)雜圖中可以看出，搜索到的無(wú)碰撞路徑，改進(jìn)方法較傳統(tǒng)方法發(fā)生轉(zhuǎn)折次數(shù)更少，且節(jié)點(diǎn)間在較短距離內(nèi)不會(huì)發(fā)生轉(zhuǎn)折，路線更加平滑，充分驗(yàn)證了峰值節(jié)點(diǎn)提取的必要性和有效性。

圖6 復(fù)雜地圖傳統(tǒng)PRM算法和改進(jìn)PRM算法路徑對(duì)比

通過將邊集約束方法應(yīng)用到傳統(tǒng)PRM算法成功查詢出一條無(wú)碰撞路徑后，設(shè)置合適的閾值φ，將生成的路徑進(jìn)行峰值節(jié)點(diǎn)提取，經(jīng)過在簡(jiǎn)單地圖和復(fù)雜地圖仿真實(shí)驗(yàn)后，通過圖5(a)、圖5(b)、圖6(a)、圖6(b)得到的可行路徑數(shù)據(jù)可以得出表3數(shù)據(jù)。在簡(jiǎn)單地圖中，傳統(tǒng)PRM算法初始路徑的節(jié)點(diǎn)個(gè)數(shù)為7個(gè)，設(shè)置閾值為38后，改進(jìn)PRM算法初始路徑節(jié)點(diǎn)個(gè)數(shù)為4個(gè)，優(yōu)化節(jié)點(diǎn)個(gè)數(shù)為3個(gè)。在復(fù)雜地圖中，傳統(tǒng)PRM算法初始路徑的節(jié)點(diǎn)個(gè)數(shù)為17個(gè)，設(shè)置閾值為25后，改進(jìn)PRM算法初始路徑節(jié)點(diǎn)個(gè)數(shù)為10個(gè)，優(yōu)化節(jié)點(diǎn)個(gè)數(shù)為7個(gè)。無(wú)論是簡(jiǎn)單地圖還是復(fù)雜地圖，較傳統(tǒng)PRM算法查詢出的無(wú)碰撞路徑中節(jié)點(diǎn)數(shù)目，改進(jìn)PRM算法后得出的路徑節(jié)點(diǎn)更少，路徑更加平滑，更利于機(jī)器人的行走。

表3 改進(jìn)PRM初始路徑與優(yōu)化路徑實(shí)驗(yàn)數(shù)據(jù)對(duì)比

4 結(jié)束語(yǔ)

針對(duì)于傳統(tǒng)PRM算法查詢路徑所需時(shí)間較長(zhǎng)及生成的初始路徑中節(jié)點(diǎn)較多等問題，本文通過對(duì)點(diǎn)集N中的隨機(jī)點(diǎn)采用內(nèi)外徑約束的邊集優(yōu)化方法，以減少生成的邊集E的大小，從而減少查詢階段的計(jì)算量，最終將峰值節(jié)點(diǎn)提取方法應(yīng)用于路徑的再優(yōu)化中，可以有效減少路徑中的節(jié)點(diǎn)數(shù)目。仿真結(jié)果表明，相比于傳統(tǒng)PRM算法，改進(jìn)后的PRM算法具有計(jì)算量小，實(shí)時(shí)性好，路徑中節(jié)點(diǎn)數(shù)目少等優(yōu)點(diǎn)，對(duì)機(jī)器人使用PRM進(jìn)行路徑規(guī)劃的后續(xù)開發(fā)有一定參考意義。