Improved Polar Scan Matching using a Scan Restoration Technique

학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2012. 2. 이범희.본 논문에서는 이동 장애물이 존재하는 동적 환경(dynamic environment)내에서 레이저 거리 센서(laser range finder)를 탑재한 이동로봇이 강인한 레이저 스캔 매칭(laser scan matching)을 수행할 수 있도록 스캔데이터를 처리하는 스캔 복원 기법을 제안한다. 레이저 스캔 매칭은 레이저 거리 센서를 탑재한 이동로봇의 Simultaneously Localization and Mapping(SLAM)을 위한 핵심기술이며, 제안된 스캔 복원 기법을 통해 동적 환경 내에서도 레이저 스캔 매칭을 원활하게 수행할 수 있다. 레이저 스캔 매칭은 서로 다른 두 시점에서 이동로봇이 획득한 두 레이저 스캔데이터를 비교한 뒤 정합(matching)하는 기술로, 정합하는 과정을 통해 두 시점간 이동로봇의 이동 정보를 추정해 이동로봇의 오도미터(odometer) 정보보다 신뢰도가 높은 이동 정보를 얻을 수 있다. 기존의 레이저 스캔 매칭 기법들 중 Polar Scan Matching(PSM)은 매칭의 결과가 정확하면서도 수행속도가 다른 기법들에 비해 빠르다는 장점을 가지므로 이동로봇의 실시간 SLAM에 적용되기 적합하다. 하지만 기존의 대다수 레이저 스캔 매칭 기법들은 실내의 정형 환경(structured environment)에서는 정확한 매칭 결과를 구할 수 있지만, 이동 장애물이 존재하는 실내 혹은 실외의 비정형 환경(unstructured environment)에서는 매칭을 제대로 수행하지 못한다는 단점을 지니고 있다. 이를 해결하기 위해 카메라와 같은 비전 센서나 GPS 등 다른 센서들을 보완책으로 사용하는 여러 연구들이 제시되고 있다. 본 논문에서는 레이저 거리 센서의 데이터만을 이용해 비정형 환경 내에서 PSM이 강인한 스캔 매칭을 수행할 수 있도록 하기 위해, 비정형 환경에 해당하는 스캔데이터의 분할(segment)들을 주변의 정형 환경으로 복원하는 방법인 스캔 복원 기법을 제안한다. 제안된 기법의 구현을 위해서 우선 적응적 변곡점 탐지기법(adaptive breakpoint detector)을 통해 스캔데이터를 분할한 뒤 스캔데이터에서 곡률함수(curvature function)를 추출한다. 이어서 복원의 대상이 될 분할을 탐색한 뒤 보간법 (interpolation)을 적용해 대상 분할을 복원한다. 실제 실험을 통해 PSM이 매칭을 실패하는 비정형 환경을 스캔 복원 기법을 이용해 정형 환경으로 복원한 경우, PSM이 성공적으로 매칭을 수행하는 것을 알 수 있었다. 또한 스캔 복원 기법의 수행속도가 PSM의 매칭 과정의 수행속도보다 빨라 이동로봇의 SLAM에 많은 계산 부하를 가하지 않은 채 적용되기에 적합한 것을 확인하였다.In this thesis, a scan restoration technique which handles raw laser scan data is proposed for a laser range finder (LRF) mounted mobile robot to perform the laser scan matching robustly in dynamic environments with the moving obstacles. The laser scan matching is a core technique for SLAM (Simultaneously Localization and Mapping) of a LRF mounted mobile robot and we can perform scan matching in dynamic environments without a hitch using the proposed technique. The laser scan matching algorithm compares two laser scan data which were acquired by a running mobile robot in two different times and matches them to estimate the pose difference of the mobile robot. Through this process, we can obtain the reliable moving information compared to odometry of the mobile robot. Polar Scan Matching (PSM), one of the laser scan matching algorithms, has advantages that its matching accuracy is high and performing speed is faster than other algorithms. Although almost all of conventional laser scan matching algorithms show superior matching result in indoor structured environments, they have a drawback that they can't fulfill matching in dynamic environments with moving obstacles or occlusions. Many researchers suggested approaches to this problem by adapting other sensors (vision sensors like camera, GPS, etc.) to support the LRF's uncertain information. In this thesis, a scan restoration technique is proposed, which restores segments of scan data, which are indicating unstructured environments, to nearby structured environment for performing robust PSM in dynamic unstructured environments using only the LRF's scan data. First, the proposed technique segments the laser scan data using an Adaptive Breakpoint Detector and extracts the curvature functions. Then, after investigating target segments for restoration, the proposed technique interpolates their curvature values based on non-restoration targets to restore the scan data. In real experiment, PSM using scan restoration technique succeeded laser scan matching in unstructured environments where original PSM failed to. Also, it was confirmed that the performance speed of scan restoration technique is faster than speed of scan matching processes of PSM, so the proposed technique can be used in SLAM without inflicting heavy computational load.Maste