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

定性推理定性推理史忠植史忠植中国科学院计算技术研究所中国科学院计算技术研究所高级人工智能高级人工智能第四章定性推理史忠植高级人工智能2024/8/7史忠植 高级人工智能2内容提要内容提要4.1 概述概述4.2 定性推理的基本方法定性推理的基本方法4.3 定性模型推理定性模型推理 4.4 定性进程推理定性进程推理 4.5 定性仿真推理定性仿真推理4.6 代数方法代数方法4.7 几何空间定性推理几何空间定性推理2023/8/20史忠植 高级人工智能2内容提要4.1 概什么是定性推理？什么是定性推理？定定 性性 推推 理理(qualitativereasoning)是是 从从 物物 理理 系系统统、生生 命命 系系 统统 的的 结结 构构 描描 述述 出出 发发,导导 出出 行行 为为 描描 述述,以以便便预预测测系系统统的的行行为为并并给给出出原原因因解解释释。定定性性推推理理采采用用系系统统部部件件间间的的局局部部结结构构规规则则来来解解释释系系统统行行为为,即即部部件件状状态态的的变变化化行行为为只只与与直直接接相相邻邻的的部部件件有有关关。什么是定性推理？定性推理(qualitative 2024/8/7史忠植 高级人工智能4 概述概述1952年年 Simmons提出定性分析的因果关系。提出定性分析的因果关系。1977年年 Rieger 发表了因果仿真的论文。发表了因果仿真的论文。1984年年 “Artificial Intelligence”杂志第杂志第24卷出版了定性推理专辑卷出版了定性推理专辑,刊载了刊载了 de Kleer,Forbus 和和Kuipers对定性推理奠基性的对定性推理奠基性的 文章文章,这标志着定性推理开始走向成熟。这标志着定性推理开始走向成熟。1986年年 Iwasaki和和Simmons发表了发表了“Causality in Device Behavior”的文章。的文章。1993年年 “Artificial Intelligence”杂志第杂志第59卷又发表了一组文章，卷又发表了一组文章，回顾十年前这几位定性推理奠基人所做的工作。回顾十年前这几位定性推理奠基人所做的工作。2023/8/20史忠植 高级人工智能4 概述1952年 2024/8/7史忠植 高级人工智能5 概述概述de Kleer的定性模型方法的定性模型方法de Kleer 1984Forbus的定性进程方法的定性进程方法Forbus 1984Kuipers 定性仿真法定性仿真法Kuipers 19842023/8/20史忠植 高级人工智能5 概述de Kle2024/8/7史忠植 高级人工智能6 概述概述Davis 提出从结构描述出发进行故障论断的方法提出从结构描述出发进行故障论断的方法Reiler提出从基本原理出发进行故障诊断的方法提出从基本原理出发进行故障诊断的方法Williams把定量运算和定性推理相结合建立了一个把定量运算和定性推理相结合建立了一个 混合代数系统混合代数系统Q1Iwasaki 和和 Simmons把经济学、热力学中所用的因果把经济学、热力学中所用的因果 关系形式化关系形式化Weld在分子生物学中设计了定性模拟程序在分子生物学中设计了定性模拟程序 2023/8/20史忠植 高级人工智能6 概述2024/8/7史忠植 高级人工智能7定性推理的基本方法定性推理的基本方法 人类对物理世界的描述、解释人类对物理世界的描述、解释,常是以某种直观的定性常是以某种直观的定性方法进行的方法进行的,很少使用微分方程及具体的数值描述很少使用微分方程及具体的数值描述,如如人们在骑自行车时人们在骑自行车时,为了避免摔倒和撞车为了避免摔倒和撞车,并不需要使用并不需要使用书本上的运动方程书本上的运动方程,而是针对几个主要参量的变化趋势而是针对几个主要参量的变化趋势给予粗略的、直观的给予粗略的、直观的,但大体上准确的描述但大体上准确的描述,这就够了。这就够了。2023/8/20史忠植 高级人工智能7定性推理的基本方法2024/8/7史忠植 高级人工智能8定性推理的基本方法定性推理的基本方法 一般分析运动系统行为的标准过程可分为三个步骤：一般分析运动系统行为的标准过程可分为三个步骤：(1)决定描述对象系统特征的量。决定描述对象系统特征的量。(2)用方程式表示量之间的相互关系。用方程式表示量之间的相互关系。(3)分析方程式，得到数值解。分析方程式，得到数值解。2023/8/20史忠植 高级人工智能8定性推理的基本方法2024/8/7史忠植 高级人工智能9定性推理的基本方法定性推理的基本方法这类运动系统行为的问题用计算机进行求解时，这类运动系统行为的问题用计算机进行求解时，将面临如下三个问题：将面临如下三个问题：(1)步骤步骤(1)(2)需要相当多的知识，并且要有相应的需要相当多的知识，并且要有相应的算法。算法。(2)有的场合对象系统的性质很难用数学式子表示。有的场合对象系统的性质很难用数学式子表示。(3)步骤步骤(3)得到了数值解，但是对象系统的行为并得到了数值解，但是对象系统的行为并不直观明了。不直观明了。2023/8/20史忠植 高级人工智能9定性推理的基本方法2024/8/7史忠植 高级人工智能10定性推理的基本方法定性推理的基本方法为了解决第二、第三个问题，定性推理一般采用下列分析步骤：为了解决第二、第三个问题，定性推理一般采用下列分析步骤：(1)结构认识：将对象系统分解成部件的组合。结构认识：将对象系统分解成部件的组合。(2)因果分析：当输入值变化时，分析对象系统中怎样传播。因果分析：当输入值变化时，分析对象系统中怎样传播。(3)行为推理：输入值随着时间变化，分析对象系统的内部状行为推理：输入值随着时间变化，分析对象系统的内部状态怎样变化。态怎样变化。(4)功能说明：行为推理的结果表明对象系统的行为，由此可功能说明：行为推理的结果表明对象系统的行为，由此可以说明对象系统的功能。以说明对象系统的功能。2023/8/20史忠植 高级人工智能10定性推理的基本方2024/8/7史忠植 高级人工智能11定性推理的基本方法定性推理的基本方法定性推理的观点大体上可这样来理解定性推理的观点大体上可这样来理解:忽略被描述对象的次要因素忽略被描述对象的次要因素,掌握主要因素简化问题的描述。掌握主要因素简化问题的描述。将随时间将随时间 t连续变化的参量连续变化的参量 x(t)的值域离散化为定性值集合的值域离散化为定性值集合,通常变量通常变量 x的定性值的定性值 x定义为定义为 依物理规律将微分方程转换成定性依物理规律将微分方程转换成定性(代数代数)方程方程,或直接依物理或直接依物理 规律建立定性模拟或给出定性进程描述。规律建立定性模拟或给出定性进程描述。最后给出定性解释最后给出定性解释2023/8/20史忠植 高级人工智能11定性推理的基本方2024/8/7史忠植 高级人工智能12定性模型推理定性模型推理de Kleerde Kleer研究解决经典物理问题需要哪些知识及如何研究解决经典物理问题需要哪些知识及如何建立问题求解系统。他提出的定性模型方法所涉及建立问题求解系统。他提出的定性模型方法所涉及的物理系统是由管子、阀门、容器等装置组成的物理系统是由管子、阀门、容器等装置组成,约束约束条件条件(定性方程定性方程)反映在这些装置的连接处反映在这些装置的连接处,依定性方依定性方程给出定性解释。程给出定性解释。为将代数方程、微分方程定性化为将代数方程、微分方程定性化,首先需定义变首先需定义变量的定性值集合以及相应的定性运算。量的定性值集合以及相应的定性运算。2023/8/20史忠植 高级人工智能12定性模型推理2024/8/7史忠植 高级人工智能13定性模型推理定性模型推理定性值集合是一个离散集合定性值集合是一个离散集合,其元素是由对数轴的划分而得到的其元素是由对数轴的划分而得到的,通常把数轴通常把数轴(,)划分成划分成(,0),0,(0,)三段三段,规定定性值规定定性值集合为集合为,0,变量变量 x的定性值的定性值 x如下定义如下定义:另外用 x表示 dx/dt的定性值,也即2023/8/20史忠植 高级人工智能13定性模型推理另外2024/8/7史忠植 高级人工智能14定性模型推理定性模型推理 xy-0+-?0-0+?+x y x y-0+-+0-0000+-0+x y 其中:符号？表示不确定或无定义。2023/8/20史忠植 高级人工智能14定性模型推理 2024/8/7史忠植 高级人工智能15定性模型推理定性模型推理下面给出和 的运算规则。设 e1,e2是公式,则有：0 e1e10 e10+e1e1-e1-e12023/8/20史忠植 高级人工智能15定性模型推理02024/8/7史忠植 高级人工智能16定性模型推理定性模型推理使用下列规则，可将运算符使用下列规则，可将运算符+、转换成转换成、：e1e2 e1 e2e1e2 e1 e22023/8/20史忠植 高级人工智能16定性模型推理 2024/8/7史忠植 高级人工智能17压力调节器压力调节器压力调节器是通过弹簧来控制阀门流量压力调节器是通过弹簧来控制阀门流量,以使流量为某以使流量为某一设定值而不受流入的流量和负载变化的影响。根据一设定值而不受流入的流量和负载变化的影响。根据物理学有物理学有2023/8/20史忠植 高级人工智能17压力调节器压力调2024/8/7史忠植 高级人工智能18压力调节器压力调节器其中其中 Q是通过阀门的流量是通过阀门的流量,P是压力是压力,A是阀门开启的面是阀门开启的面积积,而而C是常系数是常系数,是流体的质量密度。按照运算和转是流体的质量密度。按照运算和转换规则而得到定性方程：换规则而得到定性方程：Q=PQ=A+P (如果A 0)2023/8/20史忠植 高级人工智能18压力调节器其中 2024/8/7史忠植 高级人工智能19压力调节器压力调节器OPEN状态A=Amax定性方程P=0P=0WORKING 状态0A Atemperature(dst)src 温度高于dst温度2023/8/20史忠植 高级人工智能25定性进程推理 P2024/8/7史忠植 高级人工智能26定性进程推理定性进程推理 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的值直接影响 heat(dst),而且是正影响2023/8/20史忠植 高级人工智能26定性进程推理 R2024/8/7史忠植 高级人工智能27定性进程推理定性进程推理演绎过程演绎过程 在进程定性推理中，其演绎过程如下：在进程定性推理中，其演绎过程如下：(1)选进程。选进程。对一组已知的个体来说对一组已知的个体来说,在进程表中依各进程对个在进程表中依各进程对个体的说明找出可能出现的那些进程例体的说明找出可能出现的那些进程例PI。(2)确定激活的确定激活的 PI。依前提条件、数量条件确定每个。依前提条件、数量条件确定每个 PI的状态。的状态。满足这些条件的为激活的满足这些条件的为激活的 PI,激活的激活的 PI 叫进程结构。叫进程结构。(3)确定量的变化。确定量的变化。个体的变化由相应量的个体的变化由相应量的 Ds 值来表示。量的值来表示。量的变化可由进程直接影响，也可由变化可由进程直接影响，也可由Q间接影响。间接影响。(4)确定进程结构变化。量的变化将会引起进程结构的变化确定进程结构变化。量的变化将会引起进程结构的变化,确确定这种变化也叫限制分析定这种变化也叫限制分析,这样对一个物理过程的描述便由这样对一个物理过程的描述便由 (1)建建立的立的 PI 进入了下一个进入了下一个 PI。重复重复(1)(4)的步骤便可给出一个物理过程的一串进程描述。的步骤便可给出一个物理过程的一串进程描述。2023/8/20史忠植 高级人工智能27定性进程推理演绎2024/8/7史忠植 高级人工智能28定性进程推理定性进程推理2023/8/20史忠植 高级人工智能28定性进程推理2024/8/7史忠植 高级人工智能29定性仿真推理定性仿真推理 1984年年 Kuipers 发表了发表了“因果性的常识推理：从结构导出因果性的常识推理：从结构导出行为行为”论文。这篇论文建立了一种定性仿真推理的框架论文。这篇论文建立了一种定性仿真推理的框架,简单地给出了从常微分方程的抽象而得的定性结构和定性简单地给出了从常微分方程的抽象而得的定性结构和定性行为表示方法。随后，行为表示方法。随后，1986年年AI杂志又刊登了杂志又刊登了Kuipers“定性仿真定性仿真”一文，文中明确了抽象关系，提出用于定性一文，文中明确了抽象关系，提出用于定性仿真的仿真的QSIM算法，并用抽象关系证明了其有效性和不算法，并用抽象关系证明了其有效性和不完备性。这两篇文章奠定了定性仿真的基础。演绎过程完备性。这两篇文章奠定了定性仿真的基础。演绎过程 2023/8/20史忠植 高级人工智能29定性仿真推理 12024/8/7史忠植 高级人工智能30定性仿真推理定性仿真推理 定性仿真是从结构的定性描述出发来导出行为描述。直接用定性仿真是从结构的定性描述出发来导出行为描述。直接用部件的参量作为状态变量来描述物理结构部件的参量作为状态变量来描述物理结构,定性约束直接由定性约束直接由物理规律得到物理规律得到,把一个参量随时间的变化视作定性的状态序列把一个参量随时间的变化视作定性的状态序列,求解算法是从初始状态出发求解算法是从初始状态出发,生成各种可能的后续状态生成各种可能的后续状态,进而进而通过一致性过滤通过一致性过滤,重复该过程直到没有新状态出现。重复该过程直到没有新状态出现。定性仿真结构描述由系统的状态参数和约束关系组成。认为定性仿真结构描述由系统的状态参数和约束关系组成。认为参数是时间的可微函数参数是时间的可微函数,约束是参数间的二元或多元关系。如约束是参数间的二元或多元关系。如速度的导数是加速度。表为速度的导数是加速度。表为 DERIV(Vel,acc)。f=ma 表为表为 MULT(m,a,f),f 随随 g单调增加表为单调增加表为 M+(f,g),f 随随 g单调减少单调减少,表表为为 M-(f,g)。2023/8/20史忠植 高级人工智能30定性仿真推理 2024/8/7史忠植 高级人工智能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)规定为有序对规定为有序对,定义如下定义如下:2023/8/20史忠植 高级人工智能31定性仿真推理行为2024/8/7史忠植 高级人工智能32定性仿真推理定性仿真推理2023/8/20史忠植 高级人工智能32定性仿真推理2024/8/7史忠植 高级人工智能33定性仿真推理定性仿真推理 定义定义 4.2 设设 ti,ti+1是相邻的区分点是相邻的区分点,规定规定 f在在(ti,ti+1)内的内的定性状态定性状态 QS(f,ti,ti+1)仍为仍为 QS(f,t)其中 t(ti,ti+1)2023/8/20史忠植 高级人工智能33定性仿真推理 定2024/8/7史忠植 高级人工智能34定性仿真推理定性仿真推理定义定义 4.3 f 在在 a,b上的定性行为是上的定性行为是f的定性状态序列的定性状态序列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 区分点并集的元素。区分点并集的元素。2023/8/20史忠植 高级人工智能34定性仿真推理定义2024/8/7史忠植 高级人工智能35定性仿真推理定性仿真推理定性状态转换定性状态转换 在定性仿真中，定性状态转移是经常遇到的。假设在定性仿真中，定性状态转移是经常遇到的。假设 f是是可微函数可微函数,f从一个定性状态转换到另一个定性状态必须遵守从一个定性状态转换到另一个定性状态必须遵守介值定理和中值定理。定性状态转换有两类：一类是介值定理和中值定理。定性状态转换有两类：一类是P 转转换，该类转换是从时间点到时间区间；另一类是换，该类转换是从时间点到时间区间；另一类是I 转换，转换，它是从时间区间到时间点的转换。下面给出转换表它是从时间区间到时间点的转换。下面给出转换表:2023/8/20史忠植 高级人工智能35定性仿真推理定性2024/8/7史忠植 高级人工智能36定性仿真推理定性仿真推理P转换QS(f,ti)QS(f,ti,ti+1)P1P2P3P4P5P6P72023/8/20史忠植 高级人工智能36定性仿真推理P转2024/8/7史忠植 高级人工智能37定性仿真推理定性仿真推理I 转换QS(f,ti,ti+1)QS(f,ti+1)I1I2I3I4I5I6I7I8I92023/8/20史忠植 高级人工智能37定性仿真推理I 2024/8/7史忠植 高级人工智能38定性仿真推理定性仿真推理 QSIM算法可对系统的行为进行定性仿真。首先将初始状态送入算法可对系统的行为进行定性仿真。首先将初始状态送入 ACTIVE表中表中,然后重复然后重复(1)(6)直至直至 ACTIVE 表空为止。表空为止。算法算法 4.1 QSIM算法。算法。(1)从从 ACTIVE表中选一状态。表中选一状态。(2)对每个参数按转换表找出所有可能的转换。对每个参数按转换表找出所有可能的转换。(3)对约束中变元的转换生成二元组对约束中变元的转换生成二元组,三元组集合三元组集合,依约束关系依约束关系做一致性滤波。做一致性滤波。(4)对有公共变元的约束对有公共变元的约束,对元组进行组对对元组进行组对,再对组对的元组做再对组对的元组做一致性滤波。一致性滤波。2023/8/20史忠植 高级人工智能38定性仿真推理 Q2024/8/7史忠植 高级人工智能39定性仿真推理定性仿真推理(5)从剩下的元组生成所有可能的全局解释。每个解释生成从剩下的元组生成所有可能的全局解释。每个解释生成 一个新状态作为当前状态的后继状态。一个新状态作为当前状态的后继状态。(6)对新状态做全局滤波对新状态做全局滤波,剩下的状态送入剩下的状态送入 ACTIVE 表。全局表。全局 滤波排除下列状态：滤波排除下列状态：无变化情形无变化情形:如如 I1,I4,I7;循环情形循环情形:新状态与某个前辈状态相同新状态与某个前辈状态相同;发散情形发散情形:某参数值为某参数值为,这时当前时间点必为结束点。这时当前时间点必为结束点。2023/8/20史忠植 高级人工智能39定性仿真推理(52024/8/7史忠植 高级人工智能40几何空间定性推理几何空间定性推理空间定性推理是对几何形状或者运动性质进行定性推理，空间定性推理是对几何形状或者运动性质进行定性推理，首先需对空间位置及运动方式进行定性表示，进而对几何首先需对空间位置及运动方式进行定性表示，进而对几何形状及运动性质进行推理研究及预测分析，并作出逻辑解形状及运动性质进行推理研究及预测分析，并作出逻辑解释。空间定性推理是通过定义一组空间并寻找这些关系间释。空间定性推理是通过定义一组空间并寻找这些关系间的联系来进行的。目前主要的研究是针对空间定性建模方的联系来进行的。目前主要的研究是针对空间定性建模方式、式、空间形状及关系的定性表示和定性技术的形式化等空间形状及关系的定性表示和定性技术的形式化等,产生解释理论产生解释理论,但总体来看与解决工程问题距离尚远。但总体来看与解决工程问题距离尚远。2023/8/20史忠植 高级人工智能40几何空间定性推理2024/8/7史忠植 高级人工智能41几何空间定性推理几何空间定性推理将将Allen的时态逻辑的时态逻辑Allen 1984与与Randall的空间逻辑的空间逻辑Randall 1992结合起来，形成空间、时间、连续运动的结合起来，形成空间、时间、连续运动的表达逻辑。表达逻辑。另外从空间定性推理派生出空间规划理论另外从空间定性推理派生出空间规划理论,可用于为一组可用于为一组几何对象寻找满足一组约束的分布设计几何对象寻找满足一组约束的分布设计,有关方法主要用于有关方法主要用于设计自动化、定性建模等领域。设计自动化、定性建模等领域。在这一领域已取得了一些在这一领域已取得了一些较有实际意义的成果较有实际意义的成果,如约束满足问题如约束满足问题(CSP)求解理论求解理论,而实而实际上很多空间定性规划都是一个几何约束满足问题际上很多空间定性规划都是一个几何约束满足问题(GCSP)。2023/8/20史忠植 高级人工智能41几何空间定性推理2024/8/7史忠植 高级人工智能42几何空间定性推理几何空间定性推理1992年由年由Randell等人建立起来的等人建立起来的RCC 空间时间逻辑是用于空间时间逻辑是用于对空间问题进行可达性的展望对空间问题进行可达性的展望,并已程序实现。与并已程序实现。与Kuipers的的QSIM方法类似方法类似,基于基于RCC 逻辑的仿真算法也是从对系统进逻辑的仿真算法也是从对系统进行结构性的描述开始的行结构性的描述开始的,系统将初始状态作为生成树的根系统将初始状态作为生成树的根结点结点,可能的行为则是树中从根结点到叶结点的路径。可能的行为则是树中从根结点到叶结点的路径。2023/8/20史忠植 高级人工智能42几何空间定性推理2024/8/7史忠植 高级人工智能43QualitativeSpatialReasoningQualitativereasoningmodellingthecontinuousrealityinmanageableentitiessolutionforquantitativeproblemsthatarenotcomputableTwoapproachesartificialintelligenceGIScience1992Randell,Cui,CohndatabasesGISystems1991Egenhofer,FranzosaGISRUK2004UniversityofEastAngliaSlide5of20几何空间定性推理几何空间定性推理2023/8/20史忠植 高级人工智能43Qualitat2024/8/7史忠植 高级人工智能44RCCRCC=Region Connection CalculusRandell,Cui,Cohntopological relations of polygonsqualitative modellingdisjoint,meet,overlapconceptual neighbourhood-diagramGISRUK2004UniversityofEastAngliaSlide6of20RCC几何空间定性推理几何空间定性推理2023/8/20史忠植 高级人工智能44RCCRCC=2024/8/7史忠植 高级人工智能45RCC-diagramGISRUK2004UniversityofEastAngliaSlide7of20Conceptualneighbourhooddiagram几何空间定性推理几何空间定性推理2023/8/20史忠植 高级人工智能45RCC-diQualitative CalculilThesuccessofqualitativereasoningreliesonchoiceofgoodqualitativecalculilAq-calculusisgeneratedbyasetofjointlyexhaustiveandpairwisedisjoint(JEPD)relationsonthedomainofdiscourseQualitative Calculi The succes2024/8/7史忠植 高级人工智能47RCC8 Topological AlgebralRegionsarenonemptyregularclosedsubsetsofaconnectedregulartopologicalspace(e.g.Euclideanspace)lBasicRCC8relationsaredefinedonregions2023/8/20史忠植 高级人工智能47RCC8 Top2024/8/7史忠植 高级人工智能48RCC8 Basic Relations DC EC PO TPP NTPP EQdisjoint meet overlap covered_by contained_by equalBABABABAA=BBA2023/8/20史忠植 高级人工智能48RCC8 Bas2024/8/7史忠植 高级人工智能49Directional ModellPoint-basedlProjection-basedlCone-basedlRegion-basedRectangle AlgebraDirection-Relation Matix Model2023/8/20史忠植 高级人工智能49Directio2024/8/7史忠植 高级人工智能50Cone-Based Cardinal DirectionslFrank AU.Qualitative spatial reasoning:Cardinal directions as an example.IJGIS,1996,10:269290 2023/8/20史忠植 高级人工智能50Cone-Bas2024/8/7史忠植 高级人工智能51Projection-BasedCard.DirectionslFrank AU.Qualitative spatial reasoning:Cardinal directions as an example.IJGIS,1996,10:2692902023/8/20史忠植 高级人工智能51Projecti2024/8/7史忠植 高级人工智能52Rectangle 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)B2023/8/20史忠植 高级人工智能52Rectangl2024/8/7史忠植 高级人工智能53Direction-Relation MatrixlR.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.A5A8A7A6A3A2A1A42023/8/20史忠植 高级人工智能53Directio2024/8/7史忠植 高级人工智能54Direction-Relation MatrixABCThe direction relation between A,B is expressed as a 3*3 Boolean matrix M=(mij),where mij=0 iff Ai is disjoint from B.2023/8/20史忠植 高级人工智能54Directio2024/8/7史忠植 高级人工智能55Reasoning with q-CalculilConstraintslGiven a q-calclus R,and a relation r in R,(x r y)express a constraint between two variables 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 s2023/8/20史忠植 高级人工智能55Reasonin2024/8/7史忠植 高级人工智能56Reasoning with q-CalculilGiven a constraint networkN=xi rij xj,is N satisfiable?This 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.2023/8/20史忠植 高级人工智能56Reasonin2024/8/7史忠植 高级人工智能57Reasoning with q-CalculilThe satisfaction problems are often NP hard,e.g.RSAT(IA)and RSAT(RCC8)are NPClReasoning problems in IA and RCC8 have been investigated thoroughly,and many useful techniques have been developed.2023/8/20史忠植 高级人工智能57Reasonin2024/8/7史忠植 高级人工智能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 IAReasoningwithq-Calculi2023/8/20史忠植 高级人工智能58Local co2024/8/7史忠植 高级人工智能59几何空间定性推理几何空间定性推理空间逻辑的基础在于假设一个原语性的二元关系空间逻辑的基础在于假设一个原语性的二元关系 C(x,y)。其中。其中x,y表示两个区域表示两个区域(regiong),谓词谓词C表示共享一个以上公共点。也就是表示共享一个以上公共点。也就是指相接触指相接触,它具有自反性、对称性。它具有自反性、对称性。1.八个基本关系的定义八个基本关系的定义 使用关系使用关系C(x,y),一组基本的二元关系可以被定义为：一组基本的二元关系可以被定义为：(1)DC(x,y):表示两区域不相接触。表示两区域不相接触。(2)EC(x,y):表示两区域外部接触。表示两区域外部接触。(3)PO(x,y):表示两区域部分覆盖。表示两区域部分覆盖。2023/8/20史忠植 高级人工智能59几何空间定性推理2024/8/7史忠植 高级人工智能60几何空间定性推理几何空间定性推理 (4)=(x,y):表示两区域完全相同。表示两区域完全相同。(5)TPP(x,y):表示表示$x$是是$y$的一个严格部分并且的一个严格部分并且$x,y$相切相切(内切内切)。(6)NTPP(x,y):表示表示$x$是是$y$的一个严格部分但的一个严格部分但$x,y$不相接触不相接触(包含而不相切包含而不相切)。(7)TPP(x,y):表示表示$y$是是$x$的一个严格部分并且的一个严格部分并且$x,y$相切。相切。(8)TPP(x,y):表示表示$y$是是$x$的一个严格部分但的一个严格部分但$x,y$不相切接触。不相切接触。2023/8/20史忠植 高级人工智能60几何空间定性推理2024/8/7史忠植 高级人工智能61几何空间定性推理几何空间定性推理基本关系间的联系基本关系间的联系这种空间逻辑与这种空间逻辑与Allen的逻辑相类似的逻辑相类似,也使用预计算的传递性也使用预计算的传递性表来表示二元关系之间可能的变化联系表来表示二元关系之间可能的变化联系,在表中从任一关系在表中从任一关系R3(a,c)可查找出所有可能的二元关系可查找出所有可能的二元关系R1(a,b)与与R2(b,c)。这。这一表对定性仿真是很有用的。然而一表对定性仿真是很有用的。然而,近年的研究中尚未给出近年的研究中尚未给出这类传递性表的建立算法。但这类传递性表的建立算法。但Randell提到在其仿真程序中提到在其仿真程序中使用了该表来检验展望过程中状态描述的一致性。使用了该表来检验展望过程中状态描述的一致性。2023/8/20史忠植 高级人工智能61几何空间定性推理2024/8/7史忠植 高级人工智能62几何空间定性推理几何空间定性推理基本状态间的相互转换基本状态间的相互转换 根据两个区域的形状不同根据两个区域的形状不同,上述八个基本关系可被分为上述八个基本关系可被分为6个子集个子集:(1)DC EC PO =(2)DC EC PO TPP (3)DC EC PO TPP-1 (4)DC EC PO TPP NTPP (5)DC EC PO TPP-1 NTPP-1 (6)DC EC PO2023/8/20史忠植 高级人工智能62几何空间定性推理2024/8/7史忠植 高级人工智能63几何空间定性推理几何空间定性推理空间时间关系描述空间时间关系描述 1.方位性状态和运动性状态方位性状态和运动性状态 Galton 将八个将八个RCC 关系分为方位性状态关系分为方位性状态(position state)和运动和运动性状态性状态(motion state)，并且使用，并且使用Allen 关于时间关系的一些逻辑化关于时间关系的一些逻辑化的形式的形式,给出了这种分类的定义。首先介绍一下给出了这种分类的定义。首先介绍一下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的结束时刻的结束时刻;2023/8/20史忠植 高级人工智能63几何空间定性推理2024/8/7史忠植 高级人工智能64几何空间定性推理几何空间定性推理空间时间关系描述空间时间关系描述方位性状态。方位性状态。如果状态如果状态s满足满足 i(Holds-on(s,i)Holds-at(s,inf(i)Holds-at(s,sup(i)即如果一个状态即如果一个状态s在时间区间在时间区间i上存在上存在,则在该区间的起止时刻则在该区间的起止时刻这个状态都存在。具有这一性质的状态称为方位性状态。这个状态都存在。具有这一性质的状态称为方位性状态。2023/8/20史忠植 高级人工智能64几何空间定性推理2024/8/7史忠植 高级人工智能65几何空间定性推理几何空间定性推理空间时间关系描述空间时间关系描述运动性状态。如果状态运动性状态。如果状态s满足满足t(Holds-on(s,t)i(Div(t,i)Holds-on(s,i)即如果在某时刻即如果在某时刻t有状态有状态s,那么一定存在包含这一时刻的某那么一定存在包含这一时刻的某一区间使一区间使$s$在整个区间都存在在整个区间都存在,具有这一性质的状态称为具有这一性质的状态称为运动性状态。运动性状态。2023/8/20史忠植 高级人工智能65几何空间定性推理2024/8/7史忠植 高级人工智能66几何空间定性推理几何空间定性推理空间时间关系描述空间时间关系描述 扰动原理扰动原理 Galton根据这种分类给出了扰动原理根据这种分类给出了扰动原理,这是对空间状态在时域变这是对空间状态在时域变化进行描述的一组公理体系：化进行描述的一组公理体系：定义定义 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关系是它自身的扰动关系是它自身的扰动,另外一个静止性的状另外一个静止性的状态只能与一个运动性的状态互扰动态只能与一个运动性的状态互扰动,反之亦然反之亦然(只讨论刚体只讨论刚体)。2023/8/20史忠植 高级人工智能66几何空间定性推理2024/8/7史忠植 高级人工智能67几何空间定性推理几何空间定性推理 Randell算法算法假设初始状态假设初始状态S0 已放入状态集合已放入状态集合S中。中。(1)如果如果S空则停止空则停止;(2)从从S中选出状态中选出状态Si,且移出且移出;(3)如果如果Si 为不一致状态将转为不一致状态将转(2);(4)应用状态约束选择可用变换规则应用状态约束选择可用变换规则;(5)用所选出的规则产生可能的下一个状态集合用所选出的规则产生可能的下一个状态集合;(6)使用添加与删除规则使用添加与删除规则;(7)进行状态内约束检查进行状态内约束检查;(8)将剩下的状态加入将剩下的状态加入S并转并转(1)。2023/8/20史忠植 高级人工智能67几何空间定性推理2024/8/7史忠植 高级人工智能68空间推理的研究进展空间推理的研究进展l对空间推理的许多研究方向进行分类、归纳和整理之后对空间推理的许多研究方向进行分类、归纳和整理之后得到的主要研究方向是：得到的主要研究方向是：(1)空间数据库的精度。空间数据库的精度。(2)空间关系语言。空间关系语言。(3)空间推理与地理信息系统。空间推理与地理信息系统。(4)空间决策支持系统。空间决策支持系统。(5)空间数据的不确定性处理。空间数据的不确定性处理。(6)形式化的绘图知识。形式化的绘图知识。(7)时空推理。时空推理。2023/8/20史忠植 高级人工智能68空间推理的研究进2024/8/7史忠植 高级人工智能69 (8)定性空间推理。定性空间推理。(9)空间推理的用户界面。空间推理的用户界面。(10)基于案例基于案例(CASE-BASED)的空间推理的空间推理.(11)空间推理的认知问题。空间推理的认知问题。(12)空间推理与机器人视觉。空间推理与机器人视觉。(13)常识推理。常识推理。(14)区域连接演算区域连接演算RCC-8。空间推理的研究进展空间推理的研究进展2023/8/20史忠植 高级人工智能69 空间推理的研2024/8/7史忠植 高级人工智能70大量的文献空间推理的研究热点：大量的文献空间推理的研究热点：l时空推理时空推理STSR(spatio-temporal spatial STSR(spatio-temporal spatial reasoning)reasoning)、l定性空间推理定性空间推理QSR(qualitative spatial QSR(qualitative spatial reasoning)reasoning)l地理信息系统地理信息系统空间推理的研究热点空间推理的研究热点2023/8/20史忠植 高级人工智能70大量的文献空间推2024/8/7史忠植 高级人工智能71l时空推理时空推理当今世界是在漫长的历史长河中，历经沧桑演变进化而当今世界是在漫长的历史长河中，历经沧桑演变进化而来的。世界中的任何事物和现象都遵循着诞生、生长，来的。世界中的任何事物和现象都遵循着诞生、生长，直至消失或死亡的自然规律。同样，现代文明和科技的直至消失或死亡的自然规律。同样，现代文明和科技的进步无不是人类历史的经验积累和结晶。人类在认识和进步无不是人类历史的经验积累和结晶。人类在认识和解释当今世界事物和现象时解释当今世界事物和现象时,不但渴望甚至必须了解它们不但渴望甚至必须了解它们的过去的过去,而且希望预测未知的将来而且希望预测未知的将来,以便在必要的时候采以便在必要的时候采取一定措施取一定措施,使人类社会朝着美好的方向发展。在这绵延使人类社会朝着美好的方向发展。在这绵延不断的历史轨迹中，无不打上了时间的烙印，因此不断的历史轨迹中，无不打上了时间的烙印，因此,探索探索适宜的工具和方法适宜的工具和方法,沿着时间脉络研究和推理客观世界内沿着时间脉络研究和推理客观世界内在机制和时空发展规律在机制和时空发展规律,就显得十分重要。就显得十分重要。空间推理的研究热点空间推理的研究热点2023/8/20史忠植 高级人工智能71时空推理空间推理2024/8/7史忠植 高级人工智能72总的来说，影响空间推理结果的因素包括空间因素总的来说，影响空间推理结果的因素包括空间因素和时间因素。所谓时空推理是指在空间推理过程中添加和时间因素。所谓时空推理是指在空间推理过程中添加时间因素。地表、地下和大气等空间对象的状态不仅受时间因素。地表、地下和大气等空间对象的状态不仅受到空间因素的影响到空间因素的影响,同时同时,从一个漫长的时间过程来看，从一个漫长的时间过程来看，也必将受到时间因素的影响。可以说也必将受到时间因素的影响。可以说,时空推理是更为时空推理是更为一般的空间推理一般的空间推理,或者可以说空间推理是时空推理的一或者可以说空间推理是时空推理的一个特例。目前个特例。目前,时空推理方面的研究还处于起步阶段。时空推理方面的研究还处于起步阶段。下面下面,我简单地介绍一些权威学者对时空推理的认识和我简单地介绍一些权威学者对时空推理的认识和他们提出的时空推理模型。他们提出的时空推理模型。空间推理的研究热点空间推理的研究热点2023/8/20史忠植 高级人工智能72空间推理的研究热2024/8/7史忠植 高级人工智能73 1.RichardA.Block在他的论文在他的论文“PsychologicalTimeandtheProcessingofSpatialInformation”中中指出：指出：“与其说空间为时间提供了一个框架，不如说时与其说空间为时间提供了一个框架，不如说时间感知为空间感知提供了一个框架间感知为空间感知提供了一个框架”。“位置和持续时位置和持续时间之间、个人经验和常识之间以及期望和回顾之间存在间之间、个人经验和常识之间以及期望和回顾之间存在重要的区别重要的区别”。他提出了上下文时间模型，。他提出了上下文时间模型，并且把它扩并且把它扩展到空间，展到空间，模型着眼于哪些变量对持续时间和其他种类模型着眼于哪些变量对持续时间和其他种类的时间体验之间及行为和判断之间的相互作用有影响，的时间体验之间及行为和判断之间的相互作用有影响，这些变量包括实验者的特征、时间周期、时间周期上的这些变量包括实验者的特征、时间周期、时间周期上的活动和时间行为。活动和时间行为。空间推理的研究热点空间推理的研究热点2023/8/20史忠植 高级人工智能73空间推理的研究热2024/8/7史忠植 高级人工智能742.A.G.Cohn,Z.Cui,D.A.Randell在他们的论在他们的论文文“ExploitingTemporalContinuityinQualitativeSpatialCalculus”中提出了一个空间知识中提出了一个空间知识推理的逻辑框架推理的逻辑框架,目的是为人工智能系统的表示和推理目的是为人工智能系统的表示和推理提供一个形式上的时间和空间的公理理论。提供一个形式上的时间和空间的公理理论。他们的形式他们的形式方法可以用于时间或空间区域方法可以用于时间或空间区域,并且提供了一套基本关并且提供了一套基本关系和推理机。系和推理机。特别是他们定义了基本关系的合成表特别是他们定义了基本关系的合成表,可可以用于检验时空约束以用于检验时空约束,甚至用于检验区域特征的时空演甚至用于检验区域特征的时空演变。变。空间推理的研究热点空间推理的研究热点2023/8/20史忠植 高级人工智能74空间推理的研究热2024/8/7史忠植 高级人工智能75l3.在论文在论文“TemporalDynamicsandGeographicInformationSystems”中中,StephenStead认为认为,现实现实世界是沿着一条根据数值的时间范围划分的有唯一顺序世界是沿着一条根据数值的时间范围划分的有唯一顺序的时间路线运转。的时间路线运转。他借鉴考古应用中的为时间建模的方他借鉴考古应用中的为时间建模的方法法,提出了标准切割时间技术方法提出了标准切割时间技术方法,存储风景快照作为解存储风景快照作为解释背景。释背景。Stead把已知数据元素表示在四维空间把已知数据元素表示在四维空间(x,y,z 和和t)中中,这样一来这样一来,就可以为现实世界的过程建模了。就可以为现实世界的过程建模了。2000年年6月在新奥尔良召开的月在新奥尔良召开的IEA/AIE22000研讨会研讨会和在德克萨斯召开的和在德克萨斯召开的AAAI22000研讨会以及研讨会以及2000年年8月在柏林召开的月在柏林召开的ECAI22000等空间推理研讨会等空间推理研讨会,都是都是以时空推理为主题的。以时空推理为主题的。空间推理的研究热点空间推理的研究热点2023/8/20史忠植 高级人工智能75 3.2024/8/7史忠植 高级人工智能76空间推理的研究热点空间推理的研究热点2023/8/20史忠植 高级人工智能76空间推理的研究热2024/8/7史忠植 高级人工智能77l定性空间推理定性空间推理当描述一个空间配置或对这样的配置进行推理的时当描述一个空间配置或对这样的配置进行推理的时候候,要获得精确、定量的数据通常是不可能的或不必要要获得精确、定量的数据通常是不可能的或不必要的。在这种情况下的。在这种情况下,可能要用到关于空间配置的定性推可能要用到关于空间配置的定性推理。理。定性空间表示包括许多不同的方面，我们不仅要判定性空间表示包括许多不同的方面，我们不仅要判定什么样的空间实体是我们可以接受的，同时还要考虑定什么样的空间实体是我们可以接受的，同时还要考虑描述这些空间实体之间关系的不同方法。例如描述这些空间实体之间关系的不同方法。例如,我们可我们可以仅考虑它们的拓扑结构、大小、形状以仅考虑它们的拓扑结构、大小、形状,或它们之间的或它们之间的距离。距离。当然当然,这些概念之间并不是完全独立的。这些概念之间并不是完全独立的。空间推理的研究热点空间推理的研究热点2023/8/20史忠植 高级人工智能77空间推理的研究热2024/8/7史忠植 高级人工智能78