摘  要： 聯(lián)合相容分支定界算法（Joint Compatibility Branch and Bound,，JCBB）充分考慮傳感器量測之間的相關(guān)性和重新匹配關(guān)聯(lián)的可能,，但計(jì)算量隨觀測數(shù)目成指數(shù)增長。為優(yōu)化其計(jì)算復(fù)雜度和關(guān)聯(lián)準(zhǔn)確度,，以最近鄰算法（Nearest Neighbour,，NN）進(jìn)行關(guān)聯(lián)，對(duì)符合重復(fù)度和經(jīng)過設(shè)定步數(shù)的情況使用JCBB進(jìn)行特征匹配,，并以互斥準(zhǔn)則和最優(yōu)準(zhǔn)則來提高關(guān)聯(lián)準(zhǔn)確度,。引入機(jī)器學(xué)習(xí)領(lǐng)域的評(píng)價(jià)測度對(duì)改進(jìn)后算法和JCBB算法進(jìn)行比較，結(jié)果表明,，改進(jìn)后的關(guān)聯(lián)算法能夠保證更好的關(guān)聯(lián)準(zhǔn)確度,。

　　關(guān)鍵詞： 聯(lián)合相容分支定界算法（JCBB）；數(shù)據(jù)關(guān)聯(lián),；特征匹配,；準(zhǔn)確度

0 引言

　　數(shù)據(jù)關(guān)聯(lián)源于目標(biāo)跟蹤領(lǐng)域，用于確定傳感器量測信息和目標(biāo)源之間的對(duì)應(yīng)關(guān)系，錯(cuò)誤的數(shù)據(jù)關(guān)聯(lián)不僅影響導(dǎo)航和定位精度,，甚至?xí)?dǎo)致整個(gè)關(guān)聯(lián)算法不一致或者發(fā)散[1],。

　　Singer等人提出的最近鄰（Nearest Neighbor，NN）[2]算法是最早也是最簡單的數(shù)據(jù)關(guān)聯(lián)方法,，當(dāng)觀測量和特征之間的統(tǒng)計(jì)距離度量最小或者殘差概率密度最大時(shí)認(rèn)為兩者可以關(guān)聯(lián),，在環(huán)境特征密度較大的情況下，容易發(fā)生關(guān)聯(lián)失敗現(xiàn)象,。Bar-Shallom和Jaffer提出的概率數(shù)據(jù)關(guān)聯(lián)（Probability Data Association,，PDA）算法充分利用過去一定時(shí)間內(nèi)的數(shù)據(jù)信息，不依賴于過去數(shù)據(jù)關(guān)聯(lián)的正確性,，提高了算法的收斂性,，但對(duì)計(jì)算開銷要求有所提高。對(duì)PDA改進(jìn)后的聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)（Joint Probability Data Association,，JPDA）[3]算法對(duì)所有可能的關(guān)聯(lián)假設(shè)集合進(jìn)行搜索,，并以此為基礎(chǔ)尋找最優(yōu)關(guān)聯(lián)。針對(duì)NN算法忽略環(huán)境特征之間相關(guān)性的問題,，Jose Neira 等人提出了聯(lián)合相容性檢驗(yàn)（Joint Compatibility test,，JC test）算法，檢驗(yàn)一次觀測獲得的所有觀測和地圖特征之間的聯(lián)合相容性,，聯(lián)合相容分支定界（Joint Compatibility Branch and Bound,，JCBB）[4]算法能排除一些NN無法排除的關(guān)聯(lián)假設(shè)，結(jié)合分支定界法和相容性的遞增式計(jì)算搜索解釋樹的方法來獲得最優(yōu)解,。數(shù)據(jù)關(guān)聯(lián)方法還有多假設(shè)數(shù)據(jù)關(guān)聯(lián)[5],、基于圖論的關(guān)聯(lián)算法[6]、惰性數(shù)據(jù)關(guān)聯(lián)[7],、基于信息理論關(guān)聯(lián)[8]等,，它們都尋求在計(jì)算復(fù)雜度和關(guān)聯(lián)準(zhǔn)確度之間獲得更好效果，在目標(biāo)跟蹤,、數(shù)據(jù)融合等領(lǐng)域[9-11]都有廣泛涉及,。

　　在保證計(jì)算復(fù)雜度不增加的前提下，考慮算法計(jì)算復(fù)雜度和準(zhǔn)確度兩要素,，將最近鄰算法與聯(lián)合相容分支定界算法結(jié)合使用,，并以互斥準(zhǔn)則、最優(yōu)準(zhǔn)則約束誤關(guān)聯(lián)情況,，從而提高關(guān)聯(lián)準(zhǔn)確度,，降低錯(cuò)誤關(guān)聯(lián)導(dǎo)致整個(gè)算法發(fā)散的可能，進(jìn)而保證定位和更新精度,。

1 問題定義

　　1.1 特征關(guān)聯(lián)

　　移動(dòng)機(jī)器人在導(dǎo)航過程中需要構(gòu)建環(huán)境地圖并且確定自身在地圖中的位姿,，數(shù)據(jù)關(guān)聯(lián)是機(jī)器人在觀測到環(huán)境特征之后對(duì)觀測量進(jìn)行分類應(yīng)用或整合的過程,，用以確定當(dāng)前的一個(gè)或者多個(gè)觀測量是否應(yīng)該對(duì)應(yīng)到地圖中的已有特征以及對(duì)應(yīng)到哪一個(gè)特征。

　　圖1中三角形表示移動(dòng)機(jī)器人,，其頂點(diǎn)作為傳感器所在位置,，以圓形表示機(jī)器人構(gòu)建地圖中已有的特征點(diǎn)，記為F1~F5,，以方形表示當(dāng)前傳感器的觀測量z1~z5,，橢圓表示以某種距離度量表示的地圖特征的匹配范圍，忽略傳感器所得觀測量是虛警信息的情況,。z1和z2分別落在F1和F2的可匹配范圍之內(nèi)，兩對(duì)觀測—特征對(duì)可以進(jìn)行匹配,；對(duì)于z3和F3以及z3和F5均可視為匹配對(duì),，若僅以直觀距離最近原則選擇會(huì)舍去其與F5的匹配，因其與F3距離更近,；觀測量z4未落在任一特征的匹配范圍內(nèi),，將其視作待加入地圖的新特征F6。對(duì)所有觀測量和特征點(diǎn)進(jìn)行匹配即完成了數(shù)據(jù)關(guān)聯(lián)過程,，如圖1右圖所示的關(guān)聯(lián)結(jié)果直接影響地圖創(chuàng)建中特征位置的更新,，以及新特征的加入，進(jìn)而影響機(jī)器人自身定位過程,。

　　1.2 馬氏距離與卡方檢驗(yàn)

　　馬氏距離（Mahalanobis Distance）表示數(shù)據(jù)協(xié)方差之間的距離,，是計(jì)算兩個(gè)未知樣本集之間相似程度的有效方法。其與歐氏距離的不同在于它考慮不同特征之間的相關(guān)性且與測量尺度無關(guān),。對(duì)均值為,、協(xié)方差為的N維觀測量z，其馬氏距離的平方為：

　　利用Cholesky分解=CCT替換變量,，則以變量y=C-1（z-）,，得：

　　由此得馬氏距離的平方服從自由度為N的卡方分布。以符合不同自由度和準(zhǔn)確度要求的卡方分布檢驗(yàn)兩個(gè)樣本集之間是否足夠相似,，這種方法在關(guān)聯(lián)問題中得到廣泛應(yīng)用,。

2 算法

　　2.1 聯(lián)合相容分支定界算法

　　JCBB算法的核心是聯(lián)合相容準(zhǔn)則，用以檢驗(yàn)所有觀測值與地圖特征點(diǎn)之間的相容性,。相容性檢驗(yàn)標(biāo)準(zhǔn)也采用馬氏距離,，由于同時(shí)考慮所有特征與機(jī)器人之間的相關(guān)性，其匹配準(zhǔn)確度高于最近鄰算法,。對(duì)于一次關(guān)聯(lián)對(duì)應(yīng)假設(shè)集為Hk={j1,，j2，…,，jk}時(shí),，擴(kuò)展卡爾曼濾波過程中的聯(lián)合觀測方程表示為：

　　在當(dāng)前估計(jì)狀態(tài)處的線性化過程為：

　　聯(lián)合信息及其協(xié)方差為：

　　聯(lián)合相容檢測準(zhǔn)則為：

　　其中,，ｄ是聯(lián)合觀測量的維數(shù)，是要求的置信度,。如果馬氏距離滿足式（7）,，則認(rèn)為關(guān)聯(lián)解Hk滿足聯(lián)合相容條件。然后對(duì)關(guān)聯(lián)解空間采用分支定界方法進(jìn)行遍歷,，以配對(duì)數(shù)目單調(diào)非減規(guī)則為定界條件,，以聯(lián)合相容條件為分支準(zhǔn)則，搜索并最終決定觀測值和地圖特征點(diǎn)之間的最佳關(guān)聯(lián)解,。

　　2.2 改進(jìn)算法

　　初始使用最近鄰算法對(duì)多個(gè)觀測值進(jìn)行數(shù)據(jù)關(guān)聯(lián),，若無多個(gè)觀測值對(duì)應(yīng)同一個(gè)特征的情況，則接受所得關(guān)聯(lián)結(jié)果,。若出現(xiàn)干涉現(xiàn)象則調(diào)用聯(lián)合相容分支定界算法完成關(guān)聯(lián),。若在JCBB關(guān)聯(lián)過程中仍出現(xiàn)干涉現(xiàn)象，則以一次關(guān)聯(lián)中僅允許一個(gè)地圖特征與一個(gè)觀測量完成關(guān)聯(lián),，若再有此特征關(guān)聯(lián)則被拒絕,，避免多觀測量對(duì)同一地圖特征的重復(fù)匹配。

　　搜索解空間過程若有多個(gè)符合最大匹配數(shù)目的關(guān)聯(lián)解,，最優(yōu)準(zhǔn)則選定為：選擇其中Mahalanobis距離最小的關(guān)聯(lián)解作為關(guān)聯(lián)結(jié)果,。

　　改進(jìn)算法針對(duì)關(guān)于計(jì)算復(fù)雜度的考慮，結(jié)合NN計(jì)算復(fù)雜度低的特點(diǎn),，并以相應(yīng)準(zhǔn)則解決JCBB可能存在的干涉現(xiàn)象和存在多個(gè)可能的最優(yōu)解的情況以保證關(guān)聯(lián)準(zhǔn)確性,。

3 實(shí)驗(yàn)

　　3.1 評(píng)定指標(biāo)

　　引入機(jī)器學(xué)習(xí)中的評(píng)價(jià)測度對(duì)關(guān)聯(lián)性能進(jìn)行評(píng)定。以真/假（true/false）說明判斷正誤,，以正/負(fù)（positive/negative）表示判定結(jié)果,，正例判定為正例稱為真正（true positive，TP）,，負(fù)例判定為負(fù)例稱為真負(fù)（true negative,，TN），正例判定為負(fù)例稱為假負(fù)（false negative,，F(xiàn)N）,，負(fù)例判定為正例稱為假正（false positive，F(xiàn)P）,。準(zhǔn)確率（Accuracy）反映關(guān)聯(lián)算法的整體判定能力（能將正例判定為正例,，負(fù)例判定為負(fù)例），精確度（Precision）反映判定的正例中真正的正例樣本的比重,，召回率（Recall）反映被正確判定的正例占總的正例的比重,。用Precision和Recall評(píng)估一種算法，當(dāng)兩者均更高時(shí),，才能說明分類算法的性能更優(yōu)于另一種算法,。然而事實(shí)上兩者在某些情況下是矛盾的,，采用評(píng)價(jià)測度F Score（F Measure）可以綜合考慮精確度和召回率，它是二者的加權(quán)調(diào)和平均,。Accuracy（記為A）,、Precision（記為P）、Recall（記為R）,、F Score（記為F）,，依次定義為：

　　A=（TP+TN）/（TP+TN+FP+FN）（8）

　　P=TP/（TP+FP）（9）

　　R=TP/（TP+FN）（10）

　　F=（（a2+1）P×R）/（a2P+R）（11）

　　特別地，當(dāng)參數(shù)a=1時(shí),，成為最常見的F1 Score（F1 Measure）測度,，即

　　F1=2P×R/（P+R）（12）

　　3.2 實(shí)驗(yàn)參數(shù)設(shè)置

　　仿真實(shí)驗(yàn)設(shè)置為機(jī)器人從世界坐標(biāo)（0，0）出發(fā),，在規(guī)模為180 m×250 m的環(huán)境中,，沿規(guī)定路徑運(yùn)動(dòng)，依據(jù)激光測距儀傳回的觀測信息,，對(duì)環(huán)境中的62個(gè)特征點(diǎn)進(jìn)行定位，并最終返回起始點(diǎn),。仿真參數(shù)設(shè)置如下：將生成隨機(jī)噪聲的種子設(shè)置為23,，運(yùn)動(dòng)噪聲和觀測噪聲的方差分別設(shè)定為：ν=0.7 m/s，?酌=3°,；ρ=0.3 m,，b=4°。機(jī)器人運(yùn)動(dòng)速度為4 m/s,，最大轉(zhuǎn)向角速度為±20°/s,，最大轉(zhuǎn)向角±30°,，激光最大掃描距離30 m,，掃描范圍0°~180°,，控制周期和觀測周期均為0.1 s,，前后輪間距為4 m,。

　　3.3 實(shí)驗(yàn)結(jié)果分析

　　通過圖2~圖5針對(duì)不同指標(biāo)比較結(jié)果可知,，當(dāng)改進(jìn)前關(guān)聯(lián)算法的準(zhǔn)確率和精確度變低時(shí),，改進(jìn)后算法的準(zhǔn)確率和精確度仍保持較高,；以召回率和精確度都較高或者以綜合了精確度和召回率的F1 Score作為評(píng)價(jià)原則,，改進(jìn)后算法關(guān)聯(lián)性能都優(yōu)于改進(jìn)前,。調(diào)整噪聲參數(shù)，改進(jìn)后算法仍能保持更優(yōu)的關(guān)聯(lián)性能,。

4 結(jié)束語

　　針對(duì)聯(lián)合相容分支定界算法計(jì)算復(fù)雜度較高的缺點(diǎn),，為改進(jìn)其關(guān)聯(lián)性能，考慮最近鄰算法計(jì)算復(fù)雜度低及可能出現(xiàn)的干涉現(xiàn)象和搜索最優(yōu)解可能出現(xiàn)的匹配數(shù)相同的情況,，將其與最近鄰算法和最優(yōu)及互斥準(zhǔn)則融合,，改進(jìn)算法提高了關(guān)聯(lián)準(zhǔn)確度,，降低了錯(cuò)誤關(guān)聯(lián)引起算法發(fā)散的概率，進(jìn)而減少機(jī)器人對(duì)自身位姿和構(gòu)圖的不確定性,。在更復(fù)雜環(huán)境下的關(guān)聯(lián)方法選擇和計(jì)算復(fù)雜度處理是待研究的問題,。

參考文獻(xiàn)

　　[1] DURRANT-WHYTE H， BAILEY T. Simultaneous localization and mapping： part I[J]. Robotics & Automation Magazine,， IEEE,， 2006，13（2）：99-110.

　　[2] BEIS J S,， LOWE D G. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces[C]. Proceedings of the IEEE 1997 Computer Society Conference on Computer Vision and Pattern Recognition,， 1997：1000-1006.

　　[3] FORTMANN T E， BAR-SHALOM Y,， SCHEFFE M. Sonar tracking of multiple targets using joint probabilistic data association[J]. Oceanic Engineering,， IEEE Journal of， 1983,，8（3）： 173-184.

　　[4] NEIRA J,， TARD?魷S J D. Data association in stochastic mapping using the joint compatibility test[J]. Robotics and Automation， IEEE Transactions on,， 2001,，17（6）：890-897.

　　[5] COX I J， LEONARD J J. Modeling a dynamic environment using a Bayesian multiple hypothesis approach[J]. Artificial Intelligence,， 1994,，66（2）：311-344.

　　[6] BAILEY T， NEBOT E M,， ROSENBLATT J,， et al. Data association for mobile robot navigation： a graph theoretic approach[C]. Robotics and Automation， 2000. Proceedings. ICRA′00. IEEE International Conference on. 2000：2512-2517.

　　[7] H?魧HNEL D,， THRUN S,， WEGBREIT B， et al. Towards lazy data association in SLAM[C]. Robotics Research. 2005,， Springer： 421-431.

　　[8] KAESS M,， DELLAERT F. Covariance recovery from a square root information matrix for data association[J]. Robotics and Autonomous Systems， 2009,，57（12）：1198-1210.

　　[9] CHONG C Y,， KUMAR S P. Sensor networks： evolution， opportunities,， and challenges[J]. Proceedings of the IEEE,， 2003， 91（8）： 1247-1256.

　　[10] DALLIL A,， OUSSALAH M,， OULDALI A. Sensor fusion and target tracking using evidential data association[J]. Sensors Journal,， IEEE， 2013,，13（1）：285-293.

　　[11] WU Z,， THANGALI A， SCLAROFF S,， et al. Coupling detection and data association for multiple object tracking[C]. Computer Vision and Pattern Recognition （CVPR）,， 2012 IEEE Conference on. 2012： 1948-1955.