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

定性推理史忠植中国科学院计算技术研究所高级人工智能第四章定性推理史忠植高级人工智能2023/9/12史忠植高级人工智能2内容提要4.1概述4.2定性推理的基本方法4.3定性模型推理4.4定性进程推理4.5定性仿真推理4.6代数方法4.7几何空间定性推理2023/8/3史忠植高级人工智能2内容提要4.1概述什么是定性推理？

定性推理(qualitativereasoning)是从物理系统、生命系统的结构描述出发,导出行为描述,以便预测系统的行为并给出原因解释。定性推理采用系统部件间的局部结构规则来解释系统行为,即部件状态的变化行为只与直接相邻的部件有关。什么是定性推理？定性推理(qualitative2023/9/12史忠植高级人工智能4

概述1952年Simmons提出定性分析的因果关系。1977年Rieger发表了因果仿真的论文。1984年“ArtificialIntelligence”杂志第24卷出版了定性推理专辑,

刊载了deKleer,Forbus和Kuipers对定性推理奠基性的文章,这标志着定性推理开始走向成熟。1986年Iwasaki和Simmons发表了“CausalityinDeviceBehavior”的文章。1993年“ArtificialIntelligence”杂志第59卷又发表了一组文章，回顾十年前这几位定性推理奠基人所做的工作。2023/8/3史忠植高级人工智能4概述1952年2023/9/12史忠植高级人工智能5

概述deKleer的定性模型方法[deKleer1984]Forbus的定性进程方法[Forbus1984]Kuipers定性仿真法[Kuipers1984]2023/8/3史忠植高级人工智能5概述deKlee2023/9/12史忠植高级人工智能6

概述Davis提出从结构描述出发进行故障论断的方法Reiler提出从基本原理出发进行故障诊断的方法Williams把定量运算和定性推理相结合建立了一个混合代数系统Q1Iwasaki和Simmons把经济学、热力学中所用的因果关系形式化Weld在分子生物学中设计了定性模拟程序

2023/8/3史忠植高级人工智能6概述2023/9/12史忠植高级人工智能7定性推理的基本方法

人类对物理世界的描述、解释,常是以某种直观的定性方法进行的,很少使用微分方程及具体的数值描述,如人们在骑自行车时,为了避免摔倒和撞车,并不需要使用书本上的运动方程,而是针对几个主要参量的变化趋势给予粗略的、直观的,但大体上准确的描述,这就够了。2023/8/3史忠植高级人工智能7定性推理的基本方法2023/9/12史忠植高级人工智能8定性推理的基本方法

一般分析运动系统行为的标准过程可分为三个步骤：

(1)决定描述对象系统特征的量。

(2)用方程式表示量之间的相互关系。

(3)分析方程式，得到数值解。2023/8/3史忠植高级人工智能8定性推理的基本方法2023/9/12史忠植高级人工智能9定性推理的基本方法这类运动系统行为的问题用计算机进行求解时，将面临如下三个问题：

(1)步骤(1)(2)需要相当多的知识，并且要有相应的算法。

(2)有的场合对象系统的性质很难用数学式子表示。

(3)步骤(3)得到了数值解，但是对象系统的行为并不直观明了。2023/8/3史忠植高级人工智能9定性推理的基本方法这2023/9/12史忠植高级人工智能10定性推理的基本方法为了解决第二、第三个问题，定性推理一般采用下列分析步骤：

(1)结构认识：将对象系统分解成部件的组合。

(2)因果分析：当输入值变化时，分析对象系统中怎样传播。

(3)行为推理：输入值随着时间变化，分析对象系统的内部状态怎样变化。

(4)功能说明：行为推理的结果表明对象系统的行为，由此可以说明对象系统的功能。2023/8/3史忠植高级人工智能10定性推理的基本方法2023/9/12史忠植高级人工智能11定性推理的基本方法定性推理的观点大体上可这样来理解:•忽略被描述对象的次要因素,掌握主要因素简化问题的描述。•将随时间t连续变化的参量x(t)

的值域离散化为定性值集合,

通常变量x的定性值[x]定义为•依物理规律将微分方程转换成定性(代数)方程,或直接依物理规律建立定性模拟或给出定性进程描述。•最后给出定性解释2023/8/3史忠植高级人工智能11定性推理的基本方法2023/9/12史忠植高级人工智能12定性模型推理deKleer研究解决经典物理问题需要哪些知识及如何建立问题求解系统。他提出的定性模型方法所涉及的物理系统是由管子、阀门、容器等装置组成,约束条件(定性方程)反映在这些装置的连接处,依定性方程给出定性解释。为将代数方程、微分方程定性化,首先需定义变量的定性值集合以及相应的定性运算。2023/8/3史忠植高级人工智能12定性模型推理2023/9/12史忠植高级人工智能13定性模型推理定性值集合是一个离散集合,其元素是由对数轴的划分而得到的,通常把数轴(－∞,∞)划分成(－∞,0),0,(0,∞)三段,规定定性值集合为{－,0,＋},变量x的定性值[x]如下定义:另外用∂x表示dx/dt的定性值,也即2023/8/3史忠植高级人工智能13定性模型推理另外用2023/9/12史忠植高级人工智能14定性模型推理

xy

-0+---?0-0++?++[x]⊕[y]xy

-0+-+0-0000+-0+[x]⊗[y]

其中:符号？表示不确定或无定义。2023/8/3史忠植高级人工智能14定性模型推理2023/9/12史忠植高级人工智能15定性模型推理下面给出⊕和⊗的运算规则。设e1,e2是公式,则有：[0]⊕[e1]⇒[e1][0]⊗[e1]⇒[0][+]⊗[e1]⇒[e1][-]⊗[e1]⇒-[e1]2023/8/3史忠植高级人工智能15定性模型推理[0]2023/9/12史忠植高级人工智能16定性模型推理使用下列规则，可将运算符+、

转换成⊕、⊗：

[e1＋e2]⇒[e1]⊕[e2][e1

e2]⇒[e1]

[e2]2023/8/3史忠植高级人工智能16定性模型推理[2023/9/12史忠植高级人工智能17压力调节器压力调节器是通过弹簧来控制阀门流量,以使流量为某一设定值而不受流入的流量和负载变化的影响。根据物理学有2023/8/3史忠植高级人工智能17压力调节器压力调节2023/9/12史忠植高级人工智能18压力调节器其中Q是通过阀门的流量,P是压力,A是阀门开启的面积,而C是常系数,

是流体的质量密度。按照运算和转换规则而得到定性方程：[Q]=[P]∂Q=∂A+∂P(如果A>0)2023/8/3史忠植高级人工智能18压力调节器其中Q2023/9/12史忠植高级人工智能19压力调节器OPEN状态A=Amax定性方程[P]=0∂P=0WORKING状态0<A<Amax定性方程[P]=[Q]∂P+∂A=∂QCLOSED状态A=0定性方程[Q]=0∂Q=0

除了可以讨论每个状态内的定性分析还可讨论各状态间转换的定性分析。deKleer建立的ENVSION系统是使用约束传播与生成测试方法来求解定性方程。2023/8/3史忠植高级人工智能19压力调节器OPEN2023/9/12史忠植高级人工智能20定性进程推理

Forbus提出的定性进程方法把物理现象视作由一些相关的进程来描述,每个进程由一组个体、前提条件、数量条件、参数关系和影响来描述,推理过程是从已知的进程表中依次选出一些可用的进程来描述一个物理过程。定性进程理论中有关定性物理的关键思想如下：

(1)组织原则为物理进程。本体论在知识的组织上起着重要作用。在人们进行物理系统推理时，物理进程非常直观，用它组织物理领域的理论是合理的。

(2)用顺序关系表示数值。重要的性质差别常由比较而来。例如，当压力和温度不同时产生流动；当温度到达某一界值时会发生相变等。在很多情况下，用一套序数关系表示数值更自然。2023/8/3史忠植高级人工智能20定性进程推理Fo2023/9/12史忠植高级人工智能21定性进程推理

(3)单一机制假设。物理进程被看作是产生变化的机制。这样，任何变化必须解释为某些物理进程的直接或间接的影响。进程本体论为定性物理理论的因果性打下了基础。

(4)组合的定性数学。人们进行复杂系统推理时，使用部分信息并进行组合。

(5)清晰的表示及关于模型化假设的推理。明确地表示某些特定知识的适用条件，并从领域理论中为特定系统建模成为定性物理的中心任务。2023/8/3史忠植高级人工智能21定性进程推理(32023/9/12史忠植高级人工智能22定性进程推理

一个物理系统的变化是由进程引起的,一个物理过程由一些进程来描述,这就是定性推理进程方法的基本观点。下面介绍在定性进程推理中的量空间和进程的描述。2023/8/3史忠植高级人工智能22定性进程推理一个2023/9/12史忠植高级人工智能23定性进程推理1.量空间

(1)时间由区间表示,区间之间的关系有前、后、相等。两个区间可以相连,瞬间认为是极短的区间,持续时间为0。

(2)物体的参数称作量,量由其数量和导数组成。

Am表示数量的值,As表示数量的符号。

Dm表示数量导数值,Ds表示数量导数的符号。

(MQt)表示时刻t量Q的值。

HAS-Quantity是谓词,指某物体具有某参数。

(3)一个量的所有可能取值构成量空间,量空间的元素间有半序关系。2023/8/3史忠植高级人工智能23定性进程推理1.2023/9/12史忠植高级人工智能24定性进程推理2.进程

一个物理进程P由一组个体、一组前提条件、一组数量条件、一组参数关系和一组影响组成。一个进程的具体示例称作进程例，用PI表示。2023/8/3史忠植高级人工智能24定性进程推理2.2023/9/12史忠植高级人工智能25定性进程推理Processheat-flow.热流进程Individuals:一组个体

srcanobject,Has-Quantity(src,heat)src是热源

dstanobject,Has-Quantity(dst,heat)dst是受热对象pathaheat-path,path是热流路径

Heat-connection(path,src,dst)将src,dst连结起来Preconclitions:一组前提条件

Heat-Aligned(path)热流路径安排好

QuantityConditions:一组数量条件

A[temperature(src)]>A[temperature(dst)]src温度高于dst温度2023/8/3史忠植高级人工智能25定性进程推理Pr2023/9/12史忠植高级人工智能26定性进程推理Relations:一组参量关系

Letflow-ratebeaquantityflow-rate(热流量)是一个数量

A[flow-rate]>ZERO.flow-rate值>0flow-rate∝Q+(temperature(src)-temperature(dst))flow-rate与src,dst的温差定性成比例Influences:一组影响

1-(heat(src),A[flow-rate])flow-rate的值直接影响

heat(src),而且是负影响

1＋(heat(dst),A[flow-rate])flow-rate的值直接影响

heat(dst),而且是正影响2023/8/3史忠植高级人工智能26定性进程推理Re2023/9/12史忠植高级人工智能27定性进程推理演绎过程

在进程定性推理中，其演绎过程如下：

(1)选进程。对一组已知的个体来说,在进程表中依各进程对个体的说明找出可能出现的那些进程例PI。

(2)确定激活的PI。依前提条件、数量条件确定每个PI的状态。满足这些条件的为激活的PI,激活的PI叫进程结构。

(3)确定量的变化。个体的变化由相应量的Ds

值来表示。量的变化可由进程直接影响，也可由∝Q间接影响。

(4)确定进程结构变化。量的变化将会引起进程结构的变化,确定这种变化也叫限制分析,这样对一个物理过程的描述便由(1)建立的PI进入了下一个PI。重复(1)－(4)的步骤便可给出一个物理过程的一串进程描述。2023/8/3史忠植高级人工智能27定性进程推理演绎过2023/9/12史忠植高级人工智能28定性进程推理2023/8/3史忠植高级人工智能28定性进程推理2023/9/12史忠植高级人工智能29定性仿真推理

1984年Kuipers发表了“因果性的常识推理：从结构导出行为”论文。这篇论文建立了一种定性仿真推理的框架,简单地给出了从常微分方程的抽象而得的定性结构和定性行为表示方法。随后，1986年AI杂志又刊登了Kuipers“定性仿真”一文，文中明确了抽象关系，提出用于定性仿真的QSIM算法，并用抽象关系证明了其有效性和不完备性。这两篇文章奠定了定性仿真的基础。演绎过程

2023/8/3史忠植高级人工智能29定性仿真推理192023/9/12史忠植高级人工智能30定性仿真推理

定性仿真是从结构的定性描述出发来导出行为描述。直接用部件的参量作为状态变量来描述物理结构,定性约束直接由物理规律得到,把一个参量随时间的变化视作定性的状态序列,求解算法是从初始状态出发,生成各种可能的后续状态,进而通过一致性过滤,重复该过程直到没有新状态出现。定性仿真结构描述由系统的状态参数和约束关系组成。认为参数是时间的可微函数,约束是参数间的二元或多元关系。如速度的导数是加速度。表为DERIV(Vel,acc)。f=ma

表为MULT(m,a,f),f

随

g单调增加表为M+(f,g),f

随g单调减少,表为M-(f,g)。2023/8/3史忠植高级人工智能30定性仿真推理2023/9/12史忠植高级人工智能31定性仿真推理行为描述关心参量的变化。假设参量f(t)是[a,b]到［－∞,∞］的可微函数。f的界标值是一个有限集合,至少含有f(a),f(b)。集合{t|t∈[a,b]∧f(t)

是界标值}的元素称作区别点。定义4.1设l1<l2<┅<lk是f:[a,b]→[-∞,∞]的界标值。对任意t∈[a,b],f

在t的定性状态QS(f,t)规定为有序对

<qval,qdir>,定义如下:2023/8/3史忠植高级人工智能31定性仿真推理行为描2023/9/12史忠植高级人工智能32定性仿真推理2023/8/3史忠植高级人工智能32定性仿真推理2023/9/12史忠植高级人工智能33定性仿真推理

定义4.2设ti,ti+1是相邻的区分点,规定f在(ti,ti+1)内的定性状态QS(f,ti,ti+1)仍为QS(f,t)其中t∈(ti,ti+1)2023/8/3史忠植高级人工智能33定性仿真推理定义2023/9/12史忠植高级人工智能34定性仿真推理定义4.3f

在[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/3史忠植高级人工智能34定性仿真推理定义2023/9/12史忠植高级人工智能35定性仿真推理定性状态转换在定性仿真中，定性状态转移是经常遇到的。假设f是可微函数,f从一个定性状态转换到另一个定性状态必须遵守介值定理和中值定理。定性状态转换有两类：一类是P转换，该类转换是从时间点到时间区间；另一类是I转换，它是从时间区间到时间点的转换。下面给出转换表:2023/8/3史忠植高级人工智能35定性仿真推理定性状2023/9/12史忠植高级人工智能36定性仿真推理P转换QS(f,ti)

QS(f,ti,ti+1)P1<lj,std>

<lj,std>P2<lj,std>

<(lj,lj+1),inc>P3<lj,std>

<(lj-1,lj),dec>P4<lj,inc>

<(lj,lj+1),inc>P5<(lj,lj+1),inc>

<(lj,lj+1),inc>P6<lj,dec>

<(lj-1,lj),dec>P7<(lj,lj+1),dec>

<(lj,lj-1),dec>2023/8/3史忠植高级人工智能36定性仿真推理P转换2023/9/12史忠植高级人工智能37定性仿真推理I转换QS(f,ti,ti+1)

QS(f,ti+1)I1<lj,std>

<lj,std>I2<(lj,lj+1),inc>

<lj+1,std>I3<(lj,lj+1),inc>

<lj+1,inc>I4<(lj,lj+1),inc>

<(lj,lj+1),inc>I5<(lj,lj+1),dec>

<lj,std>I6<(lj,lj+1),dec>

<lj,dec>I7<(lj,lj+1),dec>

<(lj,lj+1),dec>I8<(lj,lj+1),inc>

<l*,std>I9<(lj,lj+1),dec>

<l*,std>2023/8/3史忠植高级人工智能37定性仿真推理I转2023/9/12史忠植高级人工智能38定性仿真推理

QSIM算法可对系统的行为进行定性仿真。首先将初始状态送入ACTIVE表中,然后重复(1)—(6)直至ACTIVE表空为止。算法4.1QSIM算法。

(1)从ACTIVE表中选一状态。

(2)对每个参数按转换表找出所有可能的转换。

(3)对约束中变元的转换生成二元组,三元组集合,依约束关系做一致性滤波。

(4)对有公共变元的约束,对元组进行组对,再对组对的元组做一致性滤波。2023/8/3史忠植高级人工智能38定性仿真推理QS2023/9/12史忠植高级人工智能39定性仿真推理(5)从剩下的元组生成所有可能的全局解释。每个解释生成一个新状态作为当前状态的后继状态。(6)对新状态做全局滤波,剩下的状态送入ACTIVE表。全局滤波排除下列状态：

•无变化情形:如I1,I4,I7;•循环情形:新状态与某个前辈状态相同;•发散情形:某参数值为∞,这时当前时间点必为结束点。2023/8/3史忠植高级人工智能39定性仿真推理(5)2023/9/12史忠植高级人工智能40几何空间定性推理空间定性推理是对几何形状或者运动性质进行定性推理，首先需对空间位置及运动方式进行定性表示，进而对几何形状及运动性质进行推理研究及预测分析，并作出逻辑解释。空间定性推理是通过定义一组空间并寻找这些关系间的联系来进行的。目前主要的研究是针对空间定性建模方式、空间形状及关系的定性表示和定性技术的形式化等,

产生解释理论,但总体来看与解决工程问题距离尚远。2023/8/3史忠植高级人工智能40几何空间定性推理空2023/9/12史忠植高级人工智能41几何空间定性推理将Allen的时态逻辑[Allen1984]与Randall的空间逻辑[Randall1992]结合起来，形成空间、时间、连续运动的表达逻辑。另外从空间定性推理派生出空间规划理论,可用于为一组几何对象寻找满足一组约束的分布设计,有关方法主要用于设计自动化、定性建模等领域。在这一领域已取得了一些较有实际意义的成果,如约束满足问题(CSP)求解理论,而实际上很多空间定性规划都是一个几何约束满足问题(GCSP)。2023/8/3史忠植高级人工智能41几何空间定性推理将2023/9/12史忠植高级人工智能42几何空间定性推理1992年由Randell等人建立起来的RCC空间时间逻辑是用于对空间问题进行可达性的展望,并已程序实现。与Kuipers的QSIM方法类似,基于RCC逻辑的仿真算法也是从对系统进行结构性的描述开始的,系统将初始状态作为生成树的根结点,可能的行为则是树中从根结点到叶结点的路径。2023/8/3史忠植高级人工智能42几何空间定性推理12023/9/12史忠植高级人工智能43QualitativeSpatialReasoningQualitativereasoningmodellingthecontinuousrealityinmanageableentitiessolutionforquantitativeproblemsthatarenotcomputableTwoapproachesartificialintelligence→GIScience

1992Randell,Cui,Cohndatabases→GISystems

1991Egenhofer,FranzosaGISRUK2004–UniversityofEastAngliaSlide5of20几何空间定性推理2023/8/3史忠植高级人工智能43Qualitati2023/9/12史忠植高级人工智能44RCCRCC=RegionConnectionCalculusRandell,Cui,Cohntopologicalrelationsofpolygonsqualitativemodellingdisjoint,meet,overlapconceptualneighbourhood-diagramGISRUK2004–UniversityofEastAngliaSlide6of20RCC几何空间定性推理2023/8/3史忠植高级人工智能44RCCRCC=G2023/9/12史忠植高级人工智能45RCC-diagramGISRUK2004–UniversityofEastAngliaSlide7of20Conceptualneighbourhooddiagram几何空间定性推理2023/8/3史忠植高级人工智能45RCC-diaQualitativeCalculi

ThesuccessofqualitativereasoningreliesonchoiceofgoodqualitativecalculiAq-calculusisgeneratedbyasetofjointlyexhaustiveandpairwisedisjoint(JEPD)relationsonthedomainofdiscourseQualitativeCalculiThesucces2023/9/12史忠植高级人工智能47RCC8TopologicalAlgebraRegionsarenonemptyregularclosedsubsetsofaconnectedregulartopologicalspace(e.g.Euclideanspace)BasicRCC8relationsaredefinedonregions2023/8/3史忠植高级人工智能47RCC8Topo2023/9/12史忠植高级人工智能48RCC8BasicRelationsDCECPOTPPNTPPEQdisjointmeetoverlapcovered_bycontained_byequalBABABABAA=BBA2023/8/3史忠植高级人工智能48RCC8Basi2023/9/12史忠植高级人工智能49DirectionalModelPoint-basedProjection-basedCone-basedRegion-basedRectangleAlgebraDirection-RelationMatixModel2023/8/3史忠植高级人工智能49Direction2023/9/12史忠植高级人工智能50Cone-BasedCardinalDirectionsFrankAU.Qualitativespatialreasoning:Cardinaldirectionsasanexample.IJGIS,1996,10:269~290

2023/8/3史忠植高级人工智能50Cone-Base2023/9/12史忠植高级人工智能51Projection-BasedCard.DirectionsFrankAU.Qualitativespatialreasoning:Cardinaldirectionsasanexample.IJGIS,1996,10:269~2902023/8/3史忠植高级人工智能51Projectio2023/9/12史忠植高级人工智能52RectangleAlgebraTherectanglerelationbetweentwoboxesA,Bisdescribedbytheintervalrelationsbetweenthex-andy-projectionsofA,BABABA(o,oi)BA(m,d)B2023/8/3史忠植高级人工智能52Rectangle2023/9/12史忠植高级人工智能53Direction-RelationMatrixR.K.Goyal,M.J.Egenhofer:SimilarityofCardinalDirections.SSTD2001:36-58AForeachreferenceobjectA,theplaneisdecomposedinto9tiles,Ai(i=0,…,8),withA0theMBRofA.A5A8A7A6A3A2A1A42023/8/3史忠植高级人工智能53Direction2023/9/12史忠植高级人工智能54Direction-RelationMatrixABCThedirectionrelationbetweenA,Bisexpressedasa3*3BooleanmatrixM=(mij),wheremij=0iffAiisdisjointfromB.2023/8/3史忠植高级人工智能54Direction2023/9/12史忠植高级人工智能55Reasoningwithq-CalculiConstraintsGivenaq-calclusR,andarelationrinR,(xry)expressaconstraintbetweentwovariablesxandyCompositionGiventwoconstraints(xry)&(ysz),wewanttoknowthestrongestrelationts.t.(xtz)ispossibletiscalledtheweakcompositionofrands2023/8/3史忠植高级人工智能55Reasoning2023/9/12史忠植高级人工智能56Reasoningwithq-CalculiGivenaconstraintnetworkN={xi

rijxj},isNsatisfiable?Thisisthesatisfactionproblem.ForSasubsetofthewholealgebra,wewriteRSAT(S)fortheproblemofdecidingsatisfactionofnetworkswithconstraintsoverS.2023/8/3史忠植高级人工智能56Reasoning2023/9/12史忠植高级人工智能57Reasoningwithq-CalculiThesatisfactionproblemsareoftenNPhard,e.g.RSAT(IA)andRSAT(RCC8)areNPCReasoningproblemsinIAandRCC8havebeeninvestigatedthoroughly,andmanyusefultechniqueshavebeendeveloped.2023/8/3史忠植高级人工智能57Reasoning2023/9/12史忠植高级人工智能58Localconstraintsolvingtechniquesmaybeuseful,e.g.path-consistencyalgorithm(PCA)cansolveRSAT(S)ifSisthemaximaltractablesubalgebraofIAReasoningwithq-Calculi2023/8/3史忠植高级人工智能58Localcon2023/9/12史忠植高级人工智能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/3史忠植高级人工智能59几何空间定性推理空2023/9/12史忠植高级人工智能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/3史忠植高级人工智能60几何空间定性推理2023/9/12史忠植高级人工智能61几何空间定性推理基本关系间的联系这种空间逻辑与Allen的逻辑相类似,也使用预计算的传递性表来表示二元关系之间可能的变化联系,在表中从任一关系R3(a,c)可查找出所有可能的二元关系R1(a,b)与R2(b,c)。这一表对定性仿真是很有用的。然而,近年的研究中尚未给出这类传递性表的建立算法。但Randell提到在其仿真程序中使用了该表来检验展望过程中状态描述的一致性。2023/8/3史忠植高级人工智能61几何空间定性推理基2023/9/12史忠植高级人工智能62几何空间定性推理基本状态间的相互转换根据两个区域的形状不同,上述八个基本关系可被分为6个子集:

(1)DCECPO=(2)DCECPOTPP(3)DCECPOTPP-1(4)DCECPOTPPNTPP(5)DCECPOTPP-1NTPP-1

(6)DCECPO2023/8/3史忠植高级人工智能62几何空间定性推理基2023/9/12史忠植高级人工智能63几何空间定性推理空间时间关系描述

1.方位性状态和运动性状态

Galton将八个RCC关系分为方位性状态(positionstate)和运动性状态(motionstate)，并且使用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/3史忠植高级人工智能63几何空间定性推理空2023/9/12史忠植高级人工智能64几何空间定性推理空间时间关系描述方位性状态。如果状态s满足∀i(Holds-on(s,i))→Holds-at(s,inf(i))∧Holds-at(s,sup(i))即如果一个状态s在时间区间i上存在,则在该区间的起止时刻这个状态都存在。具有这一性质的状态称为方位性状态。2023/8/3史忠植高级人工智能64几何空间定性推理空2023/9/12史忠植高级人工智能65几何空间定性推理空间时间关系描述运动性状态。如果状态s满足∀t(Holds-on(s,t)→∃i(Div(t,i)∧Holds-on(s,i)))即如果在某时刻t有状态s,那么一定存在包含这一时刻的某一区间使$s$在整个区间都存在,具有这一性质的状态称为运动性状态。2023/8/3史忠植高级人工智能65几何空间定性推理空2023/9/12史忠植高级人工智能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/3史忠植高级人工智能66几何空间定性推理空2023/9/12史忠植高级人工智能67几何空间定性推理

Randell算法假设初始状态S0

已放入状态集合S中。

(1)如果S空则停止;(2)从S中选出状态Si,且移出;(3)如果Si

为不一致状态将转(2);(4)应用状态约束选择可用变换规则;(5)用所选出的规则产生可能的下一个状态集合;(6)使用添加与删除规则;(7)进行状态内约束检查;(8)将剩下的状态加入S并转(1)。2023/8/3史忠植高级人工智能67几何空间定性推理2023/9/12史忠植高级人工智能68空间推理的研究进展对空间推理的许多研究方向进行分类、归纳和整理之后得到的主要研究方向是：

(1)空间数据库的精度。

(2)空间关系语言。

(3)空间推理与地理信息系统。

(4)空间决策支持系统。

(5)空间数据的不确定性处理。

(6)形式化的绘图知识。

(7)时空推理。2023/8/3史忠植高级人工智能68空间推理的研究进展2023/9/12史忠植高级人工智能69

(8)定性空间推理。

(9)空间推理的用户界面。

(10)基于案例(CASE-BASED)的空间推理.(11)空间推理的认知问题。

(12)空间推理与机器人视觉。

(13)常识推理。

(14)区域连接演算RCC-8。空间推理的研究进展2023/8/3史忠植高级人工智能69空间推理的研究2023/9/12史忠植高级人工智能70大量的文献空间推理的研究热点：时空推理STSR(spatio-temporalspatialreasoning)、定性空间推理QSR(qualitativespatialreasoning)地理信息系统空间推理的研究热点2023/8/3史忠植高级人工智能70大量的文献空间推理2023/9/12史忠植高级人工智能71时空推理当今世界是在漫长的历史长河中，历经沧桑演变进化而来的。世界中的任何事物和现象都遵循着诞生、生长，直至消失或死亡的自然规律。同样，现代文明和科技的进步无不是人类历史的经验积累和结晶。人类在认识和解释当今世界事物和现象时,不但渴望甚至必须了解它们的过去,而且希望预测未知的将来,以便在必要的时候采取一定措施,使人类社会朝着美好的方向发展。在这绵延不断的历史轨迹中，无不打上了时间的烙印，因此,探索适宜的工具和方法,沿着时间脉络研究和推理客观世界内在机制和时空发展规律,就显得十分重要。空间推理的研究热点2023/8/3史忠植高级人工智能71时空推理空间推理的2023/9/12史忠植高级人工智能72

总的来说，影响空间推理结果的因素包括空间因素和时间因素。所谓时空推理是指在空间推理过程中添加时间因素。地表、地下和大气等空间对象的状态不仅受到空间因素的影响,同时,从一个漫长的时间过程来看，也必将受到时间因素的影响。可以说,时空推理是更为一般的空间推理,或者可以说空间推理是时空推理的一个特例。目前,时空推理方面的研究还处于起步阶段。下面,我简单地介绍一些权威学者对时空推理的认识和他们提出的时空推理模型。空间推理的研究热点2023/8/3史忠植高级人工智能72空间推理的研究热点2023/9/12史忠植高级人工智能73

1.RichardA.Block在他的论文“PsychologicalTimeandtheProcessingofSpatialInformation”中指出：“与其说空间为时间提供了一个框架，不如说时间感知为空间感知提供了一个框架”。“位置和持续时间之间、个人经验和常识之间以及期望和回顾之间存在重要的区别”。他提出了上下文时间模型，并且把它扩展到空间，模型着眼于哪些变量对持续时间和其他种类的时间体验之间及行为和判断之间的相互作用有影响，这些变量包括实验者的特征、时间周期、时间周期上的活动和时间行为。空间推理的研究热点2023/8/3史忠植高级人工智能73空间推理的研究热点2023/9/12史忠植高级人工智能74

2.A.G.Cohn,Z.Cui,D.A.Randell在他们的论文“ExploitingTemporalContinuityinQualitativeSpatialCalculus”中提出了一个空间知识推理的逻辑框架,目的是为人工智能系统的表示和推理提供一个形式上的时间和空间的公理理论。