柵格圖特征提取下的路徑規(guī)劃建模與應用

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

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

2.國網河北省電力有限公司，石家莊 050051

1 引言

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

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

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

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

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

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

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

2 問題背景與柵格法建模

2.1 問題背景

全方位移動AGV 作為自動搬運車輛，可完成移動加工、裝配的任務?；邴溈思{姆輪的全方位移動AGV有著卓越的全方位性能，AGV實物圖如圖1所示，其結構如圖2所示。

AGV的速度公式如下所示：

圖1 自動導引車

圖2 AGV的結構

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

2.2 柵格法建模

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

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

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

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

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

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

3.1 問題描述

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

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

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

3.2 節(jié)點選擇策略

當螞蟻位于某一節(jié)點時，為了從備選點中選出一個點作為下一節(jié)點，需要對節(jié)點進行選擇，節(jié)點選擇策略如式（1）。

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

3.3 信息素更新

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

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

3.4 頂點提取與可視性判斷

為了解決傳統柵格法備選點過多、算法計算量過大的問題，提取如圖5所示的頂點作為蟻群算法的備選點。

圖5 柵格圖中的頂點提取

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

當判斷兩個頂點之間是否存在無障礙物路徑時，僅需判斷這兩個頂點之間是否存在障礙物的邊即可，即判斷兩條線段是否相交，如圖6所示。

圖6 頂點可視性判斷

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

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

3.5 算法的流程步驟

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

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

步驟2 提取障礙物頂點，進行可視性判斷，生成新的鄰接矩陣；

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

步驟4 將螞蟻置于起點，并準備開始進行路徑搜尋；

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

步驟6 更新禁忌表；

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

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

步驟9 判斷是否達到最大迭代次數，如果是，則輸出最佳路徑，否則，轉到步驟4，直到滿足最大迭代次數。

3.6 收斂性證明

為了驗證算法的可行性，本文對算法的收斂性進行以下證明。

引理兩點間的信息素滿足式（6）。

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

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

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

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

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

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

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

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

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

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

令

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

通過式（16）可得：

對上式取對數可得：

即

4 仿真結果與評價指標

4.1 仿真結果

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

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

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

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

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

4.2 評價指標

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

圖8 不同算法的迭代次數

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

表1 評價指標的對比

5 結束語

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