전역경로계획 (Global Path Planning)
쉽게 풀면
지도를 다 알고 있을 때, 출발지에서 목적지까지 전체적으로 어떤 길로 갈지 큰 그림을 먼저 짜는 것입니다.
왜 중요한가
출발점에서 목표까지 지도 전체를 고려해 경로를 구하는 단계로, 이동로봇 내비게이션의 상위 계층을 이룹니다. A*와 그 변형이 격자 지도에서, 샘플링 기반 계획기가 고차원 공간에서 표준이며 경로 길이와 계산 시간이 평가 지표입니다. 건물 전체 도면이 미리 주어지는 배송로봇처럼 환경을 사전에 완전히 알 수 있는 경우, 전역경로계획만으로도 충분히 효율적인 이동이 가능해 계산 자원을 아낄 수 있다.
어떤 절차인가
- 지도 표현: 점유격자지도, 로드맵(그래프), 형상공간 중 하나로 환경을 나타내고, 로봇의 크기만큼 장애물을 부풀립니다.
- 비용 정의: 경로 길이, 이동 시간, 위험도 등을 비용으로 정합니다.
- 탐색: 격자·그래프에서는 Dijkstra, A*처럼 비용이 작은 경로를 찾는 탐색을, 고차원이나 연속 공간에서는 RRT, PRM 같은 표본추출 기반 방법을 씁니다.
- 후처리: 기하학적 경로를 부드럽게 다듬고, 차량형 로봇의 회전 반경·가속 한계 같은 동역학 제약을 반영합니다.
- 인계: 전역 경로를 따라가며 실시간으로 장애물을 피하는 지역경로계획에 넘깁니다.
언제 쓰고 무엇을 얻나
- 알고리즘 성질: Dijkstra는 간선 비용이 음수가 아니면, A*는 휴리스틱이 허용적(실제 비용을 과대평가하지 않음)이면 최적 경로를 보장합니다(A* 알고리즘). RRT는 확률적 완전성을 갖지만 일반적으로 최적은 아니고, 표본이 늘면 최적에 수렴하도록 개선한 RRT*가 있습니다(Karaman & Frazzoli, 2011).
- 언제: 지도가 미리 주어지고 환경이 크게 변하지 않을 때(건물 도면이 있는 실내 배송 로봇 등) 전역 계획만으로도 효율적인 이동이 가능합니다.
- 한계: 지도에 없는 장애물에는 대응할 수 없고, 지도가 바뀌면 경로를 다시 계산해야 합니다. 샘플링 기반 방법은 실행마다 다른 경로가 나올 수 있습니다.
가상의 예(계산 결과). 아래 10×10 격자에서 4방향 이동, 칸당 비용 1, 맨해튼 거리 휴리스틱으로 S에서 G까지 찾았습니다(#은 장애물, 빈 칸은 60개).
S..........####.###..#......#..#.####.#..#.#..#.#..#.#.##.#..#.#....#..#.######..#...........#####.G
Dijkstra와 A*는 모두 비용 18의 같은 최적 경로를 찾았고, 확장한 노드 수는 Dijkstra가 58개, A*가 38개였습니다. 휴리스틱이 목표 쪽으로 탐색을 유도해 계산량을 줄인 것입니다(동점 처리 순서에 따라 확장 수는 조금 달라질 수 있습니다).
논문에는 이렇게 적는다
- 지도 표현과 해상도(격자 크기), 이웃 연결(4방향 또는 8방향), 장애물 팽창 반경.
- 비용 함수와 사용한 알고리즘·휴리스틱, 후처리(평활화) 방법.
- 평가 지표: 경로 길이, 계산 시간, 확장 노드 수, 성공률. 표본추출 방법은 여러 번 실행한 평균과 표준편차, 난수 시드.
- 실험 환경(지도 규모, 장애물 밀도, 하드웨어).
- 지도가 바뀌는 경우 재계획 방식과 그 비용.
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
환경 전체 정보를 미리 알고 있다는 전제 하에, 계산 시간을 들여 처음부터 끝까지의 최선의 경로를 한 번에 산출한다는 뜻입니다.
이 문장은 전역경로계획이 환경 변화에 취약해 지역경로계획과 함께 쓰이는 이유를 보여줍니다.
조금 더 깊게 보면
전역 계획은 지도가 정확하다는 전제에서 만들어지므로 실제 주행 중 만나는 동적 장애물은 지역 경로계획이 따로 처리하며, 두 계층의 역할 분담이 내비게이션 구조의 핵심입니다.
로봇의 동역학 제약을 무시한 기하 경로만 내는 경우가 많아, 차량형 로봇이 따라갈 수 없는 급회전 경로가 나오면 후처리로 평활화하거나 제약을 계획에 포함해야 합니다.
격자 기반 방법(A* 등)은 지도를 일정 크기 셀로 나누어 탐색하므로 구현이 단순하지만 해상도가 낮으면 실제로 지나갈 수 있는 좁은 통로를 놓칠 수 있고, 샘플링 기반 방법(RRT , PRM )은 연속 공간을 직접 다뤄 고차원 로봇팔 형상공간에도 적용할 수 있지만 매번 다른 무작위 경로가 나올 수 있다는 비결정성을 갖는다.
전역경로계획 결과는 대개 로봇의 실제 회전 반경이나 가속 한계를 고려하지 않은 기하학적 경로이므로, 차량형 로봇에는 이를 매끄럽게 다듬는 후처리 평활화 단계가 뒤따른다.
주의할 점
지도에 없는 새로운 장애물이 나타나면 전역 경로만으로는 대응할 수 없어 지역 경로 계획이 반드시 함께 필요합니다.
전역경로계획은 계획 시점의 지도를 그대로 신뢰하므로, 계획 이후 지도와 실제 환경 사이에 괴리가 생기면 계획된 경로가 통과할 수 없는 구간을 포함하게 될 수 있다.
헷갈리기 쉬운 용어
경로·동작 계획 용어는 층위가 다릅니다.
| 용어 | 무엇인가 | 특징 |
|---|---|---|
| 전역경로계획 | 지도 전체를 알고 있다고 보고 출발점에서 목표까지 경로를 미리 계산 | 상위 수준, 정적 지도 가정 |
| 지역경로계획 | 센서 정보로 전역 경로를 따라가며 실시간 장애물 회피 | 하위 수준, 동적 환경 대응 |
| 모션계획 | 충돌을 피하고 제약을 만족하는 동작(경로·궤적)을 계산하는 문제 전반 | 상위 범주 |
| 영역완전탐사경로계획 | 작업 영역 전체를 빠짐없이 지나가는 경로 | 목표가 한 점이 아닌 면적 전체 |
| A* 알고리즘 | 비용과 휴리스틱으로 최단 경로를 찾는 탐색 | 전역 계획에서 쓰는 대표 방법 |
참고 문헌
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
- LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
- Kavraki, L. E., Švestka, P., Latombe, J.-C., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4), 566–580.
- Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 30(7), 846–894.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.