National Taiwan University 大家好，今天我們要來 談論如何利用search的方式來做problem solving。那search基本上分成兩種 一種是所謂 uninformed, 一種是informed search. 那這裡的 informed 和 uninformed 的 search 的差別呢是在於說 我們對於問題基礎的 knowledge 有多少。那uninformed search 並不利用 我們並不利用問題本身的特性，也就是我們並不去預估如果我做了 action A 和 action B 他們可能會有甚麼結果，並不做這樣的預估。 那在這種情況下我們就是針對我們唯一有的資訊，就是我做action A 我要花多少cost, 做action B 要多少cost, 如果我們只利用這種這種資訊的話，那我們這一類稱謂所謂uninformed search， 也是我們這一講所要講的 那我們這裡所要講的範圍大概對應到課本AIMA的 3.1 到 3.4 之間的章節 好，我們今天首先會談一下 何謂一個 problem solving agent，那接下來我們會談論如何把一個problem formulate 成一個 search 的 problem. 就是 因為 這個過程有兩三種，我們可能會談到可能你有不同的 formulate 的方法。那有些formulate的方法 會使的你的問題其實比較簡單 有些formulate 方法會使得你的問題變複雜 那之後我們會談論兩種基本的search的技巧，一種是所謂的 tree search 以及graph search， 那在tree search上, graph search 上 最主要差異呢就是 tree search 裡面並不偵測說 state 是否有重覆的現象而graph search裡面偵測會去偵測 state 是否有重覆，那重覆的話就不必再度去搜尋。那一般而言當然 graph search 的效率會比較好。但是，graph search 本身有記憶體的 限制的問題，不一定在很多時候都能做得到graph search ，所以我們之後繼續再講下去的時候， 會主要focus是在tree search 這一塊，那graph search 上有一些其他的技巧， 同學們可以看一下課本有談到如何之後比較有advance的技巧， 如何在有限的記憶體空間內，去做有限的 state 是否有重覆的這樣的測試，這一類技巧我們在日後也可能會談到 那如果我們focuse在search這個 技巧本身的話，我們有所謂的最基本的有深度優先以及廣度優先， 這兩個基礎的search, 在這兩種基礎 search上，我們又繼續發展就是為了改善譬如說他 像深度優先搜尋不一定，可能會陷入無窮迴圈，不一定會回傳的情況下，我們可以Limit他的深度， 就是所謂的depth-limit-search 那之後我們也可以利用慢慢把這個深度一層一層的限制慢慢加深 達到所謂一個iterative deepening 的一種search. 那最後一個 可能性就是bidirectional search， 就是從starting point 以及 goal point 兩邊一起search回來， 那如果 這個能成立的話，基本上對search上會有蠻大的效能上的幫助， 那這大概是涵蓋我們今天所要講得範圍 一個problem solving agent 呢，第一件事就是設法一個formulate 一個 goal 還有一個problem，之後會co search 這個procedure 去尋找一個solution，那在一個search 我們之前應該有提過，那在一個search來說，所謂的solution就是一個 sequence of action, 那就是這邊談到 的一個 sequence of action. 那之後呢，你拿到sequence of action 以後， 就會一步一步去執行他，那等到你把現有的問題解決以後，你這個agent會再重新去 根據現有的狀態去formulate一個新的goal出來， 也就我們下面的sudo code可以看到 那基本上你拿到這個agent從環境中感受到，拿到一些感測透過sensor sense到一些事情後，會update他目前對世界的預估，就是他state的狀態。那之後 會根據這個，他認為，大家還記得嗎。這個state 就是我們目前對世界最好的一個猜測 對世界的model的這個猜測去formulate一個goal出來，那given我現- 在世界是甚麼樣，那我目標 是如何如何。那之後我們一旦有目標，這邊就變一個goal based 的search engine， 就是有目標，還有現在的世界狀態我們就設法去co這個formulate problem 然後去找去一個 把一個problem formulate 出來，基本上我們等一下會談到就是可能就是有所謂 initial state， 有goal state還有一些legal的action等等，之後就是co 你的 給你這個problem 後你就可以co 這個search 這個函式，那這個search input是一個problem嗎， 那當然這裡面包含了goal，我們等一下會把problem 的一個要素跟各位講一下 那他的output呢就是一個sequence of action 就我們上面寫的這個， 就sequence of action。好，那這個sequence of action 呢 基本上，之後你拿到以後就是一步一步去執行他，那基本上 這邊在做的事情就是這邊，你先執行一個，讓後把 剩下的留下來，然後之後再繼續執行下一個，直到你已經sequence empty的時候 你要再重新根據你透過sensor拿到的資料對這個 世界再重新做一次model 然後再 formulate 一個problem 然後再search這個goal 這樣一直做下去就是一個以 search為中心的一個 problem solving 的 agent 那接下來我們舉一個例子，這個例子基本上除了這一講之外，也會沿用到下一講， 那這個例子基本上是一個台北的捷運圖，那為了課程的設計 需要我們在數字上和站名上有些調整，台北的捷運不完全是個這樣字 但是我們做一些調整使得比較好舉例子，那今天假設是說你在台北有假期讓後你目前在古亭 這個站，那你接下來的目標是到台北車站， 那，你首先我們要先formulate一個目標，目標就是 達到到台北車站這個地方 好，我們要formulate一個problem的時候就需要有state， 就是有狀態以及你可以做的action， 在這個例子裡面，我state如果你是要一路做過去的話， 你agent每次做一些不同的action以後，你到達了不同的state， 其實就是指你在不同的捷運站這邊，那你的action能做的呢在這個例子上 基本上我們假設你可以take 你可以從某些 某些MRT 就是某些捷運站，移動到某些捷運站上面，實際上我們地鐵就是一列車 一路開下去，不過在我們在例子上我們就把他分成不同的action，例如從A 到B之後 是一個 action，從 B到C 這是第二個action 好那我們的目標就是要找到一個solution，那這個solution 就是一連串的 sequence of action, 我們剛剛有提過。 sequence of action。 那相對應來說，其實你要做的事情因為我們action就是兩兩捷運 站之間的移動，你也直接想成是一連串的 station 的狀態，這樣也可以成為我們的station 好這是，我們之前講過的這個圖，那我們目標就是這樣，我們目前在古亭這個地方 那我們的目標要到台北車站，那這上面的這些數字 概念上就是一種距離，那我們要 想要達到就怎麼樣從古亭能夠，怎麼樣走能走到台北車站，然後基本上 我們需要 search 到，一個情況就是你要先達到目標嘛，那如果你有多 種路經可以達到目標的話，那我們希望是那個最短的距離，那例如 像這個例子大家可以眼睛算一算，大致上，最短的距離應該是這一條 應該這一條、這樣你把cost全部加起來，應該是20加15然後加10 加35，這應該是最短，你可以試一下，那應該其他路徑都不見得會更短 好，那這個圖，我們就看一下那之後的話，同學再回來我們再談一 些例子時再來refer這一張圖，好我們首先要談一下怎麼formulate 一個problem，problem formulation 基本上 在我們的search engine 上，我們需要幾個，就這邊有五個 五個要件，好，一個要件是你要先定義你的initial state，那我們的例子的initial state 就是在古亭這個狀態，那接下來，你要定義你可以做的action 那你可以做的action，基本上是一個你在一個state對應就是，你在某一個state 你有若干步可以做，那基本上就是它可以是一個set，我們這邊就是利用一個action 類似函式的地方來講，他take一個，take的是一個 input 的是一個state，output呢，是一個set of action ok, 也就是說反正你在這個state你可能能做若干個不同的可行的 狀態，大家可以回想一下，我們就算用地圖來做例子，事實上如果是在 下棋的情況下也是ok的，就西洋棋或甚麼中國象棋，譬如說你 有時候你在不同的state 也有些不同的狀態，也許你可能柺馬腳嘛，你馬不能跳到某個地方，又或是 卡象眼，以至於你象不能動某些地方，反正在不同的狀態下，state下，我們可以定義一些不同 的action不同的move，那就是我們action這個函式，那接下來，有個很重要的其實算是 很重要的 case 的定義就是 transition model transition model 重點是他是個一個function，基本上他就是take兩個 input，一個是state，一個是action。 就如果，我在state S, 做了action A，那我 會得到到哪一個state去，那如果我要寫conditional product 的話，他就是一個 function, 然後這個funtion 大致上就是從. S，這是STATE的集合然後CONDITION CROSS一個 ACTION的集合，然後MAP到一個S。好了，這輸入是一個 輸入是一個STATE還有一個ACTION，然後輸出是一個STATE。 OK好，那這樣這個例子如果我們從古亭，那我們如果說 做這個ACTION就是GO走到東門，好，那你如果想要確定這個 到東門這件事情，這個ACTION，是在古亭可以做的事情， 然後我們可以回去CHECK一下 就是我們從古亭，我們可以做的移動的ACTION其實有兩個，就是GO東門或者GO 中正紀念堂，好這兩個。那只要確定它是可行VALID MOVE的話 那就做了這個GO古亭的，GO東門的這個動作之後，結果這個STATE就知道了 在東門這個STATE。OK，那這邊有第二種transition MODEL這是一種，我剛講的是一種表示，用函式來表示的 就是S然後乘上上A然後到S，另外一種表示方式是用SUCCESSOR，好這兩個表示方式 EQUIVALENT的就是EITHER都可以。你不需要兩個都有， 那另外的一種表示方式就是SUCCESSOR。SUCCESSOR的話還 是，它是一個集合。它的基本上就是INPUT，你可以想象INPUT是一個STATE， 它的OUTPUT就是一個SET OF STATES。 好，那怎麼定義這個是哪一些SET OF STATE呢？ 其實就是在你S，就是INPUT這個STATE所有可以執行的VALID MOVE， LEGAL的MOVE，所有能到的STATE就是一個集合。像剛剛 這個例子，像我們剛才用在古亭這個例子的話，因為在古亭的時候你可以做的 ACTION就是GO東門還有GO中正紀念堂，那這兩個 個別代表你的STATE分別就是IN東門還有IN中正紀念堂。 好，所以說在古亭這個SUCCESSOR其實就是東門還有中正紀念堂這兩個STATE。 OK，假說這邊大家可以瞭解這兩個其實IDENTICAL，基本上是EQUIVALENT的啦。 你給我SUCCESSOR還有給我RESULT結果是差不多一樣的。 好，那最後還有一個就是後面還有一個GO TEST， 就是你要怎麼知道我達了目標了沒呢？基本上GO TEST 原則上就是一個SET OF STATES。 好，那這個STATE我們會稱為GO STATE，好，就是GO STATE可能有若干個， 在我們例子里來說只有一個，就是在 台北車站這個STATE。那實際上的話你可以有若干個STATE都可以。 比如說我如果說要到台北車站也好或者我要到世貿中心也好，這樣一路 都算是到了目的然後這樣也行。好，那在我們例子里只有一個， 那最後一個就是我們要知道，如果有 你有不同的方法可以到同樣的GOAL的話我們可能需要選擇COST最小的。 所以你需要一個資訊就是COST。 好呢，我們稱為一個路徑的COST。好呢，實際上， 在大部分的例子里來說，這個路徑的COST 大部分都是可以相加的在滿多的CASES。但是有一些CASES也不是， 但是我們舉的例子都是喔。比如說如果我 距離上就相加的比如A做到B就是10公里啊，或者B做到C是15公里， 那基本上，A做到C這樣 走的方法通過B然後走到C的話總共花了25公里。好， 那大部分例子里可疊加的情況下，你也可以給我STEP COST的資訊。 好，OK，這兩個是一樣。STEP COST就是一個ACTION。 從某個STATE一個ACTION所得到的COST。 那PATH COST就是你從就從某一個S那你走到，比如說，S1之後再走到S2之後再走到S3。 這樣總體的這一條路徑的COST我們稱為PATH COST。 那可疊加的情況下我們可以加， 所以這相當於你給我個分段的這個C1、C2和C3，那你的TOTAL的PATH COST就是兩三個相加了，所以這兩個基本上你給我哪一個都可以。 好呢，在我們剛講的例子來說我們給的是 STEP COST，就是這個地圖上的這個20，好， 這個就是STEP COST，像這個15就是指 從忠孝復興你執行GO南京東路這個ACTION，那你會達到在南京東路這個STATE上的COST 好，所以呢，哦STEP COST 我寫法寫的是這樣就是基本上定義你從S執行STATE執行A ACTION 到達S PRIME，好那這個STEP COST規定是只你只能單一ACTION 好，單一ACTION，那我們要最後要找的SOLUTION呢其實就是 呃一連串的ACTION使得我可以從INITIAL STATE然後達到某一個 GO STATE。某一個就可以了。 好，這樣我們就稱為是一個SOLUTION，那如果我們 稱為一個OPTIMAL SOLUTION的話， 就是到達COST最小的那一個GO STATE。
