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