Game Engineering 2

Numerical Solution of Inverse Kinematics

1. Introduction

1-1. Notations

• IK : Target position에 end effector가 닿기
• Joint angles
  • $\theta_j$
  • column vector $\theta=(\theta_1,...,\theta_n)^T$
• end effector positions
  • $s_1,s_2, ..., s_k$
  • column vector $(s_1, s_2,..., s_k)^T : \vec{s}$
• target positions
  • $t_i$ -> i-th end effecor's target position
  • column vector $(t_1,t_2,..,t_k)^T$
• desired change
  • $e_i=t_i-s_i$
• FK
  • $\vec{s}=f(\theta)$
• IK
  • $s_d:\theta=f^{-1}(\vec{s_d)}$

1-2. Introduction

• 위에서 언급한 function f는 non-linear 하고 풀기 어렵다.
• IK를 풀기 위해선 Kinetic Angular variables 알아야 합니다..

1-3. Kinetic Angular Variables

Angular Velocity in 2D

• 곡선위를 움직이는 particle의 위치를 표현하는 방법
  • Cartesian coordinate (using angle theta)
    • $x = Rcos\theta, y=Rsin\theta$
  • Kinetic Angular Variables
    • captured by the concept of the angular velocity
      • $\omega=lim_{\Delta t \to0}\frac{\Delta\theta}{\Delta t}=\frac{d\theta}{dt}$
      • $\theta(t)=\theta_i+\omega(t-t_i)$
      • $\Delta \theta = \omega\Delta t$
    • angular acceleration
      • $\alpha = lim_{\Delta t \to 0}\frac{\Delta \omega}{\Delta t}=\frac{d\omega}{dt}$
      • $\omega(t)=\omega_i+\alpha(t-t_i)$, $\Delta\omega = \alpha\Delta t$
      • $\theta(t)=\theta_i+\omega(t-t_i)+\frac{1}{2}\alpha(t-t_i)^2$, $\Delta \theta = \omega_i\Delta t + \frac{1}{2}\alpha(\Delta t)^2$
    • arc
      • $s=R|\Delta\theta|$
      • 매우 작은 변위에서.. $s\cong|\Delta\vec{r}|$
      • $s=R|\Delta\theta|$ 를 $\Delta t$로 나누면
    • 순간 속도 (각도와 속도간의 거리를 알 수 있다)
      • $v: |\vec{v}|=|lim_{\Delta t \to 0}\frac{s}{\Delta t}|=R|\omega|$
• Angular Velocity in 2D
  • Polar coordinates $(r,\phi)$ 예시
    • 원점 O에서 P까지의 거리 r
    • p에서 가해지는 힘(캐릭터를 움직이는 힘 $v$) 벡터 분해
      • $v_{\perp}, \ v_{\parallel}$
    • 각속도 $w=\frac{d\phi}{dt}=\frac{v_{\perp}}{r}=\frac{vsin(\theta)}{r}$ -> $\vec{v_{\perp}}=r\omega$ 이므로

Angular Velocity in 3D

• 3d에서는 rotation angle이 axis angle로 표현된다.
• unity vector : 회전축 $u$
• 축 주위의 회전 크기를 설명하는 각도 : $\theta$
• orbital angular velocity vector (3차원)
  • $\omega = \omega_{2d}u = \frac{d\theta}{dt}u=\frac{vsin(\theta)}{r}u$
    -> $\omega = \frac{d\theta}{dt}, \ v_{\perp}=r\omega$ 사용
    -> $w_{2d}$ : 2차원 각속도
• $\omega = \frac{vsin(\theta)}{r}u=\frac{rvsin(\theta)u}{rr}=\frac{r\times v}{r^2}$

Angular Momentum & Moment of inertia

• Angular Momentum
  • 물체의 회전 운동을 위해 존재
  • Linear momentum (참고)
    • linear momentum :$p$
    • mass : $m$
    • linear speed : $v$
      -> $p=mv$
  • Angular momentum
    • angular momentum : $L$
    • inertia : $I$
    • angular speed : $\omega$
      -> $L=I\omega$
• Moment of inertia
  • 물체의 운동 변화에 대한 제한을 나타낸다.
  • 회전축 주변의 질량 분포에 의존
  • $mr^2$

2. Basic Math

2-1. Gradient

• 한 점에서 가장 maximum으로 가는 방향을 나타낸다.
• notation
  • $\nabla f$
• 함수에 대한 1차 편미분 형태
  • $\nabla f = (\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}, ...)$

2-2. Hessian

• local curvature 을 나타낸다.
• 계산
  • 함수에 대한 2차 편미분 형태
• 제한 조건
  • f의 2차 미분 형태가 존재해야함
  • 함수의 domain에서 연속이어야 함
    -> f의 Hessian은 n x n matrix이다.
• 특징
  • 대칭 행렬
  • Jacobian 과의 관계 : $H(f(x))=J(\nabla f(x))$

3. Jacobian Inverse Methods

3-1. Jacobian Problems

• Jacobian은 IK 문제를 푸는 linear approximation 방식이다.
  • actual motion을 근사해서 푸는 것
• 이때 $\Delta t$가 매우 작으면 $J$가 $f$와 같아질 것이라고 생각하기
  • 이렇게 근사치로 계산하는 경우 $J$를 매 $t$ 마다 구해야 하므로 느리다.
• $J(\theta)_{ij}=(\frac{\partial s_i}{\partial \theta_j})_{ij}$
  • j-th joint가 1 DoF의 rotational joint 인 경우 (간소화 하기)
  • $\omega_{2d}=\frac{\partial s_i}{\partial \theta_j}=v_j\times (s_i-p_j)$
    • s는 end effector위치
    • p는 joint 위치
    • v는 회전축의 unit vector

3-2. Jacobian으로 IK 풀기

• 우리가 구하고 싶은 것 : $\vec{s}=f(\theta)$
  • f를 모르기 때문에 J로 근사해서 풀기!
• 미분 하면...
  • $\frac{d\vec{s}}{dt_t}=J(\theta)\frac{d\theta}{dt_t}$ -> $J(\theta)=\frac{d\vec{s}}{d\theta}$
• 구하려고 하는 것이 end effector가 가야하는 곳
  -> end effector가 desired change in position 이어야 한다.
  -> $\vec{e}=J\Delta\theta$
  -> $\Delta\theta = J^{-1}\vec{e}$

3-3. Jacobian Pseudo-inverse

• $\Delta\theta = J^{-1}\vec{e}$ 식의 문제점
  • $J$ 의 det가 없는 경우..
    • not be square
    • invertible
      -> desired position에 닿지 못함
• 해결책
  • Jacobian Psudo-inverse (Moore-Penrose inverse)
  • 대략적으로 invertible 한 것 찾기
  • notation : $J^{\dagger}$
  • $\vec{e}=J\Delta\theta$ 를 푸는데 Least Square 형식의 가장 좋은 해결책!!

3-4. Pseudo-inverse

• 우리가 풀어야 하는 문제는... $\vec{e}=J\Delta\theta$
• $(I-J^{\dagger}J)$
• $J(I-J^{\dagger}J)\varphi$
  -> $\Delta \theta = J^{\dagger}\vec{e}+(I-J^{\dagger}J)\varphi$
  -> $J^{\dagger}\vec{e}$ : for IK
  -> $(I-J^{\dagger}J)\varphi$ : pseudo inverse error

3-5. Pseudo-inverse approaches

• Analytical Jacobian Method
• Moore-Penrose Method
• Jacobian Transpose Method
• Damped Least Square Method
• SVD Method