8.89 확률론적 점유 격자 지도의 원리

1. 점유 격자 지도의 개요

점유 격자 지도(Occupancy Grid Map)는 엘페스(Elfes)와 모라벡(Moravec)이 1980년대에 제안한 이산화된 환경 표현 방식이다. 환경을 이산 셀의 격자로 분할하고, 각 셀이 장애물에 의해 점유되어 있을 확률을 저장한다. 거리 센서의 잡음이 많은 관측을 확률론적으로 융합하여 일관된 지도를 구축하는 데 효과적이다.

2. 수학적 정식화

지도 $\mathbf{m}$ 을 이산 셀 $\{m_1, m_2, \ldots, m_K\}$ 의 집합으로 표현한다. 각 셀 $m_i$ 는 이진 확률 변수로, $m_i = 1$ 이면 점유, $m_i = 0$ 이면 비점유를 나타낸다.

관측과 로봇 자세의 시퀀스가 주어졌을 때, 지도의 사후 분포:

$p(\mathbf{m} \vert \mathbf{z}_{1:t}, \mathbf{x}_{1:t})$

3. 셀 독립성 가정

완전한 결합 분포 $p(\mathbf{m} \vert \mathbf{z}, \mathbf{x})$ 는 $K$ 개 셀에 대해 $2^K$ 개의 값을 가지므로 저장과 계산이 불가능하다. 이를 해결하기 위해 셀의 조건부 독립 가정을 도입한다.

$p(\mathbf{m} \vert \mathbf{z}_{1:t}, \mathbf{x}_{1:t}) = \prod_{i=1}^{K}p(m_i \vert \mathbf{z}_{1:t}, \mathbf{x}_{1:t})$

이 가정에 의해 각 셀의 점유 확률을 개별적으로 추적하면 된다. 이는 근사이지만 실용적으로 매우 효과적이다.

4. 이진 베이즈 필터

각 셀 $m_i$ 에 대해 이진 베이즈 필터를 적용한다.

$p(m_i \vert \mathbf{z}_{1:t}, \mathbf{x}_{1:t}) = \frac{p(\mathbf{z}_t \vert m_i, \mathbf{x}_t)p(m_i \vert \mathbf{z}_{1:t-1}, \mathbf{x}_{1:t-1})}{p(\mathbf{z}_t \vert \mathbf{z}_{1:t-1}, \mathbf{x}_{1:t})}$

이 갱신은 로그 오즈(log-odds) 표현을 사용하면 크게 단순화된다.

5. 로그 오즈 표현

로그 오즈는 두 사건의 확률 비율의 로그이다.

$l(m_i) = \log\frac{p(m_i)}{1 - p(m_i)}$

역변환:

$p(m_i) = 1 - \frac{1}{1 + \exp(l(m_i))}$

로그 오즈의 장점:

곱셈이 덧셈으로 변환되어 수치적으로 안정적
정규화가 필요 없음
갱신이 단순한 덧셈

6. 로그 오즈 기반 갱신

$l_t(m_i) = l_{t-1}(m_i) + \log\frac{p(m_i \vert \mathbf{z}_t, \mathbf{x}_t)}{1 - p(m_i \vert \mathbf{z}_t, \mathbf{x}_t)} - l_0$

여기서 $l_0 = \log\frac{p(m_i)}{1 - p(m_i)}$ 는 사전 확률의 로그 오즈이다(통상 $p(m_i) = 0.5$ 이므로 $l_0 = 0$ ).

7. 역 센서 모델(Inverse Sensor Model)

갱신식에서 $p(m_i \vert \mathbf{z}_t, \mathbf{x}_t)$ 는 역 센서 모델이다. 이는 “관측이 주어졌을 때 각 셀의 점유 확률“을 나타내며, 전방 센서 모델 $p(\mathbf{z}_t \vert m_i, \mathbf{x}_t)$ 로부터 유도된다.

7.1 거리 센서의 역 모델

거리 센서 $z$ 가 참 거리 $z^*$ 에 가까운 셀은 점유, 센서 이전의 셀은 비점유, 센서 이후의 셀은 사전 확률로 유지되는 것으로 모델링한다.

$p(m_i \vert z, \mathbf{x}) = \begin{cases} p_{\text{occ}} & \text{if } \lvert r_i - z \rvert < \alpha \\ p_{\text{free}} & \text{if } r_i < z - \alpha \\ p_{\text{prior}} & \text{if } r_i > z + \beta \end{cases}$

여기서 $r_i$ 는 셀 $i$ 까지의 거리이고, $\alpha, \beta$ 는 센서 모델의 매개변수이다. 통상 $p_{\text{occ}} > 0.5 > p_{\text{free}}$ 이다.

8. 지도 작성 알고리즘

입력: 이전 로그 오즈 지도 $\{l_{t-1}(m_i)\}$ , 센서 관측 $\mathbf{z}_t$ , 로봇 자세 $\mathbf{x}_t$

절차:

관측에 의해 영향받는 셀의 집합 $\mathcal{C}$ 결정 (센서 범위 내 셀)
각 셀 $m_i \in \mathcal{C}$ 에 대해:
$\quad$ 역 센서 모델 $p(m_i \vert \mathbf{z}_t, \mathbf{x}_t)$ 계산
$\quad$ 로그 오즈 갱신: $l_t(m_i) = l_{t-1}(m_i) + \text{inv\_sensor\_model}(m_i, \mathbf{z}_t, \mathbf{x}_t) - l_0$
출력: 갱신된 로그 오즈 지도

9. 지도의 해석과 시각화

로그 오즈 $l(m_i)$ 의 부호와 크기로 셀의 상태를 해석한다.

$l > 0$ : 점유 ( $p(m_i) > 0.5$ )
$l < 0$ : 비점유 ( $p(m_i) < 0.5$ )
$l \approx 0$ : 미관찰 또는 불확실

시각화에서는 흑백 또는 색깔 그래디언트로 점유 확률을 표현한다.

10. 차원 확장과 옥트리

3차원 환경에서는 3차원 점유 격자(voxel grid)가 사용된다. 해상도가 증가하면 메모리와 계산 비용이 급증하므로, 옥트리(octree) 기반 적응적 분할(OctoMap)이 효율적이다.

11. 한계와 확장

셀 독립 가정: 실제로는 이웃 셀 사이의 상관이 존재한다. 조건부 랜덤 필드(CRF), 마르코프 랜덤 필드로 상관을 모델링할 수 있다.

정적 환경 가정: 점유 격자는 환경이 정적이라 가정한다. 동적 환경에서는 변화를 감지하고 갱신하는 기법이 필요하다.

이진 점유: 다중 클래스 셀(바닥, 벽, 물체 등)을 표현하려면 의미적 지도(semantic map)로 확장된다.

12. 참고 문헌

Elfes, A. (1989). “Using Occupancy Grids for Mobile Robot Perception and Navigation.” Computer, 22(6), 46–57.
Moravec, H., & Elfes, A. (1985). “High Resolution Maps from Wide Angle Sonar.” Proceedings of ICRA, 116–121.
Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.
Hornung, A., Wurm, K. M., Bennewitz, M., Stachniss, C., & Burgard, W. (2013). “OctoMap: An Efficient Probabilistic 3D Mapping Framework Based on Octrees.” Autonomous Robots, 34(3), 189–206.

version: 1.0