劉 翔，龔道雄

LIU Xiang,GONG Dao-xiong

（北京工業(yè)大學(xué) 電子信息與控制工程學(xué)院，北京 100124）

0 引言

在現(xiàn)代社會中，火災(zāi)、爆炸、坍塌事故常有發(fā)生，救援過程中因建筑情況不清，意外坍塌事故等導(dǎo)致救援人員遇難的慘劇時有發(fā)生。為避免此類事故，應(yīng)用機器人及時探知險情和受困人員的情況和位置有著極大的應(yīng)用意義。論文中將機器人所面臨的搜救環(huán)境抽象為一個迷宮，而搜救就是要在迷宮中先搜索到目標(biāo)物并帶著目標(biāo)物返回到出發(fā)點處。

迷宮的種類[1]有很多，而用的比較普遍的是Perfect迷宮，所謂的Perfect迷宮是一種沒有任何環(huán)路且沒有任何不能到達(dá)的區(qū)域。本次實驗中，所選擇的迷宮環(huán)境都為Perfect迷宮。目前，經(jīng)典的搜索路徑算法有D*算法和A*算法，而在迷宮中運用最為普遍的搜索算法是泛洪算法，而泛洪算法是一種基于改進(jìn)的深度優(yōu)先搜索算法[2]。泛洪算法在搜索過程中多次遇到目標(biāo)點，但它的目的是要從這些路徑中找到最快到達(dá)目標(biāo)點的一條路徑，原始的泛洪算法不適合本次實驗中的搜救應(yīng)用，于是，我們在實驗中是用深度優(yōu)先搜索算法進(jìn)行比較研究。Takayuki Goto，Takeshi Kosaka研究了A*以及D*算法在ITS（智能運輸系統(tǒng)）和機器人路徑規(guī)劃中的應(yīng)用，確定了A*算法以及D*算法的優(yōu)勢[3]。而對于A*算法中啟發(fā)式函數(shù)的選取，已有多種選擇。在啟發(fā)式函數(shù)的選取上，有對A*算法估價函數(shù)所出現(xiàn)的問題，將距離和角度進(jìn)行歸一化處理[4]；也有對當(dāng)前節(jié)點進(jìn)行評估的思想上，增加了最短路徑中當(dāng)前節(jié)點的父節(jié)點，并對當(dāng)前節(jié)點與終節(jié)點的距離進(jìn)行了評估，這使得A*算法的搜索方向更加趨向終點，從而提高了搜索速度[5]；還有一般情況下對啟發(fā)式函數(shù)的設(shè)定選擇為兩點間的歐幾里得距離[6]；

本次實驗中，將分別對含有三種不同啟發(fā)式函數(shù)的A*算法與深度優(yōu)先搜索算法用于迷宮中進(jìn)行比較仿真研究。

1 實驗研究

1.1 實驗研究方法

實驗研究目的是將算法用于現(xiàn)實搜救中，既然是為了搜救，那么時間是關(guān)鍵，搜索迷宮所用時間的長短就成為評價算法優(yōu)劣的主要因素。對于機器人來說，所處的迷宮環(huán)境是未知的，它只能通過傳感器感測到目標(biāo)點所在的大致位置，然后根據(jù)算法一步一步的搜索到目標(biāo)物。從出發(fā)點處找到目標(biāo)物時所耗的時間我們記錄為搜索迷宮所用的時間，當(dāng)然，搜救的目的不僅僅是為了找到目標(biāo)物，同時是需要在找到目標(biāo)物后將目標(biāo)物帶回至出發(fā)點處。從目標(biāo)點返回到出發(fā)點時，如果沿之前的原路返回，那就會浪費很多沒必要的時間，使搜救時間變長，所以我們要做的工作是要將之前的走過的路徑進(jìn)行優(yōu)化，使機器人帶著目標(biāo)物返回出發(fā)點時不用走“冤枉路”，從而節(jié)省搜救時間。

真實環(huán)境中，目標(biāo)物在目標(biāo)點處通過敲打墻壁或地面等發(fā)出聲音，模擬“呼救”，從而讓機器人通過傳感器感知到目標(biāo)物。但由于外界因素（例如：傳感器的精度，迷宮環(huán)境中障礙物對聲音的阻礙作用等）的干擾會導(dǎo)致機器人只能判斷出目標(biāo)物的大致位置，這個大致位置是隨著機器人離目標(biāo)物越來越近而會越來越精確，直至找到目標(biāo)物。

而在本次仿真實驗中，為了能夠比較真實的模擬真實環(huán)境，我們?nèi)藶榈淖屇繕?biāo)點坐標(biāo)產(chǎn)生了一定的偏差，并且讓這個偏差值隨著機器人越來越靠近目標(biāo)點而變得越來越小。

1.2 深度優(yōu)先搜索算法

所謂“深度優(yōu)先”，即：狀態(tài)樹的生長或展開，首先沿狀態(tài)樹的深度方向進(jìn)行。深度優(yōu)先搜索算法需要記錄下狀態(tài)樹的生長過程，深度優(yōu)先搜索算法是一種盲目的搜索算法，搜索中可能很多次的搜索到目標(biāo)點，深度搜索算法通過不斷剪枝，尋找出一條從起始點到目標(biāo)點最近且最省時的路徑，即深度優(yōu)先搜索算法也是一種全局的搜索算法，這樣的深度優(yōu)先搜索算法運用到未知迷宮搜救中是沒有意義的。而本次實驗中，深度優(yōu)先搜索算法是以找到目標(biāo)物為目的，沒有剪枝的步驟，只要搜索到目標(biāo)物，迷宮的搜索過程就成功退出。

1.3 A*算法

A*算法是人工智能中的一種搜索算法，是一種啟發(fā)式搜索算法，它不需遍歷所有節(jié)點，只是利用包含問題啟發(fā)式信息的評價函數(shù)對節(jié)點進(jìn)行排序（Node Ordering），使搜索方向朝著最有可能找到目標(biāo)并產(chǎn)生最優(yōu)解的方向。它的獨特之處是檢查最短路徑中每個可能的節(jié)點時引入了全局信息，對當(dāng)前節(jié)點距終點的距離做出估計，并作為評價節(jié)點處于最短路線上的可能性的度量。A*算法中引入了評估函數(shù)，評估函數(shù)如下：

其中：n是搜索中遇到的任意狀態(tài)。g(n)是從起始狀態(tài)到n的代價。h(n)是對n到目標(biāo)狀態(tài)代價的啟發(fā)式估計。仿真實驗中，我們?yōu)锳*實現(xiàn)了三種啟發(fā)式函數(shù)，如引言中所述，一種啟發(fā)式函數(shù)為當(dāng)前點到目標(biāo)點的歐幾里得距離評估，我們定義為A*(1)；

即A*(1)算法的評估函數(shù)為：

其中啟發(fā)式函數(shù)h1(i)為當(dāng)前節(jié)點i到偏移目標(biāo)點的歐幾里得距離。

另一種啟發(fā)式函數(shù)在第一種的啟發(fā)式函數(shù)中增加了當(dāng)前節(jié)點的父節(jié)點到目標(biāo)點的歐幾里得距離評估，我們定義為A*(2)；

A*(2)算法的評估函數(shù)為：

j為當(dāng)前節(jié)點的父節(jié)點，h2(i)為已評估出的當(dāng)前節(jié)點i的父節(jié)點到偏移目標(biāo)點的距離。

最后一種啟發(fā)式函數(shù)是在第一種啟發(fā)式函數(shù)的評估上加入了當(dāng)前點到目標(biāo)點的角度評估，我們定義為A*(3)。

A*(3)算法的評估函數(shù)為：

2 仿真實驗分析

實驗的迷宮環(huán)境設(shè)置如下圖所示，將環(huán)境劃分為一個一個的柵格，紅色柵格為障礙物，白色柵格為通道，生成的10個迷宮均為Pefect迷宮，保證了整個迷宮中至少有一條從起點到目標(biāo)點的通道并不會產(chǎn)生環(huán)路。起點坐標(biāo)設(shè)為(0,0)，目標(biāo)點坐標(biāo)設(shè)為(24,24)。

圖1 迷宮仿真環(huán)境

由于機器人在檢測呼救信號時存在不準(zhǔn)確因素(例如：傳感器的精度，迷宮環(huán)境障礙物對聲音的阻礙作用等)，都會導(dǎo)致機器人在搜索時存在或多或少的誤差，所以仿真實驗中，為了比較真實的模擬現(xiàn)實搜救環(huán)境，我們對目標(biāo)點做了偏差處理，處理方式如圖2中所示。

圖2 目標(biāo)點偏差圖

其中，(xs,ys)為起始點坐標(biāo)，(x,y)為機器人當(dāng)前所在位置坐標(biāo)，(xt',yt')為偏移目標(biāo)點的坐標(biāo)，(xt,yt)為實際目標(biāo)點坐標(biāo)：

其中，k為權(quán)重值，通過實驗，取得k=40，l為當(dāng)前點坐標(biāo)到實際目標(biāo)點坐標(biāo)的歐幾里得距離，L為起始點到實際目標(biāo)點坐標(biāo)的歐幾里得距離，rand(-1,1)為隨機數(shù)，隨機數(shù)的取值范圍為(-1,1)。

實驗中，我們將三種A*算法分別在10個不同的Perfect迷宮中運行，統(tǒng)計結(jié)果如表1所示。

表1 仿真實驗比較結(jié)果

通過上表的結(jié)果分析可知，正如文獻(xiàn)3中所述，加入了父節(jié)點評估的A*算法（即A*(2)）在搜索時，提高了搜索速度；而在文獻(xiàn)2中所述的提高搜索速度的優(yōu)勢在本次實驗中沒有很好的體現(xiàn)出來，這是因為，在本次實驗中，我們加入了偏差值，對于A*(3)中的估價函數(shù)，不僅在距離上加入了偏差，同時在角度上也加入了偏差，從而使得A*(3)算法在本次搜索中沒有優(yōu)勢。從表中我們還可以得出，帶有啟發(fā)式函數(shù)的A*算法要優(yōu)于深度優(yōu)先搜索算法。

仿真實驗中，對于返回路徑的優(yōu)化，我們通過算法設(shè)定，讓機器人每走過一個柵格都將該柵格的狀態(tài)標(biāo)記為“已訪問”，被標(biāo)記為“已訪問”的柵格，機器人在搜索時就不會再走，除非遇到是死路的柵格。那么在算法中我們定義兩個狀態(tài)，一個狀態(tài)是通過柵格的次數(shù)(count)，另一個狀態(tài)是柵格是否為分支。當(dāng)機器人搜索到目標(biāo)點后，返回時只需要走count為1或者柵格為分支(isBranch=true)的路線就是返回的最優(yōu)路線，且不會走“冤枉路”。

3 結(jié)論

本文通過仿真實驗比較了A*算法與深度優(yōu)先搜索算法在未知迷宮中的搜索應(yīng)用，仿真實驗中還同時比較了三種帶有不同啟發(fā)式函數(shù)的A*算法的應(yīng)用，通過仿真實驗比較得出的結(jié)果是：總體來說，未知迷宮中，在僅知道目標(biāo)點的大概位置的情況下，進(jìn)行搜索時，A*算法要優(yōu)于深度優(yōu)先搜索算法，而A*算法在啟發(fā)式函數(shù)不同的情況下，搜索產(chǎn)生的結(jié)果也是不同的，從上述仿真實驗結(jié)果的比較中可以得出，A*(2)算法搜索路徑的時間是最優(yōu)的，其次是A*(1)和A*(3)算法。同時，從實物實驗比較結(jié)果也可以得出，帶有啟發(fā)式函數(shù)的A*算法要優(yōu)于深度優(yōu)先搜索算法。深度優(yōu)先搜索算法在未知迷宮中進(jìn)行搜索時是盲目的，而A*算法在搜索過程中通過引入啟發(fā)式信息來實現(xiàn)向目標(biāo)節(jié)點移動的判別，無需遍歷地圖，使得計算復(fù)雜度相對較小，實現(xiàn)了快速、高效。但是，這也導(dǎo)致搜索的過程中排除了大量節(jié)點，而由于經(jīng)驗及實際問題的復(fù)雜性，引入啟發(fā)信息的代價函數(shù)無法做到完全正確，這些被排除的節(jié)點可能就是最優(yōu)路徑的節(jié)點之一。

[1] http：//www.astrolog.org/labyrnth.htm.

[2] A.Francy Golda,S.Aridha,and D.Elakkiya,"Algorithmic Agent for Effective Mobile Robot Navigation in an Unknown Environment."Intelligent Agent & Multi-Agent Systems,2009,IAMA 2009.

[3] Takayuki Goto,Takeshi Kosaka,and Hiroshi Noborio,"On the Heuristics of A* or A Algorithm in ITS and Robot Path-Planning,"Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems,pp.1159-1166,Oct,2003.

[4] 史輝,曹聞,朱述龍,"A*算法的改進(jìn)及其在路徑規(guī)劃中的應(yīng)用"[J].測繪與空間地理信息,2009,32,6：208-211.

[5] 張仁平,周慶忠,熊偉,"A*算法改進(jìn)算法及其應(yīng)用"[J].計算機系統(tǒng)應(yīng)用,2009,98-100.

[6] Hiroshi Noborio,Keiichi Fhjimura,Yohei Horiuchi,"A Comparative Study of Sensor-Based Path-Planning Algorithms in an Unknown Maze,"Proceedings of the 2000 IEEE/RSJ International Conference on Intelligent Robots and Systems,2000,909-916.