一種復雜區(qū)域?qū)哟味ㄐ钥臻g推理方法

雒海東 宮海彥 耿生玲*

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

0 引 言

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

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

1 復雜區(qū)域的鄰域連接圖模型

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

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

圖1 復雜區(qū)域A

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

定義2[12] 對于一個復雜區(qū)域A，?C∈A,定義層次函數(shù)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中復雜區(qū)域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中復雜區(qū)域A對應的鄰域連接圖如圖2所示。任何一個復雜區(qū)域都可以用一個鄰域連接圖表示。復雜區(qū)域的鄰域連接圖的深度表示為τ(A)=max{lev(ai)∶?ai∈A,0≤i≤n}。

圖2 復雜區(qū)域A對應的鄰域連接圖

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

2.1 復雜區(qū)域的鄰域?qū)哟尉仃?/h3>

為了表示復雜區(qū)域內(nèi)各成分的空間層次關系，在鄰域連接圖的基礎上，建立一個鄰域?qū)哟尉仃?，反映各成分間的層次關系,得到一個n×n的數(shù)值矩陣，n表示復雜區(qū)域內(nèi)成分個數(shù)。

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

圖3 可實現(xiàn)的鄰域?qū)哟尉仃?/p>

圖4 不可實現(xiàn)的鄰域?qū)哟尉仃?/p>

定義復雜區(qū)域內(nèi)兩成分對應的鄰域?qū)哟尉仃嚘?a,b)，ε(a,b)是一個二階矩陣可表示為：

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

定義5已知二階鄰域?qū)哟尉仃嚘臿、εb,定義連接運算°：

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

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

定理1鄰域?qū)哟尉仃囀且粋€主對角線元素為0且對稱元素互為相反數(shù)的矩陣。

證明：由鄰域?qū)哟尉仃嚩x直接可得。

定理2對于復雜區(qū)域內(nèi)成分a與b、b與c、a與c的鄰域?qū)哟尉仃嚘?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 復雜區(qū)域?qū)哟味ㄐ钥臻g推理

基于鄰域?qū)哟尉仃嚨幕A上，進行層次定性空間推理，為了得到所有復雜區(qū)域成分間可實現(xiàn)的層次關系，加入約束條件，從而去掉不可實現(xiàn)的情形。

引理1對于n成分的復雜區(qū)域A, 可遞歸地得到鄰域?qū)哟尉仃嘪, 即X=°i∈[1,n]ε(ai,ai+1)。

證明：由定理2可得。

定理3鄰域?qū)哟尉仃嚱o出的復雜區(qū)域中各成分的層次關系是兩兩互斥且完備的。

證明：所有的復雜區(qū)域鄰域連接圖都可用一個鄰域?qū)哟尉仃噥肀硎?。因為在鄰域?qū)哟尉仃囍?，連接因子反映任意兩個成分之間的連接關系，兩成分間關系必存在“連接”或“無連接”的情況，并且L(a,b)給出的是鄰域連接圖中的兩節(jié)點的層次差，值必屬于集合{-(τ-1),…,-1,0,1,…,τ-1}。所以對于復雜區(qū)域內(nèi)任意成分，有且僅有一個鄰域?qū)哟尉仃噷湓卩徲蜻B接圖中的層次關系。因此兩兩互斥且完備。

約束條件1一個復雜區(qū)域A含有有限的正成分和洞成分，鄰域?qū)哟尉仃嚤硎镜氖怯薪绯煞珠g的空間層次關系，則必須滿足：?a∈A-b0,lev(a)≥1。

約束條件2一個鄰域?qū)哟尉仃嚹軌驅(qū)粋€可實現(xiàn)的復雜區(qū)域n成分連接空間關系，必須滿足：

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

對于復雜區(qū)域中各成分間的層次關系，在兩個約束條件下, 通過算法程序計算可實現(xiàn)的鄰域?qū)哟尉仃嚒Ｋ惴ㄈ缦拢?/p>

算法1GetRelation(n)

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

輸出：滿足約束條件的鄰域?qū)哟尉仃嚰蟁。

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表示復雜區(qū)域內(nèi)成分個數(shù)。例如，復雜區(qū)域中三個成分a、b和c理論上存在53=125種鄰域?qū)哟尉仃?，?25種層次關系。最終運行程序得到可實現(xiàn)的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種可實現(xiàn)的層次關系

2.3 復雜區(qū)域啟發(fā)式層次定性空間推理算法

通過對上述可實現(xiàn)的鄰域?qū)哟尉仃嚨难芯?，可以對n元層次關系進行啟發(fā)式的推理，利用算法自動生成復合表，即已知ε(ai,aj)、ε(aj,ak)，可自動推理出ε(ai,ak)。條件如下：

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

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

算法2Table_Complex(R)

輸入：滿足約束條件的鄰域?qū)哟尉仃嚰蟁；

輸出：空間關系復合表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表示復雜區(qū)域內(nèi)成分個數(shù)。

3 機器人動態(tài)避障應用實例與分析

3.1 應用實例

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

圖6 機器人避障仿真系統(tǒng)

圖7 聲納值變化

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

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

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

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

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

3.2 實驗分析

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

表1 二元層次關系復合表

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

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

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

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

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

圖10給出成分數(shù)量對模型準確性的影響。隨著成分數(shù)量n的增加, 模型的準確率越來越差, 這是由于成分數(shù)量的增加, 會增加算法時間復雜度, 導致可實現(xiàn)鄰域?qū)哟尉仃嚨脑龆? 同時也增加生成復合表的復雜性。

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

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

(1) 鄰域?qū)哟尉仃囋诒磉_3個區(qū)域間關系時可得到可實現(xiàn)的19種空間關系，而8-交集模型在表達3個區(qū)域間關系時得到109種三元拓撲關系。比較而言，鄰域?qū)哟尉仃嚹Ｐ涂蓸O大地降低搜索空間，尤其當n較大時。

(2) 8-交集模型在此機器人避障模型中給出25種避障策略選擇，表1中可看出鄰域?qū)哟尉仃嚹Ｐ徒o出13種避障策略選擇, 精減了策略選擇范疇，減少算法運行時間，提高運行效率。

總之，鄰域?qū)哟尉仃嚹Ｐ瓦m合表示復雜區(qū)域內(nèi)多個區(qū)域間空間關系和推理，而8-交集模型只適合表示3個簡單區(qū)域間空間關系和推理。比較而言, 鄰域?qū)哟尉仃嚹Ｐ捅磉_范圍更廣。

4 結 語

本文在復雜區(qū)域鄰域連接圖表示方法的基礎上，定義了鄰域?qū)哟尉仃?。并根?jù)約束條件，通過算法程序計算得到可實現(xiàn)的鄰域?qū)哟尉仃嚕ㄟ^鄰域?qū)哟尉仃?，利用二元層次關系對多成分間的空間關系進行啟發(fā)式推理。將本文所提出的基于層次關系的復雜區(qū)域定性空間推理方法應用于模擬機器人避障情形，并制定相應避障策略。

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