一種復雜區域層次定性空間推理方法

雒海東 宮海彥 耿生玲*

1(青海師范大學教務處 青海 西寧 810008)2(青海師范大學計算機學院 青海 西寧 810008)

0 引 言

在實際工程應用中,由于精確的定量空間信息難以取得，或者需要的空間信息無需定量精確表示，所以許多重要空間信息都是定性表示和推理的。定性空間推理研究已成為人工智能、地理信息系統(GIS)[1]和機器人導航[2]等領域的研究熱點。區域連接演算理論(RCC)[3]是空間區域間拓撲關系模型研究最具有代表性的邏輯方法?？臻g推理模型目前主要通過對簡單區域間的拓撲關系來研究，提出的模型主要有4-交集模型、8-交集模型、9-交集模型、12-交集模型和25-交集模型等[4-9]。在實際應用中，空間區域往往都是復雜區域，僅僅利用簡單區域間的關系已經不足以描述復雜區域內部各組成對象間的空間關系。繼Worboys等[10]提出一種樹模型、Schneider等[11]提出一種成分模型后，Li[12]提出一種圖模型，能有效地表示復雜區域內部各組成部分間的空間關系，尤其在機器人避障問題的研究中，但未涉及推理問題。

本文系統地研究復雜區域內各成分間的空間關系圖模型，給出一種啟發式定性空間推理的方法和應用模型。該方法基于復雜區域內各成分的鄰域連接圖模型，定義一個鄰域層次矩陣，可兩兩互斥并完備地表示復雜區域中n成分間的連接關系。以3成分的復雜區域為例，利用約束條件[13-14]可得到19種空間層次關系，同時給出一種啟發式推理系統。將該方法應用于對機器人與障礙物的層次關系進行模擬，對機器人避障進行建模表示，制定相應的避障方案。

1 復雜區域的鄰域連接圖模型

Li[12]將平面區域定義為實際平面的正規閉集。對于一個有界平面區域A，稱A內部的正閉集為A的正成分，記為A+;稱A外部的正閉集為A的負成分,記為A′;稱A外部唯一的一個無邊界成分的閉包為A的無邊界成分，記為b0；稱A的外部中每一個有邊界的成分為A的洞成分，或簡單稱為A的洞，記為A-。因此A的每一個成分是一個平面區域，也就是平面中的正規閉集。便于實際應用，一個有界區域存在有限多個正成分和洞。

定義1[12] 一個復雜區域A是一個實際平面的有界正規閉子集，它有有限的正成分和洞，且每個正成分和每個洞都是帶洞的簡單區域，如圖1所示。

圖1 復雜區域A

如果兩個成分交集的閉集包含一個簡單的曲線，則稱兩個成分是強連接或者連接的。每個成分至少與其他成分相連接，因為它的邊界包含在其他所有成分邊界的并集中。

定義2[12] 對于一個復雜區域A，?C∈A,定義層次函數lev:c→N,存在：

(1) 無邊界成分b0∈A，則lev(b0)=0；

(2) ?b,c∈A, 存在c連接b，則lev(b)=lev(c)+1。

對于兩個連接的成分b、c，可知lev(b)-lev(c)=±1。以圖1中復雜區域A為例，可知lev(b0)=0、lev(a1)=lev(a2)=lev(a3)=lev(a4)=lev(a5)=1、lev(b1)=lev(b2)=lev(b3)=lev(b4)=2、lev(a6)=lev(a7)=3、lev(b5)=4。

圖1中復雜區域A對應的鄰域連接圖如圖2所示。任何一個復雜區域都可以用一個鄰域連接圖表示。復雜區域的鄰域連接圖的深度表示為τ(A)=max{lev(ai)∶?ai∈A,0≤i≤n}。

圖2 復雜區域A對應的鄰域連接圖

2 基于鄰域連接圖的復雜區域定性空間推理

2.1 復雜區域的鄰域層次矩陣

為了表示復雜區域內各成分的空間層次關系，在鄰域連接圖的基礎上，建立一個鄰域層次矩陣，反映各成分間的層次關系,得到一個n×n的數值矩陣，n表示復雜區域內成分個數。

對于任意的復雜區域就對應了一個鄰域層次矩陣。當i=j,xij為ai自身的連接關系，值為0；當i≠j,xij為連接的成分ai和aj之間的層次關系，xji為連接的成分bj和bi之間的層次關系，因此xij和xji互為相反數。這樣可得到(2n-1)n(n-1)/2種鄰域層次矩陣,每種矩陣對應一種層次關系，但并不是所有的鄰域層次矩陣都可實現，如圖3和圖4所示。

圖3 可實現的鄰域層次矩陣

圖4 不可實現的鄰域層次矩陣

定義復雜區域內兩成分對應的鄰域層次矩陣ε(a,b)，ε(a,b)是一個二階矩陣可表示為：

ε(a,b)=λL(a,b)

定義5已知二階鄰域層次矩陣εa、εb,定義連接運算°：

εa°εb=(λa°λb)(La+Lb)

式中：λa°λb∈{0,1}。

定理1鄰域層次矩陣是一個主對角線元素為0且對稱元素互為相反數的矩陣。

證明：由鄰域層次矩陣定義直接可得。

定理2對于復雜區域內成分a與b、b與c、a與c的鄰域層次矩陣ε(a,b)、ε(b,c)、ε(a,c)，則如下關系成立：

ε(a,c)=ε(a,b)°ε(b,c)。

證明：由于ε(a,b)=λabL(a,b),ε(b,c)=λbcL(b,c), 則

ε(a,b)°ε(b,c)=λab°λbc(L(a,b)+L(b,c))=

得證。

2.2 復雜區域層次定性空間推理

基于鄰域層次矩陣的基礎上，進行層次定性空間推理，為了得到所有復雜區域成分間可實現的層次關系，加入約束條件，從而去掉不可實現的情形。

引理1對于n成分的復雜區域A, 可遞歸地得到鄰域層次矩陣X, 即X=°i∈[1,n]ε(ai,ai+1)。

證明：由定理2可得。

定理3鄰域層次矩陣給出的復雜區域中各成分的層次關系是兩兩互斥且完備的。

證明：所有的復雜區域鄰域連接圖都可用一個鄰域層次矩陣來表示。因為在鄰域層次矩陣中，連接因子反映任意兩個成分之間的連接關系，兩成分間關系必存在“連接”或“無連接”的情況，并且L(a,b)給出的是鄰域連接圖中的兩節點的層次差，值必屬于集合{-(τ-1),…,-1,0,1,…,τ-1}。所以對于復雜區域內任意成分，有且僅有一個鄰域層次矩陣對應其在鄰域連接圖中的層次關系。因此兩兩互斥且完備。

約束條件1一個復雜區域A含有有限的正成分和洞成分，鄰域層次矩陣表示的是有界成分間的空間層次關系，則必須滿足：?a∈A-b0,lev(a)≥1。

約束條件2一個鄰域層次矩陣能夠對應一個可實現的復雜區域n成分連接空間關系，必須滿足：

ε(A,C)=ε(A,B)°ε(B,C)

對于復雜區域中各成分間的層次關系，在兩個約束條件下, 通過算法程序計算可實現的鄰域層次矩陣。算法如下：

算法1GetRelation(n)

輸入：復雜區域成分個數n，lev= {lev(a1),lev(a2),…,lev(an)};

輸出：滿足約束條件的鄰域層次矩陣集合R。

R=null;

fori=1;i<=n;i++ do

forj=1;j<=n;j++ do

ifi=jthen

xij=0;

ifi≠jthen

ifai連接ajthen

λ=1;

else

λ=0;

X[i,j]=λ(lev(ai)-lev(aj));

for eachε(ai,aj)inXdo

{ifε(ai,aj)滿足約束條件1And約束條件2

then

R=R∪X; }

} }}

returnR;

GetRelation(n)算法時間復雜度為O(n3),n表示復雜區域內成分個數。例如，復雜區域中三個成分a、b和c理論上存在53=125種鄰域層次矩陣，即125種層次關系。最終運行程序得到可實現的19種連接關系，如圖5所示。

000000000é?êêêù?úúú[1]001001-1-10é?êêêù?úúú[2]00000-1010é?êêêù?úúú[3]00-1000100é?êêêù?úúú[4]00-100-1110é?êêêù?úúú[5]010-100000é?êêêù?úúú[6]001000-100é?êêêù?úúú[7]011-100-100é?êêêù?úúú[8]012-101-2-10é?êêêù?úúú[9]010-10-1010é?êêêù?úúú[10]01-1-10-2120é?êêêù?úúú[11]0-1-1100100é?êêêù?úúú[12]0000010-10é?êêêù?úúú[13]0-10100000é?êêêù?úúú[14]0-101010-10é?êêêù?úúú[15]0-1-210-1210é?êêêù?úúú[16]0-10102-1-20é?êêêù?úúú[17]021-20-1-110é?êêêù?úúú[18]0-2-12011-10é?êêêù?úúú[19]

圖5 19種可實現的層次關系

2.3 復雜區域啟發式層次定性空間推理算法

通過對上述可實現的鄰域層次矩陣的研究，可以對n元層次關系進行啟發式的推理，利用算法自動生成復合表，即已知ε(ai,aj)、ε(aj,ak)，可自動推理出ε(ai,ak)。條件如下：

ε(ai,ak)=ε(ai,aj)°ε(aj,ak)

記所有可實現的鄰域層次矩陣集合R={Xt;t=1,2,…,(2n-1)n(n-1)/2}，遍歷R中(ε(ai,aj),ε(aj,ak)的所有可能，對每種情況都按照條件得到ε(ai,ak)，除去重復項，則可生成層次關系復合表。算法的偽代碼描述如下：

算法2Table_Complex(R)

輸入：滿足約束條件的鄰域層次矩陣集合R；

輸出：空間關系復合表tab_com。

tab_com= null;

for eachXinRdo

foreachε(ai,aj),ε(aj,ak)inXdo

{ε(ai,ak) ←ε(ai,aj)°ε(aj,ak);

tab_com(i, 1) =ε(ai,aj) ∪ε(aj,ak) ∪

ε(ai,ak); }}

returntab_com;

Table_Complex(R)算法時間復雜度為O(n3),n表示復雜區域內成分個數。

3 機器人動態避障應用實例與分析

3.1 應用實例

文獻[15]利用簡單區域的8-交集模型對機器人和兩障礙物的避障進行推理模擬。本文所建立的基于鄰域連接圖的復雜區域定性空間推理方法，可用于對復雜區域中機器人與兩個指定障礙物的層次關系進行模擬。在層次關系推理方法的建立中，假定區域對象C為機器人，區域對象A、B為障礙物。為此本文建立的實驗環境：X2BOT輪式機器人開發平臺, 配置為四核2.7 GHz主控制器, Windows 7操作系統。圖6是機器人避障仿真系統,在此基礎上將層次定性空間推理方法運用于機器人避障預測模擬系統中。機器人避障利用聲納避障,圖6中機器人有5個聲納傳感器分別探測不同方向上機器人與障礙物的距離，1號傳感器位于機身的左側，2號傳感器位于機身的右側，3～5號傳感器從左到右依次分布于機身的前方。圖7表示5個聲納傳感器在機器人運行時的數值變化。隨著時間的增加，機器人和障礙物的距離逐漸縮短，5個傳感器的數值隨之減少。

圖6 機器人避障仿真系統

圖7 聲納值變化

如果能對機器人C與障礙物A、障礙物B間的層次關系進行預測和表示，機器人就能夠躲避障礙物運動，減少碰撞過程中的損失。根據上述層次關系推理方法可知，由障礙物A與障礙物B在鄰域連接圖中的層次關系和機器人C與任一障礙物在鄰域連接圖中的層次關系，可以推理得到機器人C與另一障礙物在鄰域連接圖中的層次關系，從而改進機器人避障方案。將機器人C與障礙物A、障礙物B的碰撞情況分為如下4種：

(1) 機器人C與障礙物A發生碰撞，但與障礙物B不發生碰撞；

(2) 機器人C與障礙物B發生碰撞，但與障礙物A不發生碰撞；

(3) 機器人C與障礙物A、B均發生碰撞；

(4) 機器人C與障礙物A、B均不發生碰撞。

3.2 實驗分析

通過算法1模擬復雜區域中機器人與障礙物間的碰撞情形，與復雜區域中三個成分間的19種層次關系相互對應，再執行算法2，經過推理得出二元層次關系復合表，如表1所示。

表1 二元層次關系復合表

圖8給出其中4種情況(圖下方的序號分別對應圖5中序號)。序號[3]表示機器人C與障礙物B發生碰撞，與障礙物A不發生碰撞;序號[6]表示機器人C與障礙物A、障礙物B均不發生碰撞;序號[7]表示機器人C與障礙物A發生碰撞，與障礙物B不發生碰撞;序號[16]表示機器人C與障礙物A、B均發生碰撞。

圖8 推理三成分間的空間關系

表1中對應的序號[1]、[6]、[14]分別表示這種情形，共有3種情況。本文認為碰撞情形是完全隨機的，故其概率為3/19=15.79%，以此類推，機器人C與障礙物A發生碰撞，與障礙物B不發生碰撞的概率為3/19=15.79%；機器人C與障礙物B發生碰撞，與障礙物A不發生碰撞的概率為3/19=15.79%；機器人C與障礙物A、B均發生碰撞的概率為10/19=52.63%。

從模型的運行時間和準確性分析得出，復雜區域內成分的數量是影響算法的主要因素。本文的層次定性空間推理方法采用隨機設置障礙物的方式, 通過對機器人避障預測,實現更高效地避障策略, 將該模型與傳統避障策略相比較,圖9給出成分數量對兩種模型運行時間的影響。當成分數量從10到80發生變化時, 可以看出, 層次空間推理模型優于傳統避障策略。

圖9 不同成分數量下算法運行時間的比較

圖10給出成分數量對模型準確性的影響。隨著成分數量n的增加, 模型的準確率越來越差, 這是由于成分數量的增加, 會增加算法時間復雜度, 導致可實現鄰域層次矩陣的增多, 同時也增加生成復合表的復雜性。

圖10 成分數量n對模型準確性的影響

將本文提出的層次定性空間推理模型與8-交集模型[15]的表達能力相比較, 可得出：

(1) 鄰域層次矩陣在表達3個區域間關系時可得到可實現的19種空間關系，而8-交集模型在表達3個區域間關系時得到109種三元拓撲關系。比較而言，鄰域層次矩陣模型可極大地降低搜索空間，尤其當n較大時。

(2) 8-交集模型在此機器人避障模型中給出25種避障策略選擇，表1中可看出鄰域層次矩陣模型給出13種避障策略選擇, 精減了策略選擇范疇，減少算法運行時間，提高運行效率。

總之，鄰域層次矩陣模型適合表示復雜區域內多個區域間空間關系和推理，而8-交集模型只適合表示3個簡單區域間空間關系和推理。比較而言, 鄰域層次矩陣模型表達范圍更廣。

4 結 語

本文在復雜區域鄰域連接圖表示方法的基礎上，定義了鄰域層次矩陣。并根據約束條件，通過算法程序計算得到可實現的鄰域層次矩陣，通過鄰域層次矩陣，利用二元層次關系對多成分間的空間關系進行啟發式推理。將本文所提出的基于層次關系的復雜區域定性空間推理方法應用于模擬機器人避障情形，并制定相應避障策略。

復雜區域內空間關系十分復雜，層次關系表示和推理是一種近似方法，還需考慮很多細節。因此，研究如何對復雜區域內空間關系定性推理和精準的定量方法結合，提高控制或決策的準確性和效率是接下來的研究重點。