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

楊 云，魏秀卓，趙 艷

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中：s—機器人執(zhí)行的躲避動作；r—動作相對應(yīng)的參數(shù)，求出(s，r)的最大Q值并對目標信號做強化趨近處理。對信號強化處理設(shè)置可控制范圍：

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

(xg，yg)—爬壁機器人下一目標位置坐標；

dqg—兩者之間的距離；

Δdqg—爬壁機器人位移差；

ω—爬壁機器人移動一次的長度；

q—信號強化的控制范圍，通過對信號強范圍的控制得出機器人躲避障礙物的動作范圍并得出規(guī)劃路線。

4 路徑平滑處理

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

式中：P(u)—曲線運動軌跡控制點；

P(f)—位置描述點；

P(0)—曲線的起點；

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

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

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

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

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

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

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

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

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

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

（7）對最終路徑平滑處理。

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

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

5 實驗

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

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

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

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

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

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

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

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

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

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

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

圖5 爬壁機器人壁面運動收斂曲線圖Fig.5 Convergence Curve of Wall Motion of Wall Climbing Robot

6 結(jié)論

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

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

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