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

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

0 引言

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

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

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

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

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

圖1 層次地圖模型

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

(1)

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

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

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

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

(2)

(3)

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

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

(4)

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)及結(jié)果分析

隨機(jī)生成50×50的柵格地圖，并初始化以下參數(shù)：設(shè)置螞蟻個(gè)數(shù)為50個(gè)，最大迭代次數(shù)為100，信息啟發(fā)式因子α=1，期望啟發(fā)式因子β=7，信息素常量Q=1，信息素?fù)]發(fā)因子ρ0=0.9。使用K-means算法將地圖分為15個(gè)區(qū)域，如圖4所示。躍層改進(jìn)蟻群算法的運(yùn)行過(guò)程如圖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)行實(shí)驗(yàn)，得到最優(yōu)路徑如圖7所示，最短路徑長(zhǎng)度曲線如圖8所示，實(shí)驗(yàn)參數(shù)如表1所示。

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

表1 實(shí)驗(yàn)參數(shù)表

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

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

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

4 結(jié)論

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