好，我們剛剛提到partial observation，那partial observation其實
帶領到另外一個更進一步的是unknown environment，因為這個裡面主要差別是，像我們剛剛的 partial
observation的話，譬如說，我們剛剛走maze的話，那地圖是知道的，或是， 我們在vacuum
world裡面，那個你知道世界是兩個房間組成的，然後你知道，
它是either有dirt或沒dirt。那這個東西還是屬於我們知道的環境， 那我們接下來要講的
是一個如果你連這個環境你都不知道，就是你只能走一步算一步的話， 那這種情況下要怎麼做。我們這種search，我們通常稱為，術語上我們通常稱為
on-line search。
好，就是有點像， 你不知道，就是使用者在跟你互動，你不知道使用者下一步要做甚麼，
但是你還是要替他iii做到一些事情。好，那基本上， 我們要minimize，基本上說我search，還要最佳化都一樣。我們要minim-
ize，就是這個，我們稱為competitive ratio。 就是你解這個問題裡面可以有最小的cost以及你實際上所花的cost
的一個比值。那這個比例當然是越小越好，那你的最小值就是1，你不可能更小。
雖然我們想要minimize這個competitive ratio， 但是，有些時候可以，
有些時候不可以。如果，今天如果我們，你的action是reversible， 就是你往，你走了，
你從A走到B這個state以後，你總有辦法可以回到A。如果是這個樣話，其實你可以用DFS的方法。
然後你保證，你如果你有足夠的記憶體把所有的state全部記完的話，你可以保證，
你worst case就是把，worst case就是所有的state看兩次。
這應該不難啦，這應該不難。就是基本上你DFS一直走，走到底以後你又回頭，不對你就回頭，
不對你就回頭，是這樣一直走。那所有對state最多被visit兩次而已。 好，這個是可以guarantee的。
但是如果今天你的action，某些若干action是不可逆的，
就像我，我一開始就講過，譬如說你如果是一個機器人，你在，
如果沒有爬坡功能，你在一個階梯對不對，你可以，你可能可以從高的階梯這一格
走到低的這一階梯這一格，就是輪子“吭”就過去，就“咚”一下。可是你如果輪子不夠大的- 話，你可能是回不來的。
也就是說這個地方，你這個動作可能一下下去了，你就到這邊再也回不來。
如果是這個樣子的話，然後你又針對 unknown的 environment的話，其實， 這個competitive ratio可以是
無限的，你根本沒辦法bond住。我們下面舉這個例子，就是 你這是starting point，你到某一個state A，
然後這邊之後你有兩條路可以選。那這個重點就是，因為你是unknown environment，
所以你到A的時候，你只能看到這裡，你只能看到，接下來你可以到這個，或是這個。 那這兩個state裡面如果沒有任何到hint的話，
接下來有一個是可以到goal，有一個這邊故意做的就是無窮迴圈，就infinit loop。
那問題就在於，接下來你有兩種可能，一個是這裡。一個是這種可能，一個是這種可能。 實際上你就是不知道。
那如果你的動作是不可逆的話，我們所謂證明就是advisory證明嘛。 就是我們用最差情況來講的話， 就是你如果選擇，
因為你你還沒看到，你這視野到這邊，你還沒看到後面，所以我可能就是，
你如果選了上面，如果你在這一條路，這個A你決定往上走，那我就跟你講實際上裡面你的環境，
其實是下面這個環境，這就是advisory證明，其實你走的路是錯的，就是這個。但是 那你如果說，好吧，那我選擇下路，那其實我跟你講，因為你還沒有看到嘛，你也不知道後面-
是甚麼，我可以跟你講， 其實你選的路是這一個。
ok，其實這個有點像那個三國演義裡面那個曹操看到華容道前面 有兩條路可以走嘛，前面點稻草，有個在冒煙，有個路小小的，有個路寬寬的，可是你不知道-
後面是甚麼。
那如果你不知道後面是甚麼的話，就是最糟情況永遠是你可以永遠選錯路。
那這邊左邊這個例子其實是 你是一個無窮，那甚至如果沒有無窮的話也可以很糟。
我們這邊做的是一個，這邊，右圖這邊畫的是說你的一個state，
你要走到goal。那你遇到牆路，這個是一個阻礙嘛，兩條路，選擇一個是往上，一個- 是往下。
那我們這邊就advisory證明也是，你的worst case可以很糟， 就是你選擇往上走，偏偏這邊我又給你擋一道牆。
然後你選擇這邊好了，你就要選擇往下走，我知道，就是每次你路的地方
我就給你擋一道牆，就是你如果這邊選上的話，似乎就可以直接走過來， 但是我就是故意不讓你，擋你。
這個其實，這個實驗可能比較殘忍。不知道大家有沒有玩過擋螞蟻走路，就是，
螞蟻在這邊搬東西，搬的很開心，你就拿個東西擋著，它就選擇一邊繞， 再拿個東西擋著，選擇一邊繞。
其實意思差不多是這個樣子吧，那你如果每次都故意擋在它 選擇的那一塊的話，其實這個competitive ratio就會變很高很高。
好，這邊只要給各位一個概念，就是，只要你針對 unknown environment的話，的時候，基本上worst case
是非常糟的，基本上是完全不能bond，根本是無窮大，這個competitive ratio是無窮大。
好， 如果你有一些記憶可以記的話，
事情基本上會有點改善，但是仍然還是 worst case也是一樣的糟，譬如說，
我們說你有，你可以記一個state，其實可以記一個state，基本上就是 我們剛剛，最一開始我們講的單點搜尋，你可以記你現在的state，然後之後
你可以產生你看大家neighbor裡面你選擇一個最好的，然後你比較這兩個誰好，然後- 你take比較好的那一個，對不對。
那如果是SA的話就是你用幾率選擇一個，然後來替換現在的。因為這就是你用，
等於說你用記憶體記一個，當然你這個記憶體變多一點，你可以記若干個，這也沒甚麼關係。 可是， 仍然你的competitive
ratio仍然是無窮大，因為我們剛剛講過，不管是任何一種meta heuristic search，其實都不能保證 是global optimal，你如果在卡在像steep decent
的話，卡在一個local optimal的話， 你就代表，之後我就即使給你無窮的時間，你都走不到global optimal。
那如果是SA的話，當然你有可能會下山， 可是隨著時間過去，溫度開始下降，如果到溫度降到很低到情況下，你還走不到global
optimal， 還是仍然是卡在一個local optimal的話，你的competitive ratio仍然是無窮大。
如果像我們剛剛講，因為我們剛剛提就是stimulated annealing嘛，如果即使，
我們今天講即使溫度不把它下降到很多，就是溫度仍然keep在某個程度上， 也就是說差別其實只是你增加了它到
random work的一個特性。
可是，雖然這樣，雖然你如果增加它random work特性，我們剛剛其實就有證明說，
我沒有真的證明啦，有講過有一個證明，也就是說，你只要有non zero幾率， 到global optimal嘛，那我給你無窮久到時間，你總走得到。它保證你一定走得到。
但是這個走得到所花到時間可以是exponentially long，可以是exponential。
舉例而言，譬如說，我們看一下下面這個例子，下面這個例子就簡單講， 就是從starting point，你的goal當然是這邊，
但是，你有很多state， 就是你這邊剪頭畫的是你可以的action，你如果用random work
的話，譬如，你可以發現，譬如說我在這個state裡面，你可以的action有一個是
往前，一個是往這邊，一個是往這邊，一個是往這邊，對不對。
這四個action裡面，其實只有一個真正會往前，其它三個都是往後，但是因為你也- 不知道，
對不對，所以基本上你只有四分之一的幾率會approach goal， 那這邊我只要給你goal多的話，你會發現到goal到那個幾率基本上就是
四分之一的，譬如說某個情況，跟n成正比，就是四分之一的n次方， 這麼小的幾率你能到goal，也就是說，
平均而言，用幾率來講，你需要4到n次方這麼多的時間，你才能走得到goal。可是這邊其實
它solution很單純，就是一條n的，n長度的solution而已。
ok，所以這邊要講的，就是說如果我不給你這個map， 當然如果我一旦把這個map給你，你知道這個state長這樣，
那你當然可以做一些分析，然後之後發現一路往右衝是最好的選擇。 但是我們現在在講的是unknown environment， 那即使你有limited
memory，你也只是稍微改善這些constant，可能4的n次方變成2的n次方， 但是基本上， 你不能避免的是它的
worst case仍然是無法bond，也無法，不能bond，而且也可能是exponential。
好，接下來我們要提的是一個，我們叫learning real time A＊ ， 就是，real
time就是相對應到的online search，就是你 如果environment是一邊在進行的時候一邊慢慢看到的情況下，我們可不可以
做類似A＊的事情。好，因為我們之前有提過， enforcer有提過A＊具有很多很好的特性，實際上呢，
是可以的，但是我等一下會提到， LRTA＊雖然這個演算法看似很好，但是它有一些問題是。
第一個最重要問題其實就是記憶體。基本上它跟A＊不太一樣， 它真的需要把每個state都記下來，我們馬上就會看到。
好，基本這邊有個 heuristic是h，這是一個function，就是這個h是一個
你可以想像是一個program，可以計算的，就是一個function call。
那這個大H呢是一個table，就是譬如說，你可以，實做的話你可以利一維陣列，或者是甚麼hatch table等等。
然後，另外一個就是一個result，就是 這也是一個table，
好，我們之前寫result的話是一個function，但我們這邊寫的這個意思是一個- table，就是你需要記錄，
如果從s執行A你會到哪個state，好，因為這個在unknown environment也是一邊走一邊慢慢
開始看到的， 好，那這邊要做的事情呢，LRTA* 它做的事情是
initially 如果你新走到的 你先，anyway，你在一個 state 里，你就一個S你還是一樣做A走到
S'，那今天如果這個新的 S'呢，你新的到的 state 如果從來沒有記錄過 從來沒有看到過，那你就先它的
H 就等於它的 h，就是它的 好或不好直接由你的 heuristic 來決定。
好，那如果不是的話，我們等一下會看到，基本上就是 如果不是第一次看到的話那你會在這所有裡面。
在這我們等一下會看到，所有可以執行的 action裡面 cost 最小的那一個， 我們等一下會看到這個
LRTA* cost，裡面所回傳的值裡面最小的那一個 拿來記錄在table 裡面， 這是一個 update，我們等一下會看到，然後
a 呢你的 action 其實也就是執行的那一個， 這裡面最小的執行的action， 不過這裡面差別是這邊用的是S，這兩行有一個差別是這邊用的都是
S，這邊用的都是 S'，這是第七行跟第八行的一個差別，等一下我們會check 一下。
好，這個 LRTA* 它在做的其實事情是一開始你如果這個 state
沒有看到的時候 你就是，其實這邊看到這邊 cost 就是，你如果從來沒看到 你基本上就是
h 了，好，你如果看到的話呢你就是 用，你如果看過的話， 基本上就是你用你前面來的，這是上一個嘛，大家還是記得這個圖。
好，你先，你還是用這個 step cost， 這個 step cost
加上你 這一個 h 就是 S’ 這一個的之前的那個 估計你記的那個值來當做你實際上的
cost， 用這個方法，然後之後我們前面一個 code 有說你有很多種
action 可以做到這件事，你選擇裡面最好的，看起來最好的那個 action，我們永遠
choose apparently best 以目前你 H 那個 table
裡面記錄的 cost 然後來算，然後不斷的更新你這個 H。
基本上會有一種會越來越精准的結果。
好，那基本上呢，它會，LRTA* 實際上它會是，它基本上
你如果 S 都沒看過嘛，我們傳的 h，那這個 h基本上不 care 你之前做的，已經到這邊來
的值，這跟 a* 是不太一樣的，也就是說 這個 H基本上是非，一般來說是非常低的，也就是說它在 encourage
你去試驗還沒看過的 state，也就是你如果從來沒看過，它會 它會 encourage
你先看，Ok，比如說你先看，用這個特性來 讓 LRTA* 可以 explore 遠一點。
好那這是 code 的部分，其實我們只要 run 一個 case，
run個實例你就知道這是甚麼意思，我們這個例子呢就是， 好，你不太清楚 goal
在哪裡啦，但是基本上這邊 set 這個框框裡面的這個是它的 initially是小於7，後來就是大於7，反正這個沒有甚麼差別，我們就看一下這個
table 是怎麼被 update，那這邊的 action 假設每一個action都是這是 cost， 這是 step cost
s、a、s'，這個箭頭上的1就是 step cost。
好，那可以看得到一開始在 a 這個state
的情況下， 這個大家可以看到這個估計值其實不太好嘛，因為你看這邊是，說我距離目標還有10，
這邊距離目標還有9，你看到這邊有一個這樣的趨勢，所以你可以估計如果這些估計值是正確的話， 你的 goal 可能在這附近。
好，可是很奇怪是你看這邊估計到7，可是你說這邊只有6和
1，這是一個不太可能會發生的狀況，你可能比較合理的是10、9、8、7 10、9、8、7這樣過來，也就是說這邊看起來，你的
h 的估計值 有一個這樣掉下來，可是不太合理的地方，就是 實際上正確的
h 可能是 這樣，到這邊就goal，goal的話是零，對不對，就是你如果 到
goal 的話這邊就是零，但是我們這邊做的一件事情就是 故意設計了一個類似這樣的東西。那等一下我們會看到隨著
LRTA* 在走的過程，它會把這個 H 會填回，會把這個填回去。
以至於下一次你在走到這裡的話，你的 h估計值會到這裡去。 我們看一下怎麼做到這件事， 這邊灰色的這個框框就是我
agent 現在在的地方， 好，那也許現在這裡，然後有兩個可能嘛，就是往左或往右走。
那這邊的你的cost，你這邊是6，然後你往這邊右邊的話這邊會變7，就是你現在的 h
加上這個 cost 是7，往這邊走的話是9加1，
9加1是10，好，會是10，好，你就比較一下這個10跟7哪個小。
就是我們剛剛的第七行，OK，第七行，那你取完了當然就是執行這一個。
所以你會走過來到這裡，這是你的 agent 地方， 然後之後你會update上一個 就是你過來的那一個的狀態，你會
update 它這邊雙圈就是你去 update 它的 h， 好，也就是說你現在走到5，你這邊是5，然後我過來花了1，你說這邊h
是5嘛, 你過來花了1，你會回去算，好，那所以這個是6。
那這個6沒有改到，實際上就是花了6。之後我們還是左右會選擇一個，那很明顯的，左邊這- 個比較好。所以你的
agent 就會回來這個6這邊，然後你會 update 剛剛這個，剛剛這個 你會，你現在這邊估計值是6，然後你花了一個
cost 是1，所以這邊其實 6加1，然後你會選擇，你就會去選擇把這個5改成7。
也就是說 Ok 我到這邊，你不太相信你上一個state， 你比較相信現在這個state，你現在說距離 你這6，就是說我這邊距離
goal 還有6步嘛，可是我剛剛已經多花了一步，所以你剛剛那一個 state 應該是7。
OK，我這邊就做一件事把5 從5變到7，然後之後做一樣的事，然後左右兩邊，你還是看一下，然後就是右邊比較promising
所以你就 agent 決定過來右邊這邊，然後把剛剛那個 state，你現在相信這個7，對不對，你剛剛
又花了一步過來，所以剛剛的 state 應該是7加1，這個 h 應該是8。
好，然後你就這樣繼續走下去，好你可以看到，各位可以看到，在這一個 state
的 時候，在這個這一步的時候，其實我們已經把這個 h 大致上填平，把中間比較不合理的６和５
已經填平了，也就是說，如果以後，如果若干，因為我不知道後面是怎麼樣子 這大概可能不光是單純線性，如果你走到這個state
之後，不知道為甚麼有一條路就會走到這裡來 的話，下次再走到這裡的時候，你會發現 我的 agent
就可以很順的一路往右從，我不用在這邊，像剛剛這邊是來來回回 在這邊是來來回回很多次，這來來回回的原因是因為你在這一個，我的
h 估計值不准的嘛， 對不對，h是這樣估計，所以你在這邊， 你在這裡的時候會看這邊，你在這裡 時候會看這邊，可是這個
h 是不准的，所以你看在這邊來來回回的時候 LRTA* 又把這邊 h 給填平了。
就是學會這些，那你下次再來這邊的話就一路很順地走過去，其實有一些很多特
性，有些證明我們這邊就不提，但是如果有個特性，譬如說，你是 n 個state，它 guarantee，LRTA* guarantee
在n的平方內， 一定可以走得到，guarantee 這件事，但是實際上一般， 這是 worst case 實際上一般來說都比 n 的平方還要快。
那，LRTA* 事實上看似很好，對不對，看似OK，你可以找到 optimal，而且我們還蠻快的。
就是基本上是 iii以下，平方以下，但是我們回想一下，他基本上記兩個table，一個是
H table，他要記這一個，他要記第二個 table 是result table。
好，這個 table的 size 呢就是
s 這整個集合，state 全部的 size。這一個 size 呢還更長。
s 這個集合乘上 action 這個集合， 整個 size，一般來說我們一開始在講 search
的時候，但大部分比較複雜一點的問題裡面 state 的數量非常大，你基本上不可能記說 state 的數量，那今天還要乘上 action，那會更慘。
好，所以實際上，我們到後面幾講會講到，後面一講應該就會開始講到，很多時候我們對這個 s 呢。
你不能真的 用 table 嚴格去記起來，你可能對一個 s
對一個 state 你會先設法把它對應到 feature domain，
也就是說你用一些 program 去算，那只要 這些 feature 值是一樣的，你就把它認為是同一個 state。
好，那這樣的話你這整個演算法的 performance 至少它能實用啦你就不用記這麼多 state，
只要是feature是一樣的，你就只要記那些就可以，那它的performance， 這樣演算法的performance是完全取決於feature
的好壞，這個會影響很大，這個我們到後面會再提一下。 好以上我們回顧一下這一講的內容，那我們首先先講的，title
是 meta heuristic 的部分，那我們提了steepest decent。
那steepest decent在很多不是很難的問題甚至像我們像八，N皇后這種問題，它可以
解到非常的大，一百萬乘一百萬的 格子，一百萬個皇后都可以，那 steepest decent
的缺點是它很容易被卡在local optimum 里，那你可以使用 simulated annealing (SA) 它會採用一些 random
walk 的方式，在初期的時候，那可以 有比較好的幾率找到 global optimum，但是你同時也付出一些代價。
好，那你也考慮用 gymnastic algorism (GA)的方式， 就是 evolutionary computation gymnastic algorism 這一部分，那後面都
有一些理論，我們大部分近年來做都是希望在也是一樣在 n的平方以內，就是你給我一個 n 的 size
的問題，我會 你的問題如果具備某些特性的時候，我們可以 Guarantee 在 n 的平方以內找到還不錯的解，但是在這部分我們不能百分之
百保證能找到最佳，我們只是說有很高的幾率你可以找到很好的解，好，那如果我們談到 non-deterministic
action 的話 那基本上你需要我們在做 search 時其實就是一個 And-or search 那就是對 所有 and 的節點，你的
solution 對說 and 的節點。每一支都要保證能夠走到 走到，就他的例子走下去，走到最後端點那個地方都要保證是
goal state，那最後還有就是 我們提到你用 sensor
來幫助我們解 non-deterministic action 的問題的時候，你可以用
sensor-less 的 agent，但基本上其實在很多 實際的現實的世界，我們其實很多 agent
都是 sensor-less 的，它們也perform得很好，很 robust。但是 如果你今天 non-deterministic
action 會增加 belief state的數量 以至於你沒辦法找出一個 solution 的話， 那你還是必須要加
sensor，目的是為了 reduce，reduce 這個 belief state 裡的size， 就是你做一些 non-deterministic
action 以後，belief state還增大 那你要再根據 sensor把它縮減，那這樣你有可能找到一些 solution。
好，那如果你連 environment 不僅是， 你的action non-deterministic
有這個特性之外，你連整個環境整個世界，這個世界到底怎麼樣你都不肯定， 你都是一邊走一邊看的話，那這樣我們稱為
on-line search，on-line search 我們今天開始提 到一些事情，就是你不管你只要自己有 limited memory
基本上大致上都是很 糟糕的啦，我可以給你一些 worst case 似的，你根本不可能收斂，或是
找到最佳解，你要花exponential的時間，那如果你的記憶體是 ok的情況下， 那你可以使用
LRTA*，但是它的記憶體是個大問題，你需要記 s 這麼大 一個 table
還有一個 s*a 這個大的 table，那如果記憶體夠的話那基本上你 LRTA* 是對 unhnown-environment 是可以做得很好，那如果你記憶體不夠的話，你可以利用一些
feature 的方式把整個 state 的 size 給reduce， 那你的performance 會完全 depends on，
會非常 heavily depends on 你這個 feature的選擇， 好， 那這個定位的方式，其實有另外一種技巧，那叫做particle
filter，那其實跟這個技巧是很類似的，particle filter 是使用一種類似蒙地卡羅法，那在 一個迷宮裡面你要定位自己的情況下，用
亂數的方式用所有可能的點都撒進去。那在一開始的時候可能就是 你既然他不知道它所有點都是可能的，那之後，你讓這個
agent 去移動，再根據它的 sensor 呢來把所有 比較不可能的點把它消除掉，剩下比較可能點之後取平均來當做你自己的
機器人認為的定位，那這個會隨著機器人一直移動然後測到不同的資訊的連續性， 然後來，這個定位會
越來越準，那關於相關影片呢，請各位同學可以上網搜尋， 或者參考一下我們coursera 裡面的，有參考鏈接，那裡面
有蠻詳細的一個蠻有趣的一個 Demo 大家可以看，那這部分的技巧也蠻常來 做應用於，使用於在一個影片裡面做
tracking，譬如說，像我 track 一個人的移動， 或它 track
一個物品的移動，那也常常被用在 sensor network 裡面的技術中。
