聯合編譯：章敏、陳圳
現有的啟發式搜尋算法不能在找到完整的解決方案之前采取行動，是以它們不适用于實時應用。是以我們提出了一種極大極小前向搜尋（minimax lookahead search）的特殊情況來處理這一問題，還提出了一種能顯著提升該算法的效率的類似于 α-β 剪枝的算法。此外，我們還提出了一種名為 real-time-a* 的新算法，該算法能用在動作必須被确實執行而不僅僅是模拟時來進行搜尋。最後，我們檢查了計算和執行成本之間的權衡的性質。
啟發式搜尋是人工智能領域一個基礎的問題解決方法。對于大多數ai問題，解決方法所需的步驟序列可以是不知道先驗的，但它必須由一個系統反複試驗決定探索替代方法。所有的這些要求構造一個搜尋問題——一系列的狀态，一系列狀态映射到狀态的操作員，一個初始狀态，和一系列目标狀态。這個任務典型的問題是：找到一個最廉價的操作員将初始狀态映射到目标狀态。使用啟發式評估函數（一般不會犧牲最優解），很大程度上降低了搜尋算法的複雜性。計算和評估從給定狀态到目标狀态最實惠方法的支出時，啟發式函數相對來說更實惠。
ai文學界在搜尋問題方面共同的例子是eight puzzle和其相對較大的fifteen puzzle。eight puzzle由一個3x3的序列框組成，包含8個編号棋子和一個稱為“空白”的空位置。法定操作人員水準或垂直從相鄰的位置滑動棋子。其任務是在一個随機的初始狀态下重新排列棋子到所需的設定。該問題有一個共同的啟發式函數稱為“曼哈頓距離”（（manhattan distance）。它以計數的方式進行計算，對于每一個不再其目标位置的棋子，沿着網格移動的數量是遠離它的目标位置，并且總計所有棋子的值，不包括空白的。
一個實時的例子如網絡路徑自動導航，或在任意地形從一個初始位置到所需的目标位置。這是典型的找出目标和初始位置之間最短路徑問題。針對該問題的一個典型的啟發式評估函數是，從給定位置到目标位置的空間直線。
最著名的啟發式搜尋算法是a*。a*是計算哪一個點f（n）是最好的首選最優搜尋算法，g（n）是搜尋該點的實際總支出，而h（n）是搜尋該點解決方法的評估支出。當啟發式函數可被采納時，a*有着一個特性，即它總是可以找到問題的最優解決方案。例如，從來都不會高估解法的實際支出。
iterative-deepening-a*( ida*)是改良版的a*，它降低了從指數到線性實踐的空間複雜度。ida*進行了一系列深度優先搜尋（depth-first searches），當邊界點的支出超過終止門檻值時，它的分支被截斷，f（n）=g（n）+h（n）。這個門檻值始于初始狀态的啟發式評估，并增加每個疊代到最小值（超過原來的門檻值）。ida*在最優解法方面和a*有着相同的特性，并且擴充相同執行個體的點，進一步說，就像是在一個指數樹上的a*，但是它僅使用線性空間。
a*和ida*共同的缺點是：他們在實踐中運作所發費的時間非常多。這是獲得最優解法不可避免的支出。如simon所注意到的一樣，然而，最優解法雖然相對稀少，但對于大多數的實時問題接近最優或者“滿意”的解法通常也能被完全接受。
還有一個相關的a*和 ida*的共同缺點是：他們在進行第一步之前必須搜尋所有的解法。原因是直到找到整個解法，且證明它至少和其它解法一樣好時，才可以保住第一步是最優的。是以，在現實世界中執行産生的解決方案的第一步之前，a*和ida*就在計劃或模拟階段運作完成。這大大限制了這些算法應用于實時應用。
在該部分，我們展示了幾個實時問題非常重要的特性，這些特性在任何的實時啟發式搜尋算法中都要被考慮到。
第一個特性是：在實際問題中，問題解決者必須面對有限的範圍。這主要是由計算或者資訊的限制造成。例如，由于fifteen puzzle的組合方式猛增，在dec20使用“曼哈頓距離”（manhattan distance）的ida*算法時，每一個問題平均發費的時間為5個小時。在大規模一點的難題将無法解決。為了防止沒有完全細節映射的消極影響，搜尋範圍（疊代，在該情況下）取決于資訊的限制——視覺相同能夠看到多遠。盡管有着精準的映射，細節的等級仍然受到限制。這引發了“fuzzy horizon”，其中地形知識的細節等級是到問題解決者距離的遞減函數。
一個相關的特性是：在實時設定中，在他們的最終結果已知之前必須采取行動。例如，下棋時，要求棋子必須移動以延長方向選擇的搜尋範圍。
最後最重要的一個特性是：行動的支出和計劃的支出可以用相同的發生表達，引起了兩個之間的權衡。例如，如果fifteen puzzle的目标是，以最短時間解決問題的同時移動數量最少，那麼相對于在機器中模拟運動，我們會量化時間進行實際的實體運動，然後原則上我們會找到一個算法，通過平衡“思考”時間和“行動”時間最小化解法的總時間。
在該部分，我們展示了一個簡單的算法，用于在單代理（single-agent）問題的啟發式搜尋（将前面所有的特性包括其中）。這相當于雙玩家遊戲（two-player game）極小極大值算法的情況。這并不新奇，因為雙玩家遊戲分享有限搜尋範圍的實時特性，并且在最終結果已知之前采取行動。首先我們設想所有的操作者有着相同的支出。
算法從目前狀态向前搜尋到固定深度（取決于計算或者資訊可利用的單體資訊），并且應用啟發式評估函數到搜尋前沿的點。在雙玩家遊戲中值會被極小極大化到樹中，緻使玩家之間交替移動。在單代理（single-agent）設定中，由于單代理控制所有的運動，是以每一個點的備份值是它下一步點的極小值。一旦目前狀态的下一步備份值被決定，就會在該方向上進行單獨的最優下一步運動，并且這個過程都是這樣重複的。不直接移動到前沿點極小極大值的原因是：遵循最小承諾的政策。在該設想下，在安排第一步行動之後，增加的資訊（來自于擴充搜尋前沿）或許會比第一搜尋更能影響到第二步的選擇。為了與極小極大值搜尋對比，我們稱該算法為極小值搜尋。
注意：除了交錯模型，兩個方法的搜尋過程完全不同。極小極小前瞻搜尋在模拟模型中進行，其中假設的移動不會實際執行，僅僅在機器中進行模拟。在一個完整的前瞻搜尋之後，找到最優移動由問題解決者在現實中進行運動。随後在目前狀态進行另一個前瞻搜尋，和實際運動。
在很多普遍的情況中，操作者有着不統一的支出，我們必須計算目前為止路徑的支出，以便啟發式評估剩餘支出。為了進行該計算，我們采用了a*支出函數f（n）=g（n）+（h）。算法随後前進固定量的移動，并且備份每一個前沿點的最小值f。替代方案向前搜尋固定量的移動，同時會向前搜尋一個固定的g（n）支出。我們在該設想下采用原先的算法，即在計劃階段計算支出是移動數量的函數，而不是實際執行移動支出的函數。
為了確定終止，必須注意防止問題解決者實際所走過的路徑無限循環。這已經被完成了， 通過維持這些狀态（問題解決者實際通路過和移動過的狀态）的closed表，和從初始狀态到目前路徑點的open堆棧。移動到closed狀态是結果輸出，随後open堆棧用于反向追蹤直到移動可以用于一個新狀态。這種保守的政策禁止算法毀滅以前的運動，除非它遇到一個死胡同。該限制在後文中将被移除。
到這一步自然而然的會問道：是否每一個前沿點都必須被檢測以便找到極小值支出，或者是否存在一個 α-β 剪枝的算法，在探索本質上更少的點時，允許同樣的決定。如果我們的算法隻使用前沿點評估，然後一個簡單的反觀點可确定沒有這樣的剪枝算法存在，因為決定最小值支出前沿點要求檢測每一個點。
然而，如果我們允許啟發式評估内部點，且支出函數是單調函數，那麼本質上的剪枝是可行的。如果支出函數f（n）不會遞減到初始狀态，那麼它就是單調函數。f（n）=g（n）+h（n）的單調性和h（n）一樣，或遵循三角形不等式，滿足最自然産生的啟發式函數的屬性，包括曼哈頓距離（manhattan distance）和空間線距離（air-line distance）。此外，如果啟發式函數是容許的但不單調，那麼一個容許的，單調的函數f（n）可以顯然是以其路徑的最大值進行建構。
一個單調f函數允許我們應用分支界定法（branch-and-bound）在不影響決定的情況下，大量減少檢測點的數量。類比于α-β 剪枝算法我們稱該算法為α剪枝算法，如下：在生成樹的過程中，保持在一個變量α（它是搜尋範圍中目前所有遇到點的f最低值）。當每一個内部點生成時計算f的值，并在f的值等于α時切斷相應的分支。可以這樣做的原因是因為函數是單調的，前沿點f的值隻能從更好或者等于該點支出的點開始遞減，并且不可以影響到運動，因為我們僅移向最小值的前沿點。當每一個前沿點生成時，同樣計算f值，如果它小于α，就用更小的值代替α，并且進行搜尋。
在使用曼哈頓距離（manhattan distance）評估函數的fifteen puzzle實驗中，α剪枝算法通過遠遠多于蠻力分支因子（brute-force branching factor從2.13到1.41）的平方根減少了有效分支因子。在相同數量的計算時，它的效果比兩倍的搜尋範圍效果還好。例如，如果計算源允許在移動時檢測上百萬的點，那麼β壓迫算法可以搜尋深度為18的移動，而α剪枝算法允許搜尋将近兩倍的深度（40步移動）。
α剪枝算法中，α剪枝算法的效率可以通過node ordring進行提升。該想法指令每一個内部點的繼承點增加f值的次序，希望找到更早的找到前沿點的最低支出，并更快的裁剪跟多的分支。
盡管這兩種算法是各自發展的，最小化α剪枝算法非常類似于iterative-deepening-a*的單獨疊代。唯一的不同點是在α剪枝算法中，中止門檻值由前沿點最小值動态決定和調整的，而不是由先前在ida *中疊代預先靜止和設定的。
目前為止我們設想了，行為一旦被執行除非遇到死胡同，不然它不會被逆轉。——主要的動機是阻止問題解決者無限循環。我們現在解決的問題是：如何在它有用進行傳回，而不是死胡同時傳回，同時仍然反正無效循環。基本想法非常簡單。從狀态（加傳回的支出）到狀态（少于從目前狀态向前移動的評估支出）評估解決方法時，它應該傳回到原來的狀态。real-time-a*是實施這一基本想法非常有效的一個算法。
最小值前瞻算法是控制搜尋仿真階段的算法，rta *是控制搜尋執行階段的算法。是以，它獨立于所選擇的模拟算法。簡單的說，我們假設：極小極小前瞻深度是封裝在計算h（n）内部的，是以，變得簡單，更準确，和更昂貴的方式計算h（n）。
rta *中，點n的優點是f（n）=g（n）+h（n），如a *中的一樣。然而，不像a *的是，rta *中g（n）的了解是點n到問題解決者目前狀态的距離，而不是原來的初始狀态。rta *隻不過是給出略有不同支出函數的最好的第一搜尋。原則上，它可以通過儲存原先所有通路過的點的h值open表實作，并且每一次移動，都會更新open上所有狀态的g值，以便準确反映它們到新的目前狀态的實際距離。然後在每一個移動循環，問題解決者通過g+h的最小值選擇下一個狀态，向它移動，并且再一次更新open上所有狀态的g值。
這種單純實作的缺點是：1）在open清單中時間的大小是進行線性移動的。2）不是非常的清楚如何更新g的值，3）不清楚如何如何從open中選擇下一個目标節點的路徑。有趣的是，在恒定的時間中，每次隻使用圖中本地的資訊移動就可以解決這些問題。想法如下：從給定的目前狀态，相鄰的狀态可以産生，啟發式函數通過前向搜尋增強（這适用于所有情況）然後，每一個鄰近狀态的邊緣支出會增加這個值，産生目前狀态每一個鄰域的f值。有着極小f值的點是從新的目前狀态和移動（已經被執行的狀态）中選擇出來的。與此同時，下一個f值儲存在以前的目前狀态。
這代表了通過回到原狀态來解決此類問題所需的代價h。接下來，新狀态下的新鄰近點就産生了，而它們的h值也就此進行計算，并且所有新狀态下的鄰近點的邊成本包括之前的狀态的都會加入h值中，導緻了所有鄰近狀态一系列的f值。再一次，節點值最小的會被除去，第二優的節點值會儲存在舊狀态的h值中。
注意到rta不需要吧open和closed清單分開，之前評價過的節點值的單一清單就以足夠。表的規模與移動的步數成線性關系，因為前饋搜尋僅僅隻會保留根節點值。并且運作時間也與步數成線性關系。原因在于盡管前饋研究所需時間與研究的深度成指數增長的關系，但研究深度會受到常數的限制。
有趣的是，人能夠建立一個例子證明rta*在在同一領域内追溯任意次數。例如，在圖1中最簡單的strighthne圖，最開始的狀态是節點a，所有的edge有一個總體的值，而在每一個節點下的數值就代表了這些節點的啟發式評價。因為前饋隻會讓例子變得更加複雜，我們會假設沒有前饋能去計算h值。并在節點a開始，f(b)=g(b)+h(b)=1+1=2，但f(c)=g(c)+h(c)=1+2=3。是以，問題求解程式移向節點b，并把節點a遺留在h(a)=3的資訊狀态。接下來，節點d會在f(d)=g(d)+h(d)=1+4=5結果下進行評價，是以節點a就變成了f(a)=g(a)+h(a)=1+3=4的結果。是以問題求解程式就移回了節點a，而在節點b之後的h(b)=5。基于此點，f(b)=g(b)+h(b)=1+5=6，并且f(c)=g(c)+h(c)=1+2=3，導緻問題求解程式又移到了節點c，讓在節點a之後的h(a)=6。閱讀者會迫不及待的把執行個體繼續進行下去以見證問題求解程式不斷地往返，直到達到目标。其原理不是在于它是一個無限的環，而是在于當它每改變一次方向，就能比之前更深入一步，就能收集到更多關于空間的資訊。這看似不合理的行為是由合理的行為在有限的探索界限和病理空間内産生的。
不幸的是，rta*的追溯能力不能作為fifteen puzzle和manhattan distance評價函數。因為在于manhattan distance在一次移動中隻會改變一次，而這會讓rta*在追溯一次就終止。
除了算法的效率之外，由最小前饋搜尋所帶來的解決方法長度也是關注的焦點。最正常的期待是希望随着解決長度的減少而深度卻會增加。在帶有fifteen puzzle的實驗中使用manhattan distance，結果顯示是期待是正确的，但并不一緻。
fifteen puzzle的一千個原始解決狀态是随機産生的。對于每一個原始狀态，阿爾法剪枝算法的最小值是在搜尋深度在1步到30步之間。為找到解決方法，會不停的進行移動，是以步數達到一千步也是有可能的，是以為防止步數過長，會對所有的結果步數進行記錄。圖2顯示的是在所有超過千步的解決方法中平均解決的長度以及搜尋限制的深度。底部的線顯示的是在100個不同的原始狀态中53個平均最優步驟。最優解決方法的長度是使用ida*進行計算的，需要幾周的cpu時間去解決上百的原始狀态。
曲線的大體形狀肯定了最初的假設增加搜尋範圍限制能減少解決運算成本。在深度為25時，平均的解決方法的長度隻在一個因素上優于最優解決方案的平均長度。這一結果的實作是通過隻在每一步隻搜尋6000個節點，或是整個解決過程隻搜尋6000,000個節點。這一過程能在hewlett-packard hp-9000工作站中隻需cpu一分鐘的運作時間。
但是在深度為3,10或是11時，增加的搜尋限制會導緻解決方法長度的輕微增加。這一現象首先是在有兩個玩家的遊戲中和dana nau命名的pathology中發現的。他發現在某些遊戲中，增加搜尋深度但遊戲結果還是較差。直到，在真實遊戲中進行路徑觀察。
盡管在涉及到大量問題時路徑的影響會相對來說較小，但在單個問題上，其影響還是很重要的。在多數案例中，通過一步來增加搜尋的深度會讓解決方法的長度增加上百步。
為更好的了解這一現象，我們對“決定品質”進行試驗，這與解決方法品質是相對應的。它們之間的差別在于一個解決方法包括大量的個别決定。解決方法的品質是由解決方法的長度決定的，決定的品質是由最優步選擇所花的時間決定的。因為在一個狀态下必須知道最優步才能确定決定的品質，是以要選擇較小或是叫溫順的eight puzzle，并用相同的manhattan distance評價函數。
圖2：搜尋限制vs 解決長度
在這個情況下，成千上萬原始狀态是随機産生的。我們不會探索整個解決方法，因為這是由最小算法産生的；我們僅僅最考慮原始狀态下的第一步移動。在不同的搜尋限制和不同起始狀态下，第一步的最優步的決定時間都會被記錄下來。搜尋限制的範圍從一步到低于最優選擇的步數。圖3展示的是錯誤率和搜尋限制。随着搜尋限制的增加，最優步數也會随之增加。是以，pathology并未在決定品質方面出現。
如果決定的品質能随着搜尋的深度而增加，那為什麼解決方法的品質會如此飄忽不定？其中一個原因是當犯錯的幾率增加時，就整體解決成本而言，個别錯誤的代價就會變高。這一點在追溯僅在遇到死胡同才會發生時表現的尤為明顯。
圖3：搜尋限制vs.決定品質
另一個錯誤的根源在于節點位于備選方案之中。當資訊不确定是必須确定移動，但連接配接不應随意破壞。更加普遍一點，當基于不準确的啟發評價時進行處理，兩個數值更加接近函數的準确度不應該被認為是虛拟的連接配接，而對于這一的處理也應是把它們看做是無法區分的。為解決這一問題，連接配接和虛拟連接配接必須在第一眼就認出來。這也就意味着當數值超過最初由錯誤因素所影響的最好結果之後，阿爾法剪枝算法必須改變。這會導緻由此産生的節點的增加。
一旦确認節點之後，必須破壞它。最理想的方法是在候選方案之中實施更深度的二次搜尋，直到連接配接崩壞。然而，這一二次搜尋也有深度的限制。如果二次搜尋達到了深度限制，而連接配接沒有崩壞，虛拟連接配接會在較低成本下解體。
用前饋搜尋檢查啟發式評價函數，根據搜尋的深度不同，更準确的啟發式函數能生出一系列啟發式函數。而這一系列的函數計算複雜性和準确度都不一樣，但一般更加昂貴的函數就算的要更準确一些。
選擇哪一個評價函數去平衡搜尋成本和決定成本。時間最小化依賴于相關的計算成本和決定，但一個合理的模式是彼此都是互相成線性關系。換一種說法如果我們假設在實際中運用一個運算操作的成本是在所有模拟實驗中運用的總和。
圖4顯示出與圖2相同的資料，但是水準軸線與每一步節點的産生數量成線性關系，這與搜尋的深度也有很大的關系。這一曲線圖顯示了計算—執行在最初某種程度上是有利的，例如小量的計算增加會帶來大量的決定成本減少。但是，當達到減少轉折點時，決定成本上的減少需要大量的計算。這一影響還有可能比當初的還要大，因為長度決定過程需要任意一百步。不同的計算成本和執行之間的關系會改變兩個軸之間的關系，但不會改變基本的曲線的基本形狀l。
現存的單代理啟發式算法不能在實際中進行運用，因為計算成本在停止計算之前都無法預知。最小化的前饋搜尋是對于這類問題的最好解決方法。此外，α剪枝算法能提高算法的有效性，但卻不影響決定的執行。此外，實時α算法解決了當遇見更有希望的算法而放棄目前算法的問題。大量的模拟顯示搜尋深度增加一般會提高決定的品質，但是出現與之相反的情況也是正常的。為避免虛拟連接配接對于決定品質産生決定性影響，附加算法也是很必要的。最後，前饋算法能看成是産生一系列具有不同準确度和計算難度的搜尋。決定品質和計算成本之間最初是互相支援的關系，但到同時也會迅速達到一個收益遞減的點。
哈爾濱工業大學李衍傑副教授的點評：由于傳統單智能體啟發式搜尋算法，如a*算法，計算量比較大，且需要搜尋完最終結果後才能執行，因而不适用于實時性要求比較高的場合，為此，這篇論文研究了實時啟發性搜尋的問題，文中利用最小最小（minimin）前瞻搜尋來避免傳統啟發式搜尋所存在的前面所述問題，同時利用alpha剪枝方法來改進算法的效率，這兩種思路的結合實際上是ida*算法的一個自适應版本，即剪枝門檻值随搜尋節點的變化自适應地動态調整，而非像ida*算法那樣靜态預先設定。此外，文中給出了一種實時的a*算法來實作目前搜尋路徑到更好的路徑的轉換。
本文作者：章敏