이동로봇 전역 경로계획

• 배달 로봇에 "3층 회의실로 가라" → 먼저 지도 전체를 보고 출발지에서 목적지까지의 길을 찾아야 함
• 이것이 전역 경로계획(Global Path Planning) — 내비게이션 앱의 길찾기와 같은 역할
• 시험 반복 출제: 전역/지역 계획의 구분 / 구성공간과 장애물 팽창 / Dijkstra와 A*의 비교(휴리스틱의 조건) / 샘플링 기반 기법(PRM·RRT)의 특징

전역 경로계획 vs 지역 경로계획

이동로봇의 경로계획은 두 층으로 나뉘어 협력한다.

이 노트는 전역 계획을, 이동로봇 지역 경로계획은 지역 계획을 다룬다.

구성공간과 장애물 팽창

• 로봇은 크기가 있는 물체 → "로봇의 중심이 이 점을 지나도 되는가"를 따지려면 몸집 고려 필요

• 계산을 단순하게 만드는 표준 기법 = 구성공간(Configuration Space, C-space) 변환

• 장애물을 로봇의 반경만큼 부풀리고(팽창, Inflation)

• 로봇은 크기 없는 점으로 취급한다

• 효과: "점이 팽창된 장애물 밖에 있는가"만 검사하면 되므로 경로계획이 훨씬 간단

• 구현 예: 격자지도(Occupancy Grid Map, → 이동로봇 지도 작성) 위에서 장애물 주변 셀에 비용을 더해 주는 코스트맵(Costmap)의 팽창 영역

그래프 탐색 기반 계획 ① — Dijkstra 알고리즘

격자지도의 셀(또는 노드)을 그래프로 보고 최단 경로를 찾는 고전적 방법이다.

• 시작 노드에서부터 누적 비용이 작은 순서로 노드를 확장해 나간다
• 목표에 도달하면 그 경로가 최단 경로임이 보장된다
• 단점: 목표 방향과 무관하게 모든 방향으로 균일하게 탐색하므로 탐색량이 많다 (물결이 퍼지듯 확장)

그래프 탐색 기반 계획 ② — A* 알고리즘

• Dijkstra에 "목표가 어느 쪽에 있는지" 힌트를 더해 탐색을 목표 쪽으로 집중시킨 알고리즘 → 격자지도 전역 계획의 사실상 표준
• 각 노드 n을 평가함수로 점수화:

• g(n): 시작점 → n까지 실제로 든 비용
• h(n): n → 목표까지의 추정 비용(휴리스틱, Heuristic) — 보통 유클리드 거리나 맨해튼 거리
• f(n)이 가장 작은 노드부터 확장

샘플링 기반 계획 — PRM과 RRT

• 격자 탐색은 공간을 빠짐없이 격자로 나누므로, 차원이 높아지면(예: 6~7자유도 머니퓰레이터의 구성공간) 격자 수가 폭발

• 이때는 공간을 무작위 샘플링으로 듬성듬성 탐사하는 기법을 사용

• PRM(Probabilistic Roadmap, 확률적 로드맵): 자유공간에 무작위 점들을 뿌리고 서로 연결해 도로망(roadmap)을 미리 구축한 뒤, 질의가 올 때마다 그 위에서 그래프 탐색. 같은 환경에서 여러 번 질의(multi-query) 할 때 유리

• RRT(Rapidly-exploring Random Tree, 급속 탐사 랜덤 트리): 시작점에서 트리를 무작위로 뻗어 나가며 목표에 닿으면 종료. 한 번의 질의(single-query) 에 적합하고, 고차원·복잡한 제약(비홀로노믹 등)에도 잘 동작

• 두 방법 모두 확률적 완전성(probabilistically complete) — 해가 존재하면 샘플을 무한히 늘릴 때 찾을 확률이 1에 수렴 — 을 갖지만, 찾은 경로가 최적이라는 보장은 없다 (들쭉날쭉한 경로가 나와 후처리로 다듬는 경우가 많다)

• RRT*: 트리를 뻗으면서 주변 연결을 계속 개선해, 샘플이 늘수록 최적 경로에 수렴(점근적 최적성)하도록 개량한 버전

알고리즘 선택 기준

• 2차원 격자지도 + 최단 경로 보장 필요 → A* (또는 Dijkstra)
• 고차원 구성공간(머니퓰레이터), 복잡한 장애물 → RRT / PRM
• 경로 품질까지 필요 → RRT* 또는 경로 후처리(smoothing)

전역 경로계획 알고리즘 분류

graph TD
    A["전역 경로계획"] --> B["그래프 탐색 기반
(격자지도)"]
    A --> C["샘플링 기반
(고차원 구성공간)"]
    B --> B1["Dijkstra
균일 확장·최적 보장"]
    B --> B2["A*
f = g + h, 휴리스틱으로 가속"]
    C --> C1["PRM
로드맵 사전 구축 (multi-query)"]
    C --> C2["RRT
랜덤 트리 확장 (single-query)"]
    C2 --> C3["RRT*
점근적 최적성 추가"]

A* 평가함수

최적성 보장 조건 (허용 가능성):

격자에서 자주 쓰는 휴리스틱 — 4방향 이동이면 맨해튼 거리 |x_1-x_2| + |y_1-y_2|, 임의 방향이면 유클리드 거리 \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}.

1. A* 알고리즘의 평가함수 f(n) = g(n) + h(n)에서 g(n)과 h(n)의 의미로 옳은 것은?

① g: 목표까지의 추정 비용, h: 시작점부터의 실제 비용 ② g: 시작점부터 n까지의 실제 비용, h: n부터 목표까지의 추정 비용 ③ g: 노드의 높이, h: 노드의 깊이 ④ g: 휴리스틱 비용, h: 이동 비용

2. A* 알고리즘이 최적 경로를 보장하기 위한 휴리스틱 h(n)의 조건은?

① 실제 잔여 비용보다 항상 커야 한다 ② 실제 잔여 비용을 과대평가하지 않아야 한다 ③ 항상 음수여야 한다 ④ 목표에서 멀수록 작아져야 한다

3. A* 알고리즘에서 휴리스틱을 h(n) = 0으로 설정하면 어떤 알고리즘과 동일하게 동작하는가?

① Dijkstra ② RRT ③ PRM ④ 포텐셜 필드

4. RRT(Rapidly-exploring Random Tree)에 대한 설명으로 옳지 않은 것은?

① 무작위 샘플링으로 트리를 확장해 나간다 ② 고차원 구성공간의 경로계획에 적합하다 ③ 찾아낸 경로는 항상 최단 경로다 ④ 머니퓰레이터의 충돌 없는 경로 탐색에 활용된다

5. 격자지도 기반 경로계획에서 장애물 주변을 로봇 반경만큼 팽창(inflation)시키는 이유로 옳은 것은?

① 지도 저장 용량을 줄이기 위해 ② 로봇을 크기 없는 점으로 취급하여 계획을 단순화하기 위해 ③ 센서 잡음을 제거하기 위해 ④ 경로를 최대한 길게 만들기 위해

• 이동로봇 지역 경로계획 — 전역 경로를 따라가며 실시간 회피
• 이동로봇 지도 작성 — 전역 계획의 입력이 되는 격자지도
• 이동로봇 충돌회피 — 코스트맵 팽창·동적 장애물 대응
• 머니퓰레이터 경로계획 — 머니퓰레이터 쪽의 경로계획
• _MOC 모션소프트웨어