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

1、第二部分 狀態(tài)空間搜索第7章 能計劃的Agent存儲與計算狀態(tài)空間圖顯式狀態(tài)空間搜索基于特征的狀態(tài)空間圖記號補充讀物和討論7.1 存儲與計算響應(yīng)型agent的動作功能幾乎沒有做任何計算。從本質(zhì)上講，這些agent執(zhí)行的動作或者由它們的設(shè)計者、或者通過學(xué)習(xí)、或者通過演算過程、或者是由以上幾方面的組合而選擇它們的。這些動作通過表、產(chǎn)生規(guī)則描述給定特征向量動作的組合邏輯電路來實現(xiàn)。在計算機科學(xué)中，這種實現(xiàn)傾向于經(jīng)典的時空權(quán)衡的“空間”一方。它們是基于空間或存儲的實現(xiàn)對設(shè)計者知識的匯編一個能在復(fù)雜環(huán)境下執(zhí)行復(fù)雜任務(wù)的反應(yīng)型機器需要大量（也是無法計算的）存儲。而且，這樣一個反應(yīng)型機器的設(shè)計者需要有超人類

2、的預(yù)見能力，要為該機器能遇到的所有可能情況預(yù)期一個合適的反應(yīng)。這啟發(fā)我們可以考慮用時間換取空間，用適應(yīng)性代替顯式的設(shè)計。首先，考慮反應(yīng)型機器設(shè)計者必須做的一些計算的動作函數(shù)。這些計算當然會需要時間，但是他們將減少agent的存儲要求和設(shè)計者的負擔(dān)。7.1 存儲與計算我們要考慮的一些計算是推測在任何給定的情況下，某些動作的可能結(jié)果。也許最重要的是如果預(yù)期計算的結(jié)果能被自動地學(xué)習(xí)或者演化，那么使用該結(jié)果的agent就能在那些連設(shè)計者都無法預(yù)見的情況下，也可以選擇合適的動作來執(zhí)行為了推測一個動作的結(jié)果，一個agent必須有一個自身所處環(huán)境的模型和一些結(jié)果模型，這些結(jié)果模型是agent對其環(huán)境模型的動

3、作結(jié)果。因此，真正的動作只有在模擬環(huán)境是安全和有效時才會發(fā)生作用。.2 狀態(tài)空間圖考慮一個有A、B、C三個積木的網(wǎng)格空間，開始時，三個積木都在地板上。假如機器人的任務(wù)是把它們堆起來以便A在B的上面， B在C的上面，C在地板上。假定機器人能夠?qū)ζ涿恳粋€動作對環(huán)境的結(jié)果建模，它可以通過一對環(huán)境模型一個代表動作執(zhí)行前的環(huán)境狀態(tài)，另一個代表動作執(zhí)行后的環(huán)境狀態(tài)來建模。假設(shè)機器人能夠把其上沒有任何其他積木的積木x移到另一個地方y(tǒng)，y是地板或其上沒有其他積木的積木?？梢酝ㄟ^一個模式的實例對這些動作建模，該模式表示為move(x,y)，其中x可以是A、B、C中的任何一個，y可以是A、B、C和地板中的任何一個

4、。我們也知道這個方法中的一些實例（如move(A,A)）是不可執(zhí)行的動作。這個方法的實例，如move(A,C)被稱為算子（operator）。因此算子是動作的模型。.2 狀態(tài)空間圖用列表結(jié)構(gòu)圖標模型，可表示所有積木都在地面時能采用的所有動作的模型。在這些結(jié)果中的(AB) (C) ) 和(A) (BC)在某些方面似乎比其他更接近于我們的目標(ABC)。因此，僅考慮單個動作的預(yù)期結(jié)果，機器人寧愿執(zhí)行動作move(A,B)和move(B,C)。當然，機器人還沒有采取真正的動作。在一個模擬環(huán)境中，只向前看一步常常就能產(chǎn)生有用的預(yù)期效果，但是多看幾步，也許直到任務(wù)完成的所有步驟都看到后就會發(fā)現(xiàn)一些捷徑，

5、從而避免走彎路。跟蹤幾個可選動作序列結(jié)果的最有用的結(jié)構(gòu)是有向圖。一個agent通過它的動作產(chǎn)生的環(huán)境集合能用一個有向圖表示。有向圖的節(jié)點代表每個環(huán)境，弧代表算子。節(jié)點表示可以是基于圖標的或基于特征的。盡管兩種特征都會考慮，但先從圖標開始。.2 狀態(tài)空間圖(AB)( C)(A)(B) (C )(B)(AC)(BA)(C)(BC)(A)(CB)(A)(CA)(B)移動一個積木的效果move(A,B)move(C,B).2 狀態(tài)空間圖如果大量可區(qū)分的環(huán)境狀態(tài)足夠小，那么一個代表所有可能動作和狀態(tài)的圖就能被顯式存儲。這種環(huán)境模型和動作圖被稱為狀態(tài)空間圖（state-space graph）。圖結(jié)構(gòu)表示

6、可能世界的優(yōu)點之一是圖中的任何節(jié)點能代表一個目標狀態(tài)也許是諸如認為的一些外部源指定的目標。這種任務(wù)靈活性可以和我們前面學(xué)習(xí)過的簡單目的agent形成對照。為了發(fā)現(xiàn)到達指定目標的一組動作，機器人只要能在圖中發(fā)現(xiàn)一條代表初始狀態(tài)節(jié)點到目標節(jié)點的路徑就可以了。然后就能從該路徑邊上的標簽讀出到達目標的動作。搭積木的機器人的任務(wù)是到達任務(wù)(CBA)，初始狀態(tài)是(ABC)。動作序列將是move(A,floor), move(B,A), move(C, B)順著路徑到達目標的所有弧的算子可以組合稱為一個序列的計劃。搜索這個序列的過程稱為規(guī)劃。這種從一系列動作結(jié)果得到的世界狀態(tài)的預(yù)測過程稱為規(guī)劃方案。.2 狀

7、態(tài)空間圖在這種方式下，為了獲得目標而執(zhí)行的一系列動作需要依靠若干假設(shè)。Agent必須能在圖節(jié)點中表示所有相關(guān)的環(huán)境狀態(tài)，它必須有在一對節(jié)點間如何動作的精確模型。動作必須總有其模型化的結(jié)果在agent的操縱系統(tǒng)中不能有錯誤或不確定性。agent的感知系統(tǒng)必須精確地指定開始節(jié)點，并且沒有任何其他的agent或動態(tài)過程會改變環(huán)境。如果所有的這些假設(shè)滿足，且搜索的目標狀態(tài)的時間允許，就能規(guī)劃，并執(zhí)行一個完整序列的動作，不需要任何環(huán)境的信息反饋.2 狀態(tài)空間圖盡管這些假設(shè)在大多數(shù)實際應(yīng)用中不能滿足，圖搜索計劃還是一個相當有用和重要的思想。它既可以被一般化，以適應(yīng)更少約束假設(shè)的設(shè)置，也能被作為一個適應(yīng)這種

8、設(shè)置的嵌入結(jié)構(gòu)部件。7.3 顯式狀態(tài)空間搜索顯式圖搜索方法涉及到在圖節(jié)點上傳播“標記”。把開始節(jié)點標記為0，然后順著圖的邊，連續(xù)傳播更大的整數(shù)直至遇到目標節(jié)點。然后順著數(shù)字下降序列從目標回溯到開始節(jié)點。順著開始點到目標點路徑上的動作序列就是獲得目標應(yīng)該采取的動作。這種方法需要O(n)步。n是圖中的節(jié)點數(shù)目。如果只有一個目標節(jié)點，這個過程也可以從相反方向?qū)崿F(xiàn)從目標節(jié)點開始，直到某個整數(shù)遇到了開始節(jié)點。搜索過程中放在節(jié)點上的數(shù)字可以作為該節(jié)點上的一種人工勢函數(shù)，并且開始節(jié)點有一個全局最小值。相反路徑（從目標到開始）順著這個函數(shù)的“梯度”下降。從(BAC)轉(zhuǎn)移到(ABC)的標記傳播過程與所謂的廣度優(yōu)

9、先算法（breadth-first search）相一致。7.3 顯式狀態(tài)空間搜索把標記一個節(jié)點的后繼節(jié)點的過程稱為擴展（expansion）。擴展將標記放在所有已標記過的節(jié)點的未標記的相鄰節(jié)點上。應(yīng)將哪一個已標記但還沒有擴展的節(jié)點作為下一個擴展點是一個很重要的效率問題。在廣度優(yōu)先搜索中，下一個要擴展的節(jié)點是其節(jié)點標識數(shù)不大于任何其他沒有擴展的節(jié)點標識數(shù)的節(jié)點。在擴展標識為j的節(jié)點之前，先要擴展標識為i的所有節(jié)點，條件是ij。其他算法有不同的節(jié)點擴展選擇。7.4 基于特征的狀態(tài)空間用圖標模型標識節(jié)點來解釋狀態(tài)空間是相當直接的可以很容易地使狀態(tài)上的動作結(jié)果形象化?？梢远x一個有特征標識的節(jié)點圖。

10、需要一種方法來描述一個動作是如何影響特征的。STRIPS系統(tǒng)使用這種技術(shù)。其基本思想是定義一個有三個列表的算子，第一個是前提列表，指定了值為1和0的特征，以便可以應(yīng)用動作。第二個是刪除列表，列出其值從1變?yōu)?的特征。第三個是從0變?yōu)?的加入列表。在刪除和加入列表中沒有明確提到的特征值是不變的。這三個列表構(gòu)成了一個STRIPS算子一個動作結(jié)果模型。7.4 基于特征的狀態(tài)空間也能訓(xùn)練一個神經(jīng)網(wǎng)絡(luò)，從它在t-1時刻的值和該時刻采取的動作來學(xué)習(xí)預(yù)測一個特征向量在時刻t時的值在訓(xùn)練后，預(yù)測網(wǎng)絡(luò)能被用來計算來源于各種動作的特征向量。這些向量反過來又能作為網(wǎng)絡(luò)的新輸入來預(yù)測兩步以后的特征向量。一個相似的過程

11、（基于統(tǒng)計群技術(shù)）被用來控制一個移動機器人。因為在預(yù)測過程中不可避免的錯誤，用這種方法企圖作出更大的移動都證實是徒勞的。7.5 圖記號一個圖由一組節(jié)點（不一定是有限的）構(gòu)成，節(jié)點由弧連接，這些弧是從節(jié)點的一方指向另一方的有向弧，這樣的弧被稱為有向圖（direct graph）。節(jié)點由環(huán)境狀態(tài)模型標識，弧由動作名標識。如果弧是從ni指向nj ，那么nj就是ni的后繼（或者叫孩子）， ni是nj的雙親。在我們研究的圖中，一個節(jié)點只能有有限個后繼。如果對節(jié)點中的每一個都可以是后繼。在這種情況下，用邊代替這一節(jié)點。只包括邊的圖稱為無向圖。在隨后有關(guān)圖的表示中，弧帶有箭頭，而邊沒有。一個有限的有向樹是有

12、向圖的特殊情況。在有向樹中（除了一個節(jié)點），每個節(jié)點只有一個父親。沒有父親的節(jié)點被稱為根節(jié)點。7.5 圖記號在樹中沒有后繼的節(jié)點稱為末端節(jié)點或葉節(jié)點，我們稱根節(jié)點的深度為0，樹上任何其他節(jié)點的深度是其父節(jié)點的深度加1。一個有根的無向樹（用邊代替弧）是一個無向圖，這里一對節(jié)點之間只有一條路徑。在理論分析中，有一些樹有這樣的特征，即除了葉節(jié)點外，所有的節(jié)點都有相同數(shù)量b個后繼。在這種情況下，b稱為這個樹的分枝因子。一個節(jié)點序列(n1,n2,nk)，ni+1是ni的后繼，i=1,2,k-1被稱為從節(jié)點n1到nk的長度為k的一條路徑（另外，我們可以把連接節(jié)點的弧序列定義為一條路徑）。如果存在從節(jié)點ni到nj的路徑，那么就說從ni可以訪問nj 。 nj就是ni的后代， ni是nj的祖先。7.5 圖記號通過分配一個正值給弧來代表執(zhí)行相應(yīng)的動作的代價常常是方便的。用符號c(ni,nj)（或者有時是c(a)）指示弧a從ni指向nj的代價。在后面的討論中，假定這些代價比任意小的正數(shù)都大。兩個節(jié)點之間的路徑代價是連接路徑上節(jié)點間所有弧的代價的總和。在某些問題中，我們想找到兩個節(jié)點之間的最小代價路徑。這個路徑被稱為最佳路