Line-Search Filter Differential Dynamic Programming for Optimal Control with Nonlinear Equality Constraints

기술 요약: 비선형 등식 제약 조건이 있는 최적 제어를 위한 FilterDDP

문제 정의
본 논문은 비선형 등식 제약 조건이 포함된 이산 시간 최적 제어 문제(OCP)를 다룹니다. 이러한 문제는 로봇 공학의 모션 플래닝, 역역학(inverse dynamics), 접촉 암시적 궤적 최적화(예: 보행 로봇, 조작)와 같은 작업에서 흔히 나타납니다. 구체적인 OCP 정식화는 초기 상태 조건, 시스템 역학, 그리고 비선형 등식 제약 조건 $c(x_t, u_t) = 0$을 준수하면서 누적 비용 함수를 최소화합니다. 미분 동적 계획법(DDP)은 제약이 없는 문제에는 효율적이지만, 비선형 등식 제약을 견고하게 처리하도록 확장하는 것은 아직 충분히 탐구되지 않은 영역입니다. 기존 방식들은 종종 증강 라그랑주(Augmented Lagrangian, AL) 방법이나 메리트 함수(merit function)에 의존하며, 이는 제한된 형식적 수렴 보장이나 수치적 불안정성을 초상할 수 있습니다.

방법론: FilterDDP
저자들은 일반적인 비선형 프로그래밍 솔버인 IPOPT에서 사용되는 접근 방식과 유사한 스텝 필터 메커니즘을 DDP 프레임워크에 통합한 라인 서치 필터 알고리즘인 FilterDDP를 제안합니다. 이 알고리즘은 역방향 패스(backward pass)와 순방향 패스(forward pass)를 교대로 수행합니다:

1. 역방향 패스 (Backward Pass): 알고리즘은 부최적 가치 함수(sub-optimal value function)의 1차 및 섭동된 2차 미분값을 계산합니다. 이후 라그랑주 함수의 정지 조건(stationarity conditions)에 **섭동된 뉴턴 단계(perturbed Newton step)**를 적용합니다. 핵심 혁신은 KKT 행렬에 섭동 항($\delta_w I$ 및 $-\delta_c I$)을 도입하여 행렬이 특정 관성(양, 음, 영의 고윳값)을 갖도록 함으로써, 비특이성(non-singularity)과 안정성을 보장하는 것입니다.
2. 순방향 패스 (Forward Pass): 백트래킹 라인 서치를 사용하여 시도 궤적(trial trajectory)을 생성합니다. 스텝 크기 $\gamma$는 필터 기준에 따라 조정됩니다.
3. 필터 기준 (Filter Criteria): 전통적인 메리트 함수 접근 방식과 달리, FilterDDP는 두 가지 양을 기반으로 한 필터를 사용합니다:
   • 제약 위반 ($\theta$): 제약 위반의 $L_1$ 노름(norm) 합계.
   • 라그랑주 ($L$): 원시 비용 함수가 아닌 라그랑주 함수의 값.
     시도 지점은 제약 위반 또는 라그랑주 값이 충분히 감소하는 경우 수락되지만, 필터에 의해 정의된 "금기(taboo)" 영역에 들어가지 않아야 합니다.

핵심 설계 선택 및 이론적 기여
본 논문은 수치적 성능을 향상시키는 두 가지 결정적인 설계 선택 사항을 식별하고 엄격하게 정당화합니다:

1. 스텝 수락 시 비용 함수 대신 라그랑주 사용: 저자들은 스텝 수락 기준에서 비용 함수를 라그랑주로 대체했습니다. 그들은 라그랑주의 충분한 감소 조건이 무제약 최적화에서의 아르미호(Armijo) 조건과 유사함을 증명했습니다. 이 선택은 라그랑주의 방향 도함수가 알고리즘에서 사용되는 탐색 방향과 일치한다는 형식적 증명에 의해 뒷받침됩니다.
2. 섭동된 헤시안 및 쌍대 변수: 역방향 패스에서 알고리즘은 섭동된 헤시안을 사용하며, 가치 함수 기울기를 원시 가치 함수 기울기가 아닌 역학 제약의 추정된 쌍대 변수(dual variable)를 사용하여 업데이트합니다.
   • 국소 이차 수렴 (Local Quadratic Convergence): 저자들은 해의 근방 내에서 FilterDDP의 국소 이차 수렴성을 엄격하게 증명했습니다. 이는 기존의 무제약 DDP(스칼라 상태/제어)에 대한 증명을 제약이 있는 벡터 값 설정으로 일반화한 것입니다. 이 증명은 최적점이 알고리즘의 고정점이며, 해에 충분히 가까워질 때 반복 횟수가 이차적으로 수렴함을 보여주는 것에 기초합니다.
3. 프라이멀-듀얼 확장: 본 논문은 프라이멀-듀얼 내부 점(interior point) 프레임워크를 사용하여 부등식 제약을 처리하는 확장을 제시합니다. 이는 부등식 제약에 대한 쌍대 변수를 도입하고 섭동된 상보성(complementarity) 조건을 가진 일련의 장벽(barrier) 하위 문제를 해결하는 과정을 포함합니다.

실험 결과
FilterDDP는 로봇 공학에서 발생하는 세 가지 도전적인 접촉 암시적 궤적 최적화 문제에 대해 검증되었습니다:

1. 쿨롱 마찰이 있는 카트-폴 스윙업(Cart-pole swing-up).
2. 하드 조인트 리밋이 있는 아크로봇(Acrobot) 스윙업.
3. 장애물 회피가 포함된 비파지적 푸싱(Non-prehensile pushing, 조작).

알고리즘은 다음 모델들과 비교되었습니다:

• IPOPT: 최첨단 일반 비선형 프로그래밍 솔버.
• IPOPT (B): IPOPT의 L-BFGS 변형 버전.
• ProxDDP: 기존의 AL 기반 DDP 알고리즘.

결과:

• 강건성 (Robustness): FilterDDP는 1차 방법(ProxDDP 및 IPOPT (B))에 비해 현저히 높은 강건성을 보여주었습니다. 특히, ProxDDP와 IPOPT (B)는 아크로봇 작업을 완전히 해결하지 못하고 실행 불가능하거나 퇴화된 솔루션을 산출했습니다.
• 효율성 (Efficiency): FilterDDP는 IPOPT보다 적은 반복 횟수와 현저히 낮은 실제 실행 시간(wall-clock time) 내에 수렴을 달야냈습니다. 세 가지 작업 전반에 걸쳐 FilterDDP의 평균 실제 실행 시간은 IPOPT 시간의 약 1027%, IPOPT (B) 시간의 약 15%였습니다.
• 수렴성 (Convergence): 경험적 결과는 국소 이차 수렴을 확인하여 이론적 분석을 검증했습니다.
• 절제 연구 (Ablation Study): 제안된 설계 선택 사항(비용 대신 라그랑주 사용, 또는 섭동되지 않은 헤시안 사용)을 제거했을 때 반복 횟수가 증가하고 실패율이 높아졌으며, 이는 이러한 수정 사항의 필요성을 확인해 주었습니다.

의의 및 주장
본 논문은 FilterDDP가 로봇 공학의 등식 제약 OCP를 해결하기 위한 강력하고 효율적인 대안을 제공한다고 주장합니다. 증강 라그랑주 접근 방식에서 벗어나 라인 서치 필터 프레임워크와 특정 이론적 수정 사항을 채택함으로써, 저자들은 더 강력한 수렴 특성과 더 나은 수치적 성능을 달성했습니다. 이 연구는 DDP의 효율성과 복잡한 제약 로봇 작업에 필요한 강건성 사이의 간극을 메우며, IPOPT와 같은 범용 솔버보다 빠르면서도 대등하거나 우수한 강건성을 유지하는 솔버를 제공합니다. 저자들은 향후 연구가 고차원 보행 로봇 이동에 FilterDDP를 적용하고 전역 수렴성을 공식적으로 확립하는 데 집중될 것이라고 언급했습니다.