Localization and map building is essential parts in autonomous mobile robot navigation. Localization determines where mobile robot is in a given environment. Map building constructs the environment map with assumed structures. In general, localization and map building are performed simultaneously so called Simultaneous Localization and Mapping (SLAM). Task completion rates of mobile robot is determined by how the mobile robot reaches where has to accomplish a task well. Even though the mobile robot is autonomous and performs tasks by itself, user finally determines the goal position of mobile robot and establishes strategy how mobile robot accomplishes tasks. Therefore, the accuracy of SLAM is very important. Furthermore, 3D map is natively suitable to our 3D space and has more useful information. Therefore, accurate 3D SLAM is a challengeable and important problem in robotics.
In this dissertation, our objective is to establish accurate 3D SLAM. Typical SLAM is composed with five major parts: dead-reckoning, feature extraction, matching, pose estimation, and map building. Improved performance of each major part can induce accurate SLAM. This dissertation approaches to achieve the accurate 3D SLAM by improved the performance of some major parts. Among five major parts, we select three parts: dead-reckoning, feature extraction, and map buildling. All major parts are important for accurate 3D SLAM, but selected three parts have influences on other major parts, one another, and the overall performance of 3D SLAM effectively.
Firstly, we propose Encoder-Edge based State Estimation (EESE). Conventional periodic encoder sensing is used to obtain the quantized motor position. But we performed detection of the encoder edge’s time and value precisely. The EESE uses the edge-time Kalman filter (ETKF) which performs predictions at edge time and periodic sampling time, and update at edge time. Since encoder edges are detected too often at high motor speed or high encoder resolution, only the first edge in each sampling interval is utilized to reduce the computation time. The EESE guarantees far more accurate state estimation with even low encoder resolution and uncertainty on motor parameters. Performance of the EESE is validated through simulations and experiment about single motor first. And then, we applied the EESE to a two-wheeled mobile robot (TMR) for more practical situation. We confirmed the performance of EESE through the motion of TMR with and without EESE.
Next, we propose Dynamic Scan Error Compensation (DSEC) for LRF. The accuracy of conventional LRF is high, but it is not true when robot is moving. Since one LRF scanning time is very small and it is not zero, all scan ray times are different. If the time difference between scan rays is not considered during scanning, all scan rays are distorted. The distortion is critical error of LRF and can be called as dynamic scan error. This impairs the accuracy of extracted features. The source of dynamic scan error is that LRF can not know where and when scan rays are measured. In order to compensate the dynamic scan error, positions of the center of LRF every scan rays have to be obtained. From encoder data, we can obtained the positions at sampling times. Since the time invertal between scan rays is smaller than encoder sampling time, we use interpolation to compute the positions. DSEC is performed with transformation matrices with simplification to reduce the computation time because about hundreds of scan rays have to be compendated every scanning. The DSEC guarantees far more accurate LRF scan measurement at even robot motion with variable speed. Performance of the DSEC is validated through simulations of DSEC itself and 2D SLAM with and without DSEC.
Finally, we propose 3D map building and 3D SLAM based on 3D polygon map. 3D SLAM has been studied to provide more information about environment while it needs far more data processing and computation loads. For less data load, 3D infinite plane is mostly used in recent 3D SLAM. But it is not appropriate to describe 3D envrionment. We propose 3D polygon map with vertices which restricts the area of 3D plane. 3D polygon map with vertices is more less data load and useful to describe 3D environment. In order to reduce computation time and enhance the accuracy of map building, we propose consecutive sequential constructions to build 3D polygon map. First, 3D scan vector sequential bi-directional extraction will be performed. When some 3D scan vectors are collected, 3D infinite plane is extracted sequentially. From grouped 3D scan vectors in 3D plane, 3D edge vectors sequential extraction is performed. Using 3D edge vectors, we extract vertices for 3D polygon map. Proposed 3D map building is performed well in several indoor environments and the potential of that is validated in outdoor environment. Hybrid 3D SLAM of 2D SLAM method and proposed algorithm is proposed. For accurate 3D SLAM, we integrate EESE and DSEC with 3D polygon map. Using the integration, accurate polygon based 3D SLAM with EESE and DSEC is validated by experiments.
위치 추정과 지도 작성은 자동 주행 이동로봇의 핵심분야이다. 위치 추정은 이동로봇이 주어진 환경에서 어디에 있는지를 알아내는 방법이다. 지도 작성은 가정한 형태로 환경에 대한 지도를 구축하는 것이다. 일반적으로 위치 추정과 지도 작성은 동시에 이루어 지며 이를 위치 추정 및 지도 작성 (SLAM)으로 부른다. 이동로봇의 작업 완수율은 이동로봇이 수행해야 하는 위치로 얼마나 정확히 도달하는 냐에 달려있다. 그러므로 SLAM의 정확도는 매우 중요하다. 이동로봇이 자동화되고 그 스스로 작업을 수행할 지라도 일반적으로 사용자가 이동로봇의 최종 목적지와 이동로봇이 작업을 어떻게 수행할 지를 계획한다. 게다가 3차원 지도는 우리 환경에 더 적합하고 더 많은 유용한 정보를 가지고 있다. 그러한 의미로, 정확한 3차원 SLAM은 로봇분야에서 도전할 만하고 중요한 문제이다.
본 논문에서 정확한 3차원 SLAM을 구축하는 것을 목표로 한다. 전형적인 SLAM은 5개의 주요부분인 추측항법, 요소추출, 매칭, 위치추정, 지도 작성으로 구성된다. 각 부분의 성능 향상을 통해 정확한 SLAM을 구축할 수 있다. 본 논문은 주요부분 중 몇 부분을 선정하여 성능을 향상시켜 정확한 3차원 SLAM을 구축한다. 위 5개의 주요부분 중 추측항법, 요소추출, 지도작성을 선정하였다. 모든 주요부분이 정확한 3차원 SLAM을 위해 중요하지만 선정한 3가지 주요부분은 다른 주요부분의 성능에 영향을 미치고, 서로의 성능에도 영향을 미치므로 3차원 SLAM 전반적인 성능에 효과적으로 영향을 미친다.
우선, 정확한 엔코더 엣지 기반의 상태추정(EESE)을 제안하였다. 전형적인 주기적 엔코더 측정은 반올림 또는 양자화(quantized)된 모터 위치를 알아낸다. 그러나 우리는 엔코더 엣지의 시각과 값을 정확히 알아내었다. EESE는 엣지 시각에 예측을 수행 후 갱신하고 주기적 시각에는 예측을 하는 엔코더 시각 칼만필터를 사용한다. 빠른 속도의 모터나 엔코더 해상도가 높을 때에 엔코더 엣지는 너무 자주 발생하기 때문에 샘플링 주기 이내의 첫번째 엔코더 엣지만을 사용해서 계산시간을 줄이도록 하였다. EESE는 엔코더 해상도가 낮거나 모터의 파라미터들의 부정확도가 높아지는 상황에서도 상당히 정확한 상태 추정을 보장한다. EESE의 성능은 하나의 모터에 대한 시뮬레이션과 실험을 통해 입증되었다. 또, 보다 현실적인 상황에 맞추어 두바퀴 이동로봇에도 EESE를 적용하였다. 우리는 두바퀴 이동로봇의 동작에 EESE의 적용유무에 따라 EESE의 성능을 확증하였다.
다음으로, 레이저 거리 측정기(LRF)의 정확한 동적 스캔 오차 보정(DSEC)을 제안하였다. 일반적인 LRF의 정확도는 높지만 로봇이 이동 중일 때는 그렇지 않다. 한번의 스캐닝 시간은 매우 짧지만 그렇다고 0이 아니기 때문에 모든 스캔 레이(ray)의 시각은 다 다르다. 이러한 스캐닝 중의 스캔 레이간의 다른 시각을 고려하지 않는다면, 모든 스캔 레이는 뒤틀리게 된다. 이 뒤틀림은 LRF의 중대한 오차이고 동적 스캔 오차라고 부를 수 있다. 동적 스캔 오차는 추출된 요소의 정확도에도 악영향을 미친다. 동적 스캔 오차의 원인은 LRF가 스캔 레이가 어디서, 언제 측정되는 지를 모르기 때문이다. 동적 스캔 오차를 보정하기 위해선 모든 스캔 레이가 측정 될 때 LRF의 중심 위치를 알아야 한다. 엔코더 데이터로 부터 우리는 샘플링 시각마다 이를 알 수 있다. 스캔 레이간 시간 간격은 샘플링 시간 간격보다 짧기 때문에 보간(interpolation)을 사용한다. 수 백개의 스캔 레이를 매 스캐닝마다 보정해야 하므로 계산 시간을 줄이기 위해 간략화된 변환행렬로 DSEC를 수행한다. DSEC는 로봇이 다양한 속도로 주행 중이어도 정확한 스캔 데이터를 보장한다. DSEC의 성능은 DSEC 자체의 보정에 대한 시뮬레이션과 DSEC의 유무에 따른 2D SLAM의 시뮬레이션을 통해 입증되었다.
마지막으로 다각형 기반의 3차원 지도작성과 3차원 SLAM을 제안한다. 3차원 SLAM은 훨씬 많은 데이터 프로세싱과 계산 시간이 필요하지만 환경에 대한 유용한 정보가 많아서 많은 연구가 이루어져 왔다. 데이터 부담을 줄이기 위해 3차원 무한 평면을 최근 3차원 SLAM에서 주로 사용된다. 그러나, 3차원 무한 평면은 3차원 환경을 묘사하기에는 적합하지 않다. 우리는 3차원 무한 평면의 영역을 제한하는 꼭지점(vertex)로 다각형에 대해 제안했다. 꼭지점과 다각형 지도는 간결하고 3차원 환경을 묘사하기 유용하다. 지도작성의 시간을 줄이고 정확도를 향상하기 위해 우리는 일련의 순차적인(consecutive sequential) 구축방법을 제안했다. 이 방법은 순차적 3차원 스캔 벡터 추출, 순차적 3차원 무한 평면 추출, 순차적 3차원 엣지 벡터 추출, 그리고 꼭지점 추출로 이루어진다. 제안된 3차원 지도작성은 다양한 실내환경에서 3차원 지도를 잘 작성함을 확인하였고 나아가 실외환경에서도 적용할 수 있음을 확인하였다. 우리는 정확한 3차원 SLAM을 위한 EESE, DSEC와 다각형 지도 작성의 통합하고 향상된 정확도를 실험으로 확인하였다.
결론적으로, 본 연구에서는 3차원 지도작성과 3차원 SLAM을 위한 새로운 3차원 다각형 기반 지도를 제안하였고 3차원 SLAM의 정확도를 향상시킬 수 있는 EESE와 DSEC를 제안하였다. 이들을 통합하고 구현하여 보다 정확한 3차원 SLAM 성능을 검증하였다. 넓은 환경에 대해서도 제안한 3차원 SLAM을 적용하기 위해서는 3차원 지도작성의 소요시간을 보다 줄일 필요가 있고 루프 닫힘(Loop closing)을 추가하여 보다 정확한 3차원 지도 작성을 보완할 필요가 있다. 이 둘을 추가하면 넓은 환경에서도 제안한 3차원 SLAM이 적용가능 할 것으로 기대된다.
