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

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

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

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

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

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

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

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

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

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

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

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