7.147 최소 스냅 궤적 생성

1. 최소 스냅 궤적의 동기

멀티로터(multirotor) 무인 비행체에서 로터의 추력은 기체의 위치 벡터 $\mathbf{r}(t)$ 의 4차 도함수, 즉 스냅(snap) $\mathbf{r}^{(4)}(t)$ 과 밀접하게 관련된다. 미분 평탄성(differential flatness) 성질에 의해 멀티로터의 상태와 제어 입력이 평탄 출력(flat output) $[\mathbf{r}(t), \psi(t)]$ (위치와 요각)과 그 도함수들로 완전히 결정되며, 추력과 모멘트는 스냅까지의 도함수에 의존한다. 따라서 스냅의 적분을 최소화하면 추력 변동이 최소화되어 매끄럽고 에너지 효율적인 비행이 실현된다.

2. 문제의 정식화

$M+1$ 개의 경유점 $\mathbf{r}_0, \mathbf{r}_1, \ldots, \mathbf{r}_M$ 과 각 구간의 시간 할당 $T_k = t_{k+1} - t_k$ 가 주어질 때, 스냅의 제곱 적분을 최소화하는 궤적을 구한다. 각 좌표 축( $x, y, z$ )에 대해 독립적으로 풀 수 있으며, 스칼라 궤적 $r(t)$ 에 대한 문제는 다음과 같다.

$\min_{r(t)} \quad \int_{t_0}^{t_M} \left(\frac{d^4 r}{dt^4}\right)^2 dt$

$\text{s.t.} \quad r(t_k) = r_k, \quad k = 0, 1, \ldots, M$

$\text{경계 조건}: \; \dot{r}(t_0), \ddot{r}(t_0), \dddot{r}(t_0), \; \dot{r}(t_M), \ddot{r}(t_M), \dddot{r}(t_M)$

3. 구분적 다항식 표현

스냅의 적분을 최소화하는 궤적은 각 구간에서 7차(또는 최소 2×4-1 = 7차) 다항식으로 표현된다. 이는 변분법의 오일러-라그랑주 방정식에 의해 각 구간에서 $r^{(8)}(t) = 0$ 이 성립하기 때문이다.

구간 $k$ 에서의 궤적:

$r_k(t) = \sum_{j=0}^{2p-1} c_{k,j}(t - t_k)^j$

여기서 $p = 4$ (스냅 최소화의 경우)이므로 7차 다항식이다.

4. 이차 계획 문제로의 환원

다항식 계수를 결정 변수로 하면, 스냅의 적분은 계수의 이차 형식이 된다.

$J_k = \int_{t_k}^{t_{k+1}} \left(\frac{d^4 r_k}{dt^4}\right)^2 dt = \mathbf{c}_k^T\mathbf{Q}_k\mathbf{c}_k$

여기서 $\mathbf{Q}_k$ 는 다항식의 4차 도함수 적분에서 유도되는 양의 반정치 행렬이다. 총 비용은 $J = \sum_k \mathbf{c}_k^T\mathbf{Q}_k\mathbf{c}_k$ 이다.

경유점 제약, 경계 조건, 구간 경계에서의 연속성 조건(위치, 속도, 가속도, 저크의 연속)은 모두 계수에 대한 선형 등식 제약이다. 따라서 전체 문제는 다음의 등식 제약 QP가 된다.

$\min_{\mathbf{c}} \quad \frac{1}{2}\mathbf{c}^T\mathbf{Q}\mathbf{c} \quad \text{s.t.} \quad \mathbf{A}\mathbf{c} = \mathbf{b}$

이 QP의 해석적 해는 KKT 시스템을 풀어 구할 수 있다.

5. 비제약 QP로의 변환

경유점에서의 중간 도함수(속도, 가속도, 저크)를 자유 변수로 두면, 등식 제약을 명시적으로 소거하여 비제약 QP로 변환할 수 있다. 각 구간의 다항식 계수는 경계 조건(양 끝점의 위치와 도함수)에 의해 유일하게 결정되므로, 결정 변수가 경유점에서의 자유 도함수 벡터 $\mathbf{d}_f$ 로 축소된다.

$\min_{\mathbf{d}_f} \quad \frac{1}{2}\mathbf{d}_f^T\mathbf{R}\mathbf{d}_f + \mathbf{d}_f^T\mathbf{p}$

이 비제약 이차 문제의 해는 $\mathbf{d}_f^* = -\mathbf{R}^{-1}\mathbf{p}$ 로 해석적으로 주어진다.

6. 안전 복도 제약의 통합

장애물 환경에서 궤적이 안전 복도(safe corridor) 내에 머물도록 부등식 제약을 추가한다. 각 구간에서 궤적이 볼록 다면체 $\mathcal{P}_k = \{\mathbf{r} : \mathbf{A}_k\mathbf{r} \leq \mathbf{b}_k\}$ 내에 있어야 한다.

구간 내의 이산 시점에서 제약을 부과하면 다항식 계수에 대한 선형 부등식이 된다.

$\mathbf{A}_k \left(\sum_j c_{k,j}(t_s - t_k)^j\right) \leq \mathbf{b}_k, \quad t_s \in \text{검사점}$

이로써 전체 문제는 부등식 제약을 포함하는 QP가 된다.

7. 시간 할당의 동시 최적화

구간 시간 $\{T_k\}$ 가 사전에 고정되면 문제는 볼록 QP이지만, $\{T_k\}$ 를 함께 최적화하면 비볼록 NLP가 된다. 구간 시간의 최적화를 위해 다음의 접근법이 사용된다.

교대 최적화: 다항식 계수와 구간 시간을 교대로 최적화한다. 계수 최적화는 QP이고, 시간 최적화는 비선형 문제이다.

경사 기반 시간 최적화: 총 비용의 $T_k$ 에 대한 그래디언트를 계산하여 경사 하강법으로 시간 할당을 갱신한다.

8. 멀티로터 궤적 생성의 실용적 구현

Mellinger와 Kumar(2011)의 프레임워크가 멀티로터 궤적 생성의 기초를 정립하였으며, 이후 Richter 등(2016)에 의해 비제약 QP 형식으로의 변환과 시간 할당 최적화가 발전되었다. 실용적 구현에서 궤적 생성의 계산 시간은 수 밀리초 수준으로, 실시간 재계획이 가능하다.

9. 참고 문헌

Mellinger, D., & Kumar, V. (2011). “Minimum Snap Trajectory Generation and Control for Quadrotors.” Proceedings of ICRA, 2520–2525.
Richter, C., Bry, A., & Roy, N. (2016). “Polynomial Trajectory Planning for Aggressive Quadrotor Flight in Dense Indoor Environments.” Robotics Research, Springer Tracts in Advanced Robotics, 649–666.
Mueller, M. W., Hehn, M., & D’Andrea, R. (2015). “A Computationally Efficient Motion Primitive for Quadrocopter Trajectory Generation.” IEEE Transactions on Robotics, 31(6), 1294–1310.

version: 1.0