基于動(dòng)作的動(dòng)態(tài)空間推理

謝玉枚,高海燕

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

0 引 言

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

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

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

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

綜上所述，動(dòng)態(tài)空間推理是定性空間推理的研究熱點(diǎn)，目前還處于起步研究階段，大多數(shù)研究?jī)H限于提出動(dòng)態(tài)空間推理的框架和相關(guān)可能的應(yīng)用場(chǎng)景，沒(méi)有對(duì)其中的動(dòng)作、事件、空間關(guān)系具體化和動(dòng)作作用下多個(gè)空間實(shí)體間空間關(guān)系改變情況[17]。

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

1 動(dòng)作及區(qū)間關(guān)系的狀態(tài)轉(zhuǎn)移圖

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

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

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

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

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

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

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

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

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

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

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

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

在以區(qū)域?yàn)榭臻g原語(yǔ)中，某一個(gè)空間實(shí)體發(fā)生移動(dòng)動(dòng)作，這個(gè)實(shí)體與空間場(chǎng)景中其他實(shí)體的空間關(guān)系可能發(fā)生改變，從而得到新的空間場(chǎng)景。在這里沒(méi)有對(duì)實(shí)體發(fā)生動(dòng)作的時(shí)間進(jìn)行量化，而是對(duì)其進(jìn)行定性化處理，認(rèn)為發(fā)生動(dòng)作的實(shí)體與空間場(chǎng)景中剩余實(shí)體的空間關(guān)系只要一個(gè)或多個(gè)發(fā)生變化，就認(rèn)為是進(jìn)入下一時(shí)刻，得到新的空間場(chǎng)景。

對(duì)于空間原語(yǔ)實(shí)體為區(qū)域的空間實(shí)體，用MBR近似空間區(qū)域，用矩形關(guān)系表示空間實(shí)體空間關(guān)系，在表達(dá)上簡(jiǎn)單明了，易于理解。因?yàn)樵诙S空間的每個(gè)坐標(biāo)軸上使用區(qū)間代數(shù)的理論，從而形成矩形代數(shù)理論，其中的關(guān)系就是矩形關(guān)系，空間實(shí)體在動(dòng)作作用下的矩形關(guān)系變化表現(xiàn)為X軸和Y軸方向上區(qū)間關(guān)系的變化，所以本文只研究區(qū)間關(guān)系在動(dòng)作作用下的變化的情況。

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

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

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

區(qū)間關(guān)系的狀態(tài)轉(zhuǎn)移圖和區(qū)間關(guān)系概念鄰域如圖3所示，看上去很類似，除去有些區(qū)間關(guān)系自身到自身，把圖1和圖2合并起來(lái)就是區(qū)間關(guān)系概念鄰域圖。區(qū)間關(guān)系概念鄰域圖也沒(méi)有對(duì)時(shí)間定量化，研究2個(gè)空間實(shí)體間空間關(guān)系的連續(xù)變化。同時(shí)也是由邊和節(jié)點(diǎn)組成，不同的是區(qū)間關(guān)系狀態(tài)轉(zhuǎn)移圖是有向邊，因?yàn)楸疚难芯靠臻g關(guān)系在動(dòng)作作用下的遷移，而區(qū)間關(guān)系概念鄰域圖沒(méi)有涉及動(dòng)作，只是基于空間關(guān)系的連續(xù)變化。區(qū)間關(guān)系的狀態(tài)轉(zhuǎn)移圖和區(qū)間關(guān)系概念鄰域圖還有一個(gè)重要的不同是：區(qū)間關(guān)系的狀態(tài)轉(zhuǎn)移圖對(duì)應(yīng)的是擁有多個(gè)空間實(shí)體的空間場(chǎng)景下一個(gè)空間實(shí)體動(dòng)作后，下一個(gè)時(shí)刻空間場(chǎng)景中空間關(guān)系的變化；而區(qū)間關(guān)系概念鄰域圖只研究2個(gè)空間實(shí)體的空間關(guān)系變化，不涉及其他空間實(shí)體。

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

定義9動(dòng)作作用下?tīng)顟B(tài)轉(zhuǎn)移函數(shù)。Nbr(R，M)={在M動(dòng)作下的狀態(tài)轉(zhuǎn)移圖上的空間關(guān)系r指向的所有基本關(guān)系|r∈R}。

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

表1 區(qū)間關(guān)系狀態(tài)轉(zhuǎn)移表

區(qū)間關(guān)系動(dòng)作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}sj5i0abt0b{o}si{oi}{di}d{d,f}{d,s}di{di,si}{di,fi}f{oi}j5i0abt0bfi{di}{o}eq{oi}{o}

舉例說(shuō)明其在動(dòng)態(tài)空間推理中的應(yīng)用。例如實(shí)體A和B的矩形關(guān)系為(o，m)，實(shí)體A向東移動(dòng)后，求下一時(shí)刻的A和B的空間關(guān)系。因?yàn)槭窍驏|移動(dòng)，所以Y軸空間關(guān)系不變，對(duì)于X軸點(diǎn)區(qū)間關(guān)系如表1所示，區(qū)間關(guān)系o在ME作用下有4種情況分別是：{o，s，eq，fi}，所以實(shí)體A向東移動(dòng)后的空間關(guān)系是：(o，m)∪(s，m)∪(eq，m)∪(fi，m)。

例如實(shí)體A和B的矩形關(guān)系為(o，m)，實(shí)體A向西南移動(dòng)后，求下一時(shí)刻的A和B的空間關(guān)系。因?yàn)槭窍蛭髂弦苿?dòng)，可以分解成MW和MS這2個(gè)動(dòng)作組合，所以對(duì)于X軸點(diǎn)區(qū)間關(guān)系如表1所示，區(qū)間關(guān)系o在MW作用下有2種情況為：{o，m}；對(duì)于Y軸點(diǎn)區(qū)間關(guān)系如表1所示，區(qū)間關(guān)系m在MS作用下只有一種情況為：{p}，所以實(shí)體A向西南移動(dòng)后的空間關(guān)系是：(o，p)∪(m，p)。

2 空間場(chǎng)景進(jìn)行形式化表示

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

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

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

在一個(gè)動(dòng)態(tài)空間系統(tǒng)中，各種空間關(guān)系隨時(shí)間發(fā)生變化，其中有的是自然界中無(wú)序的自發(fā)的，但更多的是有序的，帶有目的性的，例如大樓中人群的疏散和在空間環(huán)境中機(jī)器人地圖的學(xué)習(xí)?？臻g關(guān)系發(fā)生的改變必然是與動(dòng)作或者事件相聯(lián)系的，可以是空間實(shí)體自身發(fā)生動(dòng)作，也可以是空間實(shí)體在外力作用下發(fā)生動(dòng)作。總之最后的結(jié)果是發(fā)生動(dòng)作的空間實(shí)體與空間場(chǎng)景剩余空間實(shí)體的空間關(guān)系發(fā)生了改變。

空間關(guān)系是動(dòng)態(tài)空間系統(tǒng)的基礎(chǔ)，空間有不同方面包括拓?fù)浜头较虻龋媚姆N空間關(guān)系更符合人們常識(shí)，同時(shí)易于計(jì)算和空間各方面轉(zhuǎn)換呢？這與特定動(dòng)態(tài)空間系統(tǒng)完成的功能相關(guān)。

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

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

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

在基于動(dòng)作的動(dòng)態(tài)定性空間推理中，B是由所選擇的空間模型給出的，本文用矩形關(guān)系表示實(shí)體的空間關(guān)系，所以B為矩形關(guān)系。A是第1章所定義的8個(gè)動(dòng)作。T是B對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移表。

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

定義11Do(S,m,M)是在空間場(chǎng)景S中，空間實(shí)體m發(fā)生動(dòng)作M，下一個(gè)時(shí)刻新的空間場(chǎng)景。

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

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

3 動(dòng)作推出新空間場(chǎng)景

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

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

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

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

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

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

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

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

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

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

輸入：空間場(chǎng)景S，發(fā)生動(dòng)作實(shí)體m和發(fā)生的動(dòng)作M。

輸出：實(shí)體m發(fā)生動(dòng)作M后新的空間場(chǎng)景。

說(shuō)明：valid(N[ ][ ])是判斷所選擇關(guān)系是否對(duì)空間場(chǎng)景是路徑一致的。

Nbr(r，M)是關(guān)系r在動(dòng)作M后空間關(guān)系集合，由表1狀態(tài)轉(zhuǎn)移表獲得:

1)對(duì)輸入動(dòng)作M進(jìn)行X軸和Y軸劃分得到Mx和My；

2)根據(jù)場(chǎng)景S和動(dòng)作實(shí)體m得到Rmx[ ]和Rmy[ ]；

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

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

②否則轉(zhuǎn)到步驟4；

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

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

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

②否則轉(zhuǎn)到步驟6；

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

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

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

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

10)返回。

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

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

輸出：滿足路徑一致性要求的關(guān)系集。

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

2)對(duì)于一個(gè)M[i]， 0≤i

①對(duì)于一個(gè)M[j]， i

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

b 若為真，j++；

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

②i++；

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

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

表2 空間關(guān)系完全約束集

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所示實(shí)體分布下求Do(S,o4,MNE)可知m=o4，M=MNE，得到R4x[0]=d，R4x[1]=p，R4x[2]=pi，R4x[3]=eq，都是穩(wěn)定關(guān)系；R4y[0]=d，R4y[1]=p，R4y[2]=pi，R4y[3]=eq，都是穩(wěn)定關(guān)系。

因?yàn)镸=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}。

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

方法1 ActionReason(S，m，M)用于求空間場(chǎng)景S中一個(gè)空間實(shí)體m發(fā)生動(dòng)作M后的新空間場(chǎng)景，若有多個(gè)空間實(shí)體同時(shí)發(fā)生動(dòng)作，要考慮同時(shí)動(dòng)作實(shí)體在相對(duì)動(dòng)作作用下的空間關(guān)系變化，若沒(méi)有給定領(lǐng)域約束條件將很難求解。本文的研究不是針對(duì)特定的應(yīng)用場(chǎng)景，沒(méi)有領(lǐng)域約束，所以方法1只能適用于一個(gè)實(shí)體發(fā)生動(dòng)作。

表3 o4發(fā)生動(dòng)作MNE后S1完全空間關(guān)系約束集(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ā)生動(dòng)作MNE后S1完全空間關(guān)系約束集(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ā)生動(dòng)作MNE后S1完全空間關(guān)系約束集(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 實(shí)體o4發(fā)生動(dòng)作MNE后新空間場(chǎng)景

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

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

4 結(jié)束語(yǔ)

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

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

[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] 梁晶晶. 空間推理中多種空間關(guān)系結(jié)合和時(shí)空變化的研究[D]. 西安:西安交通大學(xué)， 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] 楊帥. 動(dòng)態(tài)空間中運(yùn)動(dòng)區(qū)間與靜止區(qū)間統(tǒng)一表達(dá)模型的研究[D]. 長(zhǎng)春:吉林大學(xué), 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.