適用於室內環境之快速機器人同步定位與建圖

A Light-and-Fast SLAM Algorithm for Robots in Indoor Environments using Line Segment Map

郭柏瑋(Bor-Woei Kuo)

指導教授 ： 黃錫瑜

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

https://doi.org/10.6843/NTHU.2010.00528

摘要

現今機器人自動導航領域中，最重要的議題不外乎是讓機器人能夠在未探索過的環境中自我定位與建立環境地圖 (Simultaneous Localization and Mapping)。但由於SLAM為高複雜度的演算法，因此往往需要很長的運算時間與大量的記憶體空間，才能達到高準確度的自我定位與建立地圖。這篇論文中，我們提出了一個適用於室內環境之輕量化粒子濾波器 (Rao-Blackwellized Particle Filter) 來進行機器人定位，並藉由從雷射測距儀掃描環境後得到的距離資訊中，提取出線段 (line segment) 來描繪環境地圖，同時只存放這些線段在我們的地圖中來達到降低記憶體使用量的效果。由於一般室內環境中，主要的環境結構 (牆壁、門、家具…) 擁有互相垂直與平行的特性。因此在我們的系統中，只考慮具有正交特性的線段來保證建立地圖的準確度與降低機器人定位所需的運算量。其中我們是利用一個參考角度 (reference direction) 來判斷從雷射測距儀所截取出的線段中屬於環境的水平與垂直線段。並且藉由動態的修正參考角度，我們的演算法可在機器人的起始位置沒有與環境的主要架構對齊時，也可以順利的判斷出環境中的水平與垂直線段。
實驗結果顯示，我們所提出的方法不但可在複雜的室內環境中準確的將機器人定位與建立環境地圖，且當機器人行走一段距離並繞行環境一周後，能夠順利將地圖銜接起來 (loop closing)。同時，經由統計結果可見，相對於一般搭配柵格狀地圖之粒子濾波器的方法，我們所提出的輕量化粒子濾波器只需要極低的記憶體使用量與運算時間就可以達到準確的效果。

關鍵字

輕量化機器人同步定位與建圖 ； 粒子濾波器 ； 以線段描繪地圖 ； 室內環境

並列摘要

Simultaneous Localization and Mapping (SLAM) is an important technique for robotic system navigation. Due to the high complexity of the algorithm, SLAM usually needs long computational time or large amount of memory to achieve accurate results. In this paper, we present a lightweight Rao-Blackwellized Particle Filter (RBPF) based SLAM algorithm for indoor environments, which uses line segments extracted from the laser range finder as the fundamental map structure so as to reduce the memory usage. Since most major structures of indoor environments are usually orthogonal to each other, we can also efficiently increase the accuracy and reduce the complexity of our algorithm by exploiting this orthogonal property of line segments; that is, we treat line segments that are parallel or perpendicular to each other in a special way when calculating the importance weight of each particle. In our work, the orthogonal scan lines extracted from the sensor can be identified by a reference direction, which is modified each time the local map is built. By dynamically modifying the reference direction, our algorithm can successfully detect the orthogonal lines even when the robots initial pose is not aligned with the major structures of the environment.
Experimental Results shows that our work not only is capable of drawing maps in complex indoor environments but also can accurately closes a loop after the robot has traveled a long distance. Results also shows that our proposed light-and fast SLAM only needs very low amount of memory and much less computational time as compared to other grid map based RBPF SLAM algorithms.

並列關鍵字

Lightweight SLAM ； Rao-BlackWellized particle filter (RBPF) ； Line segment map ； Indoor environments

參考文獻

[1]W. Jeong and K. Lee, “CV-SLAM: A new ceiling vision-based SLAM technique,” In IEEE/RJS Int. Conf. on Intelligent Robots and Systems, 2005.

[2]H. Myung, H.-M. Jeon, and W.-Y. Jeong, “Virtual Door Algorithm for Coverage Path Planning of Mobile Robot,” IEEE International Symposium on Industrial Electronics (ISIE), 2009.

[3]V. Nguyen, A. Harati, A. Martinelli, and R. Seigwart, “Orthogonal SLAM: A step toward lightweight indoor autonomous navigation”, In Proceedings of IROS, 2006.

[5]A. Doucet, J.F.G. de Freitas, K. Murphy, and S. Russel. “Rao-blackwellized particle filtering for dynamic bayesian networks”, Proc. of the Conf. on Uncertainty in Artificial Intelligence (UAI), 2000.

[6]G. Grisetti, C. Stachniss, and W. Burgard, “Improved techniques for grid mapping with Rao-Blackwellized particle filters”, IEEE Transactions on Robotics, vol. 23, pp. 34-46, Feb 2007.