復(fù)試1人工智能10

1、第10章 計(jì)劃、動(dòng)作和學(xué)習(xí)在Agent設(shè)計(jì)中的位置第一部分：響應(yīng)機(jī)器刺激響應(yīng)函數(shù)人工神經(jīng)元網(wǎng)絡(luò)、遺傳編程第二部分：狀態(tài)空間搜索盲目搜索：廣度優(yōu)先、深度優(yōu)先啟發(fā)式搜索：存在問題狀態(tài)空間搜索的假設(shè)條件包括：1）感知是確定的、正確的、完全的2）動(dòng)作模型是確定的、有結(jié)果的3）在規(guī)劃和動(dòng)作執(zhí)行過程中，環(huán)境是不變的因此，Agent并不總能制訂一個(gè)完善的計(jì)劃，并按其執(zhí)行？主要內(nèi)容感知/計(jì)劃/動(dòng)作循環(huán)逼近搜索學(xué)習(xí)啟發(fā)式函數(shù)（機(jī)器學(xué)習(xí)，不是重點(diǎn)）獎(jiǎng)賞代替目標(biāo)（增強(qiáng)學(xué)習(xí)，也不是重點(diǎn)）補(bǔ)充讀物和討論10.1 感知/計(jì)劃/動(dòng)作循環(huán)1）知覺過程不可能總是提供環(huán)境狀態(tài)的必須信息（由于噪聲或者對(duì)重要的特性不敏感）。當(dāng)兩種不

2、同的環(huán)境狀態(tài)引起相同的傳感輸入時(shí)，稱為感知混淆（perceptual aliasing）。2) 動(dòng)作并不總有其模型結(jié)果（由于模型不夠精確，或者受動(dòng)器系統(tǒng)在執(zhí)行動(dòng)作時(shí)偶爾會(huì)產(chǎn)生錯(cuò)誤）。10.1 感知/計(jì)劃/動(dòng)作循環(huán)3）可能在環(huán)境中有其他的物理過程或其他的Agent（例如，風(fēng)雨雷電，在游戲中有對(duì)手）。這些過程可能會(huì)改變環(huán)境以致于干擾Agent的動(dòng)作。4）外部作用的存在會(huì)引起其他的問題：在構(gòu)造一個(gè)計(jì)劃期間，環(huán)境可能變得與原來的計(jì)劃不相干。這種困難使得花費(fèi)太多的時(shí)間為一個(gè)Agent進(jìn)行計(jì)劃而變得無意義。10.1 感知/計(jì)劃/動(dòng)作循環(huán)5）Agent可能在完成一個(gè)到達(dá)目標(biāo)狀態(tài)的搜索之前被要求動(dòng)作。6）即使

3、Agent有充分的計(jì)算時(shí)間，但是計(jì)算要求的空間資源不允許搜索進(jìn)行到目標(biāo)狀態(tài)。10.1 感知/計(jì)劃/動(dòng)作循環(huán)（解決方法）方法之一：用概率方法來形式化知覺、環(huán)境和受動(dòng)器的不確定性。處理動(dòng)作的不確定效果的一種正式方法是假定對(duì)一定狀態(tài)下的每一個(gè)可執(zhí)行動(dòng)作，結(jié)果狀態(tài)由一個(gè)已知的概率分布給出。在這種情況下找到合適的動(dòng)作被稱為Markov決策問題（Markov decision problem, MDP）。方法之二：用各種附加的假設(shè)和近似來消除這些困難的影響。10.1 感知/計(jì)劃/動(dòng)作循環(huán)（解決方法）本書提出一個(gè)感知/計(jì)劃/動(dòng)作結(jié)構(gòu)（sense/plan/act），在很多應(yīng)用中避開了上述的一些復(fù)雜性。該結(jié)構(gòu)

4、的基本原理是即使動(dòng)作偶爾產(chǎn)生了沒有預(yù)料的結(jié)果，或者Agent有時(shí)不能決定它處于哪一種環(huán)境狀態(tài)下，但是通過保證Agent從它的執(zhí)行環(huán)境中得到連續(xù)的反饋，這些困難可以被充分地解決。10.1 感知/計(jì)劃/動(dòng)作循環(huán) （解決方法）確保連續(xù)反饋的一個(gè)方法是計(jì)劃一個(gè)動(dòng)作序列，只執(zhí)行這個(gè)序列中的第一個(gè)動(dòng)作，感知結(jié)果環(huán)境狀態(tài)，重新計(jì)算開始節(jié)點(diǎn)，然后重復(fù)上述過程。這種方式選擇動(dòng)作的Agent被叫做感知/計(jì)劃/動(dòng)作Agent。為了使該方法有效，計(jì)算一個(gè)計(jì)劃的時(shí)間必須比每個(gè)動(dòng)作的執(zhí)行時(shí)間要少。知覺處理一個(gè)感知/計(jì)劃/動(dòng)作Agent的結(jié)構(gòu)傳感器輸入當(dāng)前狀態(tài)狀態(tài)空間圖計(jì)劃（圖搜索）尋找第一個(gè)動(dòng)作動(dòng)作目標(biāo)（所需狀態(tài)）10.

5、1 感知/計(jì)劃/動(dòng)作循環(huán)在感知/計(jì)劃/動(dòng)作循環(huán)中的環(huán)境反饋允許解決感知、環(huán)境和受動(dòng)器的一些不確定性。然而，為使反饋有效，必須保證感知和動(dòng)作一般來說是精確的。在很多應(yīng)用中，這種假設(shè)是現(xiàn)實(shí)的。畢竟，提供感覺、感知和受動(dòng)器特征適合于任務(wù)要求是Agent設(shè)計(jì)人員的的任務(wù)。10.2 逼近搜索對(duì)以產(chǎn)生計(jì)劃質(zhì)量為代價(jià)的有限計(jì)算或時(shí)間資源的搜索算法進(jìn)行修改，這些計(jì)劃可能不是最佳的，或者可能不是總能可靠地到達(dá)目標(biāo)狀態(tài)。定性地講，只要第一個(gè)動(dòng)作有縮短到達(dá)目標(biāo)距離的趨勢(shì)（平均情況），經(jīng)感知/計(jì)劃/動(dòng)作的多次迭代將最終到達(dá)目標(biāo)。10.2 逼近搜索放寬產(chǎn)生最優(yōu)計(jì)劃的要求常會(huì)減少找到一個(gè)計(jì)劃的計(jì)算代價(jià)?？梢詮膬蓚€(gè)方面來減

6、少代價(jià)。一方面，找到到達(dá)目標(biāo)個(gè)一條完整路徑但不必要求它是最優(yōu)的；另一方面，找到一條局部的路徑，它不要求已達(dá)到目標(biāo)節(jié)點(diǎn)。10.2 逼近搜索一個(gè)A*類型的搜索可用于這兩種方法。對(duì)于前者，可以用一個(gè)不可接納的啟發(fā)式函數(shù)對(duì)于后者，在到達(dá)目標(biāo)前（用可接納的或不可接納的啟發(fā)式函數(shù)）退出搜索。10.2 逼近搜索在到達(dá)目標(biāo)前退出搜索是任意時(shí)間算法（anytime algorithm）的一個(gè)例子。任意時(shí)間算法能在任何時(shí)刻停止，結(jié)果的質(zhì)量會(huì)隨著運(yùn)行時(shí)間的增加而改善。10.2.1 孤島驅(qū)動(dòng)搜索在孤島驅(qū)動(dòng)（island-driver）搜索中，來自問題領(lǐng)域的啟發(fā)性知識(shí)被用于在搜索空間中建立一個(gè)“島節(jié)點(diǎn)”序列。例如，乘船

7、去美國(guó)，可以經(jīng)過漢城、大阪、夏威夷、美國(guó)西海岸10.2.1 孤島驅(qū)動(dòng)搜索例如，在計(jì)劃通過有障礙的地形時(shí)，這些島就是相應(yīng)的山。假如是n0開始節(jié)點(diǎn)， ng是目標(biāo)節(jié)點(diǎn)（ n1 ， n2 ， ng ）是這些島的一個(gè)序列?？梢杂胣0作為開始節(jié)點(diǎn)， n1作為目標(biāo)節(jié)點(diǎn)，開始一個(gè)啟發(fā)式搜索（用一個(gè)同那個(gè)目標(biāo)相適應(yīng)的啟發(fā)式函數(shù)）。10.2.1 孤島驅(qū)動(dòng)搜索當(dāng)搜索找到了一條到n1的路徑時(shí)，就用n1作起始點(diǎn)， n2作目標(biāo)點(diǎn)開始另一個(gè)搜索，等等，直到發(fā)現(xiàn)了一條到ng的路徑。10.2.1 孤島驅(qū)動(dòng)搜索孤島驅(qū)動(dòng)搜索搜索空間中的島局部搜索10.2.2 層次搜索除了沒有顯式的島集合外，層次搜索（hierarchical se

8、arch）非常像孤島搜索。假定有一些“宏算子”，它們能在一個(gè)隱式的島搜索空間中采取大步驟。一個(gè)起始島（在開始節(jié)點(diǎn)附近）和這些宏算子構(gòu)成了島的一個(gè)隱式的“元級(jí)”超大圖。10.2.2 層次搜索首先用一個(gè)元（metalevel）搜索來搜索這個(gè)超大圖，直到找到一條宏算子路徑，它可以讓我們從基級(jí)開始節(jié)點(diǎn)附近的一個(gè)節(jié)點(diǎn)到達(dá)基級(jí)目標(biāo)節(jié)點(diǎn)附近的一個(gè)節(jié)點(diǎn)。如果已經(jīng)按照一個(gè)基級(jí)算子序列定義過宏算子，宏算子可擴(kuò)展為一條基級(jí)算子路徑，然后根據(jù)基級(jí)搜索，這條路徑與開始和目標(biāo)節(jié)點(diǎn)相連接。10.2.2 層次搜索在層次計(jì)劃中，如果在計(jì)劃期間環(huán)境可能變化，僅僅展開元級(jí)計(jì)劃的開始幾步是明智的。僅僅展開第一個(gè)元級(jí)步就可以讓基級(jí)動(dòng)作

9、去執(zhí)行，在它執(zhí)行時(shí)，環(huán)境反饋可用來開發(fā)一個(gè)更新的元級(jí)計(jì)劃。在AIPS中，Hierarchical Planning是一種常用的規(guī)劃算法10.2.3 有限范圍搜索在有些問題中，用任何方法搜索發(fā)現(xiàn)一條到達(dá)目標(biāo)的路徑從計(jì)算上講都是不可能的；而在另一些問題中，一個(gè)動(dòng)作必須在一個(gè)限定的時(shí)間內(nèi)作出選擇，而不能在這個(gè)時(shí)間內(nèi)搜索到所有到達(dá)目標(biāo)的路徑。在這些問題中，用有限的時(shí)間和計(jì)算量找到一條被認(rèn)為是在到達(dá)目標(biāo)的好路徑上的節(jié)點(diǎn)可能是有用的，盡管該節(jié)點(diǎn)并不是目標(biāo)節(jié)點(diǎn)本身。當(dāng)必須終止搜索時(shí)，這個(gè)替身節(jié)點(diǎn)n*在搜索前沿的所有節(jié)點(diǎn)中，有最小的啟發(fā)式函數(shù)值10.2.3 有限范圍搜索假定在一個(gè)動(dòng)作被選擇前的可用搜索時(shí)間允許

10、搜索到深度d，即所有深度為d或小于d的路徑都能被搜索到；在該深度的節(jié)點(diǎn)將被稱為范圍節(jié)點(diǎn)。那么我們的搜索過程將搜索到深度d，然后進(jìn)行選擇。10.2.3 有限范圍搜索作為目標(biāo)節(jié)點(diǎn)的替代。這個(gè)方法叫做 有限范圍搜索（limited-horizon search）。該算法也被稱為最小搜索（minimin search）。一個(gè)感知/計(jì)劃/動(dòng)作系統(tǒng)將在到達(dá)n*的路徑上采取第一個(gè)動(dòng)作，感知結(jié)果狀態(tài)，再迭代搜索，一遍一遍地進(jìn)行下去。希望朝著一個(gè)擁有最優(yōu)啟發(fā)式指標(biāo)的節(jié)點(diǎn)的第一個(gè)動(dòng)作，正好在朝著目標(biāo)的路徑上。10.2.3 有限范圍搜索有限范圍搜索能處理一個(gè)到深度d深度優(yōu)先搜索而高效地執(zhí)行。使用單調(diào)函數(shù) 評(píng)估節(jié)點(diǎn)可

11、以極大地減少搜索工作。一旦達(dá)到搜索范圍的第一個(gè)節(jié)點(diǎn)n1，當(dāng)節(jié)點(diǎn)n的啟發(fā)式函數(shù)值大于節(jié)點(diǎn)n的啟發(fā)式函數(shù)值 ，就能在其他節(jié)點(diǎn)n下終止搜索。 10.2.4 循環(huán)在存在不確定性和Agent依賴逼近計(jì)劃的所有情況中，用感知/計(jì)劃/動(dòng)作循環(huán)可以產(chǎn)生重復(fù)的循環(huán)。即Agent可能會(huì)回到前面遇到過的狀態(tài)，重復(fù)在那里采用過的動(dòng)作。當(dāng)然，這種反復(fù)并不意味著Agent永遠(yuǎn)不能達(dá)到目標(biāo)狀態(tài)。10.2.4 循環(huán)Koaf提出了一個(gè)計(jì)劃執(zhí)行算法叫實(shí)時(shí)（real-time）A*(RTA*)，它建立了所有已經(jīng)遍歷過的狀態(tài)的一個(gè)顯式圖，同時(shí)調(diào)整這個(gè)圖中節(jié)點(diǎn)的值，使它們?cè)诘竭_(dá)前面已經(jīng)遍歷過的節(jié)點(diǎn)時(shí)不會(huì)采取動(dòng)作。10.2.5 建立反應(yīng)過程在一個(gè)反應(yīng)型機(jī)器中，設(shè)計(jì)者已為每一個(gè)可能的狀態(tài)提前計(jì)算了到達(dá)目標(biāo)的動(dòng)作。存儲(chǔ)這些和環(huán)境狀態(tài)相對(duì)應(yīng)的動(dòng)作可能需要大量的內(nèi)存。另一方面，反應(yīng)型Agent常常比計(jì)劃型Agent