몬테카를로 위치추정

1. 개요[편집]

몬테카를로 위치추정 Monte Carlo Localization (MCL)
추정 대상	평면 자세 $(x, y, \theta)$ — 3차원 상태
도구	입자 필터 (SIR)
주어지는 것	이미 만들어진 지도 (대개 점유 격자)
모형 두 개	오도메트리 운동모형 · 빔 레인지 센서모형
대표 구현	ROS amcl (adaptive MCL)
제안 논문	Dellaert, Fox, Burgard, Thrun (1999)

로봇에게 “너 지금 어디 있니”를 물으면, 잘 훈련된 로봇은 “아마 여기 아니면 저기요”라고 답한다.

몬테카를로 위치추정(Monte Carlo Localization, MCL)은 이미 주어진 지도 위에서 이동로봇의 자세 $(x,y,\theta)$를 가중 표본의 무리로 표현하고, 오도메트리와 거리 센서 관측을 번갈아 반영해 그 무리를 참값 주변으로 수렴시키는 위치추정 방법이다. 1999년 델라트·폭스·부르가르트·스룬이 이동로봇에 입자 필터를 붙이면서 붙인 이름이고, 지금도 실내 이동로봇의 사실상 표준으로 남아 있다.¹

입자 필터 일반론 — 중요도 표본추출, 가중치 붕괴, 유효 표본 수 — 은 입자 필터 문서가 다룬다. 이 문서가 다루는 것은 그 위에 얹히는 로보틱스 고유의 세 가지다. 상태공간이 지도라는 것, 우도가 광선을 쏴서 계산된다는 것, 그리고 초기 자세를 아무도 모르는 전역 위치추정(global localization)에서 출발한다는 것. 이 세 가지가 MCL을 “칼만 필터로는 못 하는 일”의 자리에 앉힌다.

2. 왜 가우시안으로는 안 되는가[편집]

칼만 필터와 그 비선형 확장은 신념(belief)을 평균과 공분산 하나로 요약한다. 즉 봉우리가 하나라고 가정한다. 로봇이 이미 자기 위치를 대충 알고 조금씩 미끄러지는 상황(자세 추적, pose tracking)에서는 이 가정이 훌륭하다.

문제는 전원을 막 켰을 때다. 로봇은 지도 어디에나 있을 수 있고, 신념은 지도 전체에 퍼진 균등분포다. 여기에 가우시안을 씌우면 “평균은 건물 정중앙, 표준편차는 40 m”라는 아무 쓸모 없는 답이 나온다. 게다가 대칭적인 건물 — 똑같이 생긴 복도가 네 개 있는 사무동, 문이 같은 간격으로 늘어선 병원 — 에서는 관측을 아무리 모아도 신념이 여러 봉우리로 갈라진 채 유지된다. 로봇은 “3층 동쪽 복도 아니면 3층 서쪽 복도”라는 상태를 정직하게 들고 있어야 하고, 그 둘의 평균인 엘리베이터 홀 한가운데를 답이라고 우기면 안 된다.

가중 입자의 무리는 이 다봉성을 공짜로 표현한다. 봉우리 하나당 입자 뭉치 하나. 복도를 따라 이동하다가 소화전 하나가 한쪽에서만 보이는 순간, 틀린 뭉치의 가중치가 무너지고 신념은 단봉으로 붕괴한다. 이 “여러 가설을 들고 다니다 증거가 나오면 하나만 남기는” 동작이 MCL의 존재 이유다.

3. 지도와 운동모형[편집]

MCL은 지도가 주어져 있다고 가정한다. 지도와 자세를 동시에 추정하는 문제는 SLAM이고 그쪽은 상태 차원이 지도 크기만큼 커져서 입자 필터를 그대로 쓸 수 없다(그래서 라오-블랙웰화 같은 장치가 따로 필요하다). 여기서는 지도를 고정된 배경으로 놓는다. 표준 형식은 점유 격자(점유 격자 지도) — 5~10 cm 셀마다 “여기 장애물이 있을 확률”을 담은 2차원 배열이다.

운동은 오도메트리로 들어온다. 바퀴 엔코더가 알려주는 두 시각 사이의 상대 이동 $(\bar{x}_{t-1}, \bar{x}_t)$를 회전–직진–회전 세 조각으로 분해한다.

$$\delta_{\text{rot1}}, \quad \delta_{\text{trans}}, \quad \delta_{\text{rot2}}$$

그리고 각 조각에 잡음을 얹어 입자를 굴린다. 잡음의 크기는 네 개의 계수 $\alpha_1 \ldots \alpha_4$로 정하는데, 회전 오차가 회전량과 이동량에, 직진 오차가 이동량과 회전량에 각각 비례한다는 구조다. 이 교차항이 중요하다 — 제자리에서 빙글 돌면 직진 거리는 0인데 각도 오차는 크게 쌓이고, 그 각도 오차가 다음 직진에서 위치 오차로 증폭된다. 카펫 위에서 바퀴가 헛돌거나 로봇이 문턱을 넘으면 $\alpha$를 아무리 키워도 모형 밖이며, 이게 뒤에 나올 납치 문제로 이어진다.

4. 빔 레인지 센서모형[편집]

핵심 계산은 우도 $p(z_t \mid x_t^{(i)}, m)$다. 입자 $i$가 진짜 로봇 자세라면, 라이다가 지금 찍은 거리값들이 나올 확률은 얼마인가.

빔 모형(beam model)은 각 광선을 독립으로 보고, 입자 자세에서 지도를 향해 레이캐스팅을 해서 “이 자세라면 이 광선은 $z^*$에서 벽에 맞아야 한다”를 구한 뒤, 실제 측정값을 네 성분의 혼합분포로 설명한다.

• $p_{\text{hit}}$ — $z^*$ 근처의 가우시안. 정상 측정.
• $p_{\text{short}}$ — $z^*$보다 짧은 쪽의 지수분포. 지도에 없는 사람·의자 때문에 광선이 일찍 맞는 경우.
• $p_{\text{max}}$ — 최대거리에 몰린 뾰족한 봉우리. 유리·검은 물체·하늘을 향해 쏴서 반사가 안 돌아온 경우.
• $p_{\text{rand}}$ — 측정 범위 전체의 균등분포. 설명 불가능한 잡값에 대한 보험.

네 가중치의 합이 1이고, 전체 우도는 광선들의 곱이다. 여기에 두 가지 함정이 있다.

첫째, 비용. 광선 하나마다 격자 레이캐스팅이 필요하고 입자가 수천 개면 스텝당 수십만 번의 레이캐스팅이 된다. 그래서 실무에서는 360개 광선 중 30개 정도만 쓰고, 지도가 고정이므로 각 셀에서 가장 가까운 장애물까지의 거리 변환을 미리 계산해 두는 우도장 모형(likelihood field)으로 갈아탄다. 광선 끝점을 지도에 던져 미리 계산된 거리표를 한 번 조회하면 끝이라 훨씬 싸고, 덤으로 우도가 자세에 대해 매끄러워진다.

둘째, 과신. 이웃한 광선들은 같은 벽을 보므로 절대 독립이 아닌데 우도를 곧이곧대로 곱하면 지수가 광선 수만큼 붙는다. 결과는 바늘처럼 뾰족한 우도 — 참값에서 몇 cm만 벗어난 입자도 가중치가 사실상 0이 되고, 재표집 한 번에 신념이 입자 하나로 붕괴한다. 대응은 두 가지다. 광선을 솎아내 유효 개수를 줄이거나, 우도 전체를 $1/\eta$ 제곱으로 눌러 무디게 만드는 것(likelihood tempering). 후자는 이론적 정당화가 약한 대신 현장에서 잘 먹혀서 대부분의 구현에 들어 있다.²

5. 전역 위치추정과 저분산 재표집[편집]

전역 위치추정은 지도의 자유공간 전체에 입자를 균등하게 흩뿌리는 것으로 시작한다. 로봇이 몇 미터 움직이며 관측을 몇 번 받으면 입자 구름이 후보 몇 개로 쪼그라들고, 대칭이 깨지는 관측 하나가 나오면 하나로 수렴한다. 이 과정 전체가 MCL이 다른 방법과 다른 지점이다.

수렴 과정에서 재표집을 어떻게 하느냐가 품질을 좌우한다. 가중치에 비례해 $M$번 독립적으로 뽑는 다항 재표집은 구현이 쉽지만 표본 잡음이 크다 — 가중치가 완전히 균등한데도 어떤 입자는 세 번 뽑히고 어떤 입자는 사라진다. 표준은 저분산 재표집(low-variance 또는 systematic resampling)이다. 난수를 딱 하나 $r \sim U[0, 1/M)$ 뽑고, 누적 가중치 위에서 $r, r + 1/M, r + 2/M, \ldots$ 지점을 순서대로 훑어 간다.

$$u_m = r + \frac{m-1}{M}, \qquad m = 1, \ldots, M$$

장점이 셋이다. $O(M)$ 시간에 끝나고(누적합을 한 번만 훑는다), 가중치가 균등하면 모든 입자가 정확히 한 번씩 살아남아 쓸데없는 다양성 손실이 없으며, 분산 자체가 다항 재표집보다 작다. 대신 표본들이 서로 독립이 아니게 되는데, 위치추정에서는 이 상관이 문제가 된 적이 없다.

재표집을 매 스텝 하는 것도 낭비다. 유효 표본 수 $\text{ESS} = 1/\sum_i (w^{(i)})^2$가 $M/2$ 아래로 떨어질 때만 재표집하는 것이 국룰이다. 특히 로봇이 가만히 서 있을 때 재표집하면 재앙이다. 운동모형이 입자를 흩어주지 않으므로 복제된 입자가 갈라지지 못하고, 몇 초 만에 전부 같은 점으로 뭉쳐 버린다. 그래서 대부분의 구현은 “일정 거리 또는 일정 각도를 움직였을 때만 필터를 한 스텝 돌린다”는 조건을 건다.

6. KLD 표집 — 입자 수를 상황에 맞춘다[편집]

전역 위치추정에는 입자가 수만 개 필요하고, 수렴한 뒤 추적 단계에는 수백 개면 충분하다. 둘 다 만족시키려고 계속 수만 개를 돌리는 것은 CPU 낭비다. KLD 표집(KLD-sampling, Fox 2001)은 입자 수를 매 스텝 스스로 정한다.

아이디어는 이렇다. 상태공간을 격자 상자로 나누고 재표집하면서 **입자가 실제로 들어간 상자 수 $k$**를 센다. 표본 근사분포와 참분포 사이의 쿨백-라이블러 발산이 $\varepsilon$ 이하가 될 확률이 $1-\delta$ 이상이려면 필요한 표본 수는 자유도 $k-1$의 카이제곱 분위수로 주어지고, 윌슨–힐퍼티 근사를 쓰면 닫힌 식이 나온다.

$$n = \frac{k-1}{2\varepsilon}\left(1 - \frac{2}{9(k-1)} + \sqrt{\frac{2}{9(k-1)}}\, z_{1-\delta}\right)^{3}$$

핵심은 $n$이 차지한 상자 수에만 의존한다는 것이다. 신념이 지도 전체에 퍼져 있으면 $k$가 크니 입자를 수만 개 뽑고, 한 점으로 수렴하면 $k$가 몇 개로 줄어 입자도 수백 개로 자동 감소한다. ROS amcl의 min_particles/max_particles가 이 식의 하한과 상한이며, “adaptive”라는 이름이 여기서 왔다.

7. 입자 고갈과 납치된 로봇[편집]

입자 필터의 고질병이 여기서는 특히 아프다. 입자 고갈(particle deprivation)은 참값 근처에 입자가 한 개도 남지 않는 사고다. 한 번 일어나면 회복 경로가 없다 — 입자는 재표집으로 복제될 뿐 없는 곳에 새로 생기지 않으므로, 필터는 틀린 자세에 확신을 갖고 눌러앉는다.

원인은 두 갈래다. 하나는 위에서 말한 과신 + 잦은 재표집으로 다양성이 말라 죽는 것. 다른 하나가 납치된 로봇 문제(kidnapped robot problem)로, 누군가 로봇을 들어 옮기거나 바퀴가 헛돌아 오도메트리가 통째로 거짓말을 하는 상황이다. 필터는 자기가 A 지점에 있다고 굳게 믿는데 실제 관측은 B 지점의 것이므로, 모든 입자의 우도가 동시에 바닥을 친다.

완화책은 실용적이고 조금 뻔뻔하다.

• 랜덤 입자 주입. 매 스텝 입자의 일부(1~5%)를 지도 위 균등분포에서 새로 뽑아 넣는다. 신념이 옳을 때는 이 입자들이 즉시 굶어 죽고, 납치가 일어나면 이들이 씨앗이 되어 신념이 새 위치로 옮겨간다.
• 증강 MCL(augmented MCL). 주입 비율을 고정하지 말고, 평균 우도의 단기 이동평균 $w_{\text{fast}}$와 장기 이동평균 $w_{\text{slow}}$의 비로 정한다. $1 - w_{\text{fast}}/w_{\text{slow}}$가 양수라는 것은 “요즘 관측이 평소보다 훨씬 안 맞는다”는 신호이고, 그만큼 주입을 늘린다. 납치 직후에만 문이 열리는 구조라 평상시 정확도를 거의 깎지 않는다.
• 관측 기반 제안분포. 운동모형 대신 관측에서 자세를 역으로 뽑아 입자를 배치하는 방식(dual MCL). 우도가 뾰족할 때 특히 유리하지만 지도에서 자세를 역산하는 절차가 필요해 구현이 무겁다.

주입은 공짜가 아니다. 정상 상황에서도 소수의 입자를 낭비하고, 무엇보다 필터가 더 이상 진짜 베이즈 사후분포를 근사하지 않는다. 이론적으로는 반칙이지만, 아무도 안 쓰는 정확한 필터보다 가끔 회복하는 부정확한 필터가 낫다는 것이 이 바닥의 합의다.³

8. 현업에서의 현실[편집]

• 튜닝의 90%는 $\alpha_1 \ldots \alpha_4$와 우도 무디기 계수다. 물리적 의미는 명확한데 값은 결국 손으로 맞춘다.
• 지도와 현실이 다르면 아무것도 안 된다. 물류창고에서 팔레트가 통째로 옮겨지면 관측의 절반이 $p_{\text{short}}$로 설명되고 우도가 평평해진다. 그래서 지도 갱신 주기가 위치추정 성능의 상한을 정한다.
• 긴 직선 복도는 여전히 최악의 무대다. 진행 방향 정보가 관측에 거의 없어서 입자 구름이 복도를 따라 길쭉하게 늘어난다. 이때 관성항법 유닛이나 천장 마커를 섞는 센서 융합이 들어간다.
• 로봇이 “확신 있게 틀린” 상태로 경로 계획에 자세를 넘기는 것이 가장 위험하다. 그래서 실무 스택은 입자 구름의 공분산을 감시하다가 임계값을 넘으면 주행을 멈추고 전역 위치추정을 다시 건다.

9. 관련 문서[편집]

• 입자 필터 · 몬테카를로 방법
• 칼만 필터 · 앙상블 칼만 필터
• SLAM · 점유 격자 지도 · 오도메트리
• 센서 융합 · 관성항법
• 경로 계획 · 능동 센싱
• 은닉 마르코프 모형 · 마르코프 결정 과정
• 쿨백-라이블러 발산 · 거리 변환

10. Footnotes[편집]

1. Dellaert, Fox, Burgard, Thrun (1999), Monte Carlo Localization for Mobile Robots, ICRA. 같은 저자들의 교과서 Probabilistic Robotics(2005) 8장이 사실상의 표준 서술이며, 이 문서의 운동모형·센서모형 표기도 그 책을 따랐다. 참고로 이 책은 로보틱스 전공자들 사이에서 “빨간책”으로 불린다. 표지가 빨개서다. ↩

2. 우도를 $p^{1/\eta}$로 누르는 것은 온도를 올려 분포를 평탄하게 만드는 것과 같은 조작이다. 담금질 계열에서 온 냄새가 나지만, 여기서는 “센서가 실제보다 정확하다고 믿지 마라”는 아주 실용적인 뜻이다. $\eta$를 얼마로 하냐고 물으면 대개 “돌려보고 정한다”는 답이 돌아온다. ↩

3. 랜덤 입자 주입이 사후분포를 왜곡한다는 점은 원 저자들도 대놓고 인정한다. 그럼에도 20년 넘게 모든 구현에 들어 있는 이유는, 실내 로봇이 사람 발에 차이거나 청소 아주머니에게 들려 옮겨지는 빈도가 논문이 가정하는 것보다 훨씬 높기 때문이다. ↩