定性模型推理-智能科学课件.ppt

1、定性推理定性推理史忠植史忠植中国科学院计算技术研究所中国科学院计算技术研究所高级人工智能高级人工智能第四章2022-6-5史忠植 高级人工智能2内容提要内容提要4.1 概述概述4.2 定性推理的基本方法定性推理的基本方法4.3 定性模型推理定性模型推理 4.4 定性进程推理定性进程推理 4.5 定性仿真推理定性仿真推理4.6 代数方法代数方法4.7 几何空间定性推理几何空间定性推理什么是定性推理？什么是定性推理？ 定性推理定性推理(qualitative reasoning)是从物理系是从物理系统 、 生 命 系 统 的 结 构 描 述 出 发统 、 生 命 系 统 的 结 构 描 述 出 发

2、 , 导 出 行 为 描 述导 出 行 为 描 述 , 以便预测系统的行为并给出原因解释。定性推理以便预测系统的行为并给出原因解释。定性推理采用系统部件间的局部结构规则来解释系统行为采用系统部件间的局部结构规则来解释系统行为, 即部件状态的变化行为只与直接相邻的部件有关。即部件状态的变化行为只与直接相邻的部件有关。2022-6-5史忠植 高级人工智能4 概述概述1952年年 Simmons提出定性分析的因果关系。提出定性分析的因果关系。1977年年 Rieger 发表了因果仿真的论文。发表了因果仿真的论文。1984年年 “Artificial Intelligence”杂志第杂志第24卷出版了

3、定性推理专辑卷出版了定性推理专辑, 刊载了刊载了 de Kleer, Forbus 和和Kuipers对定性推理奠基性的对定性推理奠基性的 文章文章, 这标志着定性推理开始走向成熟。这标志着定性推理开始走向成熟。1986年年 Iwasaki和和Simmons发表了发表了“Causality in Device Behavior” 的文章。的文章。1993年年 “Artificial Intelligence”杂志第杂志第59卷又发表了一组文章，卷又发表了一组文章， 回顾十年前这几位定性推理奠基人所做的工作。回顾十年前这几位定性推理奠基人所做的工作。2022-6-5史忠植 高级人工智能5 概述概

4、述de Kleer的定性模型方法的定性模型方法de Kleer 1984Forbus的定性进程方法的定性进程方法Forbus 1984Kuipers 定性仿真法定性仿真法Kuipers 19842022-6-5史忠植 高级人工智能6 概述概述Davis 提出从结构描述出发进行故障论断的方法提出从结构描述出发进行故障论断的方法Reiler提出从基本原理出发进行故障诊断的方法提出从基本原理出发进行故障诊断的方法Williams把定量运算和定性推理相结合建立了一个把定量运算和定性推理相结合建立了一个 混合代数系统混合代数系统Q1Iwasaki 和和 Simmons把经济学、热力学中所用的因果把经济学

5、、热力学中所用的因果 关系形式化关系形式化Weld在分子生物学中设计了定性模拟程序在分子生物学中设计了定性模拟程序 2022-6-5史忠植 高级人工智能7定性推理的基本方法定性推理的基本方法 人类对物理世界的描述、解释人类对物理世界的描述、解释, 常是以某种直观的定性常是以某种直观的定性方法进行的方法进行的,很少使用微分方程及具体的数值描述很少使用微分方程及具体的数值描述, 如如人们在骑自行车时人们在骑自行车时, 为了避免摔倒和撞车为了避免摔倒和撞车, 并不需要使用并不需要使用书本上的运动方程书本上的运动方程, 而是针对几个主要参量的变化趋势而是针对几个主要参量的变化趋势给予粗略的、直观的给予

6、粗略的、直观的, 但大体上准确的描述但大体上准确的描述, 这就够了。这就够了。2022-6-5史忠植 高级人工智能8定性推理的基本方法定性推理的基本方法 一般分析运动系统行为的标准过程可分为三个步骤：一般分析运动系统行为的标准过程可分为三个步骤： (1) 决定描述对象系统特征的量。决定描述对象系统特征的量。 (2) 用方程式表示量之间的相互关系。用方程式表示量之间的相互关系。 (3) 分析方程式，得到数值解。分析方程式，得到数值解。2022-6-5史忠植 高级人工智能9定性推理的基本方法定性推理的基本方法这类运动系统行为的问题用计算机进行求解时，这类运动系统行为的问题用计算机进行求解时，将面临

7、如下三个问题：将面临如下三个问题： (1) 步骤步骤(1)(2)需要相当多的知识，并且要有相应的需要相当多的知识，并且要有相应的算法。算法。 (2) 有的场合对象系统的性质很难用数学式子表示。有的场合对象系统的性质很难用数学式子表示。 (3) 步骤步骤(3)得到了数值解，但是对象系统的行为并得到了数值解，但是对象系统的行为并不直观明了。不直观明了。2022-6-5史忠植 高级人工智能10定性推理的基本方法定性推理的基本方法为了解决第二、第三个问题，定性推理一般采用下列分析步骤：为了解决第二、第三个问题，定性推理一般采用下列分析步骤： (1) 结构认识：将对象系统分解成部件的组合。结构认识：将对

8、象系统分解成部件的组合。 (2) 因果分析：当输入值变化时，分析对象系统中怎样传播。因果分析：当输入值变化时，分析对象系统中怎样传播。 (3) 行为推理：输入值随着时间变化，分析对象系统的内部行为推理：输入值随着时间变化，分析对象系统的内部状态怎样变化。状态怎样变化。 (4) 功能说明：行为推理的结果表明对象系统的行为，由此功能说明：行为推理的结果表明对象系统的行为，由此可以说明对象系统的功能。可以说明对象系统的功能。2022-6-5史忠植 高级人工智能11定性推理的基本方法定性推理的基本方法定性推理的观点大体上可这样来理解定性推理的观点大体上可这样来理解: 忽略被描述对象的次要因素忽略被描述

9、对象的次要因素, 掌握主要因素简化问题的描述。掌握主要因素简化问题的描述。 将随时间将随时间 t连续变化的参量连续变化的参量 x(t) 的值域离散化为定性值集合的值域离散化为定性值集合, 通常变量通常变量 x的定性值的定性值 x定义为定义为 依物理规律将微分方程转换成定性依物理规律将微分方程转换成定性(代数代数)方程方程, 或直接依物理或直接依物理 规律建立定性模拟或给出定性进程描述。规律建立定性模拟或给出定性进程描述。 最后给出定性解释最后给出定性解释 0000 xxxx当当当2022-6-5史忠植 高级人工智能12定性模型推理定性模型推理de Kleerde Kleer研究解决经典物理问题

10、需要哪些知识及如何研究解决经典物理问题需要哪些知识及如何建立问题求解系统。他提出的定性模型方法所涉及建立问题求解系统。他提出的定性模型方法所涉及的物理系统是由管子、阀门、容器等装置组成的物理系统是由管子、阀门、容器等装置组成, , 约束约束条件条件( (定性方程定性方程) )反映在这些装置的连接处反映在这些装置的连接处, , 依定性方依定性方程给出定性解释。程给出定性解释。 为将代数方程、微分方程定性化为将代数方程、微分方程定性化, , 首先需定义变首先需定义变量的定性值集合以及相应的定性运算。量的定性值集合以及相应的定性运算。2022-6-5史忠植 高级人工智能13定性模型推理定性模型推理定

11、性值集合是一个离散集合定性值集合是一个离散集合, 其元素是由对数轴的划分而得到其元素是由对数轴的划分而得到的的, 通常把数轴通常把数轴 (,)划分成划分成 (,0) , 0,(0, ) 三段三段, 规定定性规定定性值集合为值集合为 ,0, 变量变量 x的定性值的定性值 x如下定义如下定义: 0000 xxxx当当当另外用 x表示 dx/dt的定性值, 也即dtdxx2022-6-5史忠植 高级人工智能14定性模型推理定性模型推理 xy-0+-?0-0+?+x y x y-0+-+0-0000+-0+x y 其中: 符号？表示不确定或无定义。 2022-6-5史忠植 高级人工智能15定性模型推理

12、定性模型推理下面给出 和 的运算规则。设 e1, e2是公式, 则有：0 e1e10 e10+ e1e1- e1-e12022-6-5史忠植 高级人工智能16定性模型推理定性模型推理使用下列规则，可将运算符使用下列规则，可将运算符+、 转换成转换成 、 ： e1e2 e1 e2e1e2 e1 e22022-6-5史忠植 高级人工智能17压力调节器压力调节器压力调节器是通过弹簧来控制阀门流量压力调节器是通过弹簧来控制阀门流量, 以使流量为以使流量为某一设定值而不受流入的流量和负载变化的影响。根某一设定值而不受流入的流量和负载变化的影响。根据物理学有据物理学有02PPCAQdtdPPCAdtdAP

13、CdtdQ222022-6-5史忠植 高级人工智能18压力调节器压力调节器其中其中 Q是通过阀门的流量是通过阀门的流量,P是压力是压力, A是阀门开启的面是阀门开启的面积积, 而而C是常系数是常系数, 是流体的质量密度。按照运算和转是流体的质量密度。按照运算和转换规则而得到定性方程：换规则而得到定性方程：Q = PQ = A + P (如果A 0)2022-6-5史忠植 高级人工智能19压力调节器压力调节器OPEN状态A = Amax定性方程P = 0P = 0WORKING 状态0A Atemperature(dst) src 温度高于dst温度2022-6-5史忠植 高级人工智能26定性进

14、程推理定性进程推理 Relations: 一组参量关系 Let flow-rate be a quantity flow-rate (热流量)是一个数量 Aflow-rate ZERO. flow-rate 值0 flow-rate Q+ (temperature(src) -temperature(dst) flow-rate与src,dst 的温差定性成比例 Influences: 一组影响 1-(heat(src), Aflow-rate) flow-rate的值直接影响 heat(src),而且是负影响 1(heat (dst), Aflow-rate) flow-rate的值直接影响

15、 heat(dst),而且是正影响2022-6-5史忠植 高级人工智能27定性进程推理定性进程推理演绎过程演绎过程 在进程定性推理中，其演绎过程如下：在进程定性推理中，其演绎过程如下： (1) 选进程。选进程。 对一组已知的个体来说对一组已知的个体来说, 在进程表中依各进程对个在进程表中依各进程对个体的说明找出可能出现的那些进程例体的说明找出可能出现的那些进程例PI。 (2) 确定激活的确定激活的 PI。依前提条件、数量条件确定每个。依前提条件、数量条件确定每个 PI的状态。的状态。满足这些条件的为激活的满足这些条件的为激活的 PI , 激活的激活的 PI 叫进程结构。叫进程结构。 (3) 确

16、定量的变化。确定量的变化。 个体的变化由相应量的个体的变化由相应量的 Ds 值来表示。量的值来表示。量的变化可由进程直接影响，也可由变化可由进程直接影响，也可由Q间接影响。间接影响。 (4) 确定进程结构变化。量的变化将会引起进程结构的变化确定进程结构变化。量的变化将会引起进程结构的变化,确确定这种变化也叫限制分析定这种变化也叫限制分析, 这样对一个物理过程的描述便由这样对一个物理过程的描述便由 (1)建建立的立的 PI 进入了下一个进入了下一个 PI 。重复重复(1)(4) 的步骤便可给出一个物理过程的一串进程描述。的步骤便可给出一个物理过程的一串进程描述。2022-6-5史忠植 高级人工智

17、能28定性进程推理定性进程推理2022-6-5史忠植 高级人工智能29定性仿真推理定性仿真推理 1984年年 Kuipers 发表了发表了“因果性的常识推理：从结构导出因果性的常识推理：从结构导出行为行为”论文。这篇论文建立了一种定性仿真推理的框架论文。这篇论文建立了一种定性仿真推理的框架, 简单地给出了从常微分方程的抽象而得的定性结构和定性简单地给出了从常微分方程的抽象而得的定性结构和定性行为表示方法。随后，行为表示方法。随后，1986年年AI杂志又刊登了杂志又刊登了Kuipers“定性仿真定性仿真”一文，文中明确了抽象关系，提出用于定性一文，文中明确了抽象关系，提出用于定性仿真的仿真的QS

18、IM算法，并用抽象关系证明了其有效性和不算法，并用抽象关系证明了其有效性和不完备性。这两篇文章奠定了定性仿真的基础。演绎过程完备性。这两篇文章奠定了定性仿真的基础。演绎过程 2022-6-5史忠植 高级人工智能30定性仿真推理定性仿真推理 定性仿真是从结构的定性描述出发来导出行为描述。直接用定性仿真是从结构的定性描述出发来导出行为描述。直接用部件的参量作为状态变量来描述物理结构部件的参量作为状态变量来描述物理结构, 定性约束直接由定性约束直接由物理规律得到物理规律得到, 把一个参量随时间的变化视作定性的状态序列把一个参量随时间的变化视作定性的状态序列, 求解算法是从初始状态出发求解算法是从初始

19、状态出发, 生成各种可能的后续状态生成各种可能的后续状态, 进而进而通过一致性过滤通过一致性过滤, 重复该过程直到没有新状态出现。重复该过程直到没有新状态出现。 定性仿真结构描述由系统的状态参数和约束关系组成。认为定性仿真结构描述由系统的状态参数和约束关系组成。认为参数是时间的可微函数参数是时间的可微函数, 约束是参数间的二元或多元关系。如约束是参数间的二元或多元关系。如速度的导数是加速度。表为速度的导数是加速度。表为 DERIV(Vel, acc)。f = ma 表为表为 MULT(m,a,f), f 随随 g单调增加表为单调增加表为 M+(f,g),f 随随 g单调减少单调减少, 表表为为

20、 M-(f,g)。2022-6-5史忠植 高级人工智能31定性仿真推理定性仿真推理行为描述关心参量的变化。假设参量行为描述关心参量的变化。假设参量f(t)是是a,b到到, 的可微函数。的可微函数。f的界标值是一个有限集合的界标值是一个有限集合, 至少含有至少含有 f(a),f(b)。集合集合 t|t a,b f(t) 是界标值是界标值 的元素称作区别点。的元素称作区别点。 定义定义4.1 设设 l1l2 lk是是f: a,b -, 的界标值。对的界标值。对任意任意t a,b, f 在在 t的定性状态的定性状态 QS(f,t)规定为有序对规定为有序对 ,定义如下定义如下:),(),(11jjtj

21、jjtjllflllflqval如果如果2022-6-5史忠植 高级人工智能32定性仿真推理定性仿真推理0)(0)(0)(tfdectfstdtfincqdir如果如果如果2022-6-5史忠植 高级人工智能33定性仿真推理定性仿真推理 定义定义 4.2 设设 ti, ti+1是相邻的区分点是相邻的区分点,规定规定 f在在 (ti,ti+1)内的内的定性状态定性状态 QS(f, ti, ti+1) 仍为仍为 QS(f,t) 其中 t(ti,ti+1) 2022-6-5史忠植 高级人工智能34定性仿真推理定性仿真推理定义定义 4.3 f 在在 a,b上的定性行为是上的定性行为是f的定性状态序列的

22、定性状态序列QS(f,t0), QS(f,t0,t1), QS(f, t1), ,QS(f, tn)。其中。其中 ti(i=0,1,n)为所有的为所有的区分点区分点, 且且ti ti+1,若若 F = f1, , fn, 则则 F的定性行为是的定性行为是QS(F,ti) = QS(f1,ti), QS(fn,ti) QS(F,ti,ti+1)= QS(f1,ti,ti+1), QS(fn,ti,ti+1) 其中其中 ti 是是f1, , fk 区分点并集的元素。区分点并集的元素。 2022-6-5史忠植 高级人工智能35定性仿真推理定性仿真推理定性状态转换定性状态转换 在定性仿真中，定性状态转

23、移是经常遇到的。假设在定性仿真中，定性状态转移是经常遇到的。假设 f是是可微函数可微函数,f从一个定性状态转换到另一个定性状态必须遵守从一个定性状态转换到另一个定性状态必须遵守介值定理和中值定理。定性状态转换有两类：一类是介值定理和中值定理。定性状态转换有两类：一类是P 转转换，该类转换是从时间点到时间区间；另一类是换，该类转换是从时间点到时间区间；另一类是I 转换，转换，它是从时间区间到时间点的转换。下面给出转换表它是从时间区间到时间点的转换。下面给出转换表:2022-6-5史忠植 高级人工智能36定性仿真推理定性仿真推理P转换QS(f,ti)QS(f,ti,ti+1)P1P2P3P4P5P

24、6P72022-6-5史忠植 高级人工智能37定性仿真推理定性仿真推理I 转换QS(f,ti,ti+1)QS(f,ti+1)I1I2I3I4I5I6I7I8I92022-6-5史忠植 高级人工智能38定性仿真推理定性仿真推理 QSIM算法可对系统的行为进行定性仿真。首先将初始状态送入算法可对系统的行为进行定性仿真。首先将初始状态送入 ACTIVE表中表中, 然后重复然后重复 (1)(6)直至直至 ACTIVE 表空为止。表空为止。算法算法 4.1 QSIM算法。算法。 (1) 从从 ACTIVE表中选一状态。表中选一状态。 (2) 对每个参数按转换表找出所有可能的转换。对每个参数按转换表找出所

25、有可能的转换。 (3) 对约束中变元的转换生成二元组对约束中变元的转换生成二元组, 三元组集合三元组集合, 依约束关系依约束关系做一致性滤波。做一致性滤波。 (4) 对有公共变元的约束对有公共变元的约束, 对元组进行组对对元组进行组对, 再对组对的元组做再对组对的元组做一致性滤波。一致性滤波。2022-6-5史忠植 高级人工智能39定性仿真推理定性仿真推理(5) 从剩下的元组生成所有可能的全局解释。每个解释生成从剩下的元组生成所有可能的全局解释。每个解释生成 一个新状态作为当前状态的后继状态。一个新状态作为当前状态的后继状态。(6) 对新状态做全局滤波对新状态做全局滤波, 剩下的状态送入剩下的

26、状态送入 ACTIVE 表。全局表。全局 滤波排除下列状态：滤波排除下列状态： 无变化情形无变化情形: 如如 I1, I4, I7; 循环情形循环情形: 新状态与某个前辈状态相同新状态与某个前辈状态相同; 发散情形发散情形: 某参数值为某参数值为, 这时当前时间点必为结束点。这时当前时间点必为结束点。2022-6-5史忠植 高级人工智能40几何空间定性推理几何空间定性推理空间定性推理是对几何形状或者运动性质进行定性推理，空间定性推理是对几何形状或者运动性质进行定性推理，首先需对空间位置及运动方式进行定性表示，进而对几何首先需对空间位置及运动方式进行定性表示，进而对几何形状及运动性质进行推理研究

27、及预测分析，并作出逻辑解形状及运动性质进行推理研究及预测分析，并作出逻辑解释。空间定性推理是通过定义一组空间并寻找这些关系间释。空间定性推理是通过定义一组空间并寻找这些关系间的联系来进行的。目前主要的研究是针对空间定性建模方的联系来进行的。目前主要的研究是针对空间定性建模方式、式、 空间形状及关系的定性表示和定性技术的形式化等空间形状及关系的定性表示和定性技术的形式化等, 产生解释理论产生解释理论, 但总体来看与解决工程问题距离尚远。但总体来看与解决工程问题距离尚远。2022-6-5史忠植 高级人工智能41几何空间定性推理几何空间定性推理将将Allen的时态逻辑的时态逻辑Allen 1984与

28、与Randall的空间逻辑的空间逻辑Randall 1992结合起来，形成空间、时间、连续运动的结合起来，形成空间、时间、连续运动的表达逻辑。表达逻辑。 另外从空间定性推理派生出空间规划理论另外从空间定性推理派生出空间规划理论, 可用于为一组可用于为一组几何对象寻找满足一组约束的分布设计几何对象寻找满足一组约束的分布设计, 有关方法主要用于有关方法主要用于设计自动化、定性建模等领域。设计自动化、定性建模等领域。 在这一领域已取得了一些在这一领域已取得了一些较有实际意义的成果较有实际意义的成果, 如约束满足问题如约束满足问题(CSP)求解理论求解理论, 而实而实际上很多空间定性规划都是一个几何约

29、束满足问题际上很多空间定性规划都是一个几何约束满足问题(GCSP)。2022-6-5史忠植 高级人工智能42几何空间定性推理几何空间定性推理1992年由年由Randell等人建立起来的等人建立起来的RCC 空间时间逻辑是用于空间时间逻辑是用于对空间问题进行可达性的展望对空间问题进行可达性的展望, 并已程序实现。与并已程序实现。与Kuipers的的QSIM方法类似方法类似, 基于基于RCC 逻辑的仿真算法也是从对系统进逻辑的仿真算法也是从对系统进行结构性的描述开始的行结构性的描述开始的, 系统将初始状态作为生成树的根系统将初始状态作为生成树的根结点结点, 可能的行为则是树中从根结点到叶结点的路径

30、。可能的行为则是树中从根结点到叶结点的路径。2022-6-5史忠植 高级人工智能43Qualitative Spatial ReasoningQualitative reasoningmodelling the continuous reality in manageable entitiessolution for quantitative problems that are not computableTwo approachesartificial intelligence GI Science1992 Randell, Cui, Cohndatabases GI Systems1991

31、 Egenhofer, FranzosaGISRUK 2004 University of East AngliaSlide 5 of 20几何空间定性推理几何空间定性推理2022-6-5史忠植 高级人工智能44RCCRCC =Region Connection CalculusRandell, Cui, Cohntopological relations of polygonsqualitative modellingdisjoint, meet, overlapconceptual neighbourhood-diagramGISRUK 2004 University of East An

32、gliaSlide 6 of 20RCC几何空间定性推理几何空间定性推理2022-6-5史忠植 高级人工智能45RCC - diagramGISRUK 2004 University of East AngliaSlide 7 of 20Conceptual neighbourhood diagram几何空间定性推理几何空间定性推理Qualitative CalculiQualitative Calculi lThe success of qualitative reasoning relies on choice of good qualitative calculilA q-calculu

33、s is generated by a set of jointly exhaustive and pairwise disjoint (JEPD) relations on the domain of discourse2022-6-5史忠植 高级人工智能47RCC8 Topological AlgebralRegions are nonempty regular closed subsets of a connected regular topological space (e.g. Euclidean space)lBasic RCC8 relations are defined on

34、regions2022-6-5史忠植 高级人工智能48RCC8 Basic RelationsRCC8 Basic Relations DC EC PO TPP NTPP EQdisjoint meet overlap covered_by contained_by equalBABABABAA=BBA2022-6-5史忠植 高级人工智能49Directional ModelDirectional ModellPoint-basedProjection-basedCone-basedlRegion-basedRectangle AlgebraDirection-Relation Matix M

35、odel2022-6-5史忠植 高级人工智能50Cone-Based Cardinal DirectionsCone-Based Cardinal DirectionslFrank AU. Qualitative spatial reasoning: Cardinal directions as an example. IJGIS, 1996,10:269290 2022-6-5史忠植 高级人工智能51Projection-Based Card. DirectionslFrank AU. Qualitative spatial reasoning: Cardinal directions as

36、 an example. IJGIS, 1996,10:2692902022-6-5史忠植 高级人工智能52Rectangle AlgebraRectangle AlgebralThe rectangle relation between two boxes A,B is described by the interval relations between the x- and y-projections of A, BABABA(o,oi)BA(m,d)B2022-6-5史忠植 高级人工智能53Direction-Relation MatrixDirection-Relation Matr

37、ixlR.K. Goyal, M.J. Egenhofer: Similarity of Cardinal Directions. SSTD 2001: 36-58 AFor each reference object A, the plane is decomposed into 9 tiles, Ai (i=0,8), with A0 the MBR of A.A5A8A7A6A3A2A1A42022-6-5史忠植 高级人工智能54Direction-Relation MatrixDirection-Relation MatrixABCThe direction relation betw

38、een A, B is expressed as a 3*3 Boolean matrix M=(mij), where mij=0 iff Ai is disjoint from B.BABABABABABABABABAABR876504321),(2022-6-5史忠植 高级人工智能55Reasoning with q-CalculiReasoning with q-CalculilConstraintslGiven a q-calclus R, and a relation r in R, (x r y) express a constraint between two variable

39、s x and ylCompositionlGiven two constraints (x r y) & (y s z), we want to know the strongest relation t s.t. (x t z) is possiblelt is called the weak composition of r and s2022-6-5史忠植 高级人工智能56Reasoning with q-CalculiReasoning with q-CalculilGiven a constraint networkN=xi rij xj,is N satisfiable? Thi

40、s is the satisfaction problem.lFor S a subset of the whole algebra, we write RSAT(S) for the problem of deciding satisfaction of networks with constraints over S.2022-6-5史忠植 高级人工智能57Reasoning with q-CalculiReasoning with q-CalculilThe satisfaction problems are often NP hard, e.g. RSAT(IA) and RSAT(R

41、CC8) are NPClReasoning problems in IA and RCC8 have been investigated thoroughly, and many useful techniques have been developed.2022-6-5史忠植 高级人工智能58lLocal constraint solving techniques may be useful, e.g. path-consistency algorithm (PCA) can solve RSAT(S) if S is the maximal tractable subalgebra of

42、 IAReasoning with q-Calculi2022-6-5史忠植 高级人工智能59几何空间定性推理几何空间定性推理空间逻辑的基础在于假设一个原语性的二元关系空间逻辑的基础在于假设一个原语性的二元关系 C(x,y)。其中。其中x,y表示两个区域表示两个区域(regiong), 谓词谓词C表示共享一个以上公共点。也就是表示共享一个以上公共点。也就是指相接触指相接触,它具有自反性、对称性。它具有自反性、对称性。 1. 八个基本关系的定义八个基本关系的定义 使用关系使用关系C(x,y), 一组基本的二元关系可以被定义为：一组基本的二元关系可以被定义为： (1) DC(x,y): 表示两区域

43、不相接触。表示两区域不相接触。 (2) EC(x,y): 表示两区域外部接触。表示两区域外部接触。 (3) PO(x,y): 表示两区域部分覆盖。表示两区域部分覆盖。2022-6-5史忠植 高级人工智能60几何空间定性推理几何空间定性推理 (4) =(x,y): 表示两区域完全相同。表示两区域完全相同。 (5) TPP(x,y): 表示表示$x$是是$y$的一个严格部分并且的一个严格部分并且$x,y$相切相切(内内切切)。 (6) NTPP(x,y): 表示表示$x$是是$y$的一个严格部分但的一个严格部分但$x,y$不相接触不相接触(包含而不相切包含而不相切)。 (7) TPP(x,y):

44、表示表示$y$是是$x$的一个严格部分并且的一个严格部分并且$x,y$相切。相切。 (8) TPP(x,y): 表示表示$y$是是$x$的一个严格部分但的一个严格部分但$x,y$不相切接触。不相切接触。2022-6-5史忠植 高级人工智能61几何空间定性推理几何空间定性推理基本关系间的联系基本关系间的联系这种空间逻辑与这种空间逻辑与Allen的逻辑相类似的逻辑相类似, 也使用预计算的传递性也使用预计算的传递性表来表示二元关系之间可能的变化联系表来表示二元关系之间可能的变化联系, 在表中从任一关系在表中从任一关系R3(a,c)可查找出所有可能的二元关系可查找出所有可能的二元关系R1(a,b)与与

45、R2(b,c)。这。这一表对定性仿真是很有用的。然而一表对定性仿真是很有用的。然而,近年的研究中尚未给出近年的研究中尚未给出这类传递性表的建立算法。但这类传递性表的建立算法。但Randell提到在其仿真程序中提到在其仿真程序中使用了该表来检验展望过程中状态描述的一致性。使用了该表来检验展望过程中状态描述的一致性。2022-6-5史忠植 高级人工智能62几何空间定性推理几何空间定性推理基本状态间的相互转换基本状态间的相互转换 根据两个区域的形状不同根据两个区域的形状不同,上述八个基本关系可被分为上述八个基本关系可被分为6个子集个子集: (1) DC EC PO = (2) DC EC PO TP

46、P (3) DC EC PO TPP-1 (4) DC EC PO TPP NTPP (5) DC EC PO TPP-1 NTPP-1 (6) DC EC PO2022-6-5史忠植 高级人工智能63几何空间定性推理几何空间定性推理空间时间关系描述空间时间关系描述 1.方位性状态和运动性状态方位性状态和运动性状态 Galton 将八个将八个RCC 关系分为方位性状态关系分为方位性状态(position state)和运动和运动性状态性状态(motion state)，并且使用，并且使用Allen 关于时间关系的一些逻辑化关于时间关系的一些逻辑化的形式的形式, 给出了这种分类的定义。首先介绍一

47、下给出了这种分类的定义。首先介绍一下Galton使用的概念、使用的概念、谓词和函数。谓词和函数。 (1) 对时间的描述分为区间和时刻对时间的描述分为区间和时刻; (2) 状态存在的描述谓词状态存在的描述谓词: Holds-on(s,i) 表示在区间表示在区间i上存在状态上存在状态s;Holds-at(s,t) 表示在时刻表示在时刻t存在状态存在状态s; (3) 谓词谓词 Div(t,i) 表示时刻表示时刻t在区间在区间i上上; (4) 函数函数inf(i)表示在区间表示在区间i的开始时刻的开始时刻; (5) 函数函数sup(i)表示在区间表示在区间i的结束时刻的结束时刻;2022-6-5史忠植

48、 高级人工智能64几何空间定性推理几何空间定性推理空间时间关系描述空间时间关系描述方位性状态。方位性状态。 如果状态如果状态s满足满足 i (Holds-on(s,i) Holds-at(s,inf(i) Holds-at(s,sup(i)即如果一个状态即如果一个状态s在时间区间在时间区间i上存在上存在, 则在该区间的起止时刻则在该区间的起止时刻这个状态都存在。具有这一性质的状态称为方位性状态。这个状态都存在。具有这一性质的状态称为方位性状态。 2022-6-5史忠植 高级人工智能65几何空间定性推理几何空间定性推理空间时间关系描述空间时间关系描述运动性状态。如果状态运动性状态。如果状态s满足

49、满足t (Holds-on(s,t) i (Div(t,i) Holds-on(s,i)即如果在某时刻即如果在某时刻t有状态有状态s, 那么一定存在包含这一时刻的某那么一定存在包含这一时刻的某一区间使一区间使$s$在整个区间都存在在整个区间都存在, 具有这一性质的状态称为具有这一性质的状态称为运动性状态。运动性状态。2022-6-5史忠植 高级人工智能66几何空间定性推理几何空间定性推理空间时间关系描述空间时间关系描述 扰动原理扰动原理 Galton根据这种分类给出了扰动原理根据这种分类给出了扰动原理, 这是对空间状态在时域变这是对空间状态在时域变化进行描述的一组公理体系：化进行描述的一组公理

50、体系： 定义定义 4.5 扰动扰动(perturbation)。如果。如果RCC关系关系R与与R满足条件满足条件: t(Holds-at(R(a,b),t)(i(Holds-on(R(a,b),i) (inf(i)=t) (sup(i)=t)即如果时刻即如果时刻t有状态有状态R,且有一个区间且有一个区间i开始或结束于开始或结束于t区间区间i上的状态上的状态为为R。此时称。此时称R与与R 互为扰动。互为扰动。 扰动原理扰动原理: 每个每个RCC关系是它自身的扰动关系是它自身的扰动, 另外一个静止性的状另外一个静止性的状态只能与一个运动性的状态互扰动态只能与一个运动性的状态互扰动, 反之亦然反之亦