1、選取日期鍵入文檔副標題 | 劉紹翰nuaa未知環境的動態路徑規劃 度量距離灰度化四連通和8連通。第一章、靜態搜索與A*算法很多時候，我們需要在一個圖中尋找一條從源點到目標節點的最短路徑，我們稱之為路徑規劃。搜索算法主要分為，盲目搜索和啟發式搜索，它們的一個作用是能夠從解空間中需找一條從源點到目標節點的最短路徑。啟發式搜索是在搜索的過程中，參考一定的指標函數來決定搜索的策略。迪杰斯特拉算法，類似于廣度優先遍歷，利用源點到當前節點的代價值作為指標，其一定可以獲得從原點到目標節點的最短路，但是其訪問的節點數很多。而最好優先搜索，采用離標節點的距離作為搜索的代價參考值，貪心選擇最小的擴展節點，也可以獲

2、得最短路徑，而且其搜索的節點數目大大減少。 圖1 迪杰斯特拉算法 圖2 最好優先搜索算法當地圖中包含障礙物時，迪杰斯特拉算法，仍然可以獲得最短路徑的路徑，最好優先搜索的節點盡管少，但是其不能獲得最優解。 圖3 迪杰斯特拉算法 圖4 最好優先搜索算法而A*算法，參考了從原點到當前節點的代價值和當前節點到目標節點啟發值，綜合了迪杰斯特拉算法和做好優先搜索算法優點，在有障礙物和無障礙物的地圖上，可以像迪杰斯特拉算法一樣求得最短路徑同時，同時能夠像最好優先搜索一樣減少搜索范圍，減少搜索節點的數目。 圖5 無障礙物時A*路徑規劃 圖6 有障礙物時A*路徑規劃算法經典的迪杰斯特拉算法可以求得最短的路徑，而

3、啟發式搜索A* 算法，不但可以求得最短路，而且可以使得搜索的范圍大大減少，上述算法是傳統的靜態路徑規劃算法，其規劃的前提條件是已經知地圖的結構。A*算法屬于離線事先規劃，在規劃完畢之后，可以沿著最優路徑移動，不是在線規劃，不能一邊規劃一邊移動。A*算法的基本理論A*算法又叫做啟發式搜索算法，具有悠久的歷史，其啟發函數f=g+h。其中g表示從原點到當前節點已經付出的代價，好表示從當前節點到目標節點的啟發值。1) A*算法必須滿足h(x)<=h*(x)，其中h*(x)是實際的啟發值，h*(x)在實際中通常是無法事先得知的，但是這個條件是很容易滿足，只要滿足該條件，一定能夠獲得最優解。2) 如

4、果最短路徑長度為C*, 則在算法結束前，open表中至少有一個節點n, 滿足 f(n) <= C*. 這個性質可以這樣理解， 因為最短路徑存在， 我們不妨設它為: source->a->b->c->.->n->.->goal. 且在當前時刻，路徑中在節點n前的節點都在closed表中，即已經擴展了，而節點n自己在open表中（注意：算法結束前任意時刻都有這樣的節點n存在）。 則由于該條路勁是最短路徑，我們可以知道此時在open表中的n的 g(n)值已經是準確值, 即最小值了。而 f(n) = g(n) + h(n) = g*(n) + h(n)

5、<= g*(n) + h*(n) = C* . (最后一個式子取等號是由于n在最短路徑上) 有了這個性質，我們就知道，當A*算法擴展到目標節點時，必有f(goal) = g(goal) <= C* (即 = C*)。否則, 如果f(goal) > C*,由于目標節點是被擴展節點, 則open表中其他任意其他節點t, 都有f(t) >= f(goal) > C*, 和性質1 矛盾。3) 擴展新節點時很容易出現重復節點的問題，從上面的偽代碼可以看出， 如果新擴展節點已經存在于closed表中， 且f值比表中節點的f值還要小的話，則除了更新該節點f值，還需要重新擴展該節

6、點，這簡直就是把人從棺材里拖出來。 但是如果h函數滿足相容性，這一步就可以省掉了。所謂相容性就是指對任意節點s1,都滿足： h(s1) <= h(s2) + c(s1,s2) (其中c(s1,s2)是指從s1轉移到s2的代價)有這個性質我們在不等號兩邊加上g(s1), 則有 g(s1) + h(s1) <= h(s2) + g(s1) + c(s1,s2)。 如果我們此時擴展s1, 而s2又是能被s1擴展的節點，則由這個式子我們得到 f(s1) <= f'(s2). (若s2之前就已經被擴展出了，則當前的f(s2)可能比f'(s2)小) 這個式子的意義在于由當

7、前節點進行擴展這個方案下得到的節點的f值總比當前擴展節點的f值大（子節點總比父節點費用高），而我們每次又是選擇一個具有最小f值的節點進行擴展，然后讓其進入closed表，這就使得，進入closed表的每個節點的f值是遞增的，并且之后不可能出現比closed表中最大f值。還要小的節點被擴展出來（感覺有點問題），因此擴展出的新節點不必再拿到closed表中檢查更新了。4) 可以得知有如下條件成立：f(y)=g(y)+h(y)=g(x)+C(x,y)+h(y)>= g(x)+h(x)即代價函數f的值是非遞減的。5) 下面我們來討論一下h函數的相容性 ，由于C(x,y)為從 x到y的實際代價，因

8、為h的估計小于實際的代價值，h(x)<h*(x), h(y)<h*(y),也可以說h*(x)-h*(y) =C(x,y)> = h(x)- h(y)。？6) f的滿足三角不等式：h(s,s)<=h(s,s)+h(s,s)<=h(s,s)+h(s,s) +h(s,s)<=.可以一直展開下去。7)A*算法的實現眾所周知，對圖的表示可以采用數組或鏈表，而且這些表示法也各也優缺點，數組可以方便地實現對其中某個元素的存取，但插入和刪除操作卻很困難，而鏈表則利于插入和刪除，但對某個特定元素的定位卻需借助于搜索。而A*算法則需要快速插入和刪除所求得的最優值以及可以對當前結

9、點以下結點的操作，因而數組或鏈表都顯得太通用了，用來實現A*算法會使速度有所降低。要實現這些，可以通過二分樹、跳轉表等數據結構來實現，我采用的是簡單而高效的帶優先權的堆棧，經實驗表明，一個1000個結點的圖，插入而且移動一個排序的鏈表平均需500次比較和2次移動；未排序的鏈表平均需1000次比較和2次移動；而堆僅需10次比較和10次移動。需要指出的是，當結點數n大于10，000時，堆將不再是正確的選擇，但這足已滿足我們一般的要求。還有一種更好的方法是Hot Queues，而且這種方法還可應用于Dijkstra算法以降低其復雜度。當我們移動估價函數值為f的結點時，我們插入值為f+(<=C)

10、(若>=0將意味著估價函數是有效的，反之亦然)，常量C為從一個結點到相鄰結點的權的最大改變。同時我們用一些“容器”來保存估價函數值的子集（這正如o(n)的排序算法的思想）,例如，當有10個“容器”時，堆將平均只包含1/10的估價值。因而這將比用堆更為有效。A*算法的變形a. Beam Search在A*算法中需要保留所有的結點，這將使得時間和空間的消耗都很大，而Beam Search方法對結點數作出限期，當結點數過多時，它會將一些不(大)可能為最優的點排除，從而降低時間和空間的要求，但需要說明的是，由于在排除結點后需對結點排序，當排序的工作量大于排除點后所節省的工作量，則該方法無意義。b

11、. Iterative deepening這是一種在人工智能中常使用的方法，它首先產生一定值作為搜索的深度，當未能搜索到解的時候，對搜索的深度增加，繼續搜索。c. Dynamic weighting這種算法是基于這樣的考慮，即在搜索初期以速度優先，在搜索后期以準確度優先(這可通過對搜索初、后期賦予不同的權值來實現)。即：f(p) = g(p) + w(p) * h(p)d. Bidirectional search這種算法從起點和終點同時應用A*算法，直到有結點相遇。其缺點在于復雜度太大，一般僅用于復雜的圖形。e. Hierarchical A*這種算法思想是將搜索過程化，對每個簡單過程求解從

12、而得全局較優解。正如當我們到另一城市時，可分解為從家里“搜索”一條路徑至車站，再從車站“搜索”一條路徑到另一城市，當我們從家里出發時，需要考慮的是怎樣盡快地到達車站，而不是怎樣盡快地到另一城市。f. Dynamic A*(D*)這種算法主要用于人工智能和機器人技術。由于A*算法一開始要求獲得全部信息，而這在實際中有時是不可能的，而D*算法就是在假定信息不完整的前提下應用A*算法，但它會隨著得到信息的增多而不斷改進結果，這就決定了它對空間的要求相當高，因為它需要保留以前的所有獲得信息。第二章、動態路徑規劃在很多時候，地圖是未知的或者地圖在發生變化、或者需要一邊執行一邊規劃。比如電子游戲中（帝國時代、黑暗王朝、橫掃千軍），經常需要找到一條好的路徑避免