引言

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

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

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

1算法描述

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

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

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

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

圖1訓(xùn)練集和測(cè)試集的實(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ù)會(huì)影響預(yù)測(cè)的精度，所以需要經(jīng)過對(duì)比實(shí)驗(yàn)，選出滿足平方相關(guān)系數(shù)R最大，并同時(shí)保證以上幾種誤差最小的支持向量回歸模型。由表1可以看出，當(dāng)支持向量回歸模型選取高斯核函數(shù)時(shí)預(yù)測(cè)值與真實(shí)值的誤差最小。為驗(yàn)證本文算法的優(yōu)勢(shì)，可以將本文算法測(cè)試后的到的結(jié)果，分別與BP神經(jīng)網(wǎng)絡(luò)，自回歸兩種常用的預(yù)測(cè)算法進(jìn)行比較。

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

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

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

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

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

2.3時(shí)效性對(duì)比試驗(yàn)

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

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

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

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ī)器人在動(dòng)態(tài)環(huán)境下的路徑規(guī)劃問題。將動(dòng)態(tài)障礙物的位置信息，作為支持向量回歸模型的輸入。然后采用支持向量回歸機(jī)模對(duì)下一時(shí)刻動(dòng)態(tài)障礙物的位置信息進(jìn)行預(yù)測(cè)。此時(shí)動(dòng)態(tài)障礙物可以看做成瞬間靜止的，把問題轉(zhuǎn)化為瞬時(shí)靜態(tài)的路徑規(guī)劃。為尋找該時(shí)刻的最優(yōu)路徑，可以采用PRM算法進(jìn)行路徑規(guī)劃，并且實(shí)時(shí)更新路徑，最終實(shí)現(xiàn)從起點(diǎn)到終點(diǎn)的最優(yōu)路徑或近似最優(yōu)路徑。為了證明本文算法的優(yōu)越性，分別與蟻群算法和動(dòng)態(tài)柵格法進(jìn)行對(duì)比，仿真實(shí)驗(yàn)結(jié)果如下。

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

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

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

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

4總結(jié)

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