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

劉 翔，龔道雄

LIU Xiang,GONG Dao-xiong

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

0 引言

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

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

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

1 實驗研究

1.1 實驗研究方法

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

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

而在本次仿真實驗中，為了能夠比較真實的模擬真實環境，我們人為的讓目標點坐標產生了一定的偏差，并且讓這個偏差值隨著機器人越來越靠近目標點而變得越來越小。

1.2 深度優先搜索算法

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

1.3 A*算法

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

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

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

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

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

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

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

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

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

2 仿真實驗分析

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

圖1 迷宮仿真環境

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

圖2 目標點偏差圖

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

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

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

表1 仿真實驗比較結果

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

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

3 結論

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

[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].測繪與空間地理信息,2009,32,6：208-211.

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