李梓遠(yuǎn)，黃衛(wèi)華,b,c，章 政,b,c，張子然，邊 琳

(武漢科技大學(xué)a.機器人與智能系統(tǒng)研究院；b.冶金自動化與檢測技術(shù)教育部工程研究中心；c.信息科學(xué)與工程學(xué)院，武漢 430081)

0 引言

路徑規(guī)劃是機器人實現(xiàn)自主移動的基礎(chǔ)。當(dāng)移動機器人處于大規(guī)模環(huán)境時，機器人從起點到目標(biāo)點完成一次完整無碰撞的路徑規(guī)劃過程中，易出現(xiàn)搜索空間大、規(guī)劃路徑拐點較多、能耗大等問題[1-3]。因此，有效降低搜索空間對于提升移動機器人的路徑規(guī)劃效率具有重要意義。

針對大規(guī)模環(huán)境下的地圖建模問題，趙健等[4]在多路況復(fù)雜環(huán)境下提出了代價地圖的構(gòu)建方法，將代價函數(shù)與柵格地圖融合，提高機器人運行的安全性并降低其能耗。岳偉韜等[5]提出了以準(zhǔn)確度與信息量為變量的代價函數(shù)來評估占據(jù)柵格地圖的精度，獲取最佳柵格大小以提升地圖準(zhǔn)確度。郭書杰等[6]提出了一種關(guān)鍵點路徑規(guī)劃方法，將整個路徑規(guī)劃切分成多個較短的子路徑規(guī)劃，從而降低問題規(guī)模，提高規(guī)劃效率。ZAFAR等[7]使用HPA*分層搜索算法，將復(fù)雜環(huán)境分為多個抽象層次，逐層搜索后得到完整路徑，通過地圖的層次抽象表達(dá)來減少計算負(fù)荷量。對于路徑搜索策略而言，蟻群算法由于其正反饋、分布式計算能力、魯棒性等優(yōu)點被廣泛應(yīng)用于復(fù)雜大環(huán)境路徑規(guī)劃并取得了較好的效果。江明等[8]針對蟻群算法在復(fù)雜環(huán)境下收斂速度慢且易陷入局部最優(yōu)值的問題，依據(jù)起始點和目標(biāo)點位置信息選擇全局有利區(qū)域增加初始信息素濃度，提升算法全局性。肖金壯等[9]通過動態(tài)更新不同螞蟻路徑上的信息素并引入距離函數(shù)和方向函數(shù)作為啟發(fā)因子，加快了蟻群算法在大規(guī)模復(fù)雜環(huán)境中的搜索效率。

基于上述分析，針對大規(guī)模環(huán)境中路徑規(guī)劃效率的問題，傳統(tǒng)蟻群算法缺乏地圖信息的引導(dǎo)，搜索時間長且規(guī)劃所得路徑平滑度低。本文采用K-means算法對地圖進(jìn)行預(yù)處理，在實現(xiàn)層次環(huán)境建模的基礎(chǔ)上，采用近處精細(xì)遠(yuǎn)處粗略的路徑搜索策略來提升規(guī)劃效率，并將機器人運動方向引入蟻群路徑規(guī)劃中，有效減小路徑的曲折度。實驗結(jié)果表明，本文所設(shè)計的路徑規(guī)劃優(yōu)化算法具有搜索空間小、速度快、路徑轉(zhuǎn)折度小等特點。

1 層次地圖模型及路徑搜索策略

對于機器人路徑規(guī)劃過程而言，一次路徑規(guī)劃后得到一條起點至目標(biāo)點的完整路徑并不是必要的[10-12]，在地圖量化信息的引導(dǎo)下得到具有方向性的非完整路徑同樣能引導(dǎo)移動機器人尋優(yōu)。鑒于此，本文基于非完整路徑規(guī)劃策略，構(gòu)建了一種層次環(huán)境地圖模型，如圖1所示。其中，A表示規(guī)劃任務(wù)的起點，B表示目標(biāo)點，黑色區(qū)域表示障礙物，環(huán)境模型分為底層地圖S0和高層地圖S1。

圖1 層次地圖模型

由于對表征區(qū)域的高層節(jié)點進(jìn)行檢索可以降低搜索空間，因此本文設(shè)計了基于層次地圖模型的路徑搜索策略：對當(dāng)前節(jié)點在底層地圖中所處分區(qū)進(jìn)行精細(xì)搜索，所處分區(qū)外的節(jié)點則通過搜索高層節(jié)點進(jìn)行粗略搜索，以此得到一條由S0內(nèi)詳細(xì)路徑、S1內(nèi)粗略路徑以及S0至S1躍層路徑組成的非完整路徑。因此由S0至S1的躍層是實現(xiàn)層次地圖中路徑搜索及減小搜索空間的關(guān)鍵，定義層次地圖模型中路徑由底層地圖S0向高層地圖S1躍層的條件為：當(dāng)前位置節(jié)點的父節(jié)點不為空，且子節(jié)點與當(dāng)前節(jié)點位于底層地圖內(nèi)的不同分區(qū)。如式(1)所示：

(1)

2 改進(jìn)蟻群路徑規(guī)劃算法設(shè)計

針對蟻群路徑規(guī)劃算法在大規(guī)模環(huán)境中收斂速度慢、易陷入局部最優(yōu)等問題，本文將所設(shè)計的基于層次地圖模型的路徑搜索策略引入蟻群算法的狀態(tài)轉(zhuǎn)移中，減小算法的搜索空間，并在啟發(fā)函數(shù)中設(shè)置方向獎懲函數(shù)來改善路徑平滑度。

2.1 分層環(huán)境地圖下蟻群狀態(tài)轉(zhuǎn)移策略的設(shè)計

對于在底層地圖S0中進(jìn)行路徑搜索的螞蟻，直接采用傳統(tǒng)狀態(tài)轉(zhuǎn)移公式進(jìn)行計算?？紤]到傳統(tǒng)狀態(tài)轉(zhuǎn)移策略依據(jù)輪盤賭原則來選出下一行進(jìn)節(jié)點，因此搜索范圍較大。在分層環(huán)境地圖下，當(dāng)蟻群躍層至高層地圖S1中進(jìn)行節(jié)點選擇時，為了提高蟻群算法的收斂速度以及尋路的精確度，本文將環(huán)境信息與當(dāng)前位置信息融入狀態(tài)轉(zhuǎn)移函數(shù)中，設(shè)計了基于層次地圖的蟻群狀態(tài)轉(zhuǎn)移策略：

(2)

(3)

2.2 啟發(fā)函數(shù)的設(shè)計

在路徑規(guī)劃過程中，減小蟻群搜索方向與前進(jìn)方向的誤差，可有效降低機器人由于轉(zhuǎn)角過大導(dǎo)致運動時間增加的問題。為了加強螞蟻尋路時對路徑搜索方向的判斷力，本節(jié)設(shè)計了一種獎懲函數(shù)，其表達(dá)式為：

(4)

式中，Rmax為獎勵最大值；θi和θj分別為當(dāng)前節(jié)點和下一節(jié)點的航向角；ΔR為獎勵差值。

將獎懲函數(shù)引入啟發(fā)函數(shù)以增強方向引導(dǎo)性，由此定義一種具有方向獎懲因子的啟發(fā)函數(shù)：

(5)

式中，dij為節(jié)點i與節(jié)點j之間的歐氏距離；γ為獎勵因子，0<γ<1，其大小決定獎懲函數(shù)對啟發(fā)函數(shù)的影響程度。

由于蟻群在前行方向留下的信息素濃度更高，本文去除了八方向搜索中東南、西南方向的子節(jié)點，使螞蟻僅能選擇剩余6個方向的子節(jié)點，因此，將獎懲函數(shù)引入后的6方向搜索方式如圖2所示，前向方向具有最大獎勵值Rmax，當(dāng)機器人轉(zhuǎn)向時，其獎勵值按45°依次遞減ΔR。

圖2 方向獎懲函數(shù)示意圖

優(yōu)化后的啟發(fā)函數(shù)融入了機器人的行進(jìn)方向信息，使機器人傾向于前行以獲得轉(zhuǎn)折度較小的路徑，相比傳統(tǒng)啟發(fā)函數(shù)對路徑平滑性方面的考慮有明顯的提升。

2.3 改進(jìn)蟻群算法步驟

由上文可知，為提升大規(guī)模環(huán)境中路徑規(guī)劃的效率，本文使用改進(jìn)后的蟻群算法進(jìn)行路徑規(guī)劃，其執(zhí)行步驟為：

步驟1：地圖預(yù)處理。環(huán)境地圖運用柵格法處理后，使用K-means算法對柵格地圖障礙物聚類分區(qū)，并提取區(qū)域內(nèi)可行節(jié)點得到高層地圖。

步驟2：初始化蟻群算法的以下參數(shù)：種群規(guī)模m、信息素因子α、啟發(fā)式因子β、信息素?fù)]發(fā)因子ρ、信息素常量Q和最大迭代次數(shù)Zmax(Zmax=Z1+Z2+…+Zk)，設(shè)定的迭代次數(shù)ω，將迭代次數(shù)置為0，清空禁忌表。

步驟3：節(jié)點選擇。螞蟻在起點A處，按照式(2)及式(5)計算下一步到達(dá)的節(jié)點。

步驟5：迭代更新。當(dāng)m只螞蟻完成一次尋路后對其信息素進(jìn)行更新。進(jìn)行Z1次迭代后，得到一條當(dāng)前區(qū)域內(nèi)詳細(xì)，遠(yuǎn)處區(qū)域內(nèi)粗略的路徑。

步驟6：由粗略路徑規(guī)劃至詳細(xì)路徑。將躍層處節(jié)點i作為新起點，從節(jié)點i處開始迭代Z2次，再一次得到當(dāng)前區(qū)域的詳細(xì)路徑及遠(yuǎn)處區(qū)域的粗略路徑。

步驟7：得到最后一個區(qū)域的詳細(xì)路徑并整合出從起點至目標(biāo)點的詳細(xì)路徑。

所設(shè)計改進(jìn)的蟻群算法流程圖如圖3所示。

圖3 改進(jìn)蟻群算法流程圖

3 仿真實驗及結(jié)果分析

隨機生成50×50的柵格地圖，并初始化以下參數(shù)：設(shè)置螞蟻個數(shù)為50個，最大迭代次數(shù)為100，信息啟發(fā)式因子α=1，期望啟發(fā)式因子β=7，信息素常量Q=1，信息素?fù)]發(fā)因子ρ0=0.9。使用K-means算法將地圖分為15個區(qū)域，如圖4所示。躍層改進(jìn)蟻群算法的運行過程如圖5所示，其所得最優(yōu)路徑如圖6所示。

圖4 K-means聚類分區(qū)地圖

(a) 躍層改進(jìn)蟻群算法第一階段 (b) 躍層改進(jìn)蟻群算法第二階段

圖6 躍層改進(jìn)蟻群算法最優(yōu)路徑

在相同環(huán)境下，分別采用傳統(tǒng)蟻群算法、地圖分區(qū)預(yù)處理的改進(jìn)蟻群算法與僅躍層的蟻群算法進(jìn)行實驗，得到最優(yōu)路徑如圖7所示，最短路徑長度曲線如圖8所示，實驗參數(shù)如表1所示。

圖7 三種算法最優(yōu)路徑對比圖 圖8 最短路徑長度曲線圖

表1 實驗參數(shù)表

圖4中路徑規(guī)劃的起點與目標(biāo)點分別位于區(qū)域1與區(qū)域15。圖5所示的規(guī)劃過程中，圖5a為在區(qū)域1中規(guī)劃出的精確路徑并確定后續(xù)搜索區(qū)域為2→6→11→15，圖5b為以躍層節(jié)點為起點，在區(qū)域2中進(jìn)行精細(xì)搜索，并確定后續(xù)搜索區(qū)域為6→11→15，循環(huán)此過程得到圖5c與圖5d內(nèi)路徑，最后得到目標(biāo)點所在區(qū)域15內(nèi)的詳細(xì)路徑。將圖5a至圖5d的詳細(xì)路徑整合即為圖6所示完整路徑。

對比圖6和圖7傳統(tǒng)蟻群算法隨著搜索范圍增大，最優(yōu)路徑上的拐點增多；地圖分區(qū)預(yù)處理蟻群算法利用分區(qū)預(yù)處理后的區(qū)域量化信息對臨近區(qū)域搜索，減小了部分區(qū)域路徑的曲折度；躍層蟻群算法利用躍層機制降低了搜索空間并使算法跳出局部最優(yōu)；圖6躍層改進(jìn)蟻群算法在躍層基礎(chǔ)上，優(yōu)化后的啟發(fā)函數(shù)進(jìn)一步降低了搜索時間并使路徑更平滑。

由表1可知，與無改進(jìn)蟻群算法相比，本文算法利用高層粗略路徑對整體尋優(yōu)進(jìn)行引導(dǎo)，機器人的移動時間減少了53.1%；改進(jìn)啟發(fā)函數(shù)使最優(yōu)路徑上的拐點減少，轉(zhuǎn)彎次數(shù)減少了65.5%；高層路徑增強了算法跳出局部最優(yōu)解的能力，使迭代次數(shù)減少了54.3%。與地圖分區(qū)預(yù)處理的蟻群算法相比，本文算法的機器人的移動時間減少31.5%，轉(zhuǎn)彎的次數(shù)減少了41.1%，迭代次數(shù)減少了42.4%。與躍層蟻群算法相比，本文算法的機器人移動時間減少了9.4%，轉(zhuǎn)彎次數(shù)減少了23.1%，迭代次數(shù)減少了12.5%，綜合性能更優(yōu)。實驗表明，在高層路徑引導(dǎo)下進(jìn)行規(guī)劃的蟻群算法通過降低螞蟻的搜索范圍，提高了復(fù)雜環(huán)境下全局尋優(yōu)的能力。

4 結(jié)論

針對大規(guī)模環(huán)境下搜索空間增大造成規(guī)劃效率降低等問題，設(shè)計了基于層次地圖模型的改進(jìn)蟻群算法。將層次地圖模型中的路徑搜索策略引入蟻群算法的狀態(tài)轉(zhuǎn)移策略，同時設(shè)計了基于方向獎懲的啟發(fā)函數(shù)，提高蟻群算法的路徑規(guī)劃效率。實驗結(jié)果表明，本文基于層次地圖模型的改進(jìn)蟻群算法相較于傳統(tǒng)蟻群算法，對地圖區(qū)域及層次的劃分增強了算法跳出局部最優(yōu)的能力，將方向獎懲函數(shù)引入啟發(fā)函數(shù)，解決了路徑轉(zhuǎn)折率大的問題。本文算法具有更短的路徑規(guī)劃時間、更短路徑長度及更少拐點，綜合性能更優(yōu)。