基于OPRAm 的三維相對方位關系模型

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

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

0 引 言

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

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

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

1 相關理論

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

Moratz［3］在直線段模型的基礎上提出了一種具有可擴展粒度的相對方位關系模型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 的相對方位關系；圖1（c）給出了平面上兩個相同位置方位點的相對方位關系。

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

1.2 鄰域劃分圖

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

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

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

2 三維相對方位關系3DOPRAm

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

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

使用xoy 面的相對方位和z 軸的相對方位組合表示三維空間的相對方位關系。其中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 面上的方位關系，第3個字母表示z軸方位關系。

圖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 ＝（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對應角度的變化構(gòu)成方位點A 所在的歐幾里得空間的完備劃分，其所對應的方位和角度變化如表1所示，方位點B 所在歐幾里得空間的劃分和方位點A 類似。

2.2 三維空間中粗粒度方位點相對方位關系

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

xoy 面上，兩個方位點在不同位置時，總共有8×8＝64種基本關系。當兩個方位點在同一位置時，有8種方位關系；故xoy 平面上共有72種原子方位關系。z 軸有以下5種方位關系ZAB＝｛U1、U2、D1、D2、E｝?？傻贸鋈S空間中總共有360種方位關系。

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

2.3 可擴展粒度3DOPRAm 模型

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

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

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

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

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

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

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

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

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

2.4 3DOPRAm 相對方位關系的逆

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

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

當方位點A 和B 在相同位置時，方位點的逆為：

圖7 相同位置方位點的相對方位關系A2∠40BFig.7 Two o－point in A2∠40Bat the same position

3 3DOPRAm 概念鄰域及定性空間導航問題

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

3.1 3DOPRAm 概念鄰域

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

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

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

3.2 定性空間導航問題

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

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

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

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

定性空間關系導航問題求解：

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

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

4 應用舉例

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

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

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

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

方位點A 和方位點C 的最終相對方位關系為：A2∠00C

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

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

5 結(jié)束語

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

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

［2］王生生，王兆丹，劉大有，等.有向線對象細節(jié)拓撲關系模型［J］.吉林大學學報：工學版，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ī)劃方法［J］.軟件學報，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.