王 玉, 沈丹峰, 李耀杰, 李靖宇

(西安工程大學(xué) 機(jī)電工程學(xué)院，陜西 西安 710048)

0 引 言

自動導(dǎo)引小車(automated guided vehicle，AGV)研究的主要問題之一，是基于已知信息規(guī)劃環(huán)境中具有許多障礙的最優(yōu)路徑。即從起點(diǎn)到目的地點(diǎn)而不發(fā)生碰撞，并且以最快的速度和最短的路徑到達(dá)。該研究中廣泛使用的方法有勢場法[1]、柵格法[2]、動態(tài)算法[3-5]、蟻群算法[6-8]、神經(jīng)網(wǎng)絡(luò)算法[9-10]等。勢場法有助于下層的實(shí)時控制，結(jié)構(gòu)簡單但很容易陷入局部的優(yōu)的死胡同，對全局的搜索不利；動態(tài)算法計(jì)算量大、收斂速度慢，效率低。目前，神經(jīng)網(wǎng)絡(luò)成為了比較流行的優(yōu)化方法。該方法易于使用硬件實(shí)現(xiàn)，但可靠性和優(yōu)化性能較差，并且難以解決局部最優(yōu)解問題。盡管傳統(tǒng)的蟻群算法收斂速度慢，也存在死鎖的問題，但它易于并行實(shí)現(xiàn)、搜索效率高、魯棒性強(qiáng)，可以廣泛地用以各種復(fù)雜環(huán)境下的路徑規(guī)劃中。

目前，許多學(xué)者提出了不同的方式改善蟻群算法的弊端：NAZARAHARI等提出了遺傳算法規(guī)劃連續(xù)環(huán)境中多個機(jī)器人的路徑，并改進(jìn)了原有遺傳算法的啟發(fā)式功能，但是當(dāng)觸碰到障礙物時，仍然會出現(xiàn)死鎖現(xiàn)象，效率低下[11]； ZHU等將人工勢場法與蟻群算法相結(jié)合，引入誘發(fā)啟發(fā)式因素，并動態(tài)調(diào)整了算法的狀態(tài)轉(zhuǎn)移規(guī)則，因而具有更高的全局搜索能力和更快的收斂進(jìn)度[12]；OMRAN等改進(jìn)連續(xù)蟻群優(yōu)化問題，優(yōu)化了開發(fā)和尋找蟻群的機(jī)制，收斂速度有所提高[13]；馬軍等提出了融合蟻群-A*算法的路徑規(guī)劃方法，雖然改進(jìn)了啟發(fā)式函數(shù)和信息素更新方式，但蟻群算法早期搜索效率低、收斂緩慢的問題仍然不能有效地解決[14]。

針對上述問題，本文提出一種融合跳點(diǎn)搜索(JPS)的新方式，并且從一開始即建立了2組蟻群，在起點(diǎn)和目的地的2個方向上同時執(zhí)行路徑搜索，從而減少了算法運(yùn)行期間需要計(jì)算的節(jié)點(diǎn)數(shù)量，解決了螞蟻在遇到“凹”型障礙物時撤退或死亡，或產(chǎn)生一些無效信息素誤導(dǎo)搜索過程，從而加快了路徑規(guī)劃的收斂速度，降低AGV運(yùn)行時間和能量損耗，顯著提高了路徑尋優(yōu)的效率。

1 環(huán)境建模

圖 1 AGV運(yùn)行方向Fig.1 Direction of AGV movement

直角坐標(biāo)與柵格序號的轉(zhuǎn)換關(guān)系為

(1)

式中：Sx為柵格的序號；g為每行或每列的柵格個數(shù)；mod(Sx,g)為Sx/g的取余函數(shù)；ceil(Sx/g)為求取大于或者等于Sx/g的最小整數(shù)函數(shù)?？梢缘玫紸GV在當(dāng)前柵格地圖中的實(shí)際坐標(biāo)。將地圖信息存在二維矩陣M=(mij)中，其中：

(2)

為了驗(yàn)證改進(jìn)的算法在不同規(guī)模復(fù)雜環(huán)境下路徑規(guī)劃的有效性與通用性，以及是否具有良好的全局搜索能力，采用柵格法構(gòu)造了2個不同的仿真地圖，如圖2所示。

(a) 環(huán)境1柵格地圖

(b) 環(huán)境2柵格地圖圖 2 柵格地圖Fig.2 Grid map

圖2中環(huán)境1和環(huán)境2分別為20×20和30×30的柵格地圖，將S設(shè)置為AGV的起始點(diǎn)，E為目標(biāo)點(diǎn)，在地圖上，有一些障礙物呈現(xiàn)“凹”型狀，障礙物的其他部分被設(shè)置成以近似隨機(jī)分布的方式排列，沒有規(guī)則和順序。

2 融合JPS的蟻群算法

2.1 傳統(tǒng)蟻群算法原理

螞蟻尋找食物的過程中會釋放一種稱之為信息素的激素在走過的路徑上，在一定范圍內(nèi)，后續(xù)的其他螞蟻都能夠感知到這種信息素。當(dāng)經(jīng)過的路徑上有源源不斷的螞蟻時，信息素將繼續(xù)在此路徑上積聚，隨后的螞蟻選擇同一路徑的可能性將繼續(xù)增加。該路徑規(guī)劃被視為是一組螞蟻經(jīng)過多次迭代尋找食物的過程，并最終將找到一條無碰撞且最優(yōu)的路徑[15-17]。

蟻群算法狀態(tài)轉(zhuǎn)移概率如下：

(3)

(4)

式中：dij為螞蟻從柵格i到下一個柵格j的歐幾里得距離；Ix、Iy分別為當(dāng)前節(jié)點(diǎn)的橫坐標(biāo)與縱坐標(biāo)。

整個循環(huán)過程中螞蟻會不斷地釋放信息素，同時先前螞蟻釋放的信息素也會不斷消失。循環(huán)完成后，需要對信息素實(shí)時更新，更新方式為

(5)

當(dāng)路徑上所有的信息素被更新后，表示此次路徑已經(jīng)搜索結(jié)束,蟻群已經(jīng)準(zhǔn)備好開始下一輪的路徑搜索；當(dāng)?shù)_(dá)到設(shè)定的次數(shù)后，蟻群將從所尋找到的路徑中選出一條最佳路徑。

2.2 算法改進(jìn)

使用傳統(tǒng)蟻群算法盡管可以求解最優(yōu)路徑，但需要把螞蟻全部放置在起始點(diǎn)，然后搜索到目標(biāo)點(diǎn)，起始路徑是大致相同的，缺乏全局的搜索能力，且均勻分配的信息素濃度會導(dǎo)致蟻群初期盲目搜索，一定程度上降低了算法的搜索效率。因此，本文在蟻群算法的基礎(chǔ)上，融合了跳點(diǎn)搜索(JPS)算法，改進(jìn)了蟻群算法的啟發(fā)函數(shù)和信息素更新公式，并放置2組蟻群從起始點(diǎn)和目標(biāo)點(diǎn)，同時執(zhí)行雙向搜索規(guī)劃最優(yōu)路徑，使其進(jìn)入“凹”型障礙物中自鎖時可以進(jìn)行局部規(guī)劃，從而提高算法的搜索效率和速度。

2.2.1 啟發(fā)函數(shù)的改進(jìn) 在JPS算法的路徑搜索中，丟棄了大量不需要計(jì)算的節(jié)點(diǎn)，并留下代表性節(jié)點(diǎn)，這些剩余的節(jié)點(diǎn)被稱為跳點(diǎn)[18-20]。在過濾跳點(diǎn)時，首先展開所有的節(jié)點(diǎn)進(jìn)行預(yù)處理，在當(dāng)下節(jié)點(diǎn)周圍找到8個相鄰跳點(diǎn)并放置到open表中。再從周圍的鄰居節(jié)點(diǎn)集合中挑選出那些不需要計(jì)算的節(jié)點(diǎn)，將這些節(jié)點(diǎn)全部裁剪掉放置到close表中。然后展開這些點(diǎn)，當(dāng)搜索到目標(biāo)點(diǎn)時，連接所有跳點(diǎn)就是一條完整的全局路徑。跳點(diǎn)搜索(JPS)尋優(yōu)路徑如圖3所示。

圖 3 JPS算法路徑尋優(yōu)Fig.3 Path optimization of JPS algorithm

如此改進(jìn)，對open和close列表減少了大量的運(yùn)算，很大程度上提高了尋優(yōu)效率，并節(jié)省了大量的AGV路徑規(guī)劃時間。

JPS的評價(jià)函數(shù)表達(dá)式為

F(n)=G(n)+H(n)

(6)

式中：F(n)為要展開點(diǎn)的代價(jià)函數(shù)；G(n)為初始點(diǎn)到n節(jié)點(diǎn)的實(shí)際成本代價(jià)；H(n)為節(jié)點(diǎn)n至目標(biāo)點(diǎn)的預(yù)算成本代價(jià)。

傳統(tǒng)蟻群算法的啟發(fā)函數(shù)在選擇下一個柵格時,會導(dǎo)致螞蟻更加傾向于選擇方向?yàn)檎臇鸥?，且沒有考慮到最終柵格的位置。因此,使用曼哈頓距離作為雙向搜索的預(yù)算代價(jià)函數(shù)。改進(jìn)后的啟發(fā)式函數(shù)為

(7)

式中：Hij為當(dāng)前節(jié)點(diǎn)距離起始點(diǎn)或目標(biāo)點(diǎn)的幾何距離；Ix和Iy為當(dāng)前節(jié)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)；Ex和Ey為目標(biāo)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)；Sx和Sy為起始點(diǎn)的橫坐標(biāo)和縱坐標(biāo)。

2組螞蟻在它們各自的目標(biāo)點(diǎn)上執(zhí)行雙向路徑搜索，當(dāng)它們找到一個公共的節(jié)點(diǎn)時，該節(jié)點(diǎn)內(nèi)的信息素濃度就會加倍。找到的3個或更多的公共節(jié)點(diǎn)連接起來即產(chǎn)生一條新的路徑，之后2組螞蟻繼續(xù)向各自的目標(biāo)點(diǎn)移動。數(shù)學(xué)表達(dá)式為

HSE=|Ex-Sx|+|Ey-Sy|

(8)

式中：HSE表示2個目標(biāo)點(diǎn)之間的距離。

2.2.2 信息素更新公式的改進(jìn) 隨著信息素在同一路徑上的積累，傳統(tǒng)的蟻群算法選擇路徑時，后續(xù)的螞蟻將擁有大量的盲路徑,導(dǎo)致在經(jīng)過一定數(shù)量的迭代后，螞蟻發(fā)現(xiàn)的是非最優(yōu)路徑。在當(dāng)前情況下，尋找到的路徑在實(shí)踐中意義就不大了。每一輪路徑搜索過后蟻群的信息素就會被更新，設(shè)定參數(shù)ρ以指示信息素的揮發(fā)程度，改進(jìn)后的信息素更新式為

τij(t+1)=(1-ρ)τij(t)+2Δτij(t),0<ρ<1

(9)

(10)

式中：Δτij(t)為路徑信息素增加量；HSE為路徑長度；Q為信息素濃度增強(qiáng)因子。

2.3 改進(jìn)算法流程圖

將改進(jìn)的算法用于AGV路徑規(guī)劃中，算法流程圖如圖4所示。

圖 4 改進(jìn)算法流程圖Fig.4 Flow chart of improved algorithm

將參數(shù)初始化，設(shè)置初始信息素在節(jié)點(diǎn)間的濃度、信息啟發(fā)系數(shù)α、期望啟發(fā)系數(shù)β、信息素?fù)]發(fā)系數(shù)ρ以及迭代次數(shù)N；使用柵格法創(chuàng)建指定大小的地圖模型，并將障礙物存儲在相應(yīng)的網(wǎng)格中；將蟻群平均分為2組，分別放入起始點(diǎn)和目標(biāo)點(diǎn)，使用JPS算法生成初始路徑；根據(jù)式(5)更新對應(yīng)路徑的初始信息素含量，直到2組蟻群相遇有共同的節(jié)點(diǎn)并都到達(dá)目標(biāo)點(diǎn)；用改進(jìn)的公式更新上一代螞蟻留下的信息素，當(dāng)滿足設(shè)定迭代次數(shù)時，結(jié)束算法，輸出路徑，并繪制出算法收斂曲線。

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

為了驗(yàn)證改進(jìn)后算法的有效性與通用性，選擇運(yùn)行環(huán)境Windows10和8 GB RAM內(nèi)存的PC機(jī)，使用CPU為2.60 MHz的處理器，在MATLAB2019a軟件上進(jìn)行2組不同復(fù)雜環(huán)境下的仿真實(shí)驗(yàn)。設(shè)置算法的初始參數(shù)：2組螞蟻的種群數(shù)量m=20,α=2,N=200,β=5,ρ=0.5,Q=2; 2種環(huán)境地圖分別模擬100次。

3.1 環(huán)境1

在20×20的環(huán)境1柵格地圖中進(jìn)行仿真實(shí)驗(yàn)。本文算法的最優(yōu)路徑如圖5(a)；傳統(tǒng)蟻群算法的最優(yōu)路徑如圖5(b)；傳統(tǒng)算法與改進(jìn)后的算法最小路徑長度收斂曲線對比如圖5(c)。對比搜索路徑可以看出：傳統(tǒng)蟻群算法缺乏前期目標(biāo)點(diǎn)的路徑規(guī)劃，具有盲目性，導(dǎo)致后期的路徑信息素積累過高，會出現(xiàn)不必要的拐點(diǎn)；而本文算法有效避免路徑直角拐點(diǎn)的出現(xiàn)，降低了AGV的能量消耗，在路徑上無多余曲折的拐點(diǎn)且更加平滑，收斂速度更快。

(a) 改進(jìn)算法最優(yōu)路徑 (b) 傳統(tǒng)算法最優(yōu)路徑 (c) 收斂曲線對比圖 5 環(huán)境1中實(shí)驗(yàn)結(jié)果比較Fig.5 Comparison of experimental results in environment 1

3.2 環(huán)境2

在30×30的環(huán)境2柵格地圖上進(jìn)行模擬實(shí)驗(yàn)。圖6(a)和圖6(b)分別顯示了使用改進(jìn)算法與傳統(tǒng)算法尋找到的最優(yōu)路徑，圖6(c)為傳統(tǒng)算法與改進(jìn)后的算法最小路徑長度收斂曲線的比較。在更為復(fù)雜柵格環(huán)境中設(shè)置了更多“凹”型障礙物，對傳統(tǒng)算法來說，由于沒有事先規(guī)劃過路徑，導(dǎo)致后期螞蟻重復(fù)前期走過的路徑，信息素積累過高，出現(xiàn)了大量多余的拐點(diǎn)，在實(shí)際搜索中增加了能量的損耗，見圖6(b);改進(jìn)后的算法避免了路徑上信息素的過度積累，以找到最優(yōu)路徑為目標(biāo)，規(guī)劃出的路徑依然比傳統(tǒng)算法的更加平滑，并且轉(zhuǎn)折點(diǎn)的數(shù)量也少了很多，見圖6(a)；盡管改進(jìn)算法的收斂曲線在剛開始會有波動，但收斂速度比傳統(tǒng)的更快，迭代次數(shù)也遠(yuǎn)遠(yuǎn)小于傳統(tǒng)算法的迭代次數(shù)，具有良好的全局搜索能力，見圖6(c)。

(a) 改進(jìn)算法最優(yōu)路徑 (b) 傳統(tǒng)算法最優(yōu)路徑 (c) 收斂曲線對比圖 6 環(huán)境2中實(shí)驗(yàn)結(jié)果比較Fig.6 Comparison of experimental results in environment 2

改進(jìn)蟻群算法和傳統(tǒng)蟻群算法在環(huán)境1與環(huán)境2的仿真實(shí)驗(yàn)結(jié)果對比，如表1所示。

表 1 仿真結(jié)果對比Tab.1 Comparison of simulation results

由表1可知，在20×20和30×30的柵格地圖環(huán)境中，使用相同數(shù)量的螞蟻種群和迭代次數(shù)，改進(jìn)后的算法能獲取更短的路徑，具有更好的收斂速度，拐點(diǎn)數(shù)目更少，路徑更為平滑。改進(jìn)蟻群算法在搜索時間比傳統(tǒng)蟻群算法減少了30%，迭代次數(shù)降低了33.3%，最小路徑長度上縮短了4～5 m。對于實(shí)際的AGV來說，有效地降低了能量與時間的消耗。改進(jìn)后的算法比傳統(tǒng)蟻群算法在不同復(fù)雜的環(huán)境地圖中均有較好的搜索效果。

4 結(jié) 語

針對現(xiàn)有的蟻群算法收斂緩慢，無法滿足AGV的最優(yōu)路徑規(guī)劃問題，本文在傳統(tǒng)算法中融入跳點(diǎn)搜索算法，使待擴(kuò)展點(diǎn)的數(shù)量大幅度的減少，降低了搜索盲目性和計(jì)算代價(jià)。在此基礎(chǔ)上，將評估功能加入到啟發(fā)式函數(shù)中，設(shè)置2組蟻群，分別從起始點(diǎn)和目標(biāo)點(diǎn)執(zhí)行雙向搜索，并更新信息素方式，使蟻群的全局搜索能力有了很大程度上的提高。前期算法的收斂速度得以提高，避免出現(xiàn)陷入“凹”型障礙物中而直接輸出路徑，導(dǎo)致局部最優(yōu)解的情況。Matlab的仿真結(jié)果證明，當(dāng)環(huán)境變得相對復(fù)雜時，本文算法在尋找到最優(yōu)路徑的同時，計(jì)算路徑花費(fèi)的時間要比傳統(tǒng)算法更少，具有更快的收斂速度，更少的拐點(diǎn)，路徑優(yōu)化能力更好。證明本文算法在不同的復(fù)雜環(huán)境中AGV路徑規(guī)劃算法的優(yōu)越性與有效性。