卷煙廠AGV小車路徑規(guī)劃地圖的構建探討

摘 要：上世紀六十年代末期，Hart等人公開發(fā)表了一篇論文，該論文中闡述了一種設計思路十分精巧且高效的路徑規(guī)劃算法，這種算法唄命名為A-Star算法，簡稱A*算法。

關鍵詞：卷煙廠；AGV；小車路徑規(guī)劃；構建

A*算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法，要想理解A*算法的奧義，還需從啟發(fā)式搜索算法說起。啟發(fā)式搜索算法（Heuristically Search）亦稱為信息搜索法，它是利用問題擁有的啟發(fā)信息來引導搜索，達到減少搜索范圍、降低問題復雜度的目的。啟發(fā)式搜索與有序搜索有著本質(zhì)的不同，啟發(fā)式搜索引入了估價函數(shù)這一概念，通過估價函數(shù)對下一步節(jié)點的估價值來確定下一步路徑方向。因此啟發(fā)信息越多，估價函數(shù)的估價將會越準確，擴展的無用節(jié)點數(shù)就會越少，這一遍可以大大降低系統(tǒng)工作量，提高系統(tǒng)的工作效率。而有序搜索方法極具代表性的有深度優(yōu)先搜索（Depth First Search，DFS）、廣度優(yōu)先搜索（Breadth First Search，BFS）及上文所介紹的Dijkstra算法。Dijkstra算法此處便不再贅述，DFS和BFS是兩種早期的有序搜索方法，但二者均屬于盲目型搜索。也就是說，它不會選擇哪個結點在下一次搜索中更優(yōu)而去跳轉到該結點進行下一步的搜索。二者屬于盲目且執(zhí)著的搜索方法，有時經(jīng)常需要試探完整個解集空間才能完成路徑搜索，顯然，此類方法只能適用于問題規(guī)模不大的搜索問題中。而與DFS和BFS不同的是，一個經(jīng)過設計的啟發(fā)函數(shù)，往往會在很快的時間內(nèi)就可得到一個搜索問題的最優(yōu)解。

A*算法作為啟發(fā)式搜索算法中較為優(yōu)秀的一員，在實際工業(yè)生產(chǎn)應用中被廣泛使用。該方法與Dijkstra算法類似，都可以找到一條最優(yōu)路徑，其不同之處就是A*算法具備了一個估價函數(shù)，如式（1-1）所示：

f（n）=g（n）+h（n） （1-1）

其中，f（n）是每個可能節(jié)點的評估值，g（n）表示從起始節(jié)點到當前節(jié)點的代價值，h（n）則表示從當前節(jié)點到目標節(jié)點的估計值，是啟發(fā)式搜索中的核心部分，h（n）設計的好壞直接影響著A*算法的性能。

一種具有f（n）=g（n）+h（n）策略的啟發(fā)式算法能成為A*算法的充分條件是：

①搜索樹上存在著從起始點到終了點的最優(yōu)路徑；

②問題域是有限的；

③所有結點的子結點的搜索代價值>0；

④h（n）≤h*（n），其中h*（n）為實際問題的代價值。

當以上四個條件都滿足時，一個具有f（n）=g（n）+h（n）策略的啟發(fā)式算法能成為A*算法，并一定能找到最優(yōu)解。

對于一個合格的A*算法而言，其h（n）函數(shù)的選取是決定算法性能的重中之重，現(xiàn)階段常用的幾種估算方法有曼哈頓距離法、歐式距離法以及契比雪夫距離法。

一、曼哈頓距離

曼哈頓距離（Manhattan Distance）又稱出租車集合距離，是十九世紀有赫爾曼閔可夫斯基所常遭的集合度量用語。曼哈頓距離所表述的意思是兩個點在標準坐標系上的絕對軸距總和，其在二維空間中的表述如公式（1-2）所示：

d=|x1-x2 |+|y1-y2 | （1-2）

其中x和y為兩點坐標。

二、歐式距離

歐氏距離（Euclidean Distance）也稱為歐幾里得度量（Euclidean Metric），是一個慣用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。其在二維空間中的表述如公式（1-3）所示：

（1-3）

三、契比雪夫距離

契比雪夫距離（Chebyshev Distance）是對向量空間中的一種度量，兩個點之間的距離定義為其各坐標數(shù)值差的最大值。例如存在兩個點坐標分別為（x1，y1）和（x2，y2），其契比雪夫距離為：

d=max（|x1-x2|，|y1-y2|） （1-4）

以上三種方法所適用的范圍不同，且效果也不盡相同。

如圖1-11所示設在一片環(huán)境區(qū)域內(nèi)存在兩個節(jié)點，一個為起始節(jié)點（綠色）另一個為目標節(jié)點（紅色），首先用上文所述的Dijkstra算法來為起始節(jié)點到目標節(jié)點進行最優(yōu)路徑規(guī)劃，左右下角數(shù)字之和為上面的數(shù)字，本實驗里有兩個函數(shù)，一個是g（n），一個是h（n），這兩個數(shù)分別是它倆的值，它倆之和為f（n），具體情況如圖1-11所示。

從圖1-11中不難看出，Dijkstra算法在進行路徑搜索時，幾乎遍歷了整個搜索范圍，說明Dijkstra算法在路徑搜索過程中付出了較大的計算量，致使搜索速度慢，對速度要求較高的移動機器人來講該算法可能并不是十分適合。

從圖1-12中不難看出，采用了曼哈頓距離法的A*算法搜索效果較Dijkstra算法要好很多，其無需遍歷整個搜索范圍即可準確找到最佳路徑，其計算量相對較少，運算速度快，十分適合對速度有一定要求的移動機器人自主導航使用。為了驗證其他兩種距離方法在該問題上的實際效果，本文章也對采用了其他兩種距離算法的A*算法進行了測試研究，具體情況請參照圖1-13和1-14。

從圖1-12、1-13和1-14中不難看出，在完全相同的情況下，采用曼哈頓距離法的A*算法遍歷的范圍最小，其他兩種方法均較多。所以我們選定卷煙廠AGV小車路徑規(guī)劃地圖的構建探討。

作者簡介：鄭曉耘，河北白沙煙草有限責任公司。