第10章計(jì)劃、動(dòng)作和學(xué)習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、到達(dá)目標(biāo)的路徑。能從目標(biāo)節(jié)點(diǎn)向后搜索產(chǎn)生一個(gè)生成樹。目標(biāo)節(jié)點(diǎn)向后搜索產(chǎn)生一個(gè)生成樹。逼近搜索逼近搜索 例如，一個(gè)獲得目標(biāo)例如，一個(gè)獲得目標(biāo)( (塊塊A A在塊在塊B B上，塊上，塊B B在塊在塊C C上上) )的積木問的積木問題的生成樹如圖所示，它表示了從所有其他節(jié)點(diǎn)到達(dá)目標(biāo)題的生成樹如圖所示，它表示了從所有其他節(jié)點(diǎn)到達(dá)目標(biāo)的路徑。的路徑。 生成樹和局生成樹和局部生成樹能容易部生成樹能容易地轉(zhuǎn)換成完全反地轉(zhuǎn)換成完全反應(yīng)型的應(yīng)型的T-RT-R程序。程序。 如果：一個(gè)如果：一個(gè)反應(yīng)程序?yàn)槊恳环磻?yīng)程序?yàn)槊恳粋€(gè)可能的狀態(tài)指?jìng)€(gè)可能的狀態(tài)指定了一個(gè)動(dòng)作，定了一個(gè)動(dòng)作，就被稱為就被稱為通用計(jì)通用計(jì)劃劃( (

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

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

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

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