摘  要： 聯(lián)合相容分支定界算法（Joint Compatibility Branch and Bound，JCBB）充分考慮傳感器量測之間的相關(guān)性和重新匹配關(guān)聯(lián)的可能,，但計算量隨觀測數(shù)目成指數(shù)增長,。為優(yōu)化其計算復(fù)雜度和關(guān)聯(lián)準(zhǔn)確度，以最近鄰算法（Nearest Neighbour,，NN）進(jìn)行關(guān)聯(lián),，對符合重復(fù)度和經(jīng)過設(shè)定步數(shù)的情況使用JCBB進(jìn)行特征匹配，并以互斥準(zhǔn)則和最優(yōu)準(zhǔn)則來提高關(guān)聯(lián)準(zhǔn)確度,。引入機器學(xué)習(xí)領(lǐng)域的評價測度對改進(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)源之間的對應(yīng)關(guān)系，錯誤的數(shù)據(jù)關(guān)聯(lián)不僅影響導(dǎo)航和定位精度,，甚至?xí)?dǎo)致整個關(guān)聯(lián)算法不一致或者發(fā)散[1],。

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

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

1 問題定義

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

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

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

　　1.2 馬氏距離與卡方檢驗

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

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

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

2 算法

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

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

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

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

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

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

　　2.2 改進(jìn)算法

　　初始使用最近鄰算法對多個觀測值進(jìn)行數(shù)據(jù)關(guān)聯(lián),，若無多個觀測值對應(yīng)同一個特征的情況,，則接受所得關(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)中僅允許一個地圖特征與一個觀測量完成關(guān)聯(lián)，若再有此特征關(guān)聯(lián)則被拒絕,，避免多觀測量對同一地圖特征的重復(fù)匹配,。

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

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

3 實驗

　　3.1 評定指標(biāo)

　　引入機器學(xué)習(xí)中的評價測度對關(guān)聯(lián)性能進(jìn)行評定,。以真/假（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評估一種算法,，當(dāng)兩者均更高時，才能說明分類算法的性能更優(yōu)于另一種算法,。然而事實上兩者在某些情況下是矛盾的,，采用評價測度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時，成為最常見的F1 Score（F1 Measure）測度,，即

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

　　3.2 實驗參數(shù)設(shè)置

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

　　3.3 實驗結(jié)果分析

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

4 結(jié)束語

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