15.40 두 정식화의 계산 효율성 비교
1. 개요
라그랑주 정식화와 뉴턴-오일러 정식화는 매니퓰레이터의 동역학 분석의 두 가지 주요 정식화이다. 두 방법은 같은 결과를 도출하지만 계산 효율성에서는 상당한 차이를 보인다. 본 절에서는 두 정식화의 계산 효율성을 비교한다.
2. 계산 복잡도의 측정
2.1 자유도와의 관계
매니퓰레이터의 자유도 n이 증가할 때 계산 시간이 어떻게 증가하는지를 측정한다.
2.2 곱셈과 덧셈의 수
연산의 수는 일반적으로 곱셈과 덧셈의 수로 측정된다. 부동소수점 연산의 비용이 가장 큰 부분이다.
2.3 메모리 사용
계산에 필요한 메모리도 효율성의 한 측면이다.
3. 직접 라그랑주 방법
3.1 절차
직접 라그랑주 방법으로 동역학 방정식을 유도하는 절차는 다음과 같다.
- 운동 에너지의 계산: O(n^2)
- 위치 에너지의 계산: O(n)
- 라그랑지언의 미분: O(n^3) - O(n^4)
- 동역학 방정식의 정리: O(n^4)
3.2 총 복잡도
총 복잡도는 일반적으로 O(n^4)이다.
3.3 단점
자유도가 큰 매니퓰레이터에서 매우 비효율적이다. 6자유도 매니퓰레이터에서 약 7,300번의 곱셈과 5,500번의 덧셈이 필요하다.
4. 뉴턴-오일러 재귀 방법
4.1 절차
뉴턴-오일러 재귀 알고리즘은 다음의 단계로 구성된다.
- 전방 재귀: 기저로부터 말단까지 운동(속도, 가속도) 전파
- 후방 재귀: 말단으로부터 기저까지 힘과 토크 전파
- 관절 토크의 추출
4.2 총 복잡도
각 단계가 O(n)이므로 총 복잡도는 O(n)이다.
4.3 효율성
6자유도 매니퓰레이터에서 약 825번의 곱셈과 600번의 덧셈이 필요하다. 이는 라그랑주 방법의 약 1/9이다.
5. 관절 공간 관성 알고리즘
5.1 합성 강체 알고리즘 (CRBA)
CRBA는 매니퓰레이터의 관성 행렬을 계산하는 효율적 알고리즘이다. 복잡도는 O(n^2)이다.
5.2 관절 공간 관성 알고리즘 (ABA)
ABA는 페더스톤(Featherstone)이 1983년에 제시한 순동역학 알고리즘이다. 복잡도는 O(n)이다.
6. 비교 표
6.1 역동역학
| 방법 | 복잡도 | 6자유도 매니퓰레이터의 곱셈 수 |
|---|---|---|
| 직접 라그랑주 | O(n^4) | \approx 7300 |
| 효율적 라그랑주 | O(n^3) | \approx 1700 |
| 뉴턴-오일러 재귀 | O(n) | \approx 825 |
6.2 순동역학
| 방법 | 복잡도 |
|---|---|
| 라그랑주 + 직접 풀이 | O(n^4) + O(n^3) |
| CRBA + 풀이 | O(n^2) + O(n^3) |
| ABA | O(n) |
ABA가 가장 효율적이며 자유도가 클 때 매우 유리하다.
7. 자유도에 따른 효율 차이
7.1 작은 자유도
자유도가 작을 때(예: n < 6)는 정식화 사이의 차이가 크지 않다. 모든 방법이 실시간 계산이 가능하다.
7.2 중간 자유도
자유도가 중간(예: n = 7-10)이면 효율적 알고리즘의 이점이 명확해진다. 뉴턴-오일러 재귀가 직접 라그랑주보다 5-10배 빠르다.
7.3 큰 자유도
자유도가 크면(예: n > 20, 휴머노이드 로봇) 효율적 알고리즘이 필수적이다. ABA가 가장 효율적이다.
8. 자세한 비교
8.1 자유도 매니퓰레이터
표준 6자유도 매니퓰레이터에 대한 구체적 비교는 다음과 같다.
뉴턴-오일러 재귀 알고리즘
- 곱셈: \approx 825
- 덧셈: \approx 600
직접 라그랑주 방법
- 곱셈: \approx 7300
- 덧셈: \approx 5500
차이는 약 9배이다.
8.2 자유도 매니퓰레이터
7자유도 매니퓰레이터에서는 차이가 더 커진다.
8.3 자유도 휴머노이드
30자유도 휴머노이드 로봇에서는 ABA가 직접 라그랑주보다 수백 배 효율적이다.
9. 응용에 따른 선택
9.1 분석
매니퓰레이터의 동역학 분석에서는 라그랑주 방법의 닫힌 형식이 유리하다. 효율성보다는 명확성이 중요하다.
9.2 실시간 제어
실시간 제어에서는 효율적인 알고리즘(뉴턴-오일러 재귀 또는 ABA)이 필수적이다.
9.3 동적 시뮬레이션
동적 시뮬레이션에서는 ABA가 가장 효율적이다.
9.4 매개 변수 식별
매개 변수 식별에서는 회귀 행렬 형식이 사용된다. 이는 라그랑주 방법으로부터 자연스럽게 도출된다.
10. 자동화 도구의 영향
10.1 코드 생성
심볼릭 도구로 자동 생성된 코드는 두 방법 모두에서 효율적일 수 있다. 공통 부분 식의 추출 등의 최적화가 적용된다.
10.2 라이브러리
매니퓰레이터 동역학 라이브러리(Pinocchio, RBDL 등)는 효율적인 알고리즘을 제공한다.
11. 본 절의 의의
본 절은 라그랑주 방법과 뉴턴-오일러 방법의 계산 효율성을 비교했다. 효율성의 차이는 매니퓰레이터의 자유도와 응용에 따라 다르며, 적절한 방법의 선택이 실시간 응용의 가능성을 결정한다.
12. 참고 문헌
- Featherstone, R. (2008). Rigid Body Dynamics Algorithms. Springer.
- Hollerbach, J. M. (1980). A recursive Lagrangian formulation of manipulator dynamics. IEEE Transactions on Systems, Man, and Cybernetics, 10(11), 730-736.
- Walker, M. W., & Orin, D. E. (1982). Efficient dynamic computer simulation of robotic mechanisms. ASME Journal of Dynamic Systems, Measurement, and Control, 104(3), 205-211.
- Featherstone, R. (1983). The calculation of robot dynamics using articulated-body inertias. International Journal of Robotics Research, 2(1), 13-30.
version: 1.0