13.43 뉴턴-오일러 재귀 알고리즘의 원리
1. 개요
뉴턴-오일러 재귀 알고리즘(Newton-Euler recursive algorithm)은 직렬 매니퓰레이터의 동역학을 효율적으로 계산하는 알고리즘이다. 1980년대 루(J. Y. S. Luh), 워커(M. W. Walker), 폴(R. P. Paul) 등에 의해 개발되었으며, 매니퓰레이터 동역학 계산의 표준이 되었다. 본 절에서는 알고리즘의 원리와 구조를 다룬다.
2. 알고리즘의 동기
2.1 라그랑주 방법의 한계
라그랑주 방법으로 매니퓰레이터 동역학을 직접 유도하면 수식이 매우 복잡해진다. 시간 복잡도가 O(n^4)이며, 자유도 n이 클수록 비효율적이다.
2.2 재귀 알고리즘의 효율성
뉴턴-오일러 재귀 알고리즘은 시간 복잡도가 O(n)이다. 즉, 자유도에 선형적이다. 이는 실시간 제어에 적합하다.
2.3 효율성의 비결
알고리즘의 효율성은 다음의 사실에서 비롯된다.
- 인접한 링크의 운동학적, 동역학적 양 사이의 관계가 단순하다.
- 한 링크의 양은 인접 링크의 양으로부터 빠르게 계산된다.
- 이러한 관계가 재귀적으로 적용된다.
3. 알고리즘의 구조
3.1 두 단계
뉴턴-오일러 재귀 알고리즘은 두 단계로 구성된다.
3.1.1 순방향 재귀
베이스에서 말단으로 전파되는 순방향 재귀(forward recursion)에서 운동학적 양(속도, 가속도)이 계산된다.
3.1.2 역방향 재귀
말단에서 베이스로 전파되는 역방향 재귀(backward recursion)에서 동역학적 양(힘, 토크)이 계산된다.
3.2 의미
운동학은 베이스에서 말단으로 자연스럽게 전파되고, 동역학은 말단에서 베이스로 전파된다. 두 단계의 결합이 전체 동역학을 결정한다.
4. 순방향 재귀
4.1 운동학적 양
각 링크에 대해 다음의 양들이 계산된다.
- 각속도 \boldsymbol{\omega}_i
- 각가속도 \dot{\boldsymbol{\omega}}_i
- 선가속도 \mathbf{a}_i (질량 중심의 가속도)
4.2 재귀 관계
링크 i의 양은 링크 i - 1의 양과 관절 변수로부터 계산된다.
4.2.1 각속도
\boldsymbol{\omega}_i = \boldsymbol{\omega}_{i-1} + \mathbf{R}_i^{i-1}\dot q_i\hat{\mathbf{z}}_i
(회전 관절의 경우; \hat{\mathbf{z}}_i는 관절 축의 방향)
4.2.2 각가속도
\dot{\boldsymbol{\omega}}_i = \dot{\boldsymbol{\omega}}_{i-1} + \mathbf{R}_i^{i-1}\ddot q_i\hat{\mathbf{z}}_i + \boldsymbol{\omega}_i \times (\mathbf{R}_i^{i-1}\dot q_i\hat{\mathbf{z}}_i)
4.2.3 선가속도
링크의 질량 중심의 가속도는 인접 링크의 가속도와 회전 효과로부터 계산된다.
4.3 시작 조건
베이스의 운동학적 양은 알려져 있다(또는 0이다). 이로부터 재귀가 시작된다.
5. 역방향 재귀
5.1 동역학적 양
각 링크에 대해 다음의 양들이 계산된다.
- 관성력 \mathbf{F}_i
- 관성 토크 \mathbf{N}_i
- 링크에 작용하는 힘과 토크
5.2 뉴턴-오일러 방정식
각 링크에 대해 뉴턴-오일러 방정식이 적용된다.
5.2.1 뉴턴 방정식
\mathbf{F}_i = M_i\mathbf{a}_{c,i}
여기서 M_i는 질량, \mathbf{a}_{c,i}는 질량 중심의 가속도이다.
5.2.2 오일러 방정식
\mathbf{N}_i = \mathbf{I}_i\dot{\boldsymbol{\omega}}_i + \boldsymbol{\omega}_i \times (\mathbf{I}_i\boldsymbol{\omega}_i)
여기서 \mathbf{I}_i는 관성 텐서이다.
5.3 재귀 관계
각 링크에 작용하는 힘과 토크는 다음 링크에 대한 반력으로부터 계산된다.
5.3.1 힘
\mathbf{f}_i = \mathbf{R}_{i+1}^i\mathbf{f}_{i+1} + \mathbf{F}_i
여기서 \mathbf{f}_i는 링크 i - 1이 링크 i에 가하는 힘이다.
5.3.2 토크
\boldsymbol{\tau}_i = \mathbf{R}_{i+1}^i\boldsymbol{\tau}_{i+1} + \mathbf{r}_{c,i} \times \mathbf{F}_i + \mathbf{N}_i + \mathbf{r}_{i+1,i} \times (\mathbf{R}_{i+1}^i\mathbf{f}_{i+1})
5.4 시작 조건
말단 장치에 가해지는 외부 힘과 토크는 알려져 있다(또는 0이다). 이로부터 역방향 재귀가 시작된다.
5.5 관절 토크
각 관절의 토크는 링크 i에 작용하는 토크의 관절 축 방향 성분이다.
\tau_i = \boldsymbol{\tau}_i^T\hat{\mathbf{z}}_i
(회전 관절의 경우)
6. 알고리즘의 의사 코드
입력: 관절 변수 q, 속도 q_dot, 가속도 q_ddot
출력: 관절 토크 tau
// 순방향 재귀
ω_0 = 0, ω_dot_0 = 0, a_0 = -g (중력 보상)
for i = 1 to n:
ω_i = R^{i-1}_i^T (ω_{i-1} + q_dot_i * z)
ω_dot_i = R^{i-1}_i^T (ω_dot_{i-1} + q_ddot_i * z + ω_{i-1} × (q_dot_i * z))
a_i = R^{i-1}_i^T a_{i-1} + ω_dot_i × r_{i,c} + ω_i × (ω_i × r_{i,c})
// 역방향 재귀
f_{n+1} = 0, τ_{n+1} = 0 (외부 힘이 없는 경우)
for i = n to 1:
F_i = M_i * a_i
N_i = I_i * ω_dot_i + ω_i × (I_i * ω_i)
f_i = R^i_{i+1} f_{i+1} + F_i
τ_i = R^i_{i+1} τ_{i+1} + r_{i,c} × F_i + N_i + ...
// 관절 토크 추출
tau_i = τ_i^T z
7. 알고리즘의 효율성
7.1 시간 복잡도
뉴턴-오일러 재귀 알고리즘의 시간 복잡도는 O(n)이다. 자유도에 선형적이다.
7.2 공간 복잡도
공간 복잡도도 O(n)이다. 각 링크에 대한 변수만 저장하면 된다.
7.3 비교
라그랑주 방법으로 직접 유도하면 시간 복잡도가 O(n^4)이다. 뉴턴-오일러 재귀 알고리즘이 훨씬 효율적이다.
8. 응용
8.1 역동역학 계산
뉴턴-오일러 재귀 알고리즘은 역동역학(주어진 운동에 필요한 토크 계산)에 가장 효율적이다. 실시간 제어에 사용된다.
8.2 순동역학
순동역학(주어진 토크에서의 운동 계산)에는 ABA(articulated body algorithm)가 더 효율적이다.
8.3 매니퓰레이터 제어
매니퓰레이터의 계산 토크 제어, 모델 기반 제어에서 뉴턴-오일러 재귀 알고리즘이 사용된다.
9. 본 절의 의의
본 절은 뉴턴-오일러 재귀 알고리즘의 원리를 다루었다. 이는 매니퓰레이터 동역학 계산의 표준 알고리즘이며, 효율성과 정확성에서 우수하다. 후속 절에서 이 알고리즘의 세부 사항을 더 다룬다.
10. 학습 권장사항
- 알고리즘의 두 단계 구조를 이해한다.
- 순방향과 역방향 재귀의 의미를 인식한다.
- 효율성의 이유를 학습한다.
- 단순한 매니퓰레이터에 적용해 본다.
- 라그랑주 방법과의 비교를 인식한다.
11. 참고 문헌
- Luh, J. Y. S., Walker, M. W., & Paul, R. P. (1980). “On-line computational scheme for mechanical manipulators.” Journal of Dynamic Systems, Measurement, and Control, 102(2), 69–76.
- Featherstone, R. (2008). Rigid Body Dynamics Algorithms. Springer.
- Murray, R. M., Li, Z., & Sastry, S. S. (1994). A Mathematical Introduction to Robotic Manipulation. CRC Press.
- Spong, M. W., Hutchinson, S., & Vidyasagar, M. (2020). Robot Modeling and Control (2nd ed.). Wiley.
version: 1.0