기술 요약: ElastiQP: 제약 조건이 있는 로봇 제어를 위한 항상 실행 가능한 QP 솔버

문제 정의

이차 계획법(Quadratic Programming, QP)은 전신 제어(whole-body control), 안전 필터, 보행 제어 등 모델 기반 로봇 제어의 핵심 요소입니다. 로봇의 성능과 환경의 복잡성이 증가함에 따라, 이러한 QP의 제약 조건 수도 늘어나며, 이는 종종 제약 조건들이 순간적으로 불일치하여 발생하는 '순간적 불능(infeasibility)' 상태로 이어집니다. 표준 QP 솔버들은 이러한 시나리오에서 "infeasible" 상태를 반환하며, 이는 로봇 컨트롤러가 실행 가능한 명령을 생성할 수 없는, 잠재적으로 위험한 상태를 초래합니다.

불능 상태를 처리하는 기존 방식들은 다음과 같은 상당한 트레이드오프를 안고 있습니다:

• Hard Solvers (강성 솔버): 불능 상태 발생 시 아무런 해(solution)를 반환하지 않습니다.
• $\ell_2$ Relaxation (소프트 제약 조건): 위반 사항을 모든 제약 조건에 분산시킴으로써, 충돌 중이지 않은 제약 조건까지 영향을 미쳐 바람직하지 않은 트레이드오프를 유발하고 희소성(sparsity)을 상실하게 합니다.
• Expanded $\ell_1$ Relaxation (확장된 $\ell_1$ 완화): 모든 부등식 제약 조건에 슬랙 변수(slack variable)를 도입합니다. 이 방식은 실행 가능성과 희소성을 보장하지만, 결정 변수(decision vector)의 크기를 크게 확장합니다. ProxQP, PIQP, DAQP와 같은 솔버들의 경우, 이 슬랙 변수들로 인해 인수분해 비용이 지배되어 고주파(1 kHz) 제어에 필요한 엄격한 1 ms 시간 예산을 충족하지 못하는 경우가 빈번합니다.
• 기존 Elastic Solvers (탄성 솔버): qpax와 같은 방법들은 응축된 탄성 모드(condensed elastic modes)를 제공하지만, 강한 등식 제약 조건(hard equality constraints)에 대한 지원이 부족하거나, 고자유도(DoF) 시스템에서 충분한 속도를 내지 못합니다.

방법론

저자들은 마이크로초 단위의 성능을 유지하면서 실행 가능성을 보장하도록 설계된 수정된 dual active-set QP 솔버인 ElastiQP를 소개합니다. 핵심 혁신은 **탄성 슬랙 변수의 해석적 응축(analytical condensation of elastic slack variables)**에 있습니다.

1. Elastic QP 정식화

ElastiQP는 부등식 제약 조건은 정확한 $\ell_1$ 페널티를 사용하여 완화하고, 등식 제약 조건(통상적으로 동역학)은 강하게 유지하는 탄성 QP를 해결합니다:
$$\begin{aligned} \min_{x,t} \quad & \frac{1}{2}x^\top Qx + q^\top x + w^\top t \\ \text{s.t.} \quad & Ax = b \\ & Gx - t \leq h \\ & t \geq 0 \end{aligned}$$
여기서 $t$는 슬랙 변수를 나타냅니다. 결정적으로, $t$에 대한 내부 최소화 문제는 해석적으로($t_i = \max(0, [Gx-h]_i)$) 풀 수 있으며, 이를 통해 $x$에 대한 정확한 $\ell_1$ 페널티 정식화로 축소됩니다.

2. Dual Active-Set Methods에서의 탄성 응축

전통적인 솔버들은 슬랙 $t$를 결정 변수로 취급하여 문제의 크기를 키웁니다. ElastiQP는 $t$를 해석적으로 제거합니다. **Dual Active-Set Methods (ASM)**의 맥락에서, 이 응축은 문제를 단순한 듀얼 제약 조건의 수정으로 변환합니다:

• Bounded Multipliers (유계 승수): 부등식 승수 $z$는 표준적인 비음수 반직선 $[0, \infty)$ 대신 박스 제약 $[0, w]$를 가집니다.
• 세 가지 상태: 알고리즘은 부등식 제약 조건에 대해 세 가지 상태를 관리합니다:
  1. Inactive (비활성): $z_i = 0$ (만족됨).
  2. Active (활성): $0 < z_i < w_i$ (타이트함).
  3. Saturated (포화): $z_i = w_i$ (위반됨, 슬랙 $t_i > 0$).
• 선형 시스템: 이 응축 결과, 선형 시스템은 결정 변수의 개수 $n$에 의한 $n \times n$ 크기가 되며, 이는 부등식 제약 조건의 개수 $p$와 무관합니다. 이를 통해 $p \gg n$인 상황에서도 표준 ASM의 계산 효율성을 유지합니다.

3. 알고리즘 조정

솔버는 표준 dual ASM 반복 과정을 수정합니다:

• Working set 풀(solve)에는 포화된 제약 조건($M_S w_S$)을 고려하는 항이 포함됩니다.
• 업데이트 로직은 "포화된" 상태를 처리하며, 위반된 경우 working set에 제약을 추가하거나, 엄격히 만족되는 경우 제약을 제거합니다.
• 등식 제약 조건은 구조적으로 일관되므로, 탄성 dual ASM은 등식 제약 조건이 일관적인 경우 항상 해를 반환함이 보장됩니다.

주요 기여

1. ElastiQP 솔버: 해석적 슬랙 응축을 구현한 헤더 전용(header-only) C++ 라이브러리(Python/JAX 인터페이스 포함)입니다.
2. 항상 실행 가능한 보장: 부등식에 $\ell_1$ 완화를 사용하고 등식에 강한 제약을 적용함으로써, 솔버는 결코 불능(infeasible)을 반환하지 않으며, 로봇이 항상 제어 명령을 가질 수 있도록 보장합니다.
3. 성능: 슬랙 변수의 해석적 제거를 통해, ElastiQP는 실행 가능한 문제에서 선두적인 솔버들과 대등하거나 더 빠른 속도를 보여주며, 불능 문제에서는 가장 우수한 대안들보다 최대 40배 더 빠르게 동작합니다.
4. 희소성 보존: $\ell_2$ 완화와 달리, $\ell_1$ 구조는 위반 사항이 충돌하는 제약 조건에만 국한되도록 하여 희소성을 보장합니다.

결과

로봇 제어 벤치마크

저자들은 6-DoF 암, 12-DoF 양팔 시스템, 28-DoF 휴머노이드의 세 가지 로봇 제어 시나리오에서 ElastiQP를 평가했습니다.

• Feasible Loops (실행 가능한 루프): ElastiQP는 마이크로초 단위의 해결 시간을 달성하며(예: 28-DoF 휴머노이드 콜드 스타트 시 52 $\mu$s), 1 ms 예산을 여유롭게 충족합니다. 실행 가능한 문제에 대해서는 가장 빠른 강성 솔버인 DAQP와 유사한 성능을 보입니다.
• Infeasible Loops (불능 루프): 불능 문제에서 강성 솔버(DAQP, PIQP, ProxQP)는 실패하거나 불능을 보고하는 데 과도한 시간이 걸립니다. ElastiQP는 마이크로초 내에 최소한의 위반을 가진 해를 반환합니다.
  • 속도: ElastiQP는 휴머노이드 불능 문제에서 차세대 대안(ProxQP sparse backend)보다 최대 40배 빠릅니다.
  • 품질: ElastiQP는 충돌하는 제약 조건(테스트 케이스의 1개 행)만을 위반하는 반면, $\ell_2$ 솔버(DAQP-soft, ProxQP-closest)는 위반 사항을 28~29개 행 전체로 분산시킵니다.
  • 등식 일관성: ElastiQP는 등식 제약 조건(동역학)을 매우 정밀한 허용 오차($10^{-8}$) 내로 유지하는 반면, $\ell_2$ 소프트 모드는 등식 만족도를 크게 저하시킬 수 있습니다.

Maros–Mészáros 벤치마크

광범위한 일반 목적의 악조건(ill-conditioned) 문제 세트에서 평가되었습니다:

• ElastiQP는 우수한 일반 목적 솔버들(작은 문제는 DAQP, 큰 문제는 PIQP)과 경쟁할 만한 성능을 보입니다.
• 탄성 응축은 일반적인 문제의 성능을 저하시키지 않으며, ElastiQP는 다른 솔버들이 수렴에 실패하는 인스턴스들을 해결해 냅니다.
• Elстами 응축된 모드를 제공하는 유일한 다른 솔버인 qpax보다 속도와 신뢰성 모두에서 크게 앞섭니다.

의의 및 주장

본 논문은 로봇 제어의 중요한 간극을 ElastiQP가 해결한다고 주장합니다: 즉, 고주파 제어에 충분히 빠르면서도, 제약 조건 충동이 불가피한 상황에서도 로봇이 명령 없이 방치되지 않도록 견고하게 처리할 수 있는 솔버의 필요성입니다.

• 신뢰성: "항상 실행 가능한" 해를 제공하여, 컨트롤러가 출력을 내놓지 못하는 위험한 상태를 방지합니다.
• 효율성: 슬랙 변수를 해석적으로 응축함으로써, 탄성 정식화와 관련된 계산 비용을 피하고 고자유도 시스템에서도 사용 가능하게 만듭니다.
• 실용성: $\ell_1$ 페널티 구조를 통해 ($\ell_2$ 방식의 확산된 트레이드오프 없이) 계층적 완화(예: 작업 완료보다 안전을 우선시함)가 가능합니다.
• 배포: 저자들은 ElastiQP가 기존의 안전 필터 및 컨트롤러에 즉시 통합될 준비가 되었음을 강조하며, 오픈 소스로 공개되어 있습니다.

저자들은 현재의 초점이 CPU 기반 실시간 제어에 맞춰져 있음을 언급하며, 향후 연구 방향으로 미분 가능성(differentiability), 배치 처리를 위한 GPU 가속, 그리고 전역 역기구학(global IK) 파이프라인의 내부 솔버로서의 활용 등을 제시하며 겸허한 태도를 유지하고 있습니다.