대상: 자율주행, 로봇 내비게이션에서 다양한 경로 계획(Path Planning) 알고리즘의 원리를 비교하고 싶은 개발자
환경: ROS/ROS2, SLAM/Navigation Stack 기반 로봇 혹은 자율주행 차량
1. 문제/주제 요약
자율주행이나 로봇의 경로 계획(Path Planning) 은
“시작점에서 목적지까지 장애물을 피하면서 이동 가능한 경로를 찾는 과정”입니다.
이때 사용되는 대표 알고리즘은 다음 세 가지 계열로 나뉩니다:
- A*: 고전적 격자 탐색 기반
- D*: 동적 환경에서도 빠르게 재탐색 가능
- 샘플링 기반 (Sampling-based): 복잡한 공간에서도 효율적 탐색 (RRT, PRM 등)
이 글에서는 각 알고리즘의 개념, 동작 방식, 장단점을 비교해봅니다.
2. 경로 계획의 기본 개념
경로 계획은 크게 두 단계를 포함합니다:
1️⃣ 탐색(Search) — 목표까지 갈 수 있는 후보 경로를 찾음
2️⃣ 최적화(Optimization) — 후보 중에서 거리·곡률·안전도 등을 고려해 최적 경로 선택
일반적인 ROS 내비게이션 플로우는 다음과 같습니다:
Map (Occupancy Grid)
↓
Global Planner (A*, D*, PRM, etc.)
↓
Local Planner (Trajectory optimization, MPC)
3. A* 알고리즘 (A-star): 전통적 격자 탐색
(1) 개념
A*는 Dijkstra 알고리즘에 휴리스틱(heuristic) 을 더한 형태입니다.
즉,
“현재까지의 실제 비용 + 앞으로 남은 거리의 추정치”
를 합산해 탐색 우선순위를 정합니다.
(2) 평가 함수
f(n) = g(n) + h(n)
g(n): 시작점에서 현재 노드까지의 실제 비용h(n): 목적지까지의 예상 거리 (ex. 유클리드 거리)
(3) 예시 (2D Grid)
def heuristic(a, b):
return sqrt((a.x - b.x)**2 + (a.y - b.y)**2)
(4) 특징
✅ 장점
- 최단경로 보장 (휴리스틱이 admissible하면)
- 구현 간단, ROS Navigation 기본 Global Planner
⚠️ 단점
- 복잡한 환경에서 느림
- 차량의 회전 반경, 동역학 제약을 반영하기 어려움
4. D* / D*-Lite: 동적 환경을 위한 A* 확장
(1) 개념
A*는 맵이 고정되어 있을 때만 유효하지만,
자율주행에서는 장애물이 움직이거나 맵이 업데이트될 수 있습니다.
D* (Dynamic A-star)는 이전 탐색 결과를 재활용하여
경로 일부만 다시 계산합니다.
(2) 동작 흐름
1️⃣ 초기 A* 탐색 수행
2️⃣ 새로운 장애물 등장 시, 영향 받은 구간만 재탐색
3️⃣ 나머지 노드 비용은 그대로 유지
(3) 대표 변형
| 알고리즘 | 특징 |
|---|---|
| D* | 원본 (Stentz, 1994) |
| D*-Lite | 구현 단순화, ROS 적용 용이 |
| Anytime D* | 시간 제약 하에서 점진적 개선 |
(4) 특징
✅ 장점
- 맵이 변경되어도 빠른 재탐색 가능
- SLAM 기반 로봇, 동적 환경에 적합
⚠️ 단점
- 구현 복잡도 높음
- 고속 주행 차량에는 다소 느릴 수 있음
5. 샘플링 기반 방법 (Sampling-based Planning)
(1) 개념
A*나 D*처럼 격자(Grid) 기반이 아니라,
연속 공간(Continuous Space) 에서 임의의 점을 “샘플링” 하여
탐색 그래프를 점진적으로 확장합니다.
즉,
“공간 전체를 탐색하지 않고, 유망한 영역만 부분적으로 탐색”
(2) 대표 알고리즘
| 알고리즘 | 특징 |
|---|---|
| RRT (Rapidly-exploring Random Tree) | 빠르게 트리 확장, 고차원 공간에 강함 |
| RRT* | RRT에 최적화 추가 (최단경로 보장) |
| PRM (Probabilistic Roadmap) | 랜덤 샘플 + 연결 그래프 구축 |
| BIT* | RRT + A* 혼합 (효율적) |
(3) RRT 기본 원리
1️⃣ 시작점에서 랜덤한 방향으로 샘플링
2️⃣ 가장 가까운 기존 노드로부터 새 노드를 연결
3️⃣ 장애물 충돌 검사 후 트리에 추가
4️⃣ 목표 근처 도달 시 탐색 종료
new_node = nearest(tree, random_point)
if collision_free(new_node):
tree.add(new_node)
✅ 장점
- 연속 공간/복잡한 장애물 환경에서도 가능
- 차량의 동역학 제약을 쉽게 반영 (e.g. Reeds-Shepp path)
⚠️ 단점
- 결과가 랜덤 (매 실행마다 다름)
- 생성된 경로가 부드럽지 않음 → 후처리 필요
6. 알고리즘 비교 요약
| 항목 | A* | D* | RRT / Sampling-based |
|---|---|---|---|
| 탐색 방식 | 격자 기반 (Grid) | 격자 기반 + 재활용 | 연속 공간 (Sampling) |
| 환경 변화 대응 | 불가능 | 가능 (부분 업데이트) | 가능 (재샘플링) |
| 최적성 보장 | 있음 (휴리스틱 조건) | 있음 | RRT*는 있음 |
| 계산 속도 | 느림 (대규모 맵) | 빠름 (부분 재탐색) | 빠름 (확률적) |
| 동역학 반영 | 어려움 | 일부 가능 | 용이 |
| 대표 사용처 | ROS Navigation | SLAM 로봇 | 자율주행 Local Planner |
7. ROS2 예시 (Global Planner Plugin 선택)
Autoware, Nav2 등에서는 전역 플래너를 선택적으로 설정할 수 있습니다:
nav2_planner:
planner_plugins:
- name: "GridBased"
type: "nav2_navfn_planner/NavfnPlanner" # A*
- name: "SmacPlanner"
type: "nav2_smac_planner/SmacPlannerHybrid" # Hybrid A*
또는 샘플링 기반 플래너 예시:
ros2 launch ompl_planner rrt_star.launch.py
8. 시각적 비교 요약
| 알고리즘 | 탐색 방식 | 경로 형태 |
|---|---|---|
| A* | 전체 격자 탐색 | 직선+코너 기반, 일정 |
| D* | 변화 감지 시 재탐색 | 경로 일부만 수정 |
| RRT* | 트리 확장 기반 | 자연스러운 곡선형, 후처리 필요 |
9. 정리
경로 계획 알고리즘은 환경 특성에 따라 선택이 달라집니다:
- 정적·단순 환경 → A*
- SLAM 기반 동적 환경 → D*
- 복잡한 도로 구조·자율주행 궤적 생성 → RRT*
즉,
A*는 “안정적”, D*는 “똑똑하게 재탐색”, RRT는 “자유로운 확장성”
이 세 접근의 조합이 실제 자율주행 시스템에서 널리 사용됩니다.