一種移動對象間方向與距離關(guān)系的結(jié)合推理方法

董軼群，劉建東，徐文星，王淑鴻

(北京石油化工學(xué)院信息工程學(xué)院，北京 102617)

方向、距離、拓撲、尺寸等空間關(guān)系能夠描述現(xiàn)實世界的空間特征。定性空間關(guān)系表示與推理一直是人工智能領(lǐng)域的重要研究內(nèi)容[1]，在智能交通[2-3]、地理信息系統(tǒng)[4]、空間數(shù)據(jù)庫[5]、虛擬空間建模[6]等領(lǐng)域中有著廣泛應(yīng)用。眾多應(yīng)用領(lǐng)域中的問題多是復(fù)雜的，如智能交通中通常需要綜合路網(wǎng)拓撲信息、交通對象的移動方向以及彼此間的距離信息開展相關(guān)應(yīng)用。然而現(xiàn)有定性空間關(guān)系表示與推理研究多是針對對象間單一種類的空間關(guān)系[7-17]，難以對復(fù)雜空間信息進行有效處理。因此多種空間關(guān)系的表示與推理成為近年來的研究熱點[18-25]。空間方向和距離關(guān)系的結(jié)合表示與推理可以有效處理空間位置信息[18，24-25]。然而現(xiàn)有定性方向與距離關(guān)系的結(jié)合研究多是面向靜態(tài)空間對象，且難以對后續(xù)的空間關(guān)系變化做出有效推斷。

1 定性方向與距離關(guān)系

1.1 OPRAm方向關(guān)系模型

OPRAm忽略空間對象的維度與尺寸，將1個移動的空間對象抽象為1個帶方向的點，稱為有向點，記為：

S=(PS,φS)

(1)

其中：PS為平面坐標(biāo)，表示S的位置，即PS=(xS，yS)；φS是從x軸正向逆時針旋轉(zhuǎn)到S所形成的旋轉(zhuǎn)角，表示S的移動方向，該旋轉(zhuǎn)角取值區(qū)間是[0， 2π)上的循環(huán)群。

定義1給定粒度參數(shù)m∈N+，有向點A、B之間的OPRAm關(guān)系記為：

(2)

(3)

式(2)中：i、j、k，即Qm(δ)的取值，均定義在4m循環(huán)群上。每個OPRAm(A，B)取值稱為1個基本OPRAm方向關(guān)系。

1.2 定性距離變化

面向二維平面空間中移動的點對象，將對象間的歐氏距離變化定性地分為“變大”、“變小”、“不變”和“不確定”共4種情況，分別用further、nearer、unchange、uncertain表示，構(gòu)成的集合記為Udis，則有：

Udis={further，nearer，unchange，uncertain}

(4)

下面著重研究OPRA2方向關(guān)系對這4種定性距離變化的約束作用。

2 OPRA2方向關(guān)系對定性距離變化的約束作用

2.1 移動對象間的相對位置關(guān)系Rpos-pair

對于有向點A=(PA，φA)與B=(PB，φB)，用A、B分別表示以A、B為起點的射線；用AB表示以A為起點、B為終點的一條有向線段；用CAB表示以A為圓心，以A與B之間的歐氏距離(|AB|)為半徑的圓。首先根據(jù)A到B的投影情況定義B與CAB之間的位置關(guān)系，如圖2所示。

定義2對于有向點A=(PA，φA)與B=(PB，φB)，PA≠PB，將A向B所在直線投影得投影點Proj(A)，若|AProj(A)|=|AB|，即Proj(A)=B，則稱B與CAB相切，記為t(B，CAB)。

定義3對于有向點A=(PA，φA)與B=(PB，φB)，PA≠PB，將A向B所在直線投影得投影點Proj(A)，若|AProj(A)| <|AB|且Proj(A)∈B，則稱B與CAB相割，記為c(B，CAB)。

定義4對于有向點A=(PA，φA)與B=(PB，φB)，PA≠PB，將A向B所在直線投影得投影點Proj(A)，若|AProj(A)| < |AB| 且Proj(A)?B，則稱B與CAB相離，記為d(B，CAB)。

特殊地，當(dāng)PA=PB時，有|AB|=0，此時圓CAB相當(dāng)于一點，用定義5描述這種特殊情況。

定義5對于有向點A=(PA，φA)與B=(PB，φB)，若PA=PB，則稱B與CAB同置，記為i(B，CAB)。

很顯然，若有i(B，CAB)則有i(A，CBA)。

定義6對于任意2個有向點A、B，由B與CAB之間的位置關(guān)系所構(gòu)成的集合記為Rpos， 有：

Rpos={t，c，d，i}，

(5)

稱Rpos中的每個元素為1個基本Rpos關(guān)系。

由圖2可知，任意2個有向點A、B之間必定滿足1種基本Rpos關(guān)系且僅滿足1種，即關(guān)系集合Rpos是完備互斥的。為更加全面準(zhǔn)確地描述任意2個有向點A、B之間的空間信息，不僅需要B與CAB之間的位置關(guān)系，還需要A與CBA之間的位置關(guān)系。

定義7Rpos-pair為Rpos上的1個有序二元關(guān)系，定義如下：

Rpos-pair={，，，，，，，，，}

(6)

稱Rpos-pair中每個元素為1個基本Rpos-pair關(guān)系。

對于任意2個有向點A、B，二者滿足1種基本Rpos-pair關(guān)系，其語義如表1所示。

表1 基本Rpos-pair關(guān)系語義表

由于Rpos是完備互斥的，因此易知Rpos-pair也是完備互斥的。

2.2 Rpos-pair對定性距離變化的約束

對于任意2個有向點A=(PA，φA)與B=(PB，φB)，在不同基本Rpos關(guān)系下，φB與φAB間滿足命題1～命題3。

命題1對于任意2個有向點A=(PA，φA)與B=(PB，φB)，若有d(B，CAB)，φAB∈[0，2π)，則有φB∈(φAB-π/2，φAB+π/2)。

證明當(dāng)φAB∈[0，π/2)時，若d(B，CAB)，由定義4可知，Proj(A)應(yīng)位于CAB上過B點的切線的下方，因此φB∈(φAB-π/2，φAB+π/2)，如圖3所示。

類似地，若d(B，CAB)，當(dāng)φAB∈[π/2，π)，φAB∈[π，3π/2)，φAB∈[3π/2，2π)時，均有φB∈(φAB-π/2，φAB+π/2)。

證畢。

同理可證命題2與命題3成立。

命題2對于任意2個有向點A=(PA，φA)與B=(PB，φB)，若c(B，CAB)，φAB∈[0， 2π)，則有φB∈(φAB+π/2，φAB+3π/2)。

命題3對于任意2個有向點A=(PA，φA)與B=(PB，φB)，若t(B，CAB)，φAB∈[0，2π)，則有φB=φAB+(2k+1)π/2，k∈Z。

定理1任意2個有向點A=(PA，φA)與B=(PB，φB)，分別沿著各自方向移動LA、LB后到達A′=(PA′，φA)、B′=(PB′，φB)，若PA≠PB且A與CBA以及B與CAB之間不存在相切關(guān)系，當(dāng)LA=LB=0時，|A′B′|2的增量Δz滿足：

Δz≈-2((xB-xA)cosφA+(yB-yA)sinφA)ΔLA+2((xB-xA)cosφB+(yB-yA)sinφB)ΔLB

(7)

其中：φA，φB，φAB∈[0，2π)，PA=(xA，yA)，PB=(xB，yB)，PA′=(xA′，yA′)，PB′=(xB′，yB′)，ΔLA≥0與ΔLB≥0分別為一微小時間間隔內(nèi)LA、LB的增量。

證明由兩點間距離公式可知：

(8)

構(gòu)造二元函數(shù)：

z=f(LA，LB)=|A′B′|2，

(9)

將式(8)帶入式(9)有：

f(LA，LB)=(xB′-xA′)2+(yB′-yA′)2

(10)

由于xB′=LBcosφB+xB，yB′=LBsinφB+yB，xA′=LAcosφA+xA，yA′=LAsinφA+yA，如圖4所示，因此有：

f(LA，LB)=(LBcosφB+xB-LAcosφA-xA)2+(LBsinφB+yB-LAsinφA-yA)2

(11)

整理后得：

f(LA，LB)=(LBcosφB-LAcosφA)2+(LBsinφB-LAsinφA)2+2(LBcosφB-LAcosφA)(xB-xA)+2(LBsinφB-LAsinφA)(yB-yA)+(xB-xA)2+(yB-yA)2

(12)

函數(shù)f(LA，LB)描述了A、B沿著各自方向移動的距離(分別為LA、LB)與A、B移動后二者間距離(即|A′B′|)之間的關(guān)系。對f(LA，LB)求一階偏導(dǎo)數(shù)有：

fLA=2(LA-LBcos (φA-φB)-(xB-xA)cosφA-(yB-yA)sinφA)

(13)

fLB=2(LB-LAcos (φA-φB)+(xB-xA)cosφB+(yB-yA)sinφB)

(14)

因此f(LA，LB)在LA=LB=0處的全增量Δz滿足：

Δz≈dz=-2((xB-xA)cosφA+(yB-yA)sinφA)ΔLA+2((xB-xA)cosφB+(yB-yA)sinφB)ΔLB

(15)

若PA=PB，則xB=xA，yB=yA，此時無論φA、φB，ΔLA與ΔLB如何取值，式(15)中Δz恒為0，即Δz無法表示A、B間的距離增量。

若PA≠PB且xB=xA，則yB≠yA。當(dāng)t(A，CBA)時，必有φA=kπ，k∈Z，因此sinφA=0，使得無論ΔLA如何取值，式(15)中ΔLA系數(shù)恒為0，此時Δz無法描述ΔLA對A、B間距離增量的約束作用。

若PA≠PB且xB≠xA，式(15)可整理為：

Δz≈-2(cosφA+tanφABsinφA)(xB-xA)×ΔLA+2(cosφB+tanφABsinφB)(xB-xA)ΔLB

(16)

當(dāng)t(A，CBA)時，由命題3可知，cos(φAB-φA)=0，因此cosφA=-tanφABsinφA，使得無論ΔLA如何取值，式(16)中ΔLA系數(shù)恒為0，Δz無法描述ΔLA對A、B間距離增量的約束作用。同理，t(B，CAB)時情況類似。 證畢。

接下來，利用定理1研究任意2個有向點在不同基本Rpos-pair關(guān)系下的定性距離變化。

推論1對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離將不變或變小。

證明設(shè)A、B分別沿各自當(dāng)前方向移動了LA、LB到達A′、B′，經(jīng)過某一微小時間間隔后到達A″、B″，期間LA、LB的增量分別為ΔLA≥0、ΔLB≥0。已知AB，當(dāng)LA=LB=0時基于定理1中式(7)對ΔLA、ΔLB分情況討論：

(1)當(dāng)limΔLA=0，limΔLB≠ 0時，已知c(B，CAB)，由命題2可知φB∈(φAB+π/2，φAB+3π/2)，此時對于φAB在[0，2π)內(nèi)的任意取值，均有Δz<0。當(dāng)LA=LB=0時，有|A′B′|=|AB|。由于Δz是函數(shù)f(LA，LB)=|A′B′|2在(0，0)處的全增量，因此Δz<0意味著|A″B″|2-|A′B′|2<0，即有|A″B″|< |AB|，如圖5所示，因此A、B之間距離將變小。

(2)與(1)情況類似，當(dāng)limΔLB=0，limΔLA≠ 0時，由已知c(A，CBA)與命題2可知Δz<0，因此二者之間距離將變小。

(3)當(dāng)limΔLB=limΔLA=0時，可知Δz=0，這意味著在微小時間間隔內(nèi)A、B靜止，因此二者之間距離將不變。

綜上所述，若AB，當(dāng)至少一方距離增量不為0時，二者之間距離將變小；當(dāng)二者距離增量均為0時，二者之間距離將不變。證畢。

類似地，基于命題1可證明推論2成立。

推論2對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離將不變或變大。

推論3對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離變化不確定。

證明設(shè)A、B分別沿著各自當(dāng)前方向移動了LA、LB到達A′、B′，經(jīng)過某一微小時間間隔后到達A″、B″，期間LA、LB的增量分別為ΔLA≥0、ΔLB≥0，對ΔLA、ΔLB分情況討論：

(1)與定理1中式(15)之前的證明部分相同，已知AB，因此有PA≠PB，c(B，CAB)。若limΔLA=0，limΔLB≠ 0，此時與推論1證明中的(1)相同，可知二者之間距離將變小。

(2)已知t(A，CBA)，在證明定理1時已說明，此時cos(φAB-φA)=0，使得式(15)中ΔLA的系數(shù)恒為0，無法用式(15)討論距離變化。當(dāng)PA≠PB，LA=LB=0時，可知|A′B′|=|AB|;當(dāng)limΔLB=0，limΔLA≠ 0時，可知B″與B′近似相等，如圖6所示，因此有|A″B″| ≈ |A″B′|。因為|A″B″| > |A′B′|，即|A″B″| > |AB|，因此二者之間距離將變大。

(3)當(dāng)limΔLA=limΔLB=0時，A、B靜止，二者之間距離將不變。

綜上所述，若AB，無法確定二者之間的距離變化。證畢。

類似地，可證明推論4～推論9成立：

推論4對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離變化不確定。

推論5對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離變化不確定。

推論6對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離將不變或變大。

推論7對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離變化不確定。

推論8對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離將不變或變大。

推論9對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離將不變或變大。

推論10對于任意2個有向點A、B，若AB，在A、B分別沿著各自當(dāng)前方向移動某一微小時間間隔后，二者之間距離將不變或變大。

證明若AB，則PA=PB，若二者的移動方向與速度均相同，則后續(xù)距離保持不變；若二者移動方向或速度不同，則后續(xù)距離將變大。證畢。

2.3 Rpos-pair與OPRA2的對應(yīng)關(guān)系

證明由命題1可知，對任意2個有向點A、B，若d(B，CAB)，則有φB∈(φAB-π/2，φAB+π/2)。令δ=(φBA-φB)，由式(2)可知j=Qm(δ)，由于φBA=φAB+π，因此δ∈(π/2，3π/2)，由式(4)可知j∈{3，4，5}。證畢。

類似地，可證命題5與命題6成立。

命題7對于2個有向點A、B，若i(B，CAB)，則A2∠kB，其中k∈{0，1，2，3，4，5，6，7}。

證明由定義5可知，若有向點A、B對應(yīng)的射線與圓之間存在同置關(guān)系，則有PA=PB，進而由定義1可知A2∠kB，其中k∈{0，1，2，3，4，5，6，7}。證畢。

基于命題4～命題7可歸納出基本Rpos關(guān)系與OPRA2方向關(guān)系之間的對應(yīng)表、基本Rpos-pair關(guān)系與OPRA2方向關(guān)系之間的對應(yīng)關(guān)系，分別如表2和表3所示。

表2 基本Rpos關(guān)系與OPRA2方向關(guān)系對應(yīng)表

Table 2 The Corresponding Table of BasicRposRelations and OPRA4Direction Relations

基本Rpos關(guān)系OPRA2方向關(guān)系d(B,CAB)Ud2={2∠ji|i,j∈N,0≤i≤7,3≤j≤5}c(B,CAB)Uc2={2∠ji|i∈N,0≤i≤7,j∈{0,1,7}}t(B,CAB)Ut2={2∠ji|i∈N,0≤i≤7,j∈{2,6}}(B,CAB)Ui2={2∠k|k∈N,0≤k≤7}

表3 基本Rpos-pair與OPRA2方向關(guān)系對應(yīng)表

2.4 OPRA2對定性距離變化的約束

基于2.2節(jié)與2.3節(jié)中結(jié)論，借助于基本Rpos-pair關(guān)系可以建立起OPRA2方向關(guān)系與定性距離變化的內(nèi)在聯(lián)系，如表4所示。

表4 OPRA2方向關(guān)系與定性距離變化對應(yīng)表

Table 4 The Corresponding Table of OPRA4Direction Relations and Qualitative Distance Changes

OPRA2方向關(guān)系定性距離變化Udd2={2∠ji|i,j∈{3,4,5}}{further, unchange}Udt2={2∠ji|i∈{2,6},j∈{3,4,5}}{further, unchange}Udc2={2∠ji|i∈{0,1,7},j∈{3,4,5}}{uncertain}Utd2={2∠ji|i∈{3,4,5},j∈{2,6}}{further,unchange}Utt2={2∠ji|i,j∈{2,6}}{further, unchange}Utc2={2∠ji|i∈{0,1,7},j∈{2,6}}{uncertain}Ucd2={2∠ji|i∈{3,4,5},j∈{0,1,7}}{uncertain}Uct2={2∠ji|i∈{2,6},j∈{0,1,7}}{uncertain}Ucc2={2∠ji|i,j∈{0,1,7}}{nearer, unchange}Uii2={2∠k|k∈N,0≤k≤7}{further, unchange}

表4中給出了OPRA2方向關(guān)系全集的1個劃分：

(17)

因此，若已知A、B之間的基本OPRA2方向關(guān)系，可參照表4對二者間定性距離變化進行相應(yīng)的判斷。

3 基于OPRA2推斷定性距離變化算法

下面給出算法OPRA2-Distance的偽代碼，對于任意2個移動對象，當(dāng)已知二者當(dāng)前基本OPRA2方向關(guān)系時，用該算法對二者定性距離變化進行推斷。

算法 OPRA2-Distance(R)

輸出：有向點A、B間的定性距離變化D∈2Udis。

1.D←?;

3. if (((i>=2 &&i<=6) && (j>=3 &&j<=5)) || ((i>=2 &&i<=6) && (j==2||j==6)))

4.D←{unchange， further};

5. if ((("Si==0||i==1||i==7) &&(j>=2 &&j<=6)) || ((j==0||j==1||j==7)&&(i>=2 &&i<=6)))

6.D←{uncertain};

7. if ((i==0||i==1||i==7) && (j==0||j==1||j==7))

8.D←{unchange， nearer};

9. else

10.D←{unchange， further}．

推論11對于任意2個有向點A、B，若已知二者間的基本OPRA2方向關(guān)系，算法OPRA2-Distance能夠正確推斷出后續(xù)微小時間間隔內(nèi)二者間基于Udis的定性距離變化。

證明設(shè)有向點A、B滿足基本OPRA2方向關(guān)系R。

4 結(jié)論

面向移動空間對象，針對OPRA2方向關(guān)系與定性距離變化的結(jié)合推理問題，首先通過定義射線與圓之間的Rpos關(guān)系描述目標(biāo)對象相對于參照對象的移動方向；然后通過組合方式定義了Rpos-pair關(guān)系，用以描述2個移動對象間的相對Rpos關(guān)系；分別研究并證明了基本Rpos-pair關(guān)系對定性距離變化的約束作用、基本Rpos-pair關(guān)系與OPRA2方向關(guān)系之間的對應(yīng)關(guān)系，進而借助于基本Rpos-pair關(guān)系建立起OPRA2方向關(guān)系與定性距離變化之間的內(nèi)在聯(lián)系。在此基礎(chǔ)上提出一種基于基本OPRA2方向關(guān)系推理定性距離變化的方法，并證明了方法的正確性。