特征點提取下的AGV柵格法建模與分析

趙 江，孟晨陽，王曉博，郝崇清，李 冉，劉慧賢，王昭雷

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

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

自動引導車（AGV）是一種具有安全防護和多種裝載功能的運輸小車。它有多個自動引導裝置，可以按規定的路徑行駛[1]。由于AGV既可以應用于碼頭的自動裝卸，又可以提供家庭服務[2]，近年來受到越來越多的關注。由于路徑規劃是AGV實現功能的基礎，所以該問題也成為機器人領域研究的熱點。路徑規劃是指在具有障礙物的環境約束下，根據給定的起點和終點，應用算法準則，為AGV找到一條最優或接近最優的、安全、無障礙路徑[3-4]。AGV路徑規劃可分為靜態規劃和動態規劃兩種。其中靜態路徑規劃也稱為全局或離線路徑規劃，所有的環境信息均為已知；動態路徑規劃問題則是基于傳感器對周圍環境的感知，由于其環境信息為全部未知或部分未知，也被稱為局部或在線路徑規劃問題。本文研究的是已知環境下的全局靜態路徑規劃問題，通過選擇柵格法來解決這類問題。

解決靜態路徑規劃的主要方法有粒子群優化算法[5]、蟻群算法[6]、A*算法[7]、人工勢場法[8]等，這些算法通常在柵格圖環境模型中對路徑進行搜索。其中蟻群算法是一種概率仿生算法，隨著種群的迭代得到最優路徑[9]；A*算法是一種啟發式路徑規劃算法，它通過判斷從起點到當前點的距離和從當前點到終點的距離的啟發式信息之和來尋找最優路徑[10]；人工勢場法是一種虛擬力法[11]，它通過引力和斥力的相互作用將AGV引向終點。研究人員對上述算法進行了大量的研究，并提出了許多優化方案。

傳統的蟻群算法存在迭代次數多、搜索效率低等缺點。為了解決這些問題，Lee[12]提出了一種基于異構蟻群的路徑規劃方法，該方法改進了蟻群的轉移概率函數和信息素更新規則，在不需要后續平滑處理的情況下可以直接找到節點數較少的最優路徑；Zhang等[13]提出了一種智能蟻群路徑規劃算法，該方法通過消除蟻群算法中禁忌表的約束，引入臨時權值矩陣，避免了小權值路徑的重復選擇，提高了算法的效率；Lee等[14]改變了蟻群算法生成初始種群的方式，縮短了尋找最優解的時間，加快了算法的收斂速度；Saidi-Mehrabad[15]將蟻群算法分為兩個階段進行路徑搜索，有效地縮短了路徑規劃的完成時間。

傳統的A*算法搜索過程盲目，規劃出的路徑轉彎次數過多，導致AGV的運行損耗過大。為了解決這些問題，Yu等[16]提出了一種蟻群優化算法和A*算法相結合的雙層算法，其中蟻群算法負責確定目標的移動順序，A*算法負責快速建立目標之間的移動成本圖，以便于蟻群算法的計算；Song等[17]發現A*算法規劃的路徑包含大量的拐點，在實踐中會影響AGV的運行，因此提出了一種改進的A*算法，并在規劃后對路徑進行了平滑處理。

為解決傳統人工勢場法局部最優問題，Sudhakara等[18]在人工勢場法的基礎上，提出了一種不考慮排斥力和吸引力影響的優化算法，通過構建一種排斥函數產生排斥勢場，并將其應用于任意形狀的障礙物上，通過該方法可以為移動機器人提供更為準確的路徑；Orozco-Rosas等[19]提出將遺傳算法與人工勢場方法相結合，找到一條可行的安全路徑；Zhou等[20]提出用粒子群算法改進人工勢場法，引入切向量對規劃出的路徑進行優化，并在人工勢場模型中加入基于障礙物信息的矢量來輔助完成避障過程，大大改進了人工勢場法的局部最優問題。

利用上述改進算法在柵格圖中進行路徑規劃的本質仍是比較所有相鄰無障礙柵格的估計函數，即計算柵格圖中每個相鄰可行柵格的估計函數，然后通過比較估計值得到下一個路徑點。這種逐點規劃的方法存在著大量的無效計算，導致算法的效率大幅降低。為了解決這一問題，卜新蘋等[21]采用四叉樹方法對傳統柵格圖進行分割，減少柵格的數量，并對分割后柵格的連接關系進行定義，結果表明，減少柵格數可以在不影響路徑質量的情況下縮小搜索范圍，提高算法的計算效率，并減少路徑中的節點數。Han[22]提出了一種關鍵障礙物及其周圍點的提取方法，該方法根據障礙物的不同重要性，在環境中找到相對重要的障礙物，并找到與這些障礙物相關的柵格點，從而降低了三維路徑規劃的復雜度，大量仿真實驗表明，該方法可以提高三維路徑規劃的效率，并減少路徑中拐點的數量，從而提高移動機器人的運行效率。

在使用四叉樹方法對柵格圖進行分割時，對于不同的環境和不同的路徑規劃要求會有不同的分割原則，并且在重新建立柵格間的連接關系時，頻繁的入棧和出棧操作可能會導致計算量過大。而提取關鍵障礙物及其周圍柵格點的方法僅適用于對一條路徑進行微調，在尋找不同的路徑時，柵格間的重要性關系會發生改變，從而影響路徑規劃的過程。為了解決上述問題，本文提出了一種基于特征點提取的環境建模方法，該方法通過提取每個障礙物的頂點柵格作為特征點對環境進行建模，以期得到一個更為簡化且適用面更廣的環境模型，從而有效地縮小路徑規劃算法的搜索范圍，提高算法的搜索效率，得到一條更為優化的路徑。

1 傳統柵格法建模及其改進

1.1 傳統柵格模型的建立

在進行路徑規劃前，需要對AGV的運行環境進行建模。選擇的建模方法通常為柵格法，柵格法建模的方法如下。

對機器人運行環境進行量化處理，形成一些以AGV投影尺寸為單位的小單元，作為一個環境的網格映射。根據環境的大小設置相應的網格映射為m×m。網格映射模型如圖1所示。圖中紅色為起點，綠色為終點，黑色網格表示量化后的障礙物。該圖所示起點坐標表示為S=( 4 .5,4.5)，終點坐標表示為E=(1 5.5,15.5)。

圖1 柵格法建模圖示Fig.1 Grid model diagram

柵格圖內的每個格都可以設定為一個小的單元，數學表達為cell(x,y)，其中x、y表示每個小單元的位置。根據每個網格是否為障礙物，給每個單元設置為：

當機器人遇到障礙物的時候將當前單元格記錄為1，表示障礙物柵格。相對于障礙物柵格其他的柵格為0，表示可行柵格。柵格還可以儲存機器人路徑信息，表示為相關屬性和訪問屬性，同樣柵格也可以記錄自身特殊信息。

1.2 傳統柵格模型的路徑規劃

建立環境模型后，需要確定AGV的起點和終點。如圖2所示，S為起點，E為終點，找到一條從S到E的有效路徑，這個過程稱為路徑規劃。

圖2 傳統柵格圖中的路徑規劃Fig.2 Path planning in traditional grid graph

傳統的AGV路徑通常根據特定的性能指標（最短路徑、最短時間、最小損耗等）進行規劃。但在實際應用中，不僅要考慮路徑長度和運行時間，還要考慮AGV運行時的磨損、與障礙物之間的安全距離和算法的計算效率等。而在AGV的實際運行中，由于規劃的路徑通常是分段線性路徑，AGV必須在每個換向節點處停止，根據下一個路徑改變其方向，然后重新啟動。基于傳統柵格圖的路徑規劃方法在尋找最短路徑時往往忽略了節點過多而造成的影響。因此，減少換向節點對提高AGV的運行效率和減少AGV的磨損具有重要的作用。

另外，基于傳統柵格法建模的路徑規劃算法在搜索路徑時，往往通過判斷當前節點周圍的節點信息來選擇下一個節點。要計算的柵格數隨著柵格圖分辨率的增加而增加，從而降低了搜索速度。

為了使算法在不影響解的質量的情況下提高對路徑搜索的目的性，本文提出了一種基于特征點提取的柵格圖模型，以減少算法的計算量，使AGV的路徑更加平滑。

1.3 基于特征柵格提取的柵格模型

（1）特征提取規則

在路徑規劃問題中，只要起點和終點互不可見，基于柵格法規劃出的最短路徑的有效拐點往往是障礙物柵格的頂點。然而，由于逐層規劃的弊端，有效拐點之間往往存在大量無效拐點。當兩個可相互到達的有效拐點之間的路徑是一條線段時，該路徑為兩個有效拐點之間的最佳路徑，因此將特征柵格提取規則定義如下：

規則1特征柵格可以是與單個黑色柵格的四個頂點處相對應的可行柵格。

規則2特征柵格也可以是與組合黑色柵格的所有凹角處相對應的可行柵格。

規則3特征柵格數量應與障礙物柵格數量相關，障礙物數量越多特征柵格數量越多。

（2）障礙物網絡模塊化處理

結合特征柵格提取規則，本文利用蒙特卡羅搜索的方法來分析處理環境柵格模型，利用各種網絡模型來合理區分各種類型的障礙物柵格，由蒙特卡洛搜索分解出的基本障礙物柵格如圖3所示。

圖3 網絡模型化處理下的障礙物示意圖Fig.3 Obstacle diagram based on network modeling

通過蒙特卡洛模擬可以得出上述十二種基本障礙物形狀，其可以組合出柵格法建模中任意障礙物形狀。通過特征柵格的提取規則可以得出各種障礙物形狀對應的特征柵格。結合特征提取規則，任意環境中都可以提取出相應的特征柵格，特征柵格可以代表柵格法路徑規劃的全部環境信息。

柵格法建模是將AGV運行的工作環境單元分割為大小相等的方塊，形成一組網格，網格圖中每一個柵格都可以作為一個二值信息網格單元來存儲環境信息，這些信息可以包含人為指定信息，也可包含算法規劃信息，每個網格被稱為環境單元。柵格法建模將整個環境進行抽象建模，路徑規劃時采用相應的路徑規劃搜索算法在該空間內進行搜索。通過特征提取規則選擇特征柵格，其周圍都會有白色可行柵格，特征柵格可以表示周圍白色可行柵格的環境信息。基于柵格法規劃出的最短路徑中的有效拐點往往是黑色柵格對應的可行頂點柵格，而其他柵格只是作為可行柵格進行規劃，特征柵格可以很好地表達周圍白色可行柵格的環境信息，在簡化環境模型的同時，保證了環境信息的完整性。

（3）新型柵格法建模結果

基于上述規則和柵格建模方法，可以得出在柵格建模環境下，膨脹化的障礙物是由多個正方形組成的不規則圖形，由提取規則1、2，特征柵格的數量應與障礙物柵格數量相關，即障礙物柵格數量越多特征柵格數量越多。根據規則1、規則2和規則3提取特征網格，提取結果如圖3所示。

由圖4可知，從6×6網格模型中提取了10個頂點，搜索范圍從25個柵格縮小為10個柵格，減少了柵格法建模產生的60%無效柵格，新型柵格法建模減少了算法的搜索范圍，局部路徑規劃算法只需要對特征柵格進行路徑規劃，大大提高了算法的搜索效率。

圖4 特征柵格提取Fig.4 Feature grid extraction

在提取頂點后，大部分提取的柵格不再是連續柵格，因此需要通過柵格可見性判斷的方法重建每個柵格的鄰接矩陣。柵格之間的連接可以分為三種類型，如圖5所示。

圖5 柵格可見性判斷Fig.5 Grid visibility judgment

類型一：圖中的柵格a和b之間沒有障礙物，皆為白色柵格，因此，定義柵格a和b是可見的，線段l1為可行路徑。

類型二：圖中的柵格a和c之間有障礙物，存在黑色柵格，因此，定義柵格a和c是不可見的，線段l2為不可行路徑。

類型三：圖中的柵格a和d之間雖未直接經過障礙物柵格，但線段l3卻與黑色障礙物柵格交于點（1，2），由于AGV自身存在體積，為了AGV運行時的安全性，該類路徑應被定義為不可行路徑，然而，在傳統的基于柵格法的路徑規劃算法中，并沒有將該類不可行路徑排除，使AGV的運行路徑存在隱患，所以本文提出的將該類路徑定義為不可行路徑的方法，一定程度上提升了AGV運行時的安全性。

1.4 新型柵格法建模性能分析

柵格環境建模方法是將機器人周圍空間分解為互相連接且不重疊的空間單元，空間單位可以表示為柵格，柵格法建模分為精細化柵格法和近似化柵格法兩種方式。新型柵格法建模屬于近似柵格法建模，將障礙物做膨脹化處理，柵格不僅可以完整地保存環境信息還可以保證AGV在環境中的運行安全。新型柵格法建模提取的是黑色柵格頂角位置的白色柵格，由于柵格法對障礙物膨脹化處理，通過特征提取到的白色柵格保證了原有柵格法建模對環境信息的完整性，并且保證了AGV在環境中的運行安全。

相對于傳統柵格法建模中將全局環境作為有效信息輸入到AGV的路徑規劃中，新型柵格法建模大量減少了傳統柵格法中需要運算搜索的柵格數量，使用30%～40%的特征柵格就可以表示全局環境信息。圖6中，數字標出的是特征點提取下的有效柵格，障礙物邊緣是路徑規劃算法運算的重要位置，將重要位置提取出來，不僅可以保證環境信息的完整性還可以保證AGV路徑規劃的搜索速度。同時使得AGV的搜索更加具有目的性，并結合傳統柵格法建模的優點，保證了AGV運行的安全。

圖6 新舊柵格法對比分析Fig.6 Comparative analysis of new and old grid method

針對局部路徑規劃算法，如蟻群算法、A*算法和人工勢場法等需要對每個白色柵格進行算法估計，而黑色柵格頂點處白色柵格上的局部路徑規劃算法估計值變化巨大，新型柵格法建模選擇提取單個黑色柵格的四個頂點處相對應的可行柵格和組合黑色柵格的所有凹角處相對應的可行柵格作為特征柵格，可以保證特征點具有代表性。

1.5 新舊路徑對比分析

基于特征點提取的思想，將傳統柵格圖中的障礙物頂點選為特征點提取出來，在進行了頂點可視性判斷、確定頂點間的連接關系之后，重新在該環境下進行路徑規劃，得到的結果如圖7所示。

在圖7中，黑色路徑是傳統柵格模型中規劃的路徑，紅色路徑是特征柵格提取的環境模型中規劃的路徑。

圖7 新舊路徑對比分析Fig.7 Comparative analysis of old and new paths

兩條路徑之間的主要數據比較如表1所示。從路徑長度上看，相比于傳統柵格圖下的路徑規劃算法，基于特征柵格提取的柵格法規劃出的路徑由于搜索范圍被嚴格約束在了障礙物的頂點上，在進行路徑規劃時會大概率選擇路徑ab，而不選擇路徑acb。由三角形法則可得，在三角形abc中，ac+cb＞ab，最終使得路徑長度變短；從換向節點數和路徑總轉角上看，由于特征柵格提取的柵格圖中，路徑從柵格a到b沒有經過c，減少了拐點c之后，由d到g減少了三個90°的拐角，轉化成了兩個45°的角，使得路徑總轉角大幅減少，從而減少了AGV運行時的損耗；從平均安全距離上看，基于特征點提取的柵格圖中加大了路徑的平均安全距離，有利于AGV的安全運行。

表1 新舊路徑的主要數據對比Table 1 Comparison of main data between old and new paths

2 新環境模型在典型路徑規劃算法中的應用

為了驗證所提出的環境建模方法的有效性，將其應用于多種不同類型的路徑規劃算法中，包括虛擬力法、直接搜索法和進化算法，并解決算法中存在的運行時間長、局部最優等問題。柵格法為全局搜索算法，新型柵格法適用于基于先驗完全信息的局部路徑規劃方法，例如A*算法（直接搜索法）、人工勢場算法（虛擬力法）和蟻群算法（進化算法）等。

2.1 新柵格模型在人工勢場法中的應用

人工勢場法是Khatib提出的一種虛擬力法，其思想是將AGV、目標點和障礙物視為質點，將AGV運動環境抽象為一個具有吸引力和排斥力的力場。在這個力場中，障礙物提供排斥力，目標點提供吸引力，根據AGV的位置產生合力決定AGV的運動方向，其實質是根據環境建立一個模擬力場。

人工勢場法的數學模型如式（1）所示：

式（1）中，U為小車的勢能之和，Uatt為目標點對AGV的吸引力，Urep為障礙物對AGV的排斥力，再將引力場對AGV的引力梯度和斥力場對AGV的斥力梯度通過拉格朗日變換得出力的關系為：

式（2）中，Fatt為目標點對AGV的吸引力，Frep為障礙物對AGV的排斥力，AGV所受的合力如圖8所示。

圖8 柵格圖中AGV所受合力Fig.8 Resultant force of AGV in grid graph

設AGV在工作空間中的位置為p=(x,y)T，則其引力勢函數為：

k為大于零的引力勢場常量，p為AGV位置向量，pe為AGV在勢場中的目標位置，則引力勢函數的負梯度為：

該引力隨著AGV趨近于目標點而趨近于零。根據Khatib提出的一種FIARS函數得出斥力勢場公式如下：

式（5）中，η為當前障礙物對AGV有影響時的斥力勢場常量，ρ為AGV所在位置與障礙物的最短距離，ρ0為單個障礙物所能影響的最大距離范圍，當AGV與障礙物的距離大于ρ0時斥力場對AGV的影響為零。斥力場產生的斥力為：

根據上述理論依據可得人工勢場法的基本流程如下：

步驟1參數初始化：設置引力常量、斥力常量、起點以及目標點。

步驟2獲取當前AGV狀態，根據公式（2）判斷此時機器人的受力情況，確定接下來AGV的移動方向。

步驟3判斷AGV是否到達目標點，如果到達，則結束程序，否則返回步驟2。

雖然人工勢場法能有效地解決AGV與障礙物的碰撞問題，但傳統的人工勢場法路徑規劃方法仍存在以下問題：（1）當AGV移動到某一位置時，吸引力和排斥力之和為零，AGV會錯誤地認為已經到達了目標位置并停止，這是一個典型的局部最優問題；（2）傳統人工勢場法產生的路徑會頻繁經過障礙物的邊緣，無法保持有效的安全距離，從而影響AGV的安全運行。

為了解決上述問題，將基于特征點提取的柵格模型應用到人工勢場法中。由于該柵格模型的引入，由AGV所受到的合力確定AGV運動方向的方法不再適用，所以不再計算每個柵格的各個方向的合力，而是計算其勢能，然后通過勢能下降的原理確定AGV的運行方向。

在柵格模型中利用人工勢場法規劃路徑時，通常對每個柵格賦值，將導致AGV的運行在環境中缺乏有效的信息導向。因此，根據本文提出的特征點提取的柵格模型，在計算勢能時，只需計算提取的特征柵格的勢能，這樣可以為AGV的運行提供更有效的信息指導，從而解決人工勢場法路徑規劃中的局部最優問題，提高AGV與障礙物之間的安全距離，保障AGV運行時的安全。

通過對人工勢場法在新型柵格圖中的應用，可以看出新型柵格圖可以很好地解決應用虛擬力法時移動機器人的路徑規劃問題，對于以模擬退火算法和人工勢場法為代表的虛擬力法具有很好的適用性。

2.2 新柵格模型在A＊算法中的應用

A*算法是一種根據給定的代價函數，在靜態環境中尋找從起點到目標點最優路徑的一種直接搜索方法。并通過在Dijkstra算法中加入啟發式函數，提高算法的計算效率，其數學模型為：

式（6）中，f(x)是從起點S通過x位置到達終點E的最優成本，g(x)表示從位置S到目標點x的實際成本，h(x)表示從目標點x到終點E的估計成本。如圖9所示，所以估計成本中min(f(x))被選擇的概率較高。因此，A*算法在規劃路徑時總是選擇min(f(x))的節點。

圖9 利用A*算法進行路徑規劃Fig.9 Path planning using A*algorithm

每個柵格左上角的數字表示最優成本f(x)，左下角的數字表示從起點S到位置x的實際成本g(x)，右下角的數字表示從位置x到目標點E的估計成本h(x)。

根據上述理論依據可得A*算法的基本流程如下：

步驟1初始化參數，設置開發列表Q，設置起點和終點。

步驟2根據公式（6），選擇Q中的最小f(x)的節點x作為下一個路徑點。

步驟3確定搜索是否已到達終點，如果是則停止算法，如果不是則轉到步驟4。

步驟4搜索擴展，對圖中每兩個節點m、n進行比較。如果g(m)＞g(n)+cost(n,m)則g(m)=g(n)+cost(n,m),f(m)=g(m)+h(m)，并將m點加入到開放列表Q中，否則，m點不加入到Q中，返回步驟2。

A*算法在Dijkstra算法中增加了一個啟發式函數。盡管A*算法有效地減少了搜索范圍和計算復雜度，但它仍然需要估計柵格圖中每個節點的距離，用h(x)表示當前節點和目標節點之間的成本，并通過選擇最小的f(x)來選擇最優路徑。當環境較大時，柵格圖中大量的柵格將延長A*算法的搜索時間。因此，采用新柵格法來解決這個問題。

首先提取障礙物的每個頂點柵格作為特征柵格，只計算特征柵格的估計值。A*算法在搜索柵格時，只搜索這些特征柵格，從而減少A*算法在柵格模型中搜索的柵格數，避免A*算法搜索時間過長和范圍過大。另外，由于新的柵格建模方法提取的特征柵格不再是簡單的水平或垂直關系，因此使用歐幾里德距離代替曼哈頓距離來計算估計值，該方法還可以有效地減少規劃出的路徑的轉彎次數和角度。

將新型柵格法應用于A*算法中可以有效減少A*算法的搜索面積，提高搜索速度，對于以A*算法和Dijkstra算法為代表的搜索算法有很好的適用性。新型柵格法建模有效提高了算法的性能。

2.3 新柵格模型在蟻群算法中的應用

蟻群算法是一種通過模擬自然界螞蟻尋找最短覓食路徑的仿生算法。每只螞蟻在覓食時都會在路徑上留下一定濃度的信息素，并且由于信息素會揮發，所以路徑越長，信息素濃度越低。隨后的螞蟻更傾向于沿著信息素濃度較高的路徑行走，并繼續在路徑上留下新的信息素。通過上述正反饋效應，最終螞蟻們行走的路線將收斂到信息素濃度最高的最短路徑上。蟻群算法的數學模型包括節點選擇策略、信息素更新和鄰接矩陣三個部分。

節點選擇策略是指當螞蟻位于柵格中時，為了從備選柵格中選擇一個柵格進行轉移，需要使用狀態轉移概率公式來選擇下一個柵格，螞蟻k從柵格i到柵格j的轉移概率為：

其中，allowed k={c~-tabuk}代表每只螞蟻下一步中的所有可選柵格，c~為所有柵格的集合，tabuk為第k只螞蟻已經走過的所有柵格的集合，τij(t)為當前時刻i,j兩個柵格之間在t時刻的信息素濃度，ηij(t)為啟發函數，通常取ηij(t)=1/d ij，α為信息啟發因子，表示信息素的重要程度，α越大螞蟻之間的協作也就越強，β為啟發式因子，表示啟發函數的重要程度。

在路徑搜索過程中，為了避免信息素濃度過高導致啟發式信息失效，通常在搜索路徑后需要對信息素進行更新。更新規則如式（8）和（9）所示：

其中，ρ∈(0,1)為信息素揮發因子，其大小關系到算法的全局收斂能力和收斂速度表示第k只螞蟻在柵格i和j之間留下的信息素，有三種不同的蟻群算法模型，“蟻周系統”（Ant-Cycle）模型，“蟻量系統”（Ant-Quantity）模型和“蟻密系統”（Ant-Density）模型，其中蟻周系統算法性能優于其余兩種算法，其公式如下：

蟻群算法通過鄰接矩陣進行判斷兩點之間是否可達，在n×n的柵格圖中，鄰接矩陣D是一個大小為n2×n2矩陣，當i,j兩個柵格之間不可形成路徑時，D(i,j)=0，當i,j兩個柵格之間可以形成路徑時，D(i,j)=d ij。

根據上述理論依據可得蟻群算法的基本流程如下：

步驟1初始化α,β,ρ,M,N等參數。

步驟2將螞蟻置于起點，并準備開始搜索路徑。

步驟3通過式（7），在鄰接矩陣D(i,j)≠0的柵格中選擇下一個節點。

步驟4更新禁忌表tabuk。

步驟5判斷所有螞蟻是否都完成了搜索，如果完成搜索進入下一步，否則返回步驟3。

步驟6根據式（8）～（10）更新信息素。

步驟7判斷是否達到最大迭代次數，如果是則輸出最優路徑，否則返回步驟2，開始新一輪的搜索。

蟻群算法作為一種生物進化算法，其收斂速度是評價算法性能的重要指標。然而，傳統的蟻群算法存在收斂速度慢的問題。這是由于螞蟻在搜索路徑時需要考慮的路徑數量龐大，大大影響了算法的計算效率。應用本文提出的基于特征點提取的柵格模型，可以在不影響求解質量的前提下，減少對差解的搜索次數，從而提高蟻群算法的收斂速度。

在蟻群算法中，柵格間的連接關系是由鄰接矩陣D確定的。傳統蟻群算法的鄰接矩陣是通過判斷該柵格周圍的8個柵格是否為障礙物柵格求得的，設起點柵格為i，判斷柵格i+1與其的連接關系時，只需判斷柵格i+1是否為障礙物柵格或非相鄰柵格，若是則鄰接矩陣D(i,i+1)=0，若不是，則鄰接矩陣D(i,i+1)=d i+1。而當將障礙物頂點作為特征點提取出來后，判斷的不再是i與其相鄰柵格的連接關系，而是所有的障礙物頂點柵格與柵格i的連接關系。通過第1章中提到的可視性判斷，當柵格i與頂點柵格j可見時，鄰接矩陣D(i,j)=d ij,否則D(i,j)=0。

將新型柵格法建模應用于蟻群算法時有效減少了算法的搜索次數，大大提高了算法的收斂速度，說明新型柵格法建模適用于以蟻群算法、粒子群算法為代表的概率型算法。

通過以上的理論分析，可以得出局部路徑規劃算法使用二值信息的網格單元來儲存信息，都可以選擇用柵格法為工作環境進行建模。例如柵格可以存儲A*算法中每一個位置的估計值，也可以存儲蟻群算法每一個位置的信息素濃度。當移動機器人選擇可以使用柵格來存儲算法信息的路徑規劃算法時，可以選擇新型柵格法建模來完成環境建模。

3 仿真結果

為了驗證新的柵格建模方法的適用性，將其應用于三種不同的路徑規劃算法：人工勢場法、A*算法和蟻群算法中，并與傳統柵格法的路徑規劃進行比較。

為了保證實驗的客觀性，仿真中只改變路徑規劃中各算法的環境模型，而不改變其具體的算法參數。柵格的邊長設置為1，障礙物的密度和分布是隨機產生的，在10×10、20×20和30×30的柵格地圖上仿真并顯示三組不同算法的結果。

3.1 新柵格法模型應用于人工勢場法的結果

在三個柵格地圖中，起點S的坐標分別為（0.5，0.5），（1.5，18.5）和（2.5，27.5），終點E的坐標分別為（9.5，9.5），（19.5，3.5）和（24.5，1.5）。設k為1.72，圖10（a）、（b）和（c）上圖顯示了人工勢場法在傳統柵格法規劃出的路徑，下圖顯示了人工勢場法在新型柵格法規劃出的路徑，其中黑色實線為規劃路徑。

從圖10可以看出，將基于特征點提取的柵格模型應用于人工勢場法中時，可以明顯減少規劃路徑的轉向次數。另外，傳統柵格圖中利用人工勢場法規劃出的路徑會頻繁經過障礙物柵格的頂點，嚴重影響AGV的安全運行，這也是人工勢場法很少采用柵格法的主要原因，將基于特征點提取的柵格圖應用于人工勢場法路徑規劃增加了規劃出的路徑與障礙物柵格之間的安全距離，提高了AGV運行的安全性，使柵格法更適用于人工勢場法的路徑規劃中。

同時，由圖10（b）可以看出，從柵格圖中提取出特征柵格，可以有效減少柵格圖中局部最優點的個數，從而解決人工勢場法中的局部最優問題。在兩種柵格模型中人工勢場法路徑規劃的主要數據對比，如表2～4所示。從表中可以看出，新柵格模型中規劃出的路徑不再頻繁經過障礙物的頂點，提高了車輛行駛時的安全性。此外，新的網格模型中規劃出的路徑在轉彎次數和總轉彎角度上都小于傳統柵格模型中規劃出的路徑，大大降低了AGV運行時的損耗。

表2 人工勢場法在10×10環境模型中規劃路徑的數據比較Table 2 Data comparison of artificial potential field method in 10×10 environmental model

表3 人工勢場法在20×20環境模型中規劃路徑的數據比較Table 3 Data comparison of artificial potential field method in 20×20 environmental model

從柵格的計算次數上可以看出，在人工勢場法應用于新的柵格模型中進行路徑規劃后，計算量大大減少。此外，可以得出，新柵格圖的計算量不再依賴于柵格圖的大小，而是取決于環境中障礙物的形狀和分布。

表4 人工勢場法在30×30環境模型中規劃路徑的數據比較Table 4 Data comparison of artificial potential field method in 30×30 environmental model

3.2 新柵格法模型應用于A＊算法的結果

在三個柵格地圖中，起點S的坐標分別為（7.5，8.5），（0.5，0.5）和（16.5，23.5），終點E的坐標分別為（8.5，0.5），（14.5，19.5）和（13.5，8.5）。圖10（a）、（b）和（c）上圖顯示了A*算法在傳統柵格法規劃出的路徑，下圖顯示了A*算法在新型柵格法規劃出的路徑，其中黑色實線為規劃出的路徑，黑色圓圈所在的柵格為路徑中包含的柵格，灰色柵格為A*算法搜索的全部柵格。

從圖11可以看出，將A*算法應用于特征點提取的柵格建模中，可以減少規劃路徑上換向節點和非換向節點的數量。此外，還可以減少搜索的柵格數量，從而提高了A*算法的計算效率。

圖11 新舊柵格模型中A*算法路徑規劃的比較Fig.11 Comparison of A*algorithm path planning in new and old grid models

表5～7給出了A*算法在傳統柵格模型和新柵格模型中進行路徑規劃的主要數據比較。從表中可以看出，與A*算法在傳統柵格模型下規劃的路徑相比，新柵格圖的A*算法規劃的路徑更短，轉彎次數更少，總轉彎角度更小，這樣提高了AGV的運行效率，并減少AGV的運行損耗。更重要的是，A*算法的柵格計算數量大大減少，由此加快了A*算法的計算速度。

表5 A*算法在10×10環境模型中規劃路徑的數據比較Table 5 Data comparison of A*algorithm planning path in 10×10 environment model

表6 A*算法在20×20環境模型中規劃路徑的數據比較Table 6 Data comparison of A*algorithm planning path in 20×20 environment model

3.3 新柵格法模型應用于蟻群算法的結果

在三個柵格地圖中，起點S有坐標（3.5，9.5），（0.5，19.5）和（0.5，8.5），終點E有坐標（2.5，0.5），（18.5，0.5）和（25.5，28.5）。將信息素啟發因子α設為1，β設為12。η設為1.55。圖12（a）、（b）和（c）上圖顯示了蟻群算法在傳統柵格法規劃出的路徑，下圖顯示了蟻群算法在新型柵格法規劃出的路徑，其中黑色實線為規劃路徑，黑色圓圈為路徑中包含的節點。從圖12可以看出，蟻群算法在特征點提取的柵格模型中進行路徑規劃，減少了規劃路徑的拐點數量，從而降低了AGV的運行損耗。

圖12 新舊柵格模型中蟻群算法路徑規劃的比較Fig.12 Comparison of ant colony algorithm path planning in new and old grid models

表7 A*算法在30×30環境模型中規劃路徑的數據比較Table 7 Data comparison of A*algorithm planning path in 30×30 environment model

蟻群算法的迭代曲線如圖13（a）、（b）和（c）所示，其中實線為蟻群算法尋找到的當前最短路徑，虛線為蟻群算法每一代尋找到的最短路徑。

圖13 新舊柵格模型中蟻群算法迭代曲線的比較Fig.13 Comparison of iterative curves of ant colony algorithm in new and old grid models

由圖可以驗證，當蟻群算法在特征點提取的柵格模型中路徑規劃時，算法的效率顯著提高，迭代次數明顯減少。算法主要數據的比較如表8～10所示。

表8 蟻群算法在10×10環境模型中規劃路徑的數據比較Table 8 Data comparison of ant colony algorithm in 10×10 environment model

從表中可以看出，基于特征點提取的蟻群算法規劃出的路徑具有較少的轉彎點和總轉彎角度的優點，這樣可以減少AGV運行時的損耗，此外，還提高了路徑與障礙物之間的平均安全距離。從迭代次數和節點計算次數來看，基于特征點提取的柵格模型排除了原柵格模型中的一些較差解，使得蟻群算法在路徑規劃時不必考慮這些較差解，從而使路徑選擇更有目的性，大大縮短了算法的計算時間。

表9 蟻群算法在20×20環境模型中規劃路徑的數據比較Table 9 Data comparison of ant colony algorithm in 20×20 environment model

表10 蟻群算法在30×30環境模型中規劃路徑的數據比較Table 10 Data comparison of ant colony algorithm in 30×30 environment model

3.4 實驗結果分析

通過仿真結果可以看出，新型柵格法建模對于局部路徑規劃算法有很好的優化效果。局部路徑規劃算法只需要由傳感器采集環境信息，新型柵格法建模結合傳統柵格法中的環境信息表達方式保證了環境信息的完整性，同時新型柵格法建模通過特征提取的方式排除了算法中的較差解。局部路徑規劃算法中特征柵格節點與周圍節點的環境信息變化不大，過多的信息相似解反而會增加算法的運算時間，排除這些解使得算法選擇路徑更加有目的性。可以看出局部路徑規劃算法更加適合應用于新型柵格法建模。

4 結語

路徑規劃算法改進的思想通常是對算法本身進行優化和改進，有時這種改進用于其他路徑規劃算法時存在局限性。因此，本文提出了一種優化環境建模的新方法，通過提取障礙物的頂點柵格作為特征點來減小算法的搜索范圍。該方法可以應用于多種路徑規劃算法，同時保證一定的優化效果。為了驗證這種新柵格模型的適用性，將其應用于人工勢場法、A*和蟻群三種不同類型的路徑規劃算法，并對新方法的性能提升進行了評價。結果表明，新柵格模型適用于不同類型的路徑規劃算法，并且可以解決這些算法存在的局部最優、搜索速度慢和迭代次數多等問題，從而提高了這些算法的性能。特征點提取下的柵格模型具有很強的適用性，并且可以對不同的算法做出優化，為優化環境建模方法提供了一種新的思路。