第10章計劃、動作和學習

1、第第1010章章 計劃、動作和學習計劃、動作和學習 第二部分第二部分 狀態(tài)空間搜索狀態(tài)空間搜索 我們已經(jīng)探討了在圖中查找路徑的幾種我們已經(jīng)探討了在圖中查找路徑的幾種技術，現(xiàn)在來研究這些方法如何被技術，現(xiàn)在來研究這些方法如何被agentagent用于用于現(xiàn)實問題中?，F(xiàn)實問題中。 感知計劃動作循環(huán)感知計劃動作循環(huán) 基于搜索的規(guī)劃方法的功效依賴于幾個很強的假設。基于搜索的規(guī)劃方法的功效依賴于幾個很強的假設。由于以下原因，這些假設常常得不到滿足：由于以下原因，這些假設常常得不到滿足： 1) 1)知覺過程不可能總是提供環(huán)境狀態(tài)的必需信息知覺過程不可能總是提供環(huán)境狀態(tài)的必需信息( (由于由于噪聲或者對重要

2、的特性不敏感噪聲或者對重要的特性不敏感) )。當兩種不同的環(huán)境狀態(tài)引。當兩種不同的環(huán)境狀態(tài)引起相同的傳感器輸入時，我們稱這種情況為起相同的傳感器輸入時，我們稱這種情況為感知混淆感知混淆( (perceptual aliasing)perceptual aliasing)。 2) 2)動作并不總有其模型效果動作并不總有其模型效果( (由于模型不夠精確，或者由于模型不夠精確，或者受動器系統(tǒng)在執(zhí)行動作時偶爾會產生錯誤受動器系統(tǒng)在執(zhí)行動作時偶爾會產生錯誤) )。 3) 3)可能在環(huán)境中有其他的物理過程或其他的可能在環(huán)境中有其他的物理過程或其他的agent(agent(例例如，在游戲中有對手如，在游戲中

3、有對手) )。這些過程可能會改變環(huán)境以致于干。這些過程可能會改變環(huán)境以致于干擾擾agentagent的動作。的動作。 4) 4)外部作用的存在會引起其他的問題：在構造一個計外部作用的存在會引起其他的問題：在構造一個計劃期間，環(huán)境可能變得與原來的計劃不相干。這種困難使劃期間，環(huán)境可能變得與原來的計劃不相干。這種困難使得花費太多的時間為一個得花費太多的時間為一個agentagent進行計劃而變得毫無意義。進行計劃而變得毫無意義。 5) 5)agentagent可能在完成一個到達目標狀態(tài)的搜索之前被可能在完成一個到達目標狀態(tài)的搜索之前被要求動作。要求動作。 6) 6)即使即使agentagent有充

4、分的計算時間，但是計算要求的空有充分的計算時間，但是計算要求的空間資源不允許搜索進行到目標狀態(tài)。間資源不允許搜索進行到目標狀態(tài)。 感知計劃動作循環(huán)感知計劃動作循環(huán) 有兩種主要方法可以用來解決這些困難，同時又能保有兩種主要方法可以用來解決這些困難，同時又能保留基于搜索的計劃的主要特征。留基于搜索的計劃的主要特征。一種一種是用概率方法來形式是用概率方法來形式化知覺、環(huán)境和受動器的不確定性；化知覺、環(huán)境和受動器的不確定性；另一種另一種辦法是用各種辦法是用各種附加的假設和近似來消除這些困難的影響。附加的假設和近似來消除這些困難的影響。 處理動作的不確定效果的一種正式方法是假定對一定狀處理動作的不確定效

5、果的一種正式方法是假定對一定狀態(tài)下的每一個可執(zhí)行動作，結果狀態(tài)由一個已知的概率分布態(tài)下的每一個可執(zhí)行動作，結果狀態(tài)由一個已知的概率分布給出。在這種情況下找到合適的動作被稱為給出。在這種情況下找到合適的動作被稱為MarkovMarkov決策問題決策問題( (Markov decision problem , Markov decision problem , MDPMDP) ) 。 通過假定通過假定agentagent的傳感設備在它的狀態(tài)集上提供一個概的傳感設備在它的狀態(tài)集上提供一個概率分布，可以解決有缺陷知覺的其他問題。發(fā)現(xiàn)動作則被稱率分布，可以解決有缺陷知覺的其他問題。發(fā)現(xiàn)動作則被稱為為局部

6、可見的局部可見的MarkovMarkov決策問題決策問題( (Partially observable Partially observable Markov decision problemMarkov decision problem， POMDP POMDP) ) 。感知計劃動作循環(huán)感知計劃動作循環(huán) 在這里不討論正式的、基于概率的方法，而是提出一在這里不討論正式的、基于概率的方法，而是提出一個叫個叫感知計劃動作感知計劃動作( (sense/plan/actsense/plan/act) )的結構，在很多的結構，在很多應用中它避開了上述的一些復雜性。應用中它避開了上述的一些復雜性。 該結構

7、的基本原理是：即使動作偶爾產生了沒有預料該結構的基本原理是：即使動作偶爾產生了沒有預料的結果，或者的結果，或者agentagent有時不能決定它處于哪一種環(huán)境狀態(tài)有時不能決定它處于哪一種環(huán)境狀態(tài)下，但是通過保證下，但是通過保證agentagent從它的執(zhí)行環(huán)境中得到連續(xù)的反從它的執(zhí)行環(huán)境中得到連續(xù)的反饋，這些困難可以被充分地解決。饋，這些困難可以被充分地解決。 感知計劃動作循環(huán)感知計劃動作循環(huán) 確保連續(xù)反饋的一個方法是確保連續(xù)反饋的一個方法是計劃一個動作序列計劃一個動作序列，只執(zhí)只執(zhí)行這個序列中的第一個動作行這個序列中的第一個動作，感知結果環(huán)境狀態(tài)，重新計感知結果環(huán)境狀態(tài)，重新計算開始節(jié)點，然

8、后算開始節(jié)點，然后重復上述過程重復上述過程。這種方式，選擇動作的。這種方式，選擇動作的agentagent被叫做被叫做感知計劃動作感知計劃動作agentagent。然而為了使這個方然而為了使這個方法有效，計算一個計劃的時間必須比每個動作執(zhí)行時間要法有效，計算一個計劃的時間必須比每個動作執(zhí)行時間要少。少。 在良性環(huán)境中在良性環(huán)境中( (容忍幾個錯誤步驟容忍幾個錯誤步驟) )，感知和動作中的，感知和動作中的錯誤在感知計劃動作循環(huán)序列中應錯誤在感知計劃動作循環(huán)序列中應“達到平均數(shù)達到平均數(shù)”。 感知計劃動作循環(huán)感知計劃動作循環(huán) 感知計劃動作循環(huán)感知計劃動作循環(huán) 逼近搜索逼近搜索 定性地講，定性地講，

9、只要第一個動作有縮短到達目標距離只要第一個動作有縮短到達目標距離的趨勢的趨勢( (平均情況平均情況) )，經(jīng)感知計劃動作循環(huán)的多次，經(jīng)感知計劃動作循環(huán)的多次迭代將最終到達目標。迭代將最終到達目標。 放寬產生最優(yōu)計劃的要求常會減少找到一個計劃放寬產生最優(yōu)計劃的要求常會減少找到一個計劃的計算代價。的計算代價。 可以對以產生計劃的質量為代價的有限計算時可以對以產生計劃的質量為代價的有限計算時間資源的搜索算法進行修改，這些計劃可能不是最佳間資源的搜索算法進行修改，這些計劃可能不是最佳的，或者可能不是總能可靠地到達目標狀態(tài)。即使這的，或者可能不是總能可靠地到達目標狀態(tài)。即使這個計劃不是最優(yōu)的個計劃不是最

10、優(yōu)的( (甚至也不正確甚至也不正確) )，這些技術的應用，這些技術的應用也能被合并到感知計劃動作循環(huán)中。也能被合并到感知計劃動作循環(huán)中。 一個一個A A* *類型的搜索可用于這兩種方法：類型的搜索可用于這兩種方法： 對對前者前者，我們用一個不可接納的啟發(fā)式函數(shù)；，我們用一個不可接納的啟發(fā)式函數(shù)； 對對后者后者，在到達目標前，在到達目標前( (用可接納的或不可接納的用可接納的或不可接納的啟發(fā)式函數(shù)啟發(fā)式函數(shù)) )退出搜索。在到達目標前退出搜索是退出搜索。在到達目標前退出搜索是任意任意時間算法時間算法( (anytime algorithm)anytime algorithm) 的一個例子。任意時

11、的一個例子。任意時間算法能在任何時刻停止，結果的質量會隨著運行時間算法能在任何時刻停止，結果的質量會隨著運行時間的增加而改善。間的增加而改善。 可以從兩個方面來減少代價?？梢詮膬蓚€方面來減少代價。一是一是能找到到達目能找到到達目標的一條完整路徑但不必要求它是最優(yōu)的；標的一條完整路徑但不必要求它是最優(yōu)的；或者是或者是能能找到一條局部的路徑，它不要求已達到目標節(jié)點。找到一條局部的路徑，它不要求已達到目標節(jié)點。逼近搜索逼近搜索 逼近搜索逼近搜索 孤島驅動搜索孤島驅動搜索 在在孤島驅動孤島驅動( (island-driven)island-driven)搜索中，來自問題搜索中，來自問題領域的啟發(fā)性知識

12、被用于在搜索空間中建立一個領域的啟發(fā)性知識被用于在搜索空間中建立一個“島節(jié)點島節(jié)點”序列，假定有好的路徑通過這個搜索空序列，假定有好的路徑通過這個搜索空間。間。 例如，在計劃通過有障礙的地形時，這些島就例如，在計劃通過有障礙的地形時，這些島就是相應的山。假如是相應的山。假如n n0 0是開始節(jié)點，是開始節(jié)點， n ng g是目標節(jié)點，是目標節(jié)點，( (n n1 1，n n2 2，n nk k) )是這些島的一個序列。我們用是這些島的一個序列。我們用n n0 0作為開始節(jié)點，作為開始節(jié)點，n n1 1作為目標節(jié)點，開始一個啟發(fā)式作為目標節(jié)點，開始一個啟發(fā)式搜索搜索( (用一個同那個目標相適應的啟

13、發(fā)式函數(shù)用一個同那個目標相適應的啟發(fā)式函數(shù)) )。 當搜索找到了一條到當搜索找到了一條到n n1 1的路徑時，就用的路徑時，就用n n1 1作起始作起始點，點，n n2 2作目標點開始另一個搜索，等等，直到我們作目標點開始另一個搜索，等等，直到我們發(fā)現(xiàn)了一條到達發(fā)現(xiàn)了一條到達n ng g的路。的路。 逼近搜索逼近搜索 層次搜索層次搜索 逼近搜索逼近搜索 除了沒有顯式的島集合外，除了沒有顯式的島集合外，層次搜索層次搜索( (hierarchical hierarchical search)search)非常像孤島搜索。非常像孤島搜索。 假定有一些假定有一些“宏算子宏算子”，它們能在一個隱式的島搜

14、索空，它們能在一個隱式的島搜索空間中采取大步驟。一個起始島間中采取大步驟。一個起始島( (在開始節(jié)點附近在開始節(jié)點附近) )和這些宏算和這些宏算子構成了島的一個隱式的子構成了島的一個隱式的“元級元級”超大圖。超大圖。 首先用一個首先用一個元元( (metalevel)metalevel)搜索來搜索這個超大圖，直搜索來搜索這個超大圖，直到找到一條到找到一條宏算子路徑宏算子路徑，它可以讓我們從基級開始節(jié)點附近，它可以讓我們從基級開始節(jié)點附近的一個節(jié)點到達基級目標節(jié)點附近的一個節(jié)點。如果已經(jīng)按的一個節(jié)點到達基級目標節(jié)點附近的一個節(jié)點。如果已經(jīng)按照一個基級算子序列定義過宏算子，宏算子可擴展為一條基照一

15、個基級算子序列定義過宏算子，宏算子可擴展為一條基級算子路徑，然后根據(jù)基級搜索，這條路徑與開始和目標節(jié)級算子路徑，然后根據(jù)基級搜索，這條路徑與開始和目標節(jié)點相連接。點相連接。如果沒有以基級算子定義的宏算子，我們必須順如果沒有以基級算子定義的宏算子，我們必須順著元級搜索中的島節(jié)點路徑進行基級搜索著元級搜索中的島節(jié)點路徑進行基級搜索。 逼近搜索逼近搜索 逼近搜索逼近搜索 例子例子：考慮在一個網(wǎng)格空間中機器人要將一個方塊推到：考慮在一個網(wǎng)格空間中機器人要將一個方塊推到一個給定的目標位置。一個給定的目標位置。 元級計劃元級計劃 ：如何推方：如何推方塊移動到塊移動到G G單元。單元。 基級計劃基級計劃 ：

16、方塊移動：方塊移動的每一步就能展開成的每一步就能展開成一個基級計劃一個基級計劃 。逼近搜索逼近搜索 有限范圍搜索有限范圍搜索 在某些問題中，用任何方法搜索方法發(fā)現(xiàn)一條到在某些問題中，用任何方法搜索方法發(fā)現(xiàn)一條到達目標的路徑從計算上講都是不可能的；而在另外一達目標的路徑從計算上講都是不可能的；而在另外一些問題中，一個動作必須在一個限定的時間內做出選些問題中，一個動作必須在一個限定的時間內做出選擇，而不能在這個時間內搜索到所有到達目標的路徑。擇，而不能在這個時間內搜索到所有到達目標的路徑。 在這些問題中，用有限的時間和計算量找到一條在這些問題中，用有限的時間和計算量找到一條被認為是在到達目標的好路

17、徑上的節(jié)點可能是有用的，被認為是在到達目標的好路徑上的節(jié)點可能是有用的，盡管該節(jié)點并不是目標節(jié)點本身。盡管該節(jié)點并不是目標節(jié)點本身。 當必須終止搜索時，這個替身節(jié)點當必須終止搜索時，這個替身節(jié)點n n* *在搜索前沿的所有節(jié)點中，有最小的在搜索前沿的所有節(jié)點中，有最小的 值值。 f f 假定在一個動作被選擇前的可用搜索時間允許搜索假定在一個動作被選擇前的可用搜索時間允許搜索到深度到深度d d，即所有深度為即所有深度為d d或小于或小于d d的路徑都能被搜索到；的路徑都能被搜索到；在該深度的節(jié)點在該深度的節(jié)點將被稱為將被稱為范圍節(jié)點范圍節(jié)點。那么我們的搜索。那么我們的搜索過程將搜索到深度過程將搜

18、索到深度d d，然后選擇然后選擇 )(minarg*nfnHn作為目標節(jié)點的替代。這個方法叫做作為目標節(jié)點的替代。這個方法叫做有限范圍搜索有限范圍搜索( (limited-horizon search)limited-horizon search)。Korf 1990Korf 1990研究了這研究了這個算法并稱它為個算法并稱它為最小搜索最小搜索( (minimin search)minimin search)。 逼近搜索逼近搜索 一個感知計劃動作系統(tǒng)將在到達一個感知計劃動作系統(tǒng)將在到達n n* *的路徑上采的路徑上采取第一個動作，感知結果狀態(tài)，再迭代搜索，一遍一遍取第一個動作，感知結果狀態(tài)，再

19、迭代搜索，一遍一遍地進行下去。地進行下去。 我們希望朝著一個擁有最優(yōu)啟發(fā)式指標的節(jié)點的第我們希望朝著一個擁有最優(yōu)啟發(fā)式指標的節(jié)點的第一步動作，正好是在朝著目標的路徑上。一步動作，正好是在朝著目標的路徑上。 通常，一個通常，一個agentagent沒有必要去搜索所有到達目標的沒有必要去搜索所有到達目標的路徑；因為不確定性，遠距離搜索可能是不相關的，不路徑；因為不確定性，遠距離搜索可能是不相關的，不能提供比應用在搜索水平上的啟發(fā)式函數(shù)更好的信息。能提供比應用在搜索水平上的啟發(fā)式函數(shù)更好的信息。 逼近搜索逼近搜索 逼近搜索逼近搜索 循環(huán)循環(huán) 在存在不確定性和在存在不確定性和agentagent依賴逼

20、近計劃的所有情依賴逼近計劃的所有情況中，用感知計劃動作循環(huán)可以產生重復的循環(huán)。況中，用感知計劃動作循環(huán)可以產生重復的循環(huán)。即即agentagent可能會回到前面遇到過的環(huán)境狀態(tài)，重復在可能會回到前面遇到過的環(huán)境狀態(tài)，重復在那里采用過的動作。那里采用過的動作。 當然，這種反復并不意味著當然，這種反復并不意味著agentagent永遠不能達到永遠不能達到目標狀態(tài)。目標狀態(tài)。 Korf Korf提出了一個計劃執(zhí)行算法叫提出了一個計劃執(zhí)行算法叫實時實時( (real-real-time)Atime)A* *(RTA(RTA* *) )，它建立了所有已經(jīng)遍歷過的狀態(tài)的它建立了所有已經(jīng)遍歷過的狀態(tài)的一個顯

21、式圖，同時調整這個圖中節(jié)點的一個顯式圖，同時調整這個圖中節(jié)點的 值，使它值，使它們在到達前面已經(jīng)遍歷過的節(jié)點時不會采取動作們在到達前面已經(jīng)遍歷過的節(jié)點時不會采取動作。 h h逼近搜索逼近搜索 建立反應過程建立反應過程 在一個反應型機器中，設計者已為每一個可能的在一個反應型機器中，設計者已為每一個可能的狀態(tài)提前計算了合適的到達目標的動作。存儲這些和狀態(tài)提前計算了合適的到達目標的動作。存儲這些和環(huán)境狀態(tài)相對應的動作可能需要大量的內存。環(huán)境狀態(tài)相對應的動作可能需要大量的內存。 另一方面，反應型另一方面，反應型agentagent常常比計劃型常常比計劃型agentagent反應反應更快。在某些情況下，

22、提前計算更快。在某些情況下，提前計算( (匯編匯編) )一些頻繁使用一些頻繁使用的的離線離線( ( offline)offline)計劃計劃，把它們存儲為反應例程以便，把它們存儲為反應例程以便可以可以在線在線( (online)online)快速產生適當?shù)膭幼?，這樣做是有快速產生適當?shù)膭幼?，這樣做是有益的。益的。 例如例如，離線搜索能計劃一個以狀態(tài)空間圖中的目，離線搜索能計劃一個以狀態(tài)空間圖中的目標節(jié)點為根的標節(jié)點為根的生成樹生成樹( (spanning tree)spanning tree)，它包含從狀它包含從狀態(tài)空間中所有態(tài)空間中所有( (至少很多至少很多) )節(jié)點到達目標的路徑。能從節(jié)點

23、到達目標的路徑。能從目標節(jié)點向后搜索產生一個生成樹。目標節(jié)點向后搜索產生一個生成樹。逼近搜索逼近搜索 例如，一個獲得目標例如，一個獲得目標( (塊塊A A在塊在塊B B上，塊上，塊B B在塊在塊C C上上) )的積木問的積木問題的生成樹如圖所示，它表示了從所有其他節(jié)點到達目標題的生成樹如圖所示，它表示了從所有其他節(jié)點到達目標的路徑。的路徑。 生成樹和局生成樹和局部生成樹能容易部生成樹能容易地轉換成完全反地轉換成完全反應型的應型的T-RT-R程序。程序。 如果：一個如果：一個反應程序為每一反應程序為每一個可能的狀態(tài)指個可能的狀態(tài)指定了一個動作，定了一個動作，就被稱為就被稱為通用計通用計劃劃( (

24、universal universal plan) plan) 或動作策或動作策略略( (action action policy)policy)。 學習啟發(fā)式函數(shù)學習啟發(fā)式函數(shù) 如果如果agentagent沒有一個好的啟發(fā)式函數(shù)來評估到達目沒有一個好的啟發(fā)式函數(shù)來評估到達目標的代價，有時就需要學習這樣一個函數(shù)。首先解釋標的代價，有時就需要學習這樣一個函數(shù)。首先解釋一個非常簡單的適合特定情況的學習過程，在這種情一個非常簡單的適合特定情況的學習過程，在這種情況下可能會存儲所有可能節(jié)點的一個顯式列表。況下可能會存儲所有可能節(jié)點的一個顯式列表。 這個特殊的學習過程從一個隨機步開始，執(zhí)行一這個特殊的學

25、習過程從一個隨機步開始，執(zhí)行一個由評估函數(shù)導向的搜索過程，最終慢慢到達目標，個由評估函數(shù)導向的搜索過程，最終慢慢到達目標，在隨后的試驗中向后傳播來自更好路徑的更好的值。在隨后的試驗中向后傳播來自更好路徑的更好的值。連續(xù)的環(huán)境反饋減少了不確定性和彌補一個連續(xù)的環(huán)境反饋減少了不確定性和彌補一個 agentagent缺缺乏對自己動作結果的知識了解。乏對自己動作結果的知識了解。獎賞代替目標獎賞代替目標 在討論狀態(tài)空間的搜索策略中，假定在討論狀態(tài)空間的搜索策略中，假定agentagent有一有一個簡單的短期任務，它由一個目標條件描述。目標改個簡單的短期任務，它由一個目標條件描述。目標改變著世界，直到它的

26、圖標模型變著世界，直到它的圖標模型( (以數(shù)據(jù)結構的方式以數(shù)據(jù)結構的方式) )滿滿足給定的條件。足給定的條件。 在很多實際問題中，任務并不像剛才描述的那樣在很多實際問題中，任務并不像剛才描述的那樣簡單。相反，任務可能是正在進行的。用戶按照給簡單。相反，任務可能是正在進行的。用戶按照給agentagent一些偶然的正負一些偶然的正負獎賞獎賞( (reward)reward)來表達他對任務來表達他對任務執(zhí)行的滿意程度。執(zhí)行的滿意程度。 agentagent的任務的任務是把它收到的獎賞數(shù)量最大化是把它收到的獎賞數(shù)量最大化( (一個一個簡單到達目標的特例也可用這種框架來描述，在這個簡單到達目標的特例也

27、可用這種框架來描述，在這個框架中，當框架中，當agentagent到達目標時，給到達目標時，給agentagent一個正的獎賞一個正的獎賞( (只有一次只有一次) )，而每次當，而每次當agentagent采取動作時給它一個負采取動作時給它一個負的獎賞的獎賞( (根據(jù)動作的代價根據(jù)動作的代價)。 獎賞代替目標獎賞代替目標 在這種任務環(huán)境下，我們要尋找使獎賞最大化的在這種任務環(huán)境下，我們要尋找使獎賞最大化的動作策略。動作策略。 對于正在進行還沒有終止的任務，存在的一個問對于正在進行還沒有終止的任務，存在的一個問題是未來的獎賞可能是無限的，因此難以決定如何使題是未來的獎賞可能是無限的，因此難以決定如何使它最大化。它最大化。 一種處理辦法是通過一些因子對未來的獎賞打折一種處理辦法是通過一些因子對未來的獎賞打折扣，即扣，即agen