KR101202108B1

KR101202108B1 - 이동 로봇의 위치 추정 방법

Info

Publication number: KR101202108B1
Application number: KR1020100052108A
Authority: KR
Inventors: 정우진; 문창배
Original assignee: 고려대학교 산학협력단
Priority date: 2010-06-03
Filing date: 2010-06-03
Publication date: 2012-11-15
Anticipated expiration: 2030-06-03
Also published as: KR20110132659A

Abstract

본 발명은 이동 로봇의 위치 추정 방법에 관한 것이다. 본 발명에 따른 이동 로봇의 위치 추정 방법은 (a) 레인지 센서의 스캔에 따라 스캔 데이터가 획득되는 단계와; (b) 상기 스캔 데이터에 기초한 스캔 범위 영역과, 기 등록된 환경 지도로부터 예측되는 예측 데이터에 기초한 예측 범위 영역 간의 편차에 기초하여 매칭 에러를 산출하는 단계와; (c) 상기 (b) 단계에서 산출된 상기 매칭 에러가 에러 문턱치를 초과하는지 여부에 따라 위치 추정 실패 여부를 판단하는 단계와; (d) 상기 (c) 단계에서 위치 추정 실패로 판단된 경우, 상기 환경 지도 상의 적어도 일 영역으로부터 추출된 복수의 위치 샘플 각각에 대해 매칭 에러를 산출하는 단계와; (e) 상기 (d) 단계에서 산출된 상기 매칭 에러를 기 설정된 확률 밀도 함수에 적용하여 상기 이동 로봇의 위치를 추정하는 단계를 포함하는 것을 특징으로 한다. 이에 따라, 매칭 에러를 스캔 데이터와 예측 데이터에 기초한 면적 단위로 산출하여, 맵핑되지 않은 장애물 등에 의해 야기되는 센서 데이터의 부분적인 손상에 강인하고, 정확한 위치 추정 실패의 판단이 가능하게 된다.

Description

이동 로봇의 위치 추정 방법{LOCALIZING METHOD FOR MOBILE ROBOT}

본 발명은 이동 로봇의 위치 추정 방법에 관한 것으로서, 보다 상세하게는 센서 데이터의 부분적인 손상에 강인하고, 정확한 위치 추정 실패의 판단이 가능하면서도 이동 로봇의 위치 추정의 정확성 및 추정 속도가 향상된 이동 로봇의 위치 추정 방법에 관한 것이다.

이동 로봇은 실용 방안의 지속적인 연구로 인하여 산업용으로서 뿐만 아니라 청소 로봇, 경비 로봇, 안내 로봇과 같은 일상 생활용으로서도 사용되며 실생활에서도 차지하는 비중이 점점 커지고 있다.

이와 같은 이동 로봇이 자율 주행을 하기 위해서는 이동 로봇의 위치를 파악하는 위치 추정이 필수적으로 요구된다. 이동 로봇의 위치 추정은 환경에 대한 정보와 센서로 측정한 정보를 이용하여 이동 로봇의 위치를 추정하는 기술로써, 이동 로봇의 주행을 위한 핵심 기술이다.

이동 로봇의 정확한 위치 추정은 매칭 에러(Matching error)와 확률 업데이트 룰(Observation likelihood model)을 포함하는 관측 우도 모델(Observation likelihood model)의 설계, 정확한 위치 추정 실패의 감지, 그리고 위치 추정을 실패한 경우 로봇 위치로의 정확한 복귀 등과 같은 다양한 변수가 영향을 미치게 된다.

이러한 이동 로봇의 위치 추정 기술과 관련하여, F. Dellaert, D. Fox, W.Burgard and S. Thrun는 논문 "Monte Carlo Localization for Mobile Robots(IEEE International Conference on Robotics & Automation (ICRA'9), Detroit, USA, May. 1999, pp. 1322-1328)"에서 Monte Carlo Localization(이하, "MCL") 기법을 제안하였다. MCL 기법은 전역 위치 추정(Global localization)과 지역 위치 추정(Local localization) 모두를 다룰 수 있으며, 센서 노이즈에 대한 강인성으로 인해 폭넓게 사용되고 있다.

또한, 관측 우도 모델(Observation likelihood model)은 이동 로봇의 자체 위치 추정 문제의 해결을 위해 폭넓게 연구되어 왔다. 일반적으로 관측 우도 모델(Observation likelihood model)의 설계는 매칭 에러의 설계와 이를 이용한 확률 업데이트 룰(Probability update rule)의 설계를 포함하게 된다.

Thrun 등은 논문 "Probabilistic Robotics(The MIT Press, 2005, pp.153-169.)"에서 Beam model을 제안하였다. 그런데, Beam model은 개별적인 센서 측정치의 곱에 의해 계산되므로, 센서 데이터의 부분적인 오류에 민감하게 되는바, 주어진 환경 지도에서 매핑(Mapping)되지 않은 장애물의 제거를 위한 추가적인 필터링 기법이 요구된다.

한편, 이동 로봇의 위치 추정과 관련된 중요한 문제 중 하나는 위치 추정의 실패를 정확히 감지하는 것이다. Sidek 등은 논문 "Integrating Actuator Fault and Wheel Slippage Detections within FDI Framework(Proc. 5th WSEAS International Conference on Circuits, Systems, Electronics, Control & Signal Processing, Dallas, Texas, 2006, pp. 31-36.)"에서 신경망을 이용한 휠 미끄러짐의 감지를 위한 FDI framework를 제안하였다. 그런데, Sidek 등의 논문에 제시된 기법은 추가적인 가속계를 이용하고 있어, 시스템이 복잡해지는 단점이 있다.

또한, Sundvall 등은 논문 "Fault detection for mobile robots using redundant positioning systems(Proc. IEEE International Conference on Robotics & Automation (ICRA'6), Orlando, Florida, May 2006, pp. 3781-3786.)"에서 레이저 스캐너를 이용하여 매핑되지 않은 장애물에 의해 발생하는 충돌을 감지하는 방법을 제안하고 있다. 이외에도 파티클 필터를 이용하여 6개의 휠이 설치된 Rover의 결함을 감지하기 위한 방법을 제안되었다.

위치 추정을 실패한 경우 이동 로봇의 실제 위치로의 정확한 복귀를 위해, Thrun 등은 논문 "Monte Carlo Localization with Mixture Proposal Distribution(Proc. AAAI National Conference on Artificial Intelligence (AAAI 2000), Austin, Texas, 2000, pp.839-865.)에서 Mixture proposal distribution을 갖는 MCL 기법을 제안하고 있다.

Mixture proposal distribution을 갖는 MCL 기법은 센서 측정치에 기초하여 분배된 전역 위치 추정 생태로 부분적인 샘플(partial samples)을 이용하고 있다. 그러나, 이 기법은 휠 미끄러짐에 의한 위치 추정 실패에 적용하기에는 그 속도가 느린 문제점이 있다.

이에, 본 발명은 상기와 같은 기존의 연구들이 갖는 문제점을 해결하기 위해 안출된 것으로서, 인간이 공존하는 실제 환경, 예를 들어 박물관이나 오피스 빌딩과 같이 이동 로봇의 환경 지도에 맵핑(Mapping)되지 않은 장애물이 공존하는 실제 환경에서 적용이 가능한 이동 로봇의 위치 추정 방법을 제공하는데 그 목적이 있다.

또한, 맵핑되지 않은 장애물 등에 의해 야기되는 센서 데이터의 부분적인 손상에 강인하고, 정확한 위치 추정 실패의 판단이 가능하면서도 추정을 실패할 때 이동 로봇의 실제 위치로 복귀하는데 있어 이동 로봇의 위치 추정의 정확성 및 추정 속도가 향상된 이동 로봇의 위치 추정 방법을 제공하는데 또 다른 목적이 있다.

이를 위해 인간과 같은 맵핑되지 않은 장애물에 강인한 관측 우도 모델(Observation likelihood model)을 설계하고, 관측 우도 모델(Observation likelihood model) 상의 매칭 에러를 통한 위치 추정 상태를 추적하며, 돌발적인 휠 미끄러짐 등에 의해 야기되는 위치 추정 실패에서 이동 로봇의 정확하고 빠른 위치 추정이 가능한 이동 로봇의 위치 추정 방법을 제공하는데 그 목적이 있다.

상기 목적은 본 발명에 따라, 이동 로봇의 위치 추정 방법에 있어서, (a) 레인지 센서의 스캔에 따라 스캔 데이터가 획득되는 단계와; (b) 상기 스캔 데이터에 기초한 스캔 범위 영역과, 기 등록된 환경 지도로부터 예측되는 예측 데이터에 기초한 예측 범위 영역 간의 편차에 기초하여 매칭 에러를 산출하는 단계와; (c) 상기 (b) 단계에서 산출된 상기 매칭 에러가 에러 문턱치를 초과하는지 여부에 따라 위치 추정 실패 여부를 판단하는 단계와; (d) 상기 (c) 단계에서 위치 추정 실패로 판단된 경우, 상기 환경 지도 상의 적어도 일 영역으로부터 추출된 복수의 위치 샘플 각각에 대해 매칭 에러를 산출하는 단계와; (e) 상기 (d) 단계에서 산출된 상기 매칭 에러를 기 설정된 확률 밀도 함수에 적용하여 상기 이동 로봇의 위치를 추정하는 단계를 포함하는 것을 특징으로 하는 이동 로봇의 위치 추정 방법에 의해서 달성된다.

여기서, 상기 (d) 단계에서 상기 복수의 위치 샘플은 기 등록된 모션 모델에 기초한 최대 모션 경계 영역 내에서 추출될 수 있다.

한편, 상기 목적은 본 발명의 다른 실시 형태에 따라, 이동 로봇의 위치 추정 방법에 있어서, (a) 레인지 센서의 스캔에 따라 스캔 데이터가 획득되는 단계와; (b) 상기 스캔 데이터와, 기 설정된 환경 지도에 기초하여 예측되는 예측 데이터에 기초하여 매칭 에러를 산출하는 단계와; (c) 상기 (b) 단계에서 산출된 상기 매칭 에러가 에러 문턱치를 초과하는지 여부에 따라 위치 추정 실패 여부를 판단하는 단계와; (d) 상기 (c) 단계에서 위치 추정 실패로 판단된 경우, 기 등록된 모션 모델에 기초한 최대 모션 경계 영역 내에서 추출되는 복수의 위치 샘플 각각에 대해 매칭 에러를 산출하는 단계와; (e) 상기 (d) 단계에서 산출된 상기 매칭 에러를 기 설정된 확률 밀도 함수에 적용하여 상기 이동 로봇의 위치를 추정하는 단계를 포함하는 것을 특징으로 하는 이동 로봇의 위치 추정 방법에 의해서도 달성될 수 있다.

여기서, 상기 (b) 단계는 상기 스캔 데이터에 기초하여 스캔 범위 영역을 산출하는 단계와; 상기 예측 데이터에 기초하여 예측 범위 영역을 산출하는 단계와; 상기 스캔 범위 영역과 상기 예측 범위 영역 간의 편차에 기초하여 상기 매칭 에러를 산출하는 단계를 포함할 수 있다.

여기서, 상기 매칭 에러는 수학식

(여기서, Em(x)는 상기 매칭 에러이고,

는 시간 t에서의 j번째 상기 스캔 데이터이고,

는 시간 t에서의 j번째 상기 예측 데이터이고,

는 시간 t에서의 j번째 상기 스캔 범위 영역이고,

는 시간 t에서의 j번째 상기 예측 범위 영역이고, Δθ는 상기 레인지 센서의 각 해상도(Angular resolution)이다)에 의해 산출될 수 있다.

그리고, 상기 (b) 단계에서 상기 예측 데이터는 레이-캐스팅 알고리즘(Ray-casting algorithm)을 통해 상기 환경 지도로부터 계산될 수 있다.

또한, 상기 에러 문턱치는 상기 레인지 센서의 이전 스캔 동작들에 대한 상기 (b) 단계의 수행을 통해 산출된 매칭 에러의 통계값에 기초하여 업데이트될 수 있다.

그리고, 상기 에러 문턱치에는 상기 환경 지도의 그리드 해상도에 기초하여 결정되는 에러 기준치가 오차 범위로 반영될 수 있다.

여기서, 상기 에러 문턱치는 수학식

(여기서, h는 상기 에러 문턱치이고,

는 (i-k) 번째 스캔에서 i번째 스캔까지의 상기 매칭 에러의 평균값이고,

는 (i-k) 번째 스캔에서 i번째 스캔까지의 상기 매칭 에러의 표준편차이고, bias는 상기 환경 지도의 그리드 해상도에 기초하여 결정되는 에러 기준치이다)에 의해 산출될 수 있다.

그리고, 상기 (b) 단계에서 산출된 매칭 에러는 미디언 필터(Median filter)에 의해 필터링되어 상기 (c) 단계에 반영될 수 있다.

그리고, 상기 모션 모델은 가우시안 확률 분포를 갖는 모션 모델이 적용되며; 상기 최대 모션 경계 영역은 상기 (c) 단계의 수행을 통한 직전 위치 추정 성공 위치를 중심으로 상기 모션 모델에 기초하여 산출되는 최대 이동 거리를 반경으로 하는 원 형태로 설정될 수 있다.

또한, 상기 최대 이동 거리는 수학식

(여기서, S_max는 상기 최대 이동 거리이고, σ는 상기 모션 모델의 표준 편차이고, Δs_i는 상기 이동 로봇의 휠 엔코더로부터 측정된 이동 거리이다)에 의해 산출될 수 있다.

그리고, 상기 (e) 단계는 (e1) 상기 (d) 단계에서 산출된 상기 매칭 에러를 상기 확률 밀도 함수에 적용하여 상기 각 위치 샘플에 대한 추정 확률을 산출하는 단계와; (e2) 상기 산출된 추정 확률에 기초하여 후보 샘플을 추출하는 단계와; (e3) 상기 추출된 후보 샘플에 대한 매칭 에러를 산출하는 단계와; (e4) 상기 (e3) 단계에서 산출된 상기 매칭 에러를 상기 확률 밀도 함수에 적용하여 상기 각 후보 샘플에 대한 추정 확률을 산출하는 단계와; (e4) 상기 (e2) 단계, 상기 (e3) 단계 및 상기 (e4) 단계의 반복적인 수행을 통해 수렴되는 수렴 위치를 상기 이동 로봇의 위치로 추정하는 단계를 포함할 수 있다.

그리고, 상기 확률 밀도 함수는 포화 가우시안 함수(Saturated Gaussian function)가 적용되며, 수학식

(여기서, p(E_m(x))는 상기 위치 샘플 또는 상기 후보 샘플의 추정 확률이고, η는 노르말라이저(Normalizer)이고, σ_t는 시간 t에서 상기 위치 샘플 또는 상기 후보 샘플에 대한 상기 매칭 에러의 표준편차이고, μ_t는 시간 t에서 상기 위치 샘플 또는 상기 후보 샘플에 대한 상기 매칭 에러의 평균값이고, bias는 상기 환경 지도의 그리드 해상도에 기초하여 결정되는 에러 기준치이다)로 표현될 수 있다.

상기와 같은 구성을 통해, 매칭 에러를 스캔 데이터와 예측 데이터에 기초한 면적 단위로 산출하여, 맵핑되지 않은 장애물 등에 의해 야기되는 센서 데이터의 부분적인 손상에 강인하고, 정확한 위치 추정 실패의 판단이 가능한 이동 로봇의 위치 추정 방법이 제공된다.

또한, 위치 추정 실패의 상황에서 환경 지도 전체 영역으로부터 위치 샘플을 추출하지 않고 매칭 에러의 통계값에 기초한 최대 모션 경계 영역 내에서만 위치 샘플을 추출함으로써, 위치 추정 실패 상황으로부터 이동 로봇의 실제 위치로 복귀하는데 있어 이동 로봇의 위치 추정의 정확성 및 추정 속도를 현저히 향상시킬 수 있는 이동 로봇의 위치 추정 방법이 제공된다.

이를 통해, 인간이 공존하는 실제 환경, 예를 들어 박물관이나 오피스 빌딩과 같이 이동 로봇의 환경 지도에 맵핑(Mapping)되지 않은 장애물이 공존하는 실제 환경에서 적용이 가능하게 된다.

도 1은 본 발명에 따른 이동 로봇의 위치 추정 방법을 설명하기 위한 제어 흐름도이고,
도 2는 본 발명에 따른 이동 로봇의 위치 추정 방법에 따라 산출되는 매칭 에러를 개념적으로 설명하기 위한 도면이고,
도 3은 본 발명에 따른 이동 로봇의 위치 추정 방법의 매칭 에러 분포를 시뮬레이션한 예를 도시한 도면이고,
도 4는 본 발명에 따른 이동 로봇의 위치 추정 방법에서 이동 로봇의 주시 방향(Heading direction)의 오차가 존재할 때의 매칭 에러를 나타낸 도면이고,
도 5는 이동 로봇에 MCL이 적용된 생태에서, MCL이 11,000 스캔 과정을 수행하는 동안 실험적으로 측정된 매칭 에러의 히스토리를 나타낸 도면이고,
도 6은 본 발명에 따른 이동 로봇의 위치 추정 방법의 최대 모션 경계 영역을 개념적으로 설명하기 위한 도면이고,
도 7은 Beam model과 본 발명에 따른 이동 로봇의 위치 추정 방법에 따른 확률 분포를 각각 도시한 도면이고,
도 8 및 도 9는 본 발명에 따른 이동 로봇의 위치 추정 방법의 매칭 에러를 이용한 위치 추정 결과를 도시한 도면이고,
도 10은 미디언 필터가 적용되지 않은 상태와 적용된 상태에서 각각 측정된 매칭 에러와 에러 문턱치를 나타낸 그래프이고,
도 11 및 도 12는 본 발명에 따른 이동 로봇의 위치 추정 방법에 따라 이동 로봇의 실제 위치로의 복귀 과정을 설명하기 위한 도면이다.

이하에서는 첨부된 도면을 참조하여 본 발명을 상세히 설명한다.

도 1은 본 발명에 따른 이동 로봇의 위치 추정 방법을 설명하기 위한 제어 흐름도이다.

도 1을 참조하여 설명하면, 이동 로봇에 설치된 레인지 센서의 스캔에 따라 스캔 데이터가 획득된다(S10). 여기서, 본 발명에 따른 레인지 센서는 레이저 레인지 센서 형태로 마련되며, 각 해상도(Angular resolution)가 1ㅀ로, 180ㅀ의 범위를 1ㅀ단위로 스캔하는 것을 예로 한다.

레인지 센서에 의해 스캔 데이터가 획득되면, 획득된 스캔 데이터를 이용하여 매칭 에러를 산출한다(S11). 여기서, 본 발명에서는 스캔 데이터와, 기 설정된 환경 지도에 기초하여 예측되는 예측 데이터에 기초하여 매칭 에러가 산출되는 것을 예로 한다.

도 2를 참조하여 보다 구체적으로 설명하면, 스캔 데이터에 기초하여 산출되는 스캔 범위 영역과, 예측 데이터에 기초하여 산출되는 예측 범위 영역 간의 편차에 기초하여 매칭 에러가 산출된다.

즉, 본 발명에 따른 이동 로봇의 위치 추정 방법에 적용되는 관측 우도 모델(Observation likelihood model)의 매칭 에러는 스캔 데이터와 예측 데이터 자체의 차이가 아닌, 스캔 데이터, 즉 스캔된 거리 데이터에 의해 산출되는 스캔 범위 영역과 예측 데이터에 의해 산출되는 예측 범위 영역 간의 편차를 이용하게 된다. 여기서, 도 2를 참조하여 설명하면, 본 발명에 따른 매칭 에러는 [수학식 1]에 의해 산출되는 것을 예로 한다.

[수학식 1]

여기서, Em(x)는 매칭 에러이고,

는 시간 t에서의 j번째 스캔 데이터이고,

는 시간 t에서의 j번째 예측 데이터이다. 그리고,

는 시간 t에서의 j번째 상기 스캔 범위 영역이고,

는 시간 t에서의 j번째 상기 예측 범위 영역이고, Δθ는 레인지 센서의 각 해상도(Angular resolution)이다. 그리고, 본 발명에 따른 이동 로봇의 위치 추정 방법에서의 예측 데이터는 레이-캐스팅 알고리즘(Ray-casting algorithm)을 통해 환경 지도로부터 계산되는 것을 예로 한다.

[수학식 1]의 식 (4)가 매칭 에러를 정의한다. 여기서, [수학식 4]의 분모는 정규화(Normalization)을 수행한다. 여기서, 정규화는 매칭 에러가 임의의 확률로 표현되는 숫자가 아닌 % 오차로 표현되는 것을 의미하며, 이를 통해 사용자가 매칭 에러를 직관적인 의미로 인식 가능하게 된다.

또한, 정규화는 스캔 범위 영역과 예측 범위 영역의 편차, 즉 면적의 편차를 이용하여 매칭 에러를 산출함으로서, 센서 데이터의 부분적인 손상, 예를 들어 인간과 같이 환경 지도에 맵핑되지 않은 장애물에 의해 발생하는 센서 데이터의 부분적인 손상에도 강인함을 의미한다. 따라서, 종래의 매칭 에러가 센서 데이터와 예측 데이터에 대해 개별적으로 산출됨에 따라, 손상된 센서 데이터를 제거하기 위한 추가적인 필터링 기술을 적용해여야 하는 문제점을 해소할 수 있다.

도 3은 본 발명에 따른 이동 로봇의 위치 추정 방법의 매칭 에러 분포를 시뮬레이션한 예를 도시하고 있다. 도 3에서는 실제 이동 로봇의 포즈가 환경 지도의 (101,101)에 위치할 때의 매칭 에러의 분포를 시뮬레이션한 예을 도시하고 있다. 여기서, 도 3에서는 환경 지도가 정사각형이고, 그리드 맵(Grid map)을 사용하는 것을 예로 하고 있다. 그리고, 그리드 맵의 정사각형 경계는 검은 점으로 표시되어 있다.

도 3의 (a)는 장애물이 존재하지 않은 상태에서의 시뮬레이션을 도시한 것이고, 도 3의 (b)는 검은 블록으로 표시된 4개의 장애물이 존재하는 상태에서의 시뮬레이션을 도시하고 있다. 도 3(a)에 도시된 바와 같이, 실제 이동 로봇의 포즈, 즉 (101,101) 위치에서 매칭 에러가 최소가 되고, 매칭 에러의 경계면이 이동 로봇의 포즈 에러에 따라 서서히 증가함을 확인할 수 있다.

도 3의 (b)에 도시된 바와 같이, 4개의 장애물이 존재하더라도 매칭 에러의 경계면의 전체적인 형상이, 장애물에 의해 센서 데이터의 손상이 발생하더라도 많이 변하지 않음을 확인할 수 있다. 즉, 본 발명에 따른 이동 로봇의 위치 추정 방법의 매칭 에러가 센서 데이터의 부분적인 손상에도 강인함을 확인할 수 있다.

도 4는 방향 에러(Orientation error), 즉 이동 로봇의 주시 방향(Heading direction)의 오차가 존재할 때의 매칭 에러를 나타낸 도면이다. 여기서, 이동 로봇의 실제 각도는 0ㅀ로 설정된 상태이다.

도 4에서 실선으로 나타낸 그래프가 도 3의 (a)에서와 같이 장애물이 존재하지 않은 상태에서의 매칭 에러이고, 점선으로 나타낸 그래프가 도 3의 (b)에서와 같이 장애물이 존재하는 상태에서의 매칭 에러이다. 도 4를 통해 본 발명에 따른 매칭 에러가 이동 로봇의 실제 각도에서 최소가 되는 것을 확인할 수 있으며, 이를 통해 본 발명에 따른 이동 로봇의 위치 추정 방법의 매칭 에러가 이동 로봇의 위치나 주시 방향과 같은 모든 케이스에서 이상적인 수렴 특성을 나타내는 것을 확인할 수 있다.

다시, 도 1을 참조하여 설명하면, 상기와 같은 방법을 통해 이동 로봇의 주행 중에 레인지 센서로부터의 스캔 데이터를 이용하여 매칭 에러가 산출되면, 산출된 매칭 에러가 에러 문턱치를 초과하는지 여부를 판단한다(S13). 여기서, 매칭 에러가 에러 문턱치를 초과하는 것으로 판단되는 경우에는 위치 추정 실패로 인식하게 되고, 매칭 에러가 에러 문턱치를 초과하지 않는 것으로 판단되는 경우에는 위치 추정 성공으로 인식하게 된다.

여기서, 본 발명에 따른 이동 로봇의 위치 추정 방법에서는 매칭 에러가 에러 문턱치를 초과하는지 여부를 판단하기 전에 S11 단계에서 산출된 매칭 에러에 대해 미디언 필터(Median filter)가 적용되는 것을 예로 한다.

매칭 에러는 짧은 시간 간격 동안에 에러 문턱치보다 크게 나타날 수 있다. 이에, 본 발명에서는 짧은 순간의 이상치(short-time outlier value)의 제거를 위해 미디언 필터를 사용한다. 미디언 필터는 데이터가 n surrounding point의 미디언 값으로 대체하는 것에 의해 이상치를 제거하게 되며, 본 발명에서는 n값으로 15를 설정하는 것을 예로 한다.

한편, 본 발명에 따른 이동 로봇의 위치 추정 방법의 에러 문턱치는 레인지 센서의 이전 스캔 동작들을 통해 상술한 바와 같이 산출된 매칭 에러의 통계값에 기초하여 업데이트된다. 즉, 에러 문턱치는 고정된 값이 아닌 레인지 센서의 이전 스캔 동작 과정에서 산출된 매칭 에러를 이용하여 지속적으로 업데이트된다.

도 5는 이동 로봇에 MCL이 적용된 생태에서, MCL이 11,000 스캔 과정을 수행하는 동안 실험적으로 측정된 매칭 에러의 히스토리이다. 도 5에 도시된 매칭 에러는 이동 로봇이 전형적인 오피스 빌딩을 주행하는 환경에 대해 측정된 것으로, 다양한 에러 원인에 의해 매칭 에러가 0이 아님을 확인할 있다. 즉, 매칭 에러는 환경 지도의 사이즈, 매핑되지 않은 장애물이나 센서 정밀도 등에 의해 발생할 수 있다. 따라서, 본 발명에서는 이와 같이 매칭 에러에 영향을 미치는 요소가 반영될 수 있도록 이전 스캔 동작 과정에서 산출된 매칭 에러를 이용하여 에러 문턱치를 업데이트하는 것을 예로 한다.

여기서, 본 발명에 따른 이동 로봇의 위치 추정 방법에서는 에러 문턱치가 매칭 에러의 평균값과 표준편차를 이용하는 것을 예로 하며, 이는 [수학식 2]와 같이 정의될 수 있다.

[수학식 2]

여기서, h는 에러 문턱치이고,

는 (i-k) 번째 스캔에서 i번째 스캔까지의 매칭 에러의 평균값이고,

는 (i-k) 번째 스캔에서 i번째 스캔까지의 매칭 에러의 표준편차이고, bias는 환경 지도의 그리드 해상도에 기초하여 결정되는 에러 기준치이다.

그리고, 본 발명에 따른 이동 로봇의 위치 추정 방법의 에러 문턱치의 산출에 적용되는 매칭 에러는 이전 스캔 과정에서 위치 추정 성공으로 판단된 매칭 에러를 사용하게 되며, 이에 따라, 본 발명에 따른 에러 문턱치는 위치 추정 성공으로 판단된 매칭 에러의 상위 한계로 정의할 수 있다.

여기서, [수학식 2]는 가우시안 확률과

테스트를 이용한 Hypothesis testing에 기초한 슬라이딩 윈도우 기법(Sliding window method)을 적용한 것으로, Hypothesis testing을 간소화시켜 나타내고 있다. 즉, 본 발명에서는 기존의 Hypothesis testing에 기초한 슬라이딩 윈도우 기법(Sliding window method)에서

함수가 갖는 계산의 복잡성을 제거하기 위해 에러 문턱치의 계산에 [수학식 8]과 같이, 슬라이딩 윈도우 기법(Sliding window method)을 간소화시켰다. 여기서, 슬라이딩 윈도우 사이즈 k는 여러 실험으로부터 경험적으로 결정될 수 있으며, 본 발명에서는 슬라이딩 윈도우 사이즈 k를 100초를 기준으로 하여 500으로 설정하는 것을 예로 한다.

또한, [수학식 2]에서의 bias는 가우시안 확률의 상위 경계(Upper bound)를 나타내는데, 상술한 바와 같이, 환경 지도의 그리드 해상도에 기초하여 결정된다. 예를 들어, 환경 지도의 그리드 해상도가 10cm인 경우 bias 값으로 3%로 결정될 수 있다.

여기서, bias는 매칭 에러의 평균값 및 표준편차가 극단적으로 0인 경우에도 에러 문턱치가 bias의 크기로 존재하는 것을 의미하게 되며, 매칭 에러가 bias 만큼 존재하더라도, 이는 완경지도의 그리드 해상도에 따른 오차 범위 내에 속하기 때문에 위치 추정 실패나 위치 추정 성공의 판단에 영향을 미치지 않기 때문이다. 이와 같이, 환경 지도의 그리드 해상도가 bias를 통해 에러 문턱치에 반영됨으로써, 환경 지도의 그리드 해상도에 의해 발생 가능한 매칭 에러가 위치 추정 성공이나 실패를 결정하는데 미치는 영향을 제거할 수 있게 된다.

다시, 도 1을 참조하여 설명하면, 상기와 같이 업데이트되는 에러 문턱치에 기초하여, S13 단계에서 이동 로봇의 현재 위치 추정이 위치 추정 실패인지 위치 추정 성공인지 여부를 판단하게 된다.

여기서, 위치 추정 성공으로 판단되는 경우, 즉 현재 스텝에서의 매칭 에러가 에러 문턱치 이하인 경우, 현재 스캔 단계에서 산출된 매칭 에러와, [수학식 2]에서와 같이, 슬라이딩 윈도우 사이즈인 k번째 이전까지의 매칭 에러를 이용하여 평균값과 표준편차를 산출하여(S14), 에러 문턱치를 업데이트한다(S15).

한편, S12 단계에서 매칭 에러가 에러 문턱치를 초과하여 위치 추정 실패로 판단되는 경우, 환경 지도 상의 적어도 일 영역으로부터 복수의 위치 샘플을 추출한다(S16). 여기서, 위치 샘플은 환경 지도 상에서 이동 로봇이 위치하는 것으로 추정되는 위치들에 대한 샘플에 해당하며, 본 발명에서는 기 등록된 모션 모델에 기초한 최대 모션 경계 영역 내에서 위치 샘플이 추출되는 것을 예로 한다.

도 6을 참조하여 보다 구체적으로 설명하면, 이동 로봇의 위치 추정이 실패로 판단된 후, 도 6에 도시된 바와 같이, 원 형태의 최대 모션 경계 영역(Maximum Motion Boundary)이 설정된다. 이동 로봇이 시간 t₀에서 경로 1(reference path)을 추종하여 주행을 시작하는 것으로 가정하고, 시간 t₀에서는 위치 추정 성공 상태인 것으로 가정한다. 그리고, 이동 로봇이 주행하는 동안, 시간 t₁에서 이동 로봇의 좌측 휠이 미끄러져 이동 로봇이 경로 2(real path)를 따라 이동한 것으로 가정한다.

이 때, 이동 로봇은 시간 t₃에서 위치 추정 실패로 인식한다. 실제로 경로 1(reference path)에서 벗어나는 시간 t₁과 이를 감지한 시간 t₃ 사이의 차이는 본 발명에 따른 이동 로봇의 위치 추정 방법의 진행 사이클 타임과 레인지 센서의 센싱 사이클 타임 간의 편차에 의해서 발생할 수 있다.

본 발명에 따른 최대 모션 경계 영역(Maximum Motion Boundary)은 위치 추정 실패로 판단된 시간 t₃의 직전의 위치 추정 성공 위치를 중심으로 모션 모델에 기초하여 산출되는 최대 이동 거리(S_max)를 반경으로 하는 원 형태로 설정된다. 여기서, 최대 모션 경계 영역(Maximum Motion Boundary)은 이동 로봇이 이동 가능한 모든 방향에서 이동 로봇이 시간 t₀에서 t₃ 동안 이동 가능한 거리를 가정하여 계산된다.

본 발명에 따른 모션 모델은 가우시안 확률 분포를 갖는 모션 모델이 적용되는 것을 예로 하며, 최대 모션 경계 영역(Maximum Motion Boundary)의 산출을 위한 최대 이동 거리(S_max)는 [수학식 3]을 통해 산출될 수 있다.

[수학식 3]

여기서, S_max는 최대 이동 거리이고, σ는 모션 모델, 즉 가우시안 확률 분포를 갖는 모션 모델의 표준 편차이고, Δs_i는 이동 로봇에 설치된 휠 엔코더로부터 측정된 이동 거리이다.

이와 같이, 이동 로봇이 위치 추정 실패로 판단된 상태, 즉 이동 로봇의 현재 위치를 알지 못하는 상태에서, 이동 로봇의 실제 위치를 추정하기 위한 위치 샘플을 환경 지도의 전체 영역이 아닌 최대 모션 경계 영역(Maximum Motion Boundary) 내에서 추출함으로써, 전역 위치 추정(Global localization) 기법을 이용한 위치 추정보다 위치 추정에 필요한 계산량을 현저히 감소시킬 수 있게 된다.

상기와 같이 설정된 최대 모션 경계 영역(Maximum Motion Boundary) 내에서 복수의 위치 샘플이 추출되면(S16), 각 위치 샘플에 이동 로봇이 위치하는 것으로 가정하여 매칭 에러를 산출한다(S17). 여기서, 매칭 에러는 상술한 바와 같이, 본 발명에 따른 이동 로봇의 위치 추정 방법의 관측 오도 모델(Observation likelihood model)의 매칭 에러의 산출 방법에 따라 산출되며, [수학식 1]에서와 같이 산출되는 것을 예로 한다.

그런 다음, 산출된 매칭 에러를 기 설정된 확률 밀도 함수(Probability density function)에 적용하여 이동 로봇의 실제 위치를 추정하게 된다. 여기서, 본 발명에 따른 이동 로봇의 위치 추정 방법에서는 상술한 바와 같이 추출된 위치 샘플들을 본 발명에 따른 위치 추정 방법의 관측 우도 모델(Observation likelihood model)의 확률 밀도 함수(Probability density function), 즉 확률 업데이트 룰(Probability update rule)에 적용하여 이동 로봇의 실제 위치를 추정하게 된다.

도 1을 참조하여 보다 구체적으로 설명하면, 각 위치 샘플에 대해 산출된 매칭 에러를 확률 밀도 함수(Probability density function)에 적용하여 각 위치 샘플에 대한 추정 확률을 산출한다(S18). 그리고, 산출된 추정 확률에 기초하여 위치 샘플 중 후보 샘플을 추출한다(S19).

여기서, 본 발명에 따른 이동 로봇의 위치 추정 방법에서는 확률 밀도 함수(Probability density function)로 포화 가우시안 함수(Saturated Gaussian function)가 적용되는 것을 예로 하며, [수학식 4]와 같이 표현될 수 있다.

[수학식 4]

여기서, p(Em(x))는 위치 샘플의 추정 확률이고, η는 노르말라이저(Normalizer)이다. 그리고, σ_t는 시간 t에서 위치 샘플에 대한 매칭 에러의 표준편차이고, μ_t는 시간 t에서 위치 샘플에 대한 매칭 에러의 평균값이다. 그리고, bias는 환경 지도의 그리드 해상도에 기초하여 결정되는 에러 기준치로 [수학식 2]의 bias와 동일하게 설정된다. 이와 같이, 위치 샘플의 통계적 데이터, 즉 각 위치 샘플에 대한 매칭 에러의 평균값과 표준편차를 이용함으로써, 수렴 속도(Convergence speed)의 조절이 가능하게 된다.

[수학식 4]의 식 (1)은 확률의 포화 영역(Saturation region of probability)을 나타낸다. 여기서, bias, 즉 에러 기준치는 매칭 에러가 에러 기준치보다 작으면 확률이 포화되는 것을 의미하며, 본 발명에 따른 이동 로봇의 위치 추정 방법의 관측 우도 모델(Observation likelihood model)의 수렴 한계(convergence limit)를 의미하게 된다. 즉, 매칭 에러가 에러 기준치보다 작은 경우에는 [수학식 4]의 식 (2)에 나타낸 가우시한 확률 함수의 최대값과 동일한 추정 확률을 갖도록 한다.

그리고, [수학식 4]의 식 (3)은 매칭 에러가

보다 큰 경우를 나타낸 것으로, 이는 수렴 영역이 전체 확률 분포 영역의 99.7%를 차지하는 것을 의미한다. 그리고, [수학식 4]의 식 (2)는 가우시안 확률 함수를 나타낸다.

도 7의 (a)는 Beam model(Thrun 등은 논문 "Probabilistic Robotics", The MIT Press, 2005, pp.153-169.)의 확률 분포를 도시한 도면이고, 도 7의 (b)는 본 발명에 따른 이동 로봇의 위치 추정 방법에 따른 확률 분포를 도시한 도면이다. 도 7의 (a)와 (b)는 동일한 환경 조건 하에서 시뮬레이션된 그래프를 도시하고 있다.

일반적으로 연속 분포(Continuous distribution)가 불연속 분포(Discontinuous distribution)보다 강인한 것으로 알려져 있으며, 도 7의 (a)에서는 확률 분포가 실제 위치 주변에서 지역적으로 불연속적이라는 것을 확인할 수 있고, 위치 에러가 20cm보다 크다는 것을 확인할 수 있다. 이는 Beam model이 센서 노이즈를 처리하기 위해 많은 수의 위치 샘플을 필요로 한다는 것을 의미하며, 본 발명에 따른 이동 로봇의 위치 추정 방법에 따른 확률 분포가 도 7의 (b)에 도시된 바와 같이, 실제 위치 주변에서 스무드(smooth)하여 보다 효과적임을 확인할 수 있다.

다시, 도 1을 참조하여 설명하면, 상기와 같은 과정을 통해 각 위치 샘플에 대한 추정 확률이 산출되면, 추정 확률에 기초하여 후보 샘플을 추출하는(S19) 리샘플링(Re-sampling) 과정을 수행하게 된다. 그리고, 추출된 후보 샘플들에 대한 매칭 에러를 산출하고(S20), 산출된 매칭 에러를 상술한 바와 같이, 확률 밀도 함수에 적용하여 추정 확률을 산출한다(S21).

여기서, S19 단계 내지 S20 단계를 반복적으로 수행하는 과정에서, 확률 분포가 하나의 수렴 위치로 수렴되는지 여부를 판단하여(S22), 수렴 위치로 수렵하는 경우 해당 수렴 위치를 이동 로봇의 현재 위치로 판단하게 된다(S21).

이하에서는 본 발명에 따른 이동 로봇의 위치 추정 방법을 적용한 이동 로봇의 주행 결과에 대해 설명한다. 이동 로봇에는 각 해상도 1ㅀ로 180ㅀ를 스캔하는 레이저 레인지 센서가 설치되며, 레이저 레인지 센서의 최대 스캔 범위는 9m로 설정되었다.

도 8 및 도 9는 본 발명에 따른 이동 로봇의 위치 추정 방법의 매칭 에러를 이용한 위치 추정 결과를 도시한 도면이다. 도 8 및 도 9의 좌측에는 매칭 에러의 등고선이 도시되어 있고, 우측에는 확률 분포가 도시되어 있다. 도 8의 (a)는 위치 샘플이 랜덤하게 분포된 상태의 첫 번째 샘플링 결과를 도시한 도면이다. 그리고, 상술한 바와 같이 확률 업데이트 룰에 따라 업데이트된 후, 도 8의 (b)에 도시된 바와 같이 매칭 에러가 60%보다 작은 영역으로 위치 샘플이 수렴되었다.

그리고, 3번의 업데이트 후에, 도 9의 (a)에 도시된 바와 같이, 위치 샘플이 10% 영역으로 수렴하는 것을 확인할 수 있다. 그리고, 업데이트의 반복을 통해 위치 샘플이, 도 9의 (b)에 도시된 바와 같이, 실제 로봇 포즈로 수렴하는 것을 확인할 수 있다. 여기서, 도 8 및 도 9의 σ 값은 위치 샘플들에 대해 산출된 매칭 에러의 표준 편차이다.

한편, 도 10은 이동 로봇의 200초 동안 실험 환경을 이동할 때 측정된 매칭 에러와 에러 문턱치를 나타낸 그래프이다. 도 10의 (a)는 매칭 에러에 미디언 필터가 적용되지 않은 상태이고, 도 10의 (b)는 본 발명에 따른 이동 로봇의 위치 추정 방법에 따라 미디언 필터가 적용된 상태이다.

도 10의 (a)에 도시된 바와 같이, 에러 문턱치 h를 초과하는 매칭 에러가 붉은색 원으로 표시되어 있으며, 위치 추정 실패가 6회 발생하였다. 반면, 본 발명에 따른 이동 로봇의 위치 추정 방법에서는 통상적인 주행 상태, 즉 매핑되지 않는 장애물이 존재하지 않는 상태에서의 주행에서는 위치 추정 실패로의 전환 없이 주행되는 것을 확인할 수 있다.

한편, 도 11은 이동 로봇이 붉은 점으로 표시된 위치에 위치한 상태에서 환경 지도와 레인지 센서에 의해 스캔된 스캔 데이터를 오버랩하여 도시한 도면이다. 도 11의 (a) 및 (b)는 이동 로봇에서 휠 미끄러짐이 발생하여 위치 추정 실패가 발생하는 경우의 환경 지도와 레인지 센서에 의해 스캔된 스캔 데이터를 오버랩하여 도시한 도면이다. 그리고, 도 12는 상기와 같은 상황에서의 매칭 에러와 에러 문턱치를 나타낸 그래프이다. 휠 미끄러짐에 의해 870초 부분에서 이동 로봇의 위치 추정이 실패되었음을 나타내고 있다.

이 때, 본 발명에 따른 이동 로봇의 위치 추정 방법은 870s 이후에 이동 로봇의 실제 위치를 추정하게 되며, 상술한 바와 같이, 최대 모션 경계 영역 내에서 위치 샘플을 추출하여 이동 로봇의 실제 위치를 추정하게 된다. 도 11의 (c)에 도시된 바와 같이, 최대 모션 경계 영역은 좌표 (2, 17)에서 미끄러짐 이후에 도달 가능한 영역에 걸쳐 퍼지게 된다. 여기서, 위치 추정은, 도 12에 도시된 바와 같이, 대략 20s 후에 위치 추정 실패로부터 복귀(도 11의 (d) 참조)되는 것을 확인할 수 있다.

여기서, 전체 환경 지도 상의 영역이 1539m²라 가정하는 경우, 계산 비용은 위치 샘플의 개수에 비례하게 된다. 따라서, 전역 위치 추정 기법을 적용하는 경우의 위치 샘플의 사이즈는 대략 5,000 ~ 10,000개가 된다. 반면, 본 발명에 따른 이동 로봇의 위치 추정 방법을 적용하는 경우, 휠 미끄러짐에 의한 위치 추정 실패 상황에서의 최대 모션 경계 영역이 대략 2.5m²으로 설정되어 위치 샘플의 사이즈가 대략 300개로 감소되었으며, 이는 본 발명이 계산 비용 측면에서도 전역 위치 추정 기법에 비해 매우 효과적임을 알 수 있다.

비록 본 발명의 몇몇 실시예들이 도시되고 설명되었지만, 본 발명이 속하는 기술분야의 통상의 지식을 가진 당업자라면 본 발명의 원칙이나 정신에서 벗어나지 않으면서 본 실시예를 변형할 수 있음을 알 수 있을 것이다. 별명의 범위는 첨부된 청구항과 그 균등물에 의해 정해질 것이다.

Claims

이동 로봇의 위치 추정 방법에 있어서,
(a) 레인지 센서의 스캔에 따라 스캔 데이터가 획득되는 단계와;
(b) 상기 스캔 데이터에 기초한 스캔 범위 영역과, 기 등록된 환경 지도로부터 예측되는 예측 데이터에 기초한 예측 범위 영역 간의 편차에 기초하여 매칭 에러를 산출하는 단계와;
(c) 상기 (b) 단계에서 산출된 상기 매칭 에러가 에러 문턱치를 초과하는지 여부에 따라 위치 추정 실패 여부를 판단하는 단계와;
(d) 상기 (c) 단계에서 위치 추정 실패로 판단된 경우, 상기 환경 지도 상의 적어도 일 영역으로부터 추출된 복수의 위치 샘플 각각에 대해 매칭 에러를 산출하는 단계와;
(e) 상기 (d) 단계에서 산출된 상기 매칭 에러를 기 설정된 확률 밀도 함수에 적용하여 상기 이동 로봇의 위치를 추정하는 단계를 포함하며,
상기 매칭 에러는 수학식

(여기서, Em(x)는 상기 매칭 에러이고,
는 시간 t에서의 j번째 상기 스캔 데이터이고,
는 시간 t에서의 j번째 상기 예측 데이터이고,
는 시간 t에서의 j번째 상기 스캔 범위 영역이고,
는 시간 t에서의 j번째 상기 예측 범위 영역이고, Δθ는 상기 레인지 센서의 각 해상도(Angular resolution)이다)에 의해 산출되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
제1항에 있어서,
상기 (d) 단계에서 상기 복수의 위치 샘플은 기 등록된 모션 모델에 기초한 최대 모션 경계 영역 내에서 추출되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
이동 로봇의 위치 추정 방법에 있어서,
(a) 레인지 센서의 스캔에 따라 스캔 데이터가 획득되는 단계와;
(b) 상기 스캔 데이터와, 기 설정된 환경 지도에 기초하여 예측되는 예측 데이터에 기초하여 매칭 에러를 산출하는 단계와;
(c) 상기 (b) 단계에서 산출된 상기 매칭 에러가 에러 문턱치를 초과하는지 여부에 따라 위치 추정 실패 여부를 판단하는 단계와;
(d) 상기 (c) 단계에서 위치 추정 실패로 판단된 경우, 기 등록된 모션 모델에 기초한 최대 모션 경계 영역 내에서 추출되는 복수의 위치 샘플 각각에 대해 매칭 에러를 산출하는 단계와;
(e) 상기 (d) 단계에서 산출된 상기 매칭 에러를 기 설정된 확률 밀도 함수에 적용하여 상기 이동 로봇의 위치를 추정하는 단계를 포함하고,
상기 (b) 단계는,
상기 스캔 데이터에 기초하여 스캔 범위 영역을 산출하는 단계와;
상기 예측 데이터에 기초하여 예측 범위 영역을 산출하는 단계와;
상기 스캔 범위 영역과 상기 예측 범위 영역 간의 편차에 기초하여 상기 매칭 에러를 산출하는 단계를 포함하며,
상기 매칭 에러는 수학식

(여기서, Em(x)는 상기 매칭 에러이고,
는 시간 t에서의 j번째 상기 스캔 데이터이고,
는 시간 t에서의 j번째 상기 예측 데이터이고,
는 시간 t에서의 j번째 상기 스캔 범위 영역이고,
는 시간 t에서의 j번째 상기 예측 범위 영역이고, Δθ는 상기 레인지 센서의 각 해상도(Angular resolution)이다)에 의해 산출되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
삭제
삭제
제2항 또는 제3항에 있어서,
상기 (b) 단계에서 상기 예측 데이터는 레이-캐스팅 알고리즘(Ray-casting algorithm)을 통해 상기 환경 지도로부터 계산되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
제2항 또는 제3항에 있어서,
상기 에러 문턱치는 상기 레인지 센서의 이전 스캔 동작들에 대한 상기 (b) 단계의 수행을 통해 산출된 매칭 에러의 통계값에 기초하여 업데이트되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
제7항에 있어서,
상기 에러 문턱치에는 상기 환경 지도의 그리드 해상도에 기초하여 결정되는 에러 기준치가 오차 범위로 반영되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
제8항에 있어서,
상기 에러 문턱치는 수학식

(여기서, h는 상기 에러 문턱치이고,
는 (i-k) 번째 스캔에서 i번째 스캔까지의 상기 매칭 에러의 평균값이고,
는 (i-k) 번째 스캔에서 i번째 스캔까지의 상기 매칭 에러의 표준편차이고, bias는 상기 환경 지도의 그리드 해상도에 기초하여 결정되는 에러 기준치이다)에 의해 산출되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
제2항 또는 제3항에 있어서,
상기 (b) 단계에서 산출된 매칭 에러는 미디언 필터(Median filter)에 의해 필터링되어 상기 (c) 단계에 반영되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
제2항 또는 제3항에 있어서,
상기 모션 모델은 가우시안 확률 분포를 갖는 모션 모델이 적용되며;
상기 최대 모션 경계 영역은 상기 (c) 단계의 수행을 통한 직전 위치 추정 성공 위치를 중심으로 상기 모션 모델에 기초하여 산출되는 최대 이동 거리를 반경으로 하는 원 형태로 설정되는 것을 특징으로 이동 로봇의 위치 추정 방법.
제11항에 있어서,
상기 최대 이동 거리는 수학식

(여기서, S_max는 상기 최대 이동 거리이고, σ는 상기 모션 모델의 표준 편차이고, Δs_i는 상기 이동 로봇의 휠 엔코더로부터 측정된 이동 거리이다)에 의해 산출되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
제2항 또는 제3항에 있어서,
상기 (e) 단계는,
(e1) 상기 (d) 단계에서 산출된 상기 매칭 에러를 상기 확률 밀도 함수에 적용하여 상기 각 위치 샘플에 대한 추정 확률을 산출하는 단계와;
(e2) 상기 산출된 추정 확률에 기초하여 후보 샘플을 추출하는 단계와;
(e3) 상기 추출된 후보 샘플에 대한 매칭 에러를 산출하는 단계와;
(e4) 상기 (e3) 단계에서 산출된 상기 매칭 에러를 상기 확률 밀도 함수에 적용하여 상기 각 후보 샘플에 대한 추정 확률을 산출하는 단계와;
(e4) 상기 (e2) 단계, 상기 (e3) 단계 및 상기 (e4) 단계의 반복적인 수행을 통해 수렴되는 수렴 위치를 상기 이동 로봇의 위치로 추정하는 단계를 포함하는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.
제13항에 있어서,
상기 확률 밀도 함수는 포화 가우시안 함수(Saturated Gaussian function)가 적용되며, 수학식

(여기서, p(E_m(x))는 상기 위치 샘플 또는 상기 후보 샘플의 추정 확률이고, η는 노르말라이저(Normalizer)이고, σ_t는 시간 t에서 상기 위치 샘플 또는 상기 후보 샘플에 대한 상기 매칭 에러의 표준편차이고, μ_t는 시간 t에서 상기 위치 샘플 또는 상기 후보 샘플에 대한 상기 매칭 에러의 평균값이고, bias는 상기 환경 지도의 그리드 해상도에 기초하여 결정되는 에러 기준치이다)로 표현되는 것을 특징으로 하는 이동 로봇의 위치 추정 방법.