자율 주행 알고리즘 적용

경로 계획 (Path Planning)

자율 주행에서 경로 계획은 로봇이 시작 지점에서 목표 지점까지 이동하는 최적의 경로를 계산하는 과정이다. 이를 위해 일반적으로 사용하는 알고리즘에는 A*, Dijkstra, RRT(Rapidly-exploring Random Tree) 등이 있다. 각 알고리즘의 특성과 적용 방법을 간단히 설명한다.

A* 알고리즘

A* 알고리즘은 탐색 알고리즘 중 하나로, 휴리스틱을 사용하여 최적의 경로를 찾는다. 경로의 비용을 계산할 때 다음의 비용 함수를 사용한다:

$f(\mathbf{n}) = g(\mathbf{n}) + h(\mathbf{n})$

여기서: - $f(\mathbf{n})$ : 현재 노드 $\mathbf{n}$ 까지의 총 비용 - $g(\mathbf{n})$ : 시작 지점에서 현재 노드까지의 실제 비용 - $h(\mathbf{n})$ : 현재 노드에서 목표 지점까지의 추정 비용 (휴리스틱 함수)

A* 알고리즘의 목표는 최종적으로 $f(\mathbf{n})$ 을 최소화하는 경로를 찾는 것이다.

Dijkstra 알고리즘

Dijkstra 알고리즘은 A* 알고리즘과 유사하지만, 휴리스틱 없이 모든 경로의 비용만을 고려한다. 즉, 다음 비용 함수는 다음과 같이 단순화된다:

$f(\mathbf{n}) = g(\mathbf{n})$

모든 경로의 비용을 고려한 뒤, 최종적으로 최소 비용 경로를 선택한다. 자율 주행에서는 로봇이 장애물이나 동적 환경에서도 안전하게 경로를 계획할 수 있도록 이 알고리즘을 사용할 수 있다.

RRT 알고리즘

RRT는 빠른 탐색을 위한 무작위 트리 알고리즘으로, 복잡한 공간에서 로봇의 경로를 계획할 때 사용된다. RRT 알고리즘은 다음과 같은 단계를 거친다:

무작위로 새로운 점 $\mathbf{q}_{rand}$ 를 선택한다.
트리에서 $\mathbf{q}_{rand}$ 와 가장 가까운 점 $\mathbf{q}_{near}$ 을 찾는다.
$\mathbf{q}_{near}$ 에서 $\mathbf{q}_{rand}$ 방향으로 새 노드 $\mathbf{q}_{new}$ 를 추가한다.
$\mathbf{q}_{new}$ 가 목표 지점에 도달하면 탐색을 종료한다.

이 방법은 특히 높은 자유도를 가진 로봇이나 복잡한 환경에서 효과적이다.

경로 추종 (Path Following)

경로 계획 후, 로봇이 계산된 경로를 따라 움직이는 과정이 경로 추종이다. 경로 추종을 위해 PID, MPC(Model Predictive Control)와 같은 제어 알고리즘을 사용할 수 있다.

PID 제어

PID 제어는 경로 추종에서 가장 기본적인 제어 방법 중 하나이다. 현재 위치와 목표 위치의 차이, 즉 오차 $e(t)$ 를 바탕으로 제어 입력을 생성한다. PID 제어의 수식은 다음과 같다:

$u(t) = K_p e(t) + K_i \int e(t) \, dt + K_d \frac{de(t)}{dt}$

여기서: - $u(t)$ : 제어 입력 - $e(t)$ : 오차 (목표 경로와의 차이) - $K_p, K_i, K_d$ : 비례, 적분, 미분 게인

PID 제어는 간단하지만, 환경이 복잡하거나 동적일 때 성능이 제한될 수 있다.

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

자율 주행 로봇은 이동 중에 동적 장애물을 피해야 하는 경우가 많다. 이를 위해 로봇은 실시간으로 장애물의 위치를 탐지하고 경로를 재계산한다. 동적 장애물 회피를 위한 알고리즘으로는 DWA(Dynamic Window Approach) 등이 있다.

DWA 알고리즘

DWA는 로봇의 속도 공간에서 가능한 속도들을 평가하여 장애물을 피하는 경로를 결정한다. 다음과 같은 비용 함수 $C(v, \omega)$ 를 최소화하는 속도 $v, \omega$ 를 선택한다:

$C(v, \omega) = \alpha \cdot C_{heading}(v, \omega) + \beta \cdot C_{clearance}(v, \omega) + \gamma \cdot C_{velocity}(v, \omega)$

여기서: - $C_{heading}(v, \omega)$ : 로봇이 목표 방향으로 가는 정도 - $C_{clearance}(v, \omega)$ : 로봇이 장애물과의 거리를 유지하는 정도 - $C_{velocity}(v, \omega)$ : 로봇의 속도 크기

DWA 알고리즘은 실시간으로 로봇의 움직임을 조절하여 장애물을 피하고 목표로 이동할 수 있도록 한다.

모델 예측 제어 (MPC, Model Predictive Control)

MPC는 경로 추종에서 자주 사용되는 고급 제어 알고리즘이다. MPC는 일정한 시간 구간에 걸쳐 로봇의 미래 상태를 예측하고, 최적의 제어 입력을 계산하여 목표 경로를 따른다. MPC의 수식은 다음과 같이 표현된다:

$\min_{\mathbf{u}} \sum_{k=0}^{N} \left( \mathbf{x}_k^T \mathbf{Q} \mathbf{x}_k + \mathbf{u}_k^T \mathbf{R} \mathbf{u}_k \right)$

여기서: - $\mathbf{x}_k$ : $k$ -번째 예측 시간 단계에서의 로봇 상태 - $\mathbf{u}_k$ : $k$ -번째 예측 시간 단계에서의 제어 입력 - $\mathbf{Q}$ : 상태 오차에 대한 가중치 행렬 - $\mathbf{R}$ : 제어 입력에 대한 가중치 행렬 - $N$ : 예측 구간의 길이

MPC는 각 시간 단계에서 최적화 문제를 해결하여 로봇이 경로를 따라갈 수 있도록 제어 입력을 생성한다. 로봇의 모델이 미리 주어졌다는 가정 하에 로봇의 동적 특성을 정확히 반영할 수 있어 복잡한 환경에서도 안정적으로 경로를 추종할 수 있다.

상태 공간 표현

MPC에서 로봇의 동적 모델은 상태 공간 모델로 표현된다. 상태 공간 모델은 다음과 같은 형태로 주어진다:

$\mathbf{x}_{k+1} = \mathbf{A} \mathbf{x}_k + \mathbf{B} \mathbf{u}_k$

여기서: - $\mathbf{A}$ : 상태 전이 행렬 - $\mathbf{B}$ : 제어 입력 행렬

로봇의 상태 $\mathbf{x}_k$ 는 위치, 속도, 각도 등의 정보를 포함하고, 제어 입력 $\mathbf{u}_k$ 는 로봇의 속도나 방향 제어 신호를 나타낸다.

로컬 경로 계획 (Local Path Planning)

자율 주행 로봇은 전체 경로 계획 외에도 실시간으로 로컬 경로를 계획해야 한다. 로컬 경로 계획은 로봇이 주변 환경에 맞게 즉각적으로 대응하는 경로를 계산하는 과정이다. 이를 위해 자주 사용하는 기법 중 하나는 벡터 장 제어(Vector Field Control)이다.

벡터 장 제어

벡터 장 제어는 로봇의 목표 지점까지 가기 위한 가상의 벡터 필드를 생성하여 로봇을 유도한다. 각 지점에서의 벡터는 로봇의 이동 방향과 속도를 나타내며, 목표 지점에 가까워질수록 벡터의 크기가 작아진다. 벡터 장의 일반적인 표현은 다음과 같다:

$\mathbf{V}(x, y) = -k \cdot \nabla \phi(x, y)$

여기서: - $\mathbf{V}(x, y)$ : 위치 $(x, y)$ 에서의 벡터 - $\nabla \phi(x, y)$ : 목표 함수 $\phi(x, y)$ 의 그래디언트 - $k$ : 제어 이득 (gain)

벡터 장 제어는 동적 장애물을 피하면서 목표 지점으로 이동하는 데 유용한 방법이다.

경로 재계획 (Replanning)

로봇이 이동 중 예상치 못한 장애물을 만나거나 경로가 변경될 때, 즉시 새로운 경로를 계산해야 한다. 이를 경로 재계획이라고 하며, 주로 실시간으로 수행된다. 경로 재계획에서 고려해야 할 주요 요소는 다음과 같다.

경로 재계획의 기준

현재 위치에서 목표 지점까지의 새로운 최적 경로
장애물의 위치 변화에 따른 경로 수정
주변 환경의 동적 변화에 대한 실시간 반영

경로 재계획을 위한 알고리즘은 경로 계획 시 사용된 알고리즘(A*, Dijkstra, RRT 등)을 다시 사용하거나, 단순한 근거리 회피 전략을 적용할 수 있다.