# 정적 장애물 회피

#### 경로 계획의 개요

경로 계획(Path Planning)은 로봇이 시작 지점에서 목표 지점으로 이동할 때 최적의 경로를 계산하는 과정이다. 이 과정은 로봇의 작업 환경에 존재하는 장애물, 이동 가능한 경로, 로봇의 동역학적 특성 등을 고려하여 수행된다. 경로 계획은 크게 정적 장애물 회피와 동적 장애물 회피로 나뉘며, 이 중 정적 장애물 회피는 로봇의 환경이 시간이 지남에 따라 변화하지 않는 경우를 다룬다. 정적 장애물 회피는 로봇의 자율성을 확보하는 데 있어 핵심적인 역할을 한다.

#### 정적 장애물 회피의 정의

정적 장애물 회피(Static Obstacle Avoidance)는 로봇이 주어진 환경에서 고정된 장애물들을 피하면서 목적지까지 안전하게 도달할 수 있는 경로를 찾는 것을 의미한다. 이는 로봇이 환경에 대한 완전한 정보(장애물의 위치와 크기 등)를 알고 있으며, 시간이 지남에 따라 장애물의 위치가 변하지 않는다는 가정하에 이루어진다. 이 문제를 해결하기 위해 다양한 알고리즘들이 개발되어 왔으며, 그 중 대표적인 방법으로는 공간 분할 방식, 샘플링 기반 방식, 최적화 방식이 있다.

#### 공간 분할 방식

공간 분할 방식은 로봇이 이동할 수 있는 공간을 여러 개의 작은 구역으로 나누고, 각각의 구역을 탐색하면서 경로를 찾아가는 방법이다. 대표적인 예로는 사각형 그리드(Grid) 방식과 사각형 분할(Quadtree) 방식이 있다.

* **사각형 그리드(Grid) 방식:** 공간을 일정한 크기의 격자로 나누고, 각 격자가 장애물인지 아닌지를 판단한다. 로봇은 출발지에서 목적지까지 갈 수 있는 경로를 찾기 위해 인접한 격자로 이동한다. 이 방식은 구현이 간단하고 직관적이지만, 격자의 크기에 따라 경로의 정밀도가 달라진다는 단점이 있다.
* **사각형 분할(Quadtree) 방식:** 공간을 재귀적으로 사분할하여 장애물이 존재하는 영역을 효율적으로 표현하는 방법이다. 이 방식은 공간을 효율적으로 표현할 수 있지만, 장애물이 복잡한 형태일 경우 분할 과정이 복잡해질 수 있다.

#### 샘플링 기반 방식

샘플링 기반 방식은 주어진 공간에서 무작위로 샘플을 생성하고, 이 샘플들 사이를 연결하여 경로를 찾는 방법이다. 이 방식은 복잡한 환경에서도 효율적으로 경로를 찾을 수 있어 최근 많이 사용된다. 대표적인 알고리즘으로는 PRM(Probabilistic Roadmap)과 RRT(Rapidly-exploring Random Tree)가 있다.

* **PRM(Probabilistic Roadmap):** 로봇의 작업 공간에서 무작위로 여러 샘플을 생성하고, 이 샘플들을 연결하여 로드맵을 만든다. 그 후, 출발지와 목적지를 로드맵 상의 노드로 연결하여 경로를 찾는다. PRM은 오프라인에서 로드맵을 구축한 후 이를 활용하기 때문에, 경로 탐색 속도가 빠르다는 장점이 있다.
* **RRT(Rapidly-exploring Random Tree):** 무작위로 샘플을 생성하면서 트리를 확장해가는 방식으로 경로를 찾는다. 이 과정에서 장애물에 닿지 않도록 경로를 만들어 나가며, 트리가 목표 지점에 도달하면 경로 탐색을 종료한다. RRT는 실시간 경로 탐색에 적합하며, 특히 고차원의 공간에서 효과적이다.

#### 최적화 기반 방식

최적화 기반 방식은 경로를 수학적으로 최적화하여 장애물을 회피하는 방법이다. 이 방식은 로봇의 운동학적 제약 조건과 목표 함수를 고려하여 최적의 경로를 계산한다. 대표적인 방법으로는 잠재장(Potential Field) 방식과 최적 제어(Optimal Control) 방식이 있다.

* **잠재장(Potential Field) 방식:** 장애물을 회피하는 문제를 물리적인 힘으로 모델링한다. 장애물은 로봇을 밀어내는(repulsive) 힘을 생성하고, 목표 지점은 로봇을 끌어당기는(attractive) 힘을 생성하여, 로봇은 이 두 힘의 합력에 의해 경로를 결정하게 된다. 이 방식은 계산이 간단하고 실시간 적용이 가능하지만, 지역 최소값(local minima)에 빠질 수 있는 단점이 있다.
* **최적 제어(Optimal Control) 방식:** 로봇의 운동 방정식을 만족하면서 장애물을 피하고 목표 지점에 도달하는 경로를 수학적으로 최적화하는 방식이다. 이 방법은 경로의 매끄러움(smoothness)과 최적성을 동시에 달성할 수 있지만, 계산 복잡도가 높아 실시간 적용에는 어려움이 있다.

#### 정적 장애물 회피의 한계와 해결 방안

정적 장애물 회피는 장애물이 고정되어 있는 환경에서 효과적이지만, 실제 환경에서는 이 접근 방식에 한계가 존재한다. 특히, 로봇이 복잡한 환경에서 움직일 때 발생할 수 있는 계산 복잡도와 예기치 않은 환경 변화에 대한 대응이 어려운 문제점이 있다. 이러한 문제를 해결하기 위해 경로 재계획(replanning)이나 하이브리드 접근법이 연구되고 있다. 경로 재계획은 로봇이 이동 중에 환경 정보를 업데이트하면서 실시간으로 경로를 수정하는 방법이다. 하이브리드 접근법은 정적 장애물 회피와 동적 장애물 회피 기법을 결합하여 보다 유연한 경로 계획을 가능하게 한다.

***

관련 자료:

* Latombe, J.-C. (1991). Robot Motion Planning. Springer.
* LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
* Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., & Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press.