深度優(yōu)先搜索算法和A*算法在迷宮搜索中的仿真研究

劉 翔，龔道雄

LIU Xiang,GONG Dao-xiong

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

0 引言

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

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

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

1 實驗研究

1.1 實驗研究方法

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

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

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

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

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

1.3 A*算法

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

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

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

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

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

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

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

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

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

2 仿真實驗分析

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

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

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

圖2 目標點偏差圖

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

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

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

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

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

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

3 結(jié)論

本文通過仿真實驗比較了A*算法與深度優(yōu)先搜索算法在未知迷宮中的搜索應用，仿真實驗中還同時比較了三種帶有不同啟發(fā)式函數(shù)的A*算法的應用，通過仿真實驗比較得出的結(jié)果是：總體來說，未知迷宮中，在僅知道目標點的大概位置的情況下，進行搜索時，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)先搜索算法在未知迷宮中進行搜索時是盲目的，而A*算法在搜索過程中通過引入啟發(fā)式信息來實現(xiàn)向目標節(jié)點移動的判別，無需遍歷地圖，使得計算復雜度相對較小，實現(xiàn)了快速、高效。但是，這也導致搜索的過程中排除了大量節(jié)點，而由于經(jīng)驗及實際問題的復雜性，引入啟發(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*算法的改進及其在路徑規(guī)劃中的應用"[J].測繪與空間地理信息,2009,32,6：208-211.

[5] 張仁平,周慶忠,熊偉,"A*算法改進算法及其應用"[J].計算機系統(tǒ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.