14.17 뉴턴-오일러 재귀 역동역학의 계산 복잡도
1. 개요
뉴턴-오일러 재귀 역동역학 알고리즘의 계산 복잡도는 매니퓰레이터의 자유도 n에 선형적이다. 이는 다른 동역학 알고리즘과 비교하여 매우 효율적이다. 본 절에서는 알고리즘의 계산 복잡도를 분석한다.
2. 시간 복잡도
2.1 선형 복잡도
뉴턴-오일러 재귀 역동역학 알고리즘의 시간 복잡도는
T(n) = O(n)
여기서 n은 자유도이다.
2.2 이유
각 링크에 대해 일정한 수의 행렬 곱과 외적이 필요하므로, 전체 계산은 n에 선형적이다.
3. 연산의 수
3.1 곱셈과 덧셈
각 링크에 대한 연산의 수는 다음과 같이 추정된다.
- 전방 재귀 (한 링크): 약 100~150 곱셈, 약 70~100 덧셈
- 후방 재귀 (한 링크): 약 70~100 곱셈, 약 50~70 덧셈
3.2 전체
n자유도 매니퓰레이터의 전체 계산은
- 곱셈: 약 200n 정도
- 덧셈: 약 130n 정도
(정확한 수치는 구현에 따라 다르다.)
4. 공간 복잡도
4.1 메모리 사용
각 링크의 운동학적, 동역학적 양을 저장해야 한다. 따라서 메모리 사용은 O(n)이다.
4.2 변수의 수
각 링크에 대해 다음의 변수가 저장된다.
- 각속도 (3개 성분)
- 각가속도 (3개 성분)
- 선가속도 (3개 성분)
- 관성력 (3개 성분)
- 관성 모멘트 (3개 성분)
- 힘과 토크 (각각 3개 성분)
5. 다른 알고리즘과의 비교
5.1 라그랑주 직접 방법
라그랑주 방정식을 직접 유도하면 시간 복잡도가 O(n^4)이다. 자유도가 클수록 매우 비효율적이다.
5.2 효율적 라그랑주
효율적 라그랑주 방법(Walker-Orin 등)은 O(n^2) 또는 O(n^3)이다.
5.3 뉴턴-오일러 재귀
뉴턴-오일러 재귀 알고리즘은 O(n)이다. 가장 효율적이다.
| 알고리즘 | 시간 복잡도 |
|---|---|
| 라그랑주 (직접) | O(n^4) |
| 라그랑주 (효율적) | O(n^2) ~ O(n^3) |
| 뉴턴-오일러 재귀 | O(n) |
6. 실시간 성능
6.1 실시간 가능
O(n) 복잡도로 인해 뉴턴-오일러 재귀 알고리즘은 실시간 제어에 적합하다. 일반적인 6자유도 매니퓰레이터의 동역학 계산이 마이크로초 단위로 가능하다.
6.2 임베디드 시스템
임베디드 시스템에서도 효율적이다. 제한된 자원에서 동작 가능하다.
7. 순동역학과의 비교
7.1 역동역학
역동역학(주어진 운동에 필요한 토크 계산)은 O(n)이다.
7.2 순동역학
순동역학(주어진 토크에서의 가속도 계산)은 다른 알고리즘이 필요하다. 일반적으로 O(n^3)이지만, ABA(Articulated Body Algorithm)는 O(n)이다.
8. 본 절의 의의
본 절은 뉴턴-오일러 재귀 알고리즘의 계산 복잡도를 다루었다. O(n)의 효율성이 이 알고리즘이 실시간 제어와 시뮬레이션에 광범위하게 사용되는 이유이다.
9. 참고 문헌
- 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.
- Walker, M. W., & Orin, D. E. (1982). “Efficient dynamic computer simulation of robotic mechanisms.” Journal of Dynamic Systems, Measurement, and Control, 104(3), 205–211.
version: 1.0