机械控制工程精品课程7

1、Modern Control Engineering第第 12 章章 专家系统与专家控制专家系统与专家控制教材：教材：王万良，现代控制工程，高等教育出版社，王万良，现代控制工程，高等教育出版社，20112o 20世纪世纪80年代，专家系统被引入控制领域与控制理年代，专家系统被引入控制领域与控制理论相结合，尤其是启发式推理与反馈控制理论相结论相结合，尤其是启发式推理与反馈控制理论相结合，形成了专家控制系统，成为智能控制的一个重合，形成了专家控制系统，成为智能控制的一个重要分支，在工程中得到广泛应用。要分支，在工程中得到广泛应用。o 专家系统是专家控制系统的核心，本章首先简要介专家系统是专家控制系

2、统的核心，本章首先简要介绍专家系统的基本内容，然后介绍专家控制系统的绍专家系统的基本内容，然后介绍专家控制系统的基本概念、知识表示、基本推理方法和搜索策略。基本概念、知识表示、基本推理方法和搜索策略。最后介绍专家控制系统的应用实例。最后介绍专家控制系统的应用实例。第12章 专家系统与专家控制3第12章 专家系统与专家控制o 12.0 专家系统的产生和发展专家系统的产生和发展o 12.1 专家系统专家系统 o 12.2 专家控制系统专家控制系统o 12.3 专家控制系统的知识表示专家控制系统的知识表示o 12.4 专家控制系统的推理机专家控制系统的推理机o 12.5 专家控制系统的搜索技术专家控

3、制系统的搜索技术o 12.6 电脑充绒机专家控制系统电脑充绒机专家控制系统412.0 专家系统的产生和发展第一阶段第一阶段 : 初创期（初创期（20世纪世纪60年代中期年代中期 20世纪世纪70年代初）年代初）第二阶段第二阶段: 成熟期（成熟期（20世纪世纪70年代中年代中 20世纪世纪80年代初）年代初）第三阶段：发展期第三阶段：发展期（20世纪世纪80年代至今）年代至今） 512.1.1 专家系统的概念专家系统的概念12.1.2 专家系统的一般结构专家系统的一般结构12.1.3 实时专家系统实时专家系统12.1 专家系统专家系统612.1.1 专家系统的概念 1. 定义定义 费根鲍姆（费根

4、鲍姆（E. A. Feigenbaum）：）： “专家系统是一种专家系统是一种智能的计算机程序智能的计算机程序，它运用，它运用知识知识和和推理推理来解决只有专家才能解决的复杂问题。来解决只有专家才能解决的复杂问题。” 专家系统：一类包含知识和推理的智能计算机程专家系统：一类包含知识和推理的智能计算机程序序 。712.1.1 专家系统的概念 2. 专家系统的基本组成专家系统的基本组成 推 理 机数 据 库规 则 库专 家系 统 用 户知 识 获 取推 理 咨 询解 释 程 序调 度 程 序知 识 库8o 专家系统与传统程序的比较专家系统与传统程序的比较（1）编程思想）编程思想： 传统程序传统程序

5、 = 数据结构数据结构+算法算法专家系统专家系统 = 知识知识+推理推理（2）传统程序：关于问题求解的知识隐含于程序中。）传统程序：关于问题求解的知识隐含于程序中。 专家系统：知识单独组成知识库，与推理机分离。专家系统：知识单独组成知识库，与推理机分离。 （3）处理对象）处理对象： 传统程序：数值计算和数据处理。传统程序：数值计算和数据处理。 专家系统：符号处理。专家系统：符号处理。 12.1.1 专家系统的概念9o 专家系统与传统程序的比较专家系统与传统程序的比较（4）传统程序：不具有解释功能。）传统程序：不具有解释功能。 专家系统：具有解释功能。专家系统：具有解释功能。（5）传统程序：产生

6、正确的答案。）传统程序：产生正确的答案。 专家系统：通常产生正确的答案，有时产生错误的专家系统：通常产生正确的答案，有时产生错误的答案。答案。 （6）系统的体系结构不同。）系统的体系结构不同。12.1.1 专家系统的概念10专家系统的类型11专家系统的应用12专家系统的应用1312.1.2 专家系统的一般结构人机接口用户领域专家知识工程师解释机构知识获取机构数据库推理机知识库专家系统核心 专家系统的一般结构专家系统的一般结构人机接口解释机构知识获取机构综合数据库推理机知识库专家系统核心1412.1.3 实时专家系统o 实时专家系统是具有实时性的专家系统。它一方面实时专家系统是具有实时性的专家系

7、统。它一方面要满足专家系统功能的要求，另一方面还必须受时要满足专家系统功能的要求，另一方面还必须受时间条件的约束，即满足实时性要求。间条件的约束，即满足实时性要求。 o 实时专家系统的特点：实时专家系统的特点：o (1) 操作方式：操作方式：实时专家系统的信息输入主要来自实时专家系统的信息输入主要来自外界过程的传感器，且往往从多个独立的传感器输外界过程的传感器，且往往从多个独立的传感器输入。入。 o (2) 输出去向：输出去向：实时专家系统直接送往过程的控制实时专家系统直接送往过程的控制器或（和）向生产人员送出诊断、预报、操作指导器或（和）向生产人员送出诊断、预报、操作指导等信息。等信息。 1

8、512.1.3 实时专家系统o (3) 数据特征：数据特征：实时专家系统数据是连续时变的，实时专家系统数据是连续时变的，是实时数据，信息量往往很大。是实时数据，信息量往往很大。o (4) 中断功能：中断功能：实时专家系统一方面要满足专家系实时专家系统一方面要满足专家系统功能的要求，另一方面还必须受时间条件的约束，统功能的要求，另一方面还必须受时间条件的约束，即满足实时性的要求。即满足实时性的要求。 o (5) 实时性：实时性：实时专家系统响应要求快，常常为毫实时专家系统响应要求快，常常为毫秒、秒级。实时性的要求是实时专家系统首先必须秒、秒级。实时性的要求是实时专家系统首先必须考虑的。考虑的。o

9、 (6) 推理过程：推理过程：实时专家系统采用实时推理。实时专家系统采用实时推理。1612.2 专家控制系统o 12.2.1 专家控制系统的概念专家控制系统的概念o 12.2.2 间接专家控制间接专家控制o 12.2.3 直接专家控制直接专家控制o 12.2.4 专家控制器专家控制器1712.2.1 专家控制系统的概念o 从专家系统的角度，专家控制是专家系统的一个重从专家系统的角度，专家控制是专家系统的一个重要分支，属于实时专家系统研究领域；要分支，属于实时专家系统研究领域；o 从自动控制的角度，专家控制是智能控制的一个重从自动控制的角度，专家控制是智能控制的一个重要分支，是将专家系统的思想和

10、方法引入控制系统，要分支，是将专家系统的思想和方法引入控制系统，从而形成一种新的控制方法。从而形成一种新的控制方法。o 许多生产过程具有强烈的非线性、时变性及不确定许多生产过程具有强烈的非线性、时变性及不确定性，专家控制模拟人类推理能力，把生产操作人员、性，专家控制模拟人类推理能力，把生产操作人员、工程师的经验与控制算法结合起来，即把符号推理工程师的经验与控制算法结合起来，即把符号推理与数值运算结合起来，为过程控制提供了一种新的与数值运算结合起来，为过程控制提供了一种新的控制方法。控制方法。1812.2.2 间接专家控制o 间接专家控制也称为专家监督控制。其中，常规控间接专家控制也称为专家监督

11、控制。其中，常规控制器控制过程运行。制器控制过程运行。o 间接专家系统是通过对常规控制器的调整，间接地间接专家系统是通过对常规控制器的调整，间接地影响被控过程。影响被控过程。 设定输出专家系统控制器控制对象1912.2.3 直接专家控制o 在直接专家控制系统中，专家系统根据所测到的过在直接专家控制系统中，专家系统根据所测到的过程信息及知识库中的规则，导出每一采样时刻的控程信息及知识库中的规则，导出每一采样时刻的控制信号。制信号。 设定输出专家系统控制对象2012.3 专家控制系统的知识表示o 12.3.112.3.1 知识表示知识表示o 12.3.2 12.3.2 产生式知识表示产生式知识表示

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

13、、状态空间、人工神经网络、遗传编码等。遗传编码等。o 在专家控制系统中，特别是在专家控制器中，产生在专家控制系统中，特别是在专家控制器中，产生式表示法用得十分广泛。式表示法用得十分广泛。 221. 确定性规则知识的产生式表示确定性规则知识的产生式表示2. 不确定性规则知识的产生式表示不确定性规则知识的产生式表示 基本形式：基本形式： IF P THEN Q 或者：或者： 例如：例如： r4：IF 动物会飞动物会飞 AND 会下蛋会下蛋 THEN 该动物是鸟该动物是鸟QP 基本形式：基本形式： IF P THEN Q （置信度）（置信度） 或者：或者： （置信度（置信度） 例如：例如： IF 发

14、烧发烧 THEN 感冒感冒 （0.6）QP 12.3.2 产生式知识表示233. 确定性事实性知识的产生式表示确定性事实性知识的产生式表示4. 不确定性事实性知识的产生式表示不确定性事实性知识的产生式表示 三元组表示：（对象，属性，值）三元组表示：（对象，属性，值） 或者：（关系，对象或者：（关系，对象1，对象，对象2） 例：例： 老李年龄是老李年龄是40岁：岁： （Li，age，40） 老李和老王是朋友：（老李和老王是朋友：（friend，Li，Wang） 四元组表示：（对象，属性，值，置信度）四元组表示：（对象，属性，值，置信度） 或者：或者： （关系，对象（关系，对象1，对象，对象2，置

15、信度），置信度）例：老李年龄很可能是例：老李年龄很可能是40岁：岁：（Li，age，40，0.8） 老李和老王不大可能是朋友：（老李和老王不大可能是朋友：（friend，Li，Wang，0.1）12.3.2 产生式知识表示2412.3.3 产生式系统产生式系统控 制规则库推理机综合数据库产生式系统的基本结构2512.3.4 产生式系统的例子动物识别专家系统例如：例如：动物识别系统动物识别系统识别识别虎、金钱豹、斑马、长颈虎、金钱豹、斑马、长颈鹿、鸵鸟、企鹅、信天翁鹿、鸵鸟、企鹅、信天翁等七种动物的产生式系统。等七种动物的产生式系统。2612.3.4 产生式系统的例子产生式系统的例子动物识别专家

16、系统动物识别专家系统o 规则库：规则库：r1： IF 该动物有毛发该动物有毛发 THEN 该动物是哺乳动物该动物是哺乳动物r2： IF 该动物有奶该动物有奶 THEN 该动物是哺乳动物该动物是哺乳动物r3： IF 该动物有羽毛该动物有羽毛 THEN 该动物是鸟该动物是鸟r4： IF 该动物会飞该动物会飞 AND 会下蛋会下蛋 THEN 该动物是鸟该动物是鸟r5： IF 该动物吃肉该动物吃肉 THEN 该动物是食肉动物该动物是食肉动物r6： IF 该动物有犬齿该动物有犬齿 AND 有爪有爪 AND 眼盯前方眼盯前方 THEN 该动物是食肉动物该动物是食肉动物r7： IF 该动物是哺乳动物该动物是

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

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

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

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

21、（1）自然性）自然性 （2）模块性）模块性 （3）有效性）有效性 （4）清晰性）清晰性 2. 产生式表示法的缺点产生式表示法的缺点（1）效率不高）效率不高 （2）不能表达结构性知识）不能表达结构性知识 3. 适合产生式适合产生式表示的知识表示的知识（1）领域知识间关系不密切，）领域知识间关系不密切，不存在结构关系。不存在结构关系。（2）经验性及不确定性的知识，）经验性及不确定性的知识，且相关领域中对这些知识没有且相关领域中对这些知识没有严格、统一的理论。严格、统一的理论。（3）领域问题的求解过程可被）领域问题的求解过程可被表示为一系列相对独立的操作，表示为一系列相对独立的操作，且每个操作且每个

22、操作可被表示为一条或可被表示为一条或多条产生式规则。多条产生式规则。3112.4 专家控制系统的推理机专家控制系统的推理机o 12.4.1 推理的基本概念推理的基本概念o 12.4.2 推理方式及其分类推理方式及其分类o 12.4.3 推理的方向推理的方向o 12.4.4 冲突消解策略冲突消解策略32知识智能?经典逻辑推理（确定性推理）不确定性推理自然演绎推理归结演绎推理与/或形演绎推理推理推理知识智能 !12.4.1 推理的基本概念推理的基本概念从初始证据出发，按某种策从初始证据出发，按某种策略不断运用知识库中的已知略不断运用知识库中的已知知识，逐步推出结论的过程知识，逐步推出结论的过程称为

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

24、 reasoning): 个别个别 一般一般 完全归纳推理（完全归纳推理（必然性推理）必然性推理） 不完全归纳推理不完全归纳推理（非必然性推理）（非必然性推理）检查全部产品合格检查全部产品合格该厂产品合格该厂产品合格完全归纳推理完全归纳推理检查全部样品合格检查全部样品合格该厂产品合格该厂产品合格不完全归纳推理不完全归纳推理3512.4.2 推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理、归纳推理、默认推理（3）默认推理默认推理（default reasoning，缺省推理），缺省推理）n 知识不完全的情况下假设某些条件已经具备所进行的推理知识不完全的情况下假设某些条件已经具备所进行

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

26、定的，推出的结论也是不确定的。的，推出的结论也是不确定的。37X：鸟：鸟 X：会飞：会飞 X: 企鹅企鹅 12.4.2 推理方式及其分类 3. 单调推理、非单调推理单调推理、非单调推理 （1）单调推理单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。 （2）非单调推理非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。 默认推理是非单调推理默认推理是非单调推理 基于经典逻辑的演绎推理基于经典逻辑的演绎推理 X：不会飞不会飞X：企鹅：企鹅3812.4.2 推理方式及其分类4启发式推理、非启发式推理启发式推理、非启发式推理

27、 启发性知识启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。 目标：在脑膜炎、肺炎、流感中选择一个目标：在脑膜炎、肺炎、流感中选择一个 产生式规则产生式规则 r1：脑膜炎：脑膜炎 r2：肺：肺 炎炎 r3：流：流 感感 启发式知识：启发式知识：“脑膜炎危险脑膜炎危险”、“目前正在盛行流目前正在盛行流感感”。3912.4.3 推理的方向正向推理逆向推理(反向推理)双向推理混合推理推理方向推理机数据库知识库专家用户4012.4.3 推理的方向n 正向推理（事实驱动推理）正向推理（事实驱动推理）: 已知事实已知事实 结论结论 基本思想基本思想（1）从初始已知事实出发，在知识库）从初始已知

28、事实出发，在知识库KB中找出当前可适中找出当前可适用的知识，构成可适用知识集用的知识，构成可适用知识集KS。（2）按某种冲突消解策略从）按某种冲突消解策略从KS中选出一条知识进行推理，中选出一条知识进行推理，并将推出的新事实加入到数据库并将推出的新事实加入到数据库DB中作为下一步推理的中作为下一步推理的已知事实，再在已知事实，再在KB中选取可适用知识构成中选取可适用知识构成KS 。（3）重复（）重复（2），直到求得问题的解或），直到求得问题的解或KB中再无可适用中再无可适用的知识。的知识。正向推理正向推理4112.5 专家控制系统的搜索技术专家控制系统的搜索技术o 12.5.0 搜索的基本问题

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

30、题缺乏数学求绝大多数需要人工智能方法求解的问题缺乏数学求解的方法，因此，搜索不失为一种求解问题的一般解的方法，因此，搜索不失为一种求解问题的一般方法，应用非常广泛。方法，应用非常广泛。o 搜索算法是要决定树或图中状态的搜索次序。宽度、搜索算法是要决定树或图中状态的搜索次序。宽度、深度优先搜索是状态空间的最基本的搜索策略。深度优先搜索是状态空间的最基本的搜索策略。4312.5.0 搜索的基本问题与主要过程o 搜索的主要过程：搜索的主要过程：(1) 从初始或目的状态出发，并将它作为当前状态。从初始或目的状态出发，并将它作为当前状态。(2) 扫描操作算子集，将适用当前状态的一些操作算子扫描操作算子集

31、，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父作用于当前状态而得到新的状态，并建立指向其父结点的指针结点的指针 。(3) 检查所生成的新状态是否满足结束状态，如果满足，检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第新状态作为当前状态，返回第(2)步再进行搜索。步再进行搜索。 4412.5.0 搜索策略o 盲目搜索与启发式搜索盲目搜索与启发式搜索:（1）盲目搜索）盲目搜

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

33、知识的一组变量或数组：量或数组：,21nqqqQ,21mfffF 操作：表示引起状态变化的过程型知识的一组关操作：表示引起状态变化的过程型知识的一组关 系或函数：系或函数：T4612.5.1 状态空间表示法o 状态空间：利用状态变量和操作符号，表示系统或状态空间：利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元问题的有关知识的符号体系，状态空间是一个四元组：组： ),(0GSOS ：状态集合。：状态集合。 ：操作算子的集合。：操作算子的集合。 ：包含问题的初始状态是：包含问题的初始状态是 的非空子集。的非空子集。 ：若干具体状态或满足某些性质的路径信息描述。：若干

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

35、间的有向图描述51 例例2 旅行商问题旅行商问题（traveling salesman problem, TSP）或邮递员路径问题。或邮递员路径问题。 12.5.2 状态空间的图描述（家）（单位：km）可能路径：费用为375的路径（A，B，C，D，E，A） 5212.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 费用 : 费用 : 费用 : 费用: 425 525 475 525 475 375 3

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

37、有，则沿这些子结点继续搜索；如果找到目标，若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。就成功退出搜索，返回解题路径。5412.5.3 回溯策略1 AB 2E 3J 57 K9 G6 F10 H11 D8 C回溯搜索示意图回溯搜索示意图5512.5.4 宽度优先搜索策略o open表（表（NPS表）：表）：已经生成出来但其已经生成出来但其子状态未被搜索的子状态未被搜索的状态。状态。o closed表（表（ PS表和表和NSS表的合并）：表的合并）：记录了已被生成扩记录了已被生成扩展过的状态。展过的状态。 0S12345678910宽度优先搜索法中状态的搜索次序宽度优

38、先搜索法中状态的搜索次序5612.6 电脑充绒机专家控制系统o 12.6.1电脑充绒机的工作原理电脑充绒机的工作原理o 12.6.2电脑充绒机的程序控制电脑充绒机的程序控制o 12.6.3电脑充绒机羽绒重量专家控制电脑充绒机羽绒重量专家控制5712.6.1电脑充绒机的工作原理Z7Z1Z3Z4Z5Z2去 料 仓去 被 套料 斗金 属 网高 压 气 体上 箱下 箱来 自料 仓鼓 风 机Z6高 压 气 体5812.6.1电脑充绒机的工作原理电脑充绒机的工作原理o 羽绒定量充绒过程是：羽绒定量充绒过程是：o 料仓里的羽绒随鼓风机产生的气流经下箱进入料斗，料仓里的羽绒随鼓风机产生的气流经下箱进入料斗，过

39、滤网将羽绒留在料斗里，气流则通过过滤网经上过滤网将羽绒留在料斗里，气流则通过过滤网经上箱流回料仓，实现封闭传送。箱流回料仓，实现封闭传送。o 当料斗里的羽绒预测重量达到设定值时，由计算机当料斗里的羽绒预测重量达到设定值时，由计算机控制气阀停止进料，然后改变气路，使羽绒随气流控制气阀停止进料，然后改变气路，使羽绒随气流从料斗里经下箱充入充绒工作台上的被套或羽绒服从料斗里经下箱充入充绒工作台上的被套或羽绒服内，从而完成一次自动充绒工作循环。内，从而完成一次自动充绒工作循环。5912.6.1电脑充绒机的工作原理电脑充绒机的工作原理o 电脑充绒机的关键技术：电脑充绒机的关键技术：高精度动态计量。羽绒重高精度动态计量。羽绒重量轻，体积大，易膨胀，受充绒机结构限制测量范量轻，体积大，易膨胀，受充绒机结构限制测量范围较小，加上气流对料斗的影响，造成检测信号弱围较小，加上气流对料斗的影响，造成检测信号弱而