張?zhí)脛P，羅杰，李龍俊
（南京郵電大學(xué) 自動化學(xué)院，江蘇 南京 210023）
摘要：智能清潔機器人全局路徑規(guī)劃中，利用柵格法對清潔機器人的工作環(huán)境進行建模。分別介紹了K-Means聚類算法和支持向量機（SVM）算法，使用K-Means聚類算法與支持向量機（SVM）相結(jié)合的方法，以不同的約束條件進行聚類，在含有復(fù)雜障礙物的柵格地圖時能有效減少分區(qū)，利用蟻群算法對分區(qū)后的柵格地圖路徑規(guī)劃仿真，有效地提高了蟻群算法在柵格地圖路徑規(guī)劃中的整體效率。
關(guān)鍵詞：柵格地圖；K-Means聚類；支持向量機（SVM）；蟻群算法
0引言
目前市場上的智能清潔機器人在路徑規(guī)劃上大多數(shù)采用隨機遍歷的策略，清掃的全遍歷差，耗時長。路徑規(guī)劃是智能清潔機器人的基礎(chǔ)問題，對于規(guī)劃路徑的優(yōu)化主要在于提高清掃覆蓋率，降低重復(fù)率。
蟻群算法是智能理論研究領(lǐng)域的一種主要算法，可以用于大部分需要優(yōu)化的應(yīng)用領(lǐng)域，其中潛力比較大的領(lǐng)域主要有：模式識別、信號處理、電力控制以及移動機器人路徑規(guī)劃等。曾碧［1］等人將蟻群算法與一種概率路線圖相結(jié)合來規(guī)劃機器人路徑，該方法可以減少蟻群算法在進行大規(guī)模路徑規(guī)劃的時間。張赤斌［2］等人將Boustrophedon單元分解法與蟻群算法相結(jié)合，采用局部區(qū)域遍歷與全局運動相結(jié)合的完全遍歷路徑規(guī)劃方法，在降低算法復(fù)雜性的同時又加快了算法的收斂速度。但是蟻群算法還具有容易收斂到局部最優(yōu)解和解決大規(guī)模優(yōu)化問題時收斂速度過慢的缺點。這些缺點影響了蟻群算法在路徑規(guī)劃方面的使用。
針對路徑優(yōu)化算法在解決完全遍歷路徑規(guī)劃效率低下的問題，本文使用K-Means聚類算法與支持向量機（Support Vector Machine,SVM）相結(jié)合的方法，以不同的約束條件進行聚類，使得柵格地圖被縱向地分割成幾個區(qū)域，然后再利用蟻群算法對分割完成的柵格區(qū)域進行路徑尋優(yōu)，使得蟻群算法總體效率大幅增加，有效地減少了算法的收斂時間，取得了很好的路徑規(guī)劃效果。
1地圖建模
柵格法（Grid）以地圖的二維環(huán)境模型作為基礎(chǔ)，將地圖分成若干個柵格，每個柵格記錄周圍環(huán)境的信息［3］。
以環(huán)境地圖二維柵格圖的左下角為原點，Y軸豎直向上，X軸水平向右，單元柵格的邊長為1。MATLAB基于柵格法的環(huán)境建模效果圖如圖1所示。
本文使用MATLAB平臺對柵格地圖的優(yōu)化進行仿真實驗。使用直角坐標(biāo)系法對柵格地圖進行標(biāo)識，環(huán)境中一共有6個障礙物，其中1個凹形障礙物，5個矩形障礙物。
2基于K-Means的柵格障礙物聚類
K-Means聚類算法由MACQUEEN J B［4］在1967年提出，K-means算法的基本思想是：從給定的n數(shù)據(jù)樣本的集合中任取k個數(shù)據(jù)樣本作為初始的聚類中心，再根據(jù)相似性度量函數(shù)計算其他未被選取的數(shù)據(jù)樣本與各個聚類中心的相似性，并根據(jù)該相似度，將該數(shù)據(jù)樣本劃分到與它相似性最高的聚類中心所在的簇類中，根據(jù)簇類中樣本的平均值更新聚類中心，直到簇類內(nèi)誤差平方和最小［5］。
2.1聚類步驟
K-Means聚類算法對柵格地圖中的障礙物進行聚類，主要步驟如下：
?。?）將障礙物柵格坐標(biāo)輸入樣本集：
初始化最大簇類個數(shù)為K，最大迭代次數(shù)為Tmax，系統(tǒng)允許最大誤差為εmax；
?。?）從Ω中隨機選取K個柵格坐標(biāo)作為初始簇類中心，記為：
?。?）定義dis(xi,cj)為任意點xi和任意點xj之間的歐幾里得距離，公式如下：
計算點xi與點xj之間的歐幾里得距離，將樣本點xi按公式（2）計算，其中sij屬于集合C。
將樣本點xi分配到離它最近的簇類中。
?。?）按照公式（3）更新中心。其中cj為同一個簇類的中心點，N(φj)為簇類φj中數(shù)據(jù)樣本的個數(shù)，xi=(xi1,xi2,…,xid)。
?。?）按照公式（4）計算每個簇類內(nèi)的評價函數(shù)SSE。
（6）如果|SSET－SSET－1<εmax|或者T=Tmax，循環(huán)結(jié)束并輸出結(jié)果；否則令T=T+1跳轉(zhuǎn)步驟（2）。
2.2聚類仿真實驗
將障礙物柵格點xi和點xj的歐幾里得距離帶入算法進行仿真，使代表障礙物的柵格聚集到一起，得到圖2所示的聚類效果圖，其中“+”為簇類中心。
再將柵格點xi和點xj橫坐標(biāo)歐幾里得距離帶入算法進行仿真，使得柵格地圖中代表障礙物的柵格橫向聚成3類，得到圖3所示的聚類效果圖，圖中淺色的“+”為新的簇類中心，這為下一步的分區(qū)做準(zhǔn)備。
3基于SVM的柵格地圖分區(qū)
SVM算法通過尋求結(jié)構(gòu)化風(fēng)險的最小，來增大算法學(xué)習(xí)機的泛化能力，在最小化經(jīng)驗風(fēng)險的同時獲得最優(yōu)的置信區(qū)間［6］。使用SVM算法處理數(shù)據(jù)樣本，即使樣本數(shù)量較少也能獲得比較好的統(tǒng)計規(guī)律。SVM算法是統(tǒng)計學(xué)習(xí)、最優(yōu)化方法與核函數(shù)方法的結(jié)合［7］。
SVM的基本思想如圖4所示，實心圓圈和空心圓圈分別代表兩種不同的數(shù)據(jù)樣本，H為最優(yōu)分類界面，H1和H2分別是數(shù)據(jù)樣本類型的類界圖4線性可分情況下的最優(yōu)分類線面，兩個類界面之間的距離叫分類間隔（margin），類界面與最優(yōu)分類界面之間的距離叫界面間隔［8］。最優(yōu)分類界面要求將兩類數(shù)據(jù)樣本分開的同時保證分類間隔最大。分類界面的數(shù)學(xué)表達(dá)式為：
將其歸一化，使得對線性可分的數(shù)據(jù)樣本(xi,yi),xi∈Rn,yi∈{1,－1},i=1,2,…,l,滿足：
此時分類間隔等于2/w，要使間隔距離最大也就是要使得w2最小并符合式（6）的最優(yōu)分界面。
SVM要解決的數(shù)學(xué)問題可以理解為在滿足式（7）條件下，求解式（8）的最小值。
定義L(w,b,a)函數(shù)如式（9），系數(shù)ai≥0。這樣就可以通過w和b求函數(shù)的最小值來求得φ(w)的最小值。
將式（7）作為約束條件，求最小值問題就可以轉(zhuǎn)化為凸二次規(guī)劃的對偶問題。
這是一個在不等式約束條件下求解二次函數(shù)解的問題，存在唯一最優(yōu)解。不妨令a*i為最優(yōu)解，則
其中a*i的值不是零的數(shù)據(jù)樣本就是支持向量。b*可由φ(w)=0解得，最后求得的最優(yōu)分類函數(shù)為：
將第2節(jié)橫向聚類得到的圖3使用SVM分類算法對柵格進行分類，得到如圖5和圖6的結(jié)果，圖中標(biāo)出的柵格點為分類算法的支持向量，將支持向量的坐標(biāo)和最優(yōu)分類面在y=0、y=ymax的坐標(biāo)都提取出來，用于柵格地圖分區(qū)。
利用之前提取的支持向量的坐標(biāo)、分類面和邊界的坐標(biāo)，結(jié)合第2節(jié)中的聚類結(jié)果，生成一個多邊形。再計算出多邊形的邊y={1,2,3,…,ymax}時對應(yīng)的x值，然后比較柵格中點與多邊形邊上點相同y值情況下，x值的大小關(guān)系，根據(jù)x值大小的不同可以將柵格地圖劃分為3類。
仿真實驗如圖7所示。相對于基于四叉樹的柵格地圖分區(qū)和基于Boustrophedon單元分解法的柵格地圖分區(qū)，本文中基于K-Means和SVM的柵格地圖分區(qū)數(shù)量更少，在解決柵格地圖中含有大量障礙物柵格時也能取得較好的分區(qū)效果。
4蟻群算法以及仿真
蟻群能夠協(xié)同完成很多復(fù)雜的任務(wù)，蟻群算法只是對蟻群覓食行為的抽象與優(yōu)化。
蟻群算法：首先初始化參數(shù)，然后將m只螞蟻隨機地放置到n個城市中，同時更新禁忌表tabuk。開始時，每條路徑上的信息素量相等，設(shè)(C為常數(shù))τij(0)=C。螞蟻根據(jù)啟發(fā)式信息和每條路徑上的信息素量選擇它要去的下一地點［9］。螞蟻k在t時刻從點i轉(zhuǎn)移到點j的概率pkij(t)為：
其中，allowedk={1,2,…,n}－tabuk是螞蟻下一步可以選擇去的點。禁忌表tabuk中存儲了螞蟻已經(jīng)走過的點，當(dāng)tabuk中存儲點的數(shù)量等于n時，說明螞蟻k本次循環(huán)結(jié)束。式（10）中通常取ηij=1lij，α為信息啟發(fā)因子，即路徑的相對重要性；β為期望啟發(fā)因子，即啟發(fā)因子的相對重要性。當(dāng)一次循環(huán)完成后，根據(jù)式（11）更新路徑上的信息素。
其中ρ為信息素殘留系數(shù),0<ρ<1，1－ρ為信息素?fù)]發(fā)系數(shù)［9］。
根據(jù)信息素更新策略不同，給出了Δτkij的更新方法，在Ant Cycle模型中：
其中Q為信息素強度，為螞蟻在一次循環(huán)中在走過的路徑上釋放的信息素總量，它影響算法的收斂速度，Lk為第k只螞蟻單次循環(huán)中走過的路徑長度的總和。
Ant Cycle模型使用的是全局信息，即所有螞蟻完成一次遍歷之后再對路徑上殘留的信息素進行調(diào)整。
根據(jù)上面的分析，實驗選取適當(dāng)?shù)膮?shù)，使用蟻群算法對第3節(jié)中已經(jīng)分區(qū)完畢的柵格進行仿真實驗。實驗參數(shù)設(shè)置為ρ=0.15,ε=0.1,β=2.5,m=30,q0=0.85,NCmax=50。得到圖8所示的實驗效果圖，圖9為基于聚類分區(qū)和蟻群算法的清潔機器人路徑收斂曲線。
5結(jié)論
本文提出了一種新的基于聚類分區(qū)和蟻群算法的清潔機器人路徑規(guī)劃方法。利用柵格法對清潔機器人的工作環(huán)境進行建模，使用K-Means聚類算法與支持向量機（SVM）相結(jié)合的方法對柵格進行分區(qū)，再利用蟻群算法對分割完成的柵格區(qū)域進行路徑尋優(yōu)。清潔機器人沿著優(yōu)化路徑完成對已知環(huán)境的全區(qū)域覆蓋，仿真實驗結(jié)果表明，本文提出的方法能夠高效地實現(xiàn)清潔機器人全局路徑規(guī)劃。
參考文獻(xiàn)
?。?］ 曾碧, 楊宜民. 動態(tài)環(huán)境下基于蟻群算法的實時路徑規(guī)劃方法［J］. 計算機應(yīng)用研究, 2010, 27(3)：860-863.
［2］ 張赤斌,王興松.基于蟻群算法的完全遍歷路徑規(guī)劃研究［J］.中國機械工程,2008,19(16):1945-1949.
?。?］ 田春穎,劉瑜,馮申坤.基于柵格地圖的移動機器人完全遍歷算法——矩形分解法［J］.機械工程學(xué)報,2004,40(10):56-61.
?。?］ 李薈嬈.K-means聚類方法的改進及其應(yīng)用［D］.哈爾濱:東北農(nóng)業(yè)大學(xué),2014.
?。?］ JAIN A K. Data clustering: 50 years beyond Kmeans［J］. Pattern Recognition Letters, 2010, 31(8): 651-666.
?。?］ 梁燕.SVM分類器的擴展及其應(yīng)用研究［D］.長沙:湖南大學(xué),2008.
?。?］ 張學(xué)工. 關(guān)于統(tǒng)計學(xué)習(xí)理論與支持向量機［J］. 自動化學(xué)報, 2000, 26(1): 32-42.
［8］ VAPNIK V N,VAPNIK V.Statistical learning theory［M］. New York: Wiley, 1998.
?。?］ 王越, 葉秋冬. 蟻群算法在求解最短路徑問題上的改進策略［J］. 計算機工程與應(yīng)用, 2012, 48(13): 35-38.