7.146 시간 할당 최적화와 최소 시간 궤적

1. 시간 할당 문제의 정의

경유점(waypoint) 시퀀스 $\mathbf{q}_0, \mathbf{q}_1, \ldots, \mathbf{q}_M$ 이 주어지고, 각 구간의 궤적 형상이 결정되어 있을 때, 각 구간에 할당되는 시간 $T_k = t_{k+1} - t_k$ ( $k = 0, \ldots, M-1$ )를 최적화하는 문제를 시간 할당 최적화(time allocation optimization)라 한다. 총 이동 시간은 $T_{total} = \sum_{k=0}^{M-1} T_k$ 이다.

시간 할당은 궤적의 속도, 가속도, 저크(jerk) 프로파일에 직접적으로 영향을 미치며, 구간 시간이 짧으면 속도와 가속도가 증가하고, 길면 이동이 느려진다.

2. 경로를 따른 시간 최적화

2.1 경로-시간 분리

경로의 기하학적 형상이 경로 매개변수 $s \in [0, S]$ 에 의해 $\mathbf{q}(s)$ 로 사전에 정의되어 있을 때, 시간 사상(time parameterization) $s(t)$ 를 최적화하는 문제이다. 관절 속도와 가속도는 다음과 같이 분해된다.

$\dot{\mathbf{q}} = \mathbf{q}'(s)\dot{s}, \quad \ddot{\mathbf{q}} = \mathbf{q}'(s)\ddot{s} + \mathbf{q}''(s)\dot{s}^2$

토크 제약 $\lvert \tau_i \rvert \leq \tau_{i,\max}$ 를 운동 방정식에 대입하면, $(\dot{s}^2, \ddot{s})$ 공간에서의 선형 부등식 제약을 얻는다.

$a_i(s)\ddot{s} + b_i(s)\dot{s}^2 + c_i(s) \leq \tau_{i,\max}$

$a_i(s)\ddot{s} + b_i(s)\dot{s}^2 + c_i(s) \geq -\tau_{i,\max}$

2.2 볼록 최적화로의 변환

변수 치환 $b(s) = \dot{s}^2$ 를 도입하면 $\ddot{s} = \frac{1}{2}\frac{db}{ds}$ 이다. 시간 최적 문제의 비용 함수는 다음과 같이 변환된다.

$T_{total} = \int_0^S \frac{1}{\dot{s}} ds = \int_0^S \frac{1}{\sqrt{b(s)}} ds$

제약은 $b(s)$ 와 $b'(s)$ 에 대한 선형 부등식이 된다. 이 문제는 볼록 최적화로, LP 또는 SOCP로 정식화하여 전역 최적 시간 할당을 효율적으로 구할 수 있다.

3. 경유점 통과 궤적의 시간 할당

3.1 다항식 궤적의 시간 최적화

최소 스냅(minimum snap) 궤적과 같이 구간별 다항식으로 궤적이 표현되는 경우, 구간 시간 $\{T_k\}$ 가 다항식 계수와 비선형적으로 결합된다. 총 비용(스냅 적분)을 구간 시간의 함수로 표현하면 다음과 같다.

$J(\{T_k\}) = \min_{\mathbf{c}} \mathbf{c}^T\mathbf{Q}(\{T_k\})\mathbf{c}$

여기서 $\mathbf{Q}(\{T_k\})$ 는 $T_k$ 에 의존하는 비용 행렬이고, $\mathbf{c}$ 는 다항식 계수이다. $J$ 는 $T_k$ 에 대해 비볼록이므로 경사 기반 국소 최적화가 사용된다.

비용의 그래디언트 $\partial J / \partial T_k$ 는 행렬 미분과 최적 계수의 감도 분석으로 계산된다.

3.2 속도-가속도 제약하의 시간 할당

각 구간의 최대 속도와 가속도가 물리적 한계를 초과하지 않도록 $T_k$ 의 하한을 설정한다. $p$ 차 다항식 궤적에서 최대 속도는 $O(1/T_k)$ 에 비례하므로, $T_k$ 가 짧으면 속도 제약이 위반된다.

$T_k \geq T_{k,\min} = \max_i \frac{\lVert \mathbf{q}'_i \rVert_{max,k}}{\dot{q}_{i,\max}}$

4. 사다리꼴 속도 프로파일

산업용 로봇에서 널리 사용되는 단순한 시간 할당 방법으로, 각 관절에 대해 사다리꼴(trapezoidal) 속도 프로파일을 설계한다. 가속 구간, 등속 구간, 감속 구간의 세 단계로 구성되며, 최대 속도와 최대 가속도를 고려하여 각 구간의 시간을 결정한다.

가속 시간: $t_a = v_{\max} / a_{\max}$

이동 거리가 충분하면: $T = \frac{d}{v_{\max}} + \frac{v_{\max}}{a_{\max}}$

이동 거리가 짧으면 (등속 구간 없음): $T = 2\sqrt{d / a_{\max}}$

다관절 로봇에서는 가장 느린 관절에 의해 전체 구간 시간이 결정되도록 동기화한다.

5. S-커브 속도 프로파일

사다리꼴 프로파일의 가속도 불연속을 제거하기 위해, 저크(jerk) 제한을 추가한 S-커브(S-curve) 프로파일이 사용된다. 7개의 단계(저크 증가, 등가속, 저크 감소, 등속, 저크 증가, 등감속, 저크 감소)로 구성되며, 가속도가 연속으로 변화하여 기계적 진동이 억제된다.

6. 시간-에너지 복합 최적화

시간과 에너지를 동시에 고려하는 복합 비용 함수의 경우, 구간 시간의 분배가 두 목표의 상충 관계를 반영한다.

$J = \alpha \sum_k T_k + \beta \sum_k \int_{t_k}^{t_{k+1}} \lVert \boldsymbol{\tau}(t) \rVert^2 dt$

$\alpha$ 가 크면 시간 최소화가 우선되어 구간 시간이 짧아지고, $\beta$ 가 크면 에너지 최소화가 우선되어 구간 시간이 길어진다.

7. 참고 문헌

Bobrow, J. E., Dubowsky, S., & Gibson, J. S. (1985). “Time-Optimal Control of Robotic Manipulators Along Specified Paths.” The International Journal of Robotics Research, 4(3), 3–17.
Verscheure, D., et al. (2009). “Time-Optimal Path Tracking for Robots: A Convex Optimization Approach.” IEEE Transactions on Automatic Control, 54(10), 2318–2327.
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.
Biagiotti, L., & Melchiorri, C. (2008). Trajectory Planning for Automatic Machines and Robots. Springer.

version: 1.0