步態(tài)數(shù)據(jù)挖掘在爬壁機(jī)器人路徑規(guī)劃中的應(yīng)用

楊 云，魏秀卓，趙 艷

（1.長(zhǎng)春教育學(xué)院信息教研室，吉林 長(zhǎng)春 130052；2.長(zhǎng)春人文學(xué)院理工學(xué)院，吉林 長(zhǎng)春 130117；3.長(zhǎng)春師范大學(xué)教育學(xué)院，吉林 長(zhǎng)春 130123）

1 引言

爬壁機(jī)器人因其垂直立面作業(yè)的特性，屬于一種特種作業(yè)機(jī)器人，例如油罐、橋梁等建筑物的檢測(cè)，高層建筑物壁面清潔等，甚至?xí)玫椒纯謧刹爝@類特殊工作上。由于爬壁機(jī)器人不同于水平面行走的機(jī)器人，所以對(duì)其行走的路徑需要作出更具體和完善的規(guī)劃，以保證爬壁機(jī)器人能夠安全行走的同時(shí)高效工作。

由于爬壁機(jī)器人在立面極限作業(yè)的情況下，危險(xiǎn)性以及耗能都相當(dāng)之高，因此針對(duì)爬壁機(jī)器人進(jìn)行路徑規(guī)劃時(shí)，應(yīng)盡量減少其與障礙物相遇甚至是產(chǎn)生碰撞的情況，最大限度的保證機(jī)器人的安全性。同時(shí)因?yàn)楸诿媾佬胁煌谒叫凶?，機(jī)器人受到重力、摩擦力等因素的影響，其靈敏度以及越障能力都會(huì)有所下降，因此在路徑設(shè)計(jì)時(shí)，主要考慮路徑的長(zhǎng)度問(wèn)題，路徑是否平滑以及對(duì)障礙物的規(guī)避是否有效。例如，文獻(xiàn)［1］通過(guò)電勢(shì)場(chǎng)法，降低環(huán)境復(fù)雜度并對(duì)其利用電路流通能夠快速地獲得搜索路徑并平滑處理，但沒(méi)有考慮到動(dòng)態(tài)障礙物對(duì)機(jī)器人的行走路線的影響；文獻(xiàn)［2］利用免疫優(yōu)化算法，根據(jù)障礙物實(shí)際情況建立地圖模型，采用精英保留策略加強(qiáng)局部搜索，但其搜索時(shí)間較長(zhǎng)，對(duì)機(jī)器人的反應(yīng)速度有限制。

為此這里通過(guò)對(duì)越障步態(tài)數(shù)據(jù)的挖掘，研究出了一種適用于爬壁機(jī)器人的實(shí)時(shí)路徑規(guī)劃方法，在蟻群算法的基礎(chǔ)上加入避障因子，通過(guò)蟻群信息素的更新迭代找到最優(yōu)路徑，并利用障礙規(guī)避策略對(duì)實(shí)時(shí)可能產(chǎn)生的障礙物進(jìn)行探測(cè)和規(guī)避，最終將路徑曲線進(jìn)行平滑，減少爬壁機(jī)器人行走時(shí)的能耗，使能夠安全、無(wú)碰撞地完成作業(yè)。

2 爬壁機(jī)器人越障步態(tài)數(shù)據(jù)挖掘

根據(jù)數(shù)據(jù)挖掘原理，利用關(guān)聯(lián)規(guī)則挖掘爬壁機(jī)器人越障步態(tài)數(shù)據(jù)。在爬壁機(jī)器人工作環(huán)境中，定義任意一個(gè)數(shù)據(jù)項(xiàng)均為候選項(xiàng)集的集合F1中的元素，掃描數(shù)據(jù)庫(kù)并利用式（1）得到F1中各元素的支持度。

式中：c(f1∪f(wàn)2)—障礙數(shù)據(jù)f1，f2同時(shí)出現(xiàn)概率值；|D|—關(guān)聯(lián)規(guī)則挖掘的越障步態(tài)數(shù)據(jù)集。設(shè)η—最小支持度閾值，在F1中選擇支持度不小于η的項(xiàng)集組成越障步態(tài)數(shù)據(jù)頻繁項(xiàng)集為L(zhǎng)1。根據(jù)生成的關(guān)聯(lián)規(guī)則將其裁剪得到壓縮過(guò)后的C3。之后再一次遍歷越障步態(tài)數(shù)據(jù)庫(kù)，并得到F3中各元素的支持度。在F3中挑選支持度不小于η的項(xiàng)集組成越障步態(tài)數(shù)據(jù)頻繁項(xiàng)集的集合L3。最后對(duì)L3進(jìn)行自連接，以數(shù)據(jù)包的形式輸出爬壁機(jī)器人越障步態(tài)數(shù)據(jù)的挖掘結(jié)果。

3 爬壁機(jī)器人路徑規(guī)劃

3.1 蟻群算法最優(yōu)路徑選擇

蟻群覓食時(shí)會(huì)對(duì)搜索路徑釋放本身獨(dú)有的信息素，大量蟻群在不斷搜索的過(guò)程中，經(jīng)過(guò)最優(yōu)路徑或是折點(diǎn)的概率加大，從而這個(gè)地方會(huì)有很多螞蟻分泌的信息素，蟻群最終會(huì)根據(jù)信息素的數(shù)量來(lái)選擇最優(yōu)路徑，信息素的數(shù)值越高代表經(jīng)過(guò)此路徑的螞蟻越多且路徑有效。蟻群初始搜索時(shí)，信息素會(huì)分布不均勻，搜索時(shí)間以及路徑都比較長(zhǎng)，這里對(duì)搜索范圍作出限制，并將蟻群迷路的情況排除，最終將沒(méi)有迷路的蟻群信息素更新利用，尋找最優(yōu)路徑。

以上述得到的越障步態(tài)數(shù)據(jù)數(shù)據(jù)包為基礎(chǔ)，為了使蟻群搜索路徑保證在可控范圍內(nèi)，在矩形地圖的基礎(chǔ)上設(shè)定S、T兩點(diǎn)分別作為蟻群的出發(fā)點(diǎn)和目標(biāo)點(diǎn)，并將這兩點(diǎn)作為對(duì)角頂點(diǎn)在矩形地圖內(nèi)設(shè)置一個(gè)有效區(qū)域地圖，并增加該有效區(qū)域內(nèi)的信息素?cái)?shù)值，具體如下：

式中：τ0—矩形地圖內(nèi)信息素初始數(shù)值；C—常數(shù)且大于τ0；x—地圖序列號(hào)；R—矩形地圖內(nèi)有效區(qū)域。

為了避免蟻群在地圖上盲目搜索，這里對(duì)整個(gè)矩形地圖的初始信息素分布作出調(diào)整，如圖1所示。從圖1可以看出最優(yōu)路徑應(yīng)為S點(diǎn)到T點(diǎn)這個(gè)方向上的路徑，因此由出發(fā)點(diǎn)S和目標(biāo)點(diǎn)T作為對(duì)角頂點(diǎn)的矩形地圖內(nèi)蟻群信息素初始數(shù)值設(shè)定為C，地圖其他區(qū)域信息素?cái)?shù)值不變，這樣不僅可以減少螞蟻盲目搜索產(chǎn)生的無(wú)用路徑，也可以減少搜索時(shí)間提高效率。

圖1 信息素初始值分配Fig.1 Pheromone Initial Value Allocation

蟻群在剛開始搜索階段可能會(huì)產(chǎn)生很多的交叉路徑，且會(huì)有一部分螞蟻出現(xiàn)迷路的現(xiàn)象，迷失過(guò)程中沒(méi)有走到終點(diǎn)就停止了搜索并停留在最后搜索到的路徑原地打轉(zhuǎn)，這時(shí)對(duì)于搜索而言效率極低，尤其是在地圖面積擴(kuò)大或者是障礙物增加的時(shí)候，這種情況會(huì)更加嚴(yán)重，最終使算法不夠精準(zhǔn)且收斂速度較慢。而蟻群搜索是通過(guò)多數(shù)螞蟻不斷對(duì)路徑進(jìn)行搜索而最終篩選出來(lái)的擇優(yōu)路徑，所以當(dāng)前期搜索的結(jié)果越多且搜索質(zhì)量越好時(shí)，最終得出最優(yōu)路徑的概率越大，而且收斂速度會(huì)比較快，而蟻群搜索過(guò)程中個(gè)別螞蟻會(huì)迷路且停滯打轉(zhuǎn)的原因在于周圍各個(gè)路徑節(jié)點(diǎn)都已經(jīng)走過(guò)了且存在障礙物無(wú)法通過(guò)，所以在蟻群搜索初期本問(wèn)通過(guò)越障步態(tài)數(shù)據(jù)挖掘，利用避障策略［3］，增加避障因子safetyj。則螞蟻選擇一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)轉(zhuǎn)移的概率可以表示為：

式中：t—路徑篩選次數(shù)；k—任意一只螞蟻；i、j—不同搜索節(jié)點(diǎn)；τij—從i～j這條路徑上信息素的濃度；nij—針對(duì)螞蟻給出的啟發(fā)信息；allowk—螞蟻能夠到達(dá)下一個(gè)節(jié)點(diǎn)的路徑集合；α—信息素的重要程度；β—信息素對(duì)螞蟻尋路的指導(dǎo)程度；Oj—和j相鄰且有障礙物的柵格數(shù)量；Lj—和j相鄰但無(wú)法通過(guò)的柵格數(shù)量；Aj—柵格總數(shù)；ε—避障系數(shù)且為正。

增加避障策略能夠使蟻群在篩選搜索路徑時(shí)進(jìn)入迷路停滯狀態(tài)［4］的概率減小，此時(shí)：

式中：Nmax—最大篩選次數(shù)；Nm—當(dāng)前的篩選次數(shù)；δ—取值范圍在（0.5，1）的調(diào)整系數(shù)。

當(dāng)q0在初始階段取值較大時(shí)，螞蟻能夠通過(guò)對(duì)整個(gè)地圖的路徑搜索找到相對(duì)比較有利的路徑，經(jīng)過(guò)這個(gè)階段，再將q0的取值調(diào)小，有利于蟻群對(duì)路徑的隨機(jī)搜索。

每經(jīng)過(guò)一次搜索路徑的篩選后，將能夠到達(dá)目標(biāo)點(diǎn)的螞蟻信息素進(jìn)行更新保留，從而將未能到達(dá)目標(biāo)點(diǎn)、迷路停滯的螞蟻剔除，來(lái)保證信息素的有效性，如式（7）所示。

式中：ρ—信息素的揮發(fā)程度，ρ∈(0，1)；Δτij—螞蟻在路徑(i，j)上信息素的增量變化；t—時(shí)間。

同時(shí)為了讓信息素保持優(yōu)化，對(duì)全局信息素作出基礎(chǔ)擇優(yōu)規(guī)劃，分別對(duì)優(yōu)質(zhì)螞蟻和劣質(zhì)螞蟻所經(jīng)過(guò)路徑的信息素做加強(qiáng)和減弱處理，為避免信息素不均勻?qū)λ阉鳟a(chǎn)生過(guò)大影響，對(duì)其進(jìn)行濃度限值，即，設(shè)λ—信息素的增加比例，且大于0小于1，如式（8）所示：

對(duì)信息素?fù)]發(fā)程度ρ作出相應(yīng)調(diào)整［5］，經(jīng)過(guò)多次篩選蟻群算法的路徑最優(yōu)解都是同一個(gè)的情況下，這時(shí)需要避免結(jié)果是陷入局部最優(yōu)循環(huán)而得出，對(duì)ρ作出如下調(diào)整：

式中：γ—信息素衰減系數(shù)，且在（0，1）范圍內(nèi)，如果調(diào)整信息素后，連續(xù)多次路徑篩選的結(jié)果都小于歷史最優(yōu)解，此時(shí)應(yīng)按照式（6）更新信息素，得出最優(yōu)搜索路徑。

3.2 路徑障礙動(dòng)態(tài)規(guī)避

由于蟻群算法找到了最優(yōu)路徑，爬壁機(jī)器人會(huì)按照既定路線進(jìn)行作業(yè)，但在墻面作業(yè)時(shí)，不能保證不出現(xiàn)墻面脫落或是高空飛物等障礙，這時(shí)爬壁機(jī)器人不能實(shí)時(shí)地應(yīng)對(duì)突發(fā)障礙而作出有效判斷并改變既定路線，而針對(duì)這一缺陷這里在蟻群搜索得出的最優(yōu)路徑上進(jìn)一步設(shè)計(jì)了障礙規(guī)避策略，給爬壁機(jī)器人安裝聲吶數(shù)據(jù)裝置，當(dāng)遇到障礙物時(shí)其斥力與合力如下：

式中：ca—機(jī)器人與障礙物的距離比例；da—聲吶裝置發(fā)出第a個(gè)探測(cè)波與障礙物之間的距離；d0—爬壁機(jī)器人在墻面作業(yè)時(shí)與障礙物間安全距離；dma—聲吶的探測(cè)波m最大探測(cè)距離；ψ—合力角度；θa—第a個(gè)探測(cè)波的探測(cè)角度。

式中：s—機(jī)器人執(zhí)行的躲避動(dòng)作；r—?jiǎng)幼飨鄬?duì)應(yīng)的參數(shù)，求出(s，r)的最大Q值并對(duì)目標(biāo)信號(hào)做強(qiáng)化趨近處理。對(duì)信號(hào)強(qiáng)化處理設(shè)置可控制范圍：

式中：(xq，yq)—爬壁機(jī)器人所在位置坐標(biāo)；

(xg，yg)—爬壁機(jī)器人下一目標(biāo)位置坐標(biāo)；

dqg—兩者之間的距離；

Δdqg—爬壁機(jī)器人位移差；

ω—爬壁機(jī)器人移動(dòng)一次的長(zhǎng)度；

q—信號(hào)強(qiáng)化的控制范圍，通過(guò)對(duì)信號(hào)強(qiáng)范圍的控制得出機(jī)器人躲避障礙物的動(dòng)作范圍并得出規(guī)劃路線。

4 路徑平滑處理

經(jīng)過(guò)蟻群擇優(yōu)路徑和障礙物規(guī)避策略，基本路徑已經(jīng)確立，但經(jīng)過(guò)蟻群算法規(guī)劃的路徑轉(zhuǎn)折點(diǎn)較多，路徑不平滑，這時(shí)要考慮的是機(jī)器人在爬壁過(guò)程中路徑的轉(zhuǎn)折次數(shù)對(duì)機(jī)器人爬壁作業(yè)的影響，對(duì)其進(jìn)行平滑處理，減少機(jī)器人爬壁路線的折點(diǎn)，并基于以上過(guò)程規(guī)劃最終路徑。這里利用貝塞爾曲線［7］對(duì)路徑進(jìn)行描述，并連接路徑轉(zhuǎn)折點(diǎn)進(jìn)行平滑處理，其表達(dá)式為：

式中：P(u)—曲線運(yùn)動(dòng)軌跡控制點(diǎn)；

P(f)—位置描述點(diǎn)；

P(0)—曲線的起點(diǎn)；

P(1)—曲線的終點(diǎn)，所有描述點(diǎn)最終組成一個(gè)特征描述多邊形；

Bf，n(u)—n次多項(xiàng)式，且：

當(dāng)n=1時(shí)，曲線為一階且為一條直線，有兩個(gè)描述點(diǎn)，當(dāng)n=2時(shí)，曲線為二階且為一條拋物線，當(dāng)n≥3時(shí)，曲線屬于高階且有n+1個(gè)描述點(diǎn)。通過(guò)函數(shù)分析求解曲線：

基于貝塞爾曲線起始點(diǎn)和多邊形的起始點(diǎn)是相同且方向一致的，那么當(dāng)曲線特征多邊形確定的時(shí)候其形狀也就跟著確定，并不受其他因素影響，基于以上算法，可以對(duì)路徑作出平滑處理［8-10］和最終規(guī)劃。具體規(guī)劃算法如下：

（1）利用柵格法建立初始地圖，確定算法參數(shù)和爬壁機(jī)器人的出發(fā)點(diǎn)與目標(biāo)點(diǎn)；

（2）令螞蟻K從出發(fā)點(diǎn)開始搜索路徑，經(jīng)參數(shù)控制得到下一個(gè)移動(dòng)點(diǎn)；

（3）判斷螞蟻是否到達(dá)目標(biāo)點(diǎn)，若達(dá)到則設(shè)置k=k+1令所有螞蟻均在這一步驟完成對(duì)路徑的搜索并初步篩選；

（4）通過(guò)蟻群中所有螞蟻的路徑搜索結(jié)果篩選出蟻群算法最優(yōu)路徑，并對(duì)信息素值做調(diào)整最終得出優(yōu)化路徑；

（5）判斷算法是否滿足退出條件，若滿足則輸出最優(yōu)路徑，反之則轉(zhuǎn)至1）；

（6）對(duì)蟻群算法得出的最優(yōu)路徑加入聲吶動(dòng)態(tài)避障策略；

（7）對(duì)最終路徑平滑處理。

根據(jù)上述規(guī)劃算法，得到具體規(guī)劃流程，如圖2所示。

圖2 蟻群算法流程圖Fig.2 Flow Chart of Ant Colony Algorithm

5 實(shí)驗(yàn)

為驗(yàn)證這里路徑規(guī)劃方法對(duì)越障爬壁機(jī)器人的有效性，對(duì)電勢(shì)場(chǎng)法、免疫優(yōu)化算法和這里方法進(jìn)行對(duì)比實(shí)驗(yàn)，從最優(yōu)路徑、迭代次數(shù)以及算法用時(shí)三個(gè)角度進(jìn)行對(duì)比。

5.1 爬壁機(jī)器人工作環(huán)境建模

這里方法所研究的爬壁機(jī)器人工作環(huán)境為高層建筑外墻面，因此首先建立爬壁機(jī)器人工作環(huán)境三維模型，如圖3所示。

圖3 爬壁機(jī)器人工作環(huán)境三維模型Fig.3 Three Dimensional Model of Working Environment of Wall Climbing Robot

圖中：O—高層建筑橫截面圓心；R—高層建筑半徑；n—爬壁機(jī)器人左端點(diǎn)；m—爬壁機(jī)器人質(zhì)心；A—爬壁機(jī)器人底板距高層建筑外壁距離；B—爬壁機(jī)器人寬度；α—機(jī)器人爬行后的曲率角。

5.2 規(guī)劃路徑曲線圖整體效果分析

以圖3為基礎(chǔ)，建立地圖模型，使勢(shì)場(chǎng)法（文獻(xiàn)［1］）、免疫優(yōu)化算法（文獻(xiàn)［2］）和這里方法均在同一環(huán)境下搜索和規(guī)劃路徑，將三種不同方法下所產(chǎn)生的規(guī)劃路徑最終結(jié)果繪制成圖，如圖4所示。

圖4 三種方法下路徑走向曲線圖Fig.4 Path Trend Curve under Three Methods

從圖4中可以看出利用電勢(shì)場(chǎng)法所規(guī)劃的路徑相對(duì)較為平滑，但不能避免較大的轉(zhuǎn)折點(diǎn)，且路徑相對(duì)較長(zhǎng)，免疫優(yōu)化算法所規(guī)劃的路徑和這里方法下規(guī)劃的路徑大致相同，不同的是免疫優(yōu)化算法的路徑折點(diǎn)較多且路徑更長(zhǎng)，這就會(huì)使爬壁機(jī)器人移動(dòng)時(shí)在耗能以及靈活度上處于劣勢(shì)，相比之下，這里方法規(guī)劃的路徑在完美躲避障礙物的同時(shí)，相對(duì)較短且折點(diǎn)較少、更加平滑。

5.3 路徑規(guī)劃收斂性對(duì)比

經(jīng)過(guò)路徑規(guī)劃的對(duì)比，只能從單一方面看出路徑的優(yōu)劣，但對(duì)方法的整體性能并不能作出一個(gè)客觀的判斷，因此為了進(jìn)一步驗(yàn)證方法的有效性，這里對(duì)三種方法收斂情況作出詳細(xì)對(duì)比，繪制成收斂曲線圖，如圖5所示。從圖5中可以看出，與電勢(shì)場(chǎng)法和免疫優(yōu)化算法相比，這里方法收斂曲線更為平穩(wěn)，且能夠在較少的迭代次數(shù)內(nèi)進(jìn)行較大幅度地收斂，相較之下收斂速度更快，穩(wěn)定性更高，在同樣的地圖上運(yùn)動(dòng)，這里所提方法能夠使機(jī)器人通過(guò)更少次數(shù)的迭代運(yùn)算找到最優(yōu)路徑，效果較好。

圖5 爬壁機(jī)器人壁面運(yùn)動(dòng)收斂曲線圖Fig.5 Convergence Curve of Wall Motion of Wall Climbing Robot

6 結(jié)論

為解決爬壁機(jī)器人在作業(yè)時(shí)，面對(duì)固定障礙物或是移動(dòng)障礙物發(fā)生接觸碰撞問(wèn)題，這里提出了基于越障步態(tài)數(shù)據(jù)挖掘的路徑規(guī)劃方法。

（1）實(shí)驗(yàn)結(jié)果表明，所提方法規(guī)劃路徑較短且折點(diǎn)更少，能夠在一定程度上減少機(jī)器人的耗能，并使路徑更加平滑減少機(jī)器人在避免移動(dòng)的困難性，同時(shí)算法收斂更快耗時(shí)更短，有效提高了路徑規(guī)劃的效率以及機(jī)器人的反應(yīng)能力，且規(guī)劃誤差小，行動(dòng)軌跡相對(duì)穩(wěn)定，有效性更好，適用性較高。

（2）這里方法同樣存在局限性，針對(duì)凹型障礙物的避障還須進(jìn)一步研究。