# 동적 장애물 회피 (Dynamic Obstacle Avoidance)

#### 경로 계획의 기초

경로 계획은 로봇이 주어진 시작점에서 목표 지점까지 안전하고 효율적인 경로를 생성하는 과정이다. 이 과정에서 로봇은 주변 환경을 인지하고, 장애물을 회피하며, 주어진 시간 내에 목적지에 도달해야 한다. 경로 계획은 정적 환경에서의 경로 계획과 동적 환경에서의 경로 계획으로 나눌 수 있는데, 후자는 움직이는 장애물이 있는 환경에서 로봇이 실시간으로 경로를 수정하며 목표를 달성하는 것을 의미한다.

동적 장애물 회피를 고려한 경로 계획은 로봇이 정적 장애물뿐만 아니라, 움직이는 객체나 변화하는 환경 조건을 실시간으로 인지하고 대응해야 하므로, 훨씬 더 복잡하고 고도화된 알고리즘이 요구된다.

#### 동적 장애물 회피의 필요성

동적 장애물 회피는 로봇이 실시간으로 변화하는 환경에서 안전하게 작업을 수행하기 위해 필수적이다. 예를 들어, 자율 주행 차량은 도로 위에서 다른 차량, 보행자, 자전거 등을 피하면서 목표 지점으로 이동해야 한다. 로봇이 이러한 환경에서 효율적으로 작동하기 위해서는 움직이는 장애물을 인식하고, 그들의 움직임을 예측하며, 그에 따라 경로를 수정해야 한다.

동적 장애물 회피의 주요 목표는 다음과 같다:

* **안전성**: 로봇이 다른 객체와 충돌하지 않도록 보장
* **효율성**: 최소한의 경로 변경과 연산 자원 사용으로 목표를 달성
* **실시간성**: 환경 변화에 빠르게 대응하여 경로를 조정

#### 동적 장애물 회피 알고리즘

동적 장애물 회피를 위한 다양한 알고리즘이 제안되어 왔으며, 이들 알고리즘은 주로 세 가지 범주로 나눌 수 있다: 경로 기반 알고리즘, 샘플링 기반 알고리즘, 최적화 기반 알고리즘.

**경로 기반 알고리즘**

경로 기반 알고리즘은 사전에 정의된 경로를 따르면서, 실시간으로 장애물을 감지하고 회피하는 방식이다. 대표적인 알고리즘으로는 다음과 같은 것들이 있다:

* *D 알고리즘 (Dynamic A*)\*\*: A\* 알고리즘의 확장판으로, 환경 변화에 따라 경로를 재계산한다. D\*는 로봇이 새로운 장애물을 감지하면 기존 경로를 재계산하여, 로봇이 실시간으로 경로를 수정할 수 있게 한다.
* **Potential Field Method (전위장 방법)**: 이 방법은 로봇이 목표 지점으로 끌려가고 장애물로부터 밀려나는 힘을 받는 것으로 간주한다. 이 방식은 실시간으로 환경 변화를 반영할 수 있으나, 지역 최소점(local minima) 문제로 인해 효율적이지 않을 수 있다.

**샘플링 기반 알고리즘**

샘플링 기반 알고리즘은 경로 계획에서 로봇의 가능한 경로를 샘플링하여 가장 적합한 경로를 선택하는 방식이다. 동적 장애물 회피에 사용되는 대표적인 샘플링 기반 알고리즘으로는 다음이 있다:

* **RRT (Rapidly-exploring Random Tree)**: 이 알고리즘은 로봇의 작업 공간에서 무작위로 점을 샘플링하고, 그 점들을 연결하여 경로를 찾는다. RRT는 복잡한 환경에서도 효율적으로 작동하지만, 실시간 성능을 보장하기 위해 RRT\*와 같은 개선된 버전이 사용된다.
* **PRM (Probabilistic Roadmap)**: PRM은 로봇이 이동할 수 있는 공간을 그래프로 모델링하여, 무작위로 생성된 노드를 연결하여 경로를 계획한다. PRM은 사전 계산이 가능하다는 장점이 있으나, 동적 환경에서는 새로운 장애물이 발생할 때마다 경로를 다시 계산해야 한다.

**최적화 기반 알고리즘**

최적화 기반 알고리즘은 로봇의 경로를 최적화 문제로 설정하고, 이를 해결하는 방식이다. 이러한 방법들은 주로 로봇의 경로를 가능한 최단 경로나 에너지 효율이 높은 경로로 최적화하려고 시도한다.

* **Mixed-Integer Linear Programming (MILP)**: MILP는 로봇의 경로 계획 문제를 선형 프로그래밍 문제로 변환하여 해결한다. MILP는 정밀한 경로 계획이 가능하지만, 계산 복잡도가 높아 실시간 응용에는 적합하지 않을 수 있다.
* **Sequential Convex Programming (SCP)**: SCP는 비선형 경로 계획 문제를 다수의 선형 문제로 분할하여 해결한다. SCP는 실시간 장애물 회피에 유리하며, 연속적인 최적화 과정을 통해 로봇이 효율적인 경로를 찾도록 돕는다.

#### 동적 장애물 예측 및 회피

동적 장애물 회피에서 중요한 요소는 장애물의 움직임을 예측하고, 이를 기반으로 경로를 조정하는 것이다. 장애물의 예측은 주로 칼만 필터(Kalman Filter)나 확장 칼만 필터(Extended Kalman Filter)를 통해 수행된다. 이를 통해 로봇은 장애물의 속도와 가속도를 추정하고, 향후 위치를 예측할 수 있다.

* **칼만 필터**: 선형 시스템에서의 상태 추정을 위한 방법으로, 동적 장애물의 위치를 실시간으로 예측하는 데 자주 사용된다.
* **확장 칼만 필터**: 비선형 시스템에서의 상태 추정을 가능하게 하며, 복잡한 동적 환경에서의 장애물 회피에 적합한다.

동적 장애물 회피에서 중요한 또 다른 방법은 예측된 장애물 경로와 로봇 경로의 교차 가능성을 분석하는 것이다. 이를 통해 로봇은 충돌 가능성이 높은 경로를 피하고, 안전한 경로를 선택하게 된다.

***

관련 자료:

* LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
* Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.
* Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5(1), 90-98.