焦莉莉 王鳳嬌 張?zhí)K林 靳志剛
摘要:對(duì)復(fù)雜環(huán)境下移動(dòng)機(jī)器人全局路徑規(guī)劃問(wèn)題進(jìn)行研究,提出一種針對(duì)不規(guī)則機(jī)器人路徑規(guī)劃改進(jìn)的A*路徑規(guī)劃算法。首先,對(duì)全局運(yùn)動(dòng)空間進(jìn)行建圖錄制;然后,將全局地圖根據(jù)碰撞空間進(jìn)行地圖預(yù)處理,運(yùn)用改進(jìn)的A*算法規(guī)劃一條從起點(diǎn)到終點(diǎn)的全局路徑;最后在vs平臺(tái)將A*路徑規(guī)劃算法與改進(jìn)的A*路徑規(guī)劃算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明:文中方法較全局路徑規(guī)劃A*算法任務(wù)的效率明顯提升。
關(guān)鍵詞:移動(dòng)機(jī)器人;全局路徑規(guī)劃;A*算法
中圖分類號(hào):TP3? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼:A
文章編號(hào):1009-3044(2021)27-0098-03
在科學(xué)技術(shù)快速發(fā)展的今天,機(jī)器人在日常生活中得到廣泛的應(yīng)用,其中路徑規(guī)劃是機(jī)器人技術(shù)的一個(gè)重要組成部分。機(jī)器人的路徑規(guī)劃指在特定的工作環(huán)境中,不斷查詢障礙物信息從而找出一條從起始點(diǎn)到目標(biāo)終點(diǎn)的可通行路徑。路徑規(guī)劃算法是實(shí)現(xiàn)機(jī)器人自主移動(dòng)的關(guān)鍵前提。近年來(lái)路徑規(guī)劃的算法研究也被國(guó)內(nèi)外學(xué)者所熱衷。
目前路徑規(guī)劃算法主要有以下幾種:基于圖搜索的路徑規(guī)劃算法,如A*、D*、人工勢(shì)場(chǎng)法、柵格圖法等;基于智能仿生學(xué)的路徑規(guī)劃算法,如遺傳算法、蟻群算法等;基于圖搜索算法,雖然能夠收斂到路徑最優(yōu),但隨著空間緯度的增加會(huì)導(dǎo)致算法的復(fù)雜化;對(duì)于智能仿生學(xué)算法在進(jìn)行路徑搜索時(shí)可能會(huì)陷入局部最小值。為了更好地解決上述路徑規(guī)劃算法局限,有關(guān)學(xué)者提出一種基于采樣的路徑規(guī)劃算法,主要包括概率路標(biāo)算法[1](PRM)和快速拓展隨機(jī)樹(shù)算法[2](RRT)。
1 A*算法基本概念
A*算法的基本思想是從起點(diǎn)開(kāi)始根據(jù)評(píng)價(jià)函數(shù)不斷向目標(biāo)終點(diǎn)的方向進(jìn)行搜索,通過(guò)數(shù)據(jù)容器記錄每次搜索確定的點(diǎn),最后搜索到目標(biāo)點(diǎn),從而獲得最小代價(jià)的全局路徑。A*算法定義,移動(dòng)機(jī)器人基于在當(dāng)前柵格尋路時(shí),通常選擇八鄰域法,即有8個(gè)鄰域可作為下一步運(yùn)動(dòng)方向,分別為正前、正后、正左、正右、左前、左后、右前、右后。
A*算法目的在于獲得最小的代價(jià)路徑,其中評(píng)價(jià)函數(shù)為f( n) = g( n) + h( n)。評(píng)價(jià)函數(shù)中f(n)的物理意義為當(dāng)前點(diǎn)的評(píng)價(jià)函數(shù), g( n) 的物理意義為過(guò)去代價(jià)函數(shù),用于評(píng)價(jià)起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià),h( n) 的物理意義為當(dāng)前成本函數(shù),用于評(píng)價(jià)當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的代價(jià)。g(n)通常用固定的數(shù)值表示,但h(n)通常不是固定的,h(n)的表達(dá)式選擇會(huì)影響到f(n)最小代價(jià)函數(shù)的合理性。基于以上的設(shè)計(jì),啟發(fā)函數(shù)h(n)設(shè)計(jì)為A*算法的關(guān)鍵要素。合理的啟發(fā)函數(shù)設(shè)計(jì)能提高尋路效率。啟發(fā)函數(shù)常見(jiàn)四種表達(dá)式,其中最常用的是曼哈頓距離。
曼哈頓距離指代x坐標(biāo)方向距離與y坐標(biāo)方向距離之和,啟發(fā)函數(shù)表示:h(n)=D*[abs(xb-xn)+abs(yb-yn)],(xb,yb)為目標(biāo)節(jié)點(diǎn)坐標(biāo),(xn,yn)為當(dāng)前結(jié)點(diǎn)坐標(biāo),其中D表示h(n)啟發(fā)函數(shù)的代價(jià)系數(shù),針對(duì)不同地圖環(huán)境,通常選用不同的代價(jià)系數(shù),本方案選擇10為代價(jià)系數(shù)。例如文獻(xiàn)[3]根據(jù)當(dāng)前結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)的距離不同,嘗試了不同的代價(jià)系數(shù)D,從而實(shí)現(xiàn)障礙物環(huán)境地圖不變時(shí)降低搜索時(shí)間。
2改進(jìn)的A*算法
文獻(xiàn)[4]提出了一種融合改進(jìn)A*算法和動(dòng)態(tài)窗口法的全局動(dòng)態(tài)路徑規(guī)劃方法。但是A *算法的效率仍然比較低,如果地圖中存在比較多的U 型和 L 型等特殊障礙物時(shí),A *算法仍然需要訪問(wèn)大量無(wú)效地圖空間。因此,在路徑規(guī)劃的實(shí)際應(yīng)用中,當(dāng)?shù)貓D環(huán)境機(jī)器人通道空間比較寬闊時(shí)常常把地圖障礙物按照機(jī)器人半徑膨脹處理后再調(diào)用A*尋路算法。這樣可以減少A*算法的搜索時(shí)間。
但我們所研究的項(xiàng)目中機(jī)器人為車型機(jī)器人,地圖環(huán)境中機(jī)器人的通道空間比較狹窄,將車型機(jī)器人按照車型機(jī)器人半徑進(jìn)行障礙物膨脹處理時(shí)會(huì)導(dǎo)致狹窄區(qū)域沒(méi)有路徑。
針對(duì)這一問(wèn)題增加不規(guī)則機(jī)器人的障礙物碰撞邏輯。A*算法的搜索實(shí)質(zhì)上是對(duì)當(dāng)前柵格相鄰的柵格正前、正后、正左、正右、左前、左后、右前、右后進(jìn)行碰撞預(yù)判,如果相鄰柵格超出地圖邊界、相鄰柵格為障礙物區(qū)域或者相鄰柵格之前搜索過(guò)即相鄰柵格在關(guān)閉列表中,則添加該相鄰柵格進(jìn)關(guān)閉列表,其他情況則將相鄰柵格添加進(jìn)開(kāi)啟列表。增加不規(guī)則機(jī)器人的障礙物碰撞邏輯就在這一步添加,在加入開(kāi)啟列表或關(guān)閉列表前,額外再加一個(gè)條件(以鄰接?xùn)鸥駷橹行?,以目?biāo)車的方向和大小構(gòu)建下一步車的位置,判斷下一步該車是否會(huì)覆蓋到不可走狀態(tài)的柵格——即與障礙物不能碰撞),若滿足此額外條件,相鄰接?xùn)鸥窦尤腴_(kāi)啟列表,否則添加該相鄰柵格進(jìn)關(guān)閉列表。
在增加的不規(guī)則機(jī)器人的障礙物碰撞邏輯中,目標(biāo)車邊界柵格在左前、左后、右前、右后已經(jīng)不是一行或者一列,而是傾斜的,但是注意到左前、左后、右前、右后四個(gè)方向柵格傾斜的角度為45的奇數(shù)倍,依次將左前、左后、右前、右后四個(gè)方向用兩個(gè)循環(huán)來(lái)判斷長(zhǎng)和寬邊界;利用計(jì)算幾何的思路計(jì)算此時(shí)虛線矩形的四個(gè)邊角點(diǎn)a1、a2、a3和a4,每一個(gè)邊角點(diǎn)由車形機(jī)器人的幾何中心以一定的角度向外延伸一定的半徑計(jì)算得來(lái)。注意,代碼中對(duì)于目標(biāo)車越界情況進(jìn)行處理-即目標(biāo)車虛線矩形邊界覆蓋到了柵格地圖的外面,判定此時(shí)目標(biāo)車幾何中心所在柵格的相鄰柵格進(jìn)入關(guān)閉列表。
通過(guò)實(shí)際項(xiàng)目測(cè)試,可滿足車型機(jī)器人狹窄區(qū)域路徑規(guī)劃要求。
3針對(duì)不規(guī)則機(jī)器人路徑規(guī)劃的預(yù)處理算法
上述A*算法,增加了條件2的約束增加了算法的復(fù)雜性,延長(zhǎng)了算法計(jì)算周期。在實(shí)際項(xiàng)目中增加條件2的地圖預(yù)處理功能。即將條件2作為地圖柵格化的一個(gè)已知元素。在實(shí)時(shí)A*路徑規(guī)劃中降低了算法的計(jì)算周期。
本算法驗(yàn)證通過(guò)Windows操作系統(tǒng)的VisualStudio2010開(kāi)發(fā)平臺(tái)。算法主要分為3個(gè)功能模塊,地圖構(gòu)建模塊、地圖預(yù)處理模塊和主程序模塊。