Path Planning : Roadmap-based 방법과 Tree-based 방법의 차이점

Figure from TRG-planner(https://arxiv.org/pdf/2501.01806)

모바일 로봇의 Path planning을 공부하다 보면 가장 먼저 마주하게 되는 것은 Dijkstra, A*이고, 그 다음이 PRM과 RRT입니다. 샘플을 뿌린다는 점에서 유사해 보이는 이 두 알고리즘을 비교해 보고자 합니다. 

PRM (Probabilistic RoadMap)

Roadmap-based planning에서 가장 유명한 방법은 Probabilistic RoadMap(PRM) 입니다. 기본적으로는 Configuration space에서 미리 그래프(roadmap)을 구성하고, 여기서 노드는 valid configuration을, 엣지는 feasible path를 표현합니다. 이후 사용할 때는 시작점과 목표점을 roadmap에 연결하여 경로를 탐색합니다. 

Example

┌──────────────────────┐
│      ▉▉▉▉            │
│  S   ▉▉▉▉            │
│      ▉▉▉▉    ▉▉▉     │
│             G ▉▉▉    │
│          ▉▉  ▉▉▉     │
└──────────────────────┘
S: Start point
G: Goal point
▉: Obstacles

1. Random sampling

┌──────────────────────┐
│  •   ▉▉▉▉    •       │
│  S   ▉▉▉▉  •         │
│   •  ▉▉▉▉    ▉▉▉     │
│    •        G ▉▉▉    │
│  •       ▉▉  ▉▉▉     │
└──────────────────────┘
- : Random samples in Cfree

Configuration space에서 랜덤하게 점들을 샘플링한 후, Collision check를 통해 valid한 샘플만 유지합니다. 시작점(S)와 목표점(G)도 로드맵에 추가합니다. 

2. Local Planner (연결)

┌──────────────────────┐
│  •   ▉▉▉▉    •       │
│  S   ▉▉▉▉  •         │
│   •  ▉▉▉▉    ▉▉▉     │
│   \ •───────G ▉▉▉    │
│  •       ▉▉  ▉▉▉     │
└──────────────────────┘
───: Valid connections

각 샘플에 대해서 주변 neighbor점들을 KNN등으로 탐색하고, Local planner를 통해 Collision-free 경로를 확인합니다. Valid한 연결만 유지하여 그래프를 구성합니다. 

3. 최종 로드맵 (Query) 

┌──────────────────────┐
│  •───▉▉▉▉────•       │
│  S   ▉▉▉▉  •         │
│   •  ▉▉▉▉    ▉▉▉     │
│   \\ •══════G ▉▉▉    │
│  •       ▉▉  ▉▉▉     │
└──────────────────────┘
═══: Final path

시작점과 목표점을 roadmap에 연결하고, 그래프 탐색 알고리즘 (ex.Dijkstra, A*) 등으로 경로를 찾습니다. 

이렇게 구성된 roadmap은 재사용이 가능하고 (한 번 구축된 맵으로 여러 경로를 쿼리할 수 있고), 샘플 수가 증가할 수록 해를 찾을 확률이 증가하게 됩니다. 

RRT (Rapidly-exporing Random Tree)

Example

1. Initialize : First expand

┌──────────────────────┐
│      ▉▉▉▉            │
│  S→•  ▉▉▉▉           │
│      ▉▉▉▉    ▉▉▉     │
│             G ▉▉▉    │
│          ▉▉  ▉▉▉     │
└──────────────────────┘
x: 랜덤 샘플
- : 새로운 노드
→: 트리 연결

시작점 S를 트리의 루트 노드로 설정합니다. 

2. 계속 확장

┌──────────────────────┐
│      ▉▉▉▉            │
│  S→•  ▉▉▉▉           │
│   ↘•   ▉▉▉▉    ▉▉▉   │
│    ↘•        G ▉▉▉   │
│      •   ▉▉  ▉▉▉     │
└──────────────────────┘

┌──────────────────────┐
│      ▉▉▉▉    •       │
│  S→•  ▉▉▉▉   ↗       │
│   ↘•   ▉▉▉▉  • ▉▉▉   │
│    ↘•────→•→G ▉▉▉    │
│      •   ▉▉  ▉▉▉     │
└──────────────────────┘

Configuration space에서 무작위로 점들을 선택하여 반복적으로 트리를 확장해나갑니다. 이때 단계는 다음과 같습니다. 

a) 랜덤 샘플링 : Configuration space안에서 무작위로 점(x_rand)을 하나 선택
b) 최근접 노드 찾기 : 현재 트리 T에서 랜덤 샘플(x_rand)과 가장 가까운 노드(x_nearest) 찾기
c) 새로운 노드 생성 : x_nearest에서 x_rand 방향으로 정해진 step size만큼만 이동한 새로운 점(x_new) 생성
d) 충돌 검사 : x_nearest에서 x_new까지의 경로가 장애물과 충돌하는 지 확인
e) 트리에 추가 : x_new를 T에 추가. 이때 x_nearest를 x_new의 부모 노드로 설정하고 edge 추가

3. 최종 경로 

┌──────────────────────┐
│      ▉▉▉▉    •       │
│  S→•  ▉▉▉▉   ↗       │
│   ↘•   ▉▉▉▉  • ▉▉▉   │
│    ↘•────→•→G ▉▉▉    │
│      •   ▉▉  ▉▉▉     │
└──────────────────────┘

트리가 목표점에 도달하면, 목표점에서부터 시작점까지 부모 노드를 거슬러 올라가면서 경로를 생성하고 이 경로가 최종 해가 됩니다. 

 

Roadmap 방식과 Tree 방식의 차이점

샘플을 뿌리고 유효한 샘플들을 연결한다는 점에서 Roadmap 방식과 Tree 방식이 비슷하다고 느낄 수 있지만, 다음과 같은 점에서 차이가 있습니다. 

1. 구조와 성장 방식의 차이

PRM (Graph):                    RRT (Tree):
     • ─── •                        •
    /  \    \                     / | \
   •    •────•                   •  •  •
    \   |    /                    \ |
     •──•───•                      •
     
- 순환 가능                    - 순환 없음
- 양방향 연결                  - 단방향 연결
- 한번에 전체 공간 커버        - 점진적 확장

우선 PRM은 전체 공간에서 무작위로 샘플링을 한 후 이를 연결하고, RRT는 시작점에서부터 점진적으로 트리를 확장하게 됩니다. 따라서 PRM은 주로 지도가 있는 환경에서 진행하고, RRT는 Mapless, 즉 지도가 없는 실시간 경로 탐색에서 주로 사용이 됩니다. 또한 PRM은 양방향 그래프이지만 RRT는 단방향 트리라는 점에서도 차이가 있습니다. 그리고 PRM의 경우 전체 맵을 메모리에 유지하고 재사용하면서 경로를 여러 번 찾지만, RRT는 현재 쿼리에 대한 트리만 저장합니다. 

PRM:                           RRT:
[전체 맵 구축]                    [시작]
      ↓                          ↓
[다중 쿼리 재사용]               [트리 성장]
                                 ↓
                             [목표 도달]
                                 ↓
                             [트리 폐기]

따라서 PRM은 같은 환경에서 여러 경로를 반복적으로 찾아야 할 때 사용되고, RRT는 단일 쿼리 문제나 동적 환경에서 경로를 계획할 때 적합한 방법이라고 할 수 있습니다. 

Compared to radmap-based methods such as PRM, tree-based methods do not require a steering function, which requires solving the two-point boundary value problem[1].

Steering function이란 두 Configuration 사이를 연결하는 정확한 경로를 생성하는 함수이므로, Two-point boundary value problem은 시작점(boundary 1)과 도착점(boundary 2)이 주어졌을 때 연결하는 경로를 찾는 문제입니다. 

PRM의 경우

노드 A ----→ 노드 B
    정확히 B에 
    도달해야 함

이와 같이 샘플링된 두 점을 정확히 연결하는 경로가 필요합니다. 이는 로봇의 운동학/동역학 제약을 만족하면서 두 점을 연결해야 하므로 복잡한 시스템에서는 이런 경로를 찾기가 어려울 수 있습니다. 

하지만 RRT의 경우

현재노드 ---→ 랜덤샘플방향
    정확한 도달이
    필요없음

현재 노드에서 랜덤 샘플 방향으로 step size만큼만 나아가면 되기 때문에 정확한 목표점에 도달할 필요가 트리 확장 단계에서는 없습니다. 따라서 이 문장은 PRM은 더 정확한 경로 계획이 가능하지만 steering function 구현이 어렵고, RRT는 덜 정확할 수 있지만 구현이 더 쉽고 실제 로봇 시스템에 적용하기 용이하다는 점을 지적하고 있습니다.

[1] Neural Kinodynamic Planning: Learning for KinoDynamic Tree Expansion, 2024 IROS