結合擴增型卡曼濾波器及掃描匹配之機器人同步定位與地圖建置

SLAM Combining Extended Kalman Filter and Scan Matching for Robot Navigation

王美懿(Mei-Yi Wang)

指導教授 ： 陳永昌

國立清華大學/電機資訊學院/電機工程學系/碩士(2013年)

摘要

機器人同步定位及地圖建置技術(SLAM)是研究者長期關注的主題，讓機器人在未知的環境下航行，航行途中同時定位並建立環境地圖。機器人藉由所配備的感測器來預估本身的位置。從一開始使用里程計當作定位的感測器，到現在使用各種精密儀器，如相機、雷射掃描儀等，讓同步定位及地圖建置越來越準確。此外，各種使同步定位與地圖建置更精準及更有效率的方法亦逐步產生，如擴增型卡曼濾波器(Extended Kalman Filter)、粒子濾波器(Particle Filer)及掃描匹配(Scan Matching)等。
在本論文中，於同步定位及地圖建置的過程，使用雷射掃描儀SICK擷取二維環境資訊，並且以擴增型卡曼濾波器修正機器人的定位誤差。本論文將擴增型卡曼濾波器的架構結合掃描匹配的演算法；亦即，使用雷射掃描儀所取得的二維環境資訊，取代原本擴增型卡曼濾波器中的幾何特徵，如點、線等幾何特徵。再以掃描匹配替代卡曼濾波器中幾何特徵資料關聯(Data Association)的步驟，用疊代最近點(Iterative Closests Point)演算法，將前、後兩組相異的掃描點，疊代做旋轉、平移的幾何轉換，直到兩組掃描點匹配成功，也就是直到兩組掃描點的圖形趨近於相同形狀。
本論文將卡曼濾波器和掃描匹配的優點相互結合。使用掃描的資訊當作特徵，可使卡曼濾波器不需要局限於必須找出特定的幾何特徵，而能夠保留更多資料讓地圖建置得更完整；在卡曼濾波器中，幾何特徵關聯的步驟，可替代為疊代最近點演算法做前、後掃描點的掃描匹配，不需要空間保留儲存先前累積的所有掃描資料。

關鍵字

同步定位與地圖建置 ； 掃描匹配 ； 卡曼濾波器

並列摘要

Simultaneous localization and mapping (SLAM) has long been a major topic of research in mobile robot navigation. In an unknown environment, the mobile robot can localize itself and build a map at the same time while navigating. The mobile robot estimates its location through the sensors it equips with. And the sensors for SLAM get more and more accurate from odometry to camera and laser range finder. Besides, there are a variety of methods developed to make SLAM more accurate and more efficient, such as Extended Kalman Filter (EKF), Particle Filter, and scan matching.
In this thesis, the SICK laser range finder gets the raw scan data as a set of 2D points and the EKF is used to estimate the position of the robot in the SLAM process. We incorporate raw scan data and scan matching algorithms into the EKF framework. That is, the landmarks (features), like point or line, in the original feature based EKF are replaced by the raw scan data. Then, the result of the scan matching algorithm is used as a measurement to replace the data association step in the original EKF framework. Scan matching uses Iterative Closest Point (ICP) algorithm to align the corresponding points between two scan data by rotation and translation iteratively until the two data sets are matched, that is, they partially represent a common shape.
In the thesis, the combination of EKF and scan matching makes the strengths of each offset the weaknesses of the other. Using the raw scan data as landmarks makes EKF do not need to rely on the geometric models and keeps more information for map building. The data association step of EKF can be replaced by using ICP algorithm to match between two scans without the need to store the scan history.

並列關鍵字

SLAM ； Scan Matching ； Extended Kalman Filter

參考文獻

[19] J. Nieto, T. Bailey, and E. Nebot, “Recursive scan-matching SLAM,” Robotics and Autonomous Systems, pp. 39-49, 2007.

[1] R. Smith, M. Self, and P. Cheeseman. “Estimating uncertain spatial relationships in robotics,” In I.J. Cox and G.T. Wilfong, editors, Autonomous Robot Vehnicles, pp. 167-193, Springer-Verlag, 1990.

[2] R. C. Smith and P. Cheeseman. “On the representation and estimation of spatial uncertainty,” Technical Report TR 4760 & 7239, SRI, 1985.

[3] H. Durrant-Whyte and T. Bailey, “Simultaneous localization and mapping: part I,” IEEE Robotics & Automation Magazine, vol. 13, no. 2, pp. 99-110, 2006.

[4] T. Bailey and H. Durrant-Whyte, “Simultaneous localization and mapping: part II,” Robotics & Automation Magazine, IEEE, vol. 13, no. 3, pp. 108-117, 2006.