# 전역 경로 계획(Global Path Planning)

전역 경로 계획(Global Path Planning)은 로봇이 작업 공간에서 목표 위치로 이동하기 위해 최적의 경로를 결정하는 중요한 문제 중 하나이다. 이 과정은 로봇이 전체 환경을 고려하여 경로를 계획한다는 점에서 지역 경로 계획(Local Path Planning)과 구분된다. 전역 경로 계획은 다양한 복잡성을 포함하며, 이를 해결하기 위해 여러 가지 방법과 알고리즘이 개발되었다.

#### 경로 계획 문제의 정의

전역 경로 계획의 핵심 문제는 주어진 환경에서 출발점에서 목적지까지의 경로를 찾는 것이다. 환경은 일반적으로 2차원 또는 3차원 공간으로 표현되며, 이 공간에는 로봇이 이동할 수 없는 장애물이 존재할 수 있다. 이 문제를 해결하기 위해 로봇은 환경의 전체 지도를 기반으로 최적의 경로를 계산해야 한다.

경로 계획 문제는 일반적으로 다음과 같은 요소로 구성된다:

* **환경 모델링**: 로봇이 탐색해야 할 공간의 표현. 예를 들어, 그리드맵, 연속적인 공간 표현, 그래프 기반 표현 등이 사용된다.
* **비용 함수**: 경로의 품질을 평가하기 위한 기준으로, 경로의 길이, 이동 시간, 에너지 소비 등이 포함될 수 있다.
* **경로 탐색 알고리즘**: 최적의 경로를 찾기 위한 알고리즘으로, 전역 경로 계획에서는 A\*, Dijkstra, RRT\* 등이 많이 사용된다.

#### 환경 모델링

전역 경로 계획에서 환경 모델링은 매우 중요한 역할을 한다. 환경을 효과적으로 표현하고, 이 표현을 통해 경로를 탐색할 수 있어야 한다. 주요 환경 모델링 기법은 다음과 같다:

* **그리드 기반 표현**: 공간을 일정한 크기의 셀로 분할하여 각 셀이 이동 가능한지 여부를 표현한다. 간단하고 구현이 용이하지만, 해상도가 높아질수록 계산 비용이 증가하는 단점이 있다.
* **그래프 기반 표현**: 환경을 노드(장소)와 엣지(장소 간의 연결)로 표현하여 경로 탐색 문제를 그래프 탐색 문제로 변환한다. 이 접근법은 로드맵(Roadmap) 방법론, 예를 들어 PRM(Probabilistic Roadmap)에서 사용된다.
* **연속적 공간 표현**: 로봇의 위치를 연속적인 좌표로 나타내어 더 정밀한 경로 계획을 가능하게 한다. 그러나 연산 비용이 크게 증가할 수 있다.

#### 비용 함수 설계

비용 함수는 경로의 품질을 평가하는 데 사용된다. 경로의 최적화 목표에 따라 다양한 요소가 비용 함수에 포함될 수 있다. 대표적인 요소는 다음과 같다:

* **경로 길이**: 가장 기본적인 비용 요소로, 경로의 총 길이를 최소화하는 것을 목표로 한다.
* **이동 시간**: 로봇이 목적지까지 도달하는 데 소요되는 시간을 최소화하려는 경우 사용된다.
* **에너지 소비**: 로봇의 이동에 소모되는 에너지를 최소화하려는 경우 사용된다. 이는 로봇의 하드웨어적 특성과 밀접하게 연관된다.
* **안전성**: 로봇이 장애물로부터 안전한 거리를 유지하는 경로를 찾기 위해, 안전성에 대한 페널티를 포함할 수 있다.

#### 경로 탐색 알고리즘

경로 탐색 알고리즘은 주어진 환경과 비용 함수를 바탕으로 최적의 경로를 찾는 방법이다. 전역 경로 계획에서 자주 사용되는 알고리즘은 다음과 같다:

* *A 알고리즘*\*: 휴리스틱 함수(Heuristic Function)를 사용하여 최단 경로를 찾는 그래프 탐색 알고리즘이다. 효율적이고 널리 사용되지만, 복잡한 환경에서는 계산 비용이 클 수 있다.
* **Dijkstra 알고리즘**: 모든 노드 간의 최단 경로를 계산하는 알고리즘으로, A\*와 달리 휴리스틱을 사용하지 않는다. 모든 경로를 고려하므로 시간이 많이 걸릴 수 있지만, 항상 최적 해를 보장한다.
* *RRT (Rapidly-exploring Random Tree*)\*\*: 확률적 방법을 사용하여 고차원 공간에서의 경로를 탐색하는 알고리즘으로, 매우 복잡한 환경에서도 유용하다. RRT\*는 기존 RRT 알고리즘을 개선하여 최적의 경로를 보장한다.

이 외에도 전역 경로 계획에서는 다양한 최적화 기법과 머신러닝 기반 접근법이 사용될 수 있다. 이러한 방법들은 복잡한 환경에서 더 효율적이고 유연한 경로 계획을 가능하게 한다.

***

관련 자료:

* Latombe, J.-C. (1991). *Robot Motion Planning*. Kluwer Academic Publishers.
* LaValle, S. M. (2006). *Planning Algorithms*. Cambridge University Press.
* Thrun, S., Burgard, W., & Fox, D. (2005). *Probabilistic Robotics*. MIT Press.