점유 격자 지도 - 라이다로 지도 그리기

이 장에서 배우는 것

앞 장에서 로봇은 주어진 지도를 바탕으로 자신의 위치를 찾았다. 이번에는 로봇의 위치를 안다고 가정하고, 라이다 측정으로 지도를 만든다. 창고 바닥을 작은 정사각형으로 나누고 각 칸에 물체가 있을 가능성을 저장하는 점유 격자 지도(occupancy grid map)를 구현한다. 지도와 위치를 동시에 추정하는 문제는 다루지 않는다.

라이다가 선반까지의 거리를 측정했다면 선반에 해당하는 칸만 알아낸 것이 아니다. 레이저가 지나온 구간은 비어 있다는 증거도 얻었다. 반면 선반 뒤쪽은 관측하지 못했다. 이 세 가지를 구분해야 물체 뒤에 있는 공간을 잘못 비우지 않는다.

• 점유 확률을 로그 오즈(log odds)로 바꾸고, 관측 증거를 덧셈으로 누적한다.
• 광선 추적(ray tracing)으로 라이다 광선이 지나는 격자 칸을 구분한다.
• 반환점이 있는 측정과 최대 거리까지 반환점이 없는 측정을 다르게 갱신한다.
• 해상도가 지도 크기, 계산량, 장애물 표현에 미치는 영향을 설명한다.
• 작은 창고 지도를 만들고, 배열과 문자 출력으로 갱신 결과를 검증한다.

문제 상황

창고 운반 로봇이 통로의 한 지점에서 주변을 측정한다고 하자. 오른쪽에는 선반이 있고, 위쪽에는 적재물이 있다. 왼쪽에서는 센서의 최대 측정 거리까지 물체가 검출되지 않는다. 로봇은 이 측정들을 받아 주변 공간을 지도에 반영해야 한다.

반환점만 점으로 찍으면 장애물의 흔적은 남지만 통로가 비어 있다는 정보는 저장되지 않는다. 반대로 반환점 너머까지 같은 방향으로 칸을 비우면, 선반 뒤의 상자까지 없는 것으로 처리한다. 지도 갱신은 측정이 실제로 제공한 구간에서 끝나야 한다.

측정 한 번으로 칸의 상태를 확정하는 방식도 곤란하다. 선반 모서리에서는 거리값이 흔들리고, 로봇의 위치 오차 때문에 같은 물체가 이웃 칸에 번갈아 나타난다. 따라서 각 칸에는 확정된 이름 대신 점유 가능성을 저장하고, 새 관측이 들어올 때마다 그 값을 조정한다.

실습 공간은 가로 4 m, 세로 3 m다. 격자 한 변은 0.5 m로 정하고, 로봇은 세계 좌표 (1.25, 1.25) m에 둔다. 실습에서는 좌표 변환을 마친 네 개의 라이다 끝점을 직접 제공한다. 거리 측정 장치나 그래픽 창 없이도 지도 갱신 자체를 확인할 수 있는 구성이다.

로봇의 자세 오차, 센서 장착 오차, 움직이는 물체는 이번 코드의 입력에 포함하지 않는다. 실제 측정에서 얻은 거리와 방향을 세계 좌표의 끝점으로 바꾸는 과정은 기본서에서 익힌 좌표 변환을 사용한다. 여기서는 변환된 끝점이 어느 칸에 들어가는지부터 살펴본다.

확률 대신 로그 오즈를 쌓는다

한 칸이 점유되었을 확률을 p라고 하자. 아무것도 관측하지 않았다면 p = 0.5로 시작한다. 이는 그 칸의 절반에 물체가 있다는 뜻이 아니다. 점유와 비점유 중 어느 쪽을 지지할 증거도 아직 없다는 초기 가정이다.

확률에 일정한 수를 계속 더하는 방식은 사용하지 않는다. 확률은 0과 1 사이에 있어야 하고, 이미 높은 확률에 같은 관측이 들어왔을 때의 변화도 고려해야 한다. 대신 점유 확률과 비점유 확률의 비를 구한 뒤 자연로그를 취한다.

점유 오즈 = p / (1 - p)
L = ln(p / (1 - p))
p = 1 / (1 + exp(-L))

L이 0이면 p는 0.5다. L이 양수이면 점유를, 음수이면 빈 공간을 더 지지한다. 확률이 0이나 1에 도달하면 로그 오즈의 크기가 무한대로 발산하므로, 코드에서는 유한한 범위의 값만 저장한다.

현재 관측으로 계산한 한 칸의 점유 확률을 q라고 하자. 이 q를 만드는 규칙이 역 센서 모델(inverse sensor model)이다. 이 장에서는 반환점의 칸에 q = 0.75를, 광선이 통과한 칸에 q = 0.25를 부여한다. 값은 센서 사양에서 자동으로 정해지는 상수가 아니라 실습을 위해 선택한 갱신 강도다.

L_new = L_old + ln(q / (1 - q)) - L_prior
L_prior = ln(p_prior / (1 - p_prior))

p_prior = 0.5일 때:
반환점 칸: L_new = L_old + ln(3)
통과한 칸: L_new = L_old - ln(3)
미관측 칸: L_new = L_old

사전 로그 오즈를 빼는 이유는 관측으로 계산한 q에 포함된 사전 정보를 매번 중복해서 더하지 않기 위해서다. 이번에는 사전 확률이 0.5여서 L_prior가 0이 된다. 초기 확률을 다른 값으로 바꿀 때는 배열의 초기값과 갱신식의 사전 항을 함께 검토해야 한다.

초기 확률 0.5에서 관측 증거를 누적한 결과

관측 이력	로그 오즈	점유 확률
아직 관측하지 않음	0	0.500000
반환점으로 한 번 관측	ln(3)	0.750000
반환점으로 세 번 관측	3 ln(3)	0.964286
빈 공간으로 세 번 관측	−3 ln(3)	0.035714
반환점 한 번, 빈 공간 한 번	0	0.500000

마지막 행은 중요한 구분을 보여 준다. 한 번도 본 적 없는 칸과 서로 반대되는 증거가 상쇄된 칸은 모두 p = 0.5일 수 있다. 확률 배열만으로는 두 경우를 구분할 수 없다. 완성 코드에서는 관측 여부를 별도의 참·거짓 배열에 저장한다.

관측이 반복될 때 로그 오즈를 제한 없이 키우면 나중에 물체가 사라져도 빈 공간으로 바뀌는 데 많은 관측이 필요하다. 실습에서는 L의 범위를 −4 ln(3)부터 4 ln(3)까지 제한한다. 이에 대응하는 확률 범위는 약 0.012195부터 0.987805까지다.

이 제한은 오래된 관측을 지우는 시간 모델은 아니다. 새 관측이 오지 않으면 지도도 그대로 남는다. 또한 한 위치에서 연속으로 얻은 거리값은 서로 관련되어 있을 수 있다. 같은 측정을 여러 번 더한 결과를 현실의 정확한 신뢰도로 해석해서는 안 된다. 반복 횟수는 여기서 누적 동작을 확인하는 장치다.

라이다 광선을 격자 위에 놓는다

세계 좌표를 배열 인덱스로 바꾸기

지도의 왼쪽 아래 모서리를 원점으로 놓고, 오른쪽을 x의 증가 방향, 위쪽을 y의 증가 방향으로 정한다. 배열은 행과 열 순서로 접근하므로 세계 좌표에서 구한 x 방향 칸 번호는 열, y 방향 칸 번호는 행에 대응한다.

column = floor((x - origin_x) / resolution)
row = floor((y - origin_y) / resolution)
저장 위치 = grid[row, column]

해상도가 0.5 m이면 x = 1.25 m는 열 2에 속한다. 열 2가 담당하는 구간은 1.0 m 이상, 1.5 m 미만이다. 왼쪽 경계는 포함하고 오른쪽 경계는 제외하는 규칙을 모든 칸에 적용한다. 따라서 지도의 오른쪽 끝인 x = 4.0 m는 지도 밖이다.

내림 연산과 정수 변환은 음수에서 다르다. 예를 들어 −0.1을 0.5로 나눈 결과를 정수로 바꾸면 0이 되지만, 내림하면 −1이 된다. 지도 밖 좌표를 첫 번째 칸으로 잘못 넣지 않으려면 내림한 뒤 범위를 검사해야 한다.

통과한 칸과 반환점 칸 구분하기

연속 공간의 선분을 격자 칸의 열로 바꾸는 데 브레젠험 알고리즘(Bresenham algorithm)을 사용한다. 시작 칸에서 끝 칸까지 이동하면서 정수 오차를 누적하고, 오차의 크기에 따라 열과 행을 한 칸씩 움직인다. 결과에는 시작 칸과 끝 칸이 모두 들어간다.

반환점이 있는 광선에서는 중간 칸을 빈 공간으로 갱신하고, 마지막 칸만 점유로 갱신한다. 반환점 뒤쪽은 순회하지 않는다. 반환점이 없는 유효한 최대 거리 측정에서는 마지막 칸까지 빈 공간으로 갱신한다.

센서가 놓인 시작 칸은 갱신에서 제외한다. 여러 광선이 같은 시작 칸을 공유하므로 이를 매번 비우면 시작 칸에 증거가 과도하게 쌓인다. 로봇이 차지하는 면적을 지도에서 비우는 일은 별도 규칙으로 다룰 수 있지만 이번 코드에는 넣지 않는다.

실습의 광선 추적은 격자 시작점과 끝점을 연결하는 얇은 정수 선을 만든다. 실제 선분이 조금이라도 스치는 모든 칸을 열거하는 방식은 아니다. 또한 연속 좌표를 먼저 칸으로 바꾸므로 한 칸 안에서 끝점이 이동한 정보는 사라진다. 센서의 광선 폭과 칸 내부의 부분 점유도 표현하지 않는다.

이 단순화 아래에서는 최대 거리 끝점이 속한 칸도 빈 칸으로 갱신한다. 실제로는 광선이 그 칸 전체를 통과했다고 보장할 수 없다. 장애물 경계를 보수적으로 보존해야 한다면 끝점 근처의 불확실한 칸을 갱신에서 제외하거나, 센서 오차를 반영한 별도 모델이 필요하다.

반환점이 없다는 사실과 센서 읽기 실패도 구분해야 한다. 최대 거리까지 유효하게 측정했지만 반환점이 없는 경우는 빈 공간의 증거가 된다. 통신 오류나 유효하지 않은 거리값은 그런 증거가 아니다. 코드의 hit=False는 유효한 최대 거리 측정만 의미한다.

지도의 경계에서 멈추는 규칙

실제 라이다 끝점은 지도 밖에 놓일 수 있다. 이때 끝점 인덱스를 지도 가장자리에 강제로 맞추고 점유 처리하면 테두리에 가짜 장애물이 생긴다. 범용 구현에서는 광선을 지도 경계에서 잘라 내부 구간만 비우고, 지도 밖 반환점은 점유 칸으로 기록하지 않아야 한다.

완성 코드는 경계 자르기를 구현하지 않고 지도 밖 좌표에 예외를 발생시킨다. 작은 고정 지도의 입력 오류를 분명하게 드러내기 위한 선택이다. 네 개의 예제 광선은 모두 지도 내부에서 끝나므로 정상 실행에서는 예외가 발생하지 않는다.

해상도는 정보와 비용을 함께 바꾼다

해상도는 격자 한 변의 실제 길이다. 이 길이를 줄이면 더 작은 장애물과 좁은 틈을 구분할 수 있지만 칸 수가 늘어난다. 같은 면적에서 한 변의 길이를 절반으로 줄이면 가로와 세로 칸 수가 각각 두 배가 되므로 전체 칸 수는 네 배가 된다.

가로 4 m, 세로 3 m 지도의 해상도별 저장 비용

해상도	열 × 행	전체 칸 수	로그 오즈 배열
0.50 m	8 × 6	48	384바이트
0.25 m	16 × 12	192	1,536바이트
0.10 m	40 × 30	1,200	9,600바이트

표의 저장 비용은 칸마다 8바이트인 실수 배열 하나만 계산한 값이다. 관측 여부 배열, 출력용 확률 배열, 파이썬 객체의 부가 비용은 포함하지 않는다. 지도의 실제 크기가 해상도로 나누어떨어지지 않는다면 칸 수를 올림하고, 만들어진 지도가 요청한 영역보다 조금 커지는지도 명시해야 한다.

해상도를 줄이면 광선 하나가 방문하는 칸 수도 늘어난다. 동일한 물리적 길이를 추적할 때 한 변의 길이를 절반으로 줄이면 방문 칸 수는 대략 두 배가 된다. 지도 전체 저장량의 증가와 광선 하나의 처리량 증가는 서로 다른 비율이라는 점을 구분한다.

작은 칸이 항상 더 유용한 것도 아니다. 로봇 위치가 수십 센티미터씩 흔들리는데 칸 크기를 몇 센티미터로 정하면, 같은 선반의 반환점이 여러 칸에 퍼져 두꺼운 띠처럼 나타날 수 있다. 해상도는 표현하려는 장애물 크기뿐 아니라 센서와 위치 추정의 오차도 고려해서 정한다.

이번 0.5 m 격자는 얇은 기둥이나 실제 통로 폭을 정밀하게 표현하기 위한 선택이 아니다. 손으로 칸 번호와 갱신 횟수를 확인하기 위한 크기다. 한 칸이 비어 있다는 결과만으로 로봇 전체가 통과할 수 있다고 해석하지 않는다. 로봇의 크기와 이동 가능성 판단은 점유 측정과 구분되는 문제다.

완성 코드

다음 프로그램을 occupancy_grid.py로 저장한다. Python 3와 numpy가 설치된 환경에서 실행할 수 있다. 난수 시드는 7로 고정하지만 예제 입력에는 난수를 사용하지 않는다. 네 광선을 같은 순서로 세 번 반영하므로 출력은 실행할 때마다 같다.

각 광선은 끝점 좌표와 반환점 유무로 구성한다. 오른쪽, 위쪽, 오른쪽 위의 광선은 반환점이 있고, 왼쪽 광선은 최대 거리까지 반환점이 없다. 지도 출력은 위쪽 행부터 보여 주며, 내부 배열의 행 번호는 아래쪽에서부터 증가한다.

import math
import numpy as np


RESOLUTION = 0.5
WIDTH = 8
HEIGHT = 6
ORIGIN = (0.0, 0.0)

HIT_DELTA = float(np.log(3.0))
FREE_DELTA = -HIT_DELTA
LIMIT = 4.0 * HIT_DELTA


def world_to_cell(x, y):
    if not (math.isfinite(x) and math.isfinite(y)):
        raise ValueError("coordinates must be finite")
    column = math.floor((x - ORIGIN[0]) / RESOLUTION)
    row = math.floor((y - ORIGIN[1]) / RESOLUTION)
    if not (0 <= column < WIDTH and 0 <= row < HEIGHT):
        raise ValueError("point outside map")
    return column, row


def trace_cells(start, end):
    x0, y0 = start
    x1, y1 = end
    dx = abs(x1 - x0)
    dy = -abs(y1 - y0)
    sx = 1 if x0 < x1 else -1
    sy = 1 if y0 < y1 else -1
    error = dx + dy
    cells = []

    while True:
        cells.append((x0, y0))
        if x0 == x1 and y0 == y1:
            return cells
        doubled = 2 * error
        if doubled >= dy:
            error += dy
            x0 += sx
        if doubled <= dx:
            error += dx
            y0 += sy


def update_beam(log_odds, observed, sensor, endpoint, hit):
    start = world_to_cell(*sensor)
    end = world_to_cell(*endpoint)
    if start == end:
        raise ValueError("beam must leave the sensor cell")

    cells = trace_cells(start, end)
    free_cells = cells[1:-1] if hit else cells[1:]

    for column, row in free_cells:
        value = log_odds[row, column] + FREE_DELTA
        log_odds[row, column] = np.clip(value, -LIMIT, LIMIT)
        observed[row, column] = True

    if hit:
        column, row = cells[-1]
        value = log_odds[row, column] + HIT_DELTA
        log_odds[row, column] = np.clip(value, -LIMIT, LIMIT)
        observed[row, column] = True


def make_symbols(probability, observed):
    symbols = np.full(probability.shape, "?", dtype="<U1")
    symbols[observed] = "~"
    symbols[observed & (probability <= 0.30)] = "."
    symbols[observed & (probability >= 0.70)] = "#"
    return symbols


def main():
    np.random.seed(7)
    log_odds = np.zeros((HEIGHT, WIDTH), dtype=np.float64)
    observed = np.zeros((HEIGHT, WIDTH), dtype=bool)
    sensor = (1.25, 1.25)
    beams = [
        ((3.25, 1.25), True),
        ((1.25, 2.25), True),
        ((2.75, 2.75), True),
        ((0.25, 1.25), False),
    ]

    for _ in range(3):
        for endpoint, hit in beams:
            update_beam(log_odds, observed, sensor, endpoint, hit)

    probability = 1.0 / (1.0 + np.exp(-log_odds))
    symbols = make_symbols(probability, observed)
    occupied_count = int(np.count_nonzero(symbols == "#"))
    free_count = int(np.count_nonzero(symbols == "."))
    uncertain_count = int(np.count_nonzero(symbols == "~"))
    unseen_count = int(np.count_nonzero(symbols == "?"))

    print(f"grid: {WIDTH} x {HEIGHT}, resolution: {RESOLUTION:.2f} m")
    print("scans: 3, beams per scan: 4")
    print(f"log-odds bytes: {log_odds.nbytes}")
    print(f"occupied={occupied_count}, free={free_count}, "
          f"uncertain={uncertain_count}, unseen={unseen_count}")
    print(f"p(hit cell)={probability[2, 6]:.6f}")
    print(f"p(free cell)={probability[2, 3]:.6f}")
    print(f"p(unseen cell)={probability[0, 0]:.6f}")

    display = symbols.copy()
    column, row = world_to_cell(*sensor)
    display[row, column] = "R"
    print("map: top row first")
    for row in range(HEIGHT - 1, -1, -1):
        print("".join(display[row].tolist()))
    print("legend: # occupied, . free, ~ uncertain, ? unseen, R robot")


if __name__ == "__main__":
    main()

줄별 해설

RESOLUTION은 칸의 실제 길이이고 WIDTH와 HEIGHT는 칸 수다. 단위가 서로 다르므로 혼동하지 않는다. ORIGIN은 첫 번째 칸의 중심이 아니라 지도 영역의 왼쪽 아래 모서리다.

HIT_DELTA는 ln(3)을 한 번 계산해 저장한다. FREE_DELTA는 그 반대 부호이며, LIMIT는 같은 방향의 증거 네 번에 해당하는 크기다. 갱신 강도를 바꾸더라도 점유와 빈 공간에 반드시 같은 크기를 사용할 필요는 없다.

world_to_cell()의 첫 조건문은 무한대와 유효하지 않은 수를 거부한다. 이어지는 두 줄은 원점을 뺀 거리를 칸 크기로 나누고 내림한다. 마지막 조건문은 음수 인덱스가 배열 끝에서부터 접근하는 파이썬 동작을 막는다. 범위 검사는 배열 접근 전에 수행한다.

trace_cells()에서 dx는 열 차이의 크기이고 dy는 행 차이의 크기에 음수를 붙인 값이다. sx와 sy는 각 축의 진행 방향이다. error는 다음 칸을 선택하기 위한 정수 오차이며 물리적 거리나 센서 오차가 아니다.

반복문은 현재 칸을 넣은 뒤 도착 여부를 검사한다. 따라서 끝 칸도 결과에 포함된다. doubled는 축을 움직이기 전 오차의 두 배를 보존한다. 뒤의 두 조건은 독립적인 if문이므로 한 반복에서 열과 행이 모두 바뀔 수 있다. 이를 if와 elif로 바꾸면 대각선 진행 규칙이 달라진다.

update_beam()은 두 끝점을 모두 검사한 뒤 배열을 수정한다. 시작과 끝이 같은 칸이면 예외를 낸다. 이번 모델은 센서가 있는 칸을 제외하므로, 그 칸 안에서 끝나는 짧은 측정의 의미를 조용히 임의로 정하지 않기 위해서다.

cells[1:-1]은 시작과 반환점을 제외한 중간 칸이다. cells[1:]은 시작만 제외하므로 최대 거리 끝 칸도 포함한다. 빈 칸 반복문과 반환점 조건문은 서로 겹치지 않는 칸을 수정한다. 각 수정 직후 np.clip()으로 저장 범위를 제한하고 관측 표시를 남긴다.

make_symbols()는 표시 정책을 별도 함수로 둔다. 먼저 전체를 미관측 기호로 채우고, 관측한 칸만 미확정 기호로 바꾼다. 그중 확률이 0.30 이하이면 빈 공간, 0.70 이상이면 점유로 표시한다. 두 문턱 사이에 간격을 둬 증거가 약하거나 상충하는 칸을 따로 보여 준다.

main()의 두 배열은 모두 (HEIGHT, WIDTH) 형태다. 로그 오즈는 0으로 시작하므로 모든 초기 확률은 0.5다. 관측 여부는 모두 거짓으로 시작한다. 중첩 반복문은 광선 순서를 유지하면서 총 열두 번의 갱신 함수를 호출한다.

확률 변환은 갱신을 모두 마친 뒤 한 번 수행한다. 로그 오즈의 크기가 제한되어 있으므로 이 예제의 지수 계산은 큰 값으로 넘치지 않는다. 통계는 로봇 기호를 덮어쓰기 전에 계산한다. 따라서 로봇 칸은 화면에서는 R로 보이지만 통계에서는 미관측 칸에 포함된다.

마지막 반복문은 행 번호를 5부터 0까지 감소시킨다. 배열의 첫 번째 행을 화면 맨 위에 출력하면 정의한 세계 좌표와 상하가 뒤집힌다. display는 복사본이므로 로봇 위치를 표시해도 확률과 분류 결과는 바뀌지 않는다.

실행 결과

다음 명령은 소스를 바이트 코드로 컴파일한 뒤 프로그램을 실행한다. -W error는 발생한 경고를 오류로 취급한다. 정상적으로 컴파일되면 첫 번째 명령은 아무것도 출력하지 않는다.

python3 -W error -m py_compile occupancy_grid.py
python3 -W error occupancy_grid.py

예상 출력은 다음과 같다.

grid: 8 x 6, resolution: 0.50 m
scans: 3, beams per scan: 4
log-odds bytes: 384
occupied=3, free=8, uncertain=0, unseen=37
p(hit cell)=0.964286
p(free cell)=0.035714
p(unseen cell)=0.500000
map: top row first
?????#??
??#?.???
??..????
..R...#?
????????
????????
legend: # occupied, . free, ~ uncertain, ? unseen, R robot

오른쪽 광선은 열 3, 4, 5를 비우고 열 6을 점유로 만든다. 위쪽 광선은 칸 (2, 3)을 비우고 (2, 4)를 점유로 만든다. 대각선 광선은 (3, 3), (4, 4)를 비우고 (5, 5)를 점유로 만든다. 괄호 안의 순서는 열, 행이다.

왼쪽 광선은 반환점이 없으므로 (1, 2)와 (0, 2)를 모두 비운다. 이에 따라 빈 칸은 8개, 점유 칸은 3개다. 나머지 37개에는 증거를 넣지 않았다. 전체 48개와 각 분류의 합이 맞는지 확인하면 출력 기호만 볼 때 놓치기 쉬운 누락을 찾는 데 도움이 된다.

세 번의 점유 갱신은 오즈를 27로 만들므로 확률은 27/28이다. 빈 공간 갱신의 확률은 1/28이다. 이번 실행에서는 같은 칸에 반대 증거가 들어오지 않았기 때문에 미확정 칸은 0개다. 이 결과는 표시 문턱과도 일치한다.

실무에서 자주 틀리는 것

반환점까지 비운 뒤 다시 점유시키기

다음 코드는 반환점이 있는 경우에도 마지막 칸을 먼저 비운다. 이번처럼 두 갱신의 크기가 같으면 빈 공간 증거와 점유 증거가 상쇄된다. 장애물을 여러 번 보아도 확률이 초기값 근처에 머물 수 있다.

# 틀린 코드: 뒤에서 마지막 칸을 점유로 갱신한다고 가정한다.
free_cells = cells[1:]

# 고친 코드
free_cells = cells[1:-1] if hit else cells[1:]

반환점 칸에는 점유 증거만 넣는다. 다만 실제 센서 오차를 반영해 반환점 주변 여러 칸에 증거를 분산시키는 모델은 별도로 설계할 수 있다. 단순한 중복 갱신과 의도적인 오차 모델은 구분해야 한다.

좌표 순서 그대로 배열에 접근하기

좌표 변환 함수가 반환하는 순서는 열, 행이지만 배열 인덱스의 순서는 행, 열이다. 정사각형 지도에서는 잘못된 접근이 범위 안에 들어가 오류 없이 지나갈 수 있어 더 알아차리기 어렵다.

# 틀린 코드
column, row = world_to_cell(*endpoint)
log_odds[column, row] += HIT_DELTA

# 고친 코드
column, row = world_to_cell(*endpoint)
value = log_odds[row, column] + HIT_DELTA
log_odds[row, column] = np.clip(value, -LIMIT, LIMIT)

변수명을 x와 y로만 유지하기보다 배열로 넘어가는 시점에 column과 row로 바꾸면 검토하기 쉽다. 가로와 세로 크기가 다른 예제로 확인하는 것도 전치 오류를 드러내는 데 도움이 된다.

지도 밖 음수 좌표를 첫 칸으로 넣기

정수 변환은 소수 부분을 0 방향으로 버린다. 지도 원점 바로 왼쪽의 좌표가 열 0으로 바뀌면 범위 검사도 통과한다. 내림을 사용하고 결과가 음수인지 확인해야 한다.

# 틀린 코드
column = int((x - ORIGIN[0]) / RESOLUTION)

# 고친 코드
column = math.floor((x - ORIGIN[0]) / RESOLUTION)
if not 0 <= column < WIDTH:
    raise ValueError("point outside map")

행에도 같은 규칙을 적용한다. 범위를 벗어난 인덱스를 0이나 마지막 인덱스로 고정하는 방식은 입력 오류를 숨기며, 지도 가장자리의 관측 이력을 왜곡할 수 있다.

확률만 보고 미관측이라고 판단하기

점유 증거와 빈 공간 증거가 상쇄된 칸은 관측 이력이 있어도 확률이 0.5다. 부동소수점의 정확한 동등 비교 문제를 해결하더라도 관측 이력 자체를 복원할 수는 없다.

# 틀린 코드
unseen = probability == 0.5

# 고친 코드
unseen = ~observed
uncertain = observed & (probability > 0.30) & (probability < 0.70)

관측 여부와 확률은 서로 다른 질문에 답한다. 전자는 센서 증거를 넣었는지, 후자는 현재 어느 상태를 더 지지하는지 나타낸다. 재관측이 필요한 영역을 찾을 때도 이 구분을 보존하는 편이 유용하다.

한눈에 보기

점유 격자 구현에서 유지할 규칙

항목	이번 구현의 규칙	확인할 점
초기 상태	L = 0, 관측 여부는 거짓	확률 0.5와 관측 이력을 구분한다.
빈 공간	−ln(3)을 더한다.	반환점이 있으면 끝 칸을 제외한다.
반환점	ln(3)을 더한다.	반환점 뒤는 갱신하지 않는다.
최대 거리	끝 칸까지 빈 공간으로 처리한다.	센서 읽기 실패와 구분한다.
좌표와 배열	내림 후 [행, 열]로 접근한다.	음수와 지도 상한을 검사한다.
누적 제한	±4 ln(3)으로 제한한다.	관측 순서에 따라 결과가 달라질 수 있다.
해상도	한 칸의 길이는 0.5 m다.	길이를 절반으로 줄이면 칸 수는 네 배다.

이 장에서 만든 지도는 각 칸의 점유 증거를 저장한다. 다음 장에서는 격자 위의 이동을 그래프로 표현하고 경로를 찾는다. 그때도 미관측과 관측된 빈 공간을 같은 상태로 취급할지는 별도의 정책으로 정해야 한다.

연습 문제

1. 완성 코드의 세 번 갱신을 마친 뒤, 오른쪽 광선의 끝점은 그대로 두고 hit=False인 관측을 한 번 추가한다고 하자. 칸 (6, 2)의 로그 오즈와 점유 확률, 표시 기호를 구하라. 이 입력 변경이 센서 측정에서 무엇을 뜻하는지도 설명하라.
2. 지도 크기를 가로 4 m, 세로 3 m로 유지하면서 해상도를 0.25 m로 바꾼다. 열 수, 행 수, 로그 오즈 배열의 바이트 수와 로봇의 칸 번호를 구하라. 해상도만 수정하고 WIDTH와 HEIGHT를 유지하면 무엇이 달라지는가.
3. 로봇 위치에서 왼쪽 끝점 (0.25, 1.25)까지 추적한 칸을 순서대로 적어라. 반환점 유무에 따라 빈 공간과 점유로 갱신되는 칸을 비교하라.
4. 미관측 칸에 점유 증거 한 번과 빈 공간 증거 한 번을 넣었다. 이 칸의 확률과 표시 기호를 구하라. 이어서 점유 갱신 다섯 번 뒤 빈 공간 갱신 한 번을 수행한 경우와, 그 순서를 반대로 한 경우의 최종 로그 오즈를 비교하라. 각 경우는 미관측 칸에서 새로 시작한다.

정답과 해설

1. 기존 로그 오즈는 3 ln(3)이다. 반환점 없는 광선을 한 번 더 넣으면 마지막 칸도 빈 공간으로 갱신하므로 2 ln(3)이 된다. 오즈는 9이고 점유 확률은 9/10, 즉 0.9다. 여전히 점유 문턱 0.70 이상이므로 기호는 #이다. 추가 입력은 센서가 해당 끝점까지 유효하게 측정했지만 물체를 검출하지 못했다는 뜻이다. 단순히 반환점 정보가 누락되었다는 뜻으로 사용하면 안 된다.

2. 열 수는 16, 행 수는 12이며 총 192칸이다. 로그 오즈 배열은 192 × 8 = 1,536바이트다. 로봇의 열과 행은 각각 floor(1.25/0.25) = 5이므로 칸 번호는 (5, 5)다. WIDTH와 HEIGHT를 유지하면 지도 영역이 가로 2 m, 세로 1.5 m로 줄어든다. 기존 광선 끝점 일부가 지도 밖이 되어 예외가 발생한다.

3. 추적 결과는 (2, 2), (1, 2), (0, 2)다. 시작 칸 (2, 2)는 갱신하지 않는다. 반환점이 없으면 (1, 2)와 (0, 2)를 모두 비운다. 반환점이 있으면 (1, 2)만 비우고 (0, 2)는 점유로 갱신한다. 끝점 좌표가 같아도 반환점 유무에 따라 마지막 칸의 의미가 달라진다.

4. 한 번씩 상반된 증거를 넣으면 로그 오즈는 0이고 확률은 0.5다. 관측 여부는 참이므로 기호는 ~다. 뒤의 비교에서 점유 갱신 다섯 번을 먼저 넣으면 상한 때문에 4 ln(3)에서 멈추고, 빈 공간 갱신 후에는 3 ln(3)이 된다. 순서를 반대로 하면 −ln(3)에서 시작해 점유 증거 다섯 번을 더하므로 최종값은 4 ln(3)이다. 제한 없는 덧셈과 달리 매번 범위를 자르는 누적은 관측 순서의 영향을 받는다.