華承昊， 竇麗華， 方浩， 付浩

(1.北京理工大學(xué) 自動化學(xué)院，北京 100081；2.國防科技大學(xué) 機電工程與自動化學(xué)院，湖南，長沙 410073)

?

SLAM中融合形狀上下文和隨機步進的圖匹配數(shù)據(jù)關(guān)聯(lián)算法

華承昊1， 竇麗華1， 方浩1， 付浩2

(1.北京理工大學(xué) 自動化學(xué)院，北京 100081；2.國防科技大學(xué) 機電工程與自動化學(xué)院，湖南，長沙 410073)

提出了一種在非確定環(huán)境下求解SLAM數(shù)據(jù)關(guān)聯(lián)問題的圖匹配算法. 算法建立了SLAM中數(shù)據(jù)關(guān)聯(lián)的圖論模型，對圖模型節(jié)點提取了不依賴位置信息的形狀上下文特征(shape context，SC)，最后通過二次加權(quán)隨機步進算法(reweighted random walks，RRW)得到圖匹配問題的優(yōu)化解. RRW&SC圖匹配算法充分利用了路標間的拓撲結(jié)構(gòu)關(guān)系以及路標間的形狀結(jié)構(gòu)，極大地擴展了數(shù)據(jù)關(guān)聯(lián)時所依據(jù)的幾何信息量. 仿真實驗結(jié)果表明，與傳統(tǒng)算法相比，該算法能有效處理SLAM中噪聲干擾增加、機器人迷失、路標被動態(tài)遮擋等不確定程度高、歧義性大環(huán)境中的數(shù)據(jù)關(guān)聯(lián).

數(shù)據(jù)關(guān)聯(lián)；圖匹配；同步定位與建圖

SLAM是移動機器人在未知環(huán)境中以起始出發(fā)點為原點，通過自身攜帶傳感器測量的環(huán)境特征數(shù)據(jù)，在移動中不斷自我定位同時逐步繪制出其經(jīng)過環(huán)境地圖的過程[1-2]. 數(shù)據(jù)關(guān)聯(lián)則是機器人SLAM中保障地圖繪制精準與魯棒性的關(guān)鍵環(huán)節(jié)[3]. 經(jīng)過多年的探索，依據(jù)機器人所攜帶傳感器和所創(chuàng)建地圖模型的不同，研究人員提出了眾多的數(shù)據(jù)關(guān)聯(lián)算法. 現(xiàn)有的SLAM算法依據(jù)地圖表示類型可分為由傳感器原始數(shù)據(jù)生成度量地圖(metric map)或者柵格地圖(grid map)的SLAM算法，和對傳感器原始數(shù)據(jù)進行特征路標提取后的特征地圖(feature map)的SLAM算法. 其中，特征地圖匹配的數(shù)據(jù)關(guān)聯(lián)算法可以分為兩類.

第一類算法是以觀測數(shù)據(jù)與已繪地圖路標間的馬氏距離(Mahalanobis distance)規(guī)則來求解數(shù)據(jù)關(guān)聯(lián)問題. 典型方法包括獨立相容的最近鄰匹配(individual compatibility nearest neighbor， ICNN)[3]、 聯(lián)合相容的分枝限界匹配(joint compatibility branch and bound， JCBB)[3]、多假設(shè)跟蹤的數(shù)據(jù)關(guān)聯(lián)算法(multi-hypothesis tracker， MHT)[4]及各自的衍生算法等. 這類算法計算復(fù)雜度低、有助于SLAM增強實時性，但也有因馬氏距離含有的信息量低而難以解決錯誤數(shù)據(jù)關(guān)聯(lián)的缺陷. 當(dāng)SLAM進行閉環(huán)檢測時，需采用較大的馬氏距離閾值，因此易產(chǎn)生多重數(shù)據(jù)關(guān)聯(lián)；而在環(huán)境特征相對密集時，需采用較小的馬氏距離閾值從而易導(dǎo)致錯誤的數(shù)據(jù)關(guān)聯(lián). 郭帥等[5]指出：“多重數(shù)據(jù)關(guān)聯(lián)問題和錯誤數(shù)據(jù)關(guān)聯(lián)問題對馬氏距離閾值提出了相互矛盾的要求，尋找一個合適的馬氏距離閾值是一個復(fù)雜或者難以完成的任務(wù). ”即使研究者們提出諸多可保留多種數(shù)據(jù)關(guān)聯(lián)可能性的多假設(shè)算法[4，6-7]，也始終無法擺脫馬氏距離規(guī)則幾何信息含量少的根本缺陷，無法有效地解決多重數(shù)據(jù)關(guān)聯(lián)和錯誤數(shù)據(jù)關(guān)聯(lián)問題.

第二類算法則希望利用觀測數(shù)據(jù)中蘊含的拓撲結(jié)構(gòu)等更多的幾何信息來求解數(shù)據(jù)關(guān)聯(lián)問題. 如Bailey等[8]以環(huán)境特征的位置、特征間連線的距離、連線間的夾角以及特征到連線的垂直距離等拓撲關(guān)系，構(gòu)成特征圖. 通過在觀測數(shù)據(jù)與已繪地圖間尋找最大公共子圖來獲得數(shù)據(jù)關(guān)聯(lián). 該方法對錯誤關(guān)聯(lián)有很強的抗干擾能力，但是未能很好地解決搜索最大公共子圖這個不易求解的NPC(non-deterministic polynomial-complete)問題. Gamallo等[9]將匈牙利算法(Hungarian algorithm， HA)引入SLAM中的數(shù)據(jù)關(guān)聯(lián)求解. 該算法是求解分配問題最常見的優(yōu)化算法，其核心是以Hall定理為依據(jù)尋找增廣路徑求解二分圖的最大匹配[9-10]. 文獻[5]中則對環(huán)境特征采用輪廓角度、輪廓面積兩個參數(shù)加以描述，提出了輪廓匹配規(guī)則的數(shù)據(jù)關(guān)聯(lián)算法. 這類數(shù)據(jù)關(guān)聯(lián)算法為避免錯誤關(guān)聯(lián)、獲得更魯棒的關(guān)聯(lián)結(jié)果提供了更廣闊的思路，但對觀測數(shù)據(jù)蘊含幾何信息的運用仍不夠充分，因而在機器人迷失等情形時難以有良好的表現(xiàn).

在現(xiàn)實環(huán)境中，機器人常常面對各種非確定、突發(fā)狀況的挑戰(zhàn). 比如，機器人傳感器偶發(fā)故障或者因環(huán)境擾動影響帶來的運動噪聲或者觀測噪聲的增大，機器人被碰撞或者被人為突然轉(zhuǎn)移帶來的位姿迷失，機器人所在環(huán)境路標被其他動態(tài)移動物體遮擋等等. 面對環(huán)境中這些非確定狀況時，僅依賴待匹配數(shù)據(jù)間的距離信息的數(shù)據(jù)關(guān)聯(lián)算法就難以有良好的表現(xiàn). 此時，待匹配數(shù)據(jù)中蘊含的拓撲結(jié)構(gòu)信息就能為準確數(shù)據(jù)關(guān)聯(lián)提供有效支持. 在應(yīng)對這些非確定環(huán)境狀況時，為了能更充分有效地運用觀測數(shù)據(jù)中蘊含的幾何拓撲結(jié)構(gòu)信息，獲得準確、魯棒的數(shù)據(jù)關(guān)聯(lián)結(jié)果，本文提出了一種結(jié)合二次加權(quán)隨機步進[11]和形狀上下文[12]的圖匹配數(shù)據(jù)關(guān)聯(lián)算法(RRW&SC). 該算法既使用了多個路標的形狀結(jié)構(gòu)和路標間構(gòu)成的拓撲結(jié)構(gòu)信息，也利用了傳統(tǒng)數(shù)據(jù)關(guān)聯(lián)算法中機器人觀測數(shù)據(jù)與已繪地圖路標位置信息提供的馬氏距離差，極大地擴展了數(shù)據(jù)關(guān)聯(lián)時所依據(jù)的幾何信息量. 且RRW&SC算法可以獨立于數(shù)據(jù)關(guān)聯(lián)匹配的歷史紀錄.

為驗證提出算法的有效性，設(shè)定了非確定環(huán)境里常見的3種復(fù)雜狀況：運動與觀測噪聲增大、機器人迷失以及路標被動態(tài)遮擋. 并通過仿真實驗將RRW&SC算法與馬氏距離最近鄰算法、匈牙利分配算法等兩類經(jīng)典數(shù)據(jù)關(guān)聯(lián)算法進行了對比. 仿真結(jié)果表明，在不確定程度高、歧義性大的復(fù)雜非確定環(huán)境中，RRW&SC算法能更有效地求解SLAM的數(shù)據(jù)關(guān)聯(lián)問題.

1 問題描述與建模

1.1 SLAM中的數(shù)據(jù)關(guān)聯(lián)

數(shù)據(jù)關(guān)聯(lián)是研究機器人SLAM、目標跟蹤等諸多自主智能化問題中的重要環(huán)節(jié). 以SLAM研究領(lǐng)域中創(chuàng)建的平面地圖為例，在某一時刻t，移動機器人R獲得了其觀測范圍內(nèi)m個環(huán)境特征的觀測數(shù)據(jù)集. 觀測數(shù)據(jù)集中的每一個特征值zi，與來源于同一環(huán)境的歷史觀測數(shù)據(jù)集(從初始時刻到t-1時刻)所繪制環(huán)境地圖的各個特征值lj之間，都可以按照某一個確定的映射關(guān)系f確定地得到一定的對應(yīng)關(guān)系，表示為f:zi→lj. 在來源于同一環(huán)境特征值之間對應(yīng)關(guān)系的映射對中，甄選出最佳對應(yīng)匹配關(guān)系的過程，就是數(shù)據(jù)關(guān)聯(lián)[13].

(1)

(2)

(3)

若Zt中的第i個特征與地圖中的第j個特征對應(yīng)實際環(huán)境中的同一個特征，那么它們間的馬氏距離應(yīng)服從自由度為m的χ2分布[5]. 以某一置信度(如95%)的χ2分布數(shù)值為閾值，即可作為SLAM中判斷數(shù)據(jù)關(guān)聯(lián)的依據(jù). 通常，機器人在某時刻觀測獲得的環(huán)境特征有多個，多個特征間除了各自的位置信息外還有相互間的夾角、距離等拓撲結(jié)構(gòu)信息. 若能將這些幾何關(guān)系都用于求解數(shù)據(jù)關(guān)聯(lián)，可有助于解決SLAM中多重數(shù)據(jù)關(guān)聯(lián)和錯誤數(shù)據(jù)關(guān)聯(lián)問題，增強SLAM的魯棒性.

1.2 SLAM中數(shù)據(jù)關(guān)聯(lián)的圖論模型

圖論里通常用一個4元組來描述一幅含有n個節(jié)點和m條邊圖的拓撲關(guān)系[15]，

式中：P為節(jié)點的集合；Q為節(jié)點間連通邊的集合；G，H∈{0，1}n×m為拓撲關(guān)聯(lián)矩陣，gic=hic=1表示第c條邊是從i節(jié)點起始到j(luò)節(jié)點結(jié)束的.

圖論模型中，機器人在其觀測范圍內(nèi)對環(huán)境特征(如路標)的當(dāng)前觀測數(shù)據(jù)Z，與來源于同一環(huán)境中歷史觀測數(shù)據(jù)形成的已繪地圖L，是同一環(huán)境中的兩個節(jié)點集；而節(jié)點間的連線形成邊集. 假定，已繪環(huán)境地圖包含n個環(huán)境特征，其圖模型Gtp1={P1，Q1，G1，H1}；當(dāng)前觀測信息含有m個觀測特征值，其圖模型Gtp2={P2，Q2，G2，H2}.

Gtp1和Gtp2間各節(jié)點相似度的仿射矩陣為

Gtp1和Gtp2間各邊相似度的仿射矩陣為

假設(shè)n≥m，并按如下規(guī)則合并成Gtp1和Gtp2間拓撲相似度的仿射矩陣[10]為

(4)

式中:i1，i2∈(1，2，…，n);j1，j2∈(1，2，…，m);i1j1為K的行序號，i2j2為K的列序號.

給定Gtp1，Gtp2和K，SLAM中的數(shù)據(jù)關(guān)聯(lián)就轉(zhuǎn)化為求取Gtp1和Gtp2節(jié)點間的最佳匹配矩陣X*，使下面這個帶約束的目標函數(shù)取極大值，

(5)

式(5)可視為求解SLAM中數(shù)據(jù)關(guān)聯(lián)問題的一般化表示. 當(dāng)Kp為馬氏距離且Kq=0時，就可以采用基于馬氏距離規(guī)則的算法求解. 若放寬式(5)的約束條件，則可以運用多假設(shè)數(shù)據(jù)關(guān)聯(lián)算法求解. 若僅考慮只含有一階拓撲信息節(jié)點位置的Kp，在機器人定位誤差增大或者迷失等歧義性大的情形下，無法保證正確的數(shù)據(jù)關(guān)聯(lián). 因此需要引入邊相似度仿射矩陣Kq. 引入Kq后，總相似度仿射矩陣K含有的拓撲信息就從一階擴展為高階. 這樣則使得求解式(5)成為一個NPC問題. 因此需尋求一種有效魯棒的求解方法.

2 RRW&SC圖匹配數(shù)據(jù)關(guān)聯(lián)算法

在建立SLAM數(shù)據(jù)關(guān)聯(lián)圖論模型的基礎(chǔ)上，本文提出二次加權(quán)隨機步進結(jié)合形狀上下文的優(yōu)化算法RRW&SC來求解式(5).

映射f:Gtp1Gtp2為Gtp1各節(jié)點進行了某種剛性的變動. 將Gtp1中某個節(jié)點與Gtp1和Gtp2各個節(jié)點所有可能的匹配(狀態(tài))視作是一個隨機步進(random walks)運動.Gtp1和Gtp2間相似度仿射矩陣K中的非零元素描述了Gtp1和Gtp2節(jié)點與邊之間的相似性. 如果對K按行歸一化，這樣就可得到一個隨機步進矩陣. 一個隨機步進矩陣對應(yīng)的是一個遍歷的Markov鏈，任意兩個狀態(tài)間按一定的轉(zhuǎn)移概率隨機步進.

求解式(5)就是找出隨機步進中最符合仿射矩陣K的變動. 為此，本文引入了二次加權(quán)的隨機步進(RRW)算法[11]. 該算法在文獻[11]中被應(yīng)用于對圖形匹配問題的求解，本文將該算法進行改進，運用到了SLAM數(shù)據(jù)關(guān)聯(lián)問題的求解中. 具體解法如下.

算法首先構(gòu)造了可保持仿射關(guān)系K的隨機步進狀態(tài)轉(zhuǎn)移矩陣

令

dmax=maxidi，

用dmax對仿射矩陣K行歸一化，為

歸一化的同時，為了表征dmax-di的差，并保證狀態(tài)轉(zhuǎn)移矩陣的收斂性，設(shè)計了一個帶吸收態(tài)xabs的Markov鏈. 經(jīng)過仿射關(guān)系保持的加權(quán)后，隨機步進的狀態(tài)轉(zhuǎn)移矩陣P滿足

(6)

式中x(n)為狀態(tài)x的第n步狀態(tài)轉(zhuǎn)移.

式(6)是一個準穩(wěn)態(tài)分布，可以證明其結(jié)果必然收斂[11]. 式(5)中除了仿射關(guān)系矩陣外，還需要滿足匹配最多存在單一對應(yīng)約束條件. 因此，通過再次加權(quán)的方式，將約束條件

加入到隨機步進中，即在式(6)中添加了符合約束的狀態(tài)匹配再加權(quán)跳轉(zhuǎn)向量r. 構(gòu)建r分兩步：

① 令rT=exp(βx/maxx)，這可以使得概率值大的x更大，概率值小的x更小，式中β為膨脹系數(shù)；

② 對rT的行和列交替歸一化，不斷迭代，直至rT收斂. 可以證明rT必然收斂到滿足式(5)約束條件的方陣[11].

在式(6)以及再加權(quán)跳轉(zhuǎn)向量r的基礎(chǔ)上，進一步假設(shè)，狀態(tài)x以α的概率隨機狀態(tài)轉(zhuǎn)移，以1-α的概率隨機跳轉(zhuǎn). 就得到二次加權(quán)隨機步進的狀態(tài)轉(zhuǎn)移公式為

(7)

迭代求解式(7)直至收斂，將得到的連續(xù)解離散化，即式(5)的優(yōu)化解X*.

在現(xiàn)實環(huán)境中，特征的位置存在被遮擋、因機器人迷失或運動誤差過大而被誤測量等多種非確定情形. 此時，僅用位置信息描述環(huán)境特征，已難以保障SLAM過程中數(shù)據(jù)關(guān)聯(lián)的準確性. 為了使環(huán)境特征屬性的表示更具有魯棒性，本文使用形狀上下文算法[12]描述圖節(jié)點的屬性. 該算法使用特征點鄰近區(qū)域所有節(jié)點與其相對位置信息來衡量該特征點的屬性. 以Gtp1中某個節(jié)點pi為例，將pi為原點并覆蓋其他所有節(jié)點的對數(shù)極坐標空間，按30°劃分為12等分，再按對數(shù)距離lgρ將空間的半徑劃分為5部分，這樣得到60個分塊區(qū)域. 采用對數(shù)極坐標描述，可使與距離近的節(jié)點在描述屬性上有更大的影響權(quán)重. 對整個空間記錄除pi外的其余節(jié)點在這60個部分的分布數(shù)目的直方圖hi，作為pi的屬性描述

(8)

那么，來自于Gtp1的節(jié)點pi與來自于Gtp2的節(jié)點pj的相似度就可用下式描述

(9)

用形狀上下文算法描述Gtp1和Gtp2間各節(jié)點相似度的仿射矩陣Kp，是通過提取節(jié)點集的形狀模式來獲得相似度匹配. 形狀模式本身與圖節(jié)點的位置無關(guān)，而且對于旋轉(zhuǎn)等剛性變換具有固有的不變性. 同時，形狀上下文算法所提取的形狀模式，對于部分遮擋、少量噪聲點等引起的圖幾何形變也有很好魯棒性. 這些優(yōu)點，都有助于非確定環(huán)境下的數(shù)據(jù)關(guān)聯(lián)問題求解.

RRW&SC算法的主要流程如圖1所示.

3 仿真實驗與分析

在開源SLAM仿真程序的基礎(chǔ)上[16]，創(chuàng)建了一個非確定環(huán)境下機器人SLAM數(shù)據(jù)關(guān)聯(lián)的仿真平臺. 在一個200 m×200 m的仿真空間內(nèi)，放置了若干由星號表示的路標，機器人按預(yù)定軌跡勻速移動，如圖2所示.

為了更好地檢驗、對比各個數(shù)據(jù)關(guān)聯(lián)算法，設(shè)定機器人能觀測到整個仿真環(huán)境. 機器人的運動噪聲σv=0.3 m/s，σo=3°；測量噪聲σρ=0.1 m，σα=3°.

實驗分別模擬了以下3種情形.

① 模擬噪聲干擾，逐倍增加機器人的運動誤差和觀測誤差，來檢驗算法對大噪聲的魯棒性；

② 設(shè)置機器人的迷失情景，逐倍增加其距離的迷失并伴有朝向角度的隨機迷失，測試算法能否實現(xiàn)迷失后恢復(fù)正確的數(shù)據(jù)關(guān)聯(lián)；

③ 模擬機器人觀測受到動態(tài)運動物體的遮擋，隨著被遮擋路標數(shù)量的增加，測試算法在動態(tài)環(huán)境里的數(shù)據(jù)關(guān)聯(lián)效果.

在仿真中，將本文的RRW&SC圖匹配算法與馬氏距離規(guī)則算法、匈牙利分配算法進行了對比. 實驗結(jié)果和分析如下.

3.1 噪聲干擾增加實驗

當(dāng)噪聲從1倍逐倍增加至10倍，對每一種情形都重復(fù)進行了20次蒙特卡洛實驗，結(jié)果見圖3. 各個算法關(guān)聯(lián)平均準確率的統(tǒng)計結(jié)果顯示，本文提出的RRW&SC圖匹配算法和匈牙利算法對大噪聲干擾有很強的魯棒性. RRW&SC算法能夠始終保持完全正確的數(shù)據(jù)關(guān)聯(lián)結(jié)果，匈牙利算法則有個別時刻出現(xiàn)少量的錯誤關(guān)聯(lián). 而基于馬氏距離規(guī)則的算法只有在常規(guī)較小噪聲時能得到完全正確的數(shù)據(jù)關(guān)聯(lián)結(jié)果，隨著噪聲干擾的增加，其數(shù)據(jù)關(guān)聯(lián)錯誤率呈增大趨勢.

3.2 機器人迷失場景實驗

在迷失情形下，設(shè)定機器人的初始迷失距離為4.6 m，并伴有朝向角的隨機迷失. 逐倍增加機器人迷失的距離，最高至10倍即46 m. 對每一種情形都重復(fù)進行了20次蒙特卡洛實驗，結(jié)果見圖4. 各算法關(guān)聯(lián)準確率的統(tǒng)計結(jié)果顯示，RRW&SC圖匹配算法在機器人迷失后，可以立即恢復(fù)正確的數(shù)據(jù)關(guān)聯(lián). 匈牙利算法的正確率出現(xiàn)大幅波動且很少能獲得100%的準確關(guān)聯(lián)，其在各次實驗中的平均正確率都少于40%. 基于馬氏距離規(guī)則的算法一旦遇到機器人迷失的情景，就基本無法有效地進行數(shù)據(jù)關(guān)聯(lián)了. 這是由于該類算法僅依賴于位置信息所致，一旦機器人的定位出錯，其觀測的路標位置也隨之出錯. RRW&SC算法則能夠在機器人定位出錯的情形下，依靠觀測數(shù)據(jù)中保留的拓撲圖結(jié)構(gòu)信息獲得正確的數(shù)據(jù)關(guān)聯(lián).

3.3 動態(tài)遮擋情形實驗

考察機器人觀測受到動態(tài)運動物體的遮擋，且被遮擋路標數(shù)量不斷增加的情形. 被遮擋路標數(shù)從2個逐步倍增到20個，對每一種情形都重復(fù)進行了20次蒙特卡洛實驗，結(jié)果如圖5所示.

各個算法關(guān)聯(lián)準確率的統(tǒng)計結(jié)果顯示，當(dāng)數(shù)量不多的路標被遮擋時，RRW&SC圖匹配算法能有效地應(yīng)對，獲得完全正確的數(shù)據(jù)關(guān)聯(lián)結(jié)果. 可是當(dāng)路標被遮擋多于一定數(shù)量時，RRW&SC算法也開始出現(xiàn)少量錯誤關(guān)聯(lián). 而匈牙利算法在路標有被動態(tài)遮擋時就無法獲得完全正確的數(shù)據(jù)關(guān)聯(lián)，算法的關(guān)聯(lián)正確率隨著路標遮擋數(shù)量的增加而明顯下降，從95.68%降至為67.27%. 在動態(tài)遮擋的環(huán)境里，匈牙利算法的正確率很難滿足SLAM的要求. 而基于馬氏距離規(guī)則的算法，在動態(tài)遮擋環(huán)境下的有效性則表現(xiàn)出一定的差異. 在20次實驗中，有14次的數(shù)據(jù)關(guān)聯(lián)結(jié)果完全正確. 但出現(xiàn)錯誤關(guān)聯(lián)時，該算法的正確率將大幅降低，且這些關(guān)聯(lián)錯誤難以恢復(fù)，將導(dǎo)致SLAM完全發(fā)散. 在動態(tài)遮擋的情形下，將多假設(shè)算法結(jié)合馬氏距離規(guī)則，應(yīng)能使關(guān)聯(lián)正確率提高并使得關(guān)聯(lián)錯誤恢復(fù)得到較大改善.

仿真實驗結(jié)果驗證了RRW&SC圖匹配數(shù)據(jù)關(guān)聯(lián)算法大大超過馬氏距離規(guī)則算法、匈牙利分配算法這兩個SLAM經(jīng)典數(shù)據(jù)關(guān)聯(lián)算法的關(guān)聯(lián)正確率. RRW&SC算法在模擬的3種不確定程度高、歧義性大的復(fù)雜情形下，僅在動態(tài)遮擋時圖匹配算法出現(xiàn)了數(shù)據(jù)關(guān)聯(lián)錯誤，且是在路標被遮擋數(shù)超過10個后. 相應(yīng)于RRW&SC算法的優(yōu)良性能，算法的計算復(fù)雜度也有增加.

4 結(jié) 論

提出了二次加權(quán)隨機步進結(jié)合形狀上下文的圖匹配數(shù)據(jù)關(guān)聯(lián)算法(RRW&SC). 算法的突出特點是：能更充分地利用機器人在SLAM過程中觀測獲得環(huán)境路標的位置信息和拓撲結(jié)構(gòu)信息；克服了常用數(shù)據(jù)關(guān)聯(lián)算法利用的信息含量低，在不確定程度高、歧義性大的非確定環(huán)境中難以保障關(guān)聯(lián)結(jié)果正確性等缺陷. 實驗結(jié)果顯示，在面對噪聲干擾增加、機器人迷失、路標被動態(tài)遮擋等環(huán)境中常見的非確定狀況時，RRW&SC算法能有效地實現(xiàn)正確關(guān)聯(lián).

在動態(tài)遮擋環(huán)境中，當(dāng)被遮擋路標數(shù)目較多時，RRW&SC算法出現(xiàn)了少量的錯誤關(guān)聯(lián). 若能更好地處理動態(tài)遮擋帶來的拓撲信息變化，則能減少數(shù)據(jù)關(guān)聯(lián)的錯誤. 相比于傳統(tǒng)數(shù)據(jù)關(guān)聯(lián)算法，本文算法提升了在非確定性環(huán)境中數(shù)據(jù)關(guān)聯(lián)的性能，但因求解二次加權(quán)隨機步進的復(fù)雜度較高，導(dǎo)致總的計算復(fù)雜度也有增加，后續(xù)研究可在這兩方面有所改進.

[1] Durrant-Whyte H， Bailey T. Simultaneous localization and mapping: part I[J]. IEEE Robotics and Automation Magazine，2006， 13(2): 99-110.

[2]Wang Lu， Cai Zixing. Progress of CML for mobile robots in unknown environments[J]. Robot， 2004，26(4):380-384.

[3] Neira J， Tardos J. Data association in stochastic mapping using the joint compatibility test[J]. IEEE Transactions on Robotics and Automation， 2001，17(6):890-897.

[4] Jensfelt P， Kristensen S. Active global localization for a mobile robot using multiple hypothesis tracking[J]. IEEE Transactions on Robotics and Automation， 2001，17(5):748-760.

[5] Guo Shuai， Ma Shugen， Li Bin， et al. A data association approach based on multi-rules in VorSLAM[J]. Acta Automatica Sinica， 2013(6):522-527.

[6] Chen Baifan， Cai Zixing， Zou Zhirong. A multiple hypotheses data association method in mobile robot SLAM[J]. Journal of Central South University： Science and Technology， 2012，43(2):522-527.

[7] Kwok N， Dissanayake G. An efficient multiple hypothesis filter for bearing-only SLAM[C]∥Proceedings of International Conference on Intelligent Robots and Systems(IROS 2004). [S.l.]:IEEE， 2004：736-741.

[8] Bailey T， Nebot E M， Rosenblatt J K， et al. Data association for mobile robot navigation: a graph theoretic approach[C]∥Proceedings of the IEEE International Conference on Robotics and Automation. San Francisco， USA： IEEE， 2000：2512-2517.

[9] Gamallo C， Mucientes M， Regueiro C. Visual fastSLAM through omnivision[C]∥Proceedings of the Towards Autonomous Robotic Systems (TAROS 09). Derry， UK:[s.n.]， 2009:12-14.

[10] Vivet D， Checchin P， Chapuis R. Line-based SLAM with slow rotating range sensors: results and evaluations[C]∥Proceedings of 2010 11th International Conference on Control Automation Robotics & Vision (ICARCV). [S.l.]: IEEE，2010:423-430.

[11] Cho M， Lee J， Lee K M. Reweighted random walks for graph matching[C]∥Proceedings of Computer Vision-ECCV 2010. Berlin， Heidelberg: Springer， 2010:492-505.

[12] Belongie S， Malik J， Puzicha J. Shape matching and object recognition using shape contexts[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002，24(4):509-522.

[13] Cheeseman P， Smith R， Self M. A stochastic map for uncertain spatial relationships[C]∥Proceedings of the 4th International Symposium on Robotic Research. [S.l.]: IEEE， 1987:467-474.

[14] Li Y， Meng M Q， Liang H， et al. Particle filtering for WSN aided SLAM[C]∥Proceedings of IEEE/ASME International Conference on Advanced Intelligent Mechatronics. [S.l.]: IEEE， 2008:740-745.

[15] Zhou F， Torre F D L. Deformable graph matching[C]∥Proceedings of 2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). [S.l.]: IEEE， 2013，9(4):2922-2929.

[16] Bailey T， Nieto J. SLAM package of tim bailey[EB/OL]. [2013-10-21]. http://openslam.org/bailey-slam.html.

(責(zé)任編輯：李兵)

Graph Matching Algorithm for the Data Association Problem of Simultaneous Localization and Mapping in Ambiguous and Dynamic Environments

HUA Cheng-hao1， DOU Li-hua1， FANG Hao1， FU Hao2

(1.School of Automation， Beijing Institute of Technology， Beijing 100081， China; 2.College of Mechatronic Engineering and Automation， National University of Defense Technology， Changsha，Hu’nan 410073， China)

Proposed a graph matching approach RRW&SC to tackle the data association problem inherited in the SLAM. In our framework， the graph theory was utilized to build a mathematical model for data association firstly. Then the shape context feature was extracted for each node. Reweighted random walks was lastly adopted as the optimization engine to obtain the optimal solution for the graph model. The topology structure of the landmarks and the shape of the landmarks was used by RRW&SC algorithm， thus the geometric information of the environment was greatly enhanced which facilitates the data association. Simulation results show that， compared with traditional algorithms， the proposed data association algorithm can effectively handle a variety of complicated scenarios which might occur in SLAM， including enlarged observation noise， robot being kidnapped， or dynamic occlusion.

data association; graph matching;simultaneous localization and mapping (SLAM)

2015-09-28

北京市教育委員會共建專項資助項目(XK100070532)

華承昊(1983—)，男，博士生，E-mail:huachenghao@bit.edu.cn.

TP 242.6

A

1001-0645(2016)04-0405-07

10.15918/j.tbit1001-0645.2016.04.013