定性模型推理xy智能科學(xué)課件

1、定性推理史忠植中國科學(xué)院計算技術(shù)研究所高級人工智能第四章第1頁，共82頁。2022/8/5史忠植 高級人工智能2內(nèi)容提要4.1 概述4.2 定性推理的基本方法4.3 定性模型推理 4.4 定性進(jìn)程推理 4.5 定性仿真推理4.6 代數(shù)方法4.7 幾何空間定性推理第2頁，共82頁。什么是定性推理？ 定性推理(qualitative reasoning)是從物理系統(tǒng)、生命系統(tǒng)的結(jié)構(gòu)描述出發(fā),導(dǎo)出行為描述, 以便預(yù)測系統(tǒng)的行為并給出原因解釋。定性推理采用系統(tǒng)部件間的局部結(jié)構(gòu)規(guī)則來解釋系統(tǒng)行為, 即部件狀態(tài)的變化行為只與直接相鄰的部件有關(guān)。第3頁，共82頁。2022/8/5史忠植 高級人工智能4 概述

2、1952年 Simmons提出定性分析的因果關(guān)系。1977年 Rieger 發(fā)表了因果仿真的論文。1984年 “Artificial Intelligence”雜志第24卷出版了定性推理專輯, 刊載了 de Kleer, Forbus 和Kuipers對定性推理奠基性的 文章, 這標(biāo)志著定性推理開始走向成熟。1986年 Iwasaki和Simmons發(fā)表了“Causality in Device Behavior” 的文章。1993年 “Artificial Intelligence”雜志第59卷又發(fā)表了一組文章， 回顧十年前這幾位定性推理奠基人所做的工作。第4頁，共82頁。2022/8/5史

3、忠植 高級人工智能5 概述de Kleer的定性模型方法de Kleer 1984Forbus的定性進(jìn)程方法Forbus 1984Kuipers 定性仿真法Kuipers 1984第5頁，共82頁。2022/8/5史忠植 高級人工智能6 概述Davis 提出從結(jié)構(gòu)描述出發(fā)進(jìn)行故障論斷的方法Reiler提出從基本原理出發(fā)進(jìn)行故障診斷的方法Williams把定量運(yùn)算和定性推理相結(jié)合建立了一個 混合代數(shù)系統(tǒng)Q1Iwasaki 和 Simmons把經(jīng)濟(jì)學(xué)、熱力學(xué)中所用的因果 關(guān)系形式化Weld在分子生物學(xué)中設(shè)計了定性模擬程序 第6頁，共82頁。2022/8/5史忠植 高級人工智能7定性推理的基本方法

4、人類對物理世界的描述、解釋, 常是以某種直觀的定性方法進(jìn)行的,很少使用微分方程及具體的數(shù)值描述, 如人們在騎自行車時, 為了避免摔倒和撞車, 并不需要使用書本上的運(yùn)動方程, 而是針對幾個主要參量的變化趨勢給予粗略的、直觀的, 但大體上準(zhǔn)確的描述, 這就夠了。第7頁，共82頁。2022/8/5史忠植 高級人工智能8定性推理的基本方法 一般分析運(yùn)動系統(tǒng)行為的標(biāo)準(zhǔn)過程可分為三個步驟： (1) 決定描述對象系統(tǒng)特征的量。 (2) 用方程式表示量之間的相互關(guān)系。 (3) 分析方程式，得到數(shù)值解。第8頁，共82頁。2022/8/5史忠植 高級人工智能9定性推理的基本方法這類運(yùn)動系統(tǒng)行為的問題用計算機(jī)進(jìn)行求

5、解時，將面臨如下三個問題： (1) 步驟(1)(2)需要相當(dāng)多的知識，并且要有相應(yīng)的算法。 (2) 有的場合對象系統(tǒng)的性質(zhì)很難用數(shù)學(xué)式子表示。 (3) 步驟(3)得到了數(shù)值解，但是對象系統(tǒng)的行為并不直觀明了。第9頁，共82頁。2022/8/5史忠植 高級人工智能10定性推理的基本方法為了解決第二、第三個問題，定性推理一般采用下列分析步驟： (1) 結(jié)構(gòu)認(rèn)識：將對象系統(tǒng)分解成部件的組合。 (2) 因果分析：當(dāng)輸入值變化時，分析對象系統(tǒng)中怎樣傳播。 (3) 行為推理：輸入值隨著時間變化，分析對象系統(tǒng)的內(nèi)部狀態(tài)怎樣變化。 (4) 功能說明：行為推理的結(jié)果表明對象系統(tǒng)的行為，由此可以說明對象系統(tǒng)的功能

6、。第10頁，共82頁。2022/8/5史忠植 高級人工智能11定性推理的基本方法定性推理的觀點大體上可這樣來理解: 忽略被描述對象的次要因素, 掌握主要因素簡化問題的描述。 將隨時間 t連續(xù)變化的參量 x(t) 的值域離散化為定性值集合, 通常變量 x的定性值 x定義為 依物理規(guī)律將微分方程轉(zhuǎn)換成定性(代數(shù))方程, 或直接依物理 規(guī)律建立定性模擬或給出定性進(jìn)程描述。 最后給出定性解釋第11頁，共82頁。2022/8/5史忠植 高級人工智能12定性模型推理de Kleer研究解決經(jīng)典物理問題需要哪些知識及如何建立問題求解系統(tǒng)。他提出的定性模型方法所涉及的物理系統(tǒng)是由管子、閥門、容器等裝置組成,

7、約束條件(定性方程)反映在這些裝置的連接處, 依定性方程給出定性解釋。 為將代數(shù)方程、微分方程定性化, 首先需定義變量的定性值集合以及相應(yīng)的定性運(yùn)算。第12頁，共82頁。2022/8/5史忠植 高級人工智能13定性模型推理定性值集合是一個離散集合, 其元素是由對數(shù)軸的劃分而得到的, 通常把數(shù)軸 (,)劃分成 (,0) , 0,(0, ) 三段, 規(guī)定定性值集合為 ,0, 變量 x的定性值 x如下定義:另外用 x表示 dx/dt的定性值, 也即第13頁，共82頁。2022/8/5史忠植 高級人工智能14定性模型推理 xy-0+-?0-0+?+x y x y-0+-+0-0000+-0+x y 其

8、中: 符號？表示不確定或無定義。 第14頁，共82頁。2022/8/5史忠植 高級人工智能15定性模型推理下面給出和 的運(yùn)算規(guī)則。設(shè) e1, e2是公式, 則有：0 e1e10 e10+ e1e1- e1-e1第15頁，共82頁。2022/8/5史忠植 高級人工智能16定性模型推理使用下列規(guī)則，可將運(yùn)算符+、轉(zhuǎn)換成、： e1e2 e1 e2e1e2 e1 e2第16頁，共82頁。2022/8/5史忠植 高級人工智能17壓力調(diào)節(jié)器壓力調(diào)節(jié)器是通過彈簧來控制閥門流量, 以使流量為某一設(shè)定值而不受流入的流量和負(fù)載變化的影響。根據(jù)物理學(xué)有第17頁，共82頁。2022/8/5史忠植 高級人工智能18壓力

9、調(diào)節(jié)器其中 Q是通過閥門的流量,P是壓力, A是閥門開啟的面積, 而C是常系數(shù),是流體的質(zhì)量密度。按照運(yùn)算和轉(zhuǎn)換規(guī)則而得到定性方程：Q = PQ = A + P (如果A 0)第18頁，共82頁。2022/8/5史忠植 高級人工智能19壓力調(diào)節(jié)器OPEN狀態(tài)A = Amax定性方程P = 0P = 0WORKING 狀態(tài)0A Atemperature(dst) src 溫度高于dst溫度第25頁，共82頁。2022/8/5史忠植 高級人工智能26定性進(jìn)程推理 Relations: 一組參量關(guān)系 Let flow-rate be a quantity flow-rate (熱流量)是一個數(shù)量 A

10、flow-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),而且是負(fù)影響 1(heat (dst), Aflow-rate) flow-rate的值直接影響 heat(dst),而且是正影響第26頁，共82頁。2022/8/5史忠植 高級人工智能27定性進(jìn)程推理演繹過程 在進(jìn)程定性推理中，其演繹過程如下： (1

11、) 選進(jìn)程。 對一組已知的個體來說, 在進(jìn)程表中依各進(jìn)程對個體的說明找出可能出現(xiàn)的那些進(jìn)程例PI。 (2) 確定激活的 PI。依前提條件、數(shù)量條件確定每個 PI的狀態(tài)。滿足這些條件的為激活的 PI , 激活的 PI 叫進(jìn)程結(jié)構(gòu)。 (3) 確定量的變化。 個體的變化由相應(yīng)量的 Ds 值來表示。量的變化可由進(jìn)程直接影響，也可由Q間接影響。 (4) 確定進(jìn)程結(jié)構(gòu)變化。量的變化將會引起進(jìn)程結(jié)構(gòu)的變化,確定這種變化也叫限制分析, 這樣對一個物理過程的描述便由 (1)建立的 PI 進(jìn)入了下一個 PI 。重復(fù)(1)(4) 的步驟便可給出一個物理過程的一串進(jìn)程描述。第27頁，共82頁。2022/8/5史忠植

12、高級人工智能28定性進(jìn)程推理第28頁，共82頁。2022/8/5史忠植 高級人工智能29定性仿真推理 1984年 Kuipers 發(fā)表了“因果性的常識推理：從結(jié)構(gòu)導(dǎo)出行為”論文。這篇論文建立了一種定性仿真推理的框架, 簡單地給出了從常微分方程的抽象而得的定性結(jié)構(gòu)和定性行為表示方法。隨后，1986年AI雜志又刊登了Kuipers“定性仿真”一文，文中明確了抽象關(guān)系，提出用于定性仿真的QSIM算法，并用抽象關(guān)系證明了其有效性和不完備性。這兩篇文章奠定了定性仿真的基礎(chǔ)。演繹過程 第29頁，共82頁。2022/8/5史忠植 高級人工智能30定性仿真推理 定性仿真是從結(jié)構(gòu)的定性描述出發(fā)來導(dǎo)出行為描述。直

13、接用部件的參量作為狀態(tài)變量來描述物理結(jié)構(gòu), 定性約束直接由物理規(guī)律得到, 把一個參量隨時間的變化視作定性的狀態(tài)序列, 求解算法是從初始狀態(tài)出發(fā), 生成各種可能的后續(xù)狀態(tài), 進(jìn)而通過一致性過濾, 重復(fù)該過程直到?jīng)]有新狀態(tài)出現(xiàn)。 定性仿真結(jié)構(gòu)描述由系統(tǒng)的狀態(tài)參數(shù)和約束關(guān)系組成。認(rèn)為參數(shù)是時間的可微函數(shù), 約束是參數(shù)間的二元或多元關(guān)系。如速度的導(dǎo)數(shù)是加速度。表為 DERIV(Vel, acc)。f = ma 表為 MULT(m,a,f), f 隨 g單調(diào)增加表為 M+(f,g),f 隨 g單調(diào)減少, 表為 M-(f,g)。第30頁，共82頁。2022/8/5史忠植 高級人工智能31定性仿真推理行為描

14、述關(guān)心參量的變化。假設(shè)參量f(t)是a,b到, 的可微函數(shù)。f的界標(biāo)值是一個有限集合, 至少含有 f(a),f(b)。集合 t|t a,b f(t) 是界標(biāo)值 的元素稱作區(qū)別點。 定義4.1 設(shè) l1l2 lk是f: a,b -, 的界標(biāo)值。對任意t a,b, f 在 t的定性狀態(tài) QS(f,t)規(guī)定為有序?qū)?,定義如下:第31頁，共82頁。2022/8/5史忠植 高級人工智能32定性仿真推理第32頁，共82頁。2022/8/5史忠植 高級人工智能33定性仿真推理 定義 4.2 設(shè) ti, ti+1是相鄰的區(qū)分點,規(guī)定 f在 (ti,ti+1)內(nèi)的定性狀態(tài) QS(f, ti, ti+1) 仍為

15、 QS(f,t) 其中 t(ti,ti+1) 第33頁，共82頁。2022/8/5史忠植 高級人工智能34定性仿真推理定義 4.3 f 在 a,b上的定性行為是f的定性狀態(tài)序列QS(f,t0), QS(f,t0,t1), QS(f, t1), ,QS(f, tn)。其中 ti(i=0,1,n)為所有的區(qū)分點, 且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 區(qū)分點并集的元素。 第34頁，共

16、82頁。2022/8/5史忠植 高級人工智能35定性仿真推理定性狀態(tài)轉(zhuǎn)換 在定性仿真中，定性狀態(tài)轉(zhuǎn)移是經(jīng)常遇到的。假設(shè) f是可微函數(shù),f從一個定性狀態(tài)轉(zhuǎn)換到另一個定性狀態(tài)必須遵守介值定理和中值定理。定性狀態(tài)轉(zhuǎn)換有兩類：一類是P 轉(zhuǎn)換，該類轉(zhuǎn)換是從時間點到時間區(qū)間；另一類是I 轉(zhuǎn)換，它是從時間區(qū)間到時間點的轉(zhuǎn)換。下面給出轉(zhuǎn)換表:第35頁，共82頁。2022/8/5史忠植 高級人工智能36定性仿真推理P轉(zhuǎn)換QS(f,ti)QS(f,ti,ti+1)P1P2P3P4P5P6P7第36頁，共82頁。2022/8/5史忠植 高級人工智能37定性仿真推理I 轉(zhuǎn)換QS(f,ti,ti+1)QS(f,ti+1

17、)I1I2I3I4I5I6I7I8I9第37頁，共82頁。2022/8/5史忠植 高級人工智能38定性仿真推理 QSIM算法可對系統(tǒng)的行為進(jìn)行定性仿真。首先將初始狀態(tài)送入 ACTIVE表中, 然后重復(fù) (1)(6)直至 ACTIVE 表空為止。算法 4.1 QSIM算法。 (1) 從 ACTIVE表中選一狀態(tài)。 (2) 對每個參數(shù)按轉(zhuǎn)換表找出所有可能的轉(zhuǎn)換。 (3) 對約束中變元的轉(zhuǎn)換生成二元組, 三元組集合, 依約束關(guān)系做一致性濾波。 (4) 對有公共變元的約束, 對元組進(jìn)行組對, 再對組對的元組做一致性濾波。第38頁，共82頁。2022/8/5史忠植 高級人工智能39定性仿真推理(5) 從

18、剩下的元組生成所有可能的全局解釋。每個解釋生成 一個新狀態(tài)作為當(dāng)前狀態(tài)的后繼狀態(tài)。(6) 對新狀態(tài)做全局濾波, 剩下的狀態(tài)送入 ACTIVE 表。全局 濾波排除下列狀態(tài)： 無變化情形: 如 I1, I4, I7; 循環(huán)情形: 新狀態(tài)與某個前輩狀態(tài)相同; 發(fā)散情形: 某參數(shù)值為, 這時當(dāng)前時間點必為結(jié)束點。第39頁，共82頁。2022/8/5史忠植 高級人工智能40幾何空間定性推理空間定性推理是對幾何形狀或者運(yùn)動性質(zhì)進(jìn)行定性推理，首先需對空間位置及運(yùn)動方式進(jìn)行定性表示，進(jìn)而對幾何形狀及運(yùn)動性質(zhì)進(jìn)行推理研究及預(yù)測分析，并作出邏輯解釋?？臻g定性推理是通過定義一組空間并尋找這些關(guān)系間的聯(lián)系來進(jìn)行的。目

19、前主要的研究是針對空間定性建模方式、 空間形狀及關(guān)系的定性表示和定性技術(shù)的形式化等, 產(chǎn)生解釋理論, 但總體來看與解決工程問題距離尚遠(yuǎn)。第40頁，共82頁。2022/8/5史忠植 高級人工智能41幾何空間定性推理將Allen的時態(tài)邏輯Allen 1984與Randall的空間邏輯Randall 1992結(jié)合起來，形成空間、時間、連續(xù)運(yùn)動的表達(dá)邏輯。 另外從空間定性推理派生出空間規(guī)劃理論, 可用于為一組幾何對象尋找滿足一組約束的分布設(shè)計, 有關(guān)方法主要用于設(shè)計自動化、定性建模等領(lǐng)域。 在這一領(lǐng)域已取得了一些較有實際意義的成果, 如約束滿足問題(CSP)求解理論, 而實際上很多空間定性規(guī)劃都是一個

20、幾何約束滿足問題(GCSP)。第41頁，共82頁。2022/8/5史忠植 高級人工智能42幾何空間定性推理1992年由Randell等人建立起來的RCC 空間時間邏輯是用于對空間問題進(jìn)行可達(dá)性的展望, 并已程序?qū)崿F(xiàn)。與Kuipers的QSIM方法類似, 基于RCC 邏輯的仿真算法也是從對系統(tǒng)進(jìn)行結(jié)構(gòu)性的描述開始的, 系統(tǒng)將初始狀態(tài)作為生成樹的根結(jié)點, 可能的行為則是樹中從根結(jié)點到葉結(jié)點的路徑。第42頁，共82頁。2022/8/5史忠植 高級人工智能43Qualitative Spatial ReasoningQualitative reasoningmodelling the continuo

21、us reality in manageable entitiessolution for quantitative problems that are not computableTwo approachesartificial intelligence GI Science1992 Randell, Cui, Cohndatabases GI Systems1991 Egenhofer, FranzosaGISRUK 2004 University of East AngliaSlide 5 of 20幾何空間定性推理第43頁，共82頁。2022/8/5史忠植 高級人工智能44RCCRCC

22、 =Region Connection CalculusRandell, Cui, Cohntopological relations of polygonsqualitative modellingdisjoint, meet, overlapconceptual neighbourhood-diagramGISRUK 2004 University of East AngliaSlide 6 of 20RCC幾何空間定性推理第44頁，共82頁。2022/8/5史忠植 高級人工智能45RCC - diagramGISRUK 2004 University of East AngliaSlid

23、e 7 of 20Conceptual neighbourhood diagram幾何空間定性推理第45頁，共82頁。Qualitative Calculi The success of qualitative reasoning relies on choice of good qualitative calculiA q-calculus is generated by a set of jointly exhaustive and pairwise disjoint (JEPD) relations on the domain of discourse第46頁，共82頁。2022/8/5

24、史忠植 高級人工智能47RCC8 Topological AlgebraRegions are nonempty regular closed subsets of a connected regular topological space (e.g. Euclidean space)Basic RCC8 relations are defined on regions第47頁，共82頁。2022/8/5史忠植 高級人工智能48RCC8 Basic Relations DC EC PO TPP NTPP EQdisjoint meet overlap covered_by contained_

25、by equalBABABABAA=BBA第48頁，共82頁。2022/8/5史忠植 高級人工智能49Directional ModelPoint-basedProjection-basedCone-basedRegion-basedRectangle AlgebraDirection-Relation Matix Model第49頁，共82頁。2022/8/5史忠植 高級人工智能50Cone-Based Cardinal DirectionsFrank AU. Qualitative spatial reasoning: Cardinal directions as an example.

26、IJGIS, 1996,10:269290 第50頁，共82頁。2022/8/5史忠植 高級人工智能51Projection-Based Card. DirectionsFrank AU. Qualitative spatial reasoning: Cardinal directions as an example. IJGIS, 1996,10:269290第51頁，共82頁。2022/8/5史忠植 高級人工智能52Rectangle AlgebraThe rectangle relation between two boxes A,B is described by the interv

27、al relations between the x- and y-projections of A, BABABA(o,oi)BA(m,d)B第52頁，共82頁。2022/8/5史忠植 高級人工智能53Direction-Relation MatrixR.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 M

28、BR of A.A5A8A7A6A3A2A1A4第53頁，共82頁。2022/8/5史忠植 高級人工智能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.第54頁，共82頁。2022/8/5史忠植 高級人工智能55Reasoning with q-CalculiConstraintsGiven a q-calclus R, and a relati

29、on r in R, (x r y) express a constraint between two variables x and yCompositionGiven two constraints (x r y) & (y s z), we want to know the strongest relation t s.t. (x t z) is possiblet is called the weak composition of r and s第55頁，共82頁。2022/8/5史忠植 高級人工智能56Reasoning with q-CalculiGiven a constrain

30、t networkN=xi rij xj,is N satisfiable? This is the satisfaction problem.For S a subset of the whole algebra, we write RSAT(S) for the problem of deciding satisfaction of networks with constraints over S.第56頁，共82頁。2022/8/5史忠植 高級人工智能57Reasoning with q-CalculiThe satisfaction problems are often NP hard

31、, e.g. RSAT(IA) and RSAT(RCC8) are NPCReasoning problems in IA and RCC8 have been investigated thoroughly, and many useful techniques have been developed.第57頁，共82頁。2022/8/5史忠植 高級人工智能58Local constraint solving techniques may be useful, e.g. path-consistency algorithm (PCA) can solve RSAT(S) if S is t

32、he maximal tractable subalgebra of IAReasoning with q-Calculi第58頁，共82頁。2022/8/5史忠植 高級人工智能59幾何空間定性推理空間邏輯的基礎(chǔ)在于假設(shè)一個原語性的二元關(guān)系 C(x,y)。其中x,y表示兩個區(qū)域(regiong), 謂詞C表示共享一個以上公共點。也就是指相接觸,它具有自反性、對稱性。 1. 八個基本關(guān)系的定義 使用關(guān)系C(x,y), 一組基本的二元關(guān)系可以被定義為： (1) DC(x,y): 表示兩區(qū)域不相接觸。 (2) EC(x,y): 表示兩區(qū)域外部接觸。 (3) PO(x,y): 表示兩區(qū)域部分覆蓋。第5

33、9頁，共82頁。2022/8/5史忠植 高級人工智能60幾何空間定性推理 (4) =(x,y): 表示兩區(qū)域完全相同。 (5) TPP(x,y): 表示$x$是$y$的一個嚴(yán)格部分并且$x,y$相切(內(nèi)切)。 (6) NTPP(x,y): 表示$x$是$y$的一個嚴(yán)格部分但$x,y$不相接觸(包含而不相切)。 (7) TPP(x,y): 表示$y$是$x$的一個嚴(yán)格部分并且$x,y$相切。 (8) TPP(x,y): 表示$y$是$x$的一個嚴(yán)格部分但$x,y$不相切接觸。第60頁，共82頁。2022/8/5史忠植 高級人工智能61幾何空間定性推理基本關(guān)系間的聯(lián)系這種空間邏輯與Allen的邏輯

34、相類似, 也使用預(yù)計算的傳遞性表來表示二元關(guān)系之間可能的變化聯(lián)系, 在表中從任一關(guān)系R3(a,c)可查找出所有可能的二元關(guān)系R1(a,b)與R2(b,c)。這一表對定性仿真是很有用的。然而,近年的研究中尚未給出這類傳遞性表的建立算法。但Randell提到在其仿真程序中使用了該表來檢驗展望過程中狀態(tài)描述的一致性。第61頁，共82頁。2022/8/5史忠植 高級人工智能62幾何空間定性推理基本狀態(tài)間的相互轉(zhuǎn)換 根據(jù)兩個區(qū)域的形狀不同,上述八個基本關(guān)系可被分為6個子集: (1) DC EC PO = (2) DC EC PO TPP (3) DC EC PO TPP-1 (4) DC EC PO T

35、PP NTPP (5) DC EC PO TPP-1 NTPP-1 (6) DC EC PO第62頁，共82頁。2022/8/5史忠植 高級人工智能63幾何空間定性推理空間時間關(guān)系描述 1.方位性狀態(tài)和運(yùn)動性狀態(tài) Galton 將八個RCC 關(guān)系分為方位性狀態(tài)(position state)和運(yùn)動性狀態(tài)(motion state)，并且使用Allen 關(guān)于時間關(guān)系的一些邏輯化的形式, 給出了這種分類的定義。首先介紹一下Galton使用的概念、謂詞和函數(shù)。 (1) 對時間的描述分為區(qū)間和時刻; (2) 狀態(tài)存在的描述謂詞: Holds-on(s,i) 表示在區(qū)間i上存在狀態(tài)s;Holds-at(

36、s,t) 表示在時刻t存在狀態(tài)s; (3) 謂詞 Div(t,i) 表示時刻t在區(qū)間i上; (4) 函數(shù)inf(i)表示在區(qū)間i的開始時刻; (5) 函數(shù)sup(i)表示在區(qū)間i的結(jié)束時刻;第63頁，共82頁。2022/8/5史忠植 高級人工智能64幾何空間定性推理空間時間關(guān)系描述方位性狀態(tài)。 如果狀態(tài)s滿足 i (Holds-on(s,i) Holds-at(s,inf(i) Holds-at(s,sup(i)即如果一個狀態(tài)s在時間區(qū)間i上存在, 則在該區(qū)間的起止時刻這個狀態(tài)都存在。具有這一性質(zhì)的狀態(tài)稱為方位性狀態(tài)。 第64頁，共82頁。2022/8/5史忠植 高級人工智能65幾何空間定性推

37、理空間時間關(guān)系描述運(yùn)動性狀態(tài)。如果狀態(tài)s滿足t (Holds-on(s,t) i (Div(t,i) Holds-on(s,i)即如果在某時刻t有狀態(tài)s, 那么一定存在包含這一時刻的某一區(qū)間使$s$在整個區(qū)間都存在, 具有這一性質(zhì)的狀態(tài)稱為運(yùn)動性狀態(tài)。第65頁，共82頁。2022/8/5史忠植 高級人工智能66幾何空間定性推理空間時間關(guān)系描述 擾動原理 Galton根據(jù)這種分類給出了擾動原理, 這是對空間狀態(tài)在時域變化進(jìn)行描述的一組公理體系： 定義 4.5 擾動(perturbation)。如果RCC關(guān)系R與R滿足條件: t(Holds-at(R(a,b),t)(i(Holds-on(R(a,

38、b),i) (inf(i)=t) (sup(i)=t)即如果時刻t有狀態(tài)R,且有一個區(qū)間i開始或結(jié)束于t區(qū)間i上的狀態(tài)為R。此時稱R與R 互為擾動。 擾動原理: 每個RCC關(guān)系是它自身的擾動, 另外一個靜止性的狀態(tài)只能與一個運(yùn)動性的狀態(tài)互擾動, 反之亦然(只討論剛體)。第66頁，共82頁。2022/8/5史忠植 高級人工智能67幾何空間定性推理 Randell算法假設(shè)初始狀態(tài)S0 已放入狀態(tài)集合S中。 (1) 如果S空則停止; (2) 從S中選出狀態(tài)Si, 且移出; (3) 如果Si 為不一致狀態(tài)將轉(zhuǎn)(2); (4) 應(yīng)用狀態(tài)約束選擇可用變換規(guī)則; (5) 用所選出的規(guī)則產(chǎn)生可能的下一個狀態(tài)集

39、合; (6) 使用添加與刪除規(guī)則; (7) 進(jìn)行狀態(tài)內(nèi)約束檢查; (8) 將剩下的狀態(tài)加入S并轉(zhuǎn)(1)。第67頁，共82頁。2022/8/5史忠植 高級人工智能68空間推理的研究進(jìn)展對空間推理的許多研究方向進(jìn)行分類、歸納和整理之后得到的主要研究方向是： (1) 空間數(shù)據(jù)庫的精度。 (2) 空間關(guān)系語言。 (3) 空間推理與地理信息系統(tǒng)。 (4) 空間決策支持系統(tǒng)。 (5) 空間數(shù)據(jù)的不確定性處理。 (6) 形式化的繪圖知識。 (7) 時空推理。第68頁，共82頁。2022/8/5史忠植 高級人工智能69 (8) 定性空間推理。 (9) 空間推理的用戶界面。 (10) 基于案例(CASE-BAS

40、ED) 的空間推理. (11) 空間推理的認(rèn)知問題。 (12) 空間推理與機(jī)器人視覺。 (13) 常識推理。 (14) 區(qū)域連接演算RCC-8?？臻g推理的研究進(jìn)展第69頁，共82頁。2022/8/5史忠植 高級人工智能70大量的文獻(xiàn)空間推理的研究熱點：時空推理STSR (spatio-temporal spatial reasoning)、定性空間推理QSR (qualitative spatial reasoning)地理信息系統(tǒng)空間推理的研究熱點第70頁，共82頁。2022/8/5史忠植 高級人工智能71時空推理 當(dāng)今世界是在漫長的歷史長河中，歷經(jīng)滄桑演變進(jìn)化而來的。世界中的任何事物和現(xiàn)象

41、都遵循著誕生、生長，直至消失或死亡的自然規(guī)律。同樣，現(xiàn)代文明和科技的進(jìn)步無不是人類歷史的經(jīng)驗積累和結(jié)晶。人類在認(rèn)識和解釋當(dāng)今世界事物和現(xiàn)象時,不但渴望甚至必須了解它們的過去,而且希望預(yù)測未知的將來,以便在必要的時候采取一定措施,使人類社會朝著美好的方向發(fā)展。在這綿延不斷的歷史軌跡中，無不打上了時間的烙印，因此,探索適宜的工具和方法,沿著時間脈絡(luò)研究和推理客觀世界內(nèi)在機(jī)制和時空發(fā)展規(guī)律,就顯得十分重要?？臻g推理的研究熱點第71頁，共82頁。2022/8/5史忠植 高級人工智能72 總的來說，影響空間推理結(jié)果的因素包括空間因素和時間因素。所謂時空推理是指在空間推理過程中添加時間因素。地表、地下和大

42、氣等空間對象的狀態(tài)不僅受到空間因素的影響, 同時, 從一個漫長的時間過程來看，也必將受到時間因素的影響?？梢哉f, 時空推理是更為一般的空間推理, 或者可以說空間推理是時空推理的一個特例。目前, 時空推理方面的研究還處于起步階段。下面, 我簡單地介紹一些權(quán)威學(xué)者對時空推理的認(rèn)識和他們提出的時空推理模型?？臻g推理的研究熱點第72頁，共82頁。2022/8/5史忠植 高級人工智能73 1. Richard A. Block 在他的論文“Psychological Time and the Processing of Spatial Information”中指出：“與其說空間為時間提供了一個框架，不

43、如說時間感知為空間感知提供了一個框架”?！拔恢煤统掷m(xù)時間之間、個人經(jīng)驗和常識之間以及期望和回顧之間存在重要的區(qū)別”。他提出了上下文時間模型， 并且把它擴(kuò)展到空間， 模型著眼于哪些變量對持續(xù)時間和其他種類的時間體驗之間及行為和判斷之間的相互作用有影響，這些變量包括實驗者的特征、時間周期、時間周期上的活動和時間行為。空間推理的研究熱點第73頁，共82頁。2022/8/5史忠植 高級人工智能74 2. A. G. Cohn, Z. Cui, D. A. Randell 在他們的論文“Exploiting Temporal Continuity in Qualitative Spatial Calcu

44、lus”中提出了一個空間知識推理的邏輯框架, 目的是為人工智能系統(tǒng)的表示和推理提供一個形式上的時間和空間的公理理論。 他們的形式方法可以用于時間或空間區(qū)域, 并且提供了一套基本關(guān)系和推理機(jī)。 特別是他們定義了基本關(guān)系的合成表, 可以用于檢驗時空約束, 甚至用于檢驗區(qū)域特征的時空演變。空間推理的研究熱點第74頁，共82頁。2022/8/5史忠植 高級人工智能75 3. 在論文“Temporal Dynamics and Geographic Information System s”中, Stephen Stead 認(rèn)為, 現(xiàn)實世界是沿著一條根據(jù)數(shù)值的時間范圍劃分的有唯一順序的時間路線運(yùn)轉(zhuǎn)。 他借鑒考古應(yīng)用中的為時間建模的方法, 提出了標(biāo)準(zhǔn)切割時間技術(shù)方法, 存儲風(fēng)景快照作為解釋背景。 S