歐陽繼紅，祝東紅，，富 倩，楊 帥，陳 思

（1.吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，長春130012；2.吉林大學(xué) 符號計算與知識工程教育部重點實驗室，長春130012）

0 引 言

空間推理是人工智能、地理信息系統(tǒng)、機器人、計算視覺、圖像檢索、自然語言處理等領(lǐng)域的重要內(nèi)容［1］。空間推理主要研究拓?fù)浜头轿魂P(guān)系，王生生等［2］給出了有向線對象細(xì)節(jié)拓?fù)潢P(guān)系模型；Moratz［3］提出了具有可擴展粒度方位點關(guān)系代數(shù)OPRAm模型，用于描述方位點的相對方位關(guān)系。Dylla等［4］給出OPRAm模型的概念鄰域圖。Moratz等［5］給出了其復(fù)合算法。

近年來，隨著空間推理應(yīng)用研究的不斷深入，三維空間的應(yīng)用研究越來越多，因此需要研究適用于三維空間的方位關(guān)系表達和推理模型［6］。關(guān)于三維空間方位關(guān)系的研究主要分為兩方面：點對象間相對方位關(guān)系和區(qū)域?qū)ο箝g的方位關(guān)系，如Pacheco等［7］提出的三維點對象間的相對方位關(guān)系模型和Chen等［6］提出的基于MBR 的三維區(qū)域?qū)ο箝g的主方位模型。然而Pacheco提出的模型是基于雙十字模型的，對空間關(guān)系劃分不夠細(xì)致，表達相對方位關(guān)系較弱。Chen等提出的模型是針對區(qū)域的，區(qū)域?qū)ο箝g的方向關(guān)系比點對象之間的方向關(guān)系較為復(fù)雜。然而在實際應(yīng)用中當(dāng)對象間距離比較大時，通常將對象抽象為點更為合適，同時也降低了方位關(guān)系的復(fù)雜度。因此，需要研究適用于三維空間點對象間的相對方位關(guān)系表達和推理模型。

本文基于二維OPRAm模型，通過引入新的三維空間的兩個相對角來表達三維相對方位信息，得到三維點對象間的相對方位關(guān)系模型3DOPRAm。在此基礎(chǔ)上，給出了3DOPRAm模型的概念鄰域及導(dǎo)航問題的形式化表示。最后，采用新模型基于動作的鄰域關(guān)系描述了汽車導(dǎo)航問題。

1 相關(guān)理論

1.1 方位點關(guān)系代數(shù)OPRAm

Moratz［3］在直線段模型的基礎(chǔ)上提出了一種具有可擴展粒度的相對方位關(guān)系模型OPRAm，使用一個方位點（有方向的點）表示空間對象。粒度參數(shù)m ＞0∈n決定方位點的區(qū)分粒度，m 條線將二維平面劃分為2m 個線性區(qū)域和2m 個平面區(qū)域。區(qū)域按逆時針方向從0到（4m－1）進行編號，區(qū)域0和方位點的本質(zhì)方向重合。圖1給出了m＝2（見圖1（a））和m＝4（見圖1（b））時，平面上不同位置方位點A 和B 的相對方位關(guān)系；圖1（c）給出了平面上兩個相同位置方位點的相對方位關(guān)系。

圖1 兩個方位點之間的相對方位關(guān)系Fig.1 Relative directions between two oriented point

1.2 鄰域劃分圖

Freksa［8］首次定義了概念鄰域圖（Conceptual neighborhoods graph，CNG），并將概念鄰域結(jié)構(gòu)用于處理時間區(qū)間代數(shù)中時間區(qū)間連續(xù)變化的問題。宋小華等［9］指出概念鄰域圖只給出了空間關(guān)系變化的結(jié)果，沒有給出空間關(guān)系變化的原因，不知道是什么引起空間關(guān)系發(fā)生變化。宋小華在概念鄰域圖的基礎(chǔ)上，引入“動作”的概念，他認(rèn)為空間關(guān)系的變化是因為在對象上施加了動作。

如果有動作關(guān)系集合A，能夠使互斥完備的基本關(guān)系集合B 概念鄰域圖CNG（B）中的鄰域關(guān)系相互轉(zhuǎn)換，則稱集合A 為完備動作關(guān)系集合。由完備動作關(guān)系集合A、基本關(guān)系集合B 和B通過A 轉(zhuǎn)變的鄰域關(guān)系集合≈，構(gòu)造一個能表示基本關(guān)系隨動作變化的圖，則稱此圖為鄰域劃分圖（Neighborhood partition graph，NPG），其形式表示如下：

對任意原子關(guān)系b ∈B，其基于動作的鄰域關(guān)系表示為np（b），其形式表示如下：

2 三維相對方位關(guān)系3DOPRAm

2.1 三維空間中粗粒度方位點模型

三維空間中，以點為空間變量，方位點使用有序?qū)＝（PS，δS）表示，其中PS是方位點S 的笛卡爾坐標(biāo)PS＝（xS，yS，zS）；δS表示方位點的本質(zhì)方向。δS平行于地面，它所在的平面為xoy 面，垂直于xoy 面的方向為z 軸，圖2 為3DOPRAm模型參照系。

使用xoy 面的相對方位和z 軸的相對方位組合表示三維空間的相對方位關(guān)系。其中xoy 面的方位劃分如圖3所示，使用字母f、b、l、r、lf、rf、lb、rb 代 表 front、back、left、right、leftfront、rightfront、leftback、rightback；z 軸方位劃分如圖4所示，使用字母U（up）、D（down）分別表示位于xoy 面的上方和下方；E（equal）表示恰好在xoy 平面上；前兩個“＊”表示xoy 面上的方位關(guān)系，第3個字母表示z軸方位關(guān)系。

圖2 3DOPRAm 模型參照系Fig.2 Reference system of the 3DOPRAm model

圖3 xoy面方位劃分Fig.3 Directions in the xoyplane

圖4 z軸方位劃分Fig.4 Directions of the z－axis

為了區(qū)分三維空間中的兩個方位點A 和B，令A(yù) ＝（PA，δA），其中PA＝（xA，yA，zA），令B ＝（PB，δB），其 中PB＝ （xB，yB，zB）。對 二 維OPRAm模型相對角進行擴展，引入兩個相對角φAB和θAB，如圖5所示，其定義如下：

式中：φAB 為方位點B 在方位點A 所確定的xoy面投影后，兩個方位點之間的反正切值。

式中：θAB為方位點B 和方位點A 之間連線與xoy面所成的角。

圖5 三維空間中方位點A 和B 之間的相對角φAB 和θABFig.5 Relative anglesφAB andθAB of two oriented points in the three dimensions

在三維空間中，φAB－δA表示方位點B 在方位點A 所確定的xoy 面方位；φBA－δB表示方位點A在方位點B 所確定的xoy面的方位。相對角θAB表示方位點B 在方位點A 的z 軸方位。其中φAB－δA和θAB對應(yīng)角度的變化構(gòu)成方位點A 所在的歐幾里得空間的完備劃分，其所對應(yīng)的方位和角度變化如表1所示，方位點B 所在歐幾里得空間的劃分和方位點A 類似。

2.2 三維空間中粗粒度方位點相對方位關(guān)系

三維空間中，使用三元組（QAB、QBA、ZAB）表示空間中的兩個方位點之間的方位關(guān)系。QAB表示xoy 面上方位點A 相對于方位點B 的方位關(guān)系；QBA表示xoy 面上方位點B 相對于方位點A的方位關(guān)系；ZAB表示方位點B 相對于方位點A的z 軸方位關(guān)系。

xoy 面上，兩個方位點在不同位置時，總共有8×8＝64種基本關(guān)系。當(dāng)兩個方位點在同一位置時，有8種方位關(guān)系；故xoy 平面上共有72種原子方位關(guān)系。z 軸有以下5種方位關(guān)系ZAB＝｛U1、U2、D1、D2、E｝。可得出三維空間中總共有360種方位關(guān)系。

表1 方位點A 所在三維歐幾里得空間劃分Table 1 Apartition of oriented point A on the Euclidean plane

2.3 可擴展粒度3DOPRAm 模型

空間演算的粒度和空間結(jié)果的數(shù)學(xué)特性是解決定性空間任務(wù)的主要問題［10］。在實際應(yīng)用中（如復(fù)雜導(dǎo)航任務(wù)），依據(jù)所處的環(huán)境、機器人的處理能力、任務(wù)的要求，需要不同粒度下的方位關(guān)系，因此引入了可擴展粒度。選擇合適的粒度參數(shù)可以忽略一些不能引起變化的推理步驟，加快計算速度。

將上述粗粒度相對方位關(guān)系的設(shè)計準(zhǔn)則擴展到多粒度的情況，得到3DOPRAm，其中m 為粒度參數(shù)，m ＞0∈n將二維平面劃分為2m 個線性區(qū)域和2m 個平面區(qū)域。區(qū)域按逆時針方向從0到（4m－1）編號，區(qū)域0和方位點的本質(zhì)方向重合。m 條線將z 軸正半軸劃分成m 個方位，從xoy 面按逆時針編號；將z軸負(fù)半軸劃分成m 個方位，從xoy 面按順時針編號。

xoy 面上，可擴展粒度方位關(guān)系中每一個方向片i滿足如下角度范圍：

方向片j的角度范圍和方向片i 相同。當(dāng)PAPB時，使用關(guān)系A(chǔ)∠ijB 表示如下含義：給定粒度m，以B 為參照對象，A 相對于B 的位置用j描述，以A為參照對象，B相對于A 的位置用i描述。其中方向片i，j滿足如下幾何結(jié)構(gòu)：

當(dāng)PA＝PB時，使用關(guān)系A(chǔ)∠iB 表示如下含義：給定粒度m，以A 為參照對象，B 位于A 的方位。方向片i滿足如下幾何結(jié)構(gòu)：

在z軸上的方位，可擴展粒度方位關(guān)系中方向片h滿足如下角度范圍：

A∠hB 表示以A 為參照對象，B 相對于A 的高度范圍。方向片h滿足如下幾何結(jié)構(gòu)：

三維空間中的相對方位關(guān)系用xoy 面和z 軸相對方位關(guān)系組合表示，對三維空間中的方位點A 和B，當(dāng)A 和B 的位置不同時，使用表示，含義為：xoy 面上，對于B而言，B在A 的方位用i表示。對于A 而言，A 在B 的方位用j 表示；z軸上，h表示以A 為參照對象，B相對于A 的高度。當(dāng)A 和B 的位置相同時，使用A∠ihB 表示，含義為：對于B而言，B在A 的xoy 面的方位用i表示，z軸的方位用h 表示。圖6和圖7為粒度m ＝2的三維空間中方位點的相對方位關(guān)系：表示角度范圍為：φAB－δA＝3π／2，φBA－δB＝π／4，θAB∈（π／4，π／2］。A2∠40B 表示角度范圍為δBδA＝π，θAB＝0。

圖6 不同位置兩個方位點的相對方位關(guān)系Fig.6 Two o－point in relation relation at different position

2.4 3DOPRAm 相對方位關(guān)系的逆

方向關(guān)系取逆操作是方向關(guān)系的基本運算之一，對于空間中的兩個點對象A 和B，已知它們的關(guān)系為R ＝（A，B），通過求逆操作可以得到R ＝（B，A）。在3DOPRAm模型中，通過簡單的符號操作，即可求得3DOPRAm模型的逆操作。

當(dāng)三維空間中方位點A 和B 在不同位置時，方位點的逆為：

當(dāng)方位點A 和B 在相同位置時，方位點的逆為：

圖7 相同位置方位點的相對方位關(guān)系A(chǔ)2∠40BFig.7 Two o－point in A2∠40Bat the same position

3 3DOPRAm 概念鄰域及定性空間導(dǎo)航問題

為了將3DOPRAm模型用于描述定性空間導(dǎo)航問題，本文給出了基于3DOPRAm模型的概念鄰域及導(dǎo)航問題形式化的表示。通過設(shè)定規(guī)則，將動作引起鄰域關(guān)系變化用于求解導(dǎo)航問題。

3.1 3DOPRAm 概念鄰域

基于二維空間中OPRAm模型的概念鄰域，給出了3DOPRAm模型的概念鄰域。由于在實際應(yīng)用中，不同空間對象所施加的動作是不同的，或者是在研究空間關(guān)系時，因為參照對象是較少發(fā)生變化或基本不發(fā)生變化，只需要研究目標(biāo)對象的動作即可，因此針對3DOPRAm模型，需要根據(jù)實際應(yīng)用場景和特定相對方位關(guān)系，給出其引起關(guān)系變化的動作。

當(dāng)三維空間中相對方位關(guān)系為Am∠jihB 時，對A 和B 施加任意動作可得到如下概念鄰域：

當(dāng)三維空間中相對方位關(guān)系為Am∠shB 時，對A 和B 施加任意動作可得到如下概念鄰域：

3.2 定性空間導(dǎo)航問題

宋小華等［9］提出了定性空間關(guān)系自動規(guī)劃的形式化表示和推理算法，并證明此算法的可靠性，同時指出其方法在處理單方面空間關(guān)系規(guī)劃中具有通用性?；诖怂枷?，本文給出了定性空間導(dǎo)航問題的形式化表示和基本求解思路。

定性空間導(dǎo)航問題描述：直觀上，定性空間關(guān)系的導(dǎo)航就是給定初始狀態(tài)對象間的空間關(guān)系和目標(biāo)狀態(tài)對象間的空間關(guān)系的表示，求解從初始狀態(tài)到目標(biāo)狀態(tài)的動作序列。

定義1 定性空間關(guān)系導(dǎo)航是一個動作序列π＝〈a1，a2，…，ak〉，其 中k ≥0，導(dǎo) 航 的 長 度 是｜π｜＝k，即動作數(shù)目。

定義2 稱N ＝（s，g）是一個定性空間關(guān)系導(dǎo)航問題，其中s為定性空間關(guān)系初始狀態(tài)；g 為定性空間關(guān)系目標(biāo)狀態(tài)，從s經(jīng)過動作序列π到達目標(biāo)狀態(tài)g，則π是N 的一個解。

定性空間關(guān)系導(dǎo)航問題求解：

求解定性空間關(guān)系導(dǎo)航問題，就是以N ＝（s，g）作為輸入，求解動作序列π的過程。

使用遞歸回溯方法求解此類問題，其基本思路為：對初始鄰域狀態(tài)分別按順序施加動作，到達下一個動作鄰域狀態(tài)。刪除掉規(guī)則不允許和產(chǎn)生循環(huán)的動作鄰域狀態(tài)后，對產(chǎn)生的動作鄰域狀態(tài)進行遞歸求解，直至轉(zhuǎn)換到目標(biāo)狀態(tài)。如果找不到目標(biāo)狀態(tài)，返回失敗。

4 應(yīng)用舉例

基于3DOPRAm動作鄰域關(guān)系對立交橋上的汽車進行導(dǎo)航。以粒度m ＝2為例，粒度m ＝2將xoy 面的方位分為0、1、2、3、4、5、6共七個方向片，將z軸方位分為0，1，2，－1，－2共五個方向片。

如圖8所示，立交橋的入口處有個汽車，其運動狀態(tài)如方位點A所示。分別設(shè)置如圖8所示的3個目標(biāo)狀態(tài)，如方位點B、C、D 所示，3個方位點的方向為箭頭的方向。汽車可操作的動作分別為向前、向后（倒車操作）、向左（即車頭轉(zhuǎn)向左行駛）、向右（即車頭轉(zhuǎn)向右行駛）、向上（沿坡道向上行駛）、向下（沿坡道向下行駛）共6個動作，在立交橋一些位置制定一些交通規(guī)則，對汽車進行導(dǎo)航，求解出汽車從方位點A 所示狀態(tài)變化到方位點B、C、D 所示狀態(tài)的動作序列。

以汽車從方位點A 所示狀態(tài)變化到方位點C所示狀態(tài)為例說明基于動作鄰域關(guān)系變化的導(dǎo)航問題的求解過程。

圖8 立交橋汽車導(dǎo)航場景Fig.8 Spatial scenario about Car Navigation on the flyover

方位點A 和方位點C 的最終相對方位關(guān)系為：A2∠00C

對汽車施加如下動作序列：向前、向前、向右、向右、向右、向下、向前、向右、向右、向下、向右、向前，得到狀態(tài)變化如下：

同樣，得到方位點A 到達方位點B 和D 的動作序列分別為：向右、向上、向前、向前，它們的狀態(tài)變化如下：

5 結(jié)束語

在OPRAm模型的基礎(chǔ)上，提出了點對象間的相對方位模型3DOPRAm，此模型不僅能夠表示平面上的前后左右等方位關(guān)系，而且能夠表示高度的上中下等方位關(guān)系，具有更強的表達能力。與已有三維點對象間相對方位模型——雙十字模型相比，此模型具有可擴展粒度m，能表達更細(xì)致的方位關(guān)系。在此基礎(chǔ)上，給出了3DOPRAm模型的概念鄰域。最后基于其動作的鄰域關(guān)系，將新模型應(yīng)用于描述基于約束規(guī)則的汽車導(dǎo)航空間場景中。

［1］Cohn A G.Qualiative spatial representation and reasoning techniques［J］.LNCS，1997，1303：1－30.

［2］王生生，王兆丹，劉大有，等.有向線對象細(xì)節(jié)拓?fù)潢P(guān)系模型［J］.吉林大學(xué)學(xué)報：工學(xué)版，2009，39（5）：1292－1296.Wang Sheng－sheng，Wang Zhao－dan，Liu Da－you，et al.Detailed topological relation model of directed line objects［J］.Journal of Jilin University（Engineering and Technology Edition），2009，39（5）：1292－1296.

［3］Moratz R.Qualiative spatial reasoning about oriented points［R］.SFB／TR8Spatial Cognition，2004.

［4］Dylla F，Wallgrün J O.Qualitative spatial reasoning with conceptual neighborhoods for agent control［J］.Journal of Intelligent and Robotic Systems，2007，48（1）：55－78.

［5］Mossakowski T，Moratz R.Qualitative reasoning about relative direction of oriented points［J］.Artificial Intelligence，2012，180－181（2）：34－45.

［6］Chen J，Liu D，Jia H，et al.Cardinal Direction Relations in 3DSpace［M］.Berlin Heidelber：Springer，2007：623－629.

［7］Pacheco J，Escrig M T，Toledo F.Integrating 3D orientation models［C］∥5th Catalonian Conference on Artificial Intelligence，Lecture Notes in Artificial Intelligence，Springer Berlin Heidelberg，2002，2504：88－100.

［8］Freksa C.Temporal reasoning based on semi－intervals［J］.Artificial Intelligence，1992，54（1－2）：199－227.

［9］宋小華，歐陽丹彤.一種動態(tài)定性空間關(guān)系自動規(guī)劃方法［J］.軟件學(xué)報，2012，23（10）：2564－2571.Song Xiao－h(huán)ua，Ouyang Dan－tong.Automated planning method for dealing with dynamic qualitative spatial relations［J］.Journal of Software，2012，23（10）：2564－2571.

［10］Moratz R，Dylla F，F(xiàn)rommberger L.A relative orientation algebra with adjustable granularity［C］∥Proceedings of the Workshop on Agents in Real－time and Dynamic Environments，2005：61－70.