趙 江，王曉博，郝崇清，劉慧賢，薛文艷，王昭雷

1.河北科技大學(xué) 電氣工程學(xué)院，石家莊 050018

2.國網(wǎng)河北省電力有限公司，石家莊 050051

1 引言

移動(dòng)機(jī)器人逐漸代替人進(jìn)行工作，并具有高精度和高效率的優(yōu)點(diǎn)[1]。機(jī)器人綜合了機(jī)器視覺、機(jī)器人導(dǎo)航與定位、模式識別、多傳感器融合和人機(jī)接口等多種研究領(lǐng)域[2]。自動(dòng)導(dǎo)引車輛（Automated Guided Vehicle，AGV）作為一種新型的智能移動(dòng)機(jī)器人，具有自動(dòng)化程度高、靈活性強(qiáng)、抗干擾能力強(qiáng)、安全性好等優(yōu)點(diǎn)。路徑規(guī)劃作為AGV 運(yùn)動(dòng)中的關(guān)鍵問題之一，成為目前的研究熱點(diǎn)。根據(jù)已知的環(huán)境信息，路徑規(guī)劃問題可分為兩類：一類是全局路徑規(guī)劃問題[3]，即在規(guī)劃之前已經(jīng)知道所有的環(huán)境信息。另一類是局部路徑規(guī)劃問題[4]，機(jī)器人必須自己收集環(huán)境信息。本文研究的是全局路徑規(guī)劃問題。

全局路徑規(guī)劃問題有兩種常用方法：一種是窮舉搜索方法，如 Dijkstra[5]、A*算法[6]和圖論[7]。該類方法搜索的是整個(gè)空間，這意味著它一定可以找到最優(yōu)解，但執(zhí)行時(shí)間會(huì)隨著問題的大小成指數(shù)增長。為解決上述問題，Akshay 等在文獻(xiàn)[1]中提出了機(jī)器人路徑規(guī)劃的時(shí)效A*算法，它不確定每個(gè)節(jié)點(diǎn)的啟發(fā)式函數(shù)值，只在碰撞階段之前確定該值，從而縮短了A*算法的執(zhí)行時(shí)間。Song等[8]認(rèn)為A*算法僅限于生成分段線性路徑，既不平滑也不連續(xù)，使得節(jié)點(diǎn)過多不利于智能體的運(yùn)行，為此提出了一種改進(jìn)的基于路徑點(diǎn)的A*算法，來平滑A*算法規(guī)劃出的路徑，減少不必要的節(jié)點(diǎn)，使路徑更加連續(xù)，其本質(zhì)是在規(guī)劃出路徑后再對路徑進(jìn)行平滑處理，然而在進(jìn)行路徑規(guī)劃時(shí)，往往會(huì)增加算法的計(jì)算量，影響算法的實(shí)時(shí)性。

另一種解決全局路徑規(guī)劃的方法是利用啟發(fā)式算法，它是解決優(yōu)化問題的一種常用方法。由于路徑應(yīng)該是無碰撞的，并且應(yīng)該滿足一組優(yōu)化準(zhǔn)則，因此路徑規(guī)劃也被認(rèn)為是優(yōu)化問題。常用的啟發(fā)式算法有禁忌搜索法[9]、蟻群算法[10]、遺傳算法[11]、粒子群算法[12]等。但這些算法容易陷入局部最優(yōu)，且計(jì)算量較大。為此，Mo等[13]將生物地理學(xué)與粒子群算法相結(jié)合，增加了種群的多樣性，避免了局部最優(yōu)；Lee等[14]改變了遺傳算法初始種群的生成方式，縮短了尋找最優(yōu)解所需的時(shí)間，加快了算法的收斂速度；Yakoubi 等[15]考慮到轉(zhuǎn)彎次數(shù)對智能體的影響，利用遺傳算法規(guī)劃出了一條路徑較短、轉(zhuǎn)彎次數(shù)較少的路徑，并說明了這樣的路徑更有助于智能體的高效運(yùn)行。

蟻群優(yōu)化算法（Ant Colony Optimization，ACO）是一種經(jīng)典的仿生最優(yōu)路徑規(guī)劃算法，具有易于與其他算法融合、易于分布式并行計(jì)算、全局優(yōu)化性能好等優(yōu)點(diǎn)[16]。已有的研究結(jié)果表明，蟻群算法在求解復(fù)雜優(yōu)化問題，尤其是離散優(yōu)化問題方面具有一定的優(yōu)勢。王曉燕等[17]結(jié)合人工勢場法與蟻群算法，將人工勢場法求得的初始路徑與節(jié)點(diǎn)間的距離綜合構(gòu)成新的啟發(fā)信息，并引入啟發(fā)信息遞減系數(shù)，避免了因啟發(fā)信息誤導(dǎo)而造成的局部最優(yōu)問題。Lee[18]提出了一種基于異構(gòu)螞蟻的路徑規(guī)劃方法，通過改進(jìn)螞蟻的轉(zhuǎn)移概率函數(shù)和信息素更新規(guī)則來直接找到一個(gè)節(jié)點(diǎn)較少的最佳路徑，無需進(jìn)行后續(xù)的平滑處理。

規(guī)劃節(jié)點(diǎn)，即在路徑規(guī)劃過程中算法所需規(guī)劃的節(jié)點(diǎn)，傳統(tǒng)的路徑規(guī)劃方法存在著規(guī)劃節(jié)點(diǎn)過多的問題。節(jié)點(diǎn)可以分為換向節(jié)點(diǎn)和非換向節(jié)點(diǎn)。AGV在實(shí)際運(yùn)行中，由于所規(guī)劃的路徑通常是分段線性路徑，AGV必須停在每個(gè)換向節(jié)點(diǎn)，根據(jù)下一段路徑改變其方向，然后再重新啟動(dòng)[19]，因此換向節(jié)點(diǎn)的多少對提高AGV 的運(yùn)行效率、減少AGV 的磨損起著重要作用。而當(dāng)非換向節(jié)點(diǎn)過多時(shí)，由于在每一個(gè)節(jié)點(diǎn)處都要對其要到達(dá)的節(jié)點(diǎn)重新進(jìn)行計(jì)算，算法的計(jì)算量會(huì)過大，減少路徑規(guī)劃時(shí)非換向節(jié)點(diǎn)的數(shù)目，可以縮小搜索范圍，提高搜索效率。

然而，上述文獻(xiàn)雖然考慮了節(jié)點(diǎn)過多對算法計(jì)算量和AGV 運(yùn)行效率的影響，但是其改進(jìn)方法往往是對一般算法規(guī)劃出路徑后再對路徑進(jìn)行平滑處理，這樣會(huì)使路徑規(guī)劃的過程相對繁瑣，不利于使用。為此，卜新蘋等[20]利用四叉樹法對傳統(tǒng)的均勻柵格圖進(jìn)行分割，重新確定柵格之間的連接關(guān)系，減少柵格數(shù)目。結(jié)果表明，減少柵格點(diǎn)能在不影響求解質(zhì)量的同時(shí)，縮小搜索范圍，從而提高了算法的收斂速度，減少了規(guī)劃出的路徑中節(jié)點(diǎn)的數(shù)量。Han[21]提出了提取臨界障礙物和周圍點(diǎn)集的方法，該方法根據(jù)障礙物對路徑規(guī)劃的重要程度，找到相對重要的障礙物，并在環(huán)境中找到包含這些障礙物的柵格點(diǎn)子集，減少了需要考慮的柵格點(diǎn)的數(shù)目，從而降低了三維路徑規(guī)劃的復(fù)雜性。在不同的障礙物環(huán)境下進(jìn)行的仿真實(shí)驗(yàn)表明，該方法提高了三維路徑規(guī)劃的效率，也減少了規(guī)劃出的換向節(jié)點(diǎn)的個(gè)數(shù)，提高了智能體的運(yùn)行效率。

利用四叉樹法非均勻分割柵格圖時(shí)針對不同的環(huán)境會(huì)有不同的四分原則，而且重新確立連接關(guān)系時(shí)要頻繁進(jìn)行入棧出棧操作，可能會(huì)造成數(shù)據(jù)量過于龐大。而提取臨界障礙物和周圍點(diǎn)集的方法只適用于一條路徑被頻繁修改的情況，當(dāng)要尋找完全不同的另一條路徑時(shí)，之前非臨界障礙物有可能會(huì)成為新的臨界障礙物，進(jìn)而影響求解過程。為了能夠在減少規(guī)劃節(jié)點(diǎn)的同時(shí)不失去算法的廣泛適應(yīng)性，將障礙物的頂點(diǎn)作為節(jié)點(diǎn)特征進(jìn)行提取，并將其作為新的備選點(diǎn)來規(guī)劃路徑，然后采用蟻群算法在新的柵格環(huán)境下進(jìn)行路徑規(guī)劃，以期減少蟻群算法搜索過程中的節(jié)點(diǎn)數(shù)目，提高算法的收斂速度。

2 問題背景與柵格法建模

2.1 問題背景

全方位移動(dòng)AGV 作為自動(dòng)搬運(yùn)車輛，可完成移動(dòng)加工、裝配的任務(wù)。基于麥克納姆輪的全方位移動(dòng)AGV有著卓越的全方位性能，AGV實(shí)物圖如圖1所示，其結(jié)構(gòu)如圖2所示。

AGV的速度公式如下所示：

圖1 自動(dòng)導(dǎo)引車

圖2 AGV的結(jié)構(gòu)

其中，Rω是車輪的半徑；θ1、θ2、θ3、θ4分別是4個(gè)輪子的速度；L、W分別是AGV長和寬的一半；Vx、Vy分別是AGV的橫向和縱向速度；ωz是AGV的角速度。

2.2 柵格法建模

在全局環(huán)境已知且障礙物為靜態(tài)障礙物的環(huán)境下。用柵格劃分出AGV的工作區(qū)域，并用只包含0和1的矩陣生成柵格圖，障礙柵格由黑色表示，自由柵格由白色表示，如圖3所示。

圖3 柵格法環(huán)境建模

由于實(shí)際運(yùn)行時(shí)，AGV并不是一個(gè)質(zhì)點(diǎn)，如果規(guī)劃出的路徑距離障礙物過近，會(huì)影響AGV 運(yùn)行時(shí)的安全性。因此，在使用柵格法進(jìn)行環(huán)境建模時(shí)，會(huì)首先對障礙物進(jìn)行膨脹化，即只要該柵格中有障礙物，直接擴(kuò)展為整個(gè)黑色柵格，障礙物膨脹化前后規(guī)劃的路徑圖如圖 4（a）、（b）所示。

圖4 障礙物膨脹化前后規(guī)劃的路徑圖

由圖可知，在進(jìn)行膨脹化后，障礙物的實(shí)際大小小于黑色障礙物柵格，因此，規(guī)劃出的路徑可以與障礙物保持一定的安全距離。

3 新環(huán)境模型下的蟻群算法

3.1 問題描述

針對傳統(tǒng)柵格法建模規(guī)劃的路徑節(jié)點(diǎn)過多，導(dǎo)致車輛的運(yùn)行效率降低、損耗增加的問題，本文提出了一種新的環(huán)境建模方法。該方法將障礙物的頂點(diǎn)從原有柵格圖中提取出來，并作為蟻群算法中新的備選點(diǎn)用于規(guī)劃路徑。新環(huán)境模型下蟻群算法的數(shù)學(xué)描述如下。

（2）所有障礙物頂點(diǎn)的集合：C={c1,c2,…,cNc}。

（3）一個(gè)最優(yōu)解的非空集合S*，用于保存可以避開障礙物的最短路徑。

3.2 節(jié)點(diǎn)選擇策略

當(dāng)螞蟻位于某一節(jié)點(diǎn)時(shí)，為了從備選點(diǎn)中選出一個(gè)點(diǎn)作為下一節(jié)點(diǎn)，需要對節(jié)點(diǎn)進(jìn)行選擇，節(jié)點(diǎn)選擇策略如式（1）。

其中，ci是當(dāng)前節(jié)點(diǎn)，ci+1是ci的下一個(gè)可行點(diǎn)。是兩個(gè)點(diǎn)之間的信息素，是兩個(gè)點(diǎn)之間的啟發(fā)式信息，α和β分別是信息素和啟發(fā)式信息的重要程度。

3.3 信息素更新

每當(dāng)完成一次路徑的搜索，蟻群算法會(huì)對路徑上的信息素做出更新，其更新法則如式（2）～（5）所示。

其中，Q是常數(shù)，PLk,m是第k代第m只螞蟻從起點(diǎn)到終點(diǎn)的路徑長度，ρ是信息素衰減系數(shù)，是信息素初值。

3.4 頂點(diǎn)提取與可視性判斷

為了解決傳統(tǒng)柵格法備選點(diǎn)過多、算法計(jì)算量過大的問題，提取如圖5所示的頂點(diǎn)作為蟻群算法的備選點(diǎn)。

圖5 柵格圖中的頂點(diǎn)提取

由圖可知，在進(jìn)行了頂點(diǎn)提取之后，在30×30 的環(huán)境中提取出80個(gè)頂點(diǎn)。之后運(yùn)用蟻群算法進(jìn)行路徑規(guī)劃時(shí)，只需從這80 個(gè)頂點(diǎn)中找到最短路徑即可。該方法使問題的維數(shù)從900下降到80，極大地提高了算法搜索的效率。然而在提取了頂點(diǎn)之后，原有柵格之間的連接關(guān)系被打破，因此需要確定每個(gè)頂點(diǎn)的鄰域，重新構(gòu)造鄰接矩陣。

當(dāng)判斷兩個(gè)頂點(diǎn)之間是否存在無障礙物路徑時(shí)，僅需判斷這兩個(gè)頂點(diǎn)之間是否存在障礙物的邊即可，即判斷兩條線段是否相交，如圖6所示。

圖6 頂點(diǎn)可視性判斷

柵格a和b的連接線l1沒有通過障礙物的邊緣，因此定義柵格a和b是可見的，并在鄰接矩陣中記錄柵格a和b之間的距離；然而，柵格a和c的連接線l2與障礙物的兩個(gè)邊緣x=3 和x=7 相交于點(diǎn)（3，28）和點(diǎn)（7，24），因此定義柵格a和c是不可見的，并且在鄰接矩陣中記錄兩點(diǎn)之間的距離為0。

該算法實(shí)際上是通過建立新的候選列表，減少蟻群算法要搜索的節(jié)點(diǎn)個(gè)數(shù)，從而大大降低搜索空間的維度，使系統(tǒng)的計(jì)算時(shí)間保持在合理的范圍內(nèi)。

3.5 算法的流程步驟

新的柵格法建模能夠減少蟻群算法中要搜索的節(jié)點(diǎn)數(shù)目，基于該柵格方法的蟻群算法流程如下。

步驟1 采用柵格法對AGV行駛的二維工作環(huán)境進(jìn)行建模；

步驟2 提取障礙物頂點(diǎn)，進(jìn)行可視性判斷，生成新的鄰接矩陣；

步驟3 初始化α、β、ρ、M、N等參數(shù)，M為每代螞蟻的數(shù)量，N為迭代次數(shù)；

步驟4 將螞蟻置于起點(diǎn)，并準(zhǔn)備開始進(jìn)行路徑搜尋；

步驟5 通過式（1）選擇下一個(gè)節(jié)點(diǎn)；

步驟6 更新禁忌表；

步驟7 判斷是否所有螞蟻都完成了搜索，如果沒有，返回步驟4，否則，繼續(xù)到下一步；

步驟8 根據(jù)式（2）～（5）更新信息素；

步驟9 判斷是否達(dá)到最大迭代次數(shù)，如果是，則輸出最佳路徑，否則，轉(zhuǎn)到步驟4，直到滿足最大迭代次數(shù)。

3.6 收斂性證明

為了驗(yàn)證算法的可行性，本文對算法的收斂性進(jìn)行以下證明。

引理兩點(diǎn)間的信息素滿足式（6）。

其中，Q(S*)是信息素的最大增量。

證明每次迭代之后，信息素的增量最多是Q(S*)。因此可以得出在第一代之后，信息素的最大值為(1-ρ)。是信息素的初值。第二代之后，信息素再次更新，信息素的最大值為

(1-ρ)Q(S*)+Q(S*)。由于信息素的蒸發(fā)，第k代信息素應(yīng)為：

由于0<ρ<1，式（7）收斂到：

假設(shè)從起始點(diǎn)到終點(diǎn)至少有一條路徑，Ek表示螞蟻在第k代第一次找到了最短路徑，則應(yīng)該滿足式（8）：

證明代表最短路徑第i次選擇的柵格。由式（1）和節(jié)點(diǎn)的選擇相互獨(dú)立，可以得到第m'只螞蟻在第k代找到了最短路徑的概率為：

由式（5）可知第k代信息素的最小值為：

并且由引理可知，第k代信息素的最大值為：

而Nc(k,m',(ci,ci+1))的最大值可以被定義為：

其中，Nc(k,m',(ci,ci+1))是可選擇的節(jié)點(diǎn)個(gè)數(shù)，將式（11）、（12）、（13）代入式（10）可得：

令

將式（15）代入式（14）可表示為：

通過式（16）可得：

對上式取對數(shù)可得：

即

4 仿真結(jié)果與評價(jià)指標(biāo)

4.1 仿真結(jié)果

為了驗(yàn)證新柵格法建模的優(yōu)點(diǎn)，本文利用新的柵格法對環(huán)境進(jìn)行建模并進(jìn)行路徑規(guī)劃，并與傳統(tǒng)柵格法規(guī)劃出的路徑進(jìn)行比較，每個(gè)柵格的邊長設(shè)定為1。將起點(diǎn)設(shè)置為（0.5，8.5），終點(diǎn)設(shè)置為（25.5，28.5），結(jié)果如圖7所示。

從圖中可以看出，基于新柵格法建模的蟻群算法規(guī)劃出的路徑中的節(jié)點(diǎn)數(shù)量與舊路徑中的節(jié)點(diǎn)數(shù)量相比顯著減少，從而提高了車輛的運(yùn)行效率，同時(shí)保證了車輛與障礙物的安全距離。

除此之外，新的柵格法建模由于減少了蟻群算法要搜索的節(jié)點(diǎn)數(shù)量，從而減少了蟻群算法的計(jì)算量，提高了蟻群算法的收斂速度，如圖8所示。

由結(jié)果可知，使用基于特征提取的柵格法建模的改進(jìn)蟻群算法可以更快地收斂到最短路徑，保持了改進(jìn)蟻群算法的收斂速度。最短路徑長度較改進(jìn)前略有增加，這是由于在本算法中頂點(diǎn)的可見性判斷時(shí)，如果障礙物的頂點(diǎn)剛好在兩個(gè)柵格的連線上，為了安全起見，這兩個(gè)柵格設(shè)為不可見，而在原有的蟻群算法構(gòu)建鄰接矩陣時(shí)，若兩個(gè)柵格間的連線剛好經(jīng)過障礙物頂點(diǎn)，則這兩個(gè)柵格可見，但很明顯這種方法是不可取的。

圖7 不同算法規(guī)劃出的路徑對比

4.2 評價(jià)指標(biāo)

在評價(jià)傳統(tǒng)的路徑規(guī)劃算法時(shí)，主要包含以下幾個(gè)評價(jià)指標(biāo)：路徑長度、迭代次數(shù)、路徑的節(jié)點(diǎn)個(gè)數(shù)、路徑的總轉(zhuǎn)彎角、拐點(diǎn)數(shù)、每段路徑和最近障礙物點(diǎn)之間的安全距離。本文將這些評價(jià)因素提取出來，與傳統(tǒng)蟻群算法以及改進(jìn)蟻群算法進(jìn)行比較，如表1所示。

圖8 不同算法的迭代次數(shù)

由表1可知，改進(jìn)柵格法建模在保持了改進(jìn)蟻群算法路徑長度的同時(shí)，算法的迭代次數(shù)、路徑的節(jié)點(diǎn)個(gè)數(shù)、總偏轉(zhuǎn)角、拐點(diǎn)數(shù)以及安全距離都有了明顯的改善。其中，減少迭代次數(shù)意味著增強(qiáng)了算法的尋優(yōu)能力，減少節(jié)點(diǎn)個(gè)數(shù)意味著AGV 提高了運(yùn)行時(shí)的效率，減少偏轉(zhuǎn)角和拐點(diǎn)數(shù)意味著減少了AGV 運(yùn)行時(shí)的磨損，加大安全距離意味著AGV運(yùn)行時(shí)的安全性得到了保證。綜上所述，在考慮多個(gè)評價(jià)因素后，基于改進(jìn)的柵格法建模的路徑規(guī)劃具有明顯的優(yōu)勢。

表1 評價(jià)指標(biāo)的對比

5 結(jié)束語

針對傳統(tǒng)路徑規(guī)劃問題中規(guī)劃出的節(jié)點(diǎn)過多、算法計(jì)算量大的問題，本文提出了一種基于特征提取的柵格建模方法。通過提取障礙物的頂點(diǎn)，并且重新構(gòu)造鄰接矩陣，減少了規(guī)劃出的路徑的節(jié)點(diǎn)個(gè)數(shù)。該方法不僅降低了蟻群算法的復(fù)雜度，而且提高了規(guī)劃路徑的性能，保證了AGV的高效可靠運(yùn)行。同時(shí)因?yàn)樾碌臇鸥穹ㄒ?guī)劃出的路徑不會(huì)直接經(jīng)過障礙物柵格的頂點(diǎn)，所以路徑的安全性也得到了保證。為了驗(yàn)證算法的收斂性，對其進(jìn)行了數(shù)學(xué)證明，并對算法進(jìn)行了仿真。結(jié)果表明，改進(jìn)后的算法明顯優(yōu)于傳統(tǒng)的蟻群算法，解決了傳統(tǒng)路徑規(guī)劃算法中由于換向節(jié)點(diǎn)過多而導(dǎo)致車輛行駛效率低，損耗大，以及非換向節(jié)點(diǎn)過多而導(dǎo)致的算法計(jì)算量龐大的問題，為AGV 路徑規(guī)劃中環(huán)境模型的建立提供了新的思路。