시작에서 연결된 트리를 조금씩 자란다
RRT는 Rapidly-exploring Random Tree의 약자로, 시작에서 도달 가능한 상태를 트리 형태로 확장하는 접근이다. 트리는 이 예에서 시작을 뿌리로 하고 각 새 node가 하나의 부모를 갖는 연결 구조다. 새로 뽑은 샘플 자체가 반드시 트리에 들어가는 것은 아니다. 가까운 기존 node에서 샘플 방향으로 확장하고 그 연결이 유효할 때 새 node를 넣는다.
PRM이 여러 자유 샘플을 모아 연결을 구성했다면 기본 RRT는 시작에서 이미 연결된 부분을 늘린다는 차이가 있다. 그렇다고 두 계열의 모든 구현과 사용 목적이 배타적인 것은 아니다. 이 단위는 정적 평면의 점 configuration과 유클리드 거리, 직선 국소 연결을 사용한다. 실제 차량이나 동역학을 포함하는 RRT에서는 상태·제어 입력과 운동 적분으로 확장을 만들 수 있으며 같은 직선 공식을 그대로 쓰지 않는다.
Modern Robotics 저자 RRT 설명은 샘플, 최근접 상태와 실행 가능한 확장이라는 역할을 보여 준다. 무작위로 목표 경로 전체를 찍는 것이 아니라 현재 트리와 새 표본의 관계를 이용한다. 거리 척도와 표본 분포, 확장 길이 및 충돌 검사가 탐색 결과에 영향을 준다.
최근접과 길이 제한 확장을 계산한다
q_near는 샘플 q_rand에 가장 가까운 기존 configuration이고, η는 한 번 확장할 최대 길이(m)다. 두 점이 서로 다를 때 거리를 d라고 하면 이 평면 예의 새 점은 다음과 같다.
그림 M17.04-1. 각 칸은 서로 다른 역할/근거다. 아래 방향은 자료/처리의 연결이며 실제 성공을 자동으로 보장하지 않는다. 직접 제작한 개념도이며 본문의 조건과 함께 읽는다.
현재 트리가 S=(0,0) m만 가지고 샘플이 (3,4) m, η=1 m라면 d=5 m다. 이동 방향을 길이 1로 줄여 q_new=(0.6,0.8) m가 된다. 샘플까지 바로 5 m를 연결한 것이 아니다. 샘플이 η보다 가까우면 min 값이 1이 되어 샘플까지 간다. d=0인 중복 표본에서는 나누지 않고 확장을 생략하는 등의 처리를 해야 한다.
이때 장애물이 없는 경우 S에서 새 점까지의 길이는 1 m이고 유효 간선이 될 수 있다. 별도 변형으로 장애물 중심 (0.3,0.4) m, 반지름 0.1 m인 원을 주자. 시작과 새 끝점은 장애물 중심에서 각각 0.5 m 떨어져 있어 자유롭지만 연결 구간의 중간이 중심을 지난다. 따라서 이 확장은 거부한다. q_new만 검사하거나 샘플이 장애물 밖이라는 이유로 연결을 승인하면 틀리다.
한 확장 거부는 전체 경로 부재가 아니다. 다른 표본을 통해 장애물 둘레로 자랄 수 있다. 반대로 자유 끝점이 많더라도 국소 연결이 계속 충돌하거나 유효한 좁은 통로를 샘플링하지 못하면 제한 시간 내에 해를 찾지 못할 수 있다. 예산 초과·충돌 거부·잘못된 시작과 목표를 별도 상태로 기록한다.
그림 M17.04-2. 시작점에서 이미 연결된 트리를 확장하는 별도 점 모델 개념도다. 주황 확장 후보도 연결 구간 검사를 거쳐야 한다. 일반 차량의 조향/동역학을 직선 연결로 대체한 모델은 아니다. 직접 제작.
목표 편향은 안내와 탐색의 균형이다
목표 편향(goal bias)은 일부 확장에서 일반 무작위 표본 대신 목표를 샘플로 고르는 전략이다. 예를 들어 확률 0.1로 목표를 고르고 0.9로 정한 자유 공간 탐색 분포를 사용할 수 있다. 이 수치는 설명용이며 모든 문제에 좋은 기본값이라는 추천이 아니다. N번 중 정확히 10%가 목표 표본이 되는 것도 아니며 독립 시행의 기대 비율이다.
편향을 1로 두면 목표만 반복해서 향한다. 목표까지 직선이 막힌 예에서는 같은 방향의 충돌 확장을 반복하며 우회 방향을 탐색하지 못할 수 있다. 반대로 목표를 거의 보지 않아도 목표 영역을 충분히 탐색할 수 있는지는 문제와 표본 분포에 달려 있다. 필요한 공간을 계속 탐색할 가능성과 연결기·경로 여유의 조건을 유지해야 이론적 보장을 논할 수 있다.
목표의 정의도 명시한다. 어떤 pose 하나와 허용 오차가 있는 목표 영역은 다르며, 목표 근처 node를 만들었다고 마지막 연결을 검사하지 않은 채 성공으로 표시하면 안 된다. 실제 제어에서 도착했는지는 계획이 생성됐다는 사실과 별도다. 이동 중 장애물이 바뀌는 경우도 이 정적 트리의 가정 밖이다.
RRT*는 가까운 부모를 고른 뒤 비용을 다시 연결한다
기본 RRT는 보통 확장에 사용한 최근접 node를 새 점의 부모로 둔다. RRT*는 새 점 주변의 후보 중 유효한 간선으로 가장 작은 누적 비용을 주는 부모를 고르고, 새 점을 거치면 더 싸지는 이웃의 부모를 바꾸는 재배선(rewiring)을 수행한다. 단지 새 점을 더 많이 찍는 것과 다르다. 비용은 뿌리부터 그 node까지의 경로 비용이며 여기서는 간선 길이의 합이다.
별도의 장애물 없는 합성 트리를 보자. 기존 간선은 S=(0,0)→A=(0,1)→D=(0,2)→B=(1,2) m이며 각 길이가 1 m다. 누적 비용은 S:0, A:1, D:2, B:3 m다. 샘플 N=(1,1) m, 확장 한계 η=1.5 m, 이웃 반경 1.5 m를 준다. 최근접은 A와 B가 각각 1 m로 같으므로 입력 순서 S,A,D,B에서 먼저인 A를 고른다. 샘플까지 거리가 1 m여서 새 점은 N 그대로다.
기본 최근접 부모 A를 쓰면 N 비용은 1+1=2 m다. RRT*의 이웃 후보는 네 점 모두다. S에서 N의 길이는 √2≈1.414 m로 반경과 확장 한계 이내이며 유효하다. 부모 후보별 N 비용은 S:1.414, A:2, D:2+√2≈3.414, B:4 m다. 따라서 S를 부모로 골라 N 비용을 √2 m로 만든다.
이제 B를 N을 통해 가면 √2+1≈2.414 m로 기존 3 m보다 싸다. N-B 간선이 유효하므로 B의 부모를 D에서 N으로 바꾼다. 반면 A는 새 비용 2.414가 기존 1보다 크고 D는 새 비용 2.828이 기존 2보다 커서 바꾸지 않는다. 부모를 바꾸면 그 node의 후손 비용도 일관되게 갱신해야 하고 조상을 자손 밑에 붙여 순환을 만들면 안 된다. 후보가 더 싸더라도 간선이 무효면 재배선하지 않는다.
별표와 양방향 확장을 성능 보증으로 읽지 않는다
Karaman과 Frazzoli 원논문은 기본 RRT의 해 발견 성질과 RRT의 점근 최적성을 구분한다. RRT의 보장은 표본과 이웃 규칙, 유효성 검사, 경로·비용 조건 아래 표본이 늘 때의 성질이다. 위 반경 1.5 m는 한 번의 계산 입력이지 임의의 차원·표본 수에서 점근 최적성을 보장하는 규칙이 아니다. 반환한 첫 유한 경로를 정확한 최단이라고 쓰지 않는다.
OMPL 공식 목록은 두 트리를 사용하는 RRT-Connect와 RRT* 등의 변형을 구분한다. RRT-Connect는 시작과 목표 쪽의 트리를 자라 서로 연결하려는 방식이며 연결하는 중간 구간도 검사해야 한다. 양방향이라는 이름만으로 모든 문제에서 더 빠르거나 최적이라는 결론은 나오지 않는다. 어떤 변형을 사용했고 무엇을 성공으로 판정했는지 기록한다.
같은 시간 예산·지도·형상·시작과 목표에서 여러 seed의 해 발견률, 첫 해까지 시간, 비용과 충돌 거부·실패를 함께 비교한다. 유한 실패를 경로 부재로 바꾸지 않으며 기하 해를 실제 속도·가속도와 제어 실행까지 통과한 것으로 보고하지 않는다. 기존 3.5 안전한 텔레오퍼레이션 루프와 6.6 평가 설계를 연결해 계획·실행·평가 범위를 구분하자. 이 활동에서는 무작위 트리를 실제 생성하거나 로봇을 움직이지 않는다.