（计算机软件与理论专业论文）基于定性空间推理的机械装置概念设计.pdf

中囝科学技术大学硕士学位论文 摘要 定性仿真是以非数字手段处理信息输入、建模、行为分析和结果输出等仿真 环节，通过定性模型推导系统的定性行为描述。它提供了一种以定性的方式直接 求解问题的简单的推理方法，并且能够捕捉到所有定性可区分的系统行为。 定性空间推理是定性仿真领域新兴发展的研究分支，在各个方面都有广阔的 应用前景，丽机械装置的概念设计的地位也同益被人们所发觉。因此结合定性空 间推理理论应用到机械装置的概念设计中是近年来部分仿真领域的科学工作者 的着眼点。 本文在前人研究的基础上对利用定性空间推理的方法描述机械装置的空间 配置提出了一个思想框架，使得计算机能够通过对定性信息的自动推理，在机械 装置概念设计阶段预测其所有可能合理的空问配置信息。在推理过程中运用了约 束传播和符号代数的方法，其推理机制主要定位于机械装置的运动方式和空间信 息的定性描述。在每个复杂机械装置都是由输入输出功能单一的机械部件构成的 前提下，对每个构成机械装置的基础功能部件提供其描述空间运动的定性信息向 量和描述其输出方位的空问位置向量，通过有机的推理功能部件信息，得到复杂 机械装置的综合空间配置。并在动态设计的后续阶段对机械装置的动力学进行分 析，并利用流行的定性仿真方法q s i m 算法对机械装置的整体动态性能做全局 致性解释。 关链试：定性钫真定性空阚推理。概念设计枫械装置，定性符s 健数 中困科学技术大学碰一卜学位论文 a b s t r a c t q u a l i t a t i v es i m u l a t i o ni san o nn u m e r i cm e t h o dt oi n p u ti n f o r m a t i o n ，m o d e la s y s t e m ，a n a l y z et h eb e h a v i o ra n do u t p u tt h er e s u l t s i ta d d r e s s e sas i m p l ei n f e r e n c e m e t h o dt os o l v eap r o b l e md i r e c t l yi naq u a l i t a t i v ew a y a n di ti sg u a r a n t e e dt o c a p t u r ea l lq u a l i t a t i v e l yd i s t i n c tb e h a v i o r so f t h es y s t e m q u a l i t a t i v es p a t i a lr e a s o n i n gi so neo f t h en e w e s tr e s e a r c hb r a n c h e so f q u a l i t a t i v e s i m u l a t i o n a l s oi th a sw i d e l ya p p l i c a t i o n t h ei m p o r t a n c eo fc o n c e p t u a ld e s i g no f m e c h a n i s m sh a sb e e ni m p r o v i n gi nd e s i g nf i e l df o ri t sm a n ya d v a n c e s s om a n y r e s e a r c h e r ss c i e n t i s t si nq u a l i t a t i v es i m u l a t i o nh a v ef o c u st h e i rr e s e a r c ho nh o wt o c o m b i n eq u a l i t a t i v es p a t i a lr e a s o n i n gs y s t e mi n t oc o n c e p t u a ld e s i g no f m e c h a n i s m b a s e do nr e s e a r c ho fm a n ys c i e n t i s t si nq u a l i t a t i v es p a t i a lr e a s o n i n gf i e l d ，an o v e l a p p r o a c h t o q u a l i t a t i v es p a t i a lr e a s o n i n g a b o u tt h e s p a t i a lc o n f i g u r a t i o no f m e c h a n i s m st h a tc o u l db ea p p l i e dt op r o v i d eq u a l i t a t i v es p a t i a li n f o r m a t i o no ft h e m e c h a n i s mi nt h ee a r l yc o n c e p t u a ld e s i g np h a s e si sp r e s e n t e d t h eb a s i ci d e ai nt h i s a p p r o a c hi st op r e d i c ta l lr e a s o n a b l es p a t i a lc o n f i g u r a t i o n so fam e c h a n i s mu s i n g c o n s t r a i ns p r e a da n ds i g na l g e b r a t h i sp a p e ra d d r e s s e st h ep r e s e n t a t i o no fa m e c h a n i s ms p a t i a li n f o r m a t i o na n dq u a l i t a t i v ed y n a m i ci n f o r m a t i o n f i r s t l yp r e s e n t e a c hb a s i cm e c h a n i s mc o m p o n e n t s ，w h i c hc o m p o s ec o m p l e xm e c h a n i s m s ，t h e q u a l i t a t i v ei n f o r m a t i o nv e c t o r , p o s i t i o nv e c t o ra n dd y n a m i cc o n s t r a i n s t h eq u a l i t a t i v e i n f o r m a t i o nv e c t o rc o n t a i n st h eq u a l i t a t i v ec o n f i g u r a t i o ni n c l u d i n gt h ed y n a m i cs t y l e s o ft h em e c h a n i c a l c o m p o n e n t s t h ep o s i t i o n v e c t o ri n c l u d e st h eo r i e n t a t i o n i n f o r m a t i o n s u p p o s e a l lt h ec o m p l e xm e c h a n i s mi s c o m p o s e db yt h e s eb a s i c c o m p o n e n t s ，t h e i ri n f o r m a t i o nc a nb eo b t a i n e dt h r o u g hr e a s o n i n ga n ds i m u l a t i o nw i t h t h ei n f o r m a t i o no ft h e s eb a s i c c o m p o n e n t s i nd e s i g nd y n a m i ca n a l y s i sp h a s e ， a n a l y z i n gt h ep a r a m e t e r sr e l a t i o n s h i pw h e nm e c h a n i s mi sw o r k i n ga n di nt h en e x t s t e pu s i n gq s i mi n t e r p r e tt h em e c h a n i s md y n a m i cp e r f o r m a n c e k e y w o r d s ：q u a l i t a t i v es i m u l a t i o n , q u a l i t a t i v es p a t i a lr e a s o n i n g c o n c e p t u a ld e s i g n , m e c h a n i s mc o n f i g u r a t i o n , 和a l i t a t i v es i g na l g e b r a 4 中国科学技术大学硕j ：学位论文 引言 仿真技术是一门迅速发展的高新技术，由于它具有经济、可靠、安全、灵活、 可多次重复使用等优点。系统仿真技术近几十年得到了很快的发展随着计算机技 术的发展，应用计算机进行系统仿真更是日益受到人们的重视。计算机仿真技术 结合了实验和分析这两种方法，将分析的方法用于模拟实验：充分运用已有的基 本物理原理。可建立待研究系统的数学模型：采用与实际的物理系统实验相同的 基本研究方法，可在计算机上运行仿真实验。可见传统的定量仿真，首先是建立 精确的数学模型，将对象系统的结构与功能表示成以微分方程为主的一系列数学 形式，导出基于函数解或数值解的系统行为描述。但是，这些传统的定量仿真、 以方程形式建模解决问题的方法存在一些难点，例如：如何将模糊的、非精确值 的真实世界问题反映为数学方程式，以及如何把用数学符号语言形式表达的结果 解释为一般意义上自然的形式等。 定性仿真正是基于这些难点问题而慢慢发展起来的。相对于传统的定量仿真 而言，定性仿真力求模拟人的定性思考过程去推理解决问题，引入了诸如归纳推 理、因果推理、图示等人类思考问题常用的方法，使得推理过程和结果更加清晰 易行。它力求非数字化，克服定量仿真的弱点，用非数字手段处理输入、建模、 行为分析和输出等仿真环节，通过定性模型推导系统的定性行为描述。 而目前来说，空间知识的表示和处理是认知科学和人工智能研究的中心问 题。出于空间知识和空间推理本质上是定性的，因而定性空间推理是表示并处理 空间知识的一种有效方法，它的研究不仅具有重要的理论意义，同时也具有广泛 的应用前景，近几年受到普遍的重视。定性空间推理的研究涉及空间知识的拓扑、 距离、朝向、形状、路径、时间、运动、语言学、认知科学、空间描述的可视化 等方面，对空间知识与时间、因果性和动力学的集成也予以了足够的重视，探索 出了公理化、代数、几何约束满足、基于模型的推理等基本方法，并在导航、地 理信息系统、工程设计、定性物理、空间数据库和图形图像等领域进行了应用研 究。由于概念设计在机械装罨的设计中占有越来越重要的地位，将定性空间推理 应用于机械装置的概念设计是一件非常有应用前景的研究工作。 在研读了大量国内外相关研究论文之后，本文提出了一套新颖的，针对机械 装罱概念设计的理论框架，利用向量和矩阵表示构成机械装置的各个机械部件的 运动方式和空间方位，以推理得到整个复杂机械装置的定性空间配置和方位信 息。并且应用于汽车概念设计，将概念设计分为三个阶段，第一个阶段利用定性 空间推理理论得到空间配置信息；第二阶段将汽车抽象为二自由度振动模型，利 用矩阵传递法，定性描述机械装置链上机械部件的振动响应，提供设计者动态时 中国科学技术大学硕士学位论文 机械部件参数关系：第三阶段利用流行的q s i m 算法对汽车整体稳态响应做全局 一致性解释。具体内容将在后文详细阐述。 全文的组织如下：第一章介绍了定性仿真目前国内外的研究方法论，并详细 介绍了定性仿真领域一个重要的研究方面定性空间推理的研究现状。第二章 主要介绍了q i s m 算法及其用于全局解释和一致性过滤的方法，以及多自由度系 统微分方程的建立和相应的振动传递矩阵方法。第三章详细阐述了我所提出的针 对机械装置概念设计的定性空间推理理论系统框架，并给出了个简单的实例表 示。第四章以卸货卡车为例，阐述了利用定性空间推理理论进行概念设计的三个 阶段的过程。第五章说明了基于定性空间推理理论应用于概念设计软件系统的体 系结构和数据结构。第六章在对全文进行分析总结的基础上，指出新方法的不足 之处以及改进的方向。 中寓科学技术大学硕士学位论文 第一章定性仿真的方法论介绍 从1 9 8 3 年美国学者d e k l e e r 和b r o w n 提出的关于定性建模和定性推理的理 论，以及1 9 8 4 年国际人工智能杂志第一次出版了关于定性问题的专辑以来。定 性仿真技术得到了迅猛发展，成为诸多学者的关注热点。而随着定性仿真理论的 发展与日趋成熟，也形成了各种派别，其中比较有影响的流派有：s e e l yb r o w n 和j o h nd ek l e e r 提出的基于“流”的概念的理论，k d f o r b u s 的定性过程理论 ( q p t ) ，b j k u i r ) e r s 的基于q s i m 的定性仿真理论( q s ) 以及b c w i l l i a m s 的 定性代数理论等等1 2 i t 3 i 。 定性仿真( q u a l i t a t i v es i m u l a t i o n ) 是以非数字手段处理信息输入、建模、行 为分析和结果输出等仿真环节，通过定性建模推导系统的定性行为描述。相对与 传统的数字仿真而言，定性仿真技术在处理不完备知识和“深层”知识以及决策 等方面尤其独到的长处。近年来，许多学者把耳光放在定性仿真的应用领域上。 现在，定性仿真技术与物理、化工、生物学、社会学和经济学等学科相互渗透、 相互结合、相互推进，在电力、交通、工程机械制造、生化、商业流通等领域发 挥着越来越大的作用1 1 1 1 2 1 1 。 在定性仿真思想建立起来之后，很多科学家致力于定性建模和定性推理的理 论研究中。九十年代，定性仿真理论已渐趋成熟，形成了各种体系，流派。 1 1 模糊仿真法 将模糊数学和定性仿真理论结合起来就产生了模糊仿真方法。模糊数学在定 性理论中一般用来作为一种描述手段。用模糊数学扩展定性仿真可以详细地描述 函数关系，并且能够表示和使用变化速率的时序信息，构造一种有效的时序过滤 规则，大量减少奇异行为的产生。研究者最初是采用区间模糊数的行为来描述系 统的定性值。英国的q i a n gs h e n 进一步将其发展到用凸模糊数来描述定性值， 在数据表示上前进了一大步。1 9 9 3 年他和r l e i t c h 提出模糊仿真方法f u s i m l 4 i ， 较好地把定性仿真技术与模糊数学进行了集成，这种方法用模糊集合扩展了传统 的量空间，从而增强了对函数关系的强度信息和变量的变化速率的顺序信息的描 述。模糊仿真方法也存在一些弱点，比如很难确定系统真实值与模糊量空间的映 射，并且模糊量值及其空间一旦确定后就不再变动，不能根据需要引入新的模糊 量，限制了其描述能力。 1 2 归纳推理法 中国科学技术大学硕= l 学位论文 归纳推理法源于通用系统理论中的g s p s 技术。其基本思想是假设所研究系 统是一个黑箱观察其输入输出值，以发现其规律生成定性行为模型，进而对任一 输入序列预测系统行为，六十年代gjk l i r 提出g s p s 的初步设想，1 9 7 8 年他发表 ac o n c e p t u a lf o u n d m i o nf o rs y s t e m sp r o b l e ms o l v i n g ) ) ，标志g s p s 层次结构基本 形成。同年，k l i r 的研究生hju y t t e n h o v e 部分实现了g s p s 专家系统。1 9 8 1 年 第一个g s p s 专家系统软件包s a p s 问世成为商业软件。1 9 8 7 年fec e l l i e r 改进 了s a p s ，与dwy a n d e l l 合作研制出s a p s ，将g s p s 技术应用到定性仿真实 现了归纳推理法| 7 引。归纳推理法完全省略结构模型。模型来自观测数据，自动 建模。归纳推理法可以处理观测数据辨识系统中的依赖关系，建立并优化系统定 性行为模型，预测系统行为。它模仿人类固有的概括总结和学习的能力。归纳推 理法也存在一些弱点，这种方法需要采集大量的数据。并处理和维护，而且由于 现实条件的限制，不能保证归纳的完备性。 1 3 非因果关系推理方法 非因果类方法主要是因为系统建模时不需要明确指出系统内状态变迁过程 的因果方向。其中的一些方法都已逐步从实验阶段发展到工程实践领域。 e n v i s i o n 【基于流( c o n n u e n c e ) 的概念以组员( c o m p o n e n t s ) 为中心的方法】 q s i m 【基于定性微分方程( q d e ) 以约束( e o n s t r a i n t s ) 为q h 心的定性仿真方法】 q p t 以过程( p r o c e s s ) 为中心的方法】t c p 时问推理方法，都属于这一类范 畴。 1 3 1e n v i s i o n ：组元c o m p o n e n t 为中心基于流的方法 s e e l yb r o w n 和j o h n d ek l e e r 提出了基于流c o n f l u e n c e 的概念的理论| 1 0 i ，并据 此建立了e n v i s i o n 系统该理论，认为一个系统可以用三种元素来描述：材料 m a t e r i a l s ，组元c o m p o n e n t s ，通道( c o n d u i t s ) 组元。作用于材料并改变其形式或特 性一个组元的材料，经通道流到另一个组元，组元以一系列变量流连接点描述。 流表示的是种约束关系，这种约束关系决定着处在平衡点附近的变量的变化。 1 3 2q p t ：过程为中心的方法 f o b u s 于1 9 8 4 年围绕着过程p r o c e s s 的概念提出了q p t 建模与仿真方法i ， 该方法认为分析物理系统实际上就是确定浚系统是由哪些过程组成的，如液体流 动过程，热量产生过程等。并且这些过程在不同情况下是如何影响系统发展的。 过程是与对象或个体视图( i n d i v i d u a lv i e w si v ) 相关联的。系统变量的值只能由与 它关联的活动过程改变。 中国科学技术大学顿十学位论文 1 3 3q s i m ：约束为中心的方法 k u i p e r s 在1 9 8 6 年提出了基于定性微分方程( q d e ) 的定性仿真理论l i “并 给出t q s i m 算法。这是目前定性仿真中发展得最成熟的理论，且应用最为广泛。 q s i m 理论认为系统由三种元素组成变量( v a r i a b l e s ) ，约束( c o n s t r a i n t s 】，操作域 ( o p e r a t i n gr e g i o n s ) 。变量的基本约束关系有五种d e r i v ( x ，y ) a d d ( x ，y ，z ) m u l t ( x ，y ，z ) m + ( x ，y ) m - ( x ，y ) ，利用这些关系来建立系统的定性微分方程。定性 仿真算法是以描述系统定性结构的定性微分方程和系统的一个初始状态为输入， 通过仿真输出。在q s i m 基础上发展起来的仿真方法很多，基本上都是为了消除 或减少应用q s i m 算法所产生的虚假行为，即与系统约束实际产生的可能行为不 相吻合的行为。 1 3 4t c p ：时间约束传播t e m p o r a lc o n s t r a i n tp r o p a g a t o r w i l l i a m sb c1 9 8 9 提出了此方法【9 i ，主要是根据人们对连续物理系统的因果 性，连续性，反馈等特性的直觉认知，去分析系统行。为注重对系统个体按局部 时间顺序的发展过程，即行为的历史。h i s t o r i e st c p 是基于约束传播的定性推理 技术，量值仅能通过关于区间的约束方程传播。系统输出的不仅仅包括变量的值 还给出了变量变化的历史，即变量为什么这样变化的推理过程。 1 4 基于因果关系的推理方法 基于因果关系的推理方法无一例外地依赖于有向图o r i e n t e dg r a p h 定性传递 函数方法。r a i m a no 在1 9 8 6 年提出f o g 系统1 9 i ，包括一个公理，3 0 个推论。 通过表达变量关联的约束网络传播初始化信息。通过f o g 的方法可以减少系统 中的次要作用，继续保留系统中的主要作用。然而这种方法只适用于代数方程中， 而不是用于微分方程中。o u s s o nk 和t r a v e - m a s s u y e s 在1 9 9 2 年提出结合了系 统的因果关系和深层次知识，并分别用数学方程表示它们例。用该理论设计的 c a e n 算法已应用到很多实际系统中。模型表示为两层约束，第一层是由因果 图支持的局部约束层，第二层是由物理方程组成的全局约束层分层。表示知识的 方法可以克服按照因果关系建模的一些明显局限，比如无法表示全局性的约束关 系。b e r tb r e d w e g 将因果关系推理应用在故障诊断方面是非常有特色的工作。系 统基于因果推理关系建立了一个基础的详细连接模型，模型由八类组件组成，每 个组件实现不同的功能，并且有多个输入端和一个输出端，一个领域知识的调控 端及与其他组件的连接关系。调控端代表一个变量对另一个变量的影响和作用。 由于组件输出是一个分段线性函数，因此可以作为另一个组件的输入。不同组件 的输入输出可以不同，例如q p 组件，调控端是输入和输出间的定量比例关系， 中国科学技术大学硕_ ：学位论文 输入输出分别为定性知识：而q i 组件，调控端则为输入对输出的影响，输入输 出分剐为定量值。组件也由调控端确定了输入端和输出端的因果关系，即输入作 为原因，调控端给出关系，而得到输出端作为结果。在建立起详细基础模型之后， 分别对模型进行隐藏非本质细节，合并组件成块，将不同块进行分组这三步操作， 得到一个最简化的组件模型以及组件之间连接结点的知识库。隐藏非本质细节就 是将系统中对于没有改变系统性质的细节从模型中删除，初步精简模型。而第二 步合并那些具有前驱后继关系的组件成块，进一步精简模型。最后将那些并列的， 没有相互因果关系的块分组，从而获得可以应用于故障诊断的模型。错误的诊断 过程是建模的逆过程，在进行诊断时，将实际观测数据从系统输出端反向输入最 简化模型，系统通过分组的知识库，利用因果关系，无需展开组内组件即可确定 故障所在的组。进而展开故障所在的组，同理快速确定故障所在的块，并完全展 开此块，最后确定故障发生在哪个组件的输入和输出端。此系统提供了高效的故 障诊断模型，并已成功运用于学校的教学系统中i l 引。 1 5 基于二维图表推理的方法 图表是人类认知的形象描述，它并不受数学的形式限制，在定性领域有着广 泛的应用前景。近些年来，许多定性推理方面的科学家都投身于图表推理的工作 当中，以期能够找到一套不利用符号进行推理的方法。所谓图表推理就是通过模 拟人类的感知方式和形象思维的途径，而不是利用传统的符号形式化方法进行推 理。一些学者对图表进行了定性可视结构的研究。图表推理在定性推理和仿真领 域占有越来越重要的地位。早期的定性空间推理大致分为三类，包括f o r b u s 的 二维动态仿真模型、s t a n f i l l1 9 8 3 ，f a l t i n g s f o r b u s1 9 8 7 ，j o s c o w l c z1 9 8 7 n i e l s e n 1 9 8 8 的二维机械动力学分析模型、b l a e k w e l l1 9 8 7 的二维复杂路径计划模型。这 些系统模型都是用于认知科学研究中的。m h e g a r t y 在1 9 9 2 年提出的机械装置 图表包括了依据因果链的可视关注点位置的定性知识：d l s c h w a r t z 在1 9 9 5 年 提出了利用选择分析或形象策略来解决图示表示的同构问题：j f i s h 和s s c r i v e n e r 在1 9 9 0 年提出草图和视觉认知方法：g g o l d e h m i d t 于1 9 9 1 年给出了草 图的辨认方法。而a l a nb l a c k w e l l 综合b v f u n t 的视网膜计算模型、g f u m a s 的 图形重写规则计算、j e n k i n s 和g l a s g o w 的空间几何学理论、w c i t r i n 的空间图形 l a m b d a 微分系统等人的工作，阐述了针对电子电路图表，图形用户界面。乐谱 分析等领域中非确定性问题采用定性仿真求解的思路i ”i 。 1 6 基于数据的结构化建模方法 中蜀科学技术大学硕：l 学位论文 基于数据的结构化建模是相当有吸引力的一项工作。现实中很多系统一般 只能获取它的实测数据，而缺乏其结构知识。意大利科学家l i t i n a i r o n i 提出了一 套将定性理论用于定量建模过程中的方法，在仅仅拥有实验数据的情况下，结合 领域知识，建立系统的结构化定量模型l 珏l 。理论的关键是利用了定性推理的系统 辩识方法。该系统辩识过程，就是由应用任务和先验知识构成模型空间，从模型 空间中提炼出一个初等模型子集，经过对初等模型子集测试结构并观测，不断改 进此模型子集以得到一个定量模型。再通过对定量模型的评估，使模型不断细化 直到通过评估而得到一个动力学系统模型。该模型对于数据的分析依赖于其智能 数据分析框架。在获得观测数据之后，先对其进行操作，得到预处理数据；另一 方面，基于定性推理的方法利用领域知识库和观测数据对模型几何形状进行辨 识，再结合基本物理特征知识获得观测的物理特征评估，作为定性响应与预处理 数据，结合领域知识从而完成了系统辨识。这种方法也已经成功应用于药理学的 实践当中。 1 7 空间定性推理方法 定性空间推理是人工智能学科处理常识性空阎知识的一种方法，其推理任务 包括：推导知识库中的隐含知识：针对给定的部分知识或特定的上下文回答询问； 维护一致性；获取新知识特别是认知图，定性场景描述的可视化。 空间知识的表示和处理是认知科学和人工智能研究的中心问题。由于空间知 识和空间推理本质上是定性的，因而定性空间推理是表示并处理空间知识的一种 有效方法，它的研究不仅具有重要的理论意义，同时也具有广泛的应用前景，近 几年受到普遍的重视i l 引。 1 7 1 发展过程 有关定性空间推理的研究工作始于7 0 年代末。1 9 7 7 年，d ek l e e r 在n e w t o n 系统中研究了滑车运动轨道的定性表示和推理方法同年，k u i p e r s 在博士论文 “大规模空间知识的表示”中提出了机器人导航的t o u r 模型，将空间知识组织成 感知运动、过程、拓扑和度量四个层次。1 9 7 8 年h a y e s 采用公理化的方法表示容 器的形状。1 9 8 0 年，f o r b u s 在f r o b 系统中提出了度量图式( m e t r i cd i a g r a m ) 和 场所描逻( p l a c ev o c a b u l a r y ) 的概念，并在以后的工作中明确指出p v 模型是空 间推理的基本框架。1 9 8 3 年，a l l e n 给出了基于区间的时态逻辑及基于约束传播 的推理算法。 8 0 年代后期，f o r b u s ，f a l t i n g 和n i e l s e n 等开展了定性运动学和定性空间推 理的研究工作，从此定性空间推理作为一个独立的研究领域日益受到人们的重 视。1 9 9 2 年，f r e k s a 提出了概念邻域的概念，指出了定性空间推理研究的重要性。 中周科学技术大学颁士学位论文 1 9 9 4 年，h e r n a n d e z 总结了定性空间推理的早期工作。近几年，a a a i 、i j c a l 和c o s i t 等会议上，定性空间推理研究工作团受到了重视，i j c a i 9 3 、i j c a i 9 5 和i j c a i 9 7 会议上还专门举办了有关定性空间推理的研讨专题。 现在，定性空间推理的研究涉及空间知识的拓扑、距离、朝向、形状、路径、 时间、运动、语言学、认知科学、空间描述的可视化等方面，对空间知识与时间、 因果性和动力学的集成也予以了足够的重视，探索出了公理化、代数、几何约束 满足、基于模型的推理等基本方法，并在导航、地理信息系统、工程设计、定性 物理、空间数据库和图形图像等领域进行了应用研究。 1 7 2 相关领域 与定性空间推理密切相关的领域是定性推理和空间推理。定性空间推理是定 性推理的重要组成部分，空间推理本质上是定性的。 i 定性推理 定性推理的主要特点包括：针对具体问题仅作必须的表示和推理；是未 确定的( u n d e r d e r m i n e d ) 和上下文有关的；允许以不同的粒度、在多个抽象层 次上进行推理：在知识不完全和不确定的情况下可以推导出结论。由此可见， 定性推理不仅能够表示、处理深层次知识，提供问题求解的上下文，还能够在知 识不完全和不确定的情况下给出闻题合理的解定性推理弥补了定量控理的不 足。 定性推理研究始于7 0 年代末8 0 年代初。初期工作注重基本方法的研究。总 结出了三个基本方法：e k n v i s o n ，q p t 和q p c q s i m 。后来提倡招定性推理应用到 实际任务中去。近几年，定性推理研究不仅有了实质性的应用，而且加强了基础 研究。在理论体系的完备性和有效性、定性和定量的集成、时间、空间、因果性、 以及概念领域结构等方面开展了深入的工作这些工作进一步揭示了定性和定量 的关系问题指出了粒度、抽象层次和观察者在定性推理中的核心地位。 国外，定性推理已在诊断、仿莫、地理信息系统、机器人导航以及图形图象 分析与处理等领域得到了应用，国内，定性推理也针对气象预报和控制等领域进 行了研究。 i i 空间推理 空间推理从几何、使用和功能三个方面研究空间知识的表示和处理、空间推 理的研究工作可分为四类：视觉对象的识别、认知图和路径规划、人类比喻的模 拟和定性物理的可视化。 8 0 年代，由于计算机图形学、计算机视觉、图象处理、机器入学、计算复杂 性、空间数据库、自然语言处理和专家系统等领域都需要研究空间知识的表示和 处理，因而形成了空间推理这一新的专门的研究领域。它的研究范围涉及计算机 中周科学技术大学碗士学位论文 视觉、空间任务规划、移动机器入导航、大型数据库的表示和索引技术、几何约 束推理和符号推理的集成、不确定空间证据的积累、多传感器数据的融合、运动 学等。 1 7 3 基本方法 定性空间推理的基本方法包括公理化方法、代数方法、几何约束满足方法和 基于模型的推理等。下面予以介绍。 i 公理化方法 空间知识的公理化描述是h a y e s 提倡的。这类工作大都以逻辑或部分学 ( m e r e l o l g y ) 为基础，选择一组基本的关系和谓词，建立一类空间概念或空间关 系的公理和推理规则，以此表示并处理定性的空间知识，其中有代表性的工作是 空间的r c c 理论。 r c c 理论是英国l e e d s 大学的r a n d e l l ，c o h n 和c u i 从1 9 8 9 年起逐渐创立的空间 逻辑理论，该理论基于连结定义了空间区域间的8 种关系，并把区域问的和、交、 补、以及凸包运算定义为公理系统中的函数i 把l 。其他研究者进一步发展了这一工 作。1 9 9 3 年g a l t o n 改进了a l l e n 提出的时态逻辑，使之可以处理连续性，并将 它同r c c 结合起来，提出了一种能够表示并处理时间、空间和运动的集成逻辑。 1 9 9 5 年a s b e r 和v i e u 年l j 用部分学和拓扑学概念建立了一个关于空间推理的具有 完整语义描述的完备公理系统。r c c 理论已在定性仿真领域得到了应用，并在拓 扑关系和形状的定性表示方面受到研究者的重视。 i i 代数方法 代数方法把空间关系作为项来处理。在构造出基本空间关系的原子复合表 后，既可以利用约束满足算法，通过实现关系集的复合运算完成推理。也可以建 立全部关系集复合运算的完全复合表。通过查表实现推理。 代数方法是a l l e n 在基于区问的时态逻辑理论中提出来的，后人将这一方法 应用到定性空间推理领域，并从空问关系集、代数运算及应用等方面发展了这一 方法i u l 。如：将一维区间推广到高维情形，容许空间关系是点、线和区域之间任 意关系，引入新的代数等。这些研究工作涉及到空间知识的各个方面，其中既有 理论分析探索性的工作，也有面向实际应用性的工作。 后来有二项重要工作：1 9 9 2 年，f r e s k a 在基于半区间的时态逻辑中，提出了 概念邻域、粗细知识的表示和推理的问题。1 9 9 4 年，r o h r i g 提出了空间推理的序 理论，他认为可以在空间关系集上建立序结构，利用序关系的传递性实现推理步 骤。这些工作发展了代数方法并对定性空间推理乃至定性推理的研究产生了影 响。 i i i 几何约束满足方法 中囝科学技术大学硕l 学位论文 在代数方法中，所应用的约束满足方法过于一般。不能有效地解决运动学问 题。几何约束满足方法从空间的几何性质、空间的层次结构以及空间的功能划分 来定义约束和相容性，从而能较有效地解决运动学中的问题。 1 9 9 0 年和1 9 9 2 年k r a m e r 提出了基于自由度分析的几何约束满足方法。这是 一相关于几何的符号推理技术，使用一组规划段来说明、改变几何体( g e o m ) 的配 置。规划段使用固定的一组操作和自由度，能够在满足新的约束的同时保留以前 的约束。1 9 9 4 年b h a n s a l i 和k r a m e r 进一步研究了规划段的自动生成问题i l 训。 表示并利用领域结构是几何约束满足方法的重要工作。1 9 9 3 年d uv e r d i e r 在利用几何约束满足方法研究空间规划问题时，表示并利用了位置关系和朝向关 系的序结构；t 9 9 4 年h e r n a n d e z 在利用几何约束满足方法研究位置关系时，考 虑了位置关系的概念邻域结构，提出了抽象固的表示方法。这些工作丰富发展了 几何约束满足方法。 i v 基于模型的推理方法 模型既指思想模型也指物理模型。基于模型的空间推理方法首先要给出相关 空间概念和空间关系的模型。下面介绍位形空间和符号投影串二种模型。位形空 间首先用于路径规划，以后广泛用于机械机构的推理。在位形空间中，运动物体 可表示成一个点，并用该物体的点集和其他物体点集的闵可夫斯基和来表示其它 物体。这样，路径规划问圈就归约为位形空间中点的可视性问题和位形空间的连 通性问题。定性空间推理进一步研究了位形空间的拓扑结构、定性表示方法以及 增量式的建构过程，并以位形空间为基础提出了定性运动学和定性空间推理的 m d p v 框架i j 。 1 8 小结 本章主要介绍了定性仿真和定性推理领域的方法论，最后部分着重介绍了定 性空间推理和仿真领域的流行研究方法。考虑在进行机械装置概念设计时，进行 空问定性推理，存在许多冗余的推理结果，同时利用q i s m 仿真算法，利用系统 本身动力学方程，进行约束传播和冗余消除将是一个行之有效的途径，将在余下 个章中进行详尽的介绍。 中国科学技术大学硕一j ：学位论文 第二章定性空间推理理论基础 我所提出的用于复杂机械装置概念设计中，在第二阶段动力学分析和第三阶 段动态整体性能分析是建立在多自由度机械装置振动传递矩阵和定性仿真q s i m 算法的基础之上，本章详细介绍q s i m 算法及多自由度动力学系统微分方程的建 立和振动的传递矩阵法。 2 1q s i m 算法 q s i m 由美国德州大学的b j k u i p e r s 于1 9 8 6 年的国际人工智能杂志上首次 提出，发展至今，已成为定性仿真领域应用最为广泛的一个算法。它总结了前人 的思想( 如d ek l e e r ，f o r b u s 等人) 。并以严格的形式定义了定性仿真的算法。 它是一种面向约束的方法，从一个定性约束集和一个初始状态出发，预测系统未 来所有可能的行为，作为微分方程的抽象川。 系统的定性仿真是从己知的系统结构和一个初始状态出发，产生一个有向图。 该有向图由系统未来可能的状态和状态之间的直接后继关系组成，系统的行为就 是有向图中从初始状态出发的一条路径。 系统的结构由一个代表系统物理参数( 连续、可微的实函数) 的符号集合和 描述这些物理参数问相互关系的一个约束方程集合组成。这些约束是四个基本的 数学关系：a d d ( x ，y ，z ) 、m u l t ( x ，y ，z ) 、d e r i v ( x ，y ) 、m i n u s ( x ，y ) 和 两个函数之问的定性关系：m + ( x ，y ) 、m 一( x ，y ) 。约束方程可以从普通微分 方程映像过来，也可以直接从系统的结构中得出。 每个物理参数都是时间的连续、可微的实值函数，它在任何给定时间点上的 值是按照它和一个有序路标值集合的关系确定的。路标值可以用数字或符号表 示，路标值之间的顺序关系是它们的本质特征。随着定性仿真的进行。可以发现 和使用新的路标值。一个参数的定性状态由它与路标值之间的顺序关系( 或等于 一个路标值或在两个路标值之间) 和它的变化方向两部分组成。 在定性仿真中，时间被表示为以符号表示的可区分时间点的集合。当前的时 间，要么是在可区分时问点上，要么是在两个可区分时间点之间。所有的可区分 时刚点是在定性仿真过程中产生的。 系统的初始状念是通过组成系统的每个物理参数的定性状态定义的。定性仿 真产生每个物理参数定性状态的所有可能转换，然后应用约束方程过滤掉不合 理的组合，如果当前状态有多个后继状态，则仿真产生分支。 两个定性状态相致的充分必要条件是所有的参数都等于同样的路标值，而 中国科学技术大学颂士学位论文 且两个状态中，所有的参数变化方向都一致。如果一个状态的后继状态与它的一 个祖先状态一致。则导致一个循环。 2 1 1 基本概念 一个物理系统是通过一系列实值参数来标志的，定义每一个参数为一个函 数：f ： 口，b 】一r + ，只+ 气鹎+ 叼。用尉代替传统的r 是为了把o o 作为一个路标 值处理。在定性仿真中，我们讨论的函数都是所谓的可推理函数( r e a s o n a b l e f u n c t i o n ) 。 可推理函数定义为：对于陋，b 】舻，厂：陋b 】一r