AI 筆記24 - A* search

Search

search適合有用來解決“一連串選擇形成的最終事物”，怎麼找出這“一串”選擇，以及找到最好的這一串。

problem formulation

這個其實就是從AMA book摘錄出來的，畢竟主講人Peter Norvig也是書的作者，不過Columbia AI課程已經講過，就節錄ppt畫面就好：

Uniform-cost search

這邊有些有趣的圖，首先uniform-cost是建築在step cost上，會形成lcountour
-based search:

但是我們幾乎得搜尋平均來說半個search space才能reach goal! 因為他是漫無目的的地毯式搜索(實際上bfs/dfs都是，因為沒有heuristics)。

如果要改善這種無效率，uniform cost search可以加上"先expand最接近goal的node"的approach變成greedy search:

不過他不一定會找到optimal path，例如導航可能沿著河流繞一大圈才到目的地:

A* search

主要的重點還是在A*，他保證optimality 但是又比uniform cost快速，如果搭配一個 "好的" evaluation function f。

A*簡單來說就是以下這張圖而已:

他是greedy的，但是是"best estimated cost first" greedy，而不是naive greedy。

注意在把goal node放入frontier時 ，search並未結束喔!!! 要在goal node被goal test之後才算結束，這主要是演算法的結構所致，另外f是estimated cost，並非真實的cost，如果reach goal就停止會導致non-optaml result發生。

Admissible / Optimistic / No-OverEstimate Heuristics

A*只有在h function < true cost時才能保證optimality，這個已經在Columbia AI課程中證明過了。

怎麼確定一個heuristics是不是admissible?
以我們之前提到過的n-puzzle為例:

h1中，n個mispaced block至少要移動n次，所以一定小於真正要解決謎題的移動次數。
h2中，同理。

所以h1和h2都是admissible，而且h2優於h1因為h2(State) >= h1(State)，所以會減少node expansion數量，更快抵達goal。

不過如果search AI只能靠人類給他們heuristics才有辦法解決問題的話，那智慧在哪?
有沒有辦法AI自己長出heuristics?

Generating a relaxed problem

如果對n-puzzle的formal problem description為:

這可以看成是幾個constraints，限制state到state間的transition可能。

如果relax這個定義變成如下的話:

事實上這就(implies)是h2，因為adjacent implies box-to-box distance，而去除掉blank又implies euclidean distance，這個relaxed description使得h2變得自然。

如果relax到只有以下一句話:

這就是h1(當然也包括h2)，因為能從A移動到B的block就是misplaced blocks。

所以找出h1和h2是可以自動產生的!!!! 某種relaxing problem演算法可以找出candidate heuristics，如果給予某種formal problem description的規則的話。

這些candidate heuristics因為是relaxed problem下可以做的動作，所以相當於提供了state間的跳躍，或說新的transition的可能性:

所以candidates一定是admissible的，因為只會減少cost，不會增加。
另外更好的是可以採用max(h1(S),h2(S),...)當作每次的h(S)，這會更快接近goal state，但是壞處是要同時計算許多heuristics，不見得節省runing time。

使用Search的時機

其實search是最基本的AI工具，因為它只能解決很限制性的問題:
1. 我們需要有每個state的資訊
2. 我們需要知道所有可行的actions
3. actions必須是finite set
4. actions的結果不可是隨機性
5. 環境不可動態改變

所以基本上，玩棋類遊戲或是routing好像比較適合這類search AI。