For a mobile robot to operate autonomously, it should fulfill three requirements: First, it should have knowledge about its operational environment. Second, it should be able to sense the outer environment. Third, it should be provided localization ability to estimate its current position. A mobile robot obtains environmental data using exteroceptive sensors, which is converted to the preferred type of information. The obtained information is compared to the knowledge database about the environment, i.e. map, and the current pose estimate is calculated by localization process.
According to the availability of the initial pose, localization process is divided into two categories: local localization, also known as pose tracking, assumes that the initial robot pose is known. Hence, it focuses on the accuracy and speed of the localization process. The other approach, global localization concentrates on how to find the robot pose in a given map without initial guess. Hence, robustness is more important issue than algorithmic speed or accuracy.
In addition, the environmental knowledge is not always available. A mobile robot in this situation should be able to build its own representation about the environment. To build an environmental map, however, the robot should know its current position. Approaches managing this problem are called SLAM (Simultaneous Localization And Mapping) or CML (Concurrent Mapping and Localization).
In this dissertation, we deal with localization and SLAM problem for indoor mobile robots. Local localization algorithm based on proposed vector-matching makes it possible to estimate the robot`s pose more accurately and quickly than other approaches. On the other hand, traditional approaches for global localization problem does not guarantee the robustness of localization performance in an environment that is highly occupied with obstacles. We propose Vector Pattern Matching (VPM) scheme for global localization which helps efficient pose hypothesis generation and robust pose estimation even in an environment more than half of which is filled with obstacles. For SLAM problem, we proposed VectorSLAM algorithm, which enables to build a vector map using less amount of memory than grid-based approaches. Also VectorSLAM presents a novel loop-closing method, which has not been clearly stated by any other line segment-based mapping approaches. This Weighted Error Distribution (WED) method solves loop-closing problem in a highly efficient manner.
이동 로봇이 주어진 업무를 자율적으로 수행하기 위해서는 다음 세가지 요구조건을 충족시켜야 한다. 이동 로봇은 첫째, 작업 환경에 대한 배경 지식을 갖추고 있어야 한다. 둘째, 외부 환경을 인식할 수 있는 센서를 갖추어야 한다. 셋째, 자신의 위치를 추정할 수 있는 방안을 갖추어야 한다. 이동 로봇은 센서로부터 환경 정보를 수집하며, 수집된 센서 정보는 로봇이 이용하기 용이한 형태로 가공된다. 수집된 정보는 로봇에 저장된 환경 정보, 즉 지도와 함께 비교되어 로봇의 위치를 추정하는 데 활용된다.
초기 위치를 아느냐, 혹은 모르느냐에 따라 위치 추정 문제는 두 가지로 구분된다. 지역 위치 추정은, 위치 추적이라고도 불리는데, 로봇이 자신의 초기 위치를 안다고 가정한다. 따라서 위치 추정에서 중요한 것은 수행의 정확도와 속도이다. 한편, 전역 위치 추정은 로봇이 자신의 초기 위치를 모를 때, 주어진 지도에서 자신의 위치를 찾는 문제이다. 따라서 알고리즘의 속도 및 정확도 보다는 강인성에 초점을 둔다.
또한, 로봇이 환경에 대한 지도를 항상 알 수는 없다. 이런 경우 로봇은 스스로 환경에 대한 지도를 작성할 수 있어야 한다. 그런데 지도를 작성하기 위해서는 자신의 위치를 알아야 하는데 이와 같은 문제를 SLAM (Simultaneous Localization and Mapping) 혹은 CML (Concurrent Mapping and Localization)이라고 표현한다.
본 논문에서는 실내 환경에서 동작하는 로봇을 위한 위치 추정 및 SLAM 문제를 다루고자 한다. 벡터 대응법에 기반한 지역 위치 추정 알고리즘은 기존의 알고리즘에 비해 빠르고 정확한 위치 추정을 가능하게 한다. 한편, 전역 위치 추정을 위한 기존의 접근 방식은 장애물이 다수 존재하는 환경에서 그 정확성이 보장되지 못한다. 본 논문에서는 벡터 패턴 대응법을 제안하여, 장애물이 50% 이상인 환경에서도 전역 위치 추정이 안정적으로 수행되도록 하였다. SLAM 문제를 위해서는 벡터에 기반한 지도 제작 알고리즘인 VectorSLAM을 제안하여, 메모리 사용량이 매우 적은 벡터 지도를 실시간으로 작성할 수 있도록 하였다. 이 VectorSLAM 알고리즘은 기존의 선분 기반 알고리즘이 제시하지 못한 닫힌 환상선 (loop-closing) 문제에 대한 해결책으로 가산 오차 분산법 (Weighted Error Distribution)을 제안한다.
