基于經典ＤＳｍＴ 的Ｓｏｎａｒ柵格地圖創建
2007-01-01 00:00:00李新德黃心漢王敏
計算機應用研究 2007年3期
摘 要：基于最近提出的一種在貝葉斯和DST擴展而來的信息融合算法DSmT（Dezert—Smarandache Theory），在實驗的基礎上，結合Sonar測量的基本特性，對靜態結構化環境建模，并構造了廣義基本信度賦值函數，利用經典DSm融合規則，融合每個柵格的聲納冗余信息，計算柵格占用的Bel。最后，以Pioneer II 移動機器人作為試驗平臺，并在線對小型環境進行了3D柵格占用信度分布地圖創建，其俯視圖與實際2D地圖中的物體外觀輪廓及所在位置進行比較，其比較結果充分驗證了算法的有效性，為進一步研究應用基于折扣理論的DSmT解決異類或同類非可靠多源信息融合，基于Hybrid DSmT的動態環境地圖創建，以及多機器人聯合創建地圖和自定位奠定了堅實的基礎。
關鍵詞：不確定性; 信息融合算法; 柵格地圖; 信息融合; 移動機器人
中圖分類號：TP24文獻標志碼：A
文章編號：1001—3695(2007)03—0209—04
智能移動機器人對完全未知環境的探索一直是國內外機器人專家研究的熱點和難點[1，2]。由于機器人對探索區域環境一無所知，既沒有任何的先驗知識，包括環境的大小、形狀、內部結構等信息，也沒有燈塔、路標等人為標志，更沒有機器人關于自身在整個地圖中的位置信息，在這種情況下，移動機器人的自身定位和地圖創建的關系就好像“是雞生蛋呢，還是蛋孵雞”的問題。盡管這個問題的解決是非常困難的，但是機器人專家通過在移動機器人本體上安裝一系列的智能傳感器（比如里程計、電子羅盤、Sonar、激光、紅外和視覺等），就好像人體有了感知器官。
信息融合管理和利用這些“器官”的感知信息。目前就信息融合而言，國內外的專家學者還沒有給出一個統一的表示，僅針對具體的領域和系統，提出一個融合管理框架（分層遞階、集中式、分布式和集散式等），根據不同的融合層次，比較各種經典（概率論）和智能（模糊、神經網絡、粗集理論和D—S證據推理等）融合算法在具體問題中應用的有效性。就移動機器人而言，在未知環境中的自定位，依靠機器人內部傳感器（里程計、電子羅盤）和外部傳感器（Sonar、激光測距儀、紅外和視覺等），通過馬爾可夫[3]或者蒙特卡羅[4]算法估計其位置；在地圖創建中根據距離傳感器獲取的信息，利用概率理論、模糊理論或神經網絡等算法，采用柵格地圖、環境幾何特征或者拓撲地圖等表示方法表示環境信息，其中柵格地圖是應用最為成功的一種表示方法。本文提到的DSmT是由法國人Jean Dezert 和美國人Florentin Smarandache于2003年在貝葉斯概率和D—Ｓ證據推理[5]的基礎上發展而來的一種通用靈活有效的智能融合算法[6—8]。這種算法的最大優點是能夠有效地處理不確定、不精確和高沖突信息。這為移動機器人在柵格地圖[9，10]創建過程中處理由Sonar獲取的不確定信息提供了一個有力工具。
1 經典DSmT算法描述
DSmT是一種通用靈活有效的自下而上的嶄新的信息融合算法，它能夠分別處理底層（數據層）、中間層（特征層）、上層（決策層）的融合問題；不僅能夠處理靜態融合（主要體現在數據層和特征層）問題，而且能夠處理動態融合（主要體現在決策層）問題。最突出的優點是能夠處理多源信息的不確定性和高度沖突性，且計算量小，融合效果好[6—8]。
經典DSmT簡單描述如下：
2 基于Sonar柵格地圖創建
2.1 Pioneer Ⅱ移動機器人Sonar傳感器測距不確定分析
Pioneer Ⅱ移動機器人本體上裝有內部傳感器（里程計、電子羅盤等）和外部傳感器（Sonar、激光、紅外和視覺傳感器等），其外觀如圖1所示，其中Sonar傳感器在機器人本體上的分布情況如圖2所示，可見其分布是不均勻的。Sonar傳感器具有廉價性、使用簡單和處理數據方便等優點，已經成為移動機器人上的標準配置。其基本工作原理是：產生一束錐形波，來探測物體，并接收反射波。其示意圖如圖3所示。
由于聲納本身物理特性的限制，測量結果表現出很大的不確定性，主要表現在:
(1)聲納傳感器除了受本身制造誤差影響外，還與外界的環境有很大的關聯，如溫度、濕度和大氣壓對其均有很大的影響。
(2)聲波以喇叭的形式向外擴散，導致散射角的存在，隨著被測物體和聲納之間距離的加大，將無法確切得知被測物體在聲納掃描扇形區域的哪一點上。
(3)多個聲納傳感器的使用，將導致相互干擾；由于存在不規則物體或者多個物體，聲納波被反射掉，或者多次反射后又被其他Sonar接收，致使測量結果錯誤。
(4)由于聲納利用聲波的反射原理，對聲波吸收很大的被測物體，聲納將無能為力。
2.2 柵格地圖中聲納不確定性建模
機器人通過Sonar傳感器，掃描環境柵格，挖掘出物體在環境中的位置和外觀特征，以達到創建環境地圖的目的。首先通過實驗的方法來獲知Sonar傳感器的測量特性。
表１給出了障礙物在正對聲納的情況下從200 mm開始到3 000 mm時，在實驗室環境下的聲納測量距離數據。由表1中統計結果可知，在200 mm到3000mm的距離內的測量結果偏差不大，隨著距離的增加，平均值偏差和均方差都基本呈上升的趨勢。當距離超過3000mm時（表中沒有列出），其測量結果偏差比較大。因此我們取Rmax=3000mm。
由圖4可知，m(θ1)隨著柵格與聲納距離ρ的增加成拋物線的趨勢下降，在Rmin處最大，在R處為零。這是因為從Sonar的工作原理上看，越接近Sonar讀數的位置，所在柵格越可能被占，其為空的概率很小，給其賦為空的信度就越小。
由圖5可知，m(θ2)與柵格和聲納距離ρ的關系成高斯分布，在R處最大，在兩端最小，與實際Sonar的信息獲取特性非常吻合。
由圖6可知，m(θ1∩θ2)隨著柵格與聲納距離ρ的增加成拋物線分布，當曲線m(θ1)與m(θ2)相交時，兩者的矛盾沖突最大。但在實際中獲取兩者的交點比較麻煩，且沒有必要，通常我們用位置點R—2ε近似兩者的交點來簡化計算，經驗表明其近似值是比較合理的。
由圖7可知，m(θ1∪θ2)隨著柵格與聲納距離ρ的增加成雙曲線上升趨勢，在R處為零，充分反映了當R≤ρ≤Rmax時，對柵格信息的未知（Ignorance）程度。
圖8反映了每個柵格與原點連線和Sonar散射角中軸線之間夾角θ（θ如圖3所示）與λ之間的關系。當柵格越接近中軸，λ值越大，同時對信度值的貢獻就越大，反之越小。
總之，由圖4—8反映出，構造的廣義基本信度賦值函數(gbbaf)在理論上完全符合Sonar傳感器獲取柵格信息的物理特性，為處理柵格地圖創建中的不確定信息提供了理論依據。
3 實驗結果分析
3.1 柵格的聲納信息融合步驟
基于DSmT的聲納柵格地圖創建程序流程圖如圖9所示。
其融合步驟如下：
（1）初始化程序。假設初始時每個柵格完全被占用，即Bel(θ2)=1，移動機器人從圖10所示的環境地圖中的某一點出發，以某種策略來探測未知環境，通過Sonar獲取環境信息。
（2）利用第2節建立的不確定信度模型，通過式（３）—（７），gbbaf(如m(θ1)、m(θ2)、m(θ1∩θ2)和m(θ1∪θ2))將分別得到。如果所有信度賦值之和不為１，在這里需要歸一化處理。
（3）判斷所有聲納傳感器所掃描到的每個柵格的信息是否是新的，如果是，則轉到步驟（１）；否則，轉到（4）。
（4）判斷柵格是否被重復掃描，如果不是，則保存柵格信息；否則，轉到（5）。
（5）繼續判斷每個柵格的融合次數是否超過兩次，如果是，則停止融合；否則，轉到（6）。
（6）利用式（２）繼續融合，同時進一步判斷柵格信息融合次數是否是第一次，如果不是，則利用式（１）計算和更新Bel，然后轉到（７）；否則，轉到（８）。
（7）檢查是否所有的柵格Bel被更新，如果是則轉到（９）；否則，轉到（１）。
（8）用融合后的信度賦值更新過去的，然后轉到（１）。
（9）停止，最終退出程序。
3.2 融合結果分析
本文將環境5m×5m劃成虛擬柵格50×50，物體在真實環境的位置表示如圖10所示，機器人在環境中以“Z”字形探測策略探索。由于本文采用小型結構化環境，忽略機器人自定位的精度誤差，若大型復雜，甚至環形地圖，則必須考慮SLAM。DSmT融合算法采用限制傳播法[11]來節省計算量，即僅計算每個Sonar掃描到區域的柵格信度值，利用式（2）來融合k≥2次測量數據。最后，整個3D柵格在線占用信度分布地圖如圖11所示。
計算結果分析:
(1)識別準確率高。圖11反映了柵格占用的信度分布情況。從其俯視圖（圖12）可以看出，它與原始圖非常相似，除了個別柵格由于存在多次反射等原因而導致識別有誤，但影響不大，完全可以識別出結構化物體的基本輪廓特征，這為機器人探測危險且不可視環境提供了很好的人機交互界面。
(2)計算效率高。由于采用了DSmT算法和限制傳播法相結合的辦法，克服了以往每掃描一次計算所有柵格的缺點，提高了計算效率。另外，在這里盡管沒有詳細地比較DSmT和DST，僅從計算量的角度看，DSmT的冪集小于DST，且避免除法運算，因此計算量低[7]。
(3)由于Sonar本身特性的限制，只能識別結構化物體的大體外觀輪廓特征，對非結構化環境的描述，需要采用基于折扣理論的DSmT算法[5，12—14]融合其他傳感器信息，如激光、視覺和紅外等傳感器。
（4）僅對靜態環境建立了經典DSmT模型，對于動態環境必須建立DSmT的混合模型[15]。
4 結束語
采用經典DSmT算法，有效地解決了靜態環境柵格地圖的創建問題，同時對結構化環境中物體外觀輪廓特征的精確描述，為人類探測危險且不可視環境提供了很好的人機交互界面，為移動機器人地圖創建和準確定位同步化（SLAM）研究提供了可靠的理論依據。基于折扣理論的DSmT算法，為進一步融合其他傳感器信息提供了有力的算法平臺。對于動態環境（內有移動物體存在）的地圖創建，將從混合DSmT模型入手，選擇恰當的融合控制結構，融合其他傳感器信息，為進一步研究多機器人協調定位和創建地圖奠定基礎。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
