引言

隨著機(jī)器人技術(shù)逐漸成熟，機(jī)器人作業(yè)環(huán)境的復(fù)雜化，移動機(jī)器人在真實(shí)的環(huán)境中運(yùn)動并完成指定的任務(wù)，機(jī)器人的路徑規(guī)劃是首先要解決的問題。所謂的最優(yōu)路徑就是依據(jù)某些或某個準(zhǔn)則（如行走路線最短、行走時間最短、工作代價最小等），在機(jī)器人的工作空間中找到一條從起點(diǎn)到終點(diǎn)的最優(yōu)或接近最優(yōu)的路徑。

近年來，解決移動機(jī)器人在動態(tài)未知環(huán)境下的路徑規(guī)劃問題一直困擾著人們。對此，國內(nèi)外許多學(xué)者提出了有效的規(guī)劃算法：如人工勢場法，蟻群算法,隨機(jī)路標(biāo)圖法（PRM）,遺傳算法等。Tang等提出將動態(tài)障礙物在一段時間內(nèi)看成是靜態(tài)的，此時路徑規(guī)劃問題就可以用柵格法解決，此法稱之為動態(tài)柵格法。郭玉把蟻群算法應(yīng)用在復(fù)雜靜態(tài)環(huán)境中，解決了路徑規(guī)劃中的避碰問題，并且提高了路徑搜索的效率?；眲?chuàng)鋒等針對預(yù)測動態(tài)障礙物軌跡的問題提出采用自回歸模型，經(jīng)實(shí)驗(yàn)證明該模型具有良好的避障能力。

本文采用支持向量回歸機(jī)模型(SVR)預(yù)測動態(tài)障礙物軌跡，該模型具有更好的準(zhǔn)確性和時效性。人工勢場法在實(shí)現(xiàn)過程中會有計(jì)算復(fù)雜度大和運(yùn)行速度慢的現(xiàn)象，當(dāng)處于復(fù)雜的動態(tài)未知環(huán)境下時，人工勢場法難以達(dá)到實(shí)時性的要求。本文采用SVR算法與PRM算法結(jié)合的方法對機(jī)器人進(jìn)行路徑規(guī)劃時，不需要對工作空間中的障礙物進(jìn)行精準(zhǔn)地數(shù)學(xué)建模，通過仿真實(shí)驗(yàn)證明本文算法具有較好的運(yùn)行精度和實(shí)時性，并且能夠有效地解決動態(tài)工作空間中的路徑規(guī)劃問題。

1算法描述

1.1支持向量回歸機(jī)

對于動態(tài)障礙物的軌跡趨近于線性的情況下，考慮采用線性回歸函數(shù)：

表1四種核函數(shù)預(yù)測誤差比較

訓(xùn)練集和測試集的實(shí)驗(yàn)流程圖如圖1所示。

圖1訓(xùn)練集和測試集的實(shí)驗(yàn)流程圖

2.3驗(yàn)證SVR

筆者在Inter(R)Core(TM)Duo-E7500的CPU,內(nèi)存16G的Linux操作系統(tǒng)下進(jìn)行實(shí)驗(yàn)。由于選取不同的核函數(shù)會影響預(yù)測的精度，所以需要經(jīng)過對比實(shí)驗(yàn)，選出滿足平方相關(guān)系數(shù)R最大，并同時保證以上幾種誤差最小的支持向量回歸模型。由表1可以看出，當(dāng)支持向量回歸模型選取高斯核函數(shù)時預(yù)測值與真實(shí)值的誤差最小。為驗(yàn)證本文算法的優(yōu)勢，可以將本文算法測試后的到的結(jié)果，分別與BP神經(jīng)網(wǎng)絡(luò)，自回歸兩種常用的預(yù)測算法進(jìn)行比較。

在預(yù)測動態(tài)障礙物軌跡的實(shí)驗(yàn)中，選同一組數(shù)據(jù)對以上三種算法進(jìn)行測試，預(yù)測值與真實(shí)值的相對誤差對比結(jié)果如圖2所示。

圖2相對誤差比較實(shí)驗(yàn)結(jié)果

由圖2可知，SVR算法的預(yù)測誤差較小，BP神經(jīng)網(wǎng)絡(luò)的預(yù)測效果不好，可能的原因是神經(jīng)網(wǎng)絡(luò)算法得到的最優(yōu)解不一定是全局最優(yōu)解，有可能只是局部最優(yōu)解。采用自回歸算法的實(shí)驗(yàn)結(jié)果還不錯，但是沒有SVR算法的準(zhǔn)確度好。

圖3時效性比較實(shí)驗(yàn)結(jié)果

時效性對比結(jié)果如圖3所示,SVR算法在時效性具有一定的優(yōu)勢，即在一定的時間之內(nèi)應(yīng)用SVR算法能更加快速地對動態(tài)障礙的軌跡進(jìn)行預(yù)測。

2.3時效性對比試驗(yàn)

通過仿真實(shí)驗(yàn)可以證明SVR算法在預(yù)測動態(tài)障礙物軌跡方面具有一定的優(yōu)越性，然后對融合SVR的PRM算法與其他算法在路徑規(guī)劃方面進(jìn)行對比實(shí)驗(yàn)。在動態(tài)已知環(huán)境下，給定初始位置和目標(biāo)位置，分別用本文算法、蟻群算法、動態(tài)柵格法對機(jī)器人進(jìn)行路徑規(guī)劃，對比三種算法的時效性。選取10組不同的初始位置和目標(biāo)位置，分別對以上算法進(jìn)行實(shí)驗(yàn)對比，對比結(jié)果如圖4所示。由圖4可知，本文采用的SVR算法與PRM算法結(jié)合的方法與蟻群算法和動態(tài)柵格法比較，本文算法進(jìn)行路徑規(guī)劃所用時間最短，具有更好的時效性，并且規(guī)劃的路徑最短。

圖4時效性實(shí)驗(yàn)比較結(jié)果

通過實(shí)驗(yàn)證明柵格越小，環(huán)境信息儲存量就越小，規(guī)劃時間越長，越趨于最優(yōu)路徑，所以時效性和最優(yōu)路徑不能兼顧。蟻群算法雖然具有較好的魯棒性，但是容易陷入局部最優(yōu)和規(guī)劃時間較長的缺點(diǎn)。在給定相同的初始位置和目標(biāo)位置的情況下，采用本文算法所用的時間最短。

3路徑規(guī)劃

本實(shí)驗(yàn)在Inter(R)Core(TM)Duo-E7500的CPU,內(nèi)存16G的Linux操作系統(tǒng)下進(jìn)行的。通過把SVR算法和PRM算法進(jìn)行有機(jī)地結(jié)合，有效地解決了機(jī)器人在動態(tài)環(huán)境下的路徑規(guī)劃問題。將動態(tài)障礙物的位置信息，作為支持向量回歸模型的輸入。然后采用支持向量回歸機(jī)模對下一時刻動態(tài)障礙物的位置信息進(jìn)行預(yù)測。此時動態(tài)障礙物可以看做成瞬間靜止的，把問題轉(zhuǎn)化為瞬時靜態(tài)的路徑規(guī)劃。為尋找該時刻的最優(yōu)路徑，可以采用PRM算法進(jìn)行路徑規(guī)劃，并且實(shí)時更新路徑，最終實(shí)現(xiàn)從起點(diǎn)到終點(diǎn)的最優(yōu)路徑或近似最優(yōu)路徑。為了證明本文算法的優(yōu)越性，分別與蟻群算法和動態(tài)柵格法進(jìn)行對比，仿真實(shí)驗(yàn)結(jié)果如下。

圖5蟻群算法在靜態(tài)環(huán)境和動態(tài)環(huán)境下的路徑規(guī)劃

圖6動態(tài)柵格法在靜態(tài)環(huán)境和動態(tài)環(huán)境下的路徑規(guī)劃

圖7本文算法在靜態(tài)環(huán)境和動態(tài)下的路徑規(guī)劃

實(shí)驗(yàn)在長為17米，寬為15米的仿真環(huán)境下進(jìn)行，如圖5、6、7所示，機(jī)器人分別在靜態(tài)和動態(tài)環(huán)境下采用三種算法進(jìn)行路徑規(guī)劃的實(shí)驗(yàn)結(jié)果，三種算法在靜態(tài)時規(guī)劃的路徑長度分別為16.03m、15.14m、14.73m，動態(tài)時路徑長度分別為16.85m、16.64m、15.4m。從結(jié)果可以看出本文算法規(guī)劃出的路徑最短，時效性更好，不但避免了蟻群算法容易陷入局部最優(yōu)的缺點(diǎn)，也避免了動態(tài)柵格法的環(huán)境信息儲存量與規(guī)劃時間難以兼顧的缺點(diǎn)，更趨近于最優(yōu)路徑。

4總結(jié)

本文對動態(tài)未知環(huán)境下移動機(jī)器人的路徑規(guī)劃問題進(jìn)行深入研究分析，并且通過大量的仿真實(shí)驗(yàn)驗(yàn)證本文算法的可行性與時效性。利用支持向量回歸機(jī)算法對動態(tài)障礙物的行走軌跡進(jìn)行預(yù)測，把動態(tài)路徑規(guī)劃問題轉(zhuǎn)化為靜態(tài)路徑規(guī)劃問題。然后利用PRM算法對機(jī)器人進(jìn)行瞬時靜態(tài)的路徑規(guī)劃。兩種算法通過有機(jī)地結(jié)合，為移動機(jī)器人在動態(tài)環(huán)境中找到一條最優(yōu)或接近最優(yōu)的無障礙路徑。