第2章刺激響應(yīng)agent

1、第一部分第一部分 響應(yīng)機器響應(yīng)機器2.1 2.1 感知和動作感知和動作刺激響應(yīng)刺激響應(yīng)( (Stimulus-Response,S-RStimulus-Response,S-R)agent)agent：不具備內(nèi)部狀態(tài)而僅對其所處環(huán)境的即刻刺激有所反應(yīng)的機器不具備內(nèi)部狀態(tài)而僅對其所處環(huán)境的即刻刺激有所反應(yīng)的機器. 先來看這樣一個在二維先來看這樣一個在二維網(wǎng)格空間世界里的機器人，網(wǎng)格空間世界里的機器人，如圖所示。這一機器人的如圖所示。這一機器人的世界有完整的邊界線，可世界有完整的邊界線，可能還包括如圖所示的其他能還包括如圖所示的其他龐大的固定物體。龐大的固定物體。 這一世界里沒有這一世界里沒有“稠

2、密稠密空間空間( (tight space)”(tight space)”(即即物體與邊界線之間的距離物體與邊界線之間的距離只有一個單元格只有一個單元格) )。 要求：這個機器人完要求：這個機器人完成以下動作：走到與一成以下動作：走到與一邊界或物體毗鄰的單元邊界或物體毗鄰的單元格中，然后沿著它的格中，然后沿著它的 邊邊界一直走下去。界一直走下去。 該機器人能夠向與它同行或同列的毗鄰的該機器人能夠向與它同行或同列的毗鄰的( (空缺空缺) )單單元格移動，共有如下四種動作：元格移動，共有如下四種動作： northnorth：機器人在網(wǎng)格中向上移動一個單元機器人在網(wǎng)格中向上移動一個單元 eastea

3、st： 機器人在網(wǎng)格中向右移動一個單元機器人在網(wǎng)格中向右移動一個單元 southsouth：機器人在網(wǎng)格中向下移動一個單元機器人在網(wǎng)格中向下移動一個單元 west west： 機器人在網(wǎng)格中向左移動一個單元機器人在網(wǎng)格中向左移動一個單元 給定了機器人適應(yīng)的某種世界的特性給定了機器人適應(yīng)的某種世界的特性( (如前圖所示如前圖所示) )、機器人完成的任務(wù)機器人完成的任務(wù)( (沿邊界移動沿邊界移動) )和機器人傳感器和電機的和機器人傳感器和電機的功能，設(shè)計者的工作就是說明為此任務(wù)選擇適當動作的傳功能，設(shè)計者的工作就是說明為此任務(wù)選擇適當動作的傳感器輸入感器輸入( (示例中表示為示例中表示為s1,s8

4、)s1,s8)的功能。的功能。 通常我們把從傳感器信號中計算動作的過程分為兩個分通常我們把從傳感器信號中計算動作的過程分為兩個分開的階段，如下圖所示。開的階段，如下圖所示。動作和知覺處理部分動作和知覺處理部分 知覺處理階段產(chǎn)生一個特征向量知覺處理階段產(chǎn)生一個特征向量X(xX(x1 1， x xi i, ,，x xn n) )。 動作計算階段選擇一個以特征向量為基礎(chǔ)的動作：動作計算階段選擇一個以特征向量為基礎(chǔ)的動作：各特征值既可以是真正的數(shù)字各特征值既可以是真正的數(shù)字( ( numeric feature, numeric feature,數(shù)字數(shù)字特征特征) )，也可以是范疇，也可以是范疇( (

5、 categorical featurecategorical feature，范疇特范疇特征征)()(范疇特征的值是名字或特性，譬如：特征值范疇特征的值是名字或特性，譬如：特征值“顏色顏色”可能是可能是“紅紅”、“藍藍”或或“綠綠”)”)。 二進制特征這一特殊例子既可視作數(shù)字二進制特征這一特殊例子既可視作數(shù)字(0(0，1)1)，也，也可視作范疇可視作范疇( (真，假真，假) )。設(shè)計者選擇特征來將其與機器人。設(shè)計者選擇特征來將其與機器人的環(huán)境特性相聯(lián)系，而此環(huán)境特性又與由此特征描述的的環(huán)境特性相聯(lián)系，而此環(huán)境特性又與由此特征描述的狀態(tài)中機器應(yīng)做的動作密切相關(guān)。狀態(tài)中機器應(yīng)做的動作密切相關(guān)。感

6、知感知對當前的任務(wù)，剛好有四個對計算適當動作有用的傳感器的二進對當前的任務(wù)，剛好有四個對計算適當動作有用的傳感器的二進制特征值，分別制特征值，分別 x1、x2、x3 和和 x4 來表示來表示在每個圖中，當且僅當至少一個陰影單元為非空時，所在每個圖中，當且僅當至少一個陰影單元為非空時，所示的特征值為示的特征值為1 1動作動作 首先，如果特征值都不是首先，如果特征值都不是1（即機器人感知到它周圍的（即機器人感知到它周圍的單元格全部空缺），則它可向任一方向移動直至遇到邊界。單元格全部空缺），則它可向任一方向移動直至遇到邊界。 我們先讓它向北移動。若至少有一個特征值為我們先讓它向北移動。若至少有一個特

7、征值為1 1，沿邊界的，沿邊界的行動則按以下規(guī)則完成：行動則按以下規(guī)則完成：若若x1=1x1=1且且x2=0,x2=0,則向東（則向東（easteast）移動；移動；若若x2=1x2=1且且x3=0,x3=0,則向南則向南( (south)south)移動；移動；若若x3=1x3=1且且x4=0,x4=0,則向西則向西( (west)west)移動；移動；若若x4=1x4=1且且x1=0,x1=0,則向北則向北( (north)north)移動；移動；布爾代數(shù)布爾代數(shù)與，或，非（補）與，或，非（補）“與與”，“或或”具有具有交換性同時具有結(jié)合性。交換性同時具有結(jié)合性。 由單個變量組成的布爾函數(shù)

8、，稱為由單個變量組成的布爾函數(shù)，稱為原子（原子（atom atom ）; ;由單由單個變量或其補組成的布爾函數(shù)，稱為個變量或其補組成的布爾函數(shù)，稱為文字（文字（literalliteral）。 布爾代數(shù)遵守布爾代數(shù)遵守 De.Morgan De.Morgan 定律。定律。 布爾函數(shù)有多種形式，其中一種重要的形式為：布爾函數(shù)有多種形式，其中一種重要的形式為：1 12 2 k k，這，這里里i i為文字為文字，這樣書寫的函數(shù)稱為，這樣書寫的函數(shù)稱為“文字合取式文字合取式 ( (conjunction)conjunction) ” 或或“單項式（單項式（monomialmonomial）”。這一合取

9、式本身稱為一個這一合取式本身稱為一個項式項式。項式的。項式的大小即為其所含文字的大小即為其所含文字的總數(shù)總數(shù)。布爾函數(shù)的類別和形式布爾函數(shù)的類別和形式 一個一個子句子句是形如是形如1 1+2 2+k k 的表達式，其中的表達式，其中i i為文字為文字。這樣。這樣的形式稱作的形式稱作“文字析取式（文字析取式（disjunctiondisjunction）”。子句的大小即為子句的大小即為其所含文字的其所含文字的總數(shù)總數(shù)。 子句和項式互為對偶（子句和項式互為對偶（dualdual）例：子句子句項式項式41653,xxxxx42171,xxxxx 若一個布爾函數(shù)可以寫成項式析取式則稱為若一個布爾函數(shù)可

10、以寫成項式析取式則稱為“析取范式析取范式”。任何布任何布爾函數(shù)都能寫成爾函數(shù)都能寫成析取范式析取范式。有。有k k個項式組成的個項式組成的DNFDNF析取式稱為析取式稱為“k k項項DNFDNF表達表達式式”；若其中最大的項式的大小為；若其中最大的項式的大小為k,k,它就屬于它就屬于k-DNFk-DNF這一類。這一類。析取范式（析取范式（disjunctive normal form,DNFdisjunctive normal form,DNF） 若一個布爾函數(shù)可以寫成子句合取式則稱為若一個布爾函數(shù)可以寫成子句合取式則稱為“合取范式合取范式”。任何任何布爾函數(shù)都能寫成布爾函數(shù)都能寫成合取范式合

11、取范式。有。有k k個子句組成的個子句組成的CNFCNF合取式稱為合取式稱為“k k項項CNFCNF表達式表達式”；若其中最大的子句的大小為；若其中最大的子句的大小為k,k,它就屬于它就屬于k-CNFk-CNF這一類。這一類。合取范式（合取范式（conjunctive normal form,CNFconjunctive normal form,CNF）析取范式析取范式有一個對偶：有一個對偶：合取范式合取范式)(43221xxxxxf例：例：43221xxxxxf3213231xxxxxxxf2.2 2.2 動作函數(shù)的表達和執(zhí)行動作函數(shù)的表達和執(zhí)行產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng) 產(chǎn)生式系統(tǒng)是動作函數(shù)的簡

12、單表達形式之一。一個產(chǎn)生式系產(chǎn)生式系統(tǒng)是動作函數(shù)的簡單表達形式之一。一個產(chǎn)生式系統(tǒng)包含一個有序規(guī)則序列，稱為統(tǒng)包含一個有序規(guī)則序列，稱為產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則( (production rule)production rule)或或產(chǎn)生式產(chǎn)生式( (productionproduction) )。每一規(guī)則寫作。每一規(guī)則寫作: : c ci i a ai i，其中其中c ci i是是條件部條件部分（分（condition partcondition part），而而a ai i是是動作部分動作部分( (action part)action part)。 一個產(chǎn)生式系統(tǒng)包含以下規(guī)則集：一個產(chǎn)生式系統(tǒng)

13、包含以下規(guī)則集： c c1 1 a a1 1 c c2 2 a a2 2 c ci i a ai i c cm m a am m 通常，通常，條件部分是一個單項式條件部分是一個單項式一個一個布爾合取布爾合取。為了選擇一個動。為了選擇一個動作，選擇規(guī)則如下：從第一個規(guī)則作，選擇規(guī)則如下：從第一個規(guī)則c cl l a al l開始，按順序?qū)ふ业谝粋€條開始，按順序?qū)ふ业谝粋€條件部分值為件部分值為1 1的規(guī)則，并選擇那個規(guī)則的動作部分。該動作部分可以一的規(guī)則，并選擇那個規(guī)則的動作部分。該動作部分可以一個簡單動作、對另一個產(chǎn)生式系統(tǒng)的調(diào)用或者是一個要同時執(zhí)行的動作個簡單動作、對另一個產(chǎn)生式系統(tǒng)的調(diào)用或者

14、是一個要同時執(zhí)行的動作集合。通常，序列中最后一條規(guī)則的條件部分的值為集合。通常，序列中最后一條規(guī)則的條件部分的值為1 1；若在此之前沒；若在此之前沒有其他條件部分的值為有其他條件部分的值為1 1的規(guī)則，則缺省地執(zhí)行最后一條規(guī)則中的動作。的規(guī)則，則缺省地執(zhí)行最后一條規(guī)則中的動作。 運用布爾代數(shù)以及先前為沿邊界行動的機器人而定義的特征文字，運用布爾代數(shù)以及先前為沿邊界行動的機器人而定義的特征文字，可以產(chǎn)生下面的沿邊界行動路線的產(chǎn)生式系統(tǒng)表示：可以產(chǎn)生下面的沿邊界行動路線的產(chǎn)生式系統(tǒng)表示：northxx14westxx43southxx32eastxx21north1 在目標實現(xiàn)的產(chǎn)生式系統(tǒng)中，處于

15、規(guī)則序列首位的規(guī)則在目標實現(xiàn)的產(chǎn)生式系統(tǒng)中，處于規(guī)則序列首位的規(guī)則c c1 1的條件部分的條件部分說明了我們要讓動作完成的總體目標。一旦達到這一目標，說明了我們要讓動作完成的總體目標。一旦達到這一目標， agentagent便停止便停止動作。動作。 當狀態(tài)不滿足當狀態(tài)不滿足c cl l而滿足而滿足c c2 2，通常選擇條件通常選擇條件c c2 2和動作和動作a a2 2，然后動作然后動作a a2 2的完的完成將最終達成成將最終達成c c1 1的目標。的目標。 以此類推，這種產(chǎn)生式系統(tǒng)形成了一個被稱作以此類推，這種產(chǎn)生式系統(tǒng)形成了一個被稱作teleo-reactive(T-R)teleo-rea

16、ctive(T-R)程程序的形式化基礎(chǔ)。在這個序的形式化基礎(chǔ)。在這個T-RT-R程序中，每正確完成規(guī)則序列中一條規(guī)則中的程序中，每正確完成規(guī)則序列中一條規(guī)則中的動作，就滿足了此規(guī)則中一個更高的條件。若給出為動作，就滿足了此規(guī)則中一個更高的條件。若給出為agentagent設(shè)置的總體目標設(shè)置的總體目標( (使用基于特征的條件說明使用基于特征的條件說明) )，書寫此特征的產(chǎn)生式系統(tǒng)將十分容易。，書寫此特征的產(chǎn)生式系統(tǒng)將十分容易。 T-R T-R程序也十分健全，動作一直朝著目標行進。只要感知精確度合理，程序也十分健全，動作一直朝著目標行進。只要感知精確度合理，由錯誤感知、不恰當?shù)膱?zhí)行動作或?qū)Νh(huán)境信息

17、處理的偏差所造成的偶而的由錯誤感知、不恰當?shù)膱?zhí)行動作或?qū)Νh(huán)境信息處理的偏差所造成的偶而的錯誤是可以得到修正的，而且動作通常能實現(xiàn)其設(shè)計效果。錯誤是可以得到修正的，而且動作通常能實現(xiàn)其設(shè)計效果。 除這些特征外，當除這些特征外，當T-RT-R程序被調(diào)用時，可以帶上參數(shù)，而且可以調(diào)用其程序被調(diào)用時，可以帶上參數(shù)，而且可以調(diào)用其他他T-RT-R程序，還能夠遞歸調(diào)用自己。程序，還能夠遞歸調(diào)用自己。網(wǎng)絡(luò)網(wǎng)絡(luò) 在邏輯電路中，布爾函數(shù)由邏輯門在邏輯電路中，布爾函數(shù)由邏輯門( (ANDAND， NAND NAND，OROR等等) )網(wǎng)絡(luò)系統(tǒng)實現(xiàn)。一種常用的電路包括閾值元件或其他網(wǎng)絡(luò)系統(tǒng)實現(xiàn)。一種常用的電路包括閾

18、值元件或其他能計算其輸入加權(quán)總和的非線性函數(shù)元件的網(wǎng)絡(luò)系統(tǒng)。能計算其輸入加權(quán)總和的非線性函數(shù)元件的網(wǎng)絡(luò)系統(tǒng)。閾值邏輯單元（閾值邏輯單元（threshold logic unit,TLUthreshold logic unit,TLU） 可由可由TLUTLU實現(xiàn)的布爾函數(shù)稱為線性可分函數(shù)（實現(xiàn)的布爾函數(shù)稱為線性可分函數(shù)（linearly linearly separable function)separable function)( (TLUTLU用一個線性平面用一個線性平面在在n n維空間維空間中稱為超平面中稱為超平面將產(chǎn)生高于閾值響應(yīng)的輸入向量空間與將產(chǎn)生高于閾值響應(yīng)的輸入向量空間與產(chǎn)生低于

19、閾值響應(yīng)的輸入向量空間分開產(chǎn)生低于閾值響應(yīng)的輸入向量空間分開) )。許多。許多( (但并非全但并非全部部) )布爾函數(shù)都是線性可分的。譬如，任一單項式（文字的布爾函數(shù)都是線性可分的。譬如，任一單項式（文字的合?。┗蛉我蛔泳洌ㄎ淖值奈鋈。┒际蔷€性可分的；兩個合取）或任一子句（文字的析?。┒际蔷€性可分的；兩個變量的變量的“異或異或”函數(shù)就是一個線性不可分的函數(shù)。函數(shù)就是一個線性不可分的函數(shù)。 在僅有兩種可能動作的應(yīng)用，若給出特征向量的代碼表在僅有兩種可能動作的應(yīng)用，若給出特征向量的代碼表示輸入，那么單一的示輸入，那么單一的TLUTLU便可算出正確的動作，而對更復雜便可算出正確的動作，而對更復雜的問題，則需要由這樣