샘플링 기반 계획 - RRT

이 장에서 배우는 것

앞 장에서 격자의 칸을 정점으로 삼고 이웃 칸을 연결해 경로를 찾았다. 창고가 넓어지거나 위치를 더 세밀하게 표현하려면 칸 수가 늘어난다. 이번에는 공간 전체를 먼저 나누지 않고, 필요한 곳에 위치 후보를 조금씩 추가한다. 로봇이 갈 수 있는 짧은 이동을 연결하면서 출발점에서 뻗어 나가는 트리를 만든다.

이 방법을 빠르게 탐색하는 무작위 트리(Rapidly-exploring Random Tree, RRT)라고 한다. 이름에 무작위가 들어가지만 충돌 판정까지 임의로 처리하는 것은 아니다. 후보 위치를 뽑는 과정만 확률적이며, 트리에 추가하는 모든 이동은 같은 충돌 검사 규칙을 통과해야 한다. 이 장에서는 창고 선반을 돌아가는 경로를 만들고, 불필요한 굴곡을 줄인다.

• 표본 위치, 최근접 노드, 확장 길이로 트리가 자라는 과정을 구현한다.
• 목표 편향이 탐색 방향을 바꾸는 원리를 설명하고 탐색 실패를 처리한다.
• 로봇의 크기를 반영하고 이동 선분 전체의 충돌 여부를 검사한다.
• 부모 관계에서 경로를 복원하고 충돌 없는 지름길로 경로를 다듬는다.

문제 상황

가로 12m, 세로 8m인 창고에서 로봇이 왼쪽 아래의 적재 지점에서 오른쪽 아래의 출고 지점으로 이동한다. 출발점은 (1, 1), 목표점은 (11, 1)이다. 두 지점 사이에는 x가 4m부터 6m까지, y가 0m부터 6m까지인 선반이 있다. 직선으로 이동하면 선반을 통과하므로, 위쪽 통로를 이용해 돌아가야 한다.

로봇은 반지름 0.25m인 원으로 근사한다. 위치 추정 오차와 동적 장애물은 이번 실습에 포함하지 않는다. 지도와 현재 위치가 주어졌다는 조건에서 충돌 없는 위치 경로를 찾는 문제만 다룬다. 경로는 순서가 있는 좌표 목록이며, 이웃한 두 좌표 사이를 직선으로 연결해 해석한다.

차동 구동 로봇은 제자리 회전이 가능하다고 가정한다. 따라서 원형 로봇의 중심이 통과할 수 있는 선분 경로를 계획 대상으로 삼을 수 있다. 다만 여기서 얻는 꺾인 선은 주행 속도나 회전 시간을 담고 있지 않다. 통과 가능한 위치를 정하는 일과 실제로 따라갈 움직임을 만드는 일을 구분해야 한다.

이번 지도는 격자로도 충분히 풀 수 있다. 같은 문제를 다른 방식으로 구현하는 이유는 탐색 구조가 달라지는 지점을 비교하기 위해서다. 격자는 미리 정한 이웃을 따라가지만, 이번 트리는 뽑힌 표본에 따라 연결 방향을 바꾼다. 어느 방법이 빠른지는 지도 크기, 통로 폭, 해상도, 충돌 검사 비용에 따라 달라진다.

격자 탐색과 무작위 트리는 공간을 표현하고 연결하는 방식이 다르다

비교 항목	격자 탐색	이번 무작위 트리
위치 후보	미리 정한 칸의 대표점	탐색 중 생성한 실수 좌표
연결 방향	정해 둔 이웃 방향	최근접 노드에서 표본을 향한 방향
주요 조절값	격자 해상도와 이동 비용	확장 길이와 목표 편향
결과 해석	격자 그래프 위의 경로	이번 탐색에서 발견한 가능한 경로

표본을 향해 자라는 트리

트리의 첫 노드는 출발점이다. 이후에는 창고 안에서 표본 하나를 뽑고, 현재 노드 중 표본에 가장 가까운 노드를 찾는다. 그 노드에서 표본 방향으로 짧게 이동한 위치를 새 후보로 만든다. 최근접 노드에서 후보까지의 선분이 비어 있으면 후보를 트리에 넣는다. 충돌하면 후보만 버리고 다음 표본을 뽑는다.

최근접 노드를 q, 표본을 s라고 하자. 두 점의 차이 d는 s − q이고 거리는 그 차이의 유클리드 길이다. 거리가 확장 길이보다 크면 d를 단위 방향으로 만든 뒤 확장 길이만큼 이동한다. 거리가 더 짧으면 표본 자체가 후보가 된다. 확장 길이는 한 번에 추가할 선분의 최대 길이이며, 매번 그 길이만큼 이동해야 한다는 뜻은 아니다.

표본은 방향을 제안하는 역할을 한다. 표본 자체가 선반 안에 있더라도, 그 방향으로 짧게 뻗은 후보와 연결 선분이 비어 있으면 추가할 수 있다. 따라서 이 구현은 표본의 유효성을 먼저 요구하지 않는다. 실제 트리에 들어갈 후보와 그 후보까지의 이동을 검사한다.

표본에서 가장 가까운 노드를 선택하는 규칙 때문에 트리는 아직 덜 탐색한 쪽으로 뻗는 경향을 보인다. 노드가 적은 영역 근처의 가지는 넓은 영역의 표본에 대해 최근접 노드가 될 수 있다. 그렇다고 매번 새로운 영역으로 나아가는 것은 아니다. 선반을 향한 확장은 반복해서 거절될 수 있고, 좁은 입구를 찾는 데 표본을 많이 쓸 수도 있다.

각 새 노드에는 연결의 출발점인 부모 노드 번호를 기록한다. 부모는 이미 트리에 있던 노드이므로 번호가 새 노드보다 작다. 목표에 도달한 뒤 부모를 계속 따라가면 출발점에 이른다. 이 목록은 목표에서 출발점 순서로 얻어지므로 마지막에 뒤집는다. 탐색 중 만들어진 다른 가지들은 최종 경로에 들어가지 않는다.

그림에서 점선 끝의 표본까지 한 번에 연결하지 않는 이유는 확장을 지역적인 이동으로 제한하기 위해서다. 확장 길이를 작게 하면 통로 주변에서 방향을 세밀하게 바꿀 수 있지만 노드가 많아진다. 크게 하면 넓은 공간을 적은 노드로 가로지를 수 있지만 장애물을 가로지르는 후보가 자주 거절될 수 있다. 작은 값이나 큰 값 어느 쪽도 모든 지도에 유리하지 않다.

이번 코드는 최근접 노드를 찾을 때 모든 노드와의 거리를 계산한다. 노드가 n개면 한 번의 검색에 n개를 비교한다. 구현은 읽기 쉽지만 노드 수가 크게 늘면 검색 비용이 커진다. 실습에서는 최대 시도 수를 제한해 이 구조를 유지하고, 검색 자료구조의 교체보다 탐색과 충돌 검사의 관계에 집중한다.

목표 편향과 선분 충돌 검사

목표를 자주 뽑되 다른 방향도 남긴다

매번 균일한 무작위 위치만 뽑으면 목표 근처까지 트리가 자라도 정확한 목표 좌표를 뽑기는 어렵다. 목표 편향은 정해 둔 확률로 목표점을 표본으로 선택하는 방법이다. 이번에는 확률을 0.15로 둔다. 각 시도에서 목표를 뽑을 확률이 15%라는 뜻이며, 열 번 중 정해진 횟수만큼 목표를 선택한다는 뜻은 아니다.

목표 편향이 있으면 목표와 가까운 가지가 목표 방향으로 뻗을 기회가 늘어난다. 그러나 목표 방향이 선반으로 막혀 있다면 같은 연결이 반복해서 거절될 수 있다. 특히 이 지도에서 확률을 1로 두면 모든 표본이 목표점이 된다. 트리는 아래쪽 직선 방향으로만 자라다가 선반 앞에서 막혀 위쪽 통로를 찾지 못한다.

후보를 하나 추가한 뒤에는 목표까지의 거리도 확인한다. 목표가 확장 길이 안에 있고 연결 선분이 비어 있으면 목표를 붙이고 종료한다. 거리 조건과 충돌 조건을 함께 확인해야 한다. 목표 가까이에 왔다는 이유만으로 종료하면 마지막 선분이 선반 모서리를 가로지를 수 있다.

최대 시도 수는 성공 여부와 별개인 계산 예산이다. 모든 시도는 표본 하나를 처리하며, 거절된 후보도 시도 수를 소비한다. 예산을 다 쓰면 이번 실행에서는 경로를 찾지 못했다고 보고한다. 이것만으로 경로가 존재하지 않는다고 결론 내릴 수는 없다. 통로가 있어도 표본이 적절한 곳에 충분히 모이지 않았을 수 있다.

무한히 많은 시도를 생각하는 이론적 성질과 유한한 실행의 성공 보장은 구분해야 한다. 자유 공간과 연결 방식에 적절한 조건이 있으면 시도 수를 늘릴수록 성공 확률이 높아지는 성질을 논할 수 있다. 그러나 실제 로봇에서는 대기 시간을 제한해야 하며, 목표 편향이나 고정 시드가 그 시간 안의 성공을 보장하지는 않는다.

로봇의 중심이 움직일 공간을 만든다

로봇 중심을 점으로 검사하려면 먼저 로봇의 크기를 지도에 반영해야 한다. 선반의 네 변을 반지름만큼 바깥으로 옮기고, 창고의 이동 가능 경계는 반지름만큼 안으로 옮긴다. 그러면 중심점이 선반과 너무 가깝거나 외벽에 닿는 이동을 걸러낼 수 있다.

원형 로봇과 직사각형 선반의 정확한 금지 영역은 모서리가 둥근 형태다. 이번 구현은 모서리까지 직사각형으로 채워서 검사한다. 따라서 모서리 부근에서 실제 원형 로봇이 지나갈 수 있는 일부 공간도 막는다. 계산을 단순하게 만드는 보수적인 근사이며, 좁은 통로에서는 이 차이가 경로 존재 여부에 영향을 줄 수 있다.

끝점만 검사해서는 이동 중 충돌을 알 수 없다. 예를 들어 (2, 3)과 (8, 3)은 모두 선반 밖에 있지만 두 점을 잇는 선분은 선반을 관통한다. 이 장의 충돌 함수는 점을 일정 간격으로 찍는 대신, 선분과 직사각형의 겹침을 직접 계산한다. 따라서 검사 간격보다 얇은 장애물을 건너뛰는 문제를 피한다.

선분의 점은 a + t(b − a)로 나타낼 수 있고 t는 0부터 1까지다. 먼저 가능한 t 구간을 [0, 1]로 둔다. x축에서 점이 직사각형의 좌우 경계 사이에 있을 t 구간을 구해 겹치는 부분만 남긴다. y축에서도 같은 일을 한다. 마지막까지 구간이 남으면 두 축 조건을 동시에 만족하는 점이 있으므로 충돌이다.

어떤 축의 이동량이 0이면 나눗셈을 하지 않는다. 그 축의 좌표가 직사각형 범위 밖이면 선분 전체가 직사각형을 빗겨 간다. 범위 안이면 다른 축의 결과로 판단한다. 두 구간이 한 점에서만 겹쳐도 접촉으로 보고 거절한다. 창고 경계도 접촉을 허용하지 않도록 중심 좌표를 엄격한 부등식으로 검사한다.

이 계산 역시 부동소수점 연산을 사용한다. 실무에서는 지도 오차, 로봇 외형 오차, 연산 오차를 고려해 별도의 여유 폭을 둘 수 있다. 다만 여유 폭을 키우면 실제로 존재하는 통로를 닫을 수 있다. 물리적 반지름과 추가 여유 폭을 구분해 관리해야 설정 변경의 의미를 해석할 수 있다.

찾은 경로에서 불필요한 굴곡 줄이기

처음 찾은 경로에는 탐색 과정에서 생긴 굴곡이 남는다. 서로 멀리 떨어진 두 경로점을 골라 직접 연결할 수 있는지 검사하면 그 사이의 굴곡을 줄일 수 있다. 이 방식을 지름길 다듬기(shortcut smoothing)라고 한다. 연결 선분이 비어 있으면 중간 점을 지우고, 충돌하면 원래 구간을 유지한다.

두 점 사이의 직선 길이는 같은 두 점을 잇는 꺾인 선의 길이보다 길지 않다. 따라서 충돌 검사를 통과한 구간을 직선으로 바꾸면 총길이는 수학적으로 증가하지 않는다. 코드에서는 합산 순서와 반올림을 고려해 작은 허용 오차를 두고 이 성질을 확인한다. 길이가 엄격하게 줄어야 한다고 검사하면 이미 곧은 구간을 처리할 때 불필요한 실패가 발생한다.

그림의 위쪽 지름길은 선반 위의 굴곡을 제거하지만, 아래쪽 연결은 선반을 관통하므로 채택하지 않는다. 단순히 가운데 점을 여러 개 지우는 것으로는 이 차이를 판단할 수 없다. 탐색에 사용한 것과 같은 선분 검사 함수를 다듬기에도 사용해야 두 단계가 같은 안전 조건을 유지한다.

이 장의 다듬기는 선분 경로의 점을 줄이는 작업이다. 결과에 날카로운 모서리가 남을 수 있고, 방향 변화나 가속도 조건을 만족한다는 뜻도 아니다. 다음 장에서 다룰 궤적 생성은 이렇게 얻은 위치 경로를 바탕으로 부드러운 움직임과 속도를 정하는 별도의 단계다.

탐색과 다듬기에는 서로 다른 난수 생성기를 사용한다. 한 생성기를 공유하면 탐색에서 소비한 난수 개수가 달라질 때 다듬기에 쓰이는 난수도 달라진다. 생성기를 나누면 탐색 설정을 변경했을 때 다듬기까지 함께 변하는 원인을 줄일 수 있다. 다만 입력 경로가 달라지면 같은 다듬기 시드라도 선택 결과는 달라질 수 있다.

완성 코드

다음 내용을 rrt_warehouse.py로 저장한다. NumPy가 설치된 Python 3 환경을 사용한다. 좌표와 길이의 단위는 m다. 코드는 시도 횟수나 좌표 목록 대신 검증 결과를 출력한다. 탐색 실패나 경로 조건 위반을 성공 메시지로 숨기지 않고 예외로 드러낸다.

import numpy as np


WIDTH = 12.0
HEIGHT = 8.0
RADIUS = 0.25
STEP = 0.6
GOAL_BIAS = 0.15
MAX_ITER = 6000
SHORTCUT_TRIALS = 200
PLAN_SEED = 7
SHORTCUT_SEED = 11
OBSTACLES = [(4.0, 0.0, 6.0, 6.0)]


def inflate(rectangles, radius):
    return [
        (xmin - radius, ymin - radius,
         xmax + radius, ymax + radius)
        for xmin, ymin, xmax, ymax in rectangles
    ]


def inside_world(point):
    x, y = point
    return (
        RADIUS < x < WIDTH - RADIUS
        and RADIUS < y < HEIGHT - RADIUS
    )


def segment_hits_rect(a, b, rect):
    xmin, ymin, xmax, ymax = rect
    enter, leave = 0.0, 1.0
    intervals = ((xmin, xmax), (ymin, ymax))

    for axis, (lower, upper) in enumerate(intervals):
        delta = float(b[axis] - a[axis])
        origin = float(a[axis])

        if delta == 0.0:
            if origin < lower or origin > upper:
                return False
            continue

        t0 = (lower - origin) / delta
        t1 = (upper - origin) / delta
        if t0 > t1:
            t0, t1 = t1, t0

        enter = max(enter, t0)
        leave = min(leave, t1)
        if enter > leave:
            return False

    return True


def segment_free(a, b, rectangles):
    if not inside_world(a) or not inside_world(b):
        return False
    return not any(
        segment_hits_rect(a, b, rect)
        for rect in rectangles
    )


def steer(origin, sample, step):
    offset = sample - origin
    distance = float(np.linalg.norm(offset))
    if distance == 0.0:
        return None
    if distance <= step:
        return sample.copy()
    return origin + offset * (step / distance)


def recover_path(nodes, parents, index):
    path = []
    while index != -1:
        path.append(nodes[index].copy())
        index = parents[index]
    path.reverse()
    return path


def rrt(start, goal, rectangles, rng,
        step=STEP, goal_bias=GOAL_BIAS, max_iter=MAX_ITER):
    if step <= 0.0 or not 0.0 <= goal_bias <= 1.0:
        raise ValueError("拡張設定が不正")
    if max_iter < 1:
        raise ValueError("시도 수는 양수여야 한다")
    if not segment_free(start, start, rectangles):
        raise ValueError("출발점이 이동 가능 영역 밖이다")
    if not segment_free(goal, goal, rectangles):
        raise ValueError("목표점이 이동 가능 영역 밖이다")
    if np.array_equal(start, goal):
        return [start.copy()]

    nodes = [start.copy()]
    parents = [-1]
    low = np.array([RADIUS, RADIUS])
    high = np.array([WIDTH - RADIUS, HEIGHT - RADIUS])

    for _ in range(max_iter):
        if rng.random() < goal_bias:
            sample = goal.copy()
        else:
            sample = rng.uniform(low, high)

        coordinates = np.asarray(nodes)
        squared = np.sum((coordinates - sample) ** 2, axis=1)
        nearest = int(np.argmin(squared))
        candidate = steer(nodes[nearest], sample, step)

        if candidate is None:
            continue
        if not segment_free(nodes[nearest], candidate, rectangles):
            continue

        nodes.append(candidate)
        parents.append(nearest)
        new_index = len(nodes) - 1
        goal_distance = float(np.linalg.norm(candidate - goal))

        if goal_distance <= step:
            if segment_free(candidate, goal, rectangles):
                if not np.array_equal(candidate, goal):
                    nodes.append(goal.copy())
                    parents.append(new_index)
                return recover_path(nodes, parents, len(nodes) - 1)

    return None


def shortcut(path, rectangles, rng, trials=SHORTCUT_TRIALS):
    result = [point.copy() for point in path]
    for _ in range(trials):
        if len(result) <= 2:
            break
        selected = rng.choice(len(result), size=2, replace=False)
        i, j = sorted(int(index) for index in selected)
        if j <= i + 1:
            continue
        if segment_free(result[i], result[j], rectangles):
            result = result[:i + 1] + result[j:]
    return result


def path_length(path):
    return sum(
        float(np.linalg.norm(b - a))
        for a, b in zip(path, path[1:])
    )


def path_is_free(path, rectangles):
    if not path:
        return False
    if not all(segment_free(p, p, rectangles) for p in path):
        return False
    return all(
        segment_free(a, b, rectangles)
        for a, b in zip(path, path[1:])
    )


def require(condition, message):
    if not condition:
        raise RuntimeError(message)


def main():
    rectangles = inflate(OBSTACLES, RADIUS)
    start = np.array([1.0, 1.0])
    goal = np.array([11.0, 1.0])
    plan_rng = np.random.Generator(np.random.PCG64(PLAN_SEED))
    shortcut_rng = np.random.Generator(
        np.random.PCG64(SHORTCUT_SEED)
    )

    raw = rrt(start, goal, rectangles, plan_rng)
    require(raw is not None, "예산 안에서 경로를 찾지 못했다")
    refined = shortcut(raw, rectangles, shortcut_rng)

    endpoints_ok = all(
        np.array_equal(path[0], start)
        and np.array_equal(path[-1], goal)
        for path in (raw, refined)
    )
    collision_ok = all(
        path_is_free(path, rectangles)
        for path in (raw, refined)
    )
    length_ok = path_length(refined) <= path_length(raw) + 1e-9

    require(endpoints_ok, "경로의 양 끝점이 달라졌다")
    require(collision_ok, "경로에서 충돌을 발견했다")
    require(length_ok, "다듬은 경로의 길이가 증가했다")

    print(f"난수 시드: 탐색={PLAN_SEED}, 다듬기={SHORTCUT_SEED}")
    print("경로 탐색: 성공")
    print("시작점·목표점 유지: 통과")
    print("전체 선분 충돌 검사: 통과")
    print("경로 길이 비증가: 통과")


if __name__ == "__main__":
    main()

줄별 해설

WIDTH부터 OBSTACLES까지는 지도의 크기와 탐색 조건을 선언한다. 장애물 튜플의 순서는 최소 x, 최소 y, 최대 x, 최대 y다. 좌표 순서를 바꾸면 충돌 함수의 의미도 달라지므로 입력 형식을 고정한다. MAX_ITER는 추가 노드 수가 아니라 표본을 처리하는 최대 횟수다.

inflate의 목록 내포는 각 직사각형의 하한에서는 반지름을 빼고 상한에는 반지름을 더한다. 이 연산은 main에서 한 번만 호출한다. 이미 부풀린 장애물을 충돌 검사 때마다 다시 부풀리면 통로가 설정한 값보다 좁아진다.

inside_world는 중심점이 외벽에서 반지름보다 멀리 떨어졌는지 확인한다. 창고의 내부는 볼록한 직사각형이므로, 두 끝점이 이 내부에 있으면 그 사이의 직선도 내부에 있다. 이 때문에 외벽 검사는 끝점만으로 충분하다. 내부 선반에는 같은 논리를 적용할 수 없어서 별도의 교차 검사가 필요하다.

segment_hits_rect에서 enter와 leave는 아직 가능한 선분 매개변수의 하한과 상한이다. delta == 0.0 분기는 축에 평행한 선분뿐 아니라 길이가 0인 선분도 처리한다. 출발점 검사에 segment_free(start, start, rectangles)를 사용할 수 있는 이유다.

t0와 t1을 교환하는 줄은 이동 방향에 따른 순서를 정리한다. 음의 방향으로 움직이면 좌표 하한을 만나는 시점이 더 늦을 수 있다. 정렬 뒤에는 max로 진입 시점을 늦추고 min으로 이탈 시점을 당긴다. 진입이 이탈보다 늦어지는 순간 두 조건을 함께 만족할 점이 사라진다.

segment_free는 외벽 조건을 먼저 확인한 뒤 any로 장애물 교차 여부를 묻는다. 하나라도 교차하면 자유로운 선분이 아니다. 함수 이름은 자유 공간 여부를 말하고 내부 함수는 충돌 여부를 말하므로 반환값의 부정을 눈여겨봐야 한다. 이 함수 하나를 탐색, 목표 연결, 다듬기, 최종 검증에서 공유한다.

steer는 두 점이 같으면 None을 돌려준다. 길이가 0인 방향을 정규화하지 않기 위한 처리다. 표본이 확장 길이 안에 있으면 표본의 복사본을 반환한다. 밖에 있으면 방향 벡터에 step / distance를 곱해 이동량을 제한한다.

recover_path는 부모 번호가 -1인 출발점까지 거슬러 올라간다. 좌표를 복사해서 담는 것은 반환 경로를 수정할 때 트리의 좌표 배열까지 함께 바뀌는 일을 피하기 위해서다. 마지막 reverse가 실제 주행 순서를 만든다.

rrt의 첫 조건들은 확장 설정, 시도 수, 양 끝점의 유효성을 확인한다. 출발점과 목표점이 같으면 유효한 점 하나만 반환한다. 그다음 nodes와 parents를 나란히 준비한다. 같은 인덱스의 두 항목이 한 노드의 좌표와 부모를 나타내므로 항상 함께 추가해야 한다.

rng.random()을 비교하는 줄이 목표 편향을 구현한다. 나머지 경우에는 중심점이 움직일 창고 범위에서 표본을 뽑는다. 장애물 안의 표본도 포함될 수 있지만, 이후 연결 검사가 후보의 허용 여부를 결정한다. 표본 생성 범위와 실제 자유 공간이 같을 필요는 없다.

coordinates - sample은 모든 노드에서 표본까지의 좌표 차이를 한꺼번에 만든다. 제곱합은 거리 제곱이며, 최소값의 위치는 실제 거리의 최소 위치와 같다. 따라서 최근접 검색에서는 제곱근을 계산하지 않는다. argmin이 반환한 인덱스를 정수로 바꿔 부모 번호로 사용한다.

candidate가 없거나 연결이 막히면 continue로 다음 시도를 시작한다. 검사를 통과한 뒤에만 좌표와 부모를 추가하므로 트리의 모든 간선은 충돌 검사를 통과한 상태다. 목표 연결도 같은 검사를 수행하며, 후보가 목표와 이미 같을 때는 동일한 목표 노드를 다시 추가하지 않는다.

shortcut의 replace=False는 서로 다른 두 인덱스를 뽑는다. 정렬한 뒤 이웃한 점이면 바꿀 중간 구간이 없으므로 건너뛴다. result[:i + 1] + result[j:]는 양 끝점을 남기고 그 사이만 제거한다. 한 번 삭제할 때마다 목록 길이가 바뀌므로 인덱스는 매번 현재 목록에서 새로 뽑는다.

path_is_free는 빈 경로를 먼저 거절하고 각 점과 모든 선분을 검사한다. 점 검사까지 포함하므로 점 하나로 된 경로도 검증할 수 있다. main에서는 원래 경로와 다듬은 경로의 양 끝점, 충돌 여부, 길이 관계를 확인한다. 모든 검사가 끝난 뒤에 출력하므로 성공 메시지는 조건 검사를 통과했다는 뜻이다.

실행 결과

저장한 파일이 있는 디렉터리에서 다음 두 명령을 순서대로 실행한다. 첫 명령은 문법 검사와 바이트코드 컴파일을 수행하며 정상일 때 출력이 없다. 두 명령 모두 경고를 오류로 처리한다. 두 번째 명령이 실제 탐색과 다듬기를 수행한다.

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

예상 출력은 다음과 같다.

난수 시드: 탐색=7, 다듬기=11
경로 탐색: 성공
시작점·목표점 유지: 통과
전체 선분 충돌 검사: 통과
경로 길이 비증가: 통과

같은 환경에서 같은 설정으로 실행하면 난수 생성기가 같은 순서의 값을 사용하므로 결과가 재현된다. 비트 생성기는 코드에서 명시했지만, 장기간 좌표 목록까지 비교해야 한다면 Python과 NumPy 버전도 함께 기록하는 편이 좋다. 여기서는 환경별 마지막 자리 차이에 민감한 좌표 출력보다 경로가 만족해야 하는 조건을 확인한다.

길이 비증가 검사는 최단 경로를 찾았다는 판정이 아니다. 무작위 트리는 처음 발견한 경로에서 종료하고, 다듬기는 정해진 횟수만큼 두 점의 연결을 시험한다. 더 짧은 경로가 남아 있을 수 있다. 또한 검증은 같은 충돌 함수를 다시 사용하므로, 충돌 함수 자체의 오류까지 독립적으로 찾아내지는 않는다. 선반을 관통하는 선분과 경계에 닿는 선분 같은 작은 사례를 따로 확인할 필요가 있다.

실무에서 자주 틀리는 것

끝점이 비어 있으면 이동도 가능하다고 판단한다

다음 코드는 두 점만 검사한다. 선반 양쪽의 점은 모두 통과할 수 있지만 연결 선분이 선반을 가로지르는 경우를 놓친다.

# 틀린 코드
allowed = (
    segment_free(a, a, rectangles)
    and segment_free(b, b, rectangles)
)

# 고친 코드
allowed = segment_free(a, b, rectangles)

위치의 유효성과 이동의 유효성은 다른 질문이다. 특히 확장 길이를 키웠을 때 이상한 경로가 생긴다면 끝점만 확인하고 있지 않은지 먼저 살핀다. 최종 목표로 붙이는 마지막 선분도 예외가 아니다.

반지름을 반영하기 전에 점 로봇으로 검사한다

원래 선반만 검사하면 중심점은 비어 있어도 로봇의 가장자리가 선반과 겹칠 수 있다. 지도 준비 단계에서 금지 영역을 확장하고 그 결과를 모든 경로 검사에 전달한다.

# 틀린 코드
rectangles = OBSTACLES

# 고친 코드
rectangles = inflate(OBSTACLES, RADIUS)

그 반대 실수도 있다. 이미 확장한 지도를 다시 확장하면 반지름이 중복 반영된다. 원래 장애물과 확장한 장애물을 서로 다른 변수로 유지하면 이 혼동을 줄일 수 있다. 적재물 때문에 외형이 달라지는 경우에는 반지름을 바꾼 뒤 확장 지도를 다시 만들어야 한다.

목표 편향을 높이면 항상 빨라진다고 생각한다

목표가 선반 뒤에 있는 이번 지도에서는 목표 방향만 반복해서 시험하면 우회할 가지를 만들지 못한다. 목표를 향한 확장과 주변 공간 탐색이 함께 일어나도록 확률을 둔다.

# 틀린 코드
raw = rrt(start, goal, rectangles, plan_rng, goal_bias=1.0)

# 고친 코드
raw = rrt(start, goal, rectangles, plan_rng, goal_bias=0.15)

0.15가 모든 창고의 권장값이라는 뜻은 아니다. 서로 다른 시드에서 성공률과 필요한 시도 수를 비교해 값을 정한다. 하나의 시드만 보면 우연히 유리한 표본 순서를 좋은 설정의 효과로 오해할 수 있다. 고정 시드는 재현을 위한 도구이고 설정 평가에는 여러 시드가 필요하다.

점을 줄이면서 충돌 검사를 생략한다

경로점 수를 줄이는 것만 목표로 삼으면 선반 주변의 중요한 꼭짓점도 사라진다. 삭제 뒤 새로 생기는 연결이 허용되는지 먼저 확인해야 한다. 다음 조각은 다듬기 함수 안에서 사용하는 코드다.

# 틀린 코드
result = result[:i + 1] + result[j:]

# 고친 코드
if segment_free(result[i], result[j], rectangles):
    result = result[:i + 1] + result[j:]

충돌 없는 경로를 입력받았다는 사실만으로 출력 경로도 충돌이 없다고 볼 수는 없다. 삭제는 단순한 목록 편집처럼 보이지만 기하학적으로는 새 선분을 만드는 연산이다. 지도나 로봇 크기가 바뀌었다면 기존 경로의 선분도 다시 확인해야 한다.

한눈에 보기

무작위 트리의 각 단계는 후보 생성과 이동 검증을 함께 유지한다

요소	역할	확인할 조건
무작위 표본	확장할 방향을 제안한다	표본이 곧 추가 노드는 아니다
최근접 노드	새 가지의 출발점을 정한다	거리 제곱으로 비교할 수 있다
확장 길이	한 번의 이동 거리를 제한한다	작아도 선분 검사는 필요하다
목표 편향	목표를 표본으로 선택한다	우회를 위한 다른 표본도 필요하다
장애물 확장	로봇 크기를 중심점 검사에 반영한다	한 번만 적용하고 근사를 인식한다
부모 번호	도달한 경로를 복원한다	노드 추가와 함께 기록한다
경로 다듬기	불필요한 중간 점을 제거한다	새 연결의 충돌 여부를 검사한다
시도 수 제한	계산 예산을 정한다	실패가 경로 부재의 증명은 아니다

연습 문제

1. 확장된 선반을 기준으로 (2, 3)에서 (8, 3)으로 가는 선분과 (2, 7)에서 (8, 7)로 가는 선분의 충돌 여부를 설명하라. 끝점 검사만으로 첫 번째 선분을 판정하면 어떤 문제가 생기는가.
2. 나머지 설정을 유지하고 목표 편향만 1.0으로 바꾸면 이번 지도에서 탐색이 실패하는 이유를 설명하라. 이때 최대 시도 수만 늘리는 것이 해결책이 되는지도 설명하라.
3. 지름길 다듬기 전후에 유지해야 하는 조건을 세 가지 쓰고, 길이가 엄격히 감소해야 한다는 조건이 부적절한 이유를 설명하라.
4. 확장 길이 0.3과 0.9를 비교하려 한다. 시드 하나의 결과만으로 결론 내리지 않도록 실험 방법을 설계하라. 성공한 실행과 실패한 실행을 어떻게 기록할지도 포함하라.

정답과 해설

1. 확장된 선반의 x 범위는 3.75부터 6.25까지이고 y 범위는 −0.25부터 6.25까지다. 첫 선분은 y가 3으로 고정되어 있으며 x가 선반 범위를 통과하므로 충돌한다. 양 끝점은 각각 선반의 왼쪽과 오른쪽에 있어 점 검사만으로는 문제를 발견하지 못한다. 두 번째 선분은 y가 7이어서 확장된 선반 위를 지나며 외벽 조건도 만족한다. 따라서 이번 지도에서는 이동 가능하다.

2. 모든 표본이 (11, 1)이므로 출발점에서 자라는 노드는 계속 y가 1인 직선 위에 놓인다. 확장이 선반에 막힌 뒤에도 같은 최근접 노드에서 같은 후보를 만들게 된다. 위쪽 방향을 제안하는 표본이 없으므로 시도 수를 늘려도 이 상태를 벗어나지 못한다. 이 실패는 계산 예산이 부족한 사례와 구분해야 한다.

3. 출발점과 목표점이 유지되어야 하고, 모든 연결 선분이 충돌 없이 통과해야 하며, 총길이가 허용 오차 안에서 증가하지 않아야 한다. 다듬기에서 뽑힌 두 점이 이웃하거나 연결이 막혀 있으면 경로를 그대로 둔다. 중간 점이 한 직선 위에 있는 경우에도 길이가 같을 수 있다. 따라서 감소만 요구하지 말고 비증가를 검사한다.

4. 예를 들어 0부터 19까지의 탐색 시드를 두 설정 모두에 적용하고 지도, 목표 편향, 최대 시도 수를 같게 둔다. 각 실행의 성공 여부를 기록하고, 성공한 실행에는 목표 도달 시도 수와 원래 경로 길이를 기록한다. 실패한 실행은 예산 소진으로 별도 표시한다. 성공률을 먼저 비교한 뒤 성공 사례의 시도 수와 길이 분포를 살핀다. 성공 사례만 남겨 평균을 내면 자주 실패하는 설정이 유리해 보일 수 있다. 동일한 시드는 비교의 출발 조건을 맞추지만, 트리가 달라진 뒤에도 동일한 가지를 탐색한다는 뜻은 아니다.