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

定性推理史忠植中國(guó)科學(xué)院計(jì)算技術(shù)研究所高級(jí)人工智能第四章定性推理史忠植高級(jí)人工智能2023/9/12史忠植高級(jí)人工智能2內(nèi)容提要4.1概述4.2定性推理的基本方法4.3定性模型推理4.4定性進(jìn)程推理4.5定性仿真推理4.6代數(shù)方法4.7幾何空間定性推理2023/8/3史忠植高級(jí)人工智能2內(nèi)容提要4.1概述什么是定性推理？

定性推理(qualitativereasoning)是從物理系統(tǒng)、生命系統(tǒng)的結(jié)構(gòu)描述出發(fā),導(dǎo)出行為描述,以便預(yù)測(cè)系統(tǒng)的行為并給出原因解釋。定性推理采用系統(tǒng)部件間的局部結(jié)構(gòu)規(guī)則來(lái)解釋系統(tǒng)行為,即部件狀態(tài)的變化行為只與直接相鄰的部件有關(guān)。什么是定性推理？定性推理(qualitative2023/9/12史忠植高級(jí)人工智能4

概述1952年Simmons提出定性分析的因果關(guān)系。1977年Rieger發(fā)表了因果仿真的論文。1984年“ArtificialIntelligence”雜志第24卷出版了定性推理專(zhuān)輯,

刊載了deKleer,Forbus和Kuipers對(duì)定性推理奠基性的文章,這標(biāo)志著定性推理開(kāi)始走向成熟。1986年Iwasaki和Simmons發(fā)表了“CausalityinDeviceBehavior”的文章。1993年“ArtificialIntelligence”雜志第59卷又發(fā)表了一組文章，回顧十年前這幾位定性推理奠基人所做的工作。2023/8/3史忠植高級(jí)人工智能4概述1952年2023/9/12史忠植高級(jí)人工智能5

概述deKleer的定性模型方法[deKleer1984]Forbus的定性進(jìn)程方法[Forbus1984]Kuipers定性仿真法[Kuipers1984]2023/8/3史忠植高級(jí)人工智能5概述deKlee2023/9/12史忠植高級(jí)人工智能6

概述Davis提出從結(jié)構(gòu)描述出發(fā)進(jìn)行故障論斷的方法Reiler提出從基本原理出發(fā)進(jìn)行故障診斷的方法Williams把定量運(yùn)算和定性推理相結(jié)合建立了一個(gè)混合代數(shù)系統(tǒng)Q1Iwasaki和Simmons把經(jīng)濟(jì)學(xué)、熱力學(xué)中所用的因果關(guān)系形式化Weld在分子生物學(xué)中設(shè)計(jì)了定性模擬程序

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

人類(lèi)對(duì)物理世界的描述、解釋,常是以某種直觀的定性方法進(jìn)行的,很少使用微分方程及具體的數(shù)值描述,如人們?cè)隍T自行車(chē)時(shí),為了避免摔倒和撞車(chē),并不需要使用書(shū)本上的運(yùn)動(dòng)方程,而是針對(duì)幾個(gè)主要參量的變化趨勢(shì)給予粗略的、直觀的,但大體上準(zhǔn)確的描述,這就夠了。2023/8/3史忠植高級(jí)人工智能7定性推理的基本方法2023/9/12史忠植高級(jí)人工智能8定性推理的基本方法

一般分析運(yùn)動(dòng)系統(tǒng)行為的標(biāo)準(zhǔn)過(guò)程可分為三個(gè)步驟：

(1)決定描述對(duì)象系統(tǒng)特征的量。

(2)用方程式表示量之間的相互關(guān)系。

(3)分析方程式，得到數(shù)值解。2023/8/3史忠植高級(jí)人工智能8定性推理的基本方法2023/9/12史忠植高級(jí)人工智能9定性推理的基本方法這類(lèi)運(yùn)動(dòng)系統(tǒng)行為的問(wèn)題用計(jì)算機(jī)進(jìn)行求解時(shí)，將面臨如下三個(gè)問(wèn)題：

(1)步驟(1)(2)需要相當(dāng)多的知識(shí)，并且要有相應(yīng)的算法。

(2)有的場(chǎng)合對(duì)象系統(tǒng)的性質(zhì)很難用數(shù)學(xué)式子表示。

(3)步驟(3)得到了數(shù)值解，但是對(duì)象系統(tǒng)的行為并不直觀明了。2023/8/3史忠植高級(jí)人工智能9定性推理的基本方法這2023/9/12史忠植高級(jí)人工智能10定性推理的基本方法為了解決第二、第三個(gè)問(wèn)題，定性推理一般采用下列分析步驟：

(1)結(jié)構(gòu)認(rèn)識(shí)：將對(duì)象系統(tǒng)分解成部件的組合。

(2)因果分析：當(dāng)輸入值變化時(shí)，分析對(duì)象系統(tǒng)中怎樣傳播。

(3)行為推理：輸入值隨著時(shí)間變化，分析對(duì)象系統(tǒng)的內(nèi)部狀態(tài)怎樣變化。

(4)功能說(shuō)明：行為推理的結(jié)果表明對(duì)象系統(tǒng)的行為，由此可以說(shuō)明對(duì)象系統(tǒng)的功能。2023/8/3史忠植高級(jí)人工智能10定性推理的基本方法2023/9/12史忠植高級(jí)人工智能11定性推理的基本方法定性推理的觀點(diǎn)大體上可這樣來(lái)理解:?忽略被描述對(duì)象的次要因素,掌握主要因素簡(jiǎn)化問(wèn)題的描述。?將隨時(shí)間t連續(xù)變化的參量x(t)

的值域離散化為定性值集合,

通常變量x的定性值[x]定義為?依物理規(guī)律將微分方程轉(zhuǎn)換成定性(代數(shù))方程,或直接依物理規(guī)律建立定性模擬或給出定性進(jìn)程描述。?最后給出定性解釋2023/8/3史忠植高級(jí)人工智能11定性推理的基本方法2023/9/12史忠植高級(jí)人工智能12定性模型推理deKleer研究解決經(jīng)典物理問(wèn)題需要哪些知識(shí)及如何建立問(wèn)題求解系統(tǒng)。他提出的定性模型方法所涉及的物理系統(tǒng)是由管子、閥門(mén)、容器等裝置組成,約束條件(定性方程)反映在這些裝置的連接處,依定性方程給出定性解釋。為將代數(shù)方程、微分方程定性化,首先需定義變量的定性值集合以及相應(yīng)的定性運(yùn)算。2023/8/3史忠植高級(jí)人工智能12定性模型推理2023/9/12史忠植高級(jí)人工智能13定性模型推理定性值集合是一個(gè)離散集合,其元素是由對(duì)數(shù)軸的劃分而得到的,通常把數(shù)軸(－∞,∞)劃分成(－∞,0),0,(0,∞)三段,規(guī)定定性值集合為{－,0,＋},變量x的定性值[x]如下定義:另外用?x表示dx/dt的定性值,也即2023/8/3史忠植高級(jí)人工智能13定性模型推理另外用2023/9/12史忠植高級(jí)人工智能14定性模型推理

xy

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

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

其中:符號(hào)？表示不確定或無(wú)定義。2023/8/3史忠植高級(jí)人工智能14定性模型推理2023/9/12史忠植高級(jí)人工智能15定性模型推理下面給出⊕和?的運(yùn)算規(guī)則。設(shè)e1,e2是公式,則有：[0]⊕[e1]?[e1][0]?[e1]?[0][+]?[e1]?[e1][-]?[e1]?-[e1]2023/8/3史忠植高級(jí)人工智能15定性模型推理[0]2023/9/12史忠植高級(jí)人工智能16定性模型推理使用下列規(guī)則，可將運(yùn)算符+、

轉(zhuǎn)換成⊕、?：

[e1＋e2]?[e1]⊕[e2][e1

e2]?[e1]

[e2]2023/8/3史忠植高級(jí)人工智能16定性模型推理[2023/9/12史忠植高級(jí)人工智能17壓力調(diào)節(jié)器壓力調(diào)節(jié)器是通過(guò)彈簧來(lái)控制閥門(mén)流量,以使流量為某一設(shè)定值而不受流入的流量和負(fù)載變化的影響。根據(jù)物理學(xué)有2023/8/3史忠植高級(jí)人工智能17壓力調(diào)節(jié)器壓力調(diào)節(jié)2023/9/12史忠植高級(jí)人工智能18壓力調(diào)節(jié)器其中Q是通過(guò)閥門(mén)的流量,P是壓力,A是閥門(mén)開(kāi)啟的面積,而C是常系數(shù),

是流體的質(zhì)量密度。按照運(yùn)算和轉(zhuǎn)換規(guī)則而得到定性方程：[Q]=[P]?Q=?A+?P(如果A>0)2023/8/3史忠植高級(jí)人工智能18壓力調(diào)節(jié)器其中Q2023/9/12史忠植高級(jí)人工智能19壓力調(diào)節(jié)器OPEN狀態(tài)A=Amax定性方程[P]=0?P=0WORKING狀態(tài)0<A<Amax定性方程[P]=[Q]?P+?A=?QCLOSED狀態(tài)A=0定性方程[Q]=0?Q=0

除了可以討論每個(gè)狀態(tài)內(nèi)的定性分析還可討論各狀態(tài)間轉(zhuǎn)換的定性分析。deKleer建立的ENVSION系統(tǒng)是使用約束傳播與生成測(cè)試方法來(lái)求解定性方程。2023/8/3史忠植高級(jí)人工智能19壓力調(diào)節(jié)器OPEN2023/9/12史忠植高級(jí)人工智能20定性進(jìn)程推理

Forbus提出的定性進(jìn)程方法把物理現(xiàn)象視作由一些相關(guān)的進(jìn)程來(lái)描述,每個(gè)進(jìn)程由一組個(gè)體、前提條件、數(shù)量條件、參數(shù)關(guān)系和影響來(lái)描述,推理過(guò)程是從已知的進(jìn)程表中依次選出一些可用的進(jìn)程來(lái)描述一個(gè)物理過(guò)程。定性進(jìn)程理論中有關(guān)定性物理的關(guān)鍵思想如下：

(1)組織原則為物理進(jìn)程。本體論在知識(shí)的組織上起著重要作用。在人們進(jìn)行物理系統(tǒng)推理時(shí)，物理進(jìn)程非常直觀，用它組織物理領(lǐng)域的理論是合理的。

(2)用順序關(guān)系表示數(shù)值。重要的性質(zhì)差別常由比較而來(lái)。例如，當(dāng)壓力和溫度不同時(shí)產(chǎn)生流動(dòng)；當(dāng)溫度到達(dá)某一界值時(shí)會(huì)發(fā)生相變等。在很多情況下，用一套序數(shù)關(guān)系表示數(shù)值更自然。2023/8/3史忠植高級(jí)人工智能20定性進(jìn)程推理Fo2023/9/12史忠植高級(jí)人工智能21定性進(jìn)程推理

(3)單一機(jī)制假設(shè)。物理進(jìn)程被看作是產(chǎn)生變化的機(jī)制。這樣，任何變化必須解釋為某些物理進(jìn)程的直接或間接的影響。進(jìn)程本體論為定性物理理論的因果性打下了基礎(chǔ)。

(4)組合的定性數(shù)學(xué)。人們進(jìn)行復(fù)雜系統(tǒng)推理時(shí)，使用部分信息并進(jìn)行組合。

(5)清晰的表示及關(guān)于模型化假設(shè)的推理。明確地表示某些特定知識(shí)的適用條件，并從領(lǐng)域理論中為特定系統(tǒng)建模成為定性物理的中心任務(wù)。2023/8/3史忠植高級(jí)人工智能21定性進(jìn)程推理(32023/9/12史忠植高級(jí)人工智能22定性進(jìn)程推理

一個(gè)物理系統(tǒng)的變化是由進(jìn)程引起的,一個(gè)物理過(guò)程由一些進(jìn)程來(lái)描述,這就是定性推理進(jìn)程方法的基本觀點(diǎn)。下面介紹在定性進(jìn)程推理中的量空間和進(jìn)程的描述。2023/8/3史忠植高級(jí)人工智能22定性進(jìn)程推理一個(gè)2023/9/12史忠植高級(jí)人工智能23定性進(jìn)程推理1.量空間

(1)時(shí)間由區(qū)間表示,區(qū)間之間的關(guān)系有前、后、相等。兩個(gè)區(qū)間可以相連,瞬間認(rèn)為是極短的區(qū)間,持續(xù)時(shí)間為0。

(2)物體的參數(shù)稱(chēng)作量,量由其數(shù)量和導(dǎo)數(shù)組成。

Am表示數(shù)量的值,As表示數(shù)量的符號(hào)。

Dm表示數(shù)量導(dǎo)數(shù)值,Ds表示數(shù)量導(dǎo)數(shù)的符號(hào)。

(MQt)表示時(shí)刻t量Q的值。

HAS-Quantity是謂詞,指某物體具有某參數(shù)。

(3)一個(gè)量的所有可能取值構(gòu)成量空間,量空間的元素間有半序關(guān)系。2023/8/3史忠植高級(jí)人工智能23定性進(jìn)程推理1.2023/9/12史忠植高級(jí)人工智能24定性進(jìn)程推理2.進(jìn)程

一個(gè)物理進(jìn)程P由一組個(gè)體、一組前提條件、一組數(shù)量條件、一組參數(shù)關(guān)系和一組影響組成。一個(gè)進(jìn)程的具體示例稱(chēng)作進(jìn)程例，用PI表示。2023/8/3史忠植高級(jí)人工智能24定性進(jìn)程推理2.2023/9/12史忠植高級(jí)人工智能25定性進(jìn)程推理Processheat-flow.熱流進(jìn)程Individuals:一組個(gè)體

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

dstanobject,Has-Quantity(dst,heat)dst是受熱對(duì)象pathaheat-path,path是熱流路徑

Heat-connection(path,src,dst)將src,dst連結(jié)起來(lái)Preconclitions:一組前提條件

Heat-Aligned(path)熱流路徑安排好

QuantityConditions:一組數(shù)量條件

A[temperature(src)]>A[temperature(dst)]src溫度高于dst溫度2023/8/3史忠植高級(jí)人工智能25定性進(jìn)程推理Pr2023/9/12史忠植高級(jí)人工智能26定性進(jìn)程推理Relations:一組參量關(guān)系

Letflow-ratebeaquantityflow-rate(熱流量)是一個(gè)數(shù)量

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),而且是負(fù)影響

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

heat(dst),而且是正影響2023/8/3史忠植高級(jí)人工智能26定性進(jìn)程推理Re2023/9/12史忠植高級(jí)人工智能27定性進(jìn)程推理演繹過(guò)程

在進(jìn)程定性推理中，其演繹過(guò)程如下：

(1)選進(jìn)程。對(duì)一組已知的個(gè)體來(lái)說(shuō),在進(jìn)程表中依各進(jìn)程對(duì)個(gè)體的說(shuō)明找出可能出現(xiàn)的那些進(jìn)程例PI。

(2)確定激活的PI。依前提條件、數(shù)量條件確定每個(gè)PI的狀態(tài)。滿足這些條件的為激活的PI,激活的PI叫進(jìn)程結(jié)構(gòu)。

(3)確定量的變化。個(gè)體的變化由相應(yīng)量的Ds

值來(lái)表示。量的變化可由進(jìn)程直接影響，也可由∝Q間接影響。

(4)確定進(jìn)程結(jié)構(gòu)變化。量的變化將會(huì)引起進(jìn)程結(jié)構(gòu)的變化,確定這種變化也叫限制分析,這樣對(duì)一個(gè)物理過(guò)程的描述便由(1)建立的PI進(jìn)入了下一個(gè)PI。重復(fù)(1)－(4)的步驟便可給出一個(gè)物理過(guò)程的一串進(jìn)程描述。2023/8/3史忠植高級(jí)人工智能27定性進(jìn)程推理演繹過(guò)2023/9/12史忠植高級(jí)人工智能28定性進(jìn)程推理2023/8/3史忠植高級(jí)人工智能28定性進(jìn)程推理2023/9/12史忠植高級(jí)人工智能29定性仿真推理

1984年Kuipers發(fā)表了“因果性的常識(shí)推理：從結(jié)構(gòu)導(dǎo)出行為”論文。這篇論文建立了一種定性仿真推理的框架,簡(jiǎn)單地給出了從常微分方程的抽象而得的定性結(jié)構(gòu)和定性行為表示方法。隨后，1986年AI雜志又刊登了Kuipers“定性仿真”一文，文中明確了抽象關(guān)系，提出用于定性仿真的QSIM算法，并用抽象關(guān)系證明了其有效性和不完備性。這兩篇文章奠定了定性仿真的基礎(chǔ)。演繹過(guò)程

2023/8/3史忠植高級(jí)人工智能29定性仿真推理192023/9/12史忠植高級(jí)人工智能30定性仿真推理

定性仿真是從結(jié)構(gòu)的定性描述出發(fā)來(lái)導(dǎo)出行為描述。直接用部件的參量作為狀態(tài)變量來(lái)描述物理結(jié)構(gòu),定性約束直接由物理規(guī)律得到,把一個(gè)參量隨時(shí)間的變化視作定性的狀態(tài)序列,求解算法是從初始狀態(tài)出發(fā),生成各種可能的后續(xù)狀態(tài),進(jìn)而通過(guò)一致性過(guò)濾,重復(fù)該過(guò)程直到?jīng)]有新?tīng)顟B(tài)出現(xiàn)。定性仿真結(jié)構(gòu)描述由系統(tǒng)的狀態(tài)參數(shù)和約束關(guān)系組成。認(rèn)為參數(shù)是時(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)。2023/8/3史忠植高級(jí)人工智能30定性仿真推理2023/9/12史忠植高級(jí)人工智能31定性仿真推理行為描述關(guān)心參量的變化。假設(shè)參量f(t)是[a,b]到［－∞,∞］的可微函數(shù)。f的界標(biāo)值是一個(gè)有限集合,至少含有f(a),f(b)。集合{t|t∈[a,b]∧f(t)

是界標(biāo)值}的元素稱(chēng)作區(qū)別點(diǎn)。定義4.1設(shè)l1<l2<┅<lk是f:[a,b]→[-∞,∞]的界標(biāo)值。對(duì)任意t∈[a,b],f

在t的定性狀態(tài)QS(f,t)規(guī)定為有序?qū)?/p>

<qval,qdir>,定義如下:2023/8/3史忠植高級(jí)人工智能31定性仿真推理行為描2023/9/12史忠植高級(jí)人工智能32定性仿真推理2023/8/3史忠植高級(jí)人工智能32定性仿真推理2023/9/12史忠植高級(jí)人工智能33定性仿真推理

定義4.2設(shè)ti,ti+1是相鄰的區(qū)分點(diǎn),規(guī)定f在(ti,ti+1)內(nèi)的定性狀態(tài)QS(f,ti,ti+1)仍為QS(f,t)其中t∈(ti,ti+1)2023/8/3史忠植高級(jí)人工智能33定性仿真推理定義2023/9/12史忠植高級(jí)人工智能34定性仿真推理定義4.3f

在[a,b]上的定性行為是f的定性狀態(tài)序列QS(f,t0),QS(f,t0,t1),QS(f,t1),┄,QS(f,tn)。其中

ti(i=0,1,┄,n)為所有的區(qū)分點(diǎ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

區(qū)分點(diǎn)并集的元素。

2023/8/3史忠植高級(jí)人工智能34定性仿真推理定義2023/9/12史忠植高級(jí)人工智能35定性仿真推理定性狀態(tài)轉(zhuǎn)換在定性仿真中，定性狀態(tài)轉(zhuǎn)移是經(jīng)常遇到的。假設(shè)f是可微函數(shù),f從一個(gè)定性狀態(tài)轉(zhuǎn)換到另一個(gè)定性狀態(tài)必須遵守介值定理和中值定理。定性狀態(tài)轉(zhuǎn)換有兩類(lèi)：一類(lèi)是P轉(zhuǎn)換，該類(lèi)轉(zhuǎn)換是從時(shí)間點(diǎn)到時(shí)間區(qū)間；另一類(lèi)是I轉(zhuǎn)換，它是從時(shí)間區(qū)間到時(shí)間點(diǎn)的轉(zhuǎn)換。下面給出轉(zhuǎn)換表:2023/8/3史忠植高級(jí)人工智能35定性仿真推理定性狀2023/9/12史忠植高級(jí)人工智能36定性仿真推理P轉(zhuǎn)換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史忠植高級(jí)人工智能36定性仿真推理P轉(zhuǎn)換2023/9/12史忠植高級(jí)人工智能37定性仿真推理I轉(zhuǎn)換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史忠植高級(jí)人工智能37定性仿真推理I轉(zhuǎn)2023/9/12史忠植高級(jí)人工智能38定性仿真推理

QSIM算法可對(duì)系統(tǒng)的行為進(jìn)行定性仿真。首先將初始狀態(tài)送入ACTIVE表中,然后重復(fù)(1)—(6)直至ACTIVE表空為止。算法4.1QSIM算法。

(1)從ACTIVE表中選一狀態(tài)。

(2)對(duì)每個(gè)參數(shù)按轉(zhuǎn)換表找出所有可能的轉(zhuǎn)換。

(3)對(duì)約束中變?cè)霓D(zhuǎn)換生成二元組,三元組集合,依約束關(guān)系做一致性濾波。

(4)對(duì)有公共變?cè)募s束,對(duì)元組進(jìn)行組對(duì),再對(duì)組對(duì)的元組做一致性濾波。2023/8/3史忠植高級(jí)人工智能38定性仿真推理QS2023/9/12史忠植高級(jí)人工智能39定性仿真推理(5)從剩下的元組生成所有可能的全局解釋。每個(gè)解釋生成一個(gè)新?tīng)顟B(tài)作為當(dāng)前狀態(tài)的后繼狀態(tài)。(6)對(duì)新?tīng)顟B(tài)做全局濾波,剩下的狀態(tài)送入ACTIVE表。全局濾波排除下列狀態(tài)：

?無(wú)變化情形:如I1,I4,I7;?循環(huán)情形:新?tīng)顟B(tài)與某個(gè)前輩狀態(tài)相同;?發(fā)散情形:某參數(shù)值為∞,這時(shí)當(dāng)前時(shí)間點(diǎn)必為結(jié)束點(diǎn)。2023/8/3史忠植高級(jí)人工智能39定性仿真推理(5)2023/9/12史忠植高級(jí)人工智能40幾何空間定性推理空間定性推理是對(duì)幾何形狀或者運(yùn)動(dòng)性質(zhì)進(jìn)行定性推理，首先需對(duì)空間位置及運(yùn)動(dòng)方式進(jìn)行定性表示，進(jìn)而對(duì)幾何形狀及運(yùn)動(dòng)性質(zhì)進(jìn)行推理研究及預(yù)測(cè)分析，并作出邏輯解釋。空間定性推理是通過(guò)定義一組空間并尋找這些關(guān)系間的聯(lián)系來(lái)進(jìn)行的。目前主要的研究是針對(duì)空間定性建模方式、空間形狀及關(guān)系的定性表示和定性技術(shù)的形式化等,

產(chǎn)生解釋理論,但總體來(lái)看與解決工程問(wèn)題距離尚遠(yuǎn)。2023/8/3史忠植高級(jí)人工智能40幾何空間定性推理空2023/9/12史忠植高級(jí)人工智能41幾何空間定性推理將Allen的時(shí)態(tài)邏輯[Allen1984]與Randall的空間邏輯[Randall1992]結(jié)合起來(lái)，形成空間、時(shí)間、連續(xù)運(yùn)動(dòng)的表達(dá)邏輯。另外從空間定性推理派生出空間規(guī)劃理論,可用于為一組幾何對(duì)象尋找滿足一組約束的分布設(shè)計(jì),有關(guān)方法主要用于設(shè)計(jì)自動(dòng)化、定性建模等領(lǐng)域。在這一領(lǐng)域已取得了一些較有實(shí)際意義的成果,如約束滿足問(wèn)題(CSP)求解理論,而實(shí)際上很多空間定性規(guī)劃都是一個(gè)幾何約束滿足問(wèn)題(GCSP)。2023/8/3史忠植高級(jí)人工智能41幾何空間定性推理將2023/9/12史忠植高級(jí)人工智能42幾何空間定性推理1992年由Randell等人建立起來(lái)的RCC空間時(shí)間邏輯是用于對(duì)空間問(wèn)題進(jìn)行可達(dá)性的展望,并已程序?qū)崿F(xiàn)。與Kuipers的QSIM方法類(lèi)似,基于RCC邏輯的仿真算法也是從對(duì)系統(tǒng)進(jìn)行結(jié)構(gòu)性的描述開(kāi)始的,系統(tǒng)將初始狀態(tài)作為生成樹(shù)的根結(jié)點(diǎn),可能的行為則是樹(shù)中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑。2023/8/3史忠植高級(jí)人工智能42幾何空間定性推理12023/9/12史忠植高級(jí)人工智能43QualitativeSpatialReasoningQualitativereasoningmodellingthecontinuousrealityinmanageableentitiessolutionforquantitativeproblemsthatarenotcomputableTwoapproachesartificialintelligence→GIScience

1992Randell,Cui,Cohndatabases→GISystems

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

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

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

rijxj},isNsatisfiable?Thisisthesatisfactionproblem.ForSasubsetofthewholealgebra,wewriteRSAT(S)fortheproblemofdecidingsatisfactionofnetworkswithconstraintsoverS.2023/8/3史忠植高級(jí)人工智能56Reasoning2023/9/12史忠植高級(jí)人工智能57Reasoningwithq-CalculiThesatisfactionproblemsareoftenNPhard,e.g.RSAT(IA)andRSAT(RCC8)areNPCReasoningproblemsinIAandRCC8havebeeninvestigatedthoroughly,andmanyusefultechniqueshavebeendeveloped.2023/8/3史忠植高級(jí)人工智能57Reasoning2023/9/12史忠植高級(jí)人工智能58Localconstraintsolvingtechniquesmaybeuseful,e.g.path-consistencyalgorithm(PCA)cansolveRSAT(S)ifSisthemaximaltractablesubalgebraofIAReasoningwithq-Calculi2023/8/3史忠植高級(jí)人工智能58Localcon2023/9/12史忠植高級(jí)人工智能59幾何空間定性推理空間邏輯的基礎(chǔ)在于假設(shè)一個(gè)原語(yǔ)性的二元關(guān)系C(x,y)。其中x,y表示兩個(gè)區(qū)域(regiong),謂詞C表示共享一個(gè)以上公共點(diǎn)。也就是指相接觸,它具有自反性、對(duì)稱(chēng)性。

1.八個(gè)基本關(guān)系的定義使用關(guān)系C(x,y),一組基本的二元關(guān)系可以被定義為：

(1)DC(x,y):表示兩區(qū)域不相接觸。

(2)EC(x,y):表示兩區(qū)域外部接觸。

(3)PO(x,y):表示兩區(qū)域部分覆蓋。2023/8/3史忠植高級(jí)人工智能59幾何空間定性推理空2023/9/12史忠植高級(jí)人工智能60幾何空間定性推理

(4)=(x,y):表示兩區(qū)域完全相同。

(5)TPP(x,y):表示$x$是$y$的一個(gè)嚴(yán)格部分并且$x,y$相切(內(nèi)切)。

(6)NTPP(x,y):表示$x$是$y$的一個(gè)嚴(yán)格部分但$x,y$不相接觸(包含而不相切)。

(7)TPP(x,y):表示$y$是$x$的一個(gè)嚴(yán)格部分并且$x,y$相切。

(8)TPP(x,y):表示$y$是$x$的一個(gè)嚴(yán)格部分但$x,y$不相切接觸。2023/8/3史忠植高級(jí)人工智能60幾何空間定性推理2023/9/12史忠植高級(jí)人工智能61幾何空間定性推理基本關(guān)系間的聯(lián)系這種空間邏輯與Allen的邏輯相類(lèi)似,也使用預(yù)計(jì)算的傳遞性表來(lái)表示二元關(guān)系之間可能的變化聯(lián)系,在表中從任一關(guān)系R3(a,c)可查找出所有可能的二元關(guān)系R1(a,b)與R2(b,c)。這一表對(duì)定性仿真是很有用的。然而,近年的研究中尚未給出這類(lèi)傳遞性表的建立算法。但Randell提到在其仿真程序中使用了該表來(lái)檢驗(yàn)展望過(guò)程中狀態(tài)描述的一致性。2023/8/3史忠植高級(jí)人工智能61幾何空間定性推理基2023/9/12史忠植高級(jí)人工智能62幾何空間定性推理基本狀態(tài)間的相互轉(zhuǎn)換根據(jù)兩個(gè)區(qū)域的形狀不同,上述八個(gè)基本關(guān)系可被分為6個(gè)子集:

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

(6)DCECPO2023/8/3史忠植高級(jí)人工智能62幾何空間定性推理基2023/9/12史忠植高級(jí)人工智能63幾何空間定性推理空間時(shí)間關(guān)系描述

1.方位性狀態(tài)和運(yùn)動(dòng)性狀態(tài)

Galton將八個(gè)RCC關(guān)系分為方位性狀態(tài)(positionstate)和運(yùn)動(dòng)性狀態(tài)(motionstate)，并且使用Allen關(guān)于時(shí)間關(guān)系的一些邏輯化的形式,給出了這種分類(lèi)的定義。首先介紹一下Galton使用的概念、謂詞和函數(shù)。

(1)對(duì)時(shí)間的描述分為區(qū)間和時(shí)刻;(2)狀態(tài)存在的描述謂詞:Holds-on(s,i)表示在區(qū)間i上存在狀態(tài)s;Holds-at(s,t)表示在時(shí)刻t存在狀態(tài)s;(3)謂詞Div(t,i)表示時(shí)刻t在區(qū)間i上;(4)函數(shù)inf(i)表示在區(qū)間i的開(kāi)始時(shí)刻;(5)函數(shù)sup(i)表示在區(qū)間i的結(jié)束時(shí)刻;2023/8/3史忠植高級(jí)人工智能63幾何空間定性推理空2023/9/12史忠植高級(jí)人工智能64幾何空間定性推理空間時(shí)間關(guān)系描述方位性狀態(tài)。如果狀態(tài)s滿足?i(Holds-on(s,i))→Holds-at(s,inf(i))∧Holds-at(s,sup(i))即如果一個(gè)狀態(tài)s在時(shí)間區(qū)間i上存在,則在該區(qū)間的起止時(shí)刻這個(gè)狀態(tài)都存在。具有這一性質(zhì)的狀態(tài)稱(chēng)為方位性狀態(tài)。2023/8/3史忠植高級(jí)人工智能64幾何空間定性推理空2023/9/12史忠植高級(jí)人工智能65幾何空間定性推理空間時(shí)間關(guān)系描述運(yùn)動(dòng)性狀態(tài)。如果狀態(tài)s滿足?t(Holds-on(s,t)→?i(Div(t,i)∧Holds-on(s,i)))即如果在某時(shí)刻t有狀態(tài)s,那么一定存在包含這一時(shí)刻的某一區(qū)間使$s$在整個(gè)區(qū)間都存在,具有這一性質(zhì)的狀態(tài)稱(chēng)為運(yùn)動(dòng)性狀態(tài)。2023/8/3史忠植高級(jí)人工智能65幾何空間定性推理空2023/9/12史忠植高級(jí)人工智能66幾何空間定性推理空間時(shí)間關(guān)系描述

擾動(dòng)原理

Galton根據(jù)這種分類(lèi)給出了擾動(dòng)原理,這是對(duì)空間狀態(tài)在時(shí)域變化進(jìn)行描述的一組公理體系：定義4.5擾動(dòng)(perturbation)。如果RCC關(guān)系R與R'滿足條件:?t(Holds-at(R(a,b),t)∧(?i(Holds-on(R'(a,b),i))∧(inf(i)=t)∨(sup(i)=t)))))即如果時(shí)刻t有狀態(tài)R,且有一個(gè)區(qū)間i開(kāi)始或結(jié)束于t區(qū)間i上的狀態(tài)為R'。此時(shí)稱(chēng)R與R'互為擾動(dòng)。擾動(dòng)原理:每個(gè)RCC關(guān)系是它自身的擾動(dòng),另外一個(gè)靜止性的狀態(tài)只能與一個(gè)運(yùn)動(dòng)性的狀態(tài)互擾動(dòng),反之亦然(只討論剛體)。2023/8/3史忠植高級(jí)人工智能66幾何空間定性推理空2023/9/12史忠植高級(jí)人工智能67幾何空間定性推理

Randell算法假設(shè)初始狀態(tài)S0

已放入狀態(tài)集合S中。

(1)如果S空則停止;(2)從S中選出狀態(tài)Si,且移出;(3)如果Si

為不一致?tīng)顟B(tài)將轉(zhuǎn)(2);(4)應(yīng)用狀態(tài)約束選擇可用變換規(guī)則;(5)用所選出的規(guī)則產(chǎn)生可能的下一個(gè)狀態(tài)集合;(6)使用添加與刪除規(guī)則;(7)進(jìn)行狀態(tài)內(nèi)約束檢查;(8)將剩下的狀態(tài)加入S并轉(zhuǎn)(1)。2023/8/3史忠植高級(jí)人工智能67幾何空間定性推理2023/9/12史忠植高級(jí)人工智能68空間推理的研究進(jìn)展對(duì)空間推理的許多研究方向進(jìn)行分類(lèi)、歸納和整理之后得到的主要研究方向是：

(1)空間數(shù)據(jù)庫(kù)的精度。

(2)空間關(guān)系語(yǔ)言。

(3)空間推理與地理信息系統(tǒng)。

(4)空間決策支持系統(tǒng)。

(5)空間數(shù)據(jù)的不確定性處理。

(6)形式化的繪圖知識(shí)。

(7)時(shí)空推理。2023/8/3史忠植高級(jí)人工智能68空間推理的研究進(jìn)展2023/9/12史忠植高級(jí)人工智能69

(8)定性空間推理。

(9)空間推理的用戶界面。

(10)基于案例(CASE-BASED)的空間推理.(11)空間推理的認(rèn)知問(wèn)題。

(12)空間推理與機(jī)器人視覺(jué)。

(13)常識(shí)推理。

(14)區(qū)域連接演算RCC-8?？臻g推理的研究進(jìn)展2023/8/3史忠植高級(jí)人工智能69空間推理的研究2023/9/12史忠植高級(jí)人工智能70大量的文獻(xiàn)空間推理的研究熱點(diǎn)：時(shí)空推理STSR(spatio-temporalspatialreasoning)、定性空間推理QSR(qualitativespatialreasoning)地理信息系統(tǒng)空間推理的研究熱點(diǎn)2023/8/3史忠植高級(jí)人工智能70大量的文獻(xiàn)空間推理2023/9/12史忠植高級(jí)人工智能71時(shí)空推理當(dāng)今世界是在漫長(zhǎng)的歷史長(zhǎng)河中，歷經(jīng)滄桑演變進(jìn)化而來(lái)的。世界中的任何事物和現(xiàn)象都遵循著誕生、生長(zhǎng)，直至消失或死亡的自然規(guī)律。同樣，現(xiàn)代文明和科技的進(jìn)步無(wú)不是人類(lèi)歷史的經(jīng)驗(yàn)積累和結(jié)晶。人類(lèi)在認(rèn)識(shí)和解釋當(dāng)今世界事物和現(xiàn)象時(shí),不但渴望甚至必須了解它們的過(guò)去,而且希望預(yù)測(cè)未知的將來(lái),以便在必要的時(shí)候采取一定措施,使人類(lèi)社會(huì)朝著美好的方向發(fā)展。在這綿延不斷的歷史軌跡中，無(wú)不打上了時(shí)間的烙印，因此,探索適宜的工具和方法,沿著時(shí)間脈絡(luò)研究和推理客觀世界內(nèi)在機(jī)制和時(shí)空發(fā)展規(guī)律,就顯得十分重要?？臻g推理的研究熱點(diǎn)2023/8/3史忠植高級(jí)人工智能71時(shí)空推理空間推理的2023/9/12史忠植高級(jí)人工智能72

總的來(lái)說(shuō)，影響空間推理結(jié)果的因素包括空間因素和時(shí)間因素。所謂時(shí)空推理是指在空間推理過(guò)程中添加時(shí)間因素。地表、地下和大氣等空間對(duì)象的狀態(tài)不僅受到空間因素的影響,同時(shí),從一個(gè)漫長(zhǎng)的時(shí)間過(guò)程來(lái)看，也必將受到時(shí)間因素的影響。可以說(shuō),時(shí)空推理是更為一般的空間推理,或者可以說(shuō)空間推理是時(shí)空推理的一個(gè)特例。目前,時(shí)空推理方面的研究還處于起步階段。下面,我簡(jiǎn)單地介紹一些權(quán)威學(xué)者對(duì)時(shí)空推理的認(rèn)識(shí)和他們提出的時(shí)空推理模型。空間推理的研究熱點(diǎn)2023/8/3史忠植高級(jí)人工智能72空間推理的研究熱點(diǎn)2023/9/12史忠植高級(jí)人工智能73

1.RichardA.Block在他的論文“PsychologicalTimeandtheProcessingofSpatialInformation”中指出：“與其說(shuō)空間為時(shí)間提供了一個(gè)框架，不如說(shuō)時(shí)間感知為空間感知提供了一個(gè)框架”?！拔恢煤统掷m(xù)時(shí)間之間、個(gè)人經(jīng)驗(yàn)和常識(shí)之間以及期望和回顧之間存在重要的區(qū)別”。他提出了上下文時(shí)間模型，并且把它擴(kuò)展到空間，模型著眼于哪些變量對(duì)持續(xù)時(shí)間和其他種類(lèi)的時(shí)間體驗(yàn)之間及行為和判斷之間的相互作用有影響，這些變量包括實(shí)驗(yàn)者的特征、時(shí)間周期、時(shí)間周期上的活動(dòng)和時(shí)間行為?？臻g推理的研究熱點(diǎn)2023/8/3史忠植高級(jí)人工智能73空間推理的研究熱點(diǎn)2023/9/12史忠植高級(jí)人工智能74

2.A.G.Cohn,Z.Cui,D.A.Randell在他們的論文“ExploitingTemporalContinuityinQualitativeSpatialCalculus”中提出了一個(gè)空間知識(shí)推理的邏輯框架,目的是為人工智能系統(tǒng)的表示和推理提供一個(gè)形式上的時(shí)間和空間的公理理論。