Hippo: High-performance Interior-Point and Projection-based Solver for Generic Constrained Trajectory Optimization

1. 문제 정의 (Problem)

로봇 제어 및 운동 계획의 핵심인 궤적 최적화 (Trajectory Optimization) 분야에서 기존 솔버들은 다음과 같은 한계를 가지고 있습니다:

• 효율성 부족: 순차적 2 차 계획법 (SQP) 이나 미분 동적 계획법 (DDP) 기반 솔버들은 복잡한 제약 조건이 포함된 대규모 문제에서 계산 효율이 낮습니다.
• 수렴성 문제: 불평등 제약 조건 (inequality constraints) 이나 강등성 제약 (hard constraints) 이 포함된 문제에서 수렴이 느리거나 실패하는 경우가 많습니다.
• 모델링 유연성: 암시적 동역학 (implicit dynamics) 이나 복잡한 접촉 조건을 처리하는 데 유연성이 떨어집니다.
• 데이터 생성의 어려움: 행동 복제 (Behavior Cloning) 나 작업 및 운동 계획 (TAMP) 과 같은 고난도 작업을 위한 데이터 생성 시, 신뢰할 수 있는 고품질 해를 얻기 어렵습니다.

2. 제안된 방법론 (Methodology)

저자들은 Hippo라는 새로운 솔버를 제안했습니다. Hippo 는 **내부점 방법 (Interior-Point Method, IPM)**과 투영 기반 (Projection-based) 기법을 결합하여 일반화된 제약 조건 최적화 문제를 해결합니다.

핵심 알고리즘 및 기술

1. 규제된 내부점 방법 (Regularized IPM):

   • 부등식 제약 조건을 슬랙 변수 (slack variables) 를 도입하여 등식 제약으로 변환하고, KKT 조건을 완화합니다.
   • 적응형 장벽 업데이트 (Adaptive Barrier Update): Mehrotra 예측 - 수정자 (MP-C) 전략을 기반으로 장벽 파라미터 ($\mu$) 를 적응적으로 조정합니다.
   • 규제 (Regularization): 장벽 파라미터가 0 에 가까워질 때 발생하는 수치적 불안정성을 방지하기 위해 다중자 (multiplier) 규제 파라미터 ($\rho$) 를 도입하여 헤시안 행렬의 수정을 제한합니다.

2. 투영 기반 리카티 재귀 (Projection-based Riccati Recursion):

   • 등식 제약 조건 (동역학, 접촉 조건 등) 을 처리하기 위해 영공간 (Null-space) 투영 기법을 사용합니다.
   • 제약 조건의 자코비안 행렬이 랭크 결손 (rank-deficient) 일 경우에도 안정적으로 해를 구할 수 있도록 설계되었습니다.
   • 이 기법을 통해 KKT 시스템의 희소성 (sparsity) 을 유지하면서 병렬 계산이 가능해집니다.

3. 제약 조건 처리 전략:

   • 부등식 제약: IPM 을 사용하여 처리하며, 슬랙 변수와 다중자를 동시에 업데이트합니다.
   • 등식 제약:
     • 일반적인 경우: 투영 기반 기법을 사용하여 직접 처리 (가장 효율적).
     • 랭크 결손이 심하거나 수치적 문제가 예상되는 경우: IPM 을 사용하여 박스 제약 (box constraints) 으로 변환하여 처리 (Hippo(i) 모드).
   • 전역화 (Globalization): 실패 시 탈출을 위한 고정 크기 백트래킹 라인 서치 (Fixed-size Backtracking Line Search) 와 초기화 전략을 포함합니다.

4. 구현:

   • C++ 기반 (Eigen, BLASFEO 라이브러리 사용).
   • CasADi 및 Pinocchio 를 통한 자동 미분 및 코드 생성 파이프라인 지원.

3. 주요 기여 (Key Contributions)

• Hippo 솔버 개발: 내부점 방법과 투영 기반 SQP 를 결합한 간결하면서도 고성능의 솔버를 구현했습니다.
• 강건한 수렴성: 랭크 결손 제약 조건이나 복잡한 접촉 동역학이 포함된 어려운 문제에서도 IPM 의 다항식 수렴 복잡도와 투영 기법의 효율성을 결합하여 안정적인 수렴을 보장합니다.
• 파라미터 튜닝 최소화: 복잡한 솔버 파라미터를 수동으로 조정할 필요가 없으며, 체계적인 적응형 장벽 업데이트 전략을 통해 다양한 문제에 적용 가능합니다.
• 일반성: 암시적 동역학, 크로스 타임스텝 상태 제약 등 일반적인 최적 제어 문제 (OCP) 형식을 지원합니다.

4. 실험 결과 (Results)

저자들은 UR5 로봇 도달 문제와 Go2 4 발 보행 로봇의 2 단계 보행 (locomotion) 문제를 벤치마크로 사용하여 Hippo 를 기존 최첨단 솔버 (fatrop, acados, aligator, mim solver) 와 비교했습니다.

• UR5 도달 (Rank-deficient 제약 조건 테스트):

  • Hippo(i) 는 랭크 결손이 있는 등식 제약 조건을 처리할 때 가장 많은 문제를 성공적으로 해결했습니다.
  • acados 는 국소 비실현 가능 최소점 (local infeasible minima) 에 갇히는 경향이 있었으며, aligator 와 mim solver 는 더 많은 반복 횟수가 필요했습니다.
  • Hippo 는 QP 서브문제를 정확히 최소화하지 않아도 되므로 전체 반복 횟수가 적어 전체 실행 시간이 우수했습니다.

• Go2 보행 (다중 접촉 및 간헐적 접촉 테스트):

  • 복잡한 제약 조건 (Full settings): Hippo 와 Hippo(i) 는 fatrop 과 유사한 강건성을 보이면서 가장 빠른 속도를 기록했습니다.
  • 간소화된 제약 조건 (Reduced settings): 페널티 기반 접근법 (acados 등) 은 퇴화 (degeneracy) 문제로 인해 실패하거나 성능이 급격히 떨어졌습니다. 반면, Hippo 는 체계적인 전역화 전략 덕분에 대부분의 문제를 해결했습니다.
  • ALM 기반 솔버 (aligator, mim solver): 등식 제약 조건이 포함된 'Full' 설정에서 모든 테스트에 실패하거나 매우 낮은 성공률을 보였습니다. 이는 IPM 이 ALM 보다 부등식 및 등식 제약이 혼합된 문제에서 더 우월함을 입증합니다.

5. 의의 및 결론 (Significance & Conclusion)

• 로봇 제어의 새로운 표준: Hippo 는 기존 솔버들이 해결하기 어려웠던 복잡한 제약 조건 (특히 랭크 결손 및 접촉 조건) 을 가진 궤적 최적화 문제를 효율적이고 강건하게 해결할 수 있음을 입증했습니다.
• 데이터 생성 및 계획에의 활용: 행동 복제 (IL) 를 위한 고품질 데이터 생성이나 최적화 기반 TAMP (Task and Motion Planning) 와 같은 고난도 응용 분야에서 신뢰할 수 있는 도구로 활용될 수 있습니다.
• 향후 과제: IPOPT 와 같은 강력한 전역화 전략 (feasibility restoration, filter line search) 을 추가하여 더욱 견고한 솔버로 발전시킬 수 있는 여지가 있습니다.

요약하자면, Hippo는 계산 효율성과 수치적 강건성을 동시에 확보하기 위해 내부점 방법과 투영 기법을 혁신적으로 결합한 차세대 궤적 최적화 솔버입니다.