第2章刺激响应agent

1、第一部分第一部分 响应机器响应机器2.1 2.1 感知和动作感知和动作刺激响应刺激响应( (Stimulus-Response,S-RStimulus-Response,S-R)agent)agent：不具备内部状态而仅对其所处环境的即刻刺激有所反应的机器不具备内部状态而仅对其所处环境的即刻刺激有所反应的机器. 先来看这样一个在二维先来看这样一个在二维网格空间世界里的机器人，网格空间世界里的机器人，如图所示。这一机器人的如图所示。这一机器人的世界有完整的边界线，可世界有完整的边界线，可能还包括如图所示的其他能还包括如图所示的其他庞大的固定物体。庞大的固定物体。 这一世界里没有这一世界里没有“稠

2、密稠密空间空间( (tight space)”(tight space)”(即即物体与边界线之间的距离物体与边界线之间的距离只有一个单元格只有一个单元格) )。 要求：这个机器人完要求：这个机器人完成以下动作：走到与一成以下动作：走到与一边界或物体毗邻的单元边界或物体毗邻的单元格中，然后沿着它的格中，然后沿着它的 边边界一直走下去。界一直走下去。 该机器人能够向与它同行或同列的毗邻的该机器人能够向与它同行或同列的毗邻的( (空缺空缺) )单单元格移动，共有如下四种动作：元格移动，共有如下四种动作： northnorth：机器人在网格中向上移动一个单元机器人在网格中向上移动一个单元 eastea

3、st： 机器人在网格中向右移动一个单元机器人在网格中向右移动一个单元 southsouth：机器人在网格中向下移动一个单元机器人在网格中向下移动一个单元 west west： 机器人在网格中向左移动一个单元机器人在网格中向左移动一个单元 给定了机器人适应的某种世界的特性给定了机器人适应的某种世界的特性( (如前图所示如前图所示) )、机器人完成的任务机器人完成的任务( (沿边界移动沿边界移动) )和机器人传感器和电机的和机器人传感器和电机的功能，设计者的工作就是说明为此任务选择适当动作的传功能，设计者的工作就是说明为此任务选择适当动作的传感器输入感器输入( (示例中表示为示例中表示为s1,s8

4、)s1,s8)的功能。的功能。 通常我们把从传感器信号中计算动作的过程分为两个分通常我们把从传感器信号中计算动作的过程分为两个分开的阶段，如下图所示。开的阶段，如下图所示。动作和知觉处理部分动作和知觉处理部分 知觉处理阶段产生一个特征向量知觉处理阶段产生一个特征向量X(xX(x1 1， x xi i, ,，x xn n) )。 动作计算阶段选择一个以特征向量为基础的动作：动作计算阶段选择一个以特征向量为基础的动作：各特征值既可以是真正的数字各特征值既可以是真正的数字( ( numeric feature, numeric feature,数字数字特征特征) )，也可以是范畴，也可以是范畴( (

5、 categorical featurecategorical feature，范畴特范畴特征征)()(范畴特征的值是名字或特性，譬如：特征值范畴特征的值是名字或特性，譬如：特征值“颜色颜色”可能是可能是“红红”、“蓝蓝”或或“绿绿”)”)。 二进制特征这一特殊例子既可视作数字二进制特征这一特殊例子既可视作数字(0(0，1)1)，也，也可视作范畴可视作范畴( (真，假真，假) )。设计者选择特征来将其与机器人。设计者选择特征来将其与机器人的环境特性相联系，而此环境特性又与由此特征描述的的环境特性相联系，而此环境特性又与由此特征描述的状态中机器应做的动作密切相关。状态中机器应做的动作密切相关。感

6、知感知对当前的任务，刚好有四个对计算适当动作有用的传感器的二进对当前的任务，刚好有四个对计算适当动作有用的传感器的二进制特征值，分别制特征值，分别 x1、x2、x3 和和 x4 来表示来表示在每个图中，当且仅当至少一个阴影单元为非空时，所在每个图中，当且仅当至少一个阴影单元为非空时，所示的特征值为示的特征值为1 1动作动作 首先，如果特征值都不是首先，如果特征值都不是1（即机器人感知到它周围的（即机器人感知到它周围的单元格全部空缺），则它可向任一方向移动直至遇到边界。单元格全部空缺），则它可向任一方向移动直至遇到边界。 我们先让它向北移动。若至少有一个特征值为我们先让它向北移动。若至少有一个特

7、征值为1 1，沿边界的，沿边界的行动则按以下规则完成：行动则按以下规则完成：若若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)移动；移动；布尔代数布尔代数与，或，非（补）与，或，非（补）“与与”，“或或”具有具有交换性同时具有结合性。交换性同时具有结合性。 由单个变量组成的布尔函数

8、，称为由单个变量组成的布尔函数，称为原子（原子（atom atom ）; ;由单由单个变量或其补组成的布尔函数，称为个变量或其补组成的布尔函数，称为文字（文字（literalliteral）。 布尔代数遵守布尔代数遵守 De.Morgan De.Morgan 定律。定律。 布尔函数有多种形式，其中一种重要的形式为：布尔函数有多种形式，其中一种重要的形式为：1 12 2 k k，这，这里里i i为文字为文字，这样书写的函数称为，这样书写的函数称为“文字合取式文字合取式 ( (conjunction)conjunction) ” 或或“单项式（单项式（monomialmonomial）”。这一合取

9、式本身称为一个这一合取式本身称为一个项式项式。项式的。项式的大小即为其所含文字的大小即为其所含文字的总数总数。布尔函数的类别和形式布尔函数的类别和形式 一个一个子句子句是形如是形如1 1+2 2+k k 的表达式，其中的表达式，其中i i为文字为文字。这样。这样的形式称作的形式称作“文字析取式（文字析取式（disjunctiondisjunction）”。子句的大小即为子句的大小即为其所含文字的其所含文字的总数总数。 子句和项式互为对偶（子句和项式互为对偶（dualdual）例：子句子句项式项式41653,xxxxx42171,xxxxx 若一个布尔函数可以写成项式析取式则称为若一个布尔函数可

10、以写成项式析取式则称为“析取范式析取范式”。任何布任何布尔函数都能写成尔函数都能写成析取范式析取范式。有。有k k个项式组成的个项式组成的DNFDNF析取式称为析取式称为“k k项项DNFDNF表达表达式式”；若其中最大的项式的大小为；若其中最大的项式的大小为k,k,它就属于它就属于k-DNFk-DNF这一类。这一类。析取范式（析取范式（disjunctive normal form,DNFdisjunctive normal form,DNF） 若一个布尔函数可以写成子句合取式则称为若一个布尔函数可以写成子句合取式则称为“合取范式合取范式”。任何任何布尔函数都能写成布尔函数都能写成合取范式合

11、取范式。有。有k k个子句组成的个子句组成的CNFCNF合取式称为合取式称为“k k项项CNFCNF表达式表达式”；若其中最大的子句的大小为；若其中最大的子句的大小为k,k,它就属于它就属于k-CNFk-CNF这一类。这一类。合取范式（合取范式（conjunctive normal form,CNFconjunctive normal form,CNF）析取范式析取范式有一个对偶：有一个对偶：合取范式合取范式)(43221xxxxxf例：例：43221xxxxxf3213231xxxxxxxf2.2 2.2 动作函数的表达和执行动作函数的表达和执行产生式系统产生式系统 产生式系统是动作函数的简

12、单表达形式之一。一个产生式系产生式系统是动作函数的简单表达形式之一。一个产生式系统包含一个有序规则序列，称为统包含一个有序规则序列，称为产生式规则产生式规则( (production rule)production rule)或或产生式产生式( (productionproduction) )。每一规则写作。每一规则写作: : c ci i a ai i，其中其中c ci i是是条件部条件部分（分（condition partcondition part），而而a ai i是是动作部分动作部分( (action part)action part)。 一个产生式系统包含以下规则集：一个产生式系统

13、包含以下规则集： c c1 1 a a1 1 c c2 2 a a2 2 c ci i a ai i c cm m a am m 通常，通常，条件部分是一个单项式条件部分是一个单项式一个一个布尔合取布尔合取。为了选择一个动。为了选择一个动作，选择规则如下：从第一个规则作，选择规则如下：从第一个规则c cl l a al l开始，按顺序寻找第一个条开始，按顺序寻找第一个条件部分值为件部分值为1 1的规则，并选择那个规则的动作部分。该动作部分可以一的规则，并选择那个规则的动作部分。该动作部分可以一个简单动作、对另一个产生式系统的调用或者是一个要同时执行的动作个简单动作、对另一个产生式系统的调用或者

14、是一个要同时执行的动作集合。通常，序列中最后一条规则的条件部分的值为集合。通常，序列中最后一条规则的条件部分的值为1 1；若在此之前没；若在此之前没有其他条件部分的值为有其他条件部分的值为1 1的规则，则缺省地执行最后一条规则中的动作。的规则，则缺省地执行最后一条规则中的动作。 运用布尔代数以及先前为沿边界行动的机器人而定义的特征文字，运用布尔代数以及先前为沿边界行动的机器人而定义的特征文字，可以产生下面的沿边界行动路线的产生式系统表示：可以产生下面的沿边界行动路线的产生式系统表示：northxx14westxx43southxx32eastxx21north1 在目标实现的产生式系统中，处于

15、规则序列首位的规则在目标实现的产生式系统中，处于规则序列首位的规则c c1 1的条件部分的条件部分说明了我们要让动作完成的总体目标。一旦达到这一目标，说明了我们要让动作完成的总体目标。一旦达到这一目标， agentagent便停止便停止动作。动作。 当状态不满足当状态不满足c cl l而满足而满足c c2 2，通常选择条件通常选择条件c c2 2和动作和动作a a2 2，然后动作然后动作a a2 2的完的完成将最终达成成将最终达成c c1 1的目标。的目标。 以此类推，这种产生式系统形成了一个被称作以此类推，这种产生式系统形成了一个被称作teleo-reactive(T-R)teleo-rea

16、ctive(T-R)程程序的形式化基础。在这个序的形式化基础。在这个T-RT-R程序中，每正确完成规则序列中一条规则中的程序中，每正确完成规则序列中一条规则中的动作，就满足了此规则中一个更高的条件。若给出为动作，就满足了此规则中一个更高的条件。若给出为agentagent设置的总体目标设置的总体目标( (使用基于特征的条件说明使用基于特征的条件说明) )，书写此特征的产生式系统将十分容易。，书写此特征的产生式系统将十分容易。 T-R T-R程序也十分健全，动作一直朝着目标行进。只要感知精确度合理，程序也十分健全，动作一直朝着目标行进。只要感知精确度合理，由错误感知、不恰当的执行动作或对环境信息

17、处理的偏差所造成的偶而的由错误感知、不恰当的执行动作或对环境信息处理的偏差所造成的偶而的错误是可以得到修正的，而且动作通常能实现其设计效果。错误是可以得到修正的，而且动作通常能实现其设计效果。 除这些特征外，当除这些特征外，当T-RT-R程序被调用时，可以带上参数，而且可以调用其程序被调用时，可以带上参数，而且可以调用其他他T-RT-R程序，还能够递归调用自己。程序，还能够递归调用自己。网络网络 在逻辑电路中，布尔函数由逻辑门在逻辑电路中，布尔函数由逻辑门( (ANDAND， NAND NAND，OROR等等) )网络系统实现。一种常用的电路包括阈值元件或其他网络系统实现。一种常用的电路包括阈

18、值元件或其他能计算其输入加权总和的非线性函数元件的网络系统。能计算其输入加权总和的非线性函数元件的网络系统。阈值逻辑单元（阈值逻辑单元（threshold logic unit,TLUthreshold logic unit,TLU） 可由可由TLUTLU实现的布尔函数称为线性可分函数（实现的布尔函数称为线性可分函数（linearly linearly separable function)separable function)( (TLUTLU用一个线性平面用一个线性平面在在n n维空间维空间中称为超平面中称为超平面将产生高于阈值响应的输入向量空间与将产生高于阈值响应的输入向量空间与产生低于

19、阈值响应的输入向量空间分开产生低于阈值响应的输入向量空间分开) )。许多。许多( (但并非全但并非全部部) )布尔函数都是线性可分的。譬如，任一单项式（文字的布尔函数都是线性可分的。譬如，任一单项式（文字的合取）或任一子句（文字的析取）都是线性可分的；两个合取）或任一子句（文字的析取）都是线性可分的；两个变量的变量的“异或异或”函数就是一个线性不可分的函数。函数就是一个线性不可分的函数。 在仅有两种可能动作的应用，若给出特征向量的代码表在仅有两种可能动作的应用，若给出特征向量的代码表示输入，那么单一的示输入，那么单一的TLUTLU便可算出正确的动作，而对更复杂便可算出正确的动作，而对更复杂的问题，则需要由这样