基于K-Means與SVM結(jié)合的柵格分區(qū)路徑規(guī)劃方法*

張?zhí)脛P，羅 杰，李龍俊

(南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210023)

?

基于K-Means與SVM結(jié)合的柵格分區(qū)路徑規(guī)劃方法*

張?zhí)脛P，羅 杰，李龍俊

(南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210023)

智能清潔機(jī)器人全局路徑規(guī)劃中，利用柵格法對(duì)清潔機(jī)器人的工作環(huán)境進(jìn)行建模。分別介紹了K-Means聚類算法和支持向量機(jī)(SVM)算法，使用K-Means聚類算法與支持向量機(jī)(SVM)相結(jié)合的方法，以不同的約束條件進(jìn)行聚類，在含有復(fù)雜障礙物的柵格地圖時(shí)能有效減少分區(qū)，利用蟻群算法對(duì)分區(qū)后的柵格地圖路徑規(guī)劃仿真，有效地提高了蟻群算法在柵格地圖路徑規(guī)劃中的整體效率。

柵格地圖；K-Means聚類；支持向量機(jī)(SVM)；蟻群算法

0 引言

目前市場(chǎng)上的智能清潔機(jī)器人在路徑規(guī)劃上大多數(shù)采用隨機(jī)遍歷的策略，清掃的全遍歷差，耗時(shí)長。路徑規(guī)劃是智能清潔機(jī)器人的基礎(chǔ)問題，對(duì)于規(guī)劃路徑的優(yōu)化主要在于提高清掃覆蓋率，降低重復(fù)率。

蟻群算法是智能理論研究領(lǐng)域的一種主要算法，可以用于大部分需要優(yōu)化的應(yīng)用領(lǐng)域，其中潛力比較大的領(lǐng)域主要有：模式識(shí)別、信號(hào)處理、電力控制以及移動(dòng)機(jī)器人路徑規(guī)劃等。曾碧[1]等人將蟻群算法與一種概率路線圖相結(jié)合來規(guī)劃機(jī)器人路徑，該方法可以減少蟻群算法在進(jìn)行大規(guī)模路徑規(guī)劃的時(shí)間。張赤斌[2]等人將Boustrophedon單元分解法與蟻群算法相結(jié)合，采用局部區(qū)域遍歷與全局運(yùn)動(dòng)相結(jié)合的完全遍歷路徑規(guī)劃方法，在降低算法復(fù)雜性的同時(shí)又加快了算法的收斂速度。但是蟻群算法還具有容易收斂到局部最優(yōu)解和解決大規(guī)模優(yōu)化問題時(shí)收斂速度過慢的缺點(diǎn)。這些缺點(diǎn)影響了蟻群算法在路徑規(guī)劃方面的使用。

針對(duì)路徑優(yōu)化算法在解決完全遍歷路徑規(guī)劃效率低下的問題，本文使用K-Means聚類算法與支持向量機(jī)(Support Vector Machine,SVM)相結(jié)合的方法，以不同的約束條件進(jìn)行聚類，使得柵格地圖被縱向地分割成幾個(gè)區(qū)域，然后再利用蟻群算法對(duì)分割完成的柵格區(qū)域進(jìn)行路徑尋優(yōu)，使得蟻群算法總體效率大幅增加，有效地減少了算法的收斂時(shí)間，取得了很好的路徑規(guī)劃效果。

1 地圖建模

圖1 MATLAB基于柵格法的環(huán)境建模效果圖

柵格法(Grid)以地圖的二維環(huán)境模型作為基礎(chǔ)，將地圖分成若干個(gè)柵格，每個(gè)柵格記錄周圍環(huán)境的信息[3]。

以環(huán)境地圖二維柵格圖的左下角為原點(diǎn)，Y軸豎直向上，X軸水平向右，單元柵格的邊長為1。MATLAB基于柵格法的環(huán)境建模效果圖如圖1所示。

本文使用MATLAB平臺(tái)對(duì)柵格地圖的優(yōu)化進(jìn)行仿真實(shí)驗(yàn)。使用直角坐標(biāo)系法對(duì)柵格地圖進(jìn)行標(biāo)識(shí)，環(huán)境中一共有6個(gè)障礙物，其中1個(gè)凹形障礙物，5個(gè)矩形障礙物。

2 基于K-Means的柵格障礙物聚類

K-Means聚類算法由MACQUEEN J B[4]在1967年提出，K-means算法的基本思想是：從給定的n數(shù)據(jù)樣本的集合中任取k個(gè)數(shù)據(jù)樣本作為初始的聚類中心，再根據(jù)相似性度量函數(shù)計(jì)算其他未被選取的數(shù)據(jù)樣本與各個(gè)聚類中心的相似性，并根據(jù)該相似度，將該數(shù)據(jù)樣本劃分到與它相似性最高的聚類中心所在的簇類中，根據(jù)簇類中樣本的平均值更新聚類中心，直到簇類內(nèi)誤差平方和最小[5]。

2.1 聚類步驟

K-Means聚類算法對(duì)柵格地圖中的障礙物進(jìn)行聚類，主要步驟如下：

(1)將障礙物柵格坐標(biāo)輸入樣本集：Ω={xi|xi=(xi1,xi2,…,xid),i=1,2,…,n}；

初始化最大簇類個(gè)數(shù)為K，最大迭代次數(shù)為Tmax，系統(tǒng)允許最大誤差為εmax；

(2)從Ω中隨機(jī)選取K個(gè)柵格坐標(biāo)作為初始簇類中心，記為：C={cj|cj=(cj1,cj2,…,cj3),j=1,2,…,K}；

(3)定義dis(xi,cj)為任意點(diǎn)xi和任意點(diǎn)xj之間的歐幾里得距離，公式如下：

(1)

計(jì)算點(diǎn)xi與點(diǎn)xj之間的歐幾里得距離，將樣本點(diǎn)xi按公式(2)計(jì)算，其中sij屬于集合C。

(2)

將樣本點(diǎn)xi分配到離它最近的簇類中。

(4)按照公式(3)更新中心。其中cj為同一個(gè)簇類的中心點(diǎn)，N(φj)為簇類φj中數(shù)據(jù)樣本的個(gè)數(shù)，xi=(xi1,xi2,…,xid)。

(3)

(5)按照公式(4)計(jì)算每個(gè)簇類內(nèi)的評(píng)價(jià)函數(shù)SSE。

(4)

(6)如果|SSET-SSET-1<εmax|或者T=Tmax，循環(huán)結(jié)束并輸出結(jié)果；否則令T=T+1跳轉(zhuǎn)步驟(2)。

2.2 聚類仿真實(shí)驗(yàn)

將障礙物柵格點(diǎn)xi和點(diǎn)xj的歐幾里得距離帶入算法進(jìn)行仿真，使代表障礙物的柵格聚集到一起，得到圖2所示的聚類效果圖，其中“+”為簇類中心。

再將柵格點(diǎn)xi和點(diǎn)xj橫坐標(biāo)歐幾里得距離帶入算法進(jìn)行仿真，使得柵格地圖中代表障礙物的柵格橫向聚成3類，得到圖3所示的聚類效果圖，圖中淺色的“+”為新的簇類中心，這為下一步的分區(qū)做準(zhǔn)備。

圖2 柵格地圖內(nèi)的障礙物柵格聚類

3 基于SVM的柵格地圖分區(qū)

SVM算法通過尋求結(jié)構(gòu)化風(fēng)險(xiǎn)的最小，來增大算法學(xué)習(xí)機(jī)的泛化能力，在最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)的同時(shí)獲得最優(yōu)的置信區(qū)間[6]。使用SVM算法處理數(shù)據(jù)樣本，即使樣本數(shù)量較少也能獲得比較好的統(tǒng)計(jì)規(guī)律。SVM算法是統(tǒng)計(jì)學(xué)習(xí)、最優(yōu)化方法與核函數(shù)方法的結(jié)合[7]。

圖4 線性可分情況下的最優(yōu)分類線

SVM的基本思想如圖4所示，實(shí)心圓圈和空心圓圈分別代表兩種不同的數(shù)據(jù)樣本，H為最優(yōu)分類界面，H1和H2分別是數(shù)據(jù)樣本類型的類界面，兩個(gè)類界面之間的距離叫分類間隔(margin)，類界面與最優(yōu)分類界面之間的距離叫界面間隔[8]。最優(yōu)分類界面要求將兩類數(shù)據(jù)樣本分開的同時(shí)保證分類間隔最大。分類界面的數(shù)學(xué)表達(dá)式為：

(w×x)+b=0

(5)

將其歸一化，使得對(duì)線性可分的數(shù)據(jù)樣本(xi,yi),xi∈Rn,yi∈{1,-1},i=1,2,…,l,滿足：

yi[(w×x)+b]≥1,i=1,2,…,l

(6)

SVM要解決的數(shù)學(xué)問題可以理解為在滿足式(7)條件下，求解式(8)的最小值。

yi(wTxi+b)-1≥0,i=1,2,…,n

(7)

(8)

(9)

定義L(w,b,a)函數(shù)如式(9)，系數(shù)ai≥0。這樣就可以通過w和b求函數(shù)的最小值來求得φ(w)的最小值。

將式(7)作為約束條件，求最小值問題就可以轉(zhuǎn)化為凸二次規(guī)劃的對(duì)偶問題。

將第2節(jié)橫向聚類得到的圖3使用SVM分類算法對(duì)柵格進(jìn)行分類，得到如圖5和圖6的結(jié)果，圖中標(biāo)出的柵格點(diǎn)為分類算法的支持向量，將支持向量的坐標(biāo)和最優(yōu)分類面在y=0、y=ymax的坐標(biāo)都提取出來，用于柵格地圖分區(qū)。

圖5 區(qū)域1和區(qū)域2的柵格分類

圖6 區(qū)域2和區(qū)域3的柵格分類

利用之前提取的支持向量的坐標(biāo)、分類面和邊界的坐標(biāo)，結(jié)合第2節(jié)中的聚類結(jié)果，生成一個(gè)多邊形。再計(jì)算出多邊形的邊y={1,2,3,…,ymax}時(shí)對(duì)應(yīng)的x值，然后比較柵格中點(diǎn)與多邊形邊上點(diǎn)相同y值情況下，x值的大小關(guān)系，根據(jù)x值大小的不同可以將柵格地圖劃分為3類。

仿真實(shí)驗(yàn)如圖7所示。相對(duì)于基于四叉樹的柵格地圖分區(qū)和基于Boustrophedon單元分解法的柵格地圖分區(qū)，本文中基于K-Means和SVM的柵格地圖分區(qū)數(shù)量更少，在解決柵格地圖中含有大量障礙物柵格時(shí)也能取得較好的分區(qū)效果。

圖7 柵格地圖分區(qū)

4 蟻群算法以及仿真

蟻群能夠協(xié)同完成很多復(fù)雜的任務(wù)，蟻群算法只是對(duì)蟻群覓食行為的抽象與優(yōu)化。

(10)

τij(t+n)=ρ·τij(t)+Δτij

(11)

(12)

其中ρ為信息素殘留系數(shù),0<ρ<1，1-ρ為信息素?fù)]發(fā)系數(shù)[9]。

(13)

其中Q為信息素強(qiáng)度，為螞蟻在一次循環(huán)中在走過的路徑上釋放的信息素總量，它影響算法的收斂速度，Lk為第k只螞蟻單次循環(huán)中走過的路徑長度的總和。

Ant-Cycle模型使用的是全局信息，即所有螞蟻完成一次遍歷之后再對(duì)路徑上殘留的信息素進(jìn)行調(diào)整。

根據(jù)上面的分析，實(shí)驗(yàn)選取適當(dāng)?shù)膮?shù)，使用蟻群算法對(duì)第3節(jié)中已經(jīng)分區(qū)完畢的柵格進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)參數(shù)設(shè)置為ρ=0.15,ε=0.1,β=2.5,m=30,q0=0.85,NCmax=50。得到圖8所示的實(shí)驗(yàn)效果圖，圖9為基于聚類分區(qū)和蟻群算法的清潔機(jī)器人路徑收斂曲線。

圖8 分區(qū)和蟻群算法路徑尋優(yōu)效果圖

圖9 分區(qū)和蟻群算法的路徑收斂曲線

5 結(jié)論

本文提出了一種新的基于聚類分區(qū)和蟻群算法的清潔機(jī)器人路徑規(guī)劃方法。利用柵格法對(duì)清潔機(jī)器人的工作環(huán)境進(jìn)行建模，使用K-Means聚類算法與支持向量機(jī)(SVM)相結(jié)合的方法對(duì)柵格進(jìn)行分區(qū)，再利用蟻群算法對(duì)分割完成的柵格區(qū)域進(jìn)行路徑尋優(yōu)。清潔機(jī)器人沿著優(yōu)化路徑完成對(duì)已知環(huán)境的全區(qū)域覆蓋，仿真實(shí)驗(yàn)結(jié)果表明，本文提出的方法能夠高效地實(shí)現(xiàn)清潔機(jī)器人全局路徑規(guī)劃。

[1] 曾碧, 楊宜民. 動(dòng)態(tài)環(huán)境下基于蟻群算法的實(shí)時(shí)路徑規(guī)劃方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2010, 27(3)：860-863.

[2] 張赤斌,王興松.基于蟻群算法的完全遍歷路徑規(guī)劃研究[J].中國機(jī)械工程,2008,19(16):1945-1949.

[3] 田春穎,劉瑜,馮申坤.基于柵格地圖的移動(dòng)機(jī)器人完全遍歷算法——矩形分解法[J].機(jī)械工程學(xué)報(bào),2004,40(10):56-61.

[4] 李薈嬈.K-means聚類方法的改進(jìn)及其應(yīng)用[D].哈爾濱:東北農(nóng)業(yè)大學(xué),2014.[5] JAIN A K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666.

[6] 梁燕.SVM分類器的擴(kuò)展及其應(yīng)用研究[D].長沙:湖南大學(xué),2008.

[7] 張學(xué)工. 關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)[J]. 自動(dòng)化學(xué)報(bào), 2000, 26(1): 32-42.

[8] VAPNIK V N,VAPNIK V.Statistical learning theory[M]. New York: Wiley, 1998.

[9] 王越, 葉秋冬. 蟻群算法在求解最短路徑問題上的改進(jìn)策略[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(13): 35-38.

Path planning method based on K-Means and SVM combination grid partition

Zhang Tangkai, Luo Jie, Li Longjun

(College of Automation, Nanjing University of Posts and Telecommunications, Nanjing 210023,China)

In the global path planning of intelligent cleaning robot, the grid method is used to model the working environment of the robot. This paper introduced K-means clustering algorithm and Support Vector Machine (SVM) algorithm, using a combination of K-means clustering algorithm and SVM method for clustering with different constraint conditions. In the gird map containing complex obstacles, raster map can effectively reduce partition. Using ant colony algorithm to simulate the partitioned grid map path planning. It can effectively improve the ant colony algorithm in path planning of raster map of overall efficiency.

grid map; K-Means clustering; Support Vector Machine (SVM); ant colony algorithm

國家自然科學(xué)基金(61203028)

TP312

A

10.19358/j.issn.1674- 7720.2016.21.005

張?zhí)脛P，羅杰，李龍俊. 基于K-Means與SVM結(jié)合的柵格分區(qū)路徑規(guī)劃方法[J].微型機(jī)與應(yīng)用，2016,35(21)：16-19,23.

2016-08-02)

張?zhí)脛P(1992-)，男，碩士，主要研究方向：智能系統(tǒng)應(yīng)用。

羅杰(1965-)，男，博士，教授，主要研究方向：分布式智能控制系統(tǒng)，群體智能等。

李龍俊(1988-)，男，碩士，主要研究方向：智能系統(tǒng)應(yīng)用。