운동 경로 계획 - 실험 도서관

운동 경로 계획(Motion Path Planning)은 물체가 시작점에서 목표점까지 이동하는 동안의 경로를 설정하는 과정이다. 이 과정에서는 물리적인 충돌을 방지하고, 원하는 동작을 수행할 수 있도록 최적화된 경로를 계산하는 것이 중요하다. 운동 경로 계획은 로봇공학, 자율주행 차량, 컴퓨터 그래픽스, 그리고 생체역학 등 다양한 분야에서 사용된다.

기본 개념

운동 경로 계획의 기본 개념은 시작점과 목표점을 설정한 후, 그 사이의 충돌 없는 경로를 찾는 것이다. 이는 주로 2D 혹은 3D 공간에서의 경로를 의미하며, 경로는 직선, 곡선, 또는 복합적인 형태로 나타날 수 있다.

경로 계획을 수학적으로 표현하기 위해, 일반적으로 다음과 같은 요소들을 정의한다:

상태 공간 (State Space): 로봇 또는 물체의 가능한 모든 위치와 자세를 나타내는 공간이다.
예를 들어, 이차원 평면에서의 로봇의 상태는 $\mathbf{x} = [x, y]^{\top}$ 로 나타낼 수 있다.
3D 공간에서의 로봇 상태는 $\mathbf{x} = [x, y, z]^{\top}$ 로 확장될 수 있다.
장애물 (Obstacles): 물체가 충돌하지 말아야 할 물리적 제약이다. 경로 계획에서 장애물을 고려하는 것이 필수적이다.
장애물은 상태 공간에서 특정한 영역을 차지하며, 이를 $\mathcal{O}$ 로 정의할 수 있다.
자유 공간 (Free Space): 물체가 자유롭게 이동할 수 있는 공간으로, 장애물을 제외한 상태 공간이다. 이는 $\mathcal{F} = \mathcal{X} \setminus \mathcal{O}$ 로 정의된다.

경로 계획의 수학적 정의

경로 계획 문제는 주어진 시작 상태 $\mathbf{x}_\text{start}$ 와 목표 상태 $\mathbf{x}_\text{goal}$ 사이의 경로 $\mathbf{p}(t)$ 를 찾는 것으로 정의된다. 여기서 $\mathbf{p}(t)$ 는 시간 $t$ 에 따른 경로를 나타내는 함수이다.

목표는 다음 조건을 만족하는 경로를 찾는 것이다:

경로는 시작 상태에서 출발하여 목표 상태에 도달한다.

$\mathbf{p}(0) = \mathbf{x}_\text{start}, \quad \mathbf{p}(T) = \mathbf{x}_\text{goal}$

여기서 $T$ 는 경로를 완료하는 시간이다.

경로는 자유 공간 내에 존재한다.

$\mathbf{p}(t) \in \mathcal{F}, \quad \forall t \in [0, T]$

경로 표현 방식

경로를 표현하는 방식에는 여러 가지가 있으며, 상황에 따라 적절한 방식을 선택해야 한다.

다각형 경로 (Piecewise Linear Path): 경로가 여러 직선 구간으로 이루어지는 경우로, 각 구간은 선형 방정식으로 나타낼 수 있다.

$\mathbf{p}(t) = \mathbf{x}_i + t (\mathbf{x}_{i+1} - \mathbf{x}_i), \quad t \in [0, 1]$

이 때, $\mathbf{x}_i$ 는 경로의 분할점이다.

곡선 경로 (Curved Path): 경로가 곡선으로 나타나는 경우, 곡선은 주로 이차 또는 삼차 다항식으로 표현된다.

$\mathbf{p}(t) = a_0 + a_1 t + a_2 t^2 + a_3 t^3$

여기서 $a_0, a_1, a_2, a_3$ 는 곡선의 계수를 나타낸다.

파라메트릭 경로 (Parametric Path): 경로를 시간이나 다른 파라미터에 대한 함수로 나타내는 방식이다.

$\mathbf{p}(t) = [x(t), y(t), z(t)]^{\top}$

이 경우, 각 좌표 축의 변화가 시간 함수로 정의된다.

경로 계획 알고리즘

경로 계획 문제를 해결하기 위해 다양한 알고리즘이 사용된다. 대표적인 경로 계획 알고리즘으로는 다음과 같은 것들이 있다.

1. 탐색 기반 알고리즘 (Search-Based Algorithms)

탐색 기반 알고리즘은 상태 공간을 탐색하여 시작점에서 목표점까지의 경로를 찾는 방법이다. 대표적인 알고리즘으로는 A* 알고리즘과 Dijkstra 알고리즘이 있다.

A* 알고리즘: 이 알고리즘은 휴리스틱 함수 $h(\mathbf{x})$ 를 사용하여 경로의 최적화를 시도한다. 시작점에서 특정 지점까지의 실제 비용 $g(\mathbf{x})$ 와 휴리스틱 비용을 합산하여 평가한다.

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

여기서, $g(\mathbf{x})$ 는 시작점에서 해당 지점까지의 경로 비용이고, $h(\mathbf{x})$ 는 해당 지점에서 목표점까지의 예상 비용이다. A* 알고리즘은 $f(\mathbf{x})$ 값을 최소화하는 경로를 탐색한다.

Dijkstra 알고리즘: Dijkstra 알고리즘은 시작점에서 목표점까지의 최단 경로를 찾는 데 주로 사용된다. 이는 경로 비용을 최소화하면서 장애물을 피해가는 경로를 계산하는 방식으로 작동한다. 이 알고리즘은 $g(\mathbf{x})$ 만을 고려하며, 휴리스틱 함수가 없다.

2. 샘플링 기반 알고리즘 (Sampling-Based Algorithms)

샘플링 기반 알고리즘은 상태 공간 내에서 무작위로 샘플을 생성하여 경로를 계획하는 방식이다. 이 방법은 특히 고차원 공간에서 효과적이다.

PRM (Probabilistic Roadmap): 이 알고리즘은 상태 공간에서 무작위로 샘플을 생성하고, 이 샘플을 그래프로 연결하여 경로를 찾는다. 이때, 장애물과의 충돌을 피하면서 시작점에서 목표점까지의 경로를 찾는 것이다.
PRM은 크게 두 가지 단계로 이루어진다:
1. 구성 단계 (Construction Phase): 상태 공간에서 무작위로 샘플을 생성하고, 샘플들 간의 충돌이 없는 연결을 생성하여 로드맵을 만든다.
2. 질의 단계 (Query Phase): 시작점과 목표점이 주어졌을 때, 로드맵 상에서 경로를 찾는다.
RRT (Rapidly-exploring Random Tree): RRT 알고리즘은 시작점에서부터 무작위로 샘플을 탐색하며 트리를 확장해 나가는 방식이다. 이 알고리즘은 특히 복잡한 환경에서 경로를 빠르게 탐색할 수 있다.
RRT 알고리즘의 핵심은 트리를 확장하면서 목표점에 가까워지는 방향으로 경로를 생성하는 것이다. 이는 상태 공간 내에서 무작위로 샘플을 선택하고, 해당 샘플에 가장 가까운 트리의 노드에서 새 노드를 생성하여 트리를 확장하는 방식으로 작동한다.

3. 최적화 기반 알고리즘 (Optimization-Based Algorithms)

최적화 기반 알고리즘은 경로의 비용을 최소화하거나 특정한 목적을 달성하기 위해 최적화 문제를 푸는 방식이다.

QP (Quadratic Programming): 이 방식은 이차 방정식을 이용하여 경로를 최적화한다. $\mathbf{p}(t)$ 가 최소 비용을 갖도록 목적 함수를 설정한 후, 경로 계획 문제를 최적화 문제로 변환하여 해결한다.

$\min_{\mathbf{p}(t)} \quad \mathbf{p}(t)^{\top} Q \mathbf{p}(t)$

여기서 $Q$ 는 경로의 비용을 결정하는 행렬이다.

Constrained Optimization: 경로 계획 문제에서 장애물 회피와 같은 제약 조건을 포함하여 최적화 문제를 해결할 수 있다. 이 경우 목적 함수는 경로의 비용을 최소화하면서 제약 조건을 만족하는 방식으로 설정된다.

$\min_{\mathbf{p}(t)} \quad f(\mathbf{p}(t)), \quad \text{subject to} \quad \mathbf{p}(t) \in \mathcal{F}$

4. 혼합 기반 알고리즘 (Hybrid Algorithms)

혼합 기반 알고리즘은 탐색 기반과 최적화 기반 방법을 결합하여 더 나은 경로 계획 성능을 제공하는 방식이다. 탐색과 최적화를 결합하면, 경로 탐색의 초기 단계에서는 탐색 알고리즘을 사용하고, 이후 최적화 알고리즘으로 경로를 미세 조정하는 방식이다.

RRT* (RRT Star): RRT 알고리즘을 개선한 방식으로, 경로 탐색 후 경로의 최적화를 수행하여 더 짧은 경로를 찾는 방법이다.
PRM*: PRM 알고리즘을 개선하여 샘플링과 경로 최적화를 동시에 수행하는 방식이다.

장애물 회피 경로 계획

장애물 회피 경로 계획은 경로 계획 과정에서 장애물을 피하는 경로를 찾는 방법이다. 이를 위해 경로는 상태 공간 내에서 장애물과의 충돌을 피하면서 자유 공간 내에 존재해야 한다.

1. 전위장 기법 (Potential Field Method)

전위장 기법은 로봇이 목표점에 가까워질수록 인력을 받고, 장애물에 가까워질수록 척력을 받는 가상의 전기장처럼 경로를 설정하는 방식이다. 목표점에서의 인력 $F_{\text{goal}}$ 과 장애물에서의 척력 $F_{\text{obs}}$ 을 계산하여 총 힘을 통해 로봇의 경로를 결정한다.

$F_{\text{total}} = F_{\text{goal}} + F_{\text{obs}}$

이 방식은 계산이 간단하지만, 지역 최적해에 빠질 수 있는 단점이 있다.

2. Voronoi 다이어그램 (Voronoi Diagram)

Voronoi 다이어그램은 상태 공간에서 장애물로부터 최대한 멀리 떨어진 경로를 찾는 방법이다. 이는 상태 공간을 장애물과의 거리에 따라 분할한 후, 경로가 이러한 분할된 영역의 경계선을 따르도록 설계하는 방식이다. 이를 통해 로봇이 장애물에 최대한 가까워지지 않도록 경로를 찾을 수 있다.

경로 최적화 기법

경로 계획에서 경로 최적화는 목표 지점에 도달하는 경로를 가능한 한 짧거나 매끄럽게 만드는 것을 목표로 한다. 이는 연속적인 운동에서 에너지를 최소화하거나 충돌을 회피하면서 최적의 경로를 생성하기 위한 필수적인 과정이다.

1. 스플라인 기반 경로 최적화 (Spline-Based Path Optimization)

스플라인(Spline)은 주어진 제어점들을 부드럽게 연결하는 곡선을 의미하며, 경로 최적화에서 자주 사용된다. 특히, 3차 스플라인이 경로 최적화에서 많이 사용된다.

스플라인 곡선은 다음과 같이 정의할 수 있다.

$\mathbf{p}(t) = \sum_{i=0}^{n} \mathbf{a}_i t^i$

여기서 $\mathbf{a}_i$ 는 제어점을 나타내는 계수이며, $t$ 는 매개 변수이다. 이 방식은 매끄러운 경로를 보장하면서 충돌을 피하는 경로를 생성할 수 있다.

또한, 경로의 매끄러움을 보장하기 위해 스플라인의 연속성을 만족하는 제약 조건을 추가할 수 있다. 예를 들어, 경로의 첫 번째 도함수와 두 번째 도함수의 연속성을 다음과 같이 설정할 수 있다.

$\mathbf{p}'(t_i) = \mathbf{p}'(t_{i+1}), \quad \mathbf{p}''(t_i) = \mathbf{p}''(t_{i+1})$

이러한 제약을 통해 경로의 부드러움을 극대화할 수 있다.

2. 비용 함수 기반 경로 최적화 (Cost Function-Based Optimization)

경로 최적화 문제는 비용 함수 $J$ 를 최소화하는 최적화 문제로 정의할 수 있다. 비용 함수는 경로의 길이, 매끄러움, 에너지 소비 등을 포함할 수 있으며, 이와 같은 목표들을 달성하기 위해 정의된다.

경로 최적화 문제는 다음과 같은 형태로 표현할 수 있다.

$\min_{\mathbf{p}(t)} J(\mathbf{p}(t)), \quad \text{subject to} \quad \mathbf{p}(t) \in \mathcal{F}$

여기서 $J(\mathbf{p}(t))$ 는 경로의 성능을 평가하는 비용 함수이고, $\mathcal{F}$ 는 자유 공간이다.

예를 들어, 경로의 길이를 최소화하는 비용 함수는 다음과 같이 정의될 수 있다.

$J(\mathbf{p}(t)) = \int_0^T \|\mathbf{p}'(t)\| dt$

이 비용 함수는 경로의 속도를 최소화하여 최단 경로를 찾는 데 사용될 수 있다.

또한, 경로의 매끄러움을 극대화하기 위한 비용 함수는 두 번째 도함수를 최소화하는 방식으로 정의될 수 있다.

$J(\mathbf{p}(t)) = \int_0^T \|\mathbf{p}''(t)\|^2 dt$

이러한 비용 함수를 사용하면 경로의 급격한 변화 없이 매끄러운 경로를 생성할 수 있다.

3. 제약 조건을 고려한 최적화 (Constrained Optimization)

경로 최적화에서 제약 조건을 고려한 최적화는 특정 제약 조건을 만족하면서 경로를 최적화하는 방법이다. 대표적인 제약 조건으로는 장애물 회피, 속도 제한, 가속도 제한 등이 있다.

예를 들어, 장애물 회피를 위한 제약 조건은 다음과 같이 정의될 수 있다.

$\mathbf{p}(t) \notin \mathcal{O}, \quad \forall t \in [0, T]$

여기서 $\mathcal{O}$ 는 장애물 공간을 의미한다.

속도 제한을 위한 제약 조건은 다음과 같이 정의된다.

$\|\mathbf{p}'(t)\| \leq v_{\text{max}}, \quad \forall t \in [0, T]$

이러한 제약 조건을 통해 경로 계획에서 물체의 물리적 한계를 고려할 수 있다.

4. 경로 스무딩 (Path Smoothing)

경로 계획에서 생성된 경로가 직선 구간으로 이루어져 있을 경우, 경로의 급격한 변화가 발생할 수 있다. 이를 해결하기 위해 경로 스무딩 기술이 사용되며, 경로를 매끄럽게 변환하여 이동 과정에서의 불연속성을 제거한다.

스무딩 기법은 주로 스플라인을 사용하여 직선 구간을 곡선으로 변환한다. 특히, 3차 베지어 곡선 (Cubic Bezier Curve)이 많이 사용된다. 베지어 곡선은 주어진 시작점과 끝점, 그리고 두 개의 제어점을 이용하여 곡선을 정의한다.

3차 베지어 곡선은 다음과 같은 형태로 정의된다.

$\mathbf{p}(t) = (1 - t)^3 \mathbf{P}_0 + 3(1 - t)^2 t \mathbf{P}_1 + 3(1 - t) t^2 \mathbf{P}_2 + t^3 \mathbf{P}_3, \quad t \in [0, 1]$

여기서 $\mathbf{P}_0, \mathbf{P}_1, \mathbf{P}_2, \mathbf{P}_3$ 는 제어점이고, $t$ 는 매개변수이다.

5. 휴리스틱 기법 (Heuristic Methods)

휴리스틱 기법은 비용 함수의 전역 최적화를 보장하지 않지만, 비교적 짧은 시간 내에 근사 해를 찾는 데 유용하다. 대표적인 휴리스틱 기법으로는 유전자 알고리즘 (Genetic Algorithm)과 그리디 알고리즘 (Greedy Algorithm)이 있다.

유전자 알고리즘: 유전자 알고리즘은 진화론적 모델을 기반으로 최적 경로를 찾는 기법이다. 다양한 경로를 초기 개체로 설정하고, 이 개체들을 교차 및 변이를 통해 새로운 개체를 생성한 후, 적합도가 높은 경로를 선택하는 방식으로 최적의 경로를 찾는다.
그리디 알고리즘: 그리디 알고리즘은 현재 상태에서 최적의 선택을 반복적으로 수행하여 최종 경로를 찾는 방식이다. 이 방법은 항상 전역 최적해를 보장하지는 않지만, 계산량이 적고 빠르게 경로를 찾을 수 있다.