基于K-Means與SVM結合的柵格分區路徑規劃方法*

張堂凱，羅 杰，李龍俊

(南京郵電大學 自動化學院，江蘇 南京 210023)

?

基于K-Means與SVM結合的柵格分區路徑規劃方法*

張堂凱，羅 杰，李龍俊

(南京郵電大學 自動化學院，江蘇 南京 210023)

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

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

0 引言

目前市場上的智能清潔機器人在路徑規劃上大多數采用隨機遍歷的策略，清掃的全遍歷差，耗時長。路徑規劃是智能清潔機器人的基礎問題，對于規劃路徑的優化主要在于提高清掃覆蓋率，降低重復率。

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

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

1 地圖建模

圖1 MATLAB基于柵格法的環境建模效果圖

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

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

本文使用MATLAB平臺對柵格地圖的優化進行仿真實驗。使用直角坐標系法對柵格地圖進行標識，環境中一共有6個障礙物，其中1個凹形障礙物，5個矩形障礙物。

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

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

2.1 聚類步驟

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

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

初始化最大簇類個數為K，最大迭代次數為Tmax，系統允許最大誤差為εmax；

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

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

(1)

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

(2)

將樣本點xi分配到離它最近的簇類中。

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

(3)

(5)按照公式(4)計算每個簇類內的評價函數SSE。

(4)

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

2.2 聚類仿真實驗

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

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

圖2 柵格地圖內的障礙物柵格聚類

3 基于SVM的柵格地圖分區

SVM算法通過尋求結構化風險的最小，來增大算法學習機的泛化能力，在最小化經驗風險的同時獲得最優的置信區間[6]。使用SVM算法處理數據樣本，即使樣本數量較少也能獲得比較好的統計規律。SVM算法是統計學習、最優化方法與核函數方法的結合[7]。

圖4 線性可分情況下的最優分類線

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

(w×x)+b=0

(5)

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

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

(6)

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

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

(7)

(8)

(9)

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

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

將第2節橫向聚類得到的圖3使用SVM分類算法對柵格進行分類，得到如圖5和圖6的結果，圖中標出的柵格點為分類算法的支持向量，將支持向量的坐標和最優分類面在y=0、y=ymax的坐標都提取出來，用于柵格地圖分區。

圖5 區域1和區域2的柵格分類

圖6 區域2和區域3的柵格分類

利用之前提取的支持向量的坐標、分類面和邊界的坐標，結合第2節中的聚類結果，生成一個多邊形。再計算出多邊形的邊y={1,2,3,…,ymax}時對應的x值，然后比較柵格中點與多邊形邊上點相同y值情況下，x值的大小關系，根據x值大小的不同可以將柵格地圖劃分為3類。

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

圖7 柵格地圖分區

4 蟻群算法以及仿真

蟻群能夠協同完成很多復雜的任務，蟻群算法只是對蟻群覓食行為的抽象與優化。

(10)

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

(11)

(12)

其中ρ為信息素殘留系數,0<ρ<1，1-ρ為信息素揮發系數[9]。

(13)

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

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

根據上面的分析，實驗選取適當的參數，使用蟻群算法對第3節中已經分區完畢的柵格進行仿真實驗。實驗參數設置為ρ=0.15,ε=0.1,β=2.5,m=30,q0=0.85,NCmax=50。得到圖8所示的實驗效果圖，圖9為基于聚類分區和蟻群算法的清潔機器人路徑收斂曲線。

圖8 分區和蟻群算法路徑尋優效果圖

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

5 結論

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

[1] 曾碧, 楊宜民. 動態環境下基于蟻群算法的實時路徑規劃方法[J]. 計算機應用研究, 2010, 27(3)：860-863.

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

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

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

[6] 梁燕.SVM分類器的擴展及其應用研究[D].長沙:湖南大學,2008.

[7] 張學工. 關于統計學習理論與支持向量機[J]. 自動化學報, 2000, 26(1): 32-42.

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

[9] 王越, 葉秋冬. 蟻群算法在求解最短路徑問題上的改進策略[J]. 計算機工程與應用, 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

國家自然科學基金(61203028)

TP312

A

10.19358/j.issn.1674- 7720.2016.21.005

張堂凱，羅杰，李龍俊. 基于K-Means與SVM結合的柵格分區路徑規劃方法[J].微型機與應用，2016,35(21)：16-19,23.

2016-08-02)

張堂凱(1992-)，男，碩士，主要研究方向：智能系統應用。

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

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