謝玉枚,高海燕

(1.福建江夏學院電子信息科學學院,福建 福州350108; 2.廈門學院電氣與自動化學院,福建 廈門 361024)

0 引 言

雖然現(xiàn)階段在定性空間推理中有一套相對成熟的表示模型和推理方法，但是空間信息的表達和推理強調的往往是靜態(tài)空間的配置。在實際應用中，多數(shù)智能系統(tǒng)處理的定性空間信息都是動態(tài)變化的，動態(tài)空間信息的表達和推理尤為重要。特別是近年來，動態(tài)定性空間推理的研究在定性空間領域得到越來越多的關注，已經(jīng)成為定性空間推理中的研究熱點[1]。

大多數(shù)應用領域涉及空間、動作和空間變化的交互[2]，例如機器人導航、協(xié)同自治Agent和自動規(guī)劃等領域，它們需要處理的動態(tài)變化空間信息通常是由動作造成的。時間信息隱藏在動態(tài)變化的狀態(tài)中，并非單獨出現(xiàn)。而動態(tài)關系變化的研究主要側重于動作產(chǎn)生的空間關系的改變，因此不需要在已經(jīng)很復雜的空間表示中再加入時間維度，時空信息的表示推理變得簡單很多。

Freksa[3]所提出的概念鄰域圖在研究動態(tài)空間關系變化的方法中得到廣泛應用，幾乎所有的定性空間推理模型中有概念鄰域圖的表示。一系列處理變化的動態(tài)空間關系的方法在此基礎上提出[4-6]。2006年，Bhatt等人[7]用場景演算對空間拓撲關系的變化進行形式化描述，同時表示了空間推理中的基本概念空間關系約束、復合表和概念鄰域圖，但是沒有對引起空間拓撲關系變化的動作和事件具體表示和分析。2007年，Delafontaine等人[8]提出了在動態(tài)變化的拓撲關系網(wǎng)絡中移動實體的定性關系變化的研究方法，用定性軌道關系表示在網(wǎng)絡中移動點之間的關系。他定義了網(wǎng)絡中發(fā)生動態(tài)變化時2個移動點之間的關系變化，這種變化必須是連續(xù)的。2008年，Bhatt等人[1]用場景演算對動態(tài)空間系統(tǒng)進行建模，提出動態(tài)空間系統(tǒng)建模的通用框架，定義多類邏輯語言對動作和事件進行形式化表示，它能表示空間的各個方面，如空間關系的不同方面、物理屬性、空間屬性等，但他同樣沒有對動作、事件、空間關系和應用場景具體化。2010年，Bhatt[9-10]提出一種集成推理方法可作為一個有用范例使得定性空間表達和推理技術可廣泛用于動態(tài)GIS智能環(huán)境、認知機器人和空間設計的應用，并且這種范例支持解決動態(tài)空間系統(tǒng)建模的形式化并保證了空間推理領域、動作和變化推理領域和常識性推理之間的交互。在應用方面，Suhan等人[11]在動態(tài)空間系統(tǒng)的基礎上提出了一種基于歸納邏輯規(guī)劃的歸納時空學習框架。Waga等人[12]在動態(tài)空間系統(tǒng)的系統(tǒng)建模的需求上，提出非單調空間推理原型。

國內定性空間推理的研究方向集中于多方面空間關系結合的表示和推理、方向關系建模和異構定性空間推理等領域。目前研究動態(tài)空間推理的人比較少，梁晶晶[13]用區(qū)間概念鄰域圖表示空間變化過程，用空間關系在概念鄰域的變化次數(shù)表示時間，求若干時間后空間關系的變化，因為時間是用簡單定量表示，這種動態(tài)推理簡單。Song等人[14]用概念鄰域劃分表來刻畫空間關系與動作之間的轉換關系，給出了狀態(tài)動作表，用完備互斥的空間關系集合以及其領域劃分圖來描述定性空間關系的規(guī)劃問題，提出了規(guī)劃求解方法，但是其針對的是單個空間關系，相對簡單。楊帥[15]通過對動態(tài)空間中區(qū)間的空間結構進行劃分，提出了基于交集矩陣的運動區(qū)間與靜止區(qū)間統(tǒng)一表達模型UMMS，成功區(qū)分和識別出共計49種基本區(qū)間關系。為了進一步研究區(qū)間關系的動態(tài)變化，分析了這些關系的概念鄰域關系并給出有向概念鄰域圖。在應用方面Zhou等人[16]基于地理視頻本體論的基礎上，利用時空推理模型實現(xiàn)視頻數(shù)據(jù)的聚集。

綜上所述，動態(tài)空間推理是定性空間推理的研究熱點，目前還處于起步研究階段，大多數(shù)研究僅限于提出動態(tài)空間推理的框架和相關可能的應用場景，沒有對其中的動作、事件、空間關系具體化和動作作用下多個空間實體間空間關系改變情況[17]。

本文以動態(tài)空間信息的表示和推理為研究背景，研究在二維平面中擁有多個區(qū)域實體的空間場景下基于動作的動態(tài)空間推理問題。本文具體的安排如下：1)介紹動態(tài)空間推理的研究現(xiàn)狀；2)定義空間場景中的動作和給出區(qū)間關系的狀態(tài)轉移圖；3)對Bhatt定義的動態(tài)空間系統(tǒng)進行細化和擴展，用一個元組對動態(tài)空間系統(tǒng)中的空間場景進行形式化表示；4)介紹實體在歷史場景中發(fā)生移動動作推出新空間場景的方法，同時給出一個應用場景；5)對本文的主要內容進行總結，并對下一步的工作進行展望。

1 動作及區(qū)間關系的狀態(tài)轉移圖

空間實體在現(xiàn)實生活的移動極為常見，比如從圖書館到宿舍、天空中的云朵在不停地漂移和機器人導航中機器人的移動都是移動動作。移動的結果就是空間實體自身位置的改變，從而與空間場景中其他實體的空間關系也發(fā)生了變化，進入新的空間場景。

假設空間實體在移動地過程中大小不發(fā)生變化，在二維平面中，對移動動作進行分析和總結，可以得到8個移動動作如定義1～定義8所示?？臻g實體在二維平面中發(fā)生移動，其空間位置發(fā)生變化，所以以下8個移動動作表現(xiàn)為空間實體在X軸和Y軸上發(fā)生位置改變。

定義1動作謂詞MW，MW(A)表示實體A大小不變，A在Y軸上的坐標不變，X軸上的坐標向西移動。

定義2動作謂詞MN，MN(A)表示實體A大小不變，A在X軸上的坐標不變，Y軸上的坐標向北移動。

定義3動作謂詞ME，ME(A)表示實體A大小不變，A在Y軸上的坐標不變，X軸上的坐標向東移動。

定義4動作謂詞MS，MS(A)表示實體A大小不變，A在X軸上的坐標不變，Y軸上的坐標向南移動。

定義5動作謂詞MNW，MNW(A)表示實體A大小不變，A在X軸上的坐標向西移動，Y軸上的坐標向北移動。

定義6動作謂詞MNE，MNE(A)表示實體A大小不變，A在X軸上的坐標向東移動，Y軸上的坐標向北移動。

定義7動作謂詞MSE，MSE(A)表示實體A大小不變，A在X軸上的坐標向東移動，Y軸上的坐標向南移動。

定義8動作謂詞MSW，MSW(A)表示實體A大小不變，A在X軸上的坐標向西移動，Y軸上的坐標向南移動。

從上述定義可以看出對于MNW,MNE,MSE和MSW可認為在實體A上同時發(fā)生了2個移動動作。例如MNW(A)可以看成是實體A上發(fā)生了移動動作MN和MW，因此在下面分析空間實體在移動動作作用下的狀態(tài)轉移圖也只考慮MN,ME,MS和MW動作謂詞；MNW,MNE,MSE和MSW看成是MN,ME,MS和MW之間兩兩相互組合。

本文研究動態(tài)空間系統(tǒng)中基于動作的動態(tài)空間推理問題，即在一個空間場景中有多個實體，空間場景發(fā)生變化的原因是由于空間實體發(fā)生了動作，在上面的論述中把廣度意義上的動作抽象為8個移動動作，空間實體發(fā)生動作后，空間實體間的空間關系會發(fā)生怎樣的改變呢？

在以區(qū)域為空間原語中，某一個空間實體發(fā)生移動動作，這個實體與空間場景中其他實體的空間關系可能發(fā)生改變，從而得到新的空間場景。在這里沒有對實體發(fā)生動作的時間進行量化，而是對其進行定性化處理，認為發(fā)生動作的實體與空間場景中剩余實體的空間關系只要一個或多個發(fā)生變化，就認為是進入下一時刻，得到新的空間場景。

對于空間原語實體為區(qū)域的空間實體，用MBR近似空間區(qū)域，用矩形關系表示空間實體空間關系，在表達上簡單明了，易于理解。因為在二維空間的每個坐標軸上使用區(qū)間代數(shù)的理論，從而形成矩形代數(shù)理論，其中的關系就是矩形關系，空間實體在動作作用下的矩形關系變化表現(xiàn)為X軸和Y軸方向上區(qū)間關系的變化，所以本文只研究區(qū)間關系在動作作用下的變化的情況。

區(qū)間代數(shù)因有13個區(qū)間關系，在區(qū)間代數(shù)中m,mi,s,si,f,fi,eq是不穩(wěn)定關系，所謂不穩(wěn)定關系就是一旦相關的空間實體發(fā)生了移動動作，下一時刻空間關系肯定改變；而p,pi,d,di,o,oi是穩(wěn)定關系，當相關空間實體發(fā)生移動動作，下一時刻空間關系有可能還是原來的空間關系。如圖1～圖2所示為區(qū)間關系在動作作用下的狀態(tài)轉移圖，其中ME和MN動作的狀態(tài)轉移圖相同，MW和MS動作的狀態(tài)轉移圖相同。它由節(jié)點和有向邊組成，節(jié)點表示空間關系，節(jié)點之間有有向邊相連表示在動作作用下下一時刻的空間關系，而如果節(jié)點之間要經(jīng)過多條有向邊才能到達，則表示實體間的空間關系需要經(jīng)過多次的動作才可以到達。

圖1 ME/MN區(qū)間關系狀態(tài)轉移圖

圖2 MW/MS區(qū)間關系狀態(tài)轉移圖

區(qū)間關系的狀態(tài)轉移圖和區(qū)間關系概念鄰域如圖3所示，看上去很類似，除去有些區(qū)間關系自身到自身，把圖1和圖2合并起來就是區(qū)間關系概念鄰域圖。區(qū)間關系概念鄰域圖也沒有對時間定量化，研究2個空間實體間空間關系的連續(xù)變化。同時也是由邊和節(jié)點組成，不同的是區(qū)間關系狀態(tài)轉移圖是有向邊，因為本文研究空間關系在動作作用下的遷移，而區(qū)間關系概念鄰域圖沒有涉及動作，只是基于空間關系的連續(xù)變化。區(qū)間關系的狀態(tài)轉移圖和區(qū)間關系概念鄰域圖還有一個重要的不同是：區(qū)間關系的狀態(tài)轉移圖對應的是擁有多個空間實體的空間場景下一個空間實體動作后，下一個時刻空間場景中空間關系的變化；而區(qū)間關系概念鄰域圖只研究2個空間實體的空間關系變化，不涉及其他空間實體。

圖3 區(qū)間關系的概念鄰域圖

定義9動作作用下狀態(tài)轉移函數(shù)。Nbr(R，M)={在M動作下的狀態(tài)轉移圖上的空間關系r指向的所有基本關系|r∈R}。

給定M動作下的狀態(tài)轉移圖和指定要求解的空間關系集合R，通過對R中每個原子關系調用狀態(tài)轉移函數(shù)，所得的每個結果之間進行析取即為整個集合的動作M作用后的狀態(tài)轉移關系，如表1所示為區(qū)間關系每個原子關系的狀態(tài)轉移關系。例如求R={p，eq}，M=ME時其狀態(tài)轉移關系，通過查表1可得其狀態(tài)轉移關系是：{p，m}∪{oi}。“動作作用下狀態(tài)轉移函數(shù)”在空間實體發(fā)生動作后新的空間場景的求解中經(jīng)常用到。

表1 區(qū)間關系狀態(tài)轉移表

區(qū)間關系動作ME/MNMW/MSp{p,m}{p}pi{pi}{pi,mi}m{o}{p}mi{pi}{oi}o{o,s,eq,fi}{o,m}oi{oi,mi}{oi,si,eq,f}ssyggg00{o}si{oi}{di}d{d,f}{d,s}di{di,si}{di,fi}f{oi}syggg00fi{di}{o}eq{oi}{o}

舉例說明其在動態(tài)空間推理中的應用。例如實體A和B的矩形關系為(o，m)，實體A向東移動后，求下一時刻的A和B的空間關系。因為是向東移動，所以Y軸空間關系不變，對于X軸點區(qū)間關系如表1所示，區(qū)間關系o在ME作用下有4種情況分別是：{o，s，eq，fi}，所以實體A向東移動后的空間關系是：(o，m)∪(s，m)∪(eq，m)∪(fi，m)。

例如實體A和B的矩形關系為(o，m)，實體A向西南移動后，求下一時刻的A和B的空間關系。因為是向西南移動，可以分解成MW和MS這2個動作組合，所以對于X軸點區(qū)間關系如表1所示，區(qū)間關系o在MW作用下有2種情況為：{o，m}；對于Y軸點區(qū)間關系如表1所示，區(qū)間關系m在MS作用下只有一種情況為：{p}，所以實體A向西南移動后的空間關系是：(o，p)∪(m，p)。

2 空間場景進行形式化表示

客觀世界是不斷變化的，空間場景也同樣不斷地發(fā)生著各種各樣的變化。在定性空間推理中，大多數(shù)研究的焦點是靜態(tài)空間推理問題，即用定性空間關系表示空間實體間的關系，并在此基礎上研究復合運算、復合表和一致性判斷等問題。然而，當前面臨的問題是在一個動態(tài)變化的空間環(huán)境中，人們應該如何對動態(tài)變化的空間環(huán)境進行定義？如何對引起空間關系變化的原因進行表示？

Bhatt等人[1]定義的動態(tài)空間系統(tǒng)為在事物的內部作用和外部作用下空間配置發(fā)生變化和遷移的空間系統(tǒng)，其中空間配置由空間關系集合表示。該定義中空間關系集合是動態(tài)空間的基礎，用空間關系描述動態(tài)空間系統(tǒng)的屬性，并確定空間關系的改變是由于自身或外力的作用。

一般意義上的空間在事物活動中處于基本地位，物體在空間位置上發(fā)生各種動作。動態(tài)空間系統(tǒng)中所說的空間不僅僅是一般意義上的空間，空間實體還可以是具有行為和感知能力的實體，例如空間實體可以是人、移動的車輛和機器人等。

在一個動態(tài)空間系統(tǒng)中，各種空間關系隨時間發(fā)生變化，其中有的是自然界中無序的自發(fā)的，但更多的是有序的，帶有目的性的，例如大樓中人群的疏散和在空間環(huán)境中機器人地圖的學習?？臻g關系發(fā)生的改變必然是與動作或者事件相聯(lián)系的，可以是空間實體自身發(fā)生動作，也可以是空間實體在外力作用下發(fā)生動作?？傊詈蟮慕Y果是發(fā)生動作的空間實體與空間場景剩余空間實體的空間關系發(fā)生了改變。

空間關系是動態(tài)空間系統(tǒng)的基礎，空間有不同方面包括拓撲和方向等，用哪種空間關系更符合人們常識，同時易于計算和空間各方面轉換呢？這與特定動態(tài)空間系統(tǒng)完成的功能相關。

通過以上對動態(tài)空間系統(tǒng)的論述，對Bhatt定義的動態(tài)空間系統(tǒng)進行細化和擴展。動態(tài)空間系統(tǒng)是由空間場景構成，動作可以引起空間場景的改變?？臻g場景包含空間實體、空間關系和空間實體上所允許的動作。空間實體在動作作用下使空間場景發(fā)生改變，從而達到一定目標。其中空間實體是包含帶有行為和感知能力的空間實體以及一般的空間實體。這里論述的動態(tài)空間系統(tǒng)是個不針對特定領域、完成特定任務的空間系統(tǒng)，它是一個通用的空間系統(tǒng)。

在動態(tài)空間系統(tǒng)中，空間場景表示其基本屬性，空間場景包括了空間實體、實體間定性空間關系和空間實體所允許的動作，用一個元組表示空間場景。定義如下：

定義10空間場景用一個元組S表示，S=，B是完備互斥的定性空間原子關系集合；X是空間實體集合；R是X中的空間實體在B上成立的完全約束集合；A是空間實體允許的完備動作集合；T是B的狀態(tài)轉移表。

在基于動作的動態(tài)定性空間推理中，B是由所選擇的空間模型給出的，本文用矩形關系表示實體的空間關系，所以B為矩形關系。A是第1章所定義的8個動作。T是B對應的狀態(tài)轉移表。

在動態(tài)空間系統(tǒng)中，空間場景描述了空間實體的空間關系及實體可允許的動作，它有一個基本問題需要解決：實體在歷史場景中發(fā)生移動動作推出新空間場景。倘若允許多個空間實體同時發(fā)生動作，同時發(fā)生動作的實體需要研究它們相對動作下的空間關系變化，若沒有特定領域約束，問題變得特別復雜，所以這里假定只有一個實體發(fā)生動作。

定義11Do(S,m,M)是在空間場景S中，空間實體m發(fā)生動作M，下一個時刻新的空間場景。

例如如圖4所示的空間實體分布，實體o1發(fā)生向東南方向移動動作后得到新的空間場景可表示為Do(S,o1,MSE)。若空間實體連續(xù)發(fā)生動作，則可以得到動態(tài)空間系統(tǒng)中的空間場景序列{S1,S2,S3,…,Sn}。

圖4 區(qū)域空間實體分布圖

3 動作推出新空間場景

由定義11可知Do(S,m,M)是空間場景S在空間實體m發(fā)生動作M后下一個時刻的空間場景，空間場景S到新空間場景空間變化的改變只能是與實體m相關空間關系的改變。若已知空間場景中有n個空間實體，因為空間場景給定的是完全約束集，與實體m相關的n-1個空間關系可能發(fā)生變化(當然它自身與自身的關系在動作下不發(fā)生改變)，所以只研究這n-1個空間關系在動作作用下的情況就可以得到新空間場景。

用矩形關系表示空間場景中實體的空間關系，因此可以把動作劃分為X軸方向動作Mx和Y軸方向動作My，研究實體m與場景中實體的X軸定性關系Rmx[ ]和Y軸定性關系Rmy[ ]在Mx和My作用下的NX[ ]和NY[ ]。若給定n個空間實體，則Rmx[ ]和Rmy[ ]的個數(shù)都為n，所求的NX[ ]和NY[ ]的個數(shù)也為n。根據(jù)給定S，m，M有以下步驟：

1)提取Mx，My，Rmx[ ]和Rmy[ ]；

2)若Mx!=null，根據(jù)Mx下的狀態(tài)轉移表得到滿足路徑一致性要求的、實體m與空間場景中剩余實體的X軸定性關系NX[ ]；

3)若My!=null，根據(jù)My下的狀態(tài)轉移表得到滿足路徑一致性要求的、實體m與空間場景中剩余實體的Y軸定性關系NY[ ]；

4)若Mx!=null && My!=null，則NX[ ]與NY[ ]組合，更新空間場景；

5)若Mx!=null && My==null，則NX[ ]與Rmy[ ]組合，更新空間場景；

6)若Mx==null && My!=null，則Rmx[ ]與NY[ ]組合，更新空間場景。

需要注意的是，因為Do(S,m,M)是求下一時刻的新空間場景，根據(jù)下一個時刻的概念，當場景中有一個空間關系發(fā)生改變時，就認為是進入新空間場景。若Mx不等于null時Rmx[ ]有一個或多個不穩(wěn)定關系，此空間關系根據(jù)在Mx下的狀態(tài)轉移表得到定性關系，剩余不穩(wěn)定關系保持不變，因為不穩(wěn)定關系在動作作用下只有一個定性關系，所以可得到唯一的NX[ ]；若Rmx[ ]所有關系都是穩(wěn)定關系，那么每一個穩(wěn)定關系通過在Mx下的狀態(tài)轉移表得到一個空間關系集，從每一個空間關系集中選擇一個定性關系使得滿足路徑一致的要求可到NX[ ]，符合要求的關系序列NX[ ]可能不止一個。

方法1動作推理方法ActionReason(S，m，M)

輸入：空間場景S，發(fā)生動作實體m和發(fā)生的動作M。

輸出：實體m發(fā)生動作M后新的空間場景。

說明：valid(N[ ][ ])是判斷所選擇關系是否對空間場景是路徑一致的。

Nbr(r，M)是關系r在動作M后空間關系集合，由表1狀態(tài)轉移表獲得:

1)對輸入動作M進行X軸和Y軸劃分得到Mx和My；

2)根據(jù)場景S和動作實體m得到Rmx[ ]和Rmy[ ]；

3)若Mx!=null，判斷Rmx[ ]中是否有不穩(wěn)定關系；

①若有，當Rmx[i]為不穩(wěn)定關系，則NX[i]= Nbr(Rmx[i]，Mx)；當Rmx[j]為穩(wěn)定關系，令NX[j]=Rmx[j]。得到唯一NX[ ]，轉到步驟5；

②否則轉到步驟4；

4)對于每一個Rmx[i]，可以得到空間關系集合Nx[i][ ]=Nbr(Rmx[i]，Mx)，從而可得到NX[ ]=valid(Nx[ ][ ])；

5)若My!=null，判斷Rmy[ ]中是否有不穩(wěn)定關系；

①若有，當Rmy[i]為不穩(wěn)定關系，則NY[i]= Nbr(Rmy[i]，My)；當Rmy[j]為穩(wěn)定關系，令NY[j]=Rmy[j]；得到唯一NY[ ]，轉到步驟7；

②否則轉到步驟6；

6)對于每一個Rmy[i]，可得到空間關系集合Ny[i][ ]= Nbr(Rmy[i]，My)，從而可得到NY[ ]=valid(Ny[ ][ ])；

7)若Mx!=null && My!=null，則NX[ ]與NY[ ]組合，更新空間場景；

8)若Mx!=null && My==null，則NX[ ]與Rmy[ ]組合，更新空間場景；

9)若Mx==null && My!=null，則Rmx[ ]與NY[ ]組合，更新空間場景；

10)返回。

對于valid (N[ ][ ])有：

輸入：Rmx[ ](Rmy[ ])的空間關系集。

輸出：滿足路徑一致性要求的關系集。

1)對于每一個定性關系集合N[0][ ],…,N[n-1][ ]選擇一個區(qū)間關系，得到n個定性系列M[ ]；

2)對于一個M[i]， 0≤i

①對于一個M[j]， i

a 判斷M[i]-1。M[j]∧Rx[i，j]==1是否為真；

b 若為真，j++；

c 若為假，退出循環(huán)轉到步驟1，重新選擇一組M[ ]。

②i++；

3)得到滿足一致性要求的M[ ]。

對于輸入空間原語為區(qū)域的空間實體，若有如圖4所示的空間實體分布，圖4中空間實體的完全約束關系集如表2所示。

表2 空間關系完全約束集

o1o2o3o4o1(eq,eq)(fi,fi)(di,si)(di,di)o2(f,f)(eq,eq)(pi,pi)(pi,pi)o3(d,s)(p,p)(eq,eq)(p,p)o4(d,d)(p,p)(pi,pi)(eq,eq)

在圖4所示實體分布下求Do(S,o4,MNE)可知m=o4，M=MNE，得到R4x[0]=d，R4x[1]=p，R4x[2]=pi，R4x[3]=eq，都是穩(wěn)定關系；R4y[0]=d，R4y[1]=p，R4y[2]=pi，R4y[3]=eq，都是穩(wěn)定關系。

因為M=MNE，可以看成是ME和MN共同作用，所以R4x[ ]在ME作用下Nx[0][ ]={d,f}，Nx[1][ ]={p,m}，Nx[2][ ]={pi}，Nx[3][ ]={eq}；R4y[ ]在MN作用下Ny[0][ ]={d,f}，Ny[1][ ]={p,m}，Ny[2][ ]={pi}，Ny[3][ ]={eq}。

通過一致性檢測滿足要求的有：NX[ ]={d,p,pi,eq}∨{d,m,pi,eq}；NY[ ]={d,m,pi,eq}∨{d,p,pi,eq}。NX[ ]和NY[ ]通過組合可以得到4種空間場景，其中一種與原來空間場景一樣，所以新的空間場景S1有3個，如表3～表5所示，其動作后實體分布如圖5所示，符合實體o4發(fā)生動作MNE后的實體分布。

方法1 ActionReason(S，m，M)用于求空間場景S中一個空間實體m發(fā)生動作M后的新空間場景，若有多個空間實體同時發(fā)生動作，要考慮同時動作實體在相對動作作用下的空間關系變化，若沒有給定領域約束條件將很難求解。本文的研究不是針對特定的應用場景，沒有領域約束，所以方法1只能適用于一個實體發(fā)生動作。

表3 o4發(fā)生動作MNE后S1完全空間關系約束集(1)

o1o2o3o4o1(eq,eq)(fi,fi)(di,si)(di,di)o2(f,f)(eq,eq)(pi,pi)(pi,mi)o3(d,s)(p,p)(eq,eq)(p,p)o4(d,d)(p,m)(pi,pi)(eq,eq)

表4 o4發(fā)生動作MNE后S1完全空間關系約束集(2)

o1o2o3o4o1(eq,eq)(fi,fi)(di,si)(di,di)o2(f,f)(eq,eq)(pi,pi)(mi,pi)o3(d,s)(p,p)(eq,eq)(p,p)o4(d,d)(m,p)(pi,pi)(eq,eq)

表5 o4發(fā)生動作MNE后S1完全空間關系約束集(3)

o1o2o3o4o1(eq,eq)(fi,fi)(di,si)(di,di)o2(f,f)(eq,eq)(pi,pi)(mi,mi)o3(d,s)(p,p)(eq,eq)(p,p)o4(d,d)(m,m)(pi,pi)(eq,eq)

圖5 實體o4發(fā)生動作MNE后新空間場景

在一個動態(tài)空間環(huán)境中，有n個空間實體，初始空間場景中a和b空間關系為R(a,b)=R1。當a發(fā)生移動動作序列，求從R(a,b)=R1到R(a,b)=R2的過程中的一個空間場景序列。這在機器人導航中有重要的應用，這個問題可以轉化為Agent從位置L1到位置L2移動過程中的空間關系變化過程。

例如，如圖4所示空間實體分布，若o2要到達o3的西南方，求o2移動過程中空間場景序列。圖4中R1=(pi,pi)，因為o2要到達o3的西南方，通過查矩形關系與方向關系對應表可得到R2=(p,p)。從R1到R2變化過程中，X軸方向上是pi到p，由區(qū)間關系的狀態(tài)轉移圖可知o2在X軸方向發(fā)生的動作是Mx=MW；Y軸方向上是pi到p，由區(qū)間關系的狀態(tài)轉移圖可知o2在Y軸方向發(fā)生的動作是My=MS。o2要到達o3的西南方，o2可選擇多種動作序列例如{MSW，MSW，…}，{MW，MW，…，MS，MS，…}，{MS，MS，…，MW，MW，…}等。由o2選擇的移動動作序列，可以得到一序列空間場景序列，這些空間場景序列描述著o2從一個位置L1到位置L2空間場景的改變過程。

4 結束語

本文在定性空間推理基礎上，研究擁有多個空間實體的空間場景下基于動作的動態(tài)空間推理問題。定義了空間實體的8個移動動作，給出了空間實體在動作作用下的狀態(tài)轉態(tài)圖和狀態(tài)轉移表，并對概念鄰域圖和狀態(tài)轉移圖進行對比，指出其相同點和不同點。用一個元組對動態(tài)空間系統(tǒng)中的空間場景進行形式化表示，提出了由實體移動動作推出新空間場景方法，并指出方法的局限和不足，同時給出一個應用場景。以概念鄰域圖為基礎研究單個空間關系變化問題相比復雜度有所提高，對動態(tài)空間推理和表示有一定的理論和實際應用價值。

動態(tài)定性空間推理已經(jīng)成為定性空間推理中的研究熱點，且其關乎到實際應用。本文對動態(tài)空間系統(tǒng)的論述不太全面，隨著動態(tài)空間推理技術的發(fā)展，對動態(tài)空間系統(tǒng)應該有更深的認識和研究。在實際應用中存在多個實體同時發(fā)生動作，且其作用在實體的時間都不一樣，所以情況就非常復雜，對所提方法缺乏數(shù)學的證明，這些都是下一步要做的工作。

[1] Bhatt M, Loke S. Modelling dynamaic spatial systems in the situation calculus[J]. Spatial Cognition and Computation, 2008,8(1-2):86-130.

[2] Bhatt M, Guesgen H, Wolfl S, et al. Qualitative spatial and temporal reasoning: Emerging applications,trends,and directions[J]. Spatial Cognition & Computation, 2011,11(1):1-14.

[3] Freksa C. Conceptual neighborhood and its role in temporal and spatial reasoning[M]// Decision Support Systems and Qualitative Reasoning. 1991:181-187.

[4] Egenhofer M J, Al-Taha K K. Reasoning about gradual changes of topological relationships[M]// Theories and Methods of Spatio-temporal Reasoning in Geographic Space. 1992:196-219.

[5] Rajagoplan R. A model for integrated qualitative spatial and dynamic reasoning about physical systems[C]// Proceedings of the 12th National Conference on Artificial Intelligence(AAAI-94). 1994:1411-1417.

[6] Dylla F, Moratz R. Exploiting qualitative spatial neighborhoods in the situation calculus[C]// Proceedings of the 4th International Conference on Spatial Cognition IV Reasoning, Action, Interaction. 2004:304-332.

[7] Bhatt M, Rahayu W, Sterling G. Qualitative spatial reasoning with topological relations in the situation calculus[C]// Proceedings of the 19th International Florida Artificial Intelligence Research Society Conference. 2006:713-718.

[8] Delafontaine M, Weghe N V D, Bogaert P， et al. Qualitative relations between moving objects in a network changing its topological relations[J]. Information Sciences, 2008,178(8):1997-2006.

[9] Bhatt M. Reasoning about Space, actions, and change: A paradigm for applications of spatial reasoning[M]// Qualitative Spatio-temporal Representation and Reasoning: Trends and Future Directions. 2012:284-320.

[10] Bhatt M. Commonsense inference in dynamic spatial systems: Epistemological requirements[C]// The 23rd International Florida Artificial Intelligence Research Society Conference (FLAIRS 2010). 2010:3-20.

[11] Suchan J, Bhatt M, Schultz C. Deeply semantic inductive spatio-temporal learning[C]// The 26th International Conference on Inductive Logic Programming. 2016:73-80.

[13] 梁晶晶. 空間推理中多種空間關系結合和時空變化的研究[D]. 西安:西安交通大學， 2011．

[14] Song Xiaohua, Quyang Dantong. Automated planning method for dealing with dynamic spatial relations[J]. Journal of Software, 2012,23(10):2564-2571.

[15] 楊帥. 動態(tài)空間中運動區(qū)間與靜止區(qū)間統(tǒng)一表達模型的研究[D]. 長春:吉林大學, 2014.

[16] Zhou Yan, Wang Zhe, He Di. Spatial-temporal reasoning of Geovideo data based on ontology[C]// 2016 IEEE International Geoscience and Remote Sensing Symposium (IGARSS). 2016:4470-4473.

[17] Bhatt M, Guesgen H, Hazarika S. Proceedings of the workshop on Spatio-Temporal dynamics(STeDy)[C]// IJCAI 2015: International Joint Conference on Artificial Intelligence(Buenos Aires, Argentina). 2015.