12.14 급속 탐색 무작위 트리(RRT)

1. RRT의 개요

급속 탐색 무작위 트리(Rapidly-exploring Random Tree, RRT)는 1998년 스티븐 라발(Steven LaValle)이 제안한 샘플링 기반 운동 계획 알고리즘이다. 시작 자세에서 트리를 구축하면서 자유 공간을 빠르게 탐색하고, 목표에 도달하는 경로를 찾는다. RRT는 단일 쿼리에 효율적이며, 고차원 공간과 비홀로노믹 시스템에 효과적이다. 매니퓰레이터, 자율 주행 차량, 무인 항공기, 인간형 로봇 등 다양한 시스템의 운동 계획에서 표준 알고리즘으로 사용된다.

2. RRT의 핵심 아이디어

2.1 트리 구조

RRT는 그래프(로드맵) 대신 트리 구조를 사용한다. 트리는 시작 자세에서 시작하여 점진적으로 확장된다.

2.2 무작위 샘플링

자유 공간에서 무작위 점을 샘플링하고, 이 점 방향으로 트리를 확장한다. 무작위 샘플링이 자유 공간 탐색을 자연스럽게 유도한다.

2.3 빠른 탐색

RRT는 자유 공간의 미탐색 영역으로 빠르게 확장하는 성질이 있다. 이는 트리가 자유 공간을 균등하게 덮도록 한다.

3. RRT의 알고리즘

3.1 기본 알고리즘

RRT(C_free, q_start, q_goal, max_iter):
    T = tree with q_start as root
    
    for i = 1 to max_iter:
        q_rand = random sample from C_space
        q_near = nearest node in T to q_rand
        q_new = steer(q_near, q_rand)
        
        if collision_free(q_near, q_new):
            T.add_node(q_new)
            T.add_edge(q_near, q_new)
            
            if distance(q_new, q_goal) < threshold:
                return path from q_start to q_new
    
    return failure

3.2 단계별 동작

초기화: 시작 자세를 트리의 루트로 한다.
반복: 최대 반복 횟수까지 다음을 반복한다.

자유 공간에서 무작위 점 $q_{\text{rand}}$ 를 샘플링한다.
트리에서 $q_{\text{rand}}$ 에 가장 가까운 노드 $q_{\text{near}}$ 를 찾는다.
$q_{\text{near}}$ 에서 $q_{\text{rand}}$ 방향으로 일정 거리 진행한 점 $q_{\text{new}}$ 를 계산한다.
$q_{\text{near}}$ 에서 $q_{\text{new}}$ 로의 경로가 충돌이 없으면 트리에 추가한다.
$q_{\text{new}}$ 가 목표에 충분히 가까우면 종료한다.

종료: 경로를 추출하거나 실패를 반환한다.

4. 핵심 구성 요소

4.1 무작위 샘플링

대부분의 경우 자유 공간에서 균등 무작위 샘플링을 사용한다. 일부 변형은 목표 편향(goal-biased) 샘플링을 사용한다.

def random_sample(c_space):
    return np.random.uniform(c_space.low, c_space.high)

4.2 가까운 노드 검색

트리에서 무작위 점에 가장 가까운 노드를 찾는다. 트리가 작을 때는 선형 검색이 가능하지만, 트리가 커지면 k-d Tree 등이 효율적이다.

def nearest_node(tree, q_rand):
    return min(tree.nodes, key=lambda q: distance(q, q_rand))

4.3 Steer 함수

Steer 함수는 $q_{\text{near}}$ 에서 $q_{\text{rand}}$ 방향으로 일정 거리(step size) 진행한 점을 계산한다.

def steer(q_near, q_rand, step_size):
    direction = (q_rand - q_near)
    norm = np.linalg.norm(direction)
    if norm < step_size:
        return q_rand
    return q_near + step_size * direction / norm

4.4 충돌 검사

새로운 노드와 새로운 엣지가 자유 공간에 있는지 검사한다. 일반적으로 직선 보간 위의 여러 점에서 충돌 검사를 수행한다.

5. RRT의 성질

5.1 빠른 탐색

RRT는 자유 공간의 미탐색 영역으로 빠르게 확장한다. 이는 무작위 샘플링이 미탐색 영역에서 더 자주 발생하기 때문이다.

5.2 점근적 완전성

RRT는 점근적으로 확률적 완전(probabilistically complete)이다. 즉, 해답이 존재하면 시간이 무한대로 갈 때 발견할 확률이 1로 수렴한다.

5.3 비최적성

기본 RRT는 최적이 아니다. 발견된 경로가 최적 경로보다 길 수 있다.

5.4 단일 쿼리

RRT는 단일 시작-목표 쌍에 대해 동작한다. 다른 쌍에 대해서는 처음부터 트리를 다시 구축해야 한다.

6. RRT의 변형

6.1 목표 편향 RRT

목표 편향 RRT(Goal-Biased RRT)는 일정 확률로 목표 자세를 샘플로 사용한다. 이는 트리가 목표 방향으로 확장하도록 유도한다.

def random_sample_biased(q_goal, bias_prob=0.1):
    if random.random() < bias_prob:
        return q_goal
    return random_sample(c_space)

6.2 Bidirectional RRT (RRT-Connect)

양방향 RRT는 시작과 목표 자세에서 동시에 두 트리를 확장한다. 두 트리가 만나면 경로가 완성된다.

RRT_Connect(q_start, q_goal):
    T_a = tree from q_start
    T_b = tree from q_goal
    
    for i = 1 to max_iter:
        q_rand = random sample
        if extend(T_a, q_rand) succeeds:
            if connect(T_b, last node of T_a) succeeds:
                return path
        swap(T_a, T_b)
    
    return failure

6.3 RRT*

RRT*는 RRT의 점근적 최적 변형이다. 새로운 노드를 추가할 때 주변 노드들을 다시 연결하여 더 짧은 경로를 만든다.

6.3.1 알고리즘

RRT_star(C_free, q_start, q_goal, max_iter):
    T = tree with q_start as root
    
    for i = 1 to max_iter:
        q_rand = random sample
        q_near = nearest(T, q_rand)
        q_new = steer(q_near, q_rand)
        
        if collision_free(q_near, q_new):
            // 가까운 이웃들 찾기
            Q_near = near_nodes(T, q_new, radius)
            
            // 최소 비용 부모 선택
            q_min = q_near
            c_min = cost(q_near) + dist(q_near, q_new)
            for q in Q_near:
                if collision_free(q, q_new):
                    c = cost(q) + dist(q, q_new)
                    if c < c_min:
                        q_min = q
                        c_min = c
            
            T.add_node(q_new, parent=q_min)
            
            // 가까운 노드들 다시 연결
            for q in Q_near:
                if collision_free(q_new, q):
                    if cost(q_new) + dist(q_new, q) < cost(q):
                        T.change_parent(q, q_new)
    
    return path

6.3.2 점근적 최적성

RRT*는 점근적 최적이다. 시간이 무한대로 갈 때 발견된 경로가 최적 경로로 수렴한다.

6.4 Informed RRT*

Informed RRT*는 첫 해답이 발견된 후 검색 공간을 타원체로 제한한다. 이는 검색을 더 집중시키고 수렴 속도를 향상시킨다.

6.5 Kinodynamic RRT

Kinodynamic RRT는 동역학 제약을 고려한 RRT이다. 운동학과 동역학이 결합된 시스템에 적용된다.

6.6 CL-RRT

Closed-Loop RRT(CL-RRT)는 폐루프 동역학 시스템에 적용된다. 자율 주행 차량의 운동 계획에서 사용된다.

6.7 Anytime RRT

Anytime RRT는 시간 제약이 있는 환경에서 사용 가능한 해답을 점진적으로 개선한다.

7. RRT와 PRM의 비교

측면	RRT	PRM
구조	트리	그래프
쿼리	단일	다중
학습	통합	분리
메모리	적음	많음
최적성	RRT*는 최적	PRM*는 최적
적합 영역	동적 환경, 단일 쿼리	정적 환경, 다중 쿼리

8. RRT의 성능 분석

8.1 시간 복잡도

RRT의 시간 복잡도는 다음에 의존한다.

반복 횟수
가까운 이웃 검색의 효율성
충돌 검사 시간

각 반복의 비용은 $O(\log n)$ ~ $O(n)$ 이며, $n$ 은 트리의 노드 수이다.

8.2 공간 복잡도

RRT의 공간 복잡도는 트리의 크기에 비례한다. RRT*는 가까운 이웃 검색으로 인해 약간 더 많은 메모리를 사용한다.

9. Python 구현

import numpy as np
import random

class Tree:
    def __init__(self, root):
        self.nodes = [root]
        self.parents = {0: None}
    
    def add_node(self, node, parent_idx):
        self.nodes.append(node)
        self.parents[len(self.nodes) - 1] = parent_idx
    
    def nearest(self, q):
        distances = [np.linalg.norm(np.array(n) - np.array(q)) for n in self.nodes]
        return np.argmin(distances)
    
    def get_path(self, end_idx):
        path = []
        current = end_idx
        while current is not None:
            path.append(self.nodes[current])
            current = self.parents[current]
        return path[::-1]

def steer(q_near, q_rand, step_size):
    q_near = np.array(q_near)
    q_rand = np.array(q_rand)
    direction = q_rand - q_near
    norm = np.linalg.norm(direction)
    if norm < step_size:
        return tuple(q_rand)
    return tuple(q_near + step_size * direction / norm)

def rrt(c_space, c_free_check, q_start, q_goal, max_iter=1000, step_size=0.1, goal_threshold=0.2):
    tree = Tree(q_start)
    
    for i in range(max_iter):
        # 무작위 샘플
        if random.random() < 0.1:
            q_rand = q_goal
        else:
            q_rand = tuple(np.random.uniform(c_space.low, c_space.high))
        
        # 가까운 노드
        nearest_idx = tree.nearest(q_rand)
        q_near = tree.nodes[nearest_idx]
        
        # Steer
        q_new = steer(q_near, q_rand, step_size)
        
        # 충돌 검사
        if c_free_check(q_new) and collision_free_path(q_near, q_new, c_free_check):
            tree.add_node(q_new, nearest_idx)
            new_idx = len(tree.nodes) - 1
            
            # 목표 도달 검사
            if np.linalg.norm(np.array(q_new) - np.array(q_goal)) < goal_threshold:
                tree.add_node(q_goal, new_idx)
                return tree.get_path(len(tree.nodes) - 1)
    
    return None

10. RRT의 응용

10.1 매니퓰레이터의 운동 계획

매니퓰레이터의 구성 공간에서 RRT가 표준 알고리즘이다. 고차원 공간에서도 효과적이다.

10.2 자율 주행 차량

자율 주행 차량의 경로 계획에서 Kinodynamic RRT가 사용된다. 차량의 비홀로노믹 제약이 반영된다.

10.3 무인 항공기

드론의 3차원 경로 계획에서 RRT가 활용된다. 충돌 회피와 동적 환경에 적합하다.

10.4 인간형 로봇

인간형 로봇의 동작 계획에 RRT가 사용된다. 균형, 충돌 회피 등이 고려된다.

10.5 우주 로봇

우주 로봇이 복잡한 환경에서 운동을 계획할 때 RRT가 활용된다.

11. 응용 예시: 매니퓰레이터의 픽 앤 플레이스

매니퓰레이터가 부품을 집어 옮기는 작업에서 RRT가 경로 계획에 사용된다. 시작 자세에서 목표 자세까지의 충돌 없는 경로를 찾는다.

12. 응용 예시: 자율 주차

자율 주차 시스템에서 RRT가 사용된다. 차량의 운동학적 제약(앞바퀴 조향, 후진 가능)을 고려한 경로가 생성된다.

13. 응용 예시: 드론의 장애물 회피

드론이 장애물이 있는 환경에서 비행할 때 RRT가 경로 계획에 사용된다. 3차원 환경에서 효과적이다.

14. 응용 예시: 매니퓰레이션의 잡기 계획

매니퓰레이터가 객체를 잡을 때 도달 자세까지의 경로를 RRT로 계획한다. 자기 충돌과 환경 충돌을 모두 고려한다.

15. 응용 예시: 다리 보행 로봇

이족 또는 사족 보행 로봇의 발걸음 계획에 RRT가 사용된다. 안정성과 환경 회피가 고려된다.

16. RRT의 한계

16.1 최적성 부족

기본 RRT는 최적 경로를 보장하지 않는다. 점근적 최적성을 위해서는 RRT*를 사용해야 한다.

16.2 좁은 통로

좁은 통로에서 RRT의 성능이 저하될 수 있다. 특수한 샘플링 전략이 필요하다.

16.3 매개변수 튜닝

step size, goal bias, 최대 반복 횟수 등의 매개변수가 결과에 영향을 준다.

16.4 무작위성

RRT는 무작위 알고리즘이므로 같은 입력에 대해 다른 결과를 산출할 수 있다.

17. 라이브러리 지원

17.1 OMPL

OMPL은 다양한 RRT 변형을 구현한다.

#include <ompl/geometric/planners/rrt/RRT.h>
auto planner = std::make_shared<og::RRT>(si);

지원되는 변형:

RRT
RRT-Connect
RRT*
Informed RRT*
LBT-RRT (Lower Bound Tree RRT)
T-RRT (Transition-based RRT)

17.2 MoveIt

MoveIt은 OMPL을 통해 RRT 변형들을 지원한다.

17.3 다른 라이브러리

Drake
Klampt
ROS의 navigation 패키지

18. 학습의 가치

RRT를 깊이 이해하는 것은 다음과 같은 이점을 제공한다.

샘플링 기반 운동 계획의 핵심 알고리즘을 익힌다.
고차원 공간에서의 운동 계획을 학습한다.
다양한 로봇 시스템의 운동 계획 표준 도구를 습득한다.
트리 기반 접근법의 장단점을 이해한다.
OMPL 등의 운동 계획 라이브러리를 효과적으로 사용할 수 있다.

19. 학습 권장사항

19.1 직접 구현

간단한 2차원 환경에서 RRT를 직접 구현해 본다. 점차 고차원으로 확장한다.

19.2 시각화

RRT의 트리 확장과 경로를 시각화하면 이해가 깊어진다.

19.3 변형 학습

RRT*, Bidirectional RRT, Informed RRT* 등의 변형을 학습한다.

19.4 응용 학습

실제 로봇 응용에 RRT를 적용해 본다. OMPL을 활용한다.

20. 본 절의 의의

본 절은 급속 탐색 무작위 트리(RRT)를 자세히 다루었다. RRT는 샘플링 기반 운동 계획의 가장 영향력 있는 알고리즘 중 하나이며, 매니퓰레이터, 모바일 로봇, 무인 항공기 등 다양한 시스템의 운동 계획에서 표준이다. RRT의 이해는 현대 로봇공학의 운동 계획을 학습하는 데 필수적이다.

21. 참고 문헌

LaValle, S. M. (1998). “Rapidly-exploring random trees: A new tool for path planning.” Technical Report TR 98-11, Computer Science Dept., Iowa State University.
Kuffner, J. J., & LaValle, S. M. (2000). “RRT-connect: An efficient approach to single-query path planning.” IEEE International Conference on Robotics and Automation, 995–1001.
Karaman, S., & Frazzoli, E. (2011). “Sampling-based algorithms for optimal motion planning.” International Journal of Robotics Research, 30(7), 846–894.
Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2014). “Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic.” IEEE/RSJ International Conference on Intelligent Robots and Systems, 2997–3004.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
Şucan, I. A., Moll, M., & Kavraki, L. E. (2012). “The Open Motion Planning Library.” IEEE Robotics & Automation Magazine, 19(4), 72–82.

version: 1.0