張?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］等人將蟻群算法與一種概率路線(xiàn)圖相結(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)誤差平方和最小［5］,。
2.1聚類(lèi)步驟
K-Means聚類(lèi)算法對(duì)柵格地圖中的障礙物進(jìn)行聚類(lèi)，主要步驟如下：
?。?）將障礙物柵格坐標(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)中。
?。?）按照公式（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線(xiàn)性可分情況下的最優(yōu)分類(lèi)線(xiàn)面，兩個(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ì)線(xiàn)性可分的數(shù)據(jù)樣本(xi,yi),xi∈Rn,yi∈{1,－1},i=1,2,…,l,滿(mǎn)足：
此時(shí)分類(lèi)間隔等于2/w,，要使間隔距離最大也就是要使得w2最小并符合式（6）的最優(yōu)分界面。
SVM要解決的數(shù)學(xué)問(wèn)題可以理解為在滿(mǎ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ī)器人路徑收斂曲線(xiàn)。
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)
?。?］ 曾碧, 楊宜民. 動(dòng)態(tài)環(huán)境下基于蟻群算法的實(shí)時(shí)路徑規(guī)劃方法［J］. 計(jì)算機(jī)應(yīng)用研究, 2010, 27(3)：860-863.
［2］ 張赤斌,王興松.基于蟻群算法的完全遍歷路徑規(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.
［5］ 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.