Differential dynamic programming

• 다른 이름: DDP
• 카테고리: Planning & manipulation › Trajectory optimisation
• 태그: trajectory-optimization, optimal-control, model-predictive-control, numerical-optimization, shooting-methods

현재 궤적을 따라 잔여 비용(cost-to-go)의 국소 2차 모델을 사용해, 역방향 패스와 순방향 패스를 반복하며 제어 입력 시퀀스를 개선하는 궤적 최적화 방법.

정의

미분 동적 계획법(Differential dynamic programming, DDP)은 궤적 최적화 알고리즘이다. 동역학 모델, 상태와 제어 입력에 대한 비용, 초기 상태가 주어지면 전체 비용을 국소적으로 최소화하는 제어 입력 시퀀스를 찾는다. 1966년 David Mayne이 처음 제시했고, 1970년 Jacobson과 Mayne의 같은 제목의 책에서 더 발전되었다. DDP는 슈팅(shooting) 방법이다. 결정 변수는 제어 입력이며, 고전적 형태에서는 상태를 항상 동역학을 앞으로 시뮬레이션해 얻으므로 모든 반복값이 동역학적으로 실현 가능한 궤적이다.

각 반복은 두 개의 패스로 이루어진다. 역방향 패스는 마지막 시간 단계에서 시작해 처음 쪽으로 진행하며 Bellman의 최적성 원리를 국소적으로 적용한다. 동역학과 비용의 1차·2차 도함수로부터 현재 궤적 주위에서 잔여 비용(cost-to-go)의 2차 근사를 만들고, 매 단계마다 피드포워드 항 k와 피드백 이득 행렬 K로 이루어진 아핀 제어 업데이트를 푼다. 그다음 순방향 패스는 업데이트된 제어 입력 u = ū + αk + K(x − x̄)로 시스템을 시뮬레이션하는데, 여기서 α는 선 탐색(line search) 스텝 크기이다. 전개에 동역학의 2차 항이 포함되므로 DDP는 Newton 방법처럼 국소 최솟값 근처에서 2차 수렴하며, 반복당 계산량은 호라이즌 길이에 선형으로만 증가한다.

동역학의 2차 도함수는 계산 비용이 크기 때문에, 가장 널리 쓰이는 변형인 반복 선형 2차 레귤레이터(iterative linear quadratic regulator, iLQR)는 이를 버리고 동역학의 1차 모델, 즉 Gauss-Newton 근사를 유지한다. 실용적인 솔버는 역방향 패스를 정규화해 조건수를 양호하게 유지하고, 이 방법을 제어 입력 한계(control-limited DDP), 일반 제약(ALTRO 같은 증강 라그랑주 방법), 실현 불가능한 초기 추정(Crocoddyl의 feasibility-driven DDP), 그리고 Parameterized DDP에서처럼 제어 입력과 함께 최적화되는 시불변 파라미터로 확장한다. DDP는 국소 최적해만 찾으므로 결과는 초기 추정에 달려 있다. 유용한 부산물은 피드백 이득의 집합으로, 이를 이용해 최적화된 궤적 주위에서 로봇을 안정화할 수 있다.

중요한 이유

DDP와 iLQR은 로봇 궤적 최적화와 비선형 모델 예측 제어에 가장 많이 쓰이는 솔버에 속한다. 문제의 시간 구조를 활용하고, 호라이즌 길이에 선형으로 확장되며, 궤적과 함께 국소 피드백 정책을 반환한다. 그래서 보행 로봇, 휴머노이드, 드론이 이를 탑재된 컴퓨터에서 실시간으로 실행한다.

주요 응용

• 보행 로봇과 휴머노이드를 위한 비선형 모델 예측 제어
• 드론과 민첩한 이동체를 위한 궤적 최적화
• 로봇 암을 위한 토크 수준 모션 계획
• 부족구동 시스템의 스윙업과 균형 유지
• 궤적과 모델 또는 설계 파라미터의 공동 최적화

실제 사례

사족 보행 로봇을 위한 전신 모델 예측 제어를 구축하는 팀이 Crocoddyl에서 문제를 정식화한다. 접촉 시퀀스는 고정된 보행 스케줄에서 나오므로 각 단계의 접촉은 알려져 있으며, 비용은 몸체 추종, 발 배치, 제어 노력, 그리고 접촉력을 마찰 원뿔 안에 유지하는 페널티를 결합한다. 매 제어 주기마다 솔버는 한 단계 이동한 이전 해로 웜 스타트하고 한 번 또는 몇 번의 반복만 실행한다. 첫 번째 제어 입력과 그 피드백 이득은 저수준 관절 제어기로 보내지며, 저수준 제어기는 이 이득을 사용해 솔버 업데이트 사이의 상태 변화를 보정한다. 튜닝 노력의 대부분은 비용 가중치, 정규화, 그리고 앞을 내다보는 범위와 풀이 시간을 맞바꾸는 호라이즌 길이에 들어간다.

흔한 오해

• DDP는 전역 최적 궤적을 찾는다 — DDP는 국소적 방법이다. 결과는 초기 추정에 달려 있으며 좋지 않은 국소 최솟값일 수 있다
• iLQR과 DDP는 같은 알고리즘이다 — iLQR은 2차 동역학 항을 생략하므로 반복 비용이 훨씬 싸지만, 해 근처에서 수렴이 더 느리다
• DDP는 제약을 다룰 수 없다 — 기본 알고리즘은 비제약이지만, 제어 입력 한계 변형과 증강 라그랑주 변형이 널리 쓰인다
• DDP는 전체 상태 공간에 대한 동적 계획법이다 — DDP는 Bellman 재귀를 하나의 궤적을 따라서만 적용하므로 차원의 저주를 피하지만 국소적 결과만 준다

알아야 할 사람

• 보행 로봇과 드론을 위한 모델 예측 제어기를 구축하는 제어 엔지니어
• 궤적 최적화 연구자
• 휴머노이드 및 전신 제어 개발자
• 최적 제어를 공부하는 로보틱스 학생

관련 기술

• iLQR
• Crocoddyl
• ALTRO
• Riccati 재귀(Riccati Recursion)
• 슈팅 방법(Shooting Methods)

관련 용어

• Direct Collocation
• Model Predictive Control
• Trajectory Planning
• Moving horizon estimation
• Underactuated system
• Hybrid system

관련 프로젝트

• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• MuJoCo MPC: DeepMind's interactive real-time model predictive control framework for MuJoCo
• python_simple_mppi: MPPI control derived and implemented in numpy, with four worked examples
• mjbatch: Runs thousands of MuJoCo simulations in parallel on the CPU
• Quadruped-PyMPC: Python MPC framework for quadruped locomotion with gradient and sampling control
• STLCG: JAX toolbox for differentiable Signal Temporal Logic robustness