Occupancy Grid Mapping
**점유 격자(occupancy grid)**는 공간을 셀(2D 정사각형 또는 3D 복셀)로 분할하고, 각 셀 에 대해 그것이 장애물로 점유되어 있을 확률 를 저장합니다. (SLAM에서 얻은) 알려진 로봇 자세와 거리 측정값(LiDAR, 초음파, 깊이 카메라)이 주어지면, 점유 격자 매핑은 각 셀에 대한 여러 잡음 섞인 관측을 융합하여 안정적인 자유/점유/미지 분류로 만들어냅니다 — 이는 경로 계획기가 실제로 소비하는 지도 형식입니다.
셀 단위 이진 베이즈 필터
핵심 모델링 가정은 다음과 같습니다: 각 셀은 이진, 정적 확률 변수(점유 또는 자유, 시간에 따라 변하지 않음)이며, 셀들은 서로 독립입니다. 이 가정 아래에서는 전체 지도에 대한 사후분포가 셀별 사후분포들로 인수분해되며, 각각은 측정값 가 도착할 때마다 이진 베이즈 필터로 업데이트됩니다.
확률을 직접 다루면 업데이트마다 재정규화가 필요합니다. 표준적인 트릭은 로그 오즈(log-odds) 표현입니다.
로그 오즈는 을 로 매핑합니다: 은 미지()를, 양수는 점유일 가능성이 높음을, 음수는 자유일 가능성이 높음을 의미합니다. 로그 오즈 형태에서는 베이즈 업데이트가 단순한 덧셈이 됩니다.
여기서:
- — 측정값 를 반영한 후 해당 셀의 로그 오즈,
- — 역 센서 모델(inverse sensor model): 현재 측정값만으로 시사되는 점유 확률,
- — 사전 로그 오즈(비정보적 사전 에 대해서는 0).
재정규화도 없고, 곱셈도 없습니다 — 각 관측은 그저 일정한 증분을 더할 뿐입니다. 이것이 점유 매핑이 임베디드 로봇에서 실행될 만큼 저렴한 이유입니다.
역 센서 모델과 광선 추적
거리 센서의 경우, 각 빔은 격자 위에서 측정된 광선을 **광선 추적(ray casting)**하여 처리됩니다 (예: Bresenham 선 순회 방식).
- 빔이 히트 지점에 도달하기 전 지나온 셀들은 관측을 통과했으므로 미스(miss) 업데이트를 받습니다: 음의 증분 (예: 역 모델 확률 약 ~).
- 측정된 거리에 위치한 셀은 빔을 반사시켰으므로, 양의 히트(hit) 증분 을 받습니다 (예: 확률 약 ~).
- 히트 지점 너머의 셀들은 가려져 있으므로 — 정보도 없고 업데이트도 없습니다.
일치하는 관측이 반복되면 누적되므로, 20번의 미스와 한 번의 우발적인 히트를 받은 셀도 여전히 명확하게 자유로 읽힙니다. 움직이는 사람은 일시적인 흔적을 남기지만 이후의 미스들이 이를 지워줍니다. 구현체들은 보통 셀이 계속 업데이트 가능하도록 로그 오즈를 최소/최대 범위로 **클램핑(clamp)**하며(이 유계 확신도 클램핑이 바로 OctoMap이 하는 방식입니다), 계획을 위해 셀을 분류할 때 에 임계값(예: )을 적용합니다.
2D 격자, 옥트리, 복셀
평면 2D 격자는 실내 이동 로봇의 고전적인 표현입니다 (ROS nav_msgs/OccupancyGrid). 3D에서는 밀집 격자가 의 메모리를 소모하므로, 실용적인 시스템은 계층적 또는 희소 구조를 사용합니다: OctoMap은 기하 구조가 존재하는 곳에서만 세분화하고 균일한 영역은 가지치기할 수 있는 옥트리에 확률적 점유도를 저장하며, 해시 기반 복셀 맵은 계층 구조 대신 O(1) 접근을 취합니다. 셀 단위 로그 오즈 수식은 이들 모두에서 동일합니다.
SLAM에서의 의미
SLAM은 궤적과 랜드마크/점 지도를 제공하지만 — 희소한 포인트 클라우드는 “이 공간을 지나가도 안전한가?”라는 질문에 답할 수 없습니다. 자유 공간에 대해 아무것도 말해주지 않기 때문입니다. 점유 격자는 자유, 점유, 미지 볼륨을 명시적으로 표현하며, 이는 충돌 검사, 프런티어 기반 탐색, 경로 계획에 필요한 정보입니다. 실제로는 SLAM 시스템이 자세를 제공하고, 점유 매핑기가 자세가 부여된 스캔을 내비게이션 스택이 사용하는 코스트맵으로 변환합니다. 로그 오즈 필터는 또한 원시 기하학적 지도에는 없는, 동적 객체와 센서 잡음에 대한 자연스러운 강건성을 제공합니다.