基于SVM的受約束D*算法在無人車尋路中的應(yīng)用?

劉曉濤 蔡云飛 王田橙

基于SVM的受約束D*算法在無人車尋路中的應(yīng)用?

劉曉濤 蔡云飛 王田橙

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

針對在未知環(huán)境無人車受約束控制條件下的動態(tài)路徑平滑規(guī)劃問題，提出了一種基于支持向量機(jī)（SVM）的D*改進(jìn)算法。該算法通過柵格法對環(huán)境建模，建立車輛受約束動態(tài)方程，在動態(tài)規(guī)劃路徑選取之后使用SVM算法對無人車轉(zhuǎn)向位置處進(jìn)行局部路徑平滑優(yōu)化。實(shí)現(xiàn)無人車在真實(shí)環(huán)境中流暢穩(wěn)定的運(yùn)動。實(shí)驗(yàn)結(jié)果表明：該算法能夠在未知環(huán)境中規(guī)劃出平滑的動態(tài)路徑，具有較好的可靠性和穩(wěn)定性。

無人車；受約束D*算法；SVM；線性核；動態(tài)路徑平滑規(guī)劃

AbstractFor the problem of the dynamic path planning and path smoothing of automated vehicle in unknown environment with constraints，an improved algorithm of D*based on support vector machine（SVM）is presented.In this algorithm the environ?mental modeling is based on the grid method and then establish the constrained dynamic equation of the vehicle.After the dynamic planning path is selected，the SVM algorithm is used to smooth optimization the local path of automated vehicle at the steering posi?tion.By this algorithm automated vehicle can smooth and stable movement in real environment.Experimental results show that this algorithm can dynamically plan a smooth path in unknown environment，which has sufficient reliability and stability.

Key Wordsautomated vehicle，constrained D*algorithm，SVM，linear kernel，dynamic path planning and path smoothing

Class NumberTP391

1 引言

無人車涉及認(rèn)知科學(xué)、人工智能、機(jī)器人技術(shù)與車輛工程等交叉學(xué)科，是各種新興技術(shù)的綜合試驗(yàn)床與理想載體，也是當(dāng)今前沿科技的重要發(fā)展方向。無人駕駛技術(shù)是傳感器、計(jì)算機(jī)、人工智能、通信、導(dǎo)航定位、模式識別、智能控制等多門學(xué)科的綜合體，無人駕駛汽車的關(guān)鍵技術(shù)包括環(huán)境感知、導(dǎo)航定位、路徑規(guī)劃、決策控制等。環(huán)境感知模塊相當(dāng)于無人駕駛汽車的眼和耳，無人駕駛汽車通過環(huán)境感知模塊識別自己所處的環(huán)境，感知自身位置以及分析處理傳感器傳回的環(huán)境信息。導(dǎo)航定位模塊用于確認(rèn)無人駕駛車所處的地理位置，是路徑規(guī)劃的前提和保障。路徑規(guī)劃模塊是實(shí)現(xiàn)無人駕駛的基礎(chǔ)。路徑規(guī)劃問題指機(jī)器人按照某些性能指標(biāo)搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或者近似最優(yōu)的無碰撞路徑。決策控制模塊用于無人駕駛車下一步的行為決策，用于控制無人車的運(yùn)動［1］。

路徑規(guī)劃是支撐無人車系統(tǒng)自主駕駛的基礎(chǔ)，是無人車研究中的一個(gè)基本和關(guān)鍵的問題。無人駕駛車的自主駕駛需要路徑規(guī)劃模塊給出合理的路線。在自主駕駛系統(tǒng)中，通過傳感器的感知，發(fā)現(xiàn)路線中的障礙后，需要路徑規(guī)劃模塊合理的處理，規(guī)避障礙物。在自主駕駛系統(tǒng)中，無人車完全自主行駛，路徑規(guī)劃模塊需要給無人車提供確定的行駛方向等信息?？傊窂揭?guī)劃技術(shù)是無人車發(fā)展中一個(gè)至關(guān)重要的部分，成熟的路徑規(guī)劃技術(shù)，可以提高無人車行駛的效率、安全性和穩(wěn)定性。

本文主要的研究思路是基于支持向量機(jī)與受車輛模型約束的D*改進(jìn)算法。受約束車輛模型對車輛控制軌跡的影響主要包括速度影響和方向影響。受約束車輛模型的研究對整個(gè)規(guī)劃過程具有非常重要的意義。

2 相關(guān)研究工作

對于路徑規(guī)劃問題，國內(nèi)外學(xué)者已經(jīng)探索出很多有效的方法，路徑規(guī)劃可以分為全局路徑規(guī)劃和局部路徑規(guī)劃。全局路徑規(guī)劃主要有可視圖法和柵格法等，局部路徑規(guī)劃主要有遺傳算法和人工勢場等［2～3］。

可視圖法［4］是20世紀(jì)70年代末期提出，其最大的特點(diǎn)是將障礙物描述為多邊形或者多面體。該方法把對象視為一個(gè)點(diǎn)，將對象、目標(biāo)點(diǎn)和障礙物多邊形各個(gè)頂點(diǎn)進(jìn)行組合連接，必須保證所有的組合連線不能穿過障礙物。此方法簡單可行，但是在多維空間環(huán)境下，算法變的特別復(fù)雜。柵格法［5，7］是20世紀(jì)80年代提出，該方法的思想是將環(huán)境分解成一系列簡單的網(wǎng)格。柵格法多采用基于位置碼的四叉樹建模方法，搜索策略有靜態(tài)的A*算法和動態(tài)的D*算法以及它們的一些改進(jìn)算法。柵格法具有容易創(chuàng)建、維護(hù)和理解的優(yōu)點(diǎn)，能夠存儲和維護(hù)的數(shù)據(jù)量大。人工勢場法［6］是20世紀(jì)80年代提出的一種虛擬力法，其基本思想是將物體的運(yùn)動模擬為一種虛擬的人工力場中的運(yùn)動，目標(biāo)點(diǎn)對物體具有吸引力，障礙物點(diǎn)對物體具有排斥力。該方法具有一個(gè)明顯的缺點(diǎn)就是可能產(chǎn)生死鎖現(xiàn)象，吸引力和排斥力的平衡使得物體停留在環(huán)境中的某一點(diǎn)。遺傳算法是近年來提出的新的算法，將局部路徑規(guī)劃推向了智能化和仿生化的方向發(fā)展。該算法選取隨機(jī)的遺傳因子，多代遺傳后往往會有很好的結(jié)果，并且在發(fā)生死鎖時(shí)允許系統(tǒng)回退。但是由于遺傳因子的隨機(jī)性，該算法有很小的概率出現(xiàn)遺傳方向的偏離，產(chǎn)生特別差的規(guī)劃效果。

綜合路徑規(guī)劃現(xiàn)有的技術(shù)，很多研究者提出了多個(gè)算法融合的新算法，實(shí)踐結(jié)果表明，融合算法的效率往往比單一的某個(gè)算法要高，同時(shí)在實(shí)際復(fù)雜的環(huán)境應(yīng)用中也具有更高的魯棒性。

3 柵格地圖的構(gòu)建

3.1 柵格地圖的優(yōu)點(diǎn)

無人車的路徑規(guī)劃模塊僅需要識別出環(huán)境中的障礙物，采用激光雷達(dá)傳感器獲取環(huán)境中的距離信息，對環(huán)境的圖形化數(shù)據(jù)要求不高，只對地圖做障礙物標(biāo)記處理，選用柵格地圖完全滿足上述需求。柵格地圖數(shù)據(jù)結(jié)構(gòu)簡單，易于算法的實(shí)現(xiàn)，對二維空間數(shù)據(jù)的處理非常容易，易于與激光雷達(dá)數(shù)據(jù)的同步，對環(huán)境信息描述簡單，減少了信息量，易于模擬環(huán)境信息。柵格地圖還具有輸出方法快速簡潔，非常有利于算法數(shù)據(jù)的融合。因此選用柵格地圖來對局規(guī)劃的環(huán)境進(jìn)行建模。

3.2 柵格的構(gòu)建方法

本文使用了一系列節(jié)點(diǎn)來存儲柵格地圖中的節(jié)點(diǎn)。柵格地圖的每一個(gè)網(wǎng)格點(diǎn)都是一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)中存儲了有關(guān)的信息，柵格節(jié)點(diǎn)主要用于標(biāo)記環(huán)境中的狀態(tài)。對于算法的每個(gè)輸入也是以節(jié)點(diǎn)的形式傳遞信息。無人車所在的環(huán)境是由基本元素組成的矩形區(qū)域，每一個(gè)元素就是一個(gè)柵格。柵格的分辨率為a，即每個(gè)柵格的邊長為a。整個(gè)柵格的大小和分辨率均可以根據(jù)需要對區(qū)域進(jìn)行擴(kuò)大或者縮小。定義X和Y作為無人車在柵格中的坐標(biāo)，為柵格中的所有節(jié)點(diǎn)按順序進(jìn)行編號。柵格地圖中的節(jié)點(diǎn)可以簡單視為占據(jù)、空白和未知三種類型。根據(jù)改進(jìn)的D*算法的需要，為了找到最終的路徑，需要保存柵格中元素的父節(jié)點(diǎn)信息，定義存儲當(dāng)前元素的父節(jié)點(diǎn)信息。

算法需要對柵格地圖中的一系列節(jié)點(diǎn)進(jìn)行處理，本文定義算法節(jié)點(diǎn)來對柵格信息進(jìn)行處理，需要保證算法節(jié)點(diǎn)與柵格節(jié)點(diǎn)的同步性。算法節(jié)點(diǎn)的選取采用如圖1所示的方向。

圖1 鄰接節(jié)點(diǎn)

上下左右四個(gè)方向權(quán)值設(shè)置為1，四個(gè)對角線方向權(quán)值設(shè)置為1.4。這八個(gè)方向類似于八叉樹的八個(gè)子節(jié)點(diǎn)，除了柵格邊緣的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都存在與其相鄰的八個(gè)子節(jié)點(diǎn)。

4 受約束車輛模型

一個(gè)兩輪驅(qū)動的無人車的運(yùn)動方程如下［8～9］：

其中，x?，y?分別表示在X軸和Y軸上前進(jìn)的距離，r表示輪子的半徑，η表示車輛模型底盤寬度的一半，?表示前進(jìn)方向與X軸的夾角，VR，VL分別表示右輪的速度和左輪的速度。?的取值范圍為-＜?＜0和0＜?＜。

經(jīng)過一系列簡單的數(shù)學(xué)變換，式（1）可以變形為式（2）：

上述兩個(gè)式子分別表示右輪速度與無人車在X軸方向上前進(jìn)距離的關(guān)系和左輪速度與無人車在Y軸方向上前進(jìn)距離的關(guān)系。這樣變換使得實(shí)驗(yàn)用車在單個(gè)坐標(biāo)軸上的位移只與其中一個(gè)輪子的速度有關(guān)，這樣設(shè)計(jì)的好處就是方便計(jì)算實(shí)驗(yàn)用車的轉(zhuǎn)彎半徑、輪子轉(zhuǎn)動圈數(shù)等數(shù)據(jù)。

在實(shí)際的實(shí)驗(yàn)環(huán)境下，還需要考慮輪子打滑以及里程計(jì)本身的誤差造成的位移誤差，我們用ex，ey表示誤差項(xiàng)，因此，公式形式如下：實(shí)驗(yàn)用車和車體坐標(biāo)系示意如圖2和圖3所示。

圖2 實(shí)驗(yàn)用車

圖3 車體坐標(biāo)系

本實(shí)驗(yàn)采用圖2所示無人車，車底盤半徑約20cm，共有四個(gè)輪子，其中左右輪為主動輪，前后輪為從動輪，故圖3中描繪的車輪只畫出了左右主動輪，而省略掉了前后的從動輪。實(shí)驗(yàn)用車的傳感器是Hokuyo單線雷達(dá)，雷達(dá)安裝在車的前部距離地面15cm處。

5 D*算法

本文采用柵格法進(jìn)行環(huán)境建模，使用D*算法［10～11］的改進(jìn)算法進(jìn)行路徑的搜索。D*算法與A*算法［12］類似，區(qū)別在于A*算法是靜態(tài)的路徑規(guī)劃，而D*算法是動態(tài)的路徑規(guī)劃。在整個(gè)規(guī)劃過程中，D*算法允許路徑上障礙物位置隨意的變化。這一點(diǎn)在真實(shí)環(huán)境下是非常關(guān)鍵的。算法需要維護(hù)一個(gè)OPEN表，OPEN表用于傳遞節(jié)點(diǎn)之間權(quán)值發(fā)生變化后的信息以及計(jì)算路徑長度。每一個(gè)節(jié)點(diǎn)都有一個(gè)tag作為標(biāo)識位，有NEW、OPEN、CLOSED三個(gè)狀態(tài)。如果一個(gè)節(jié)點(diǎn)從來沒有出現(xiàn)在OPEN表中，則tag=NEW；如果一個(gè)節(jié)點(diǎn)當(dāng)前處于OPEN表中，則tag=OPEN；如果一個(gè)節(jié)點(diǎn)從OPEN表中移除，則tag=CLOSED。

本章主要介紹D*算法的定義、描述以及受約束車輛模型對D*算法的影響。

5.1 D*算法的簡介

D*算法的目的是移動機(jī)器人從起始點(diǎn)S按照規(guī)劃的路徑，規(guī)避障礙，到達(dá)目標(biāo)點(diǎn)G，衡量路徑優(yōu)劣的標(biāo)準(zhǔn)是機(jī)器人移動過程中的消耗，即成本問題，用 f(S，G)表示。這一問題可以簡單的描述為選取一系列有效節(jié)點(diǎn){X1，…，Xn}，使得機(jī)器人按照一定的順序在節(jié)點(diǎn)之間移動，直到到達(dá)目標(biāo)點(diǎn)。節(jié)點(diǎn)之間連接的弧具有正的權(quán)值，這些有效點(diǎn)之間弧的權(quán)值之和就是機(jī)器人的成本。每個(gè)節(jié)點(diǎn)Xi（其中1≤i≤n）都有一個(gè)后繼節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)就是后繼節(jié)點(diǎn)的父節(jié)點(diǎn)，路徑就是通過當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)連接而形成的。節(jié)點(diǎn)X與其后繼節(jié)點(diǎn)之間的消耗定義為C(X，Y)，C(X，Y)是判斷路徑成本是否增加的一個(gè)重要參數(shù)。X和Y在空間上是鄰接的，即節(jié)點(diǎn)Y是以節(jié)點(diǎn)X為中心的八個(gè)方向上節(jié)點(diǎn)中的一個(gè)。

定義 g(S，Xi)表示起始點(diǎn)S到當(dāng)前節(jié)點(diǎn) Xi之間的成本。定義h(Xi，G)表示當(dāng)前節(jié)點(diǎn) Xi到目標(biāo)點(diǎn)G之間的成本。因此，總的成本表示為

D*算法主要包含兩部分內(nèi)容：第一部分用于計(jì)算到目標(biāo)點(diǎn)最優(yōu)路徑的成本；第二部分用于改變兩個(gè)節(jié)點(diǎn)之間弧的權(quán)值和獲得OPEN表中成本發(fā)生變化的節(jié)點(diǎn)。算法初始化時(shí)，將所有的節(jié)點(diǎn)狀態(tài)設(shè)置為NEW，即tag=NEW。將所有節(jié)點(diǎn)的h(Xi，G)設(shè)置為0，并將目標(biāo)點(diǎn)G放入OPEN表中，即tag=OPEN。

算法的偽代碼流程如下：

開始：

1 Insert（Goal Point）；

2 While（return of p（x）＞-1）

3 Return of p（x）=p（x）；

4 end

p（x）：

1 Neighbor（x）；//X節(jié)點(diǎn)的鄰接節(jié)點(diǎn)

2 Cost（x，neighbor of x）；//鄰接節(jié)點(diǎn)花費(fèi)

3 Insert（neighbor of x）；

動態(tài)障礙：

1 If（x==障礙）

2 Modify（）；//修改花費(fèi)

3 While（return of p（x）＞-1）

4 return of p（x）=p（x）；

5 end

6 end

5.2 受約束車輛模型對D*算法的影響

在實(shí)際應(yīng)用中，D*算法給出的路徑并不能作為無人車運(yùn)動的軌跡。無人車的運(yùn)動軌跡受車輛模型的影響比較大，還需要考慮車輛模型對D*算法的影響。

本實(shí)驗(yàn)用車可以實(shí)現(xiàn)原地180°轉(zhuǎn)身，所以在受約束的D*算法中遇到死鎖情況，需要調(diào)整實(shí)驗(yàn)用車的速度參數(shù)，使其原地掉頭回退一步，實(shí)驗(yàn)用車的這一特性解決了車輛模型對死鎖問題的約束。針對死鎖問題的算法解決方案是出現(xiàn)死鎖位置后回溯到之前不存在死鎖問題的節(jié)點(diǎn)上。在回退之后，重新計(jì)算當(dāng)前位置到目的地的最短路徑，同時(shí)在遇到路徑消耗相同的兩條路時(shí)，采用了路徑優(yōu)先級，優(yōu)先選擇最快尋找的路徑，這樣的設(shè)計(jì)很好地避免了死鎖問題。

本實(shí)驗(yàn)用車的雷達(dá)傳感器掃描角度范圍為前方0°～180°，受雷達(dá)傳感器的約束，除開死鎖問題，其他環(huán)境下應(yīng)避免向后方的轉(zhuǎn)向。因此，受車輛模型和雷達(dá)傳感器的雙重約束下，采用盡量小的轉(zhuǎn)彎角度來確保車輛的安全和效率。未改進(jìn)的D*算法轉(zhuǎn)彎角度為α=45°，約束后的轉(zhuǎn)彎角度調(diào)整為β1=18.5°和β2=26.5°兩次小角度轉(zhuǎn)彎。如下圖所示：

圖4 轉(zhuǎn)彎角度

6 受約束模型下的SVM改進(jìn)

上述D*算法可以得出全局最優(yōu)路徑，但是實(shí)際情況中，在局部路徑規(guī)劃中可能需要對全局的路徑進(jìn)行一定的平滑處理，這樣做的目的是使得機(jī)器人前進(jìn)的路徑更為有效?？紤]到機(jī)器人的運(yùn)動特性，需要根據(jù)機(jī)器人的轉(zhuǎn)彎半徑和模型等問題，使路徑較為平滑。本文采用基于SVM的平滑技術(shù)，使得機(jī)器人的運(yùn)動更加的流暢，降低消耗。

6.1 支持向量機(jī)（SVM）

支持向量機(jī)（SVM）是機(jī)器學(xué)習(xí)中的一種分類算法，是一種將樣本劃分為兩類的分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，即支持向量機(jī)的學(xué)習(xí)策略便是間隔最大化，最終可轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問題的求解［13］。

假 設(shè) 訓(xùn) 練 樣 本 集 合 D={(x1，y1)，(x2，y2)，…，，用于劃分兩類樣本的超平面用如下線性方程描述：

其中 w=(w1，w2，…，wd)為法向量，決定超平面的方向；b為位移項(xiàng)，決定了超平面與原點(diǎn)之間的距離。

6.2 基于核函數(shù)的SVM

SVM是一個(gè)兩類樣本的分類器，與路徑規(guī)劃中障礙物點(diǎn)和非障礙物點(diǎn)剛好吻合。SVM中的yi∈{ -1，+1 }，對于障礙物點(diǎn)，取 yi=-1，表示不可通行；對于非障礙物點(diǎn)，取 yi=+1，表示可以通行。以下為不同的核函數(shù)確定的障礙物與非障礙物之間的分割平面效果圖對比：

以上三個(gè)實(shí)驗(yàn)采用相同的數(shù)據(jù)，實(shí)驗(yàn)結(jié)果均為障礙物與非障礙物之間確定出的分割平面。在本次試驗(yàn)中，樣本可以視為是在二維的平面上的運(yùn)動。在局部優(yōu)化的過程中，我們認(rèn)為總是存在一個(gè)分割平面可以將障礙物與非障礙物進(jìn)行分類。SVM在無人車的運(yùn)動環(huán)境下可以描述為，尋找局部路徑中障礙物與非障礙物之間的分類平面。為了局部優(yōu)化D*算法的路徑，我們引入了線性核函數(shù)：

圖5 線性核SVM

圖6 Sigmoid核SVM

圖7 高斯核SVM

基于線性核的SVM的原理是在保證實(shí)驗(yàn)用車在障礙物之間可通行的最大寬度內(nèi)，通過SVM的線性劃分，增大實(shí)驗(yàn)用車的轉(zhuǎn)彎角度，且同時(shí)可以縮短無人車的行進(jìn)距離［14～18］。

實(shí)驗(yàn)用車車體直徑約40cm，算法描述的兩個(gè)障礙物之間的距離小于40cm，則認(rèn)為兩個(gè)障礙物之間不可通行，用上下或者左右鄰接的兩個(gè)障礙物柵格表示。兩個(gè)障礙物在柵格地圖中處于對角線位置時(shí)，若對角線之間的距離大于40cm，則認(rèn)為可以通行。

假設(shè)無人車轉(zhuǎn)彎因子為a，a受轉(zhuǎn)彎角度的大小影響；無人車前進(jìn)距離為x；函數(shù)A表示轉(zhuǎn)彎消耗；函數(shù)D表示前進(jìn)消耗；常量E表示無人車系統(tǒng)的自身消耗；代價(jià)函數(shù)F(a，x)，表示線性SVM平滑部分的總消耗。

在這種情況下算法應(yīng)用了線性SVM［19～20］，在確保實(shí)驗(yàn)用車運(yùn)動到障礙物之間對角線之上后，對后邊的路徑進(jìn)行線性劃分，這樣就可以在下次遇到障礙物之前調(diào)整車的位姿，因此縮短了路徑長度。同時(shí)在算法進(jìn)行線性SVM優(yōu)化前，無人車是在檢測到下一障礙物之后進(jìn)行位姿調(diào)整，優(yōu)化后提前調(diào)整位姿，無人車具有更大的轉(zhuǎn)彎角度，節(jié)省了無人車的運(yùn)行時(shí)間，提高了效率。

7 實(shí)驗(yàn)及分析

7.1 實(shí)驗(yàn)環(huán)境

本次實(shí)驗(yàn)的環(huán)境如圖8（a），環(huán)境中的障礙物隨機(jī)擺放，實(shí)驗(yàn)采集的雷達(dá)圖像如圖8（b），圖中可以明顯地看出整個(gè)實(shí)驗(yàn)環(huán)境的邊界，中間部分的障礙物。邊界左下角部分不夠明顯是因?yàn)?，雷達(dá)的掃描線受玻璃門的影響而沒有返回其邊界的數(shù)據(jù)。

圖8 實(shí)驗(yàn)環(huán)境

7.2 實(shí)驗(yàn)結(jié)果

以下為D*算法的一次路徑規(guī)劃實(shí)驗(yàn)：實(shí)驗(yàn)環(huán)境為VS2010，柵格規(guī)模為30×30，柵格節(jié)點(diǎn)總數(shù)為31×31，黃色矩形圖標(biāo)代表起點(diǎn)，綠色六角圖標(biāo)代表終點(diǎn)，黑色矩形圖標(biāo)代表初始障礙物，紅叉代表動態(tài)添加的障礙物。圖9為一次完整的路徑規(guī)劃過程，圖9（a）為隨機(jī)標(biāo)記的障礙物，算法給出的最短路徑；圖9（b）為模擬無人車的移動；圖9（c）為路徑點(diǎn)上出現(xiàn)新的障礙，無人車后退一步；圖9（d）為算法給出了最新的最短路徑；圖9（e）為無人車遇到堵塞，搜索周圍給出的最短路徑；圖9（f）為重新規(guī)劃并最終到達(dá)終點(diǎn)。整個(gè)過程可以看出算法不存在死鎖的情況，具有很好的魯棒性。

圖9 一次完整的規(guī)劃

由于實(shí)驗(yàn)所在環(huán)境的影響，測試時(shí)調(diào)整了地圖創(chuàng)建的柵格的尺寸。圖10為接收雷達(dá)數(shù)據(jù)后繪制的環(huán)境地圖以及最終路徑對比圖，由于雷達(dá)采集數(shù)據(jù)存在一定的誤差，柵格地圖經(jīng)過了一些手工的標(biāo)定。以下為未優(yōu)化的D*算法與線性核SVM優(yōu)化后的D*算法的結(jié)果比較圖（以下對比只選取最終的路徑比較）。

圖10 對比結(jié)果圖

表1為多次實(shí)驗(yàn)結(jié)果后的得出的路徑長度（單位：CM）。從表中可以看出，基于SVM的受約束D*改進(jìn)算法比傳統(tǒng)的D*算法具有更短的路徑，同時(shí)經(jīng)過SVM線性平滑后，無人車的轉(zhuǎn)彎時(shí)間會更短。無人車應(yīng)用本算法有更高的效率。

表1 算法路徑長度對比

8 結(jié)語

對于移動機(jī)器人的動態(tài)路徑平滑規(guī)劃問題，本文使用了受約束D*的算法的動態(tài)路徑規(guī)劃和基于SVM的路徑平滑。受約束D*的算法的路徑規(guī)劃在實(shí)際的環(huán)境下具有較好的表現(xiàn)，考慮到機(jī)器人的模型及尺寸以及運(yùn)動，能夠生成可行的運(yùn)動軌跡?；赟VM的路徑平滑能夠在處理障礙物與非障礙物的交界處表現(xiàn)較好，可以使得路徑更為的平滑，使移動機(jī)器人能夠安全流暢的通過障礙物。實(shí)驗(yàn)時(shí)我們設(shè)置了多個(gè)障礙以檢測算法的正確性，從模擬結(jié)果與實(shí)際場景的結(jié)果，驗(yàn)證了算法具有有效性和實(shí)用性。

［1］趙陽.無人駕駛汽車關(guān)鍵技術(shù)［J］.應(yīng)用技術(shù)，2011，26：272.

ZHAO Yang.The Key Technologies of Automated Vehicle［J］.China Science and Technology Review，2011，26：272.

［2］朱大奇，顏明重.移動機(jī)器人路徑規(guī)劃技術(shù)綜述［J］.控制與決策，2010，25（7）：961-967.

ZHU Daqi，YAN Mingzhong.Survey on technology of mo?bile robot path planning［J］.Control and Decision，2010，25（7）：961-967.

［3］曲道奎，杜振軍，徐殿國，等.移動機(jī)器人路徑規(guī)劃方法研究［J］.機(jī)器人，2008，30（2）：97-101，106.

QU Daokui，DU Zhenjun，WU Dianguo，et al.Research on Path Planning for a Mobile Robot［J］.ROBOT，2008，30（2）：97-101，106.

［4］T.Lozano-Perez，M.Wesley.An Algorithm for Planning Collision-free Paths Among Polyhedral Obstacles［J］.Communica-tions of the ACM，1979，22（5）：436-450.

［5］M.Metea，J.Tsai.Route planning for intelligence autono?mous land vehicles using hierarchical terrain representa?tion［C］//Ro-botics and Automation.1987 IEEE Interna?tional Conference on，1987：1947-1952.

［6］O Khatib.Real-time Obstacle Avoidance for Manipulators and Mobile Robots［J］.Int J Robotics Research，1986，5（1）：90-98.

［7］張彪，曹其新，王雯珊.使用三維柵格地圖的移動機(jī)器人路徑規(guī)劃［J］.西安交通大學(xué)學(xué)報(bào)，2013，47（10）：57-61.

ZHANG Biao，CAO Qixin，WANG Wenshan.An Algo?rithm for Mobile Robot Path Planning Based on 3D Grid Map［J］.Journal of Xi`an Jiaotong University，2013，47（10）：57-61.

［8］I.Zohar，A.Ailon，R.Rabinovici.Mobile robot char?ac-terized by dynamic and kinematic equations and actua?tor dynamics：Trajectory tracking and related application.Robotics and Auton.Syst.，2011，59（6）：343-353，

［9］Kuo-Ho Su，F(xiàn)eng-Li Lian，Chan-Yun Yang.Navigation design with SVM path planning and fuzzy-basedpath tracking for wheeled agent［C］//2012 International confer?ence on Fuzzy Theory and Its Applications，2012：273-278.

［10］Anthony Stentz.Optimal and Efficient Path Planning for Partially-Known Environments［M］.The Robotics Insti?tute；Cmegie Mellon University；Pittsburgh，PA 15213.

［11］Anthony Stentz.The Focussed D*Algorithm for Re?al-Time Replanning［C］//Robotics Institute Carnegie Mellon University Pittsburgh，Pennsylvania 15213 U.S.A

［12］P.E.Hart，N.J.Nilsson，and B.Raphael.A formal ba?sis for the heuristic determination of minimum cost paths in graphs［C］//IEEE Trans.Syst.Sci.and Cybernetics，SSC-4（2）：100-107，1968.

［13］N.M.Amato，Y.Wu.A Randomized Roadmap Method for Path and Manipulation Planning［J］.In Proceedings of 1996 IEEE Int.Conf.on Robotics and Automa-tion，pp.113-120，1996.

［14］S.Avidan.Support Vector Tracking［C］//IEEE Trans.On Pattern Analysis and Machine Intelligence，Vol

［15］C.J.Burges.A Tutorial on Support Vector Machines for Pattern Recognition［J］.Data Mining and Knowledge Dis?covery，1998，2（2）：121-167.

［16］ Nikhil ajaj，Niko J.Murrell，Julie G.Whitney，Jan P.Alle?bach；George T.C.Chiu.Expert-prescribed weighting for support vector machineclassification［C］//2016 IEEE International Conference on Advanced Intelligent Mecha?tronics（AIM）.913-918，2016.

［17］Hiroshi Kawase， Yojiro Mori， Hiroshi Hasegawa，Ken-ichi Sato.Dynamic Router Performance Control Uti?liz-ing SupportVector Machines for Energy Consumption Reduction［J］.IEEE Transactions on Network and Ser?vice Manage-ment.Vol.pp，1-1，2016.

［18］ Gaze latent support vector machine for image classifica?tion.Xin Wang，Nicolas Thome，Matthieu Cord 2016［C］//IEEE Interna-tional Conference on Image Process?ing（ICIP）.236-240，2016.

［19］M.Krishna Satya Varma，N.K.K.Rao，K.K.Raju，G.P.S.Varma.Pixel-Based Classification Us-ing Support Vector MachineClassifier［C］//2016 IEEE 6th Interna?tional Conference on Advanced Computing（IACC）.51-55，2016.

［20］Pin-Kao Huang，Jyh-Horng Chou.Uniform design meth?od to finding the optimal parameters for support vector machine［C］//2016 International Conference on System Science and Engineering（ICSSE）.1-3，2016.

An App lication of Constrained D*A lgorithm Based on Support Vector M achine in Automated Vehicle Routing

LIU Xiaotao CAI Yunfei WANG Tiancheng
（College of Computer Science and Engineering，Nanjing University of Science&Technology，Nanjing 210094）

TP391

10.3969/j.issn.1672-9722.2017.09.013

2017年4月1日，

2017年5月17日

國家軍口核高基（編號：2015ZX01041101）；國家自然基金青年項(xiàng)目（編號：61305134）；教育部博士點(diǎn)基金項(xiàng)目（編號：20133219120035）資助。

劉曉濤，男，碩士研究生，研究方向：智能機(jī)器人路徑規(guī)劃。蔡云飛，男，講師，研究方向：模式識別與智能系統(tǒng)。王田橙，男，碩士研究生，研究方向：智能機(jī)器人SLAM算法。