现代控制工程-第12章专家控制系统

1、1第12章 专家系统与专家控制o 12.0 专家系统的产生和发展专家系统的产生和发展o 12.1 专家系统专家系统 o 12.2 专家控制系统专家控制系统o 12.3 专家控制系统的知识表示专家控制系统的知识表示o 12.4 专家控制系统的推理机专家控制系统的推理机o 12.5 专家控制系统的搜索技术专家控制系统的搜索技术o 12.6 电脑充绒机专家控制系统电脑充绒机专家控制系统212.0 专家系统的产生和发展第一阶段第一阶段 : 初创期（初创期（20世纪世纪60年代中期年代中期 20世纪世纪70年代初）年代初） DENDRAL系统（系统（1968年，年，斯坦福大学斯坦福大学费根鲍姆等人）费根

2、鲍姆等人）推推 断化学分子结构的专家系统断化学分子结构的专家系统 MYCSYMA系统（系统（1971年，年，麻省理工学院麻省理工学院 ）用于数学运用于数学运 算的数学专家系统算的数学专家系统 特点：高度的专业化。特点：高度的专业化。 专门问题求解能力强。专门问题求解能力强。 结构、功能不完整。结构、功能不完整。 移植性差。移植性差。 缺乏解释功能。缺乏解释功能。312.0 专家系统的产生和发展第二阶段第二阶段: 成熟期成熟期（20世纪世纪70年代中年代中 20世纪世纪80年代初）年代初） MYCIN系统系统（斯坦福大学斯坦福大学 ）血液感染病诊断专家系血液感染病诊断专家系统统 PROSPECT

3、OR系统（系统（斯坦福研究所斯坦福研究所 ）探矿专家系统探矿专家系统 CASNET系统（拉特格尔大学）：用于青光眼诊断与治疗。系统（拉特格尔大学）：用于青光眼诊断与治疗。 AM系统（系统（ 1981年，斯坦福大学年，斯坦福大学）：模拟人类进行概括、：模拟人类进行概括、抽象和归纳推理，发现某些数论的概念和定理。抽象和归纳推理，发现某些数论的概念和定理。 HEARSAY系统系统（卡内基梅隆大学）（卡内基梅隆大学）语音识别专家语音识别专家系统系统412.0 专家系统的产生和发展第二阶段第二阶段: 成熟期成熟期（20世纪世纪70年代中期年代中期 20世纪世纪80年代初）年代初） 特点：特点： （1）单

4、学科专业型专家系统。）单学科专业型专家系统。（2）系统结构完整，功能较全面，移植性好。）系统结构完整，功能较全面，移植性好。（3）具有推理解释功能，透明性好。）具有推理解释功能，透明性好。（4）采用启发式推理、不精确推理。）采用启发式推理、不精确推理。（5）用产生式规则、框架、语义网络表达知识。）用产生式规则、框架、语义网络表达知识。（6）用限定性英语进行人机交互。）用限定性英语进行人机交互。512.0 专家系统的产生和发展第三阶段：发展期第三阶段：发展期（20世纪世纪80年代至今）年代至今） 专家系统专家系统XCON（DEC公司、卡内基梅隆大公司、卡内基梅隆大学学 ）：为：为VAX计算机系统

5、制订硬件配置方案。计算机系统制订硬件配置方案。 专家系统开发工具：专家系统开发工具：l骨架系统：骨架系统：EMYCIN、KAS、EXPERT 等。等。l通用型知识表达语言：通用型知识表达语言： OPS5 等。等。l专家系统开发环境：专家系统开发环境： AGE 等。等。612.0 专家系统的产生和发展第三阶段：发展期第三阶段：发展期（20世纪世纪80年代至今）年代至今） 我国研制开发的专家系统：我国研制开发的专家系统：l施肥专家系统（中国科学院合肥智能机械研究所）施肥专家系统（中国科学院合肥智能机械研究所）l新构造找水专家系统（南京大学）新构造找水专家系统（南京大学）l勘探专家系统及油气资源评价

6、专家系统（吉林大学）勘探专家系统及油气资源评价专家系统（吉林大学）l服装剪裁专家系统及花布图案设计专家系统（浙江服装剪裁专家系统及花布图案设计专家系统（浙江大学）大学）l关幼波肝病诊断专家系统（北京中医学院）关幼波肝病诊断专家系统（北京中医学院）712.1.1 专家系统的概念专家系统的概念12.1.2 专家系统的一般结构专家系统的一般结构12.1.3 实时专家系统实时专家系统12.1 专家系统专家系统812.1.1 专家系统的概念 1. 定义定义 费根鲍姆（费根鲍姆（E. A. Feigenbaum）：）： “专家系统是一种专家系统是一种智能的计算机程序智能的计算机程序，它运用，它运用知识知识

7、和和推理推理来解决只有专家才能解决的复杂问题。来解决只有专家才能解决的复杂问题。” 专家系统：一类包含知识和推理的智能计算机程专家系统：一类包含知识和推理的智能计算机程序序 。912.1.1 专家系统的概念 2. 专家系统的基本组成专家系统的基本组成 推 理 机数 据 库规 则 库专 家系 统 用 户知 识 获 取推 理 咨 询解 释 程 序调 度 程 序知 识 库10专家系统的特点专家系统的特点（1）具有专家水平的专业知识。）具有专家水平的专业知识。（2）能进行有效的推理。）能进行有效的推理。 （3）启发性。）启发性。（4）灵活性。）灵活性。（5）透明性。）透明性。（6）交互性。）交互性。一

8、个计算机程序系统的透明性：系统自身及其行一个计算机程序系统的透明性：系统自身及其行为能被用户所理解。为能被用户所理解。 12.1.1 专家系统的概念11o 专家系统与传统程序的比较专家系统与传统程序的比较（1）编程思想）编程思想： 传统程序传统程序 = 数据结构数据结构+算法算法专家系统专家系统 = 知识知识+推理推理（2）传统程序：关于问题求解的知识隐含于程序中。）传统程序：关于问题求解的知识隐含于程序中。 专家系统：知识单独组成知识库，与推理机分离。专家系统：知识单独组成知识库，与推理机分离。 （3）处理对象）处理对象： 传统程序：数值计算和数据处理。传统程序：数值计算和数据处理。 专家系

9、统：符号处理。专家系统：符号处理。 12.1.1 专家系统的概念12o 专家系统与传统程序的比较专家系统与传统程序的比较（4）传统程序：不具有解释功能。）传统程序：不具有解释功能。 专家系统：具有解释功能。专家系统：具有解释功能。（5）传统程序：产生正确的答案。）传统程序：产生正确的答案。 专家系统：通常产生正确的答案，有时产生错误的专家系统：通常产生正确的答案，有时产生错误的答案。答案。 （6）系统的体系结构不同。）系统的体系结构不同。12.1.1 专家系统的概念13专家系统的类型14专家系统的应用15专家系统的应用1612.1.2 专家系统的一般结构人机接口用户领域专家知识工程师解释机构知

10、识获取机构数据库推理机知识库专家系统核心 专家系统的一般结构专家系统的一般结构人机接口解释机构知识获取机构数据库推理机知识库专家系统核心1712.1.3 实时专家系统o 实时专家系统是具有实时性的专家系统。它一方面实时专家系统是具有实时性的专家系统。它一方面要满足专家系统功能的要求，另一方面还必须受时要满足专家系统功能的要求，另一方面还必须受时间条件的约束，即满足实时性要求。间条件的约束，即满足实时性要求。 o 实时专家系统的特点：实时专家系统的特点：o (1) 操作方式：实时专家系统的信息输入主要来自操作方式：实时专家系统的信息输入主要来自外界过程的传感器，且往往从多个独立的传感器输外界过程

11、的传感器，且往往从多个独立的传感器输入。入。 o (2) 输出去向：实时专家系统直接送往过程的控制输出去向：实时专家系统直接送往过程的控制器或（和）向生产人员送出诊断、预报、操作指导器或（和）向生产人员送出诊断、预报、操作指导等信息。等信息。 1812.1.3 实时专家系统o (3) 数据特征：实时专家系统数据是连续时变的，数据特征：实时专家系统数据是连续时变的，是实时数据，信息量往往很大。是实时数据，信息量往往很大。o (4) 中断功能：实时专家系统一方面要满足专家系中断功能：实时专家系统一方面要满足专家系统功能的要求，另一方面还必须受时间条件的约束，统功能的要求，另一方面还必须受时间条件的

12、约束，即满足实时性的要求。即满足实时性的要求。 o (5) 实时性：实时专家系统响应要求快，常常为毫实时性：实时专家系统响应要求快，常常为毫秒、秒级。实时性的要求是实时专家系统首先必须秒、秒级。实时性的要求是实时专家系统首先必须考虑的。考虑的。o (6) 推理过程：实时专家系统采用实时推理。推理过程：实时专家系统采用实时推理。1912.2 专家控制系统o 12.2.1 专家控制系统的概念专家控制系统的概念o 12.2.2 间接专家控制间接专家控制o 12.2.3 直接专家控制直接专家控制o 12.2.4 专家控制器专家控制器2012.2.1 专家控制系统的概念o 从专家系统的角度来说，专家控制

13、是专家系统的一从专家系统的角度来说，专家控制是专家系统的一个重要分支，属于实时专家系统研究领域；个重要分支，属于实时专家系统研究领域；o 从自动控制的角度来说，专家控制是智能控制的一从自动控制的角度来说，专家控制是智能控制的一个重要分支，是将专家系统的思想和方法引入控制个重要分支，是将专家系统的思想和方法引入控制系统，从而形成一种新的控制方法。系统，从而形成一种新的控制方法。o 许多生产过程具有强烈的非线性、时变性及不确定许多生产过程具有强烈的非线性、时变性及不确定性，专家控制模拟人类推理能力，把生产操作人员、性，专家控制模拟人类推理能力，把生产操作人员、工程师的经验与控制算法结合起来，即把符

14、号推理工程师的经验与控制算法结合起来，即把符号推理与数值运算结合起来，为过程控制提供了一种新的与数值运算结合起来，为过程控制提供了一种新的控制方法。控制方法。2112.2.2 间接专家控制o 间接专家控制也称为专家监督控制。其中，常规控间接专家控制也称为专家监督控制。其中，常规控制器控制过程运行。专家系统只是通过对常规控制制器控制过程运行。专家系统只是通过对常规控制器的调整，间接地影响被控过程。器的调整，间接地影响被控过程。 设定输出专家系统控制器控制对象2212.2.3 直接专家控制o 在直接专家控制系统中，专家系统根据所测到的过在直接专家控制系统中，专家系统根据所测到的过程信息及知识库中的

15、规则，导出每一采样时刻的控程信息及知识库中的规则，导出每一采样时刻的控制信号。制信号。 设定输出专家系统控制对象2312.2.4 专家控制器o 对简单控制对象，可以简化成如图所示结构，通常对简单控制对象，可以简化成如图所示结构，通常将简单的专家控制系统称为专家控制器。将简单的专家控制系统称为专家控制器。 学习与适应装置 LA数据库 DB特征识别信息处理 FR&IP推理机 IE 控制规则集 CRS控制对象传感器EeuRSIUY被控制量专家控制器KG知识库 KBEC2412.3 专家控制系统的知识表示o 12.3.1 知识表示知识表示o 12.3.2 产生式产生式知识表示知识表示o 12.

16、3.3 产生式系统产生式系统o 12.3.4 产生式系统的例子产生式系统的例子动物识别系统动物识别系统o 12.3.5 产生式表示法的特点产生式表示法的特点2512.3.1 知识表示知识表示o 专家系统是建立在知识的基础之上的，专家控制是专家系统是建立在知识的基础之上的，专家控制是基于知识的控制。基于知识的控制。o 知识表示是将人类知识形式化或者模型化。知识表示是将人类知识形式化或者模型化。o 目前已经提出了许多知识表示方法，例如一阶谓词目前已经提出了许多知识表示方法，例如一阶谓词逻辑、产生式、框架、状态空间、人工神经网络、逻辑、产生式、框架、状态空间、人工神经网络、遗传编码等。遗传编码等。o

17、 在专家控制系统中，特别是在专家控制器中，产生在专家控制系统中，特别是在专家控制器中，产生式表示法用得十分广泛。式表示法用得十分广泛。 26o “产生式产生式”：1943年，美国数学家波斯特（年，美国数学家波斯特（E. Post）首先提出。）首先提出。 o 1972年，纽厄尔和西蒙在研究人类的认知模型年，纽厄尔和西蒙在研究人类的认知模型中开发了基于规则的产生式系统。中开发了基于规则的产生式系统。o 产生式通常用于表示事实、规则以及它们的不产生式通常用于表示事实、规则以及它们的不确定性度量，适合于表示事实性知识和规则性确定性度量，适合于表示事实性知识和规则性知识。知识。12.3.2 产生式知识表

18、示271. 确定性规则知识的产生式表示确定性规则知识的产生式表示2. 不确定性规则知识的产生式表示不确定性规则知识的产生式表示 基本形式：基本形式： IF P THEN Q 或者：或者： 例如：例如： r4：IF 动物会飞动物会飞 AND 会下蛋会下蛋 THEN 该动物是鸟该动物是鸟QP 基本形式：基本形式： IF P THEN Q （置信度）（置信度） 或者：或者： （置信度（置信度） 例如：例如： IF 发烧发烧 THEN 感冒感冒 （0.6）QP 12.3.2 产生式知识表示283. 确定性事实性知识的产生式表示确定性事实性知识的产生式表示4. 不确定性事实性知识的产生式表示不确定性事实

19、性知识的产生式表示 三元组表示：（对象，属性，值）三元组表示：（对象，属性，值） 或者：（关系，对象或者：（关系，对象1，对象，对象2） 例：例： 老李年龄是老李年龄是40岁：岁： （Li，age，40） 老李和老王是朋友：（老李和老王是朋友：（friend，Li，Wang） 四元组表示：（对象，属性，值，置信度）四元组表示：（对象，属性，值，置信度） 或者：或者： （关系，对象（关系，对象1，对象，对象2，置信度），置信度）例：老李年龄很可能是例：老李年龄很可能是40岁：岁：（Li，age，40，0.8） 老李和老王不大可能是朋友：（老李和老王不大可能是朋友：（friend，Li，Wang，

20、0.1）12.3.2 产生式知识表示29o 产生式与谓词逻辑中的蕴含式的区别：产生式与谓词逻辑中的蕴含式的区别：（1）除逻辑蕴含外，产生式还包括各种操作、规则、）除逻辑蕴含外，产生式还包括各种操作、规则、变换、算子、函数等。例如，变换、算子、函数等。例如，“如果炉温超过上限，如果炉温超过上限，则立即关闭风门则立即关闭风门”是产生式，但不是蕴含式。是产生式，但不是蕴含式。（2）蕴含式只能表示精确知识，而产生式不仅可以表）蕴含式只能表示精确知识，而产生式不仅可以表示精确的知识，还可以表示不精确知识。蕴含式的示精确的知识，还可以表示不精确知识。蕴含式的匹配总要求是精确的。产生式匹配可以是精确的，匹配

21、总要求是精确的。产生式匹配可以是精确的，也可以是不精确的，只要按某种算法求出的相似度也可以是不精确的，只要按某种算法求出的相似度落在预先指定的范围内就认为是可匹配的。落在预先指定的范围内就认为是可匹配的。12.3.2 产生式知识表示30o 产生式的形式描述及语义产生式的形式描述及语义巴科斯范式巴科斯范式BNF（backus normal form） := :=|:=|:=ANDAND |OROR:=(，)符号符号“:=”表示表示“定义为定义为”；符号；符号“|”|”表示表示“或或者是者是”；符号；符号“ ” ”表示表示“可缺省可缺省”。 12.3.2 产生式知识表示3112.3.3 产生式系统

22、产生式系统控 制规则库推理机综合数据库产生式系统的基本结构3212.3.3 产生式系统产生式系统1. 规则库规则库2. 综合数据库综合数据库 规则库规则库: : 用于描述相应领域内知识的产生式集合。 综合数据库综合数据库(事实库、上下文、黑板等)：一个用于存放问题求解过程中各种当前信息的数据结构。 3推理机推理机 由一组程序组成，负责整个产生式系统的运行，实现对问题的求解。 3312.3.3 产生式系统产生式系统4控制系统控制系统 控制系统要做以下几项工作： （1）从规则库中选择与综合数据库中的已知事实进行匹配。 （2）匹配成功的规则可能不止一条，进行冲突消解。（ 3）执行某一规则时，如果其右

23、部是一个或多个结论，则把这些结论加入到综合数据库中：如果其右部是一个或多个操作，则执行这些操作。 （ 4）对于不确定性知识，在执行每一条规则时还要按一定的算法计算结论的不确定性。（ 5）检查综合数据库中是否包含了最终结论，决定是否停止系统的运行。 3412.3.4 产生式系统的例子动物识别系统例如：例如：动物识别系统动物识别系统识别识别虎、金钱豹、斑马、长颈虎、金钱豹、斑马、长颈鹿、鸵鸟、企鹅、信天翁鹿、鸵鸟、企鹅、信天翁等七种动物的产生式系统。等七种动物的产生式系统。3512.3.4 产生式系统的例子产生式系统的例子动物识别系统动物识别系统o 规则库：规则库：r1： IF 该动物有毛发该动物

24、有毛发 THEN 该动物是哺乳动物该动物是哺乳动物r2： IF 该动物有奶该动物有奶 THEN 该动物是哺乳动物该动物是哺乳动物r3： IF 该动物有羽毛该动物有羽毛 THEN 该动物是鸟该动物是鸟r4： IF 该动物会飞该动物会飞 AND 会下蛋会下蛋 THEN 该动物是鸟该动物是鸟r5： IF 该动物吃肉该动物吃肉 THEN 该动物是食肉动物该动物是食肉动物r6： IF 该动物有犬齿该动物有犬齿 AND 有爪有爪 AND 眼盯前方眼盯前方 THEN 该动物是食肉动物该动物是食肉动物r7： IF 该动物是哺乳动物该动物是哺乳动物 AND 有蹄有蹄 THEN 该动物是有蹄类动物该动物是有蹄类动

25、物r 8： IF 该动物是哺乳动物该动物是哺乳动物 AND 是反刍动物是反刍动物 THEN 该动物是有蹄类动物该动物是有蹄类动物3612.3.4 产生式系统的例子产生式系统的例子动物识别系统动物识别系统r9： IF 该动物是哺乳动物该动物是哺乳动物 AND 是食肉动物是食肉动物 AND 是黄褐色是黄褐色 AND 身上有暗斑点身上有暗斑点 THEN 该动物是金钱豹该动物是金钱豹 r10：IF 该动物是哺乳动物该动物是哺乳动物 AND 是食肉动物是食肉动物 AND 是黄褐色是黄褐色 AND 身上有黑色条纹身上有黑色条纹 THEN 该动物是虎该动物是虎 r11： IF 该动物是有蹄类动物该动物是有蹄

26、类动物 AND 有长脖子有长脖子 AND 有长腿有长腿 AND 身上有暗斑点身上有暗斑点 THEN 该动物是长颈鹿该动物是长颈鹿 r 12：IF 该动物有蹄类动物该动物有蹄类动物 AND 身上有黑色条纹身上有黑色条纹 THEN 该动物是斑马该动物是斑马r13：IF 该动物是鸟该动物是鸟 AND 有长脖子有长脖子 AND 有长腿有长腿 AND 不会飞不会飞 AND 有黑白二色有黑白二色 THEN 该动物是鸵鸟该动物是鸵鸟r14： IF 该动物是鸟该动物是鸟 AND 会游泳会游泳 AND 不会飞不会飞 AND 有黑白二色有黑白二色 THEN 该动物是企鹅该动物是企鹅 r15： IF 该动物是鸟该动

27、物是鸟 AND 善飞善飞 THEN 该动物是信天翁该动物是信天翁3712.3.4 产生式系统的例子产生式系统的例子动物识别系统动物识别系统o 设已知初始事实存放在综合数据库综合数据库中： 该动物身上有：暗斑点，长脖子，长腿，奶，蹄该动物身上有：暗斑点，长脖子，长腿，奶，蹄o 推理过程推理过程 ：（1）从规则库中取出r1，检查其前提是否可与综合数据库中的已知事实匹配。匹配失败则r1不能被用于推理。然后取r2进行同样的工作。匹配成功则r2被执行。 综合数据库综合数据库 ： 该动物身上有：暗斑点，长脖子，长腿，奶，蹄，哺该动物身上有：暗斑点，长脖子，长腿，奶，蹄，哺乳动物乳动物 3812.3.4 产

28、生式系统的例子产生式系统的例子动物识别系统动物识别系统（2）分别用r3，r4，r5，r6综合数据库中的已知事实进行匹配，均不成功。 r7匹配成功，执行r7 。 综合数据库：综合数据库： 该动物身上有：暗斑点，长脖子，长腿，奶，蹄，哺该动物身上有：暗斑点，长脖子，长腿，奶，蹄，哺乳动物，有蹄类动物乳动物，有蹄类动物（3）r11匹配成功，并推出 “该动物是长颈鹿” 。 推理机构的工作过程推理机构的工作过程 ：3912.3.5 产生式表示法的特点产生式表示法的特点1. 产生式表示法的优点产生式表示法的优点（1）自然性）自然性 （2）模块性）模块性 （3）有效性）有效性 （4）清晰性）清晰性 2. 产

29、生式表示法的缺点产生式表示法的缺点（1）效率不高）效率不高 （2）不能表达结构性知识）不能表达结构性知识 3. 适合产生式适合产生式表示的知识表示的知识（1）领域知识间关系不密切，）领域知识间关系不密切，不存在结构关系。不存在结构关系。（2）经验性及不确定性的知识，）经验性及不确定性的知识，且相关领域中对这些知识没有且相关领域中对这些知识没有严格、统一的理论。严格、统一的理论。（3）领域问题的求解过程可被）领域问题的求解过程可被表示为一系列相对独立的操作，表示为一系列相对独立的操作，且每个操作且每个操作可被表示为一条或可被表示为一条或多条产生式规则。多条产生式规则。4012.4 专家控制系统的

30、推理机专家控制系统的推理机o 12.4.1 推理的基本概念推理的基本概念o 12.4.2 推理方式及其分类推理方式及其分类o 12.4.3 推理的方向推理的方向o 12.4.4 冲突消解策略冲突消解策略41知识智能?经典逻辑推理（确定性推理）不确定性推理自然演绎推理归结演绎推理与/或形演绎推理推理推理知识智能 !12.4.1 推理的基本概念推理的基本概念从初始证据出发，按某种策从初始证据出发，按某种策略不断运用知识库中的已知略不断运用知识库中的已知知识，逐步推出结论的过程知识，逐步推出结论的过程称为推理。称为推理。42（1）演绎推理演绎推理 (deductive reasoning) : 一般

31、一般 个别个别 三段论式三段论式（三段论法）（三段论法） 足球运动员的身体都是强壮的足球运动员的身体都是强壮的 ； 高波是一名足球运动员；高波是一名足球运动员； 所以，高波的身体是强壮的。所以，高波的身体是强壮的。12.4.2 推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（ 大前提大前提 ）（ 小前提小前提 ）（ 结结 论论 ）4312.4.2 推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（2）归纳推理归纳推理 (inductive reasoning): 个别个别 一般一般 完全归纳推理（完全归纳推理（必然性推理）必然性推理

32、） 不完全归纳推理不完全归纳推理（非必然性推理）（非必然性推理）检查全部产品合格检查全部产品合格该厂产品合格该厂产品合格完全归纳推理完全归纳推理检查全部样品合格检查全部样品合格该厂产品合格该厂产品合格不完全归纳推理不完全归纳推理4412.4.2 推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（3）默认推理默认推理（default reasoning，缺省推理），缺省推理）n 知识不完全的情况下假设某些条件已经具备所进行的推理知识不完全的情况下假设某些条件已经具备所进行的推理。 结结 论论 A 成立成立 B 成立？成立？（默认（默认B成立）成立）鸟笼要鸟笼要有盖子

33、有盖子 制造鸟笼制造鸟笼 鸟会飞？鸟会飞？（默认成立）（默认成立）4512.4.2 推理方式及其分类 2. 确定性推理、不确定性推理确定性推理、不确定性推理似然推理近似推理或模糊推理不确定性推理（概率论）（模糊逻辑）（1）确定性推理确定性推理：推理时所用的知识与证据都是确定的，：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。推出的结论也是确定的，其真值或者为真或者为假。 （2）不确定性不确定性推理推理：推理时所用的知识与证据不都是确定：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。的，推出的结论也是不确定的。46X：鸟：鸟 X：会飞：会飞 X:

34、企鹅企鹅 12.4.2 推理方式及其分类 3. 单调推理、非单调推理单调推理、非单调推理 （1）单调推理单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。 （2）非单调推理非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。 默认推理是非单调推理默认推理是非单调推理 基于经典逻辑的演绎推理基于经典逻辑的演绎推理 X：不会飞不会飞X：企鹅：企鹅4712.4.2 推理方式及其分类4启发式推理、非启发式推理启发式推理、非启发式推理 启发性知识启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。 目标：在脑膜炎、肺炎、

35、流感中选择一个目标：在脑膜炎、肺炎、流感中选择一个 产生式规则产生式规则 r1：脑膜炎：脑膜炎 r2：肺：肺 炎炎 r3：流：流 感感 启发式知识：启发式知识：“脑膜炎危险脑膜炎危险”、“目前正在盛行流目前正在盛行流感感”。4812.4.3 推理的方向正向推理逆向推理(反向推理)双向推理混合推理推理方向推理机数据库知识库专家用户4912.4.3 推理的方向n 正向推理（事实驱动推理）正向推理（事实驱动推理）: 已知事实已知事实 结论结论 基本思想基本思想（1）从初始已知事实出发，在知识库）从初始已知事实出发，在知识库KB中找出当前可适中找出当前可适用的知识，构成可适用知识集用的知识，构成可适用

36、知识集KS。（2）按某种冲突消解策略从）按某种冲突消解策略从KS中选出一条知识进行推理，中选出一条知识进行推理，并将推出的新事实加入到数据库并将推出的新事实加入到数据库DB中作为下一步推理的中作为下一步推理的已知事实，再在已知事实，再在KB中选取可适用知识构成中选取可适用知识构成KS 。（3）重复（）重复（2），直到求得问题的解或），直到求得问题的解或KB中再无可适用中再无可适用的知识。的知识。1. 正向推理正向推理5012.4.3 推理的方向n 实现正向推理需要解决的问题：实现正向推理需要解决的问题：l 确定匹配（知识与已知事实）的方法。确定匹配（知识与已知事实）的方法。l 按什么策略搜索知

37、识库。按什么策略搜索知识库。l 冲突消解策略。冲突消解策略。 正向推理简单，易实现，但目的性不强，效率低。正向推理简单，易实现，但目的性不强，效率低。1. 正向推理正向推理5112.4.3 推理的方向n 逆向推理（目标驱动推理）：以逆向推理（目标驱动推理）：以某个假设目标某个假设目标作为出发点。作为出发点。 基本思想：基本思想： 选定一个假设目标。选定一个假设目标。 寻找支持该假设的证据，若所需的证据都能找到，则原假寻找支持该假设的证据，若所需的证据都能找到，则原假设成立；若无论如何都找不到所需要的证据，说明原假设不设成立；若无论如何都找不到所需要的证据，说明原假设不成立的；为此需要另作新的假

38、设。成立的；为此需要另作新的假设。 主要优点：不必使用与目标无关的知识，目的性强，同时主要优点：不必使用与目标无关的知识，目的性强，同时它还有利于向用户提供解释。它还有利于向用户提供解释。 主要缺点：起始目标的选择有盲目性。主要缺点：起始目标的选择有盲目性。2. 逆向推理逆向推理5212.4.3 推理的方向n 逆向推理需要解决的问题：逆向推理需要解决的问题：u 如何判断一个假设是否是证据？如何判断一个假设是否是证据？u 当导出假设的知识有多条时，如何确定先选哪一条？当导出假设的知识有多条时，如何确定先选哪一条？ u一条知识的运用条件一般都有多个，当其中的一个经一条知识的运用条件一般都有多个，当

39、其中的一个经验证成立后，如何自动地换为对另一个的验证？验证成立后，如何自动地换为对另一个的验证？u . 逆向推理：目的性强，利于向用户提供解释，但选择初始逆向推理：目的性强，利于向用户提供解释，但选择初始目标时具有盲目性，比正向推理复杂。目标时具有盲目性，比正向推理复杂。2. 逆向推理逆向推理5312.4.3 推理的方向n 正向推理正向推理: 盲目、效率低。盲目、效率低。 逆向推理逆向推理: 若提出的假设目标不符合实际，会降低效率。若提出的假设目标不符合实际，会降低效率。 正反向混合推理：正反向混合推理：（1）先正向后逆向：先正向后逆向：先进行正向推理，帮助选择某个目标，即先进行正向推理，帮助

40、选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；提高其可信度；（2）先逆向后正向：先逆向后正向：先假设一个目标进行逆向推理，然后再利先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。用逆向推理中得到的信息进行正向推理，以推出更多的结论。3. 混合推理混合推理5412.4.4 冲突消解策略 已知事实与知识的三种匹配情况已知事实与知识的三种匹配情况：（1）恰好匹配成功（一对一）；）恰好匹配成功（一对一）；（2）不能匹配成功；）不能匹配成功；（3）多种匹配成功多种匹配成功

41、（一对多、多对一、多对多）（一对多、多对一、多对多）冲突消解冲突消解5512.4.4 冲突消解策略 多种冲突消解策略：多种冲突消解策略：（1）按针对性排序）按针对性排序（2）按已知事实的新鲜性排序）按已知事实的新鲜性排序（3）按匹配度排序）按匹配度排序（4）按条件个数排序）按条件个数排序（5）按上下文限制排序）按上下文限制排序（6）按冗余限制排序）按冗余限制排序（7）根据领域问题的特点排序）根据领域问题的特点排序r1: IF A1 AND A2 THEN H1r2: IF A1 AND A2 AND A3 AND A4 THEN H25612.5 专家控制系统的搜索技术专家控制系统的搜索技术o

42、 12.5.0 搜索的基本问题与主要过程搜索的基本问题与主要过程o 12.5.1 状态空间知识表示方法状态空间知识表示方法o 12.5.2 状态空间的图描述状态空间的图描述o 12.5.3 回溯策略回溯策略o 12.5.4 宽度优先搜索策略宽度优先搜索策略5712.5.0 搜索的基本问题与主要过程o 在求解一个问题时，涉及到两个方面：在求解一个问题时，涉及到两个方面： 一个是该问题的表示。如果一个问题找不到一个合适的表一个是该问题的表示。如果一个问题找不到一个合适的表示方法，就谈不上对它求解。示方法，就谈不上对它求解。 另一个是选择一种相对合适的求解方法。在人工智能中，另一个是选择一种相对合适

43、的求解方法。在人工智能中，问题求解的基本方法有搜索法、归约法、归结法、推理法及问题求解的基本方法有搜索法、归约法、归结法、推理法及产生式等。产生式等。o 由于绝大多数需要人工智能方法求解的问题缺乏数学求解的由于绝大多数需要人工智能方法求解的问题缺乏数学求解的方法，因此，搜索不失为一种求解问题的一般方法，应用非方法，因此，搜索不失为一种求解问题的一般方法，应用非常广泛。常广泛。o 一个搜索算法的策略就是要决定树或图中状态的搜索次序。一个搜索算法的策略就是要决定树或图中状态的搜索次序。宽度、深度优先搜索是状态空间的最基本的搜索策略。宽度、深度优先搜索是状态空间的最基本的搜索策略。5812.5.0

44、搜索的基本问题与主要过程 o搜索中需要解决的基本问题：搜索中需要解决的基本问题：（1）是否一定能找到一个解。）是否一定能找到一个解。（2）是否终止运行或是否会陷入一个死循环。）是否终止运行或是否会陷入一个死循环。（3）找到的解是否是最佳解。）找到的解是否是最佳解。（4）时间与空间复杂性如何。）时间与空间复杂性如何。5912.5.0 搜索的基本问题与主要过程o 搜索的主要过程：搜索的主要过程：(1) 从初始或目的状态出发，并将它作为当前状态。从初始或目的状态出发，并将它作为当前状态。(2) 扫描操作算子集，将适用当前状态的一些操作算子扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得

45、到新的状态，并建立指向其父作用于当前状态而得到新的状态，并建立指向其父结点的指针结点的指针 。(3) 检查所生成的新状态是否满足结束状态，如果满足，检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第新状态作为当前状态，返回第(2)步再进行搜索。步再进行搜索。 6012.5.0 搜索策略o 1. 搜索方向：搜索方向： (1) 数据驱动数据驱动：从初始状态出发的正向搜索。：从初始状态出发的正向搜索。 正

46、向搜索正向搜索从问题给出的条件出发。从问题给出的条件出发。逆向搜索逆向搜索：从想达到的目的入手，看哪些操作算子能产生：从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。该目的以及应用这些操作算子产生目的时需要哪些条件。 (2) 目的驱动目的驱动：从目的：从目的状态出发的逆向搜索。状态出发的逆向搜索。双向搜索：从开始状态出发作正向搜索，同时又从目的状双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。态出发作逆向搜索，直到两条路径在中间的某处汇合为止。(3) 双向搜索双向搜索6112.5.0 搜索策略o 2

47、. 盲目搜索与启发式搜索盲目搜索与启发式搜索:（1）盲目搜索）盲目搜索：在不具有对特定问题的任何有关信：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。作算子）进行的搜索。 （2）启发式搜索）启发式搜索：考虑特定问题领域可应用的知识，：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束快地到达结束状态。状态。6212.5.1 状态空间表示法o 状态：表

48、示系统状态、事实等叙述型知识的一组变状态：表示系统状态、事实等叙述型知识的一组变量或数组：量或数组：,21nqqqQ,21mfffF 操作：表示引起状态变化的过程型知识的一组关操作：表示引起状态变化的过程型知识的一组关 系或函数：系或函数：T6312.5.1 状态空间表示法o 状态空间：利用状态变量和操作符号，表示系统或状态空间：利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元问题的有关知识的符号体系，状态空间是一个四元组：组： ),(0GSOS ：状态集合。：状态集合。 ：操作算子的集合。：操作算子的集合。 ：包含问题的初始状态是：包含问题的初始状态是 的非空子

49、集。的非空子集。 ：若干具体状态或满足某些性质的路径信息描述。：若干具体状态或满足某些性质的路径信息描述。O0SGSS6412.5.1 状态空间表示法o 求解路径求解路径：从 结点到 结点的路径。 0SGGSSSkOOOO321210kOO,1：状态空间的一个解。 状态空间的一个解状态空间的一个解：一个有限的操作算子序列。65o 例例1 八数码问题的状态空间八数码问题的状态空间。 12.5.1 状态空间表示法状态集 ：所有摆法S操作算子：将空格向上移Up将空格向左移Left将空格向下移Down将空格向右移Right6612.5.2 状态空间的图描述八数码八数码状态空间图状态空间图 6712.5

50、.2 状态空间的图描述（状态）（操作算子）状态空间的有向图描述状态空间的有向图描述68 例例2 旅行商问题旅行商问题（traveling salesman problem, TSP）或邮递员路径问题。或邮递员路径问题。 12.5.2 状态空间的图描述（家）（单位：km）可能路径：费用为375的路径（A，B，C，D，E，A） 6912.5.2 状态空间的图描述 旅行推销员状态空间图（部分） ABCDEA 375 A A A A B B C C C C D D D D A E E E E E E E D 路径: 路径: 路径 : 路径: ABCEDA ABDCE ABDECA 费用 : 费用 :

51、费用 : 费用: 425 525 475 525 475 375 325 400 400 300 275 275 250 225 150 100 75 125 175 225 250 100 175 225 425 . . . . . . . 7012.5.3 回溯策略o 带回溯策略的搜索：带回溯策略的搜索： 从初始状态出发，不停地、试探性地寻找路径，从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或直到它到达目的或“不可解结点不可解结点”，即，即“死胡同死胡同”为止。为止。 若它遇到不可解结点就回溯到路径中最近的父结若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其

52、他的子结点未被扩展。点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。就成功退出搜索，返回解题路径。7112.5.3 回溯策略1 AB 2E 3J 57 K9 G6 F10 H11 D8 C回溯搜索示意图回溯搜索示意图7212.5.3 回溯策略o 回溯搜索的算法回溯搜索的算法(1) PS（path states）表）表：保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。 (2) NPS（new path states）表）表：新的路径状态表。它包含了等待搜索的

53、状态，其后裔状态还未被搜索到，即未被生成扩展 。(3) NSS（no solvable states）表）表：不可解状态集，列出了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。 7312.5.3 回溯策略o 图搜索算法（深度优先、宽度优先、最好优先搜索等）图搜索算法（深度优先、宽度优先、最好优先搜索等）的回溯思想：的回溯思想：（1）用未处理状态表（）用未处理状态表（NPS）使算法能返回（回溯）到其）使算法能返回（回溯）到其 中任一状态。中任一状态。 （2）用一张）用一张“死胡同死胡同”状态表（状态表（NSS）来避免算法重新搜索）来避免算法重新

54、搜索 无解的路径。无解的路径。 （3）在）在PS 表中记录当前搜索路径的状态，当满足目的时可表中记录当前搜索路径的状态，当满足目的时可 以将它作为结果返回。以将它作为结果返回。 （4）为避免陷入死循环必须对新生成的子状态进行检查，）为避免陷入死循环必须对新生成的子状态进行检查， 看它是否在该三张表中看它是否在该三张表中 。7412.5.4 宽度优先搜索策略o open表（表（NPS表）：表）：已经生成出来但其已经生成出来但其子状态未被搜索的子状态未被搜索的状态。状态。o closed表（表（ PS表和表和NSS表的合并）：表的合并）：记录了已被生成扩记录了已被生成扩展过的状态。展过的状态。 0

55、S12345678910宽度优先搜索法中状态的搜索次序宽度优先搜索法中状态的搜索次序75o 例例3 通过搬动积木块，希望从初始状态达到一个目的状态，即三块积木堆叠在一起。 12.5.4 宽度优先搜索策略BCAABC(a) 初始状态(b) 目的状态 积木问题积木问题76o 操作算子为MOVE（X，Y）：把积木X搬到Y（积木或桌面）上面。12.5.4 宽度优先搜索策略MOVE（A，Table）：“搬动积木A到桌面上”。 操作算子可运用的先决条件：（1）被搬动积木的顶部必须为空。（2）如果 Y 是积木，则积木 Y 的顶部也必须为空。（3）同一状态下，运用操作算子的次数不得多于一次。77ABABACC

56、BACCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(C,A)MOVE(A,C)MOVE(B,A)MOVE(B,C) MOVE(C,A)MOVE(C,B) MOVE(C,B)MOVE(A,B)0S1S2S3S4S5S6S7S8S9S10S没有后裔，失败退出 积木问题的宽度优先搜索树12.5.4 宽度优先搜索策略7812.6 电脑充绒机专家控制系统o 12.6.1电脑充绒机的工作原理电脑充绒机的工作原理o 12.6.2电脑充绒机的程序控制电脑充绒机的程序控制o 12.6.3电脑充绒机羽绒重量专家控制电脑充绒机羽绒重量专家控制7912.6.1电脑充绒机的工作原理Z7Z1Z3Z4Z5Z2去