점유 격자 지도

1. 개요[편집]

점유 격자 지도 Occupancy Grid Map
표현	공간을 격자로 자르고 셀마다 「점유 확률」 하나
핵심 트릭	로그 오즈 누적 — 곱셈 갱신을 덧셈으로
갱신 모형	역센서모형 + 레이 캐스팅(경로는 free, 끝점은 occupied)
결정적 가정	셀끼리 독립 — 편하고, 자주 틀린다
계보	모라벡·엘페스(1985) 소나 격자 → GMapping → OctoMap
쓰는 곳	위치추정 · 경로 계획의 비용지도 · 자유공간 판정

점유 격자 지도(occupancy grid map)는 로봇 주변 공간을 일정 크기의 셀로 나누고, 각 셀이 장애물에 점유되어 있을 확률을 하나씩 들고 다니는 지도 표현이다. 실내 이동로봇이라면 대개 5~10 cm 셀의 2차원 배열이고, 값은 0(확실히 비었다)에서 1(확실히 막혔다) 사이이며 아직 관측되지 않은 셀은 0.5로 시작한다.

이 표현이 40년 가까이 살아남은 이유는 세 가지다. 첫째, 자유공간을 명시적으로 표현한다. 특징점 지도는 “여기 기둥이 있다”는 말만 하지 “여기는 지나가도 된다”는 말을 못 하는데, 경로 계획이 진짜로 필요로 하는 정보는 후자다. 둘째, 센서 잡음을 확률로 흡수한다. 한 번의 오검출이 지도를 망치지 않는다. 셋째, 갱신이 미친 듯이 싸다 — 아래에서 볼 로그 오즈 트릭 덕분에 셀 하나 갱신이 덧셈 한 번이다.

2. 문제 설정과 셀 독립 가정[편집]

지도를 $m=\{m_1,\dots,m_N\}$ 이라 하고 각 $m_i\in\{0,1\}$ 을 셀 $i$ 의 점유 여부라 하자. 로봇의 자세 $x_{1:t}$ 를 안다고 가정하고(모르면 그건 SLAM이다) 관측 $z_{1:t}$ 가 주어졌을 때 사후분포 $p(m \mid z_{1:t}, x_{1:t})$ 를 구하는 것이 목표다.

정직하게 하려면 $2^N$ 개 조합 위의 분포를 다뤄야 한다. 셀이 10만 개인 평범한 실내 지도에서 이건 농담이다. 그래서 판을 깔기 전에 가정 하나를 던진다.

$$p(m \mid z_{1:t}, x_{1:t}) = \prod_i p(m_i \mid z_{1:t}, x_{1:t})$$

셀끼리 독립이라는 것. 이 한 줄로 문제가 $N$ 개의 독립적인 이진 베이즈 필터로 쪼개지고, 각 셀이 자기 확률 하나만 들고 있으면 되는 구조가 나온다. 물론 현실의 셀은 독립이 아니다 — 벽은 길게 이어지고, 방은 닫혀 있고, 옆 셀이 막혀 있으면 이 셀도 막혀 있을 확률이 높다. 이 가정을 버린 대가는 아래 「한계」 절에서 전부 청구된다.

3. 로그 오즈 — 곱셈을 덧셈으로[편집]

셀 하나에 집중하자. 상태가 시간에 따라 변하지 않는다는 가정(정적 지도)에서 베이즈 정리를 두 번 적용하면 사후확률이

$$p(m_i \mid z_{1:t}) = \frac{p(m_i \mid z_t)\,p(z_t)\,p(m_i \mid z_{1:t-1})}{p(m_i)\,p(z_t \mid z_{1:t-1})}$$

형태로 정리된다(자세 조건은 표기에서 생략). 여기서 $p(m_i \mid z_t)$ 가 역센서모형(inverse sensor model) — “이 관측을 봤을 때 이 셀이 막혀 있을 확률”이다. 문제는 식에 붙어 있는 $p(z_t)$ 류의 정규화 항들인데, 이것들이 $m_i$ 에 의존하지 않는다는 점이 탈출구를 준다. 같은 식을 $\lnot m_i$ 에 대해서도 쓰고 두 식을 나누면 그 항들이 통째로 사라진다.

남는 것을 오즈비로 두고 로그를 취하자. 로그 오즈를

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

로 정의하면 갱신식이 이렇게 된다.

$$l_{i,t} = l_{i,t-1} + \underbrace{\log\frac{p(m_i \mid z_t)}{1-p(m_i \mid z_t)}}_{\text{이번 관측이 주는 증거}} - \underbrace{l_{i,0}}_{\text{사전확률 상쇄}}$$

이게 이 문서의 전부다. 관측이 하나 들어올 때마다 셀 값에 상수를 더한다. 곱셈도, 나눗셈도, 정규화도 없다. 사전확률을 0.5로 두면 $l_{i,0}=0$ 이라 마지막 항까지 사라져서 갱신이 문자 그대로 l[i] += l_occ 한 줄이 된다. 확률로 되돌리고 싶으면

$$p(m_i) = 1 - \frac{1}{1+e^{\,l_i}}$$

를 쓰면 되는데, 실무에서는 시각화할 때만 되돌린다. 계산은 끝까지 로그 오즈로 한다.

부가 이득도 크다. 확률을 직접 곱해 나가면 값이 0이나 1에 붙어 부동소수점이 죽지만, 로그 오즈는 $\pm\infty$ 로 완만하게 발산할 뿐 언더플로가 없다. 로지스틱 회귀에서 로짓을 쓰는 이유와 정확히 같은 이유다.

4. 역센서모형과 레이 캐스팅[편집]

그럼 더할 상수 $\log\frac{p(m_i \mid z_t)}{1-p(m_i\mid z_t)}$ 는 어디서 오나. 거리센서 빔 하나가 거리 $r$ 을 반환했다면, 그 빔이 지나온 경로의 셀들은 비어 있고(안 비었으면 더 일찍 맞았을 테니) 끝점 근처의 셀은 막혀 있다. 그래서 실제 구현은 이렇게 생겼다.

각 빔 (각도 θ, 거리 r) 에 대해:
    끝점 = 센서위치 + r·(cosθ, sinθ)
    경로셀 ← 선 그리기(센서위치 → 끝점)      # 브레젠험
    for c in 경로셀[:-1]:  l[c] += l_free      # l_free < 0
    if r < r_max:        l[끝점] += l_occ      # l_occ > 0
    l[*] ← clamp(l[*], l_min, l_max)

전형적인 값은 $p_{\text{occ}}=0.7$, $p_{\text{free}}=0.4$ 로 두어 $l_{\text{occ}}\approx0.85$, $l_{\text{free}}\approx-0.41$ 정도다. 비었다는 증거를 막혔다는 증거보다 약하게 주는 것이 관례인데, 한 번의 미검출(유리·검은 표면)이 벽을 지워 버리는 사고를 막기 위해서다.¹ 선 그리기는 정수 연산만으로 격자 위의 선을 긋는 브레젠험 알고리즘을 그대로 쓴다 — 컴퓨터 그래픽스의 1960년대 알고리즘이 로봇 지도 작성의 내부 루프에 앉아 있는 셈이다.

빔이 최대 사거리를 반환했으면(r == r_max) 끝점을 점유로 찍으면 안 된다. 그건 “아무것도 못 봤다”는 뜻이지 “저기 벽이 있다”가 아니다. 초보 구현이 반드시 밟는 지뢰고, 증상은 지도 가장자리를 따라 유령 벽이 동심원으로 생기는 것이다.

4.1. 클램핑 — 지도가 고집불통이 되는 것을 막는다[편집]

로그 오즈는 무한정 누적된다. 같은 벽을 1000번 보면 $l$ 이 800쯤 되고, 확률로는 1과 구분이 안 된다. 그 뒤에 벽이 치워지면 그걸 지우는 데 또 수천 번의 관측이 필요하다. 지도가 자기 과거를 못 버리는 것이다.

처방은 값을 $[l_{\min}, l_{\max}]$ 로 잘라 두는 것(clamping)이다. 상한을 예컨대 $l_{\max}=3.5$ 로 두면 아무리 많이 봐도 확률이 0.97에서 멈추고, 반대 증거 몇 번이면 다시 내려온다. 이 한 줄이 정적 지도라는 거짓말과 동적 세계라는 현실 사이의 타협이며, 나중에 볼 옥트리 압축의 전제이기도 하다.

5. 이 모형이 사실 편법인 이유[편집]

짚고 넘어가야 할 게 있다. 확률론적으로 올바른 방법은 순방향 센서모형 $p(z_t \mid m, x_t)$ — 지도가 이렇다면 센서가 무엇을 읽을지 — 를 쓰고 지도 전체에 대한 사후분포를 구하는 것이다. 위에서 쓴 역센서모형 $p(m_i \mid z_t)$ 는 그것을 셀 단위로 억지로 뒤집은 근사이며, 셀 독립 가정과 합쳐져 원리적으로 틀린 답을 싸게 준다.

틀림이 눈에 보이는 상황도 있다. 폭이 셀 하나보다 좁은 장애물, 빔이 비스듬히 스치는 모서리, 여러 빔이 서로 모순되는 증거를 주는 경우에 그렇다. 순방향 모형을 제대로 써서 지도를 최대사후(MAP)로 추정하면 이런 경우가 개선되지만 비용이 몇 자릿수 비싸고, 무엇보다 온라인으로 못 돈다. 로봇이 30 Hz로 도는 세상에서 “원리적으로 옳지만 느린 방법”은 선택지가 아니다. 점유 격자가 40년간 표준인 이유는 우아해서가 아니라 싸고 충분히 쓸 만해서다.

덧붙여 확률을 아예 안 쓰는 대안도 있다. 셀마다 「끝점으로 찍힌 횟수」와 「통과당한 횟수」를 세고 그 비율 $\text{hits}/(\text{hits}+\text{misses})$ 를 반사율 추정으로 쓰는 계수 모형(reflection map)인데, 실은 특정 가정 아래 최대우도 추정이라 위의 베이즈 갱신과 대단히 가까운 값을 준다.

6. 한계 — 어디서 깨지나[편집]

상황	무슨 일이 벌어지나	흔한 대응
셀보다 얇은 벽	인접 셀이 각각 「반쯤 막힘」이 되어 벽이 뚫린 것처럼 보임	해상도 상향, 끝점 셀에만 점유 부여
유리·거울·검은 표면	빔이 안 돌아오거나 엉뚱한 거리 → 없는 자유공간이 생김	다중 센서 융합, 최대사거리 빔 무시
비스듬한 벽면	반사 강도 저하로 간헐적 미검출, 벽이 점선으로	강도 임계 완화, 여러 각도에서 재관측
움직이는 물체	잔상(ghost trail)이 지도에 눌어붙음	클램핑, 동적 물체 필터링, 동적 점유 격자
자세 오차	같은 벽이 두 겹으로 찍히는 「고스팅」	SLAM 백엔드가 자세를 먼저 고쳐야 한다

표의 둘째 줄은 실내 로봇 운용에서 가장 자주 사고를 내는 항목이고, 대책이 알고리즘 바깥에 있는 경우가 많다.²

마지막 줄이 가장 중요하다. 점유 격자 지도의 품질은 거의 전적으로 자세의 품질에 종속된다. 자세가 몇 cm만 틀려도 벽이 두 겹이 되고, 그 두 겹 사이의 가짜 통로로 경로 계획기가 경로를 뽑는 사고가 난다. 그래서 실제 시스템에서 격자 지도는 혼자 서 있지 않고 늘 위치추정과 짝을 이룬다 — 지도가 주어졌을 때 자세를 찾는 쪽이 몬테카를로 위치추정, 둘을 동시에 푸는 쪽이 SLAM이다.

움직이는 물체의 잔상 문제에는 별도의 계보가 있다. 셀마다 점유 확률뿐 아니라 속도 분포까지 들고 다니면서 예측-갱신을 돌리는 동적 점유 격자가 그것으로, 셀 속도를 입자 필터로 표현하는 구현이 대표적이다. 자율주행 인지에서 “물체로 분할하기 전 단계의 동적 자유공간”을 만드는 데 쓰인다.

7. 계보[편집]

• 1985 — 모라벡과 엘페스. 카네기멜런에서 소나 링을 단 이동로봇에 확률 격자를 도입했다. 당시 소나는 빔 폭이 20~30°나 되고 다중반사가 심해 개별 측정이 거의 쓸모없었는데, 쓸모없는 측정 수천 개를 확률적으로 누적하면 쓸 만한 지도가 나온다는 것을 보인 것이 기여다.³ 엘페스의 1989년 학위논문이 이 표현을 「occupancy grid」라는 이름으로 정착시켰다.
• 1990~2000년대 — 레이저와 필터. 소나가 레이저 거리계로 바뀌면서 빔 모형이 훨씬 날카로워졌고, 지도와 자세를 동시에 푸는 문제로 넘어갔다. 입자마다 자기 격자 지도를 통째로 들고 다니는 라오-블랙웰화 입자 필터(GMapping 계열)가 2차원 실내 SLAM의 사실상 표준이 됐다. 지도 하나가 입자 하나마다 복제되므로 메모리가 살인적이고, 그래서 지도 복제를 피하는 자료구조 트릭이 이 시기 연구의 큰 부분을 차지한다.
• 2010년대 — 3차원과 계층화. 3차원으로 올라가면 격자 셀 수가 해상도의 세제곱으로 늘어 밀집 배열이 즉시 파산한다. 옥트리로 공간을 계층 분할하는 OctoMap이 사실상 표준이 됐는데, 핵심은 클램핑 덕분에 자식 노드들이 같은 값에 도달하면 가지를 쳐낼 수 있다는 점이다. 빈 공간이 압도적으로 넓은 실제 환경에서 이 압축률이 극적이고, 덤으로 임의 해상도의 질의가 공짜로 된다. 옥트리 문서가 자료구조 자체를, 여기서는 확률 갱신과의 결합만 본다.

8. 다른 지도 표현과의 자리 나누기[편집]

점유 격자가 만능은 아니다. 로보틱스가 쓰는 지도 표현은 「무엇을 명시적으로 들고 있는가」로 갈린다.

표현	명시하는 것	강한 곳	약한 곳
특징점 지도	랜드마크 좌표와 공분산	희소·경량, 위치추정에 최적	자유공간을 모름 → 계획에 못 씀
점유 격자	셀별 점유 확률	자유공간·미지 구분, 갱신이 쌈	메모리가 체적에 비례, 얇은 구조에 약함
TSDF / 부호거리장	표면까지의 부호 있는 거리	표면 추출·정합·충돌 여유 계산	자유공간 전체를 담지 않음, 메모리 큼
위상 지도	장소와 연결관계	대규모 경로 계획, 사람의 언어에 가까움	기하 정밀도 없음

실제 시스템은 이 중 하나를 고르지 않고 층으로 쌓는다. 위치추정은 특징점이나 스캔 정합이 담당하고, 국소 회피는 로봇 주위를 따라다니는 작은 점유 격자가, 전역 경로는 위상 지도가, 표면 모형이 필요하면 TSDF가 맡는 식이다. 「하나의 지도」를 고집하는 설계가 오히려 드물다.

메모리 산수를 한 번 해 보면 왜 그런지 바로 보인다. 50 m × 50 m 실내를 5 cm 셀로 덮으면 셀이 100만 개, 셀당 2바이트면 2 MB로 아무 문제가 없다. 그런데 같은 공간을 3차원 5 cm 복셀로 덮으면 높이 3 m만 잡아도 6000만 복셀, 120 MB다. 도심 한 블록으로 넓히면 즉시 기가바이트 단위가 된다. 2차원에서 공짜였던 것이 3차원에서 파산한다는 것이 옥트리 같은 계층 표현이 선택이 아니라 필수인 이유다. 실시간 주행 스택이 전역 3차원 격자 대신 자차를 따라 원점이 미끄러지는 국소 롤링 윈도 격자를 쓰는 것도 같은 이유다 — 뒤에 두고 온 공간은 잊어버린다.

9. 격자 너머 — 거리장으로[편집]

경로 계획기는 사실 “이 셀이 막혔나”보다 “가장 가까운 장애물까지 몇 미터인가” 를 더 자주 묻는다. 충돌 여유를 비용에 넣거나, 경사하강으로 궤적을 장애물에서 밀어내려면 거리와 그 기울기가 필요하기 때문이다. 그래서 현대 3차원 매핑 스택은 점유 격자와 나란히 ESDF(Euclidean Signed Distance Field) — 셀마다 최근접 표면까지의 부호 있는 거리를 담은 장 — 를 유지한다.

만드는 방법은 두 갈래다. 점유 격자가 확정된 뒤 거리 변환을 한 번 돌리는 배치 방식과, 관측이 들어올 때마다 영향받은 영역만 파도처럼 갱신하는 증분 방식이다. 후자는 고속 행진법이 파면을 전파시키는 것과 발상이 같고, 실시간 비행 로봇의 지도 갱신이 이 방식으로 돈다. 중간 표현으로 TSDF(절단 부호거리장)를 유지하다 ESDF를 뽑는 구성이 흔한데, TSDF는 메시 생성으로도 바로 넘어갈 수 있어 일석이조다.

10. 실무에서 조심할 것[편집]

• 셀 크기를 먼저 정해라. 셀은 로봇 폭의 1/5~1/10 정도가 실용적이다. 너무 크면 문틈이 사라지고, 너무 작으면 메모리와 갱신 비용이 제곱(3차원은 세제곱)으로 튄다.
• 미지 상태를 자유공간과 구분해라. 확률 0.5인 셀과 0.1인 셀은 계획기에 전혀 다른 의미다. 「아직 모른다」를 「비었다」로 접어 넣는 순간 로봇이 관측해 본 적 없는 공간으로 태연히 달려든다. 탐사(exploration) 알고리즘이 찾는 프런티어가 정확히 미지와 자유의 경계다.
• 경로 계획에는 원본 격자를 그대로 주지 마라. 로봇을 점으로 취급할 수 있도록 장애물을 로봇 반경만큼 부풀린 비용지도(inflation)를 따로 만든다. 경로 계획의 구성공간 개념이 격자 위에서 구현되는 방식이 이것이다.
• 로그 오즈로 저장하고 확률로 보여 줘라. 갱신 루프에서 지수·로그를 부르는 구현을 종종 보는데, 로그 오즈 트릭을 쓰는 이유가 통째로 날아간다.
• 자세를 먼저 의심해라. 지도가 이상하면 열에 아홉은 센서모형이 아니라 오도메트리나 스캔 정합이 틀린 것이다. 벽이 두 겹으로 보이는 순간 격자 파라미터를 만지는 것은 시간 낭비다.

11. 관련 문서[편집]

• SLAM · 몬테카를로 위치추정 · 입자 필터 · 오도메트리
• 베이즈 정리 · 칼만 필터 · 센서 융합 · 로지스틱 회귀
• 경로 계획 · A* 알고리즘 · 거리 변환 · 고속 행진법
• 옥트리 · OctoMap · 메시 생성 · 레벨셋 방법
• 자율주행 · DBSCAN · 브레젠험 알고리즘

12. Footnotes[편집]

1. 0.7과 0.4라는 값에 깊은 이론적 근거는 없다. 대부분의 오픈소스 구현이 대략 이 언저리를 기본값으로 들고 있고, 실무자는 “지도가 너무 잘 지워지면 free를 약하게, 유령 벽이 많으면 occ를 약하게” 정도의 감으로 조정한다. 센서 사양서에서 유도한 값이 아니라 현장에서 굳은 값이라는 점을 알고 쓰는 것과 모르고 쓰는 것의 차이는 크다. ↩

2. 유리문이 있는 건물에서 로봇을 돌려 보면 이 문제가 얼마나 실전적인지 바로 안다. 레이저는 유리를 그냥 통과해 버리고, 지도에는 로비 바깥까지 뻥 뚫린 자유공간이 그려지며, 계획기는 신나게 그리로 경로를 뽑는다. 그래서 유리가 많은 건물에는 범퍼 센서나 초음파를 따로 달고, 심하면 지도에 「가상 벽」을 손으로 그려 넣는다. 21세기 로보틱스의 현실적 해법이 종종 마스킹 테이프와 그림판이라는 점은 놀랍도록 변하지 않았다. ↩

3. 모라벡·엘페스가 쓴 폴라로이드 소나는 원래 카메라 자동초점용 부품이었다. 로봇 연구자들이 그걸 링으로 둘러 달고 “측정 하나하나는 못 믿겠지만 확률로 쌓으면 되지 않겠나”를 시도한 것이 이 분야의 시작이다. 싸구려 센서 + 통계라는 조합은 그 뒤로도 로보틱스의 국룰이 됐다. ↩