논문

[RRT] RRT - Connect : An efficient Approach to single-Query path planning

정지홍 2025. 4. 10. 08:24

Steven M. LaValle

 

Steven M. LaValle

Rapidly exploring Random Trees (RRTs) Back in June 1998, I introduced the RRT (see this Iowa State tech report), which is a simple, iterative algorithm that quickly searches complicated, high-dimensional spaces for feasible paths. The idea is to incrementa

lavalle.pl

 

 

0. Abstract

  • 고차원 공간에서 single-query path planning문제를 해결하기 위한, 효율적이고 간단한 randomized algorithm을 제안한다.
  • 이 방법은 고차원 공간에서 start와 goal을 root로 하는 두개의 RRT를 점진적으로 구축하는 방식으로 동작한다.
  • 각 트리는 자신의 주변 공간을 탐색하며, 동시에 greedy heuristic을 사용해서 서로를 향해 나아간다.
  • 원래 해당 알고리즘은 충돌 없는 물체 잡기 및 조작 작업의 자동 그래픽 애니메이션을 위해서, 인간의 팔에 대한 움직음을 계획하기 위해서 설계되었으나, 다양한 경로 계획 문제에 성공적으로 적용되었습니다.
  • 계산의 예시로는 2D 및 3D 공간에서의 물체에 대한 충돌 없는 움직임 생성, 그리고 3D작업 공간에서의 6자유도인 PUMA 로봇 팔에 대한 충돌없는 조작 움직임 생성등이 존재합니다.
  • 또한 일부 기본적인 이론 분석도 함께 제시합니다.

 

그림 1 . 자유도가 7인 인간팔의 path planning

1. Introduction

  • motion planning문제는 다양한 분야에서 발생합니다. 이러한 문제는 하나 이상의 복잡한 기하학적 물체의 시스템 구성 공간에서, 주어진 start와 goal을 연결하는 collision free path를 찾는 작업을 포함하며, 동시에 obstacle로 인해 부과되는 constrain 조건도 만족시켜야 합니다.
    • 이러한 일반적인 클래스의 문제에 대해서는 완전한 알고리즘들이 알려져있습니다. 하지만 이들의 계산 복잡도는 저차원 공간에서만 현실적으로 사용이 가능하다는 한계가 존재합니다. 
    • 계산 복잡도에 대한 한계와 실제적인 planning문제를 해결하고자는 동기들은, randomization을 사용하는 다양한 path planning기법을 개발하게 했습니다.
    • 이러한 방법들은 '불완전하지만, 충분한 실행시간이 주어진다면 어떤 확률로든 해를 찾는다'라는 절충안이 있습니다.
      여기에서 핵심은 실제로 빠르게 수렴하면서도 일관된 동작과 분석이 가능한 단순한 randomization기법을 개발하는 것입니다.
    • randomized path planning algorithms은 보통 두가지 상황중 하나를 위해서 설계됩니다. 
      • single-query planning : 하나의 path planning문제를 어떠한 preprossessing없이 빠르게 해결해야 한다고 가정합니다. 이 방법에서 쉽고 인기있는 방법중 하나는 randomized potential field 방법이 있습니다.
      • multiple-query planning : 동일한 환경에서 여러개의 path planning 문제가 반복적으로 해결되어야 한다고 가정한다. 이러한 경우에는 정보를 미리 처리해서 빠른 query를 가능하게 하는 data structture에 저장해두는게 더 효율적이다. 이러한 방법을 다룬 접근법은 PRM이다. 이는 configuration space에서 무작위로 많은 configuration을 선택하고, 근처의 구성쌍을 local planner로 연결하여 그래프를 생성합니다.
      • 이러한 randomized 방식은 단순하면서도, 신뢰할 수 있는 동작으로 인해 최근에 큰 성공을 거두었으며, 현재는 이론적 분석과 병목 현상 같은 예외적인 상황 처리에 초점이 맞춰져 있습니다.
      • single-query 문제에서 potential field planner가 더 나은 성능을 보일수 있음에도, 신뢰성 덕분에 PRM 방식이 선호되어 왔습니다. potential field planner는 configuration space위에 potential function형태로 greedy heuristic을 encoding하여 빠른 해를 찾기도 했지만, local minimum에 빠졌을 경우에는 이를 탈출하기 위해서 random walk를 사용하는 방식은 신뢰성 보장이 어려웠습니다.
        • 이러한 배경에서, PRM의 장점을 가지면서도 single-query 문제에 특화된 단순하고 신뢰할 수 있는 방법에 대한 요구가 생겼습니다.
          그래서 우리는 RRT와 두 트리를 공격적으로 연결하려는 단순한 greedy hueristic을 결합한 것 입니다.
    • RRT-Connect는 초기 구성과 목표 구성에서 각각 트리를 확장하는 아이디어는 AI의 bidirectional search에서 유래한 것이며, 이전의 motion planning 방법에서의 활용은 [12]에서 정리되어 있습니다.
    • 최근에는 고 자유도 문제에 대해서 흥미로운 무작위 양방향 플래너가 제안되기도 했습니다.
      • 우리의 핵심은 RRT를 단순한 샘플링 기법이자 데이터 구조로 활용하여, 구성공간을 빠르고 균일하게 탐색하도록 하는 것 입니다.
      • RRT - Connect는 다양한 경로 계획 문제에서도 효율적이고 신뢰성 높게 적용이 될수 있습니다.

 

2. RRT

  • path planning 문제는 일반적으로 configuration space인 C에서의 탐색문제라고 할 수 있습니다.
    • 이 구성공간의 각 q ∈ C는 2D or 3D세계에서 하나 이상의 복잡한 기하학적 물체의 position과 oridentation을 나타냅니다.
    • 구성 공간 C에는 거리 개념( 메트릭 ) ρ가 정의되어 있다고 가정합니다. ( 다시 말하면, "거리를 구하는 방법인 ρ가 정의되어 있다라고 가정하자. " 라는 의미 )
  • C free는 장애물과 충돌하지 않는 구성들의 집합이다. 장애물들은 세계 내에서 완전히 모델링 되어 있으나, C free에 대한 명시적인 표현은 존재하지 않는다. 하지만 충돌 판별 알고리즘을 사용하면, 주어진 q ∈ C 가 C free에 속하는지 여부를 테스트 할 수 있다.
    • single-query path planning문제는 초기 구성인 q init에서 목표인 q goal로의 연속적인 경로를 preprocessing없이 계산하는 것이다.
  • RRT는 sampling기반 기법이며, 장애물로 인한 대수적 제약과 nonholonomic or dynamics 제약이 있는 고차원 공간을 빠르게 탐색하는데 적합합니다.
    • 이것의 핵심 아이디어는 덜 탐색된 공간 방향으로 편향( bias )시키는 것입니다.
    • 이와 유사한 아이디어로는 path planning연구에서 제안된 Ariadne's clew 알고리즘이나, expansive configuration space 개념 등이 있습니다. 또한 state space에서 두개의 RRT를 생성하고 연결하여, kynodynamics and nonholonomic path planning을 수행하는 방법이 제안되었습니다.
    • 본 논문에서는 미분제약이 없으며, 문제를 configuration space C로 표현할 수 있는 경우에 특화된  방식을 제시합니다.

figure2 . the basic RRT construction algorithm
figure 3. the extend operation

  • 기본적인 RRT 구성 알고리즘은 figure 2에 제시되어 있습니다.
    • 이 알고리즘은 간단한 iteration으로 구성되며, 각 단계에서 무작위로 선택된 구성 방향으로 RRT를 확장하려고 시도합니다.
    • EXTEND 함수를 보면 샘플링 된 q에서, RRT내의 정점중 가장 가까운 것을 선택합니다. ( line1) 
      그후에는 NEW_CONFIG함수로 q방향으로 고정된 거리 ε 만큼이동합니다. ( 단, 해당되는 경로에 충돌이 있는지 없는지 테스트 하면서... 이때 테스트는 증분 거리 계산 알고리즘을 사용하면 빠르게 가능. [9,20,22] )
      • 고정된 거리만큼 이동할때 3가지 상황이 발생할 수 있다.
      • 1. Reached : q근처에 이미 정점이 있어서, q를 직접 RRT에 추가할
      • 2. Advanced : q != q new인 새로운 정점이 추가된 경우
      • 3. Trapped : 새 정점이 C free에 속하지 않아서 거부된 경우
  • 아래 figure4의 상단은 2d 정사각형 공간에서 구성된 RRT를 보여주고, 하단은 그 정점들에 대한 보로노이 다이어그램을 보여줍니다.
    • 여기에서 각 정점이 확장을 위해서 선택될 확률은 자신의 보로노이 영역의 면적에 비례합니다. 이로 인해서 RRT는 미탐색 영역을 빠르게 탐색하는 경향을 가지게 됩니다.
    • 섹션 4에서 RRT가 구성 공간을 균일하게 커버하게 됨을 보여줄것이며, 이는 PRM의 특성과도 일치한다.

 

3. The RRT-Connect Path Planner

  • RRT-Connect planner는 미분 제약이 없는 path planning문제에 특화되어 설계된 알고리즘 입니다.
    • 이러한 경우에는 점진적인 움직임의 필요성이 상대적으로 덜 중요합니다.
    • 이 방법은 아래 2가지 주요 아이디어에 기반합니다.
      • 1. 더 긴 거리로 이동하려는 connect 휴리스틱
      • 2. start와 goal에서 각각의 RRT를 확장해 나아가는 전략
  • Connect heuristic
    • connect heuristic은 greedy함수로써, figure 2에 나오는 EXTEND함수의 대안으로 볼 수 있습니다.
      • EXTEND함수는 한 단계만 RRT를 확장하는데 반해서, Connect는 q or obstacle에 도달할 때 까지 EXTEND를 반복합니다. ( 이는 figure 5에 설명됨 )
      • 이 동작은 randomized potential field에서 사용하는 airtificail potential 함수와 유사하다. 두 방식은 모두 greey하게 빠르게 해에 수렴한다. 
        그래서 RRT-Connect는 greedy전략을 더해서 RRT를 더 빠르게 만들고, local minima에 빠지는 문제를 회피할수 있다. 
        • 비유하자면, potential field방식에서는 'basin of attraction'이 고정되어 있지만, RRT-Connect에서는 RRT가 성장함에 따라서 그 attraction이 계속 이동하게 됩니다.

figure 5. the RRT-Connect algorithm

  • RRT-Connect planner algorithm
    • figure 5는 RRT-Connect planner 알고리즘을 보여주며, figure 2의 BUILD-RRT와 비교 될수있다.
    • 이 알고리즘에서는 2개의 트리가 항상 유지되며, 서로 연결되어 경로가 발견될때까지 확장합니다.
    • 각 반복에서..
      • 1. 한쪽 트리가 확장되고,
      • 2. 다른 한쪽 트리에서 가장 가까운 정점이 새 정점에 연결을 시도하며,
      • 3. 그 이후에는, 두 트리가 서로의 역할을 스왑해서 서로 번갈아 가면서 확장한다.
    • 이는 두 트리가 모두 자유 구성 공간 C free를 탐색하면서, 서로 연결되기 위해 노력하게 만드는 전략입니다.
      • 이와 유사하게 [19]에서 kinodynamic planning을 위해 제안된 적이 있으나, 이는 두 트리가 단지 무작위 구성 방향으로 확장되었을뿐, 서로를 향해서 확장하지는 않았습니다.
      • 현재의 알고리즘에서는 서로를 향하면서 성장하는게 훨씬 더 좋은 성능을 보였습니다.

  • 가능한 다양한 변형
    • 1. RRT-Connect Planner에서 Connect를 EXTEND로 바꾸면, 단순한 두개의 RRT기반 planner가 된다.
    • 2. EXTEND를 Connect로 바꾸면, 더 강력한 greedy heuristic을 가진 탐색 플래너가 된다.
    • 3. EXTEND반복에서 마지막 정점만 RRT에 추가할수 있도록 Connect를 조정하는것. ( 이러면 생성되는 노드 수를 줄일수있다. )
  • Connect함수의 장점은, 단 한번의 knn탐색으로 긴 경로를 생성할 수 있다는 것이다.

 

 

4. Analysis

  • 이번절에서는 RRT와 RRT-Connect에 대한 분석을 할것이다.
  • 분석의 핵심 결과는 아래와 같다.
    • 1. RRT의 정점 분포는 일반적으로 uniform sampling distribution을 따르도록 수렴한다.
    • 2. RRT-Connect알고리즘은 probabilistic completeness를 갖는다. => 즉, 충분한 시간이 존재한다면 경로를 찾을 확률은 1에 수렴한다. ( 다만, 수렴 속도에 대한 이론적인 특성은 아직 제시되지 않았지만, 실제로는 매우 빠르게 수렴하는 것으로 관찰된다. )

 

 

 

5. Exeriments 

  • 실험 대상 : 2d와 3d에서 강체의 움직임. 6자유도의 로봇팔 , 가상의 캐릭터와 피아노
  • 경로 후처리 : 최종 경로는 스무딩 처리로 부드럽게함
  • 충돌 검사 : OBB_Tree기반의 RAPID사용 
  • 성능 비교
    • 장애물이 적은 환경에서는 connect가 3~4배 빠르지만, 장애물이 많은 환경에서는 속도 향상은 거의 없었다.
  • 기타사항
    • connect는 공간이 넓고 개방된 환경에 효과적

6. Conclusions

  •  RRT-Connect는 single-query path planning에 효과적인 알고리즘이다.
  • 장점
    • 1. 파라미터 튜닝 불필요
    • 2. 사전 처리 없어도 괜찮은 속도
    • 3. 반복 실험에서도 단순하고 안정적인 동작
    • 4. greedy탐색과 균일한 탐색 사이의 균형
    • 5. 빠른 거리 계산과 최근접 탐색 알고리즘에 잘맞음
  • 향후과제
    • 현재까지의 성능은 긍정적이나 더 많은 벤치마크 실험 필요
    • 특정 조건에서는 성능이 급격히 나빠질 수 있음. 병목 사례 분석 필요