Result Representation of Rao-Blackwellized Particle Filter for Mobile Robot SLAM

Rao-Blackwellized 파티클 필터를 이용한 이동로봇의 위치 및 환경 인식 결과 도출

Result Representation of Rao-Blackwellized Particle Filter for Mobile Robot SLAM

곽 노 산

¹

, 이 범 희

²

, YOKOI Kazuhito

³

Nosan Kwak

¹

, Beom-Hee Lee

²

, Kazuhito Yokoi

³

Abstract Recently, simultaneous localization and mapping (SLAM) approaches employing Rao- Blackwellized particle filter (RBPF) have shown good results. However, no research is conducted to analyze the result representation of SLAM using RBPF (RBPF-SLAM) when particle diversity is preserved. After finishing the particle filtering, the results such as a map and a path are stored in the separate particles. Thus, we propose several result representations and provide the analysis of the representations. For the analysis, estimation errors and their variances, and consistency of RBPF-SLAM are dealt in this study. According to the simulation results, combining data of each particle provides the better result with high probability than using just data of a particle such as the highest weighted particle representation.

Rao-Blackwellized Particle Filter, SLAM, Mobile Robot, Particle Diversity

1. 서 론

최근, 파티클 필터(Particle filter)는 로봇분야에서 다양 하게 이용되고 있다. 그 중에서, 로봇의 위치(pose) 및 환경맵(map)을 동시에 추정하는 SLAM 문제를 해결하 기 위해 많은 연구가 진행되어 오고 있다. SLAM 문제 는 로봇의 위치와 로봇 주변 환경을 동시에 추정해야 하는 어려운 문제이다. 로봇의 위치와 환경을 확률적으 로 추정하고자, 최근 Rao-Blackwellized 파티클 필터 (RBPF)^[1,2]가 확장 칼만 필터(Extended Kalman Filter, EKF) 보다 주로 사용되고 있다. 그 이유는 RBPF가 가진 두 개의 큰 장점 때문인데^[3], 첫 째, 기존의 EKF를 이용한 SLAM (EKF-SLAM)의 복잡도는 특징점(feature)의 수의 제곱에 비례하는데, RBPF를 이용한 SLAM (RBPF-

SLAM)은 복잡도가 특징점 개수의 선형으로 증가한다.

두 번째 장점은, 강인한 다중 측정 데이터 연관(data association) 인데, 이것은 EKF-SLAM이 하나의 추정치만 을 저장하는 것과 달리, 파티클 각각 다른 추정치를 저 장함으로써, 추정치간의 보완이 가능하기 때문이다.

하지만, RBPF-SLAM의 단점은 파티클의 다양성 손실 로 인한 추정 성능 저하이다. RBPF-SLAM에서는 파티 클들이 재귀적 알고리즘에 의해 로봇의 위치 및 환경을 동시에 추정하는데, 알고리즘의 마지막 단계인 재추출 과정에서 파티클의 복사 혹은 제거가 발생한다. 이 때, 제거된 파티클이 가지고 있던 정보는 모두 사라지고, 결국 특정 파티클이 파티클 집합을 장악하게 된다. 이 것이 파티클의 다양성 손실 문제인데, 파티클의 다양성 을 잃음으로써, RBPF-SLAM의 장점인 강인한 측정 데 이터 연관을 수행 할 수 없게 된다^[4]. 이것은 파티클 개 수가 초기 개수와 같지만, 내부적으로 파티클의 추정 정보를 살펴봤을 때, 실제적으로는 극소수의 파티클 정 보가 다른 파티클에 복사가 된 것을 확인할 수 있다.

우리는 이 파티클 손실 문제를 해결하고자 기존의 재 추출 방법을 사용하지 않고, 파티클의 가중치를 이용한

※ 본 연구는 일본 학술 진흥회(JSPS)의 Grant-in-for JSPS Postdoctoral Fellowship for Foreign Researchers, 서울대학교 BK21, 서울대학교 지 능로봇연구실의 KOSEF, NRL Program (no. R0A-2008-000-20004-0)을 통한 연구비 지원으로 수행되었으며, [10]의 연구내용을 확장한 것 이다

1 일본 산업총합기술연구원(AIST) JSPS Postdoctoral Fellow

2 서울대학교 전기.컴퓨터공학부 교수

3 일본 산업총합기술연구원(AIST) 자율행동제어 Group Leader

보정 방법(Compensation Technique)을 제안하였다^[5]. 이방 법은 파티클의 정보 보정을 통해, 파티클의 다양성을 유지하였고, SLAM의 추정오차를 줄일 수 있었다. 그렇 지만, SLAM 과정을 마쳤을 때 각각의 파티클은 다양한 정보를 가지고 있게 되는데, SLAM의 수행 결과를 보여 주기 위한 방법이 요구된다. 기존의 대부분의 연구자들 은 SLAM 수행 결과로써, 가중치가 가장 큰 파티클의 정보, 즉 로봇의 경로 및 환경맵으로 나타내었다^[2,6]. 하 지만, 실제적으로 위와 같은 결과 도출 방법은 항상 최 상의 결과를 도출할 수 없다. 더욱이 많은 연구자들은 RBPF-SLAM의 결과 도출 문제를 간과하였다^[3,4,7]. 따라 서, 본 논문에서는 RBPF-SLAM의 결과를 도출하기 위 한 여러 방법들을 제안하는데, 그것은 첫째, 최대 가중 치를 이용하는 방법, 둘째, 파티클 분포의 기하정보를 이용하는 파티클 트리(Particle Tree)의 루트(root) 파티클 을 이용하는 방법, 셋째, 파티클 집합에 속한 모든 파티 클 정보의 평균을 이용하는 방법, 마지막으로, 파티클 분포의 기하정보를 이용하고, 그 분포의 경계를 파티클 트리의 끝노드(leaf node)의 정보를 이용하는 방법이다.

제안된 여러 결과 도출 방법의 성능 평가 기준으로, RBPF-SLAM의 일관성(consistency), 추정 오차, 오차의 분산을 도입한다.

2장에서는 RBPF-SLAM의 개요와 파티클 다양성에 대해서 기술한다. 3장에서는 결과 도출방법, 4장에서 컴 퓨터 모의 실험을 수행하고, 그 결과를 나타내고, 결과 에 대한 검토를 기술한다. 마지막으로 5장에서는 본 연 구의 의미와 적용 대상에 대해서 언급한다.

2. RBPF-SLAM 및 파티클 다양성

2.1 RBPF-SLAM의 개요

SLAM문제는 로봇이 로봇의 위치와 환경맵을 동시에 추정해야 하는 어려움이 있다. 하지만, RBPF-SLAM은 Rao-Blackwellization^[1,2]을 이용하여, 연관관계 c 를 안_1:t 다고 가정했을 때, (1)과 같이 SLAM 사후 확률(Posterior) 을 로봇 위치 추정 확률부분과 환경맵 추정 확률 부분 으로 인수분해 할 수 있다^[7].

1: 1: 1: 1: 1: 1: 1: 1: 1: 1: 1:

1

( , | , , ) ( | , , )

^F

( | , , )

(1)

N n

t t t t t t t t t t t

n

p x M z u c p x z u c p m x z c

=

= ∏

여기서,

x

_1:t,

z

_1:t ,

u

_1:t^은 초기부터 현재 시간 t까지의 각각 로봇 경로, 센서 측정값, 로봇 제어 입력을 나타낸 다. 그리고, mn은 n번째 특징점(feature)을 나타내고, NF개 의 특징점들이 환경맵 M을 구성한다.

그림 1에 RBPF-SLAM의 재귀적 네 단계, 즉 추출, 특 징점 정보 갱신, 파티클 가중치 계산, 재추출 과정을 두 개의 파티클에 대해서 묘사하였다. 추출 과정은 각각의 파티클이 로봇의 위치를 추정하기 위해 추정 확률 분포 로부터 임의 점을 뽑아내는 것이다. 두 번째 단계는 센 서의 측정 데이터를 이용하여 각각의 파티클이 가지고 있는 특징점의 정보를 갱신하는 과정이다. 세 번째 단 계로, 파티클의 성능을 평가하기 위해 시간 t에서 k번째 파티클의 가중치 w^{[ ]}_t^k 를 다음과 같이 실제 확률 분포 (target distribution)과 추정 확률 분포(proposal distribution) 의 비로 구한다:

target distribution [ ]

proposal distribution w t k =

그림 1(c)에서는 파티클 두 개의 가중치를 구하는 것 도식적으로 보여주며, 여기서 각 파티클의 가중치는 정 규화된 값이다. 마지막 단계인 재추출 과정에서는 파티 클의 가중치를 이용하여, 다음 재귀 단계에서 이용될 파티클을 다시 뽑는다. 이 마지막 과정은 재생산 과정 이라고도 불린다. 이 때, 제거된 파티클들이 가지고 있 던 로봇 경로 정보 및 환경맵은 파티클과 같이 사라지 게 된다.

[ ] 1 m

xt−

[ ] 1 n

xt−

[ ] tmp m

x

t

[ ] tmp n

x

t

[ ]

tmp m

xt

[ ] tmp n

xt

Landmark filter

#1 of particle m

Landmark filter

#2 of particle m

Landmark filter

#1 of particle n

Landmark filter

#2 of particle n

(a) 추출 (b) 특징점 정보 갱신

Importance

Weight : ^{0.1 0.8}

Proposal Distribution

Target Distribution

[ ]m

Yt Yt^{[ ]n}

••

•

^• _•^{• •}_•

••

•

• ^•

••

[ Temporary set at time t ]

[ Resampled set at time t ]

•

^•

•

_•

•

Resampling with weights

is replicated three times

is rejected [ ]m

Yt

[ ]n

Yt

[ ]n

Yt

[ ]m

Yt

(c) 파티클 가중치 계산 (d) 재추출 그림 1. RBPF-SLAM의 재귀적 과정

2.2 파티클 다양성

RBPF-SLAM의 장점인 다중 측정 데이터 연관은 파 티클의 다양성에 기인한다. 하지만, RBPF-SLAM의 마지 막 단계인 재추출 과정에서, 제거되는 파티클들이 발생 하고, 장기적으로는 소수의 파티클들이 파티클 집합을 차지하여 다양성을 잃게 되는 문제가 발생한다. 파티클 다양성이 낮아졌을 때, 소수의 파티클에 비교적 큰 오 차가 발생하면, RBPF-SLAM은 더 이상 추정을 제대로 수행할 수가 없게 된다. 파티클의 다양성이 낮아지는 직접적인 원인은 재추출 과정에서 가중치가 낮은 파티 클들은 바로 제거되고, 가중치가 높은 파티클들은 복사 되기 때문이다. 따라서, 우리는 RBPF-SLAM에 일반적 으로 쓰이는 재추출 방법들을 비교 검토하였지만^[5], 파 티클의 다양성을 장기적으로 유지할 수 없었다. 일례로, 여러 재추출 알고리즘에 의한 파티클의 다양성을 측정 하기 위해, 초기의 파티클 집합으로부터 제거되지 않고 남아 있는 파티클의 개수(distinct particles)를 측정한 결과 가 그림 2에 나타나 있다. 그림 2에서, 비교된 재추출 방법은 부분 재추출(Partial Resampling, PR), 체계적 추출 (Systematic Resampling, SR)과 SR을 개선시킨 잉여 체계 적 추출(Residual Systematic Resampling, RSR) 이다. 그림에 는 두 곳의 로봇 경로가 교차하는 loop-closure도 같이 표 시되어 있다. 모든 경우에서 파티클의 다양성이 급격하 게 감소함을 알 수 있다. 첫 번째 loop-closure에서, 초기 100개의 파티클 중에서 실제적으로 파티클 집합에 남아 있는 개수는 단 한 개였고, 나머지는 이 파티클의 복사 본이었다. 따라서, 과거에 우리는 파티클의 다양성을 유 지하고자 재추출 방법을 대신하는 보정 방법을 제안하 였고, 이로 인한 RBPF-SLAM의 성능을 향상 시켰다^[5].

0 500 1000 1500

0 20 40 60 80 100

Time (step)

Number of Distinct Particles (%)

PR SR

RSR Loop-closures

그림 2. 재추출 방법에 따른 파티클 다양성 변화

3. RBPF-SLAM의 결과 도출

3.1 결과 도출에 대한 연구 배경

지금까지는 파티클 다양성의 감소로 인한 문제에 대 해 소개하였다. 하지만, 파티클 다양성이 유지되었을 때, 생각해 볼 수 있는 문제가 있다. 즉, 파티클들이 다양한 정보를 저장하고 있는데, 과연 어떻게 RBPF-SLAM의 결과를 표시할 것인가? 우리가 제안한 보정 방법^[5]을 사 용하여, 파티클 다양성을 유지하며 RBPF-SLAM 수행을 마쳤을 때, 각각의 파티클의 가진 정보가 얼마나 다른 지 표 1에 분산 데이터를 나타내었다.

표 1. 파티클 데이터의 분산 값

로봇 위치 분산 환경맵 분산(평균) x (meter) y (meter) x (meter) y (meter) 분산 0.038 0.067 0.223 0.115 최소값 7.469 6.381 0.009 0.002 최대값 8.545 8.138 0.782 0.242 표 1에 따르면, 로봇 위치에 대한 분산은 비교적 적 으나 환경맵 분산은 매우 큼을 알 수 있다. 일례로, 위 결과를 도출한 모의 실험에서 특정 특징점의 환경맵 분 산은 약 0.8m 였다. 따라서, 그림 3과 같이 우리는 RBPF- SLAM의 결과를 표시하기 위한 방법이 필요하게 된다.

Result Repre- sentation

그림 3. 다양한 파티클 데이터로부터 SLAM 결과도출

대부분의 연구자들은 가장 높은 가중치를 가지는 파 티클의 정보를 이용하여 결과를 도출하였고, 간혹 데이터 의 평균을 사용하여 결과를 도출하였다. 하지만, 파티클 의 다양성이 유지될 때, 결과 도출 문제에 대한 분석이 이루어지지 않았다. 따라서, 본 논문에서는 여러 도출 방법을 제안하고, 각각에 대한 추정 오차, 오차의 분산, 필터의 일관성을 분석하는 것이 주요 연구 동기이다.

3.2 RBPF-SLAM 결과 도출 방법

본 논문에서는 그림 4와 같이 네 가지의 결과 도출 방법을 제안한다. 첫째, 최대 가중치를 가지는 파티클의 정보 이용, 둘째, 파티클 집합에 속한 모든 파티클 정보 의 평균을 이용, 셋째, 파티클 트리의 루트(root) 파티클 을 이용, 마지막으로, 파티클 트리의 끝노드(leaf node)의

정보를 이용하는 것이다.

그림 4. RBPF-SLAM의 결과 도출 방법 및 절차

3.2.1 최대 가중치 파티클 데이터

RBPF-SLAM의 수행을 끝마친 후, 최대 가중치를 가 지는 파티클의 정보를 이용한다. 이것은 많은 연구자들 에 의해, 당연히 가장 좋은 결과를 줄 것이라는 가정하 에 많이 사용되었다. 먼저, 최대 가중치를 갖는 파티클 의 인덱스(index) kmax는 다음과 같이 쉽게 구할 수 있다:

arg max

[ ]

, 1,..., (2)

f

max i ti P

k = w i = N

여기서, ^{[ ]}

f

i

w

t 는 RBPF-SLAM이 끝난 후, 시간 tf에서 전체 파티클 개수 NP중의 i번째 파티클의 가중치를 나 타낸다. 따라서, RBPF-SLAM의 결과 도출인 로봇 경로 (path)와 환경맵(map)은 다음과 같이 이루어진다:

max

max

[ ]

1:

[ ]

1:

f

F

k t k N

path = x map = μ

여기서, _1:^{[ max]}

f

k

x

t ,

μ

_1:^{[ max]}

F

k

N 는 초기부터 시간 tf까지의 각 각 로봇 경로 및 환경맵을 나타낸다.

3.2.2 파티클의 평균 데이터

각각의 파티클이 가지고 있는 정보의 평균을 취하는 방법 또한 의미 있는 것이다. 파티클 정보의 평균을 구 하는 것도 다음과 같이 간단히 구할 수 있다:

[ ] 1:

=1 [ ] 1:

=1

P f

P F

N k P k t

N k P k N

path = 1 x N map = 1

N μ

∑

∑

3.2.3 파티클 트리의 루트

기존 RBPF-SLAM의 재추출 과정에서 파티클의 가중 치만을 이용하여 파티클의 복사 및 제거가 이루어지는 데, 파티클의 분포 정보를 이용하여 가중치만을 이용하 는 방법을 보정할 수 있다. 따라서, 가중치가 가장 큰 파티클의 정보를 이용하지 않고, 파티클 트리의 중심이 되는 파티클의 정보를 이용한다. 파티클 트리의 중심점 을 구하기 위해, 여기서는 트리는 만들지 않고, 기하적 중심을 찾기 위해 다음과 같이 파티클 간의 거리가 최 소로 되는 점을 택한다:

[ ] [ ] 1

arg min ( ), 1,..., (3)

P

f f

N

j

root i ti t P

j

k x x i N

=

= ∑ − =

(a) 파티클 분포 및 경계(P1, P4, P5가 끝노드)

(b) 균형 2차원 파티클 트리

그림 5. 파티클 기하 분포와 균형 파티클 트리의 형성

3.2.4 파티클 트리의 끝노드의 평균

파티클의 분포를 고려한 평균 데이터를 이용하기 위 해 파티클 트리를 만들 수 있다. 이 때, 파티클 트리는

파티클간의 기하 정보를 이용하기 위해 균형 k차원 트 리(balanced kd-tree)^[9]를 구성한다. 균형 k차원 트리 형성 후, 트리의 끝노드(leaf node)만을 취하면, 파티클 분포의 대략적인 경계를 구할 수 있다. 예를 들면, 그림 5(a)와 같이 6개의 파티클 P1(2,3), P2(5,4), P3(9,6), P4(4,7), P5(8,1), P6(7,2)가 분포하고 있을 때, 균형 2차원 트리는 그림 5(b)와 같이 형성된다. 형성된 파티클 트리에서 제일 끝 단에 위치하는 파티클인 P1, P4, P5를 취하면 대략적인 파티클의 기하 분포의 경계를 구할 수 있다. 이 때, 끝 노드의 평균값을 RBPF-SLAM의 결과로 사용한다. 이 방법은 파티클 분포가 크게 몇 개의 집단을 형성할 때, 3.2.2의 단순 평균값과는 달리 분포의 경계를 취하기 때 문에 기하적인 평균을 구할 수 있는 장점이 있다.

4. 결과 도출 방법의 모의 실험

4.1 모의 실험 설정

3장에서 제안한 방법의 성능 비교를 위해 그림 6과 같은 모의 실험 환경을 구성하였다. 모의 실험에서는 100개의 파티클을 사용하였고, 로봇의 이동 잡음 및 센 서의 측정 잡음은 (0.5m/s, 5°/s), (0.3m, 3°)로 설정하였다.

또한, 제어 입력 주기는 25ms, 센서 측정 주기는 200ms 였다. 사용된 컴퓨터는 1.86GHz, 2GB 램의 노트북이었 다. RBPF-SLAM은 확률 기반이므로, 매번 임의의 결과 가 얻어지므로, 결과의 검증을 위해 50번의 Monte Carlo 실험을 수행하였다.

그림 6. 모의 실험 환경

0 500 1000 1500

0 0.5 1 1.5 2 2.5 3 3.5 4

Time (step)

Average NEES

그림 7. 일관성 검사를 위한 평균 NEES

그림 8. 결과 도출 방법의 RMS 오차 비교

4.2 RBPF-SLAM 일관성

먼저, 파티클의 다양성을 유지시키기 위해 재추출방 법 대신 보정 방법을 사용하였는데, 그 효과를 알아보 기 위해 일관성 검사를 하였다. RBPF-SLAM의 일관성 (consistency)를 측정하기 위해 일반적으로 Normalized Estimation Error Squared (NEES)를 본 연구에서도 적용하 였다. 그 결과가 그림 7에 나타나 있다. 필터의 일관성 검사에 대한 내용은 참고문헌^[8]을 참고하고, 그림 7에서 가로축은 시간의 흐름을 나타내기 위한 RBPF-SLAM의 재귀적 네 단계의 반복회수이고, 세로축의 두 개의 평 행선은 필터가 일관성이 있다고 가정했을 때의 NEES 상한과 하한이다. 일반적인 재추출 방법을 적용하였을 때는, NEES가 SLAM 초기에 급격히 증가하여 파티클들 이 불확실성을 무시(optimistic or over-confident)해지는 현 상이 나타난다. 하지만, 그림 7에서는 NEES가 일관적인 필터의 상한선을 넘지 않고 있다. 비록, 보정 방법을 사 용하였을 때, RBPF-SLAM이 매 순간 일관성을 보이진 않지만, 파티클들이 불확실성(pessimistic)을 유지하며 추 정을 수행하는 것을 알 수 있다.

표 2. 각 결과도출방법의 오차의 표준 편차 결과도출방법 로봇위치 로봇방향 환경맵

최대 가중치 0.1710 0.0179 0.1158 파티클 평균 0.0329 0.0027 0.0346

트리 루트 0.1159 0.0100 0.1424 끝노드 평균 0.0344 0.0037 0.0353 4.3 RBPF-SLAM 오차 및 오차 분산

SLAM의 기본 평가 기준은 얼마나 정확한 로봇 경로 와 환경맵을 작성이다. 이를 위해 일반적으로 사용되는 것이 Root Mean Square (RMS) 오차이다. 그림 8에 각 방 법의 오차를 표시하였다. 이 결과는 모의 실험을 독립 적으로(Monte Carlo Run)으로 50회 실행하여 얻은 결과 이다. 결과를 보면, 가장 일반적으로 사용되는 가중치가 가장 큰(highest) 파티클의 데이터를 이용했을 때, 로봇 의 2차원 위치와 환경맵의 오차가 상대적으로 평균을 이용했을 때보다 많이 큼을 알 수 있다. 또한, 파티클 트리의 루트를 이용하는 방법도 다른 방법과 비교했을 때, 이점이 없었다. 반면에, 파티클의 평균을 사용했을 때, 모든 경우에서 가장 적은 오차를 보여준다. 파티클 트리의 끝노드를 이용한 경우도 평균을 이용한 방법과 유사한 성능을 보이지만, 파티클 트리를 만들기 위한 추가적인 비용이 필요하여, 전체 평균 방법이 낫다.

모의 실험 회수에 대해서, 각각의 방법에 대한 오차 의 표준 편차를 표 2에 나타내었다. 파티클 데이터의 평균을 이용한 경우, 표준 편차 또한 가장 적었다. 즉, 파티클의 평균 데이터를 이용하여 하나의 로봇 경로와 환경맵을 추출 했을 때, 높은 확률로 오차가 적은 결과 를 얻었다. 특정 번째의 모의 실험이 끝난 후 각 방법에 의한 결과를 그림 9에 나타내었다. 결론적으로, 같은 데 이터를 어떤 방법으로 도출하느냐에 따라 서로 다른 결 과를 보여준다.

5. 결 론

본 연구는 파티클 다양성이 유지될 때, RBPF-SLAM 을 결과를 도출하기 위한 방법들을 제안하고, 성능을 비교하였다. 이것은 많은 연구자들이 파티클 필터를 사 용하지만 그 결과를 도출하기 위한 방법에 대한 고찰을 하지 않고, 최대 가중치를 가지는 파티클의 데이터를 결과로서 사용해 왔다. 하지만, 본 연구 결과에 따르면, 전체 파티클의 정보를 모두 이용하는 파티클 평균 방법 이 가장 적은 추정 오차를 보였다. 더욱이 이 방법은 다 른 방법에 비해 적은 표준 편차를 가졌다. 즉, 여러 회 동안 추정 성능이 좋다는 것을 의미한다. 본 연구 결과

0 5 10 15 20 25 30 35 40

0 5 10 15 20 25 30 35 40

X (m)

Y (m)

landmark environment path of robot path of highest weight path of root path of mean map of mean map of highest weight map of root

그림 9. 각 방법으로 로봇의 경로와 환경맵 도출

를 보면, 여러 파티클의 정보를 이용하여 결과를 도출 하는 경우가 단일 파티클의 정보를 이용하는 경우보다 그 결과가 좋음을 확인하였다.

[1] K. Murphy, “Bayesian map learning in dynamic environments,”Advanced in Neural Information Processing Systems, MIT Press, 1999.

[2] A. Doucet, N. de Freitas, K. Murphy, et al., “Rao- Blackwellized particle filtering for dynamic Bayesian networks,” in Proc. of Conference on Uncertainty in Artificial Intelligence, pp. 176-183, 2000.

[3] M. Montemerlo, FastSLAM: A factored solution to the simultaneous localization and mapping problem with unknown data association, Ph.D. Dissertation, Carnegie Mellon University, 2003.

[4] T. Bailey, J. Nieto, and E. Nebot, “Consistency of the FastSLAM algorithm,” in Proc. of IEEE Int’l Conf. on Robotics and Automation, pp. 424-429, 2006.

[5] N. Kwak, G. W. Kim, and B. H. Lee, “A new com- pensation technique based on analysis of resampling process in FastSLAM,” Robotica, vol. 26, no.2, pp.

205-217, March 2008.

[6] G. Grisetti, C. Stachniss, and W. Burgard, “Improved technique for grid mapping with Rao-Blackwellized particle filters,” IEEE Transactions on Robotics, vol. 23, no. 1, 2007.

[7] S. Thrun, W. Burgard, and D. Fox, Probabilistic robotics, Cambridge: MIT Press, 2005.

[8] Y. Bar-Shalom, X. R. Li, and T. Kirubarajan, Esti- mation with Applications to Tracking and Navigation, John Wiley and Sons, 2001.

[9] kd-tree(short for k-dimensional tree), Wikipedia, http://

en.wikipedia.org/wiki/Kd-tree

[10] N. Kwak, B. H. Lee, and K. Yokoi, “Result represent- tation of Rao-Blackwellized particle filtering for SLAM,”

Int’l Conf. on Control, Automation and Systems pp.

698-703, 2008.

Kazuhito YOKOI

1984 Nagoya Institute of

Technology, Mechanical Eng. (B.E.)

1986 Tokyo Institute of Technology, Mechanical Eng. Science (M.E.) 1994 Tokyo Institute of Technology, Mechnical Eng.

Science (Ph.D.)

2003~현재 Joint Japanese-French Robotics Lab. Co-director 2004-현재 AIST 자율행동제어 Group Leader

2005~현재 University of Tsukuba, 교수

관심분야 : Humanoid robots, Intelligent robot systems

이 범 희

1978 서울대학교 전자공학

(공학사)

1980 서울대학교 전자공학 (공학석사)

1985 University of Michigan.

컴퓨터,정보,제어공학 (공학박사)

1985~1987 Purdue University 조교수

1996~현재 서울대학교 전기.컴퓨터공학부 교수 2004~현재 IEEE Fellow, Robotics and Automation Society 관심분야 : 다개체 로봇 제어, motion planning

곽 노 산

2001 아주대학교 기계공학

(공학사)

2008 서울대학교 전기.컴퓨 터 공학 (공학박사) 2008~현재 AIST 자율행동제

어 JSPS Postdoctoral Fellow

관심분야 : SLAM, Particle diversity and cooperation, Humanoid robot exploration