基于多維數(shù)據(jù)挖掘的智能機(jī)器人避障路徑自適應(yīng)選擇

王苗, 李明倩, 劉芳

(1.武漢城市學(xué)院,實(shí)驗(yàn)實(shí)訓(xùn)中心,湖北,武漢 430083; 2.武漢大學(xué),計算機(jī)學(xué)院,湖北,武漢 430072)

0 引言

智能機(jī)器人集合了環(huán)境感知、軌跡規(guī)劃和行為決策等多種功能,一直是高新技術(shù)領(lǐng)域研究熱點(diǎn),已經(jīng)廣泛應(yīng)用在航空、國防、工業(yè)生產(chǎn)和醫(yī)療服務(wù)等領(lǐng)域。機(jī)器人技術(shù)在國內(nèi)外普遍得到重視,尤其在西方一些國家,機(jī)器人不僅能代替人們探索惡劣的外太空環(huán)境,還可以輔助人們進(jìn)行深海作業(yè),幫助人們完成更多艱巨的任務(wù)。無論機(jī)器人執(zhí)行哪種任務(wù)都離不開傳感器、導(dǎo)航、識別等技術(shù),以解決明確身在何處、目的地點(diǎn)以及如何到達(dá)目標(biāo)地點(diǎn)這三個問題。智能機(jī)器人需通過傳感器獲取環(huán)境信息找到最佳避障路徑,因此路徑選擇問題成為機(jī)器人執(zhí)行任務(wù)的重要前提。路徑選擇可描述為在具有障礙物的環(huán)境中,根據(jù)相關(guān)規(guī)范為機(jī)器人規(guī)劃一條從起點(diǎn)到終點(diǎn)的不碰撞路徑。

現(xiàn)階段,機(jī)器人路徑選擇經(jīng)常借助數(shù)學(xué)工具實(shí)現(xiàn)。例如韓順杰等[1]基于改進(jìn)粒子群算法規(guī)劃機(jī)器人軌跡。將時間作為適應(yīng)度函數(shù)優(yōu)化軌跡,融合分段式差值函數(shù)與粒子群算法,減少函數(shù)構(gòu)造的復(fù)雜度,同時避免陷入局部最優(yōu)。熊俊濤等[2]利用深度強(qiáng)化學(xué)習(xí)算法獲得機(jī)器人避障路徑。結(jié)合機(jī)器人運(yùn)動學(xué)模型和實(shí)際工作任務(wù),設(shè)置環(huán)境觀測集合,將其作為網(wǎng)絡(luò)輸入,使用人工勢場法構(gòu)建獎懲函數(shù),將障礙物范圍懲罰變換成單一懲罰,分析碰撞結(jié)果,優(yōu)化路徑長度,提高機(jī)器人工作效率的同時實(shí)現(xiàn)避障。

機(jī)器人路徑選擇屬于一項(xiàng)復(fù)雜的問題,當(dāng)障礙物靜止不動時上述方法能夠選擇出最佳路徑。但是如果障礙物處于運(yùn)動狀態(tài),則會出現(xiàn)碰撞問題。為此,本文通過多維數(shù)據(jù)挖掘技術(shù)確保機(jī)器人能夠自適應(yīng)選擇避障路徑。數(shù)據(jù)挖掘[3]就是從海量數(shù)據(jù)中提取有用的信息。實(shí)現(xiàn)數(shù)據(jù)挖掘的方式多種多樣,通常分為統(tǒng)計學(xué)習(xí)和機(jī)器學(xué)習(xí)兩大類。本文選用機(jī)器學(xué)習(xí)[4]完成多維數(shù)據(jù)挖掘。路徑選擇在機(jī)器學(xué)習(xí)中屬于最優(yōu)化問題,需通過智能算法解決,蟻群算法針對此類問題有著突出的表現(xiàn)。通過機(jī)器人采集模塊獲取作業(yè)環(huán)境、運(yùn)動模型、障礙物信息等多維數(shù)據(jù),將其作為蟻群算法的參數(shù)信息,經(jīng)過多次迭代,挖掘出有用的信息素,自適應(yīng)輸出最佳避障路徑。

1 智能機(jī)器人多維數(shù)據(jù)采集

1.1 機(jī)器人運(yùn)動數(shù)據(jù)

通過固連坐標(biāo)系表示機(jī)器人在空間內(nèi)的位置,同時考慮機(jī)器人位置矢量等相關(guān)概念[5]。

(1) 位置描述

(1)

(2) 位姿描述

(2)

1.2 作業(yè)環(huán)境數(shù)據(jù)

構(gòu)建機(jī)器人工作環(huán)境模型,通過環(huán)境表示方法描述工作區(qū)域內(nèi)的機(jī)器人位置,為路徑規(guī)劃提供依據(jù)。假設(shè)B代表一個智能機(jī)器人,在作業(yè)區(qū)間內(nèi)存在多個障礙物O={O1,O2,…,On},將每個障礙物當(dāng)作一個多邊形。為便于描述機(jī)器人運(yùn)行路線,將其看作一個點(diǎn)。

利用可視圖建模方式建立作業(yè)環(huán)境模型[6],主要步驟如下。

步驟一:簡化障礙物,假設(shè)PS和PG分別表示機(jī)器人起點(diǎn)與終點(diǎn),作直線PSPG,保證PSPG可以穿過障礙物;分別在PS、PG兩端選擇距離PSPG最遠(yuǎn)的障礙物頂點(diǎn)Phigh和Plow;利用PS、PG、Phigh和Plow4個點(diǎn)作四邊形,如果PS和PG的某一端存在多個滿足要求的頂點(diǎn),則將這些點(diǎn)分別和起點(diǎn)、終點(diǎn)相連;判斷是否存在除穿越穿直線PSPG外的其他障礙物和四邊形相交,即使位于四邊形內(nèi)部也算相交,如果有,則需要保存;保留穿過直線PSPG的障礙物和與四邊形相交的障礙物,去除其他障礙物。

步驟二:視圖最小化處理,最小化視圖由2個障礙物的公共切線構(gòu)成,按照相關(guān)要求能夠分割為多個最小可視圖。

步驟三:全局視圖[7],將點(diǎn)PS和PG添加到工作區(qū)域中,構(gòu)建完整視圖。

1.3 障礙物感知數(shù)據(jù)

如果僅依靠單一傳感器獲取障礙物信息,難以保障信息的全面性。機(jī)器人自身設(shè)置了多種類型傳感器,利用這些傳感器采集障礙物形狀、大小、狀態(tài)等數(shù)據(jù)。

將視覺傳感器作為障礙物形狀信息采集的第一階段,再通過超聲波和紅外傳感器分別測試障礙物距離,通常情況下超聲波適用于短距離測試,而紅外傳感器則多用于長距離,使用二者共同檢測的方式彌補(bǔ)了各自不足,可獲取障礙物精準(zhǔn)信息。

(1) 圖像采集

圖像采集是機(jī)器人視覺系統(tǒng)的重要功能[8],此模塊同時也負(fù)責(zé)圖像處理、儲存、結(jié)果判斷等任務(wù),將判斷結(jié)果通過無線網(wǎng)絡(luò)上傳到上位機(jī)。機(jī)器人圖像采集部分整體結(jié)構(gòu)如圖1所示。

圖1 圖像采集模塊結(jié)構(gòu)圖

(2) 超聲波測距

超聲波[9]類型的傳感器包括發(fā)送端和接收端。在測距過程中,碰到障礙物時,聲波返回,接收端不再計時。如果V是超聲波傳播速度,t是發(fā)送和接收的時間差,則機(jī)器人到障礙物的距離S表示為

(3)

溫度對超聲波傳輸速度帶來一定影響,若溫度為T,超生波傳輸速度表達(dá)式如下:

V=221.45+0.607T

(4)

(3) 紅外測距

紅外傳感器通過光學(xué)測距原理獲取障礙物距離。假設(shè)在紅外系統(tǒng)中,光源經(jīng)過透鏡L1后生成外發(fā)散光線,光線觸碰到障礙物時反射,又經(jīng)過透鏡L2匯聚到光敏器件中,構(gòu)成入射光斑D。如果L1與L2的間距是b,透鏡與光敏器件的間距是f′,光斑D和光敏器件中心點(diǎn)C的間距是y′,則結(jié)合三角形相似理論,獲得待測距離h:

(5)

只要獲取光敏器件中入射光點(diǎn)的坐標(biāo),即可獲取障礙物距離。

2 基于多維數(shù)據(jù)挖掘的機(jī)器人避障路徑選擇

2.1 避障路徑自適應(yīng)選擇的約束條件

為獲得最佳路徑選擇結(jié)果,基于上述獲取的機(jī)器人運(yùn)動參數(shù)、作業(yè)環(huán)境數(shù)據(jù)以及障礙物距離等多維數(shù)據(jù),設(shè)計一種基于蟻群算法的數(shù)據(jù)挖掘方法,通過挖掘過程實(shí)現(xiàn)機(jī)器人避障路徑的自適應(yīng)選擇。在算法執(zhí)行前,還需設(shè)置路徑選擇的相關(guān)約束條件,確立目標(biāo)函數(shù)。

(1) 時間約束

f1=min(maxt′) (1≤t′≤n)

(6)

式中,f1是機(jī)器人從起點(diǎn)PS到終點(diǎn)PG所用的最短時間,t′是時間節(jié)點(diǎn)。

(2) 路程最短

(7)

式中,f2是PS與PG間最短軌跡,(xi,yi)是路徑坐標(biāo)點(diǎn)。

(3) 轉(zhuǎn)彎次數(shù)

(8)

式中,f3是機(jī)器人運(yùn)行過程中的最少轉(zhuǎn)彎次數(shù)。

結(jié)合上述3個約束條件,建立機(jī)器人路徑選擇目標(biāo)函數(shù):

F=a1f1+a2f2+a3f3

(9)

式中,a1、a2和a3都屬于最優(yōu)路徑選擇系數(shù)。

2.2 機(jī)器人避障路徑自適應(yīng)選擇

將采集的所有多維數(shù)據(jù)作為蟻群算法的參數(shù)信息,通過螞蟻覓食過程實(shí)現(xiàn)機(jī)器人避障路徑自適應(yīng)選擇。蟻群算法在問題空間進(jìn)行獨(dú)立的解搜索不僅增加了算法的可靠性,也使得算法具有較強(qiáng)的全局搜索能力。不僅如此,蟻群算法具有較強(qiáng)的魯棒性,且參數(shù)數(shù)目少,設(shè)置簡單,因此具有較高的執(zhí)行效率。

螞蟻在尋找食物時會產(chǎn)生信息素,路徑越短的螞蟻產(chǎn)生的信息素越多,隨時間增加,信息素會越來越多,而選擇該路徑的螞蟻也會增加。利用此種反饋機(jī)制系確定最佳路徑,該方法具有自適應(yīng)性強(qiáng)、迭代過程簡便等優(yōu)勢。具體實(shí)現(xiàn)過程如下。

(1) 信息素表示

信息素作為蟻群覓食過程的信息載體,影響著算法的全局收斂性能,決定求解速度。當(dāng)利用蟻群算法計算三維空間路徑選擇問題時,通常使用柵格化建模方式,將空間做網(wǎng)格化處理,用離散點(diǎn)表示網(wǎng)格單元。

為減小空間復(fù)雜程度,將離散點(diǎn)直接作為信息素載體,任意一個離散點(diǎn)均有各自的信息素值,該值大小決定了對螞蟻的吸引程度。

(2) 狀態(tài)轉(zhuǎn)移規(guī)則設(shè)置

算法執(zhí)行過程中,蟻群會根據(jù)信息量選擇目標(biāo)點(diǎn),將其稱為轉(zhuǎn)移概率[10],其中決策規(guī)則即為偽隨機(jī)比規(guī)則。此規(guī)則就是在轉(zhuǎn)移時,利用啟發(fā)信息和信息素信息,對目標(biāo)點(diǎn)做趨向性搜索。本文設(shè)置的概率轉(zhuǎn)移規(guī)則如下。

假設(shè)螞蟻數(shù)量為M,將所有螞蟻放置在初始位置,在路徑生成過程中,利用式(10)獲取下一步蟻群將會移動到哪個位置:

(10)

式中,J屬于隨機(jī)變量,q和q0均為隨機(jī)常數(shù),取值范圍分別為q∈[0,1]、q0∈[0,1]。τt′+1描述平面上某點(diǎn)的信息素含量,ηt′,t′+1屬于啟發(fā)函數(shù)[11],可啟發(fā)未來信息。

針對平面∏t′+1上某點(diǎn)Pt′(it′,jt′,kt′)上的蟻群,選取∏t′+1上的Pt′+1(it′+1,jt′+1,kt′+1)的概率表示為

(11)

將兩個鄰近路徑之間的距離當(dāng)作路徑選擇的優(yōu)化準(zhǔn)則[12],則啟發(fā)函數(shù)ηt′,t′+1表示為

(12)

式中,d′為兩個相鄰路徑之間的最短距離。

(3) 信息素更新準(zhǔn)則

在蟻群規(guī)劃路徑時,必須掌握環(huán)境的全局信息。為此,需更新全部路徑上的信息素,計算信息素濃度差異[13],便于選擇最佳路徑。

信息素更新通常包括全局和局部更新兩種。其中,前者表示螞蟻完成某次循環(huán)后對整個空間的信息素更新,更新公式如下:

(13)

(14)

(15)

式中,ρ是信息素?fù)]發(fā)因子,取值為0<ρ<1,Δτit′jt′kt′是經(jīng)過一次循環(huán)后,信息素增量。

局部更新。當(dāng)螞蟻轉(zhuǎn)移到新路徑點(diǎn)上時,需使用局部更新方式更新信息素:

(16)

式中,μ代表常數(shù),取值為0<μ<1。

重復(fù)狀態(tài)轉(zhuǎn)移和信息素更新過程,當(dāng)滿足迭代次數(shù)要求時,輸出所選的避障路徑。

3 仿真實(shí)驗(yàn)數(shù)據(jù)分析與研究

仿真實(shí)驗(yàn)中,選擇輪式智能機(jī)器人作為仿真目標(biāo)。該產(chǎn)品由飛凌公司生產(chǎn),在市場上應(yīng)用較為成熟。其內(nèi)部資源豐富,Samsung S3C6410是它的核心,可支持多類型接口,開發(fā)人員可根據(jù)自身需求調(diào)試。除安裝超聲波傳感器外,還設(shè)置了紅外傳感器,可采集多維度環(huán)境信息。機(jī)器人其他性能參數(shù)如表1所示。

表1 機(jī)器人性能參數(shù)表

在機(jī)器人參數(shù)不變條件下,分別設(shè)置靜態(tài)和動態(tài)障礙物場景,分析本文方法、改進(jìn)粒子群算法和深度強(qiáng)化學(xué)習(xí)方法自適應(yīng)選擇路徑,測試結(jié)果如下。

(1) 靜態(tài)障礙物環(huán)境

當(dāng)障礙物為靜止不動時,假設(shè)不同方法下的機(jī)器人起點(diǎn)和終點(diǎn)的位置相同,則路徑選擇情況分別如圖2～圖4所示。

圖2 本文方法自適應(yīng)路徑選擇結(jié)果圖

圖3 改進(jìn)粒子群算法自適應(yīng)路徑選擇結(jié)果圖

圖4 深度強(qiáng)化學(xué)習(xí)方法自適應(yīng)路徑選擇結(jié)果圖

分析圖2～圖4可知:當(dāng)障礙物為靜態(tài)時,本文方法能夠選擇最短路徑;改進(jìn)粒子群算法雖然能夠成功躲避障礙物,但是路徑較長;深度強(qiáng)化學(xué)習(xí)算法當(dāng)躲避障礙物轉(zhuǎn)彎時出現(xiàn)碰撞現(xiàn)象。這是因?yàn)楸疚倪x擇的目標(biāo)函數(shù)較為合理,在時間、路程和轉(zhuǎn)彎次數(shù)最少的約束下完成避障路徑自適應(yīng)選擇。

(2) 動態(tài)障礙物環(huán)境

假設(shè)機(jī)器人運(yùn)動的起點(diǎn)坐標(biāo)為(1,19),動態(tài)障礙物的起點(diǎn)坐標(biāo)為(2,5),兩者分別以各自設(shè)定的速度運(yùn)動。假設(shè)在不躲避障礙物情況下,在坐標(biāo)為(16,5)處相遇。在此種狀況下,分別利用不同算法完成避障路徑自適應(yīng)選擇,選擇結(jié)果如圖5～圖7所示。

圖5 本文方法路徑選擇結(jié)果圖

圖6 改進(jìn)粒子群算法路徑選擇結(jié)果

圖7 深度強(qiáng)化學(xué)習(xí)方法路徑選擇結(jié)果

由圖5～圖7能夠看出,在障礙物不斷運(yùn)動的情況下,本文方法可以準(zhǔn)確判斷出障礙物的位置,及時躲避障礙物,未發(fā)生碰撞現(xiàn)象。此外,避障結(jié)束后本文所提方法的機(jī)器人依然能夠快速回到指定運(yùn)行軌跡上繼續(xù)前進(jìn),直到到達(dá)終點(diǎn)位置。這是因?yàn)榛谙伻核惴ǖ亩嗑S數(shù)據(jù)挖掘可以有效獲取各方面信息,綜合這些信息為路徑選擇提供更多依據(jù)。

(3) 算法收斂性比較

算法收斂性是驗(yàn)證算法收斂性能最為重要的指標(biāo)之一,所以比較了本文算法、改進(jìn)粒子群算法、深度強(qiáng)化學(xué)習(xí)算法在智能機(jī)器人避障路徑自適應(yīng)選擇中的收斂性,比較結(jié)果如圖8所示。

圖8 算法收斂性比較

分析圖8可知,改進(jìn)粒子群算法在130次左右實(shí)現(xiàn)了收斂,損失值保持在較低水平,說明這一算法的收斂速度慢。而與改進(jìn)粒子群算法相比,深度強(qiáng)化學(xué)習(xí)算法的一直未收斂,且損失值保持在一個較高的水平,說明該算法的收斂性能差。本文算法在30次左右就實(shí)現(xiàn)了收斂,且損失值一直保持在一個較低水平,說明該算法的收斂速度快,收斂性能更優(yōu)。

4 總結(jié)

為進(jìn)一步擴(kuò)大智能機(jī)器人的應(yīng)用領(lǐng)域,完善路徑選擇等功能,本文利用多維數(shù)據(jù)挖掘方法選擇避障路徑。融合環(huán)境、機(jī)器人自身動力學(xué)參數(shù)、障礙物信息等多維數(shù)據(jù),通過蟻群算法的迭代過程不斷挖掘數(shù)據(jù)的有用信息,為路徑選擇提供數(shù)據(jù)支持。仿真實(shí)驗(yàn)表明,本文所提方法在障礙物為靜態(tài)和動態(tài)時都能表現(xiàn)出很強(qiáng)的避障能力。還有更多問題需要解決。例如,建立的機(jī)器人工作環(huán)境較為簡單,應(yīng)提高環(huán)境復(fù)雜度。此外,基于蟻群算法的數(shù)據(jù)挖掘還要解決算法搜索速度問題,提高搜索效率。