Reachability-Augmented Dual Dynamic Programming for Optimal Path Parameterization

기술 요약: 최적 경로 매개변수화를 위한 도달성 강화 이중 동적 프로그래밍

문제 정의
최적 경로 매개변수화 (OPP) 는 운동동역학적 제약 조건과 작업 의존적 목적 함수 하에서 지정된 기하학적 경로에 대한 최적 시간 매개변수화를 찾는 것을 포함합니다. 시간 최적 경로 매개변수화 (TOPP) 는 이동 시간을 최소화하지만, 그 결과 생성되는 "뱅 - 특이 - 뱅 (bang-singular-bang)" 제어 프로파일은 종종 진동 및 추적 오차를 유발합니다. 일반적인 목적 함수 (예: 에너지, 부드러움) 를 도입하면 이러한 문제를 완화할 수 있지만, 기존 솔버는 다음 네 가지 핵심 요구 사항을 동시에 만족하는 데 어려움을 겪습니다:

1. 실현 가능성: 궤적이 상태 및 혼합 상태 - 제어 제약을 만족함을 보장합니다.
2. 일반 목적 함수 최적성: 시간 외 목적 함수에 대한 최적성 증명을 제공합니다.
3. 효율성: 낮은 지연 시간으로 온라인 운동 생성을 가능하게 합니다.
4. 고차원 능력: 비볼록 저크 (jerk) 제약을 포함하는 3 차 시스템 (OPP3) 을 처리합니다.

현재 방법론들은 트레이드오프에 직면해 있습니다: 수치 적분 (NI) 은 TOPP 에 효율적이지만 일반적인 목적 함수를 지원하지 않으며; 볼록 최적화 (CO) 는 강력한 최적성 보장을 제공하지만 높은 계산 비용으로 고통받습니다; 그리드 기반 동적 프로그래밍 (DP) 은 일반적인 목적 함수를 처리하지만 차원의 저주로 고통받으며 고차 시스템에 대한 전역 최적성 보장이 부족합니다; 도달성 분석 (RA) 은 효율적으로 실현 가능성을 보장하지만 일반적으로 시간 최적 목적 함수로 제한됩니다.

방법론: 도달성 강화 이중 동적 프로그래밍 (RDDP)
본 논문은 RA 의 실현 가능성 보존과 이중 동적 프로그래밍 (DDP) 의 최적성 보장을 통합하는 상태 - 그리드 없는, 목적 함수 인식 동적 프로그래밍 프레임워크인 RDDP 를 제안합니다.

• 핵심 메커니즘: RDDP 는 고전적 DDP 에서 사용되는 "상대적 완전한 재귀 (relatively complete recourse)" 가정을 명시적인 역방향 도달 집합 (BRS) 으로 대체합니다. 고정된 상태 그리드 위에서 가치 함수를 근사하는 대신, RDDP 는 계산된 BRS 내부에서만 가치 함수 절단 (cuts) 과 시험 궤적을 생성합니다.
• 실현 가능성 보존: 종료 집합에서 역방향으로 BRS 를 전파함으로써, 알고리즘은 이러한 집합 내에서 생성된 모든 순방향 궤적이 실현 가능함을 보장합니다. 이는 종종 퇴화된 종료 집합으로 인해 OPP 에서 실패하는 실현 가능성 절단이나 완전한 재귀 가정에 대한 의존성을 제거합니다.
• 가치 함수를 통한 최적성: 이 프레임워크는 연속 상태 공간에서 아핀 최적성 절단 (지지 초평면) 을 사용하여 가치 함수를 근사합니다.
  • 볼록 OPP (COPP) 의 경우: RDDP 는 전역 최적점으로 수렴합니다. 알고리즘은 시험 궤적을 사용하여 가치 함수 근사를 반복적으로 정제하며, 계산 가능한 최적성 간격 (DDP 간격) 을 제공하여 정지 기준으로 삼습니다.
  • 일반 비볼록 OPP (GOPP) 의 경우: RDDP 는 순차적 볼록 프로그래밍 (SCP) 프레임워크 내에 내장됩니다. 비볼록 함수는 분해 (DC 분해) 되어 각 반복 단계에서 볼록화됩니다. 이론적 분석은 RDDP 가 BRS 의 보수적인 다면체 근사 (OPP3 에서 일반적임) 를 사용하더라도 Karush-Kuhn-Tucker (KKT) 해로 수렴함을 증명합니다.
• 효율적인 구현:
  • OPP2: 양방향 전파를 통해 계산된 정확한 구간 도달 집합을 활용합니다.
  • OPP3: 보수적인 다면체 BRS 를 계산하기 위해 두 가지 방법을 사용합니다: 투영 기반 방법 (정확한 집합의 꼭짓점 샘플링) 과 검색 기반 방법 (선형 제약 조건을 따라 접선 방향으로 꼭짓점을 반복적으로 탐색). 후자는 저차원 선형 프로그래밍을 해결함으로써 계산 복잡성을 크게 줄입니다.

주요 기여

1. 새로운 프레임워크: 이는 로봇 OPP 에 DDP 를 적용한 최초의 사례입니다. RDDP 는 명시적 도달성 기반 실현 가능성 보존과 목적 함수 인식 가치 함수 가이드를 독창적으로 결합하여, 기존 방법들이 실현 가능성, 일반 최적성, 효율성을 통합하지 못하는 능력 격차를 해소합니다.
2. 이론적 보장:
   • 볼록 문제의 경우, 전역 최적성 수렴을 증명합니다.
   • 비볼록 문제의 경우, SCP 하에서 KKT 수렴을 확립합니다.
   • 결정적으로, 충분한 실현 가능성 절단이 생성되기 전까지 표준 DDP 구현체에서 종종 결여되었던 모든 순방향 반복에 대한 실현 가능성 보장을 제공합니다.
3. 알고리즘적 효율성: 제안된 상태 - 그리드 없는 접근법은 차원의 저주를 피합니다. 대규모 최적화를 일련의 저차원 부분 문제 (OPP2 의 경우 1 차원, OPP3 의 경우 2 차원/3 차원) 로 분해함으로써 상당한 속도 향상을 달성합니다.

실험 결과
무작위 7 축 경로에서 실험을 수행하여 $n$ 축 경로 ($n$ 최대 100) 로 확장했으며, RDDP 를 RA, 볼록 최적화 (SOCP), 그리드 기반 DP 베이스라인과 비교했습니다.

• 성능: RDDP 는 SOCP 베이스라인 (최적성의 금표준) 과 비교 가능한 목적 함수 값을 달성했으나, OPP2 의 경우 계산 시간을 28.6 배, OPP3 의 경우 5.8 배 단축했습니다.
• RA 와의 비교: RA 기반 방법은 순수 TOPP 에 가장 빠르지만, RDDP 는 더 엄격한 최적성 간격을 유지하며 RA 가 실패하는 일반적인 목적 함수 (예: 시간 - 에너지 트레이드오프) 를 지원합니다.
• 그리드 기반 DP 와의 비교: RDDP 는 더 빠른 수렴과 높은 성공률을 보여주었으며, OPP3 에서 그리드 기반 방법을 괴롭히는 "차원의 저주"를 피했습니다.
• 실제 세계 검증: 7 축 Franka Emika Panda 매니퓰레이터에 대한 사례 연구에서, 시간 - 열적 목적 함수 (GOPP) 를 사용하면 순수 TOPP 에 비해 피드백 가속도의 정규화된 총 변동이 87.7% 감소했으나 이동 시간은 0.15% 만 증가했습니다. 이는 진동 감소를 위한 부드러움 목적 함수의 실용적 이점을 강조합니다.

의의 및 주장
저자들은 RDDP 가 최적 경로 매개변수화에서 근본적인 능력 격차를 해소한다고 주장합니다. 인증 가능한 일반 목적 함수 최적화, 도달성 기반 실현 가능성 보존, 그리고 온라인 호환 저차원 계산을 단일 상태 - 그리드 없는 프레임워크로 통합함으로써 RDDP 는 2 차 및 3 차 시스템 모두에 대해 고품질 실현 가능 궤적을 생성할 수 있게 합니다. 이 방법은 대규모 볼록 최적화에 대한 원칙적인 대안으로 제시되며, 온라인 로봇 응용에 적합한 계산 효율성을 크게 개선하면서도 비교 가능한 최적성을 제공합니다. 논문은 SCP 를 통해 비볼록성을 처리하지만, 전역 최적성 보장은 볼록 부분 문제에 국한되며 비볼록 사례는 KKT 점으로 수렴한다고 명시적으로 지적합니다.