RRT*
- 다른 이름: RRT star, RRT-star, optimal RRT
- 카테고리: Planning & manipulation › Motion planning
- 태그: motion-planning, sampling-based-planning, path-planning, optimization, manipulation
Rapidly-exploring Random Tree 플래너의 점근적으로 최적인 버전으로, 트리가 자라면서 재배선하여 반환하는 경로가 최저 비용 경로를 향해 계속 개선되게 한다.
정의
RRT\("RRT 스타"로 읽음)는 충돌 없는 경로를 찾고, 샘플이 충분하면 최적 경로로 수렴해 가는 샘플링 기반 동작 계획 알고리즘이다. 2011년 Sertac Karaman과 Emilio Frazzoli가 1998년 Steven LaValle이 제안한 Rapidly-exploring Random Tree(RRT) 알고리즘의 확장으로 발표했다.
원래의 RRT는 구성 공간에서 무작위 점을 반복적으로 샘플링하고, 트리에서 가장 가까운 노드를 찾아, 그 움직임에 충돌이 없으면 샘플 쪽으로 짧게 한 걸음 확장하는 방식으로 출발 구성에서부터 트리를 키운다. RRT는 로봇 암의 관절 공간 같은 고차원 공간에서도 실행 가능한 경로를 빠르게 찾지만, 그 경로는 보통 들쭉날쭉하고 최단 경로와 거리가 멀며, 샘플을 더 추가해도 개선되지 않는다.
RRT*는 두 가지를 바꾼다. 새 노드를 추가할 때 이웃 반경 안의 모든 트리 노드를 살펴, 단순히 가장 가까운 노드가 아니라 출발점으로부터의 비용이 가장 낮아지는 노드에 연결한다. 그런 다음 재배선(rewire)한다. 각 이웃에 대해 새 노드를 거쳐 가는 경로가 더 저렴하면 그 이웃의 부모를 바꾼다. Karaman과 Frazzoli는 트리가 커짐에 따라 이웃 반경을 적절히 줄이면, 샘플 수가 무한대로 갈 때 해의 비용이 최적값으로 수렴함을 보였으며, 이 성질을 점근적 최적성이라고 한다.
그 대가는 샘플당 추가 연산이므로, RRT는 첫 해를 찾는 데 RRT보다 느리다. Informed RRT와 BIT* 같은 변형은 샘플링을 집중시켜 수렴 속도를 높인다.
중요한 이유
많은 로봇에게는 아무 경로가 아니라 더 짧거나, 더 매끄럽거나, 에너지가 덜 드는 좋은 경로가 필요하다. RRT*는 고차원 구성 공간으로 확장되는 샘플링 기반 플래너에 경로 품질로 가는 원리적인 방법을 제공하며, 동작 계획 연구와 소프트웨어에서 표준 기준선이다.
주요 응용
- 복잡한 작업 공간에서 로봇 암의 충돌 없는 동작 계획
- 모바일 로봇과 드론의 전역 경로 계획
- 격자 탐색이 비실용적인 고차원 구성 공간에서의 계획
- 궤적 최적화를 위한 참조 경로 생성
실제 사례
로보틱스 팀은 보통 RRT를 직접 작성하기보다 계획 라이브러리를 통해 사용한다. MoveIt이 로봇 암에 사용하는 Open Motion Planning Library(OMPL)에는 RRT, RRT-Connect, PRM과 함께 RRT와 그 여러 변형이 들어 있다. 흔한 패턴은 고정된 시간 예산으로 RRT를 실행하고, 시간이 다 되었을 때까지 찾은 가장 좋은 경로를 가져온 뒤, 지름길 처리와 평활화를 거쳐 시간 파라미터화된 궤적으로 변환하는 것이다. 모바일 로봇과 드론의 경우 팀은 2D 또는 3D 점유 지도 위에서 RRT를 전역 플래너로도 사용하며, 계획 시간과 스텝 크기를 골라 경로 품질과 응답 시간을 맞바꾼다.
흔한 오해
- RRT*는 최적 경로를 반환한다 — 점근적으로 최적일 뿐이므로, 경로 비용은 샘플 수가 한없이 늘어날 때에만 최적값에 다가간다
- RRT* 경로는 매끄럽다 — 구간별 선형이며, 실행 전에 보통 지름길 처리와 평활화가 필요하다
- RRT*는 항상 RRT보다 낫다 — 실행 가능한 경로만 빨리 필요할 때는 일반 RRT나 RRT-Connect가 더 나은 선택인 경우가 많다
알아야 할 사람
- 동작 계획 엔지니어
- 로봇 암 및 조작 소프트웨어 개발자
- 자율 드론 및 모바일 로봇 개발자
- 계획 알고리즘을 공부하는 로봇공학 학생
관련 기술
- OMPL
- MoveIt
- RRT-Connect
- Informed RRT*
- BIT*
- 충돌 검사(Collision Checking)
관련 용어
관련 프로젝트
- LeRobot: HuggingFace ML library for real-world robotics in PyTorch
- Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
- NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
- OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
- Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
동영상
- Path Planning with A* and RRT | Autonomous Navigation, Part 4: MATLAB