급속 탐색 무작위 트리

표본을 향한 확장

탐색 영역에서 표본을 뽑고 트리 안에서 가까운 정점을 찾는다. 그 정점에서 표본 방향으로 허용된 운동을 만들고 충돌하지 않으면 새 정점과 간선을 추가한다. 매번 기존 정점을 무작위로 골라 걷는 방식과 다르다. 아직 정점이 적은 영역의 표본이 가까운 트리 정점을 끌어 확장을 유도한다.

한 번의 확장 계산

장애물이 없는 평면에서 가까운 정점이 (0,0), 표본이 (3,4), 최대 확장 길이가 1이라고 하자. 표본까지 거리는 5이므로 새 정점은 (0.6,0.8)이다. 표본 자체를 곧바로 트리에 넣는 것이 아니다. 이 구간에 장애물이 있다면 끝점이 비충돌이어도 간선을 그대로 추가할 수 없다. 확장 길이는 탐색 성질과 검사 비용에도 영향을 준다.

운동 제약과 거리

차량처럼 옆으로 바로 움직일 수 없는 대상에는 좌표 사이 직선이 실행 가능한 운동이 아닐 수 있다. 후보 제어 입력을 짧게 적분해 얻은 상태들 중 표본에 가까운 것을 고르는 방법도 있다. 위치와 각도를 함께 비교할 때에는 단위와 각도의 주기성을 반영해야 한다. 단순 유클리드 거리가 실제 도달 시간이나 운동 난이도를 항상 나타내지는 않는다.

경로 복원과 품질

새 정점이 목표 영역에 들어가면 부모 연결을 거슬러 시작점까지 이어 경로를 복원한다. 목표 쪽 표본을 가끔 선택해 탐색을 유도할 수도 있다. 기본 RRT에서 정점을 더 만든다고 최적 경로로 수렴하는 것은 아니다. 재연결 규칙을 갖는 RRT*는 별도 변형이며, 그 보장도 운동 모델과 연결 조건 등을 전제로 한다.