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

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

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

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

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

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

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

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

②問(wèn)題域是有限的；

③所有結(jié)點(diǎn)的子結(jié)點(diǎn)的搜索代價(jià)值>0；

④h（n）≤h*（n），其中h*（n）為實(shí)際問(wèn)題的代價(jià)值。

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

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

一、曼哈頓距離

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

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

其中x和y為兩點(diǎn)坐標(biāo)。

二、歐式距離

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

（1-3）

三、契比雪夫距離

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

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

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

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

從圖1-11中不難看出，Dijkstra算法在進(jìn)行路徑搜索時(shí)，幾乎遍歷了整個(gè)搜索范圍，說(shuō)明Dijkstra算法在路徑搜索過(guò)程中付出了較大的計(jì)算量，致使搜索速度慢，對(duì)速度要求較高的移動(dòng)機(jī)器人來(lái)講該算法可能并不是十分適合。

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

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

作者簡(jiǎn)介：鄭曉耘，河北白沙煙草有限責(zé)任公司。