12.16 점유 격자 지도와 그래프 변환

1. 점유 격자 지도의 개요

점유 격자 지도(Occupancy Grid Map, OGM)는 로봇이 활동하는 환경을 격자(셀) 단위로 분할하고, 각 셀이 장애물에 의해 점유되어 있는지를 나타내는 표현이다. 알베르토 엘페스(Alberto Elfes)와 한스 모라벡(Hans Moravec)이 1980년대에 제안한 이래, 모바일 로봇의 환경 표현과 경로 계획에서 가장 널리 사용되는 방법 중 하나가 되었다. 점유 격자 지도는 직관적이고 구현이 단순하며, 다양한 센서로부터 정보를 통합할 수 있다. 본 절에서는 점유 격자 지도의 정의, 구축 방법, 그리고 그래프로의 변환을 다룬다.

2. 점유 격자 지도의 정의

2.1 격자 분할

환경을 일정 크기의 사각형 셀로 분할한다. 2차원 환경에서는 정사각형 격자가 일반적이며, 3차원 환경에서는 정육면체 셀(복셀, voxel)이 사용된다.

2.2 점유 확률

각 셀에 대해 그 셀이 장애물에 의해 점유되어 있을 확률을 저장한다.

m(c) = P(c \text{ is occupied})

여기서 m(c)는 셀 c의 점유 확률이며, 0 \leq m(c) \leq 1이다.

2.3 셀의 상태

점유 확률에 따라 셀의 상태를 다음과 같이 분류한다.

• 자유 셀(free): m(c)가 임계값(예: 0.5) 미만
• 점유 셀(occupied): m(c)가 다른 임계값 이상
• 미지 셀(unknown): 그 사이의 값

2.4 해상도

격자의 해상도(셀의 크기)는 정확성과 메모리 사용의 균형이다. 작은 셀은 정확하지만 많은 메모리를 사용한다.

3. 점유 격자 지도의 구축

3.1 베이즈 갱신

점유 확률은 베이즈 정리를 사용하여 갱신된다. 새로운 측정값 z가 도착할 때 사후 확률은 다음과 같다.

P(c | z, m_{\text{prev}}) = \frac{P(z | c)P(c | m_{\text{prev}})}{P(z | m_{\text{prev}})}

3.2 로그 확률

수치적 안정성을 위해 점유 확률의 로그 비율(log odds)이 자주 사용된다.

l(c) = \log\frac{P(c | z)}{1 - P(c | z)}

로그 확률에서 베이즈 갱신은 단순한 덧셈이 된다.

l_{\text{new}}(c) = l_{\text{prev}}(c) + l_{\text{meas}}(c) - l_0(c)

여기서 l_{\text{meas}}는 측정에 의한 로그 확률이고, l_0는 사전 로그 확률이다.

3.3 측정 모형

다양한 센서에 대한 측정 모형이 있다.

3.3.1 라이다 측정 모형

라이다 빔이 셀을 통과하면 그 셀은 자유로 갱신된다. 빔이 멈추는 셀은 점유로 갱신된다.

3.3.2 초음파 측정 모형

초음파 센서는 빔의 모양이 더 넓다. 빔 안의 셀들이 비례적으로 갱신된다.

3.3.3 카메라 측정 모형

카메라의 깊이 정보를 사용하여 점유 격자 지도를 갱신할 수 있다.

3.4 빔 모형

빔 모형(beam model)은 각 센서 빔의 정보를 격자에 매핑한다. 일반적으로 빔이 통과하는 셀들과 끝나는 셀이 서로 다르게 갱신된다.

4. 점유 격자 지도의 종류

4.1 D 격자

가장 기본적인 형태이며, 평면 환경에 사용된다. 각 셀은 점유 확률을 저장한다.

4.2 D 격자 (복셀 그리드)

3차원 환경을 위한 점유 격자 지도이다. 메모리 사용이 크다는 단점이 있다.

4.3 옥트리

옥트리(octree)는 3차원 공간을 효율적으로 표현한다. 균일하지 않은 영역을 큰 노드로 표현하여 메모리를 절약한다. OctoMap 라이브러리가 대표적이다.

4.4 다중 해상도 격자

다중 해상도 격자(multi-resolution grid)는 영역에 따라 다른 해상도를 사용한다. 중요한 영역은 높은 해상도, 단순한 영역은 낮은 해상도를 사용한다.

4.5 동적 격자

동적 격자는 환경의 동적 변화를 추적한다. 시간에 따라 셀의 상태가 변할 수 있다.

5. 점유 격자 지도의 장점

5.1 직관성

격자 지도는 직관적이고 시각적으로 이해하기 쉽다.

5.2 단순한 구현

격자의 표현과 갱신이 단순하다.

5.3 다양한 센서의 통합

여러 센서의 정보를 통합하기 쉽다.

5.4 동적 환경의 처리

시간에 따른 변화를 처리할 수 있다.

5.5 그래프로의 자연스러운 변환

격자가 그래프 구조를 자연스럽게 정의한다.

6. 점유 격자 지도의 단점

6.1 메모리 사용

큰 환경에서는 메모리 사용이 크다. 특히 3차원에서는 차원의 저주가 심각하다.

6.2 해상도의 한계

격자의 해상도가 정확성을 제한한다. 작은 객체는 표현하기 어려울 수 있다.

6.3 격자 이산화 오차

연속적인 환경을 격자로 이산화하면서 오차가 발생한다.

7. 그래프로의 변환

7.1 기본 변환

점유 격자 지도를 그래프로 변환하는 가장 단순한 방법은 다음과 같다.

• 자유 셀을 노드로 한다.
• 인접한 자유 셀을 엣지로 연결한다.

이 그래프 위에서 경로 계획 알고리즘이 적용된다.

7.2 방향 vs 8방향

격자의 인접성은 두 가지로 정의된다.

7.2.1 방향 (4-connectivity)

각 셀이 상, 하, 좌, 우의 4개 이웃을 가진다.

def get_neighbors_4(cell, grid):
    r, c = cell
    rows, cols = len(grid), len(grid[0])
    neighbors = []
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
            neighbors.append((nr, nc))
    return neighbors

7.2.2 방향 (8-connectivity)

각 셀이 4방향에 더해 4개의 대각선 이웃을 가진다.

def get_neighbors_8(cell, grid):
    r, c = cell
    rows, cols = len(grid), len(grid[0])
    neighbors = []
    for dr in [-1, 0, 1]:
        for dc in [-1, 0, 1]:
            if dr == 0 and dc == 0:
                continue
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                neighbors.append((nr, nc))
    return neighbors

7.3 가중치

격자 그래프의 엣지 가중치는 응용에 따라 다르다.

• 직선 이동: 1
• 대각선 이동: \sqrt{2}
• 셀의 비용: 표면 거칠기, 위험도 등을 반영

7.4 이산화로 인한 경로의 부자연스러움

격자 그래프 위의 경로는 격자 형태이므로 부자연스러울 수 있다. 이를 해결하기 위한 방법이 있다.

7.4.1 경로 평활화

경로의 중간점을 조정하여 더 매끄럽게 만든다.

7.4.2 Theta* 알고리즘

Theta*는 격자 위에서 직선 경로를 찾는다. 가시성 검사를 활용한다.

7.4.3 Field D*

Field D*는 격자 위에서 비격자 경로를 찾는다.

8. 동적 환경의 처리

8.1 점유 확률의 갱신

새로운 측정이 도착할 때마다 점유 확률이 갱신된다. 동적 객체는 시간에 따라 점유 상태가 변한다.

8.2 그래프의 갱신

점유 확률이 변하면 그래프도 갱신되어야 한다. 동적 알고리즘(D* Lite)이 사용된다.

9. 점유 격자 지도의 응용

9.1 모바일 로봇의 매핑

청소 로봇, 배달 로봇 등 모바일 로봇은 점유 격자 지도를 사용하여 환경을 매핑한다. SLAM 알고리즘이 격자 지도를 동시에 구축하고 위치를 추정한다.

9.2 자율 주행 차량

자율 주행 차량은 도로 환경의 점유 격자 지도를 사용한다. 다른 차량, 보행자, 장애물의 위치를 격자로 표현한다.

9.3 경로 계획

점유 격자 지도는 경로 계획의 기본 표현이다. A* 등의 알고리즘이 격자 그래프 위에서 동작한다.

9.4 탐색

미지의 환경을 탐색할 때 점유 격자 지도가 미지 영역을 표시한다. 미지 영역으로 로봇을 안내한다.

9.5 충돌 회피

실시간 충돌 회피에서 점유 격자 지도가 장애물 정보를 제공한다.

10. SLAM과의 결합

10.1 격자 SLAM

격자 기반 SLAM(grid-based SLAM)은 점유 격자 지도와 로봇의 위치를 동시에 추정한다.

10.2 Gmapping

Gmapping은 입자 필터 기반 SLAM 알고리즘이며, 격자 지도를 사용한다.

10.3 Cartographer

Google의 Cartographer는 라이다 기반 SLAM이며, 격자 지도를 활용한다.

10.4 Hector SLAM

Hector SLAM은 라이다와 격자 지도를 사용한 효율적인 SLAM이다.

11. OctoMap

11.1 개요

OctoMap은 3차원 환경을 위한 효율적인 옥트리 기반 점유 표현이다. 큰 빈 공간을 큰 노드로 표현하여 메모리를 절약한다.

11.2 옥트리 구조

옥트리는 3차원 공간을 8개의 옥탄트로 재귀적으로 분할한다. 균일한 영역은 더 큰 옥탄트로 표현된다.

11.3 응용

OctoMap은 드론, 매니퓰레이터 등 3차원 환경에서 동작하는 로봇에 활용된다.

12. 비용 지도

12.1 비용 지도의 개념

비용 지도(cost map)는 점유 격자 지도의 확장이다. 각 셀에 단순한 점유 확률 대신 이동 비용을 저장한다.

12.2 비용의 계산

비용은 다양한 요소를 고려하여 계산된다.

• 점유 상태
• 장애물까지의 거리
• 동적 객체의 예측 위치
• 표면의 종류

12.3 응용

비용 지도는 자율 주행, 매니퓰레이션, 모바일 로봇 등에서 사용된다. ROS의 nav_costmap 등이 이 개념을 구현한다.

13. 점유 격자 지도의 시각화

13.1 색상 코딩

점유 확률을 색상으로 표현한다.

• 흰색: 자유
• 검은색: 점유
• 회색: 미지

13.2 등고선

점유 확률의 등고선을 그릴 수 있다. 안전 거리를 표현하는 데 유용하다.

13.3 D 시각화

3차원 점유 격자 지도는 3D 시각화 도구로 표현된다.

14. ROS의 점유 격자 지도

14.1 nav_msgs/OccupancyGrid

ROS는 점유 격자 지도를 위한 표준 메시지 타입을 제공한다.

nav_msgs/OccupancyGrid:
  header
  info: MapMetaData
    resolution: float32
    width: uint32
    height: uint32
    origin: Pose
  data: int8[]  # -1: unknown, 0: free, 100: occupied

14.2 map_server

map_server 노드는 점유 격자 지도를 파일로 저장하고 로드한다.

14.3 costmap_2d

costmap_2d는 ROS의 비용 지도 라이브러리이며, 다층 비용 지도를 지원한다.

15. Python 구현

15.1 격자 그래프 구축

def grid_to_graph(grid, threshold=50):
    rows, cols = grid.shape
    graph = {}
    
    for r in range(rows):
        for c in range(cols):
            if grid[r, c] < threshold:  # 자유
                graph[(r, c)] = []
                for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr, nc] < threshold:
                        graph[(r, c)].append((nr, nc))
    
    return graph

15.2 점유 격자 지도의 갱신

def update_grid(grid_log_odds, sensor_measurements, robot_pose):
    for measurement in sensor_measurements:
        cells_traversed = trace_beam(robot_pose, measurement)
        for cell in cells_traversed[:-1]:
            grid_log_odds[cell] -= 0.4  # 자유로 갱신
        grid_log_odds[cells_traversed[-1]] += 0.85  # 점유로 갱신
        
        # 클램핑
        grid_log_odds[cell] = np.clip(grid_log_odds[cell], -2, 3.5)

16. 응용 예시: 청소 로봇

청소 로봇은 점유 격자 지도를 사용하여 방을 매핑한다. 로봇의 라이다나 거리 센서로부터 데이터를 받아 격자를 갱신한다. 매핑 후 격자 지도가 그래프로 변환되고, A*로 경로가 계획된다.

17. 응용 예시: 자율 주행

자율 주행 차량은 도로의 점유 격자 지도를 사용한다. 차선, 다른 차량, 보행자 등이 격자에 표현된다. 비용 지도가 안전한 경로 계획에 활용된다.

18. 응용 예시: 드론

드론은 3차원 점유 격자 지도(OctoMap)를 사용한다. 비행 경로 계획에 활용된다.

19. 응용 예시: 창고 로봇

창고에서 운반 로봇이 격자 지도를 사용하여 이동한다. 격자가 통로와 적재 공간을 구분한다.

20. 응용 예시: 탐색 로봇

미지의 환경을 탐색하는 로봇이 점유 격자 지도를 점진적으로 구축한다. 미지 영역(frontier)으로 로봇을 안내한다.

21. 학습의 가치

점유 격자 지도와 그래프 변환을 이해하는 것은 다음과 같은 이점을 제공한다.

• 모바일 로봇의 환경 표현 표준을 익힌다.
• 센서 데이터로부터 환경 모델을 구축하는 방법을 학습한다.
• 격자 그래프 위의 경로 계획을 이해한다.
• ROS와 같은 표준 프레임워크를 효과적으로 활용할 수 있다.

22. 학습 권장사항

22.1 직접 구현

작은 환경에서 점유 격자 지도를 직접 구축해 본다. 시뮬레이션 데이터로 시작한다.

22.2 ROS 활용

ROS의 map_server, gmapping 등을 사용하여 실제 매핑 작업을 경험한다.

22.3 시각화

점유 격자 지도를 시각화하여 갱신 과정을 관찰한다.

22.4 알고리즘 결합

점유 격자 지도와 경로 계획 알고리즘을 결합한 시스템을 구축한다.

23. 본 절의 의의

본 절은 점유 격자 지도와 그래프 변환을 다루었다. 점유 격자 지도는 모바일 로봇의 환경 표현의 표준이며, 그래프 변환을 통해 경로 계획 알고리즘과 자연스럽게 결합된다. 이 두 개념의 이해는 로봇 매핑과 항법의 기초이다.

24. 참고 문헌

• Elfes, A. (1989). “Using occupancy grids for mobile robot perception and navigation.” Computer, 22(6), 46–57.
• Moravec, H. P. (1988). “Sensor fusion in certainty grids for mobile robots.” AI Magazine, 9(2), 61–74.
• 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.
• Grisetti, G., Stachniss, C., & Burgard, W. (2007). “Improved techniques for grid mapping with Rao-Blackwellized particle filters.” IEEE Transactions on Robotics, 23(1), 34–46.
• Hess, W., Kohler, D., Rapp, H., & Andor, D. (2016). “Real-time loop closure in 2D LIDAR SLAM.” IEEE International Conference on Robotics and Automation, 1271–1278.

version: 1.0