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

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

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

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

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

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

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

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

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

②問題域是有限的；

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

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

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

對于一個合格的A*算法而言，其h（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）是對向量空間中的一種度量，兩個點之間的距離定義為其各坐標數值差的最大值。例如存在兩個點坐標分別為（x1，y1）和（x2，y2），其契比雪夫距離為：

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

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

如圖1-11所示設在一片環境區域內存在兩個節點，一個為起始節點（綠色）另一個為目標節點（紅色），首先用上文所述的Dijkstra算法來為起始節點到目標節點進行最優路徑規劃，左右下角數字之和為上面的數字，本實驗里有兩個函數，一個是g（n），一個是h（n），這兩個數分別是它倆的值，它倆之和為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小車路徑規劃地圖的構建探討。

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