Rapidly-exploring random tree
- 다른 이름: RRT
- 카테고리: Planning & manipulation › Motion planning
- 태그: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance
무작위 상태를 반복해서 샘플링하고 가장 가까운 트리 노드를 그쪽으로 확장하는 방식으로 시작 상태에서 트리를 키워, 큰 공간을 빠르게 탐색하는 샘플링 기반 모션 계획기.
정의
급속 탐색 랜덤 트리(rapidly-exploring random tree, RRT)는 시작 상태에서 목표 영역까지의 실현 가능한 경로를 찾는 샘플링 기반 알고리즘이다. 1998년 Steven LaValle이 도입했다. 이 알고리즘은 시작 상태를 루트로 하는 트리를 키운다. 매 반복마다 형상 공간 또는 상태 공간에서 무작위 상태를 샘플링하고, 트리에서 가장 가까운 노드를 찾고, 그 노드에서 샘플 쪽으로 짧은 거리만큼 확장한다. 확장이 충돌 없이 이루어지면 새 상태를 트리에 추가한다. 트리가 목표 영역에 도달하면 탐색이 끝나고, 각 노드의 부모를 따라 거슬러 올라가며 경로를 읽어 낸다.
핵심 성질은 보로노이 편향(Voronoi bias)이다. 트리의 경계에 있는 노드들은 보로노이 영역이 가장 크므로 무작위 샘플에 가장 가까울 가능성이 가장 높고, 따라서 트리는 이미 덮은 영역을 채우는 대신 탐색되지 않은 공간 쪽으로 끌려간다. 이 덕분에 RRT는 로봇 암의 관절 공간 같은 고차원 공간에서 효과적이다. RRT는 확률적으로 완전하다. 해가 존재하면 샘플 수가 늘어날수록 그 해를 찾을 확률이 1에 가까워진다. 흔한 개선으로는 샘플의 일부를 목표에서 뽑는 목표 편향(goal biasing), 그리고 시작과 목표 양쪽에서 트리를 키워 탐욕적으로 잇는 RRT-Connect가 있다.
확장 단계는 한 상태에서 다른 상태 쪽으로 이동하는 방법만 있으면 되므로, RRT는 로봇이 상태 공간에서 직선으로 움직일 수 없는 운동동역학적(kinodynamic) 계획도 다룬다. 이때 확장 단계는 샘플링되거나 최적화된 제어 입력을 적용하고 동역학을 앞으로 시뮬레이션하거나(LaValle과 Kuffner의 kinodynamic RRT처럼), 미리 계산된 모션 프리미티브를 이어 붙인다. 이 덕분에 거리 척도와 확장 단계를 동역학에 맞춰 설계해야 하는 차량, 보행 로봇, 접촉이 많은 조작에 유용하다. RRT의 경로는 대개 들쭉날쭉하고 최적이 아니며, 경로를 한 번 찾은 뒤에는 샘플을 더 추가해도 경로가 개선되지 않는다. RRT\는 부모 선택 단계와, 더 싼 경로가 있을 때마다 근처 노드를 다시 연결하는 재배선(rewiring) 단계를 추가하여, 샘플당 계산량이 늘어나는 대가로 점근적으로 최적이 된다. 실현 가능한 경로가 빨리 필요할 때는 기본 RRT나 RRT-Connect 뒤에 지름길 처리와 평활화를 붙이는 방식이 여전히 흔한 선택이다.
중요한 이유
RRT는 자유도가 많은 로봇과 동역학을 가진 시스템에서 모션 계획을 실용적으로 만들었고, 지금도 OMPL과 MoveIt 같은 라이브러리의 기본 계획기이다. RRT*를 비롯한 많은 후속 계획기가 그 구조 위에 세워졌다.
주요 응용
- 복잡한 작업 공간에서의 로봇 암 모션 계획
- 자동차, 드론, 보행 로봇을 위한 운동동역학적 계획
- 맞춤 거리 척도를 사용한 접촉이 많은 조작 계획
- 보행을 위한 모션 프리미티브 그래프 위의 계획
- 미지 환경의 탐사
실제 사례
선반에서 물품을 집는 7축 팔을 위해 MoveIt을 구성하는 팀이 OMPL의 RRT-Connect를 기본 계획기로 사용한다. 충돌 검사에는 로봇 모델과 깊이 카메라로 만든 옥트리를 사용한다. 이들은 계획 시간 한도와 확장 스텝 크기를 선반 입구의 여유 공간에 맞춰 설정한 다음, 각 경로를 지름길 처리와 시간 매개변수화로 후처리해 팔이 매끄럽게 움직이게 한다. 좁은 선반 칸 깊숙이 도달하는 계획이 잘 안 될 때는 목표 편향을 높이거나 좁은 통로에서 더 잘 동작하는 계획기를 시도하고, 정적인 셀에서 반복되는 질의에는 대신 확률적 로드맵을 고려한다.
흔한 오해
- RRT는 최단 경로를 찾는다 — RRT는 실현 가능한 경로를 찾는다. 좋은 경로 품질을 얻으려면 RRT*나 후처리가 필요하다
- RRT는 정해진 시간 안에 경로를 찾는 것이 보장된다 — RRT는 확률적으로 완전하므로 샘플링을 계속할수록 경로를 찾을 확률이 1에 가까워질 뿐이며, 좁은 통로는 오래 걸릴 수 있다
- RRT가 항상 더 나은 선택이다 — RRT는 시간이 지나며 경로를 개선하지만 첫 해까지는 더 느리다. 속도가 중요할 때는 평활화를 곁들인 RRT-Connect가 흔히 선호된다
알아야 할 사람
- 모션 계획 엔지니어
- MoveIt이나 OMPL을 사용하는 조작 및 모바일 로봇 개발자
- 자율주행차 및 드론 계획 엔지니어
- 로보틱스 학생
관련 기술
- OMPL
- MoveIt
- RRT-Connect
- Kinodynamic RRT
- Informed RRT*
- 경로 지름길 처리(Path Shortcutting)
관련 용어
관련 프로젝트
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
- ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
- OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
- MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
- PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
- mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
동영상
- Motion Planning: Rapidly Exploring Random Trees (RRT): Algorithm Implementation Step by Step!: VDEngineering