Parallel Branch Model Predictive Control on GPUs

기술 요약: GPU 기반의 병렬 분기 모델 예측 제어(Parallel Branch Model Predictive Control)

문제 정의
분기 모델 예측 제어(BMPC)는 자동 운전과 같이 동적인 환경에서 불확실성을 처리하기 위한 강력한 계획 프레임워크이지만, 다양한 불확실성 실현에 대응하는 궤적 트리(trajectory trees)를 생성할 때 발생하는 막대한 계산 부담으로 인해 광범위한 배포가 저해되고 있습니다. 특히 긴 계획 수평선(planning horizons)과 수많은 예측 시나리오를 다룰 때 기존 솔버들은 종종 트리의 구조를 효율적으로 활용하지 못하거나 시간적 병렬성(temporal parallelism)을 달ato하지 못하여, 실시간 애플리케이션에 적합하지 않은 경우가 많습니다. 또한, 트리 구조의 최적 제어 프레임워크 내에서 일반적인 단계별 제약 조건(stage-wise constraints)을 병렬 하드웨어에서 처리하는 것은 여전히 과제로 남아 있습니다.

방법론
저자들은 제약 조건 처리를 위해 증강 라그랑주(Augmented Lagrangian, AL) 방법을 결합한 다중 슈팅(multiple-shooting) 정식화 기반의 GPU 기반 BMPC 솔버를 제안합니다. 이 접근 방식의 핵심은 트리의 희소 구조(tree-sparse structure)를 활용하도록 설계된 두 가지 맞춤형 내부 선형 이차 조절기(LQR) 솔버에 의존합니다:

1. 병렬 트리 LQR 솔버:

   • SLQR (시나리오 레벨 병렬화): 이 솔버는 리프 노드(leaf nodes)에서 루트(root)로 향하는 수정된 리카티 재귀(Riccian recursion)를 수행합니다. 각 단계에서 자식 노드의 가치 함수(value functions)를 집계함으로써, 각 노드에서의 독립적인 최소화 문제를 병렬로 해결할 수 있게 합니다. 이 방식은 GPU 자원을 적게 소모하며 자원이 제한적인 시나리오에 적합합니다.
   • STLQR (시나리오 및 시간적 병렬화): 이 솔버는 병렬 스캔 알고리즘을 활용하여 역방향(Riccati) 및 순방향(rollout) 패스 모두에서 시나리오 레벨과 시간적 병렬성을 동시에 달성합니다. 이는 조건부 가치 함수(Conditional Value Functions, CVFs)와 트리 구조의 결합 규칙을 사용하여 가치 함수와 아핀 제어 법칙(affine control laws)을 $O(\log N)$ 시간 복잡도로 계산합니다. 이 방법은 더 높은 병렬성을 제공하지만 더 많은 GPU 자원을 요구합니다.

2. 증강 라그랑주를 통한 제약 조건 처리:
   일반적인 단계별 제약 조건을 처리하기 위해 저자들은 증강 라그랑주(AL) 방법을 사용합니다. 내부 루프는 제약이 있는 문제를 Powell-Hestenes-Rockafellar(PHR) 페널티 함수를 사용하여 제약이 없는 트리 LQR 문제로 근사하는 반복적 iLQR 방식을 사용합니다. 효율적인 GPU 병렬화를 위해 최적의 섭동(perturbations)을 계산하는 데 선형 롤아웃(linear rollout)이 사용됩니다. 외부 루프는 BCL 규칙을 따라 제약 위반에 따라 라그랑주 승수와 페널티 가중치를 적응적으로 업데이트합니다.

3. 구현:
   솔버는 JAX로 구현되었으며, GPU 가속을 위해 자동 미분 및 XLA 컴파일러를 활용합니다. 이 프레임워크는 단정밀도(FP32) 및 배정밀도(FP64) 산술 연산을 모두 지원합니다.

주요 기여
본 논문은 세 가지 주요 기여를 설명합니다:

1. 이중 병렬 솔버: 문제 크기와 가용 계산 자원에 따라 적절한 방법을 선택할 수 있도록 서로 다른 수준의 병렬성을 제공하는 두 가지 병렬 트리 LQR 솔버(SLQR 및 STLQR)를 개발했습니다.
2. 제약이 있는 비선형 BMPC 솔버: 견고한 제약 조건 처리와 웜 스타트(warm-starting) 능력을 위해 증강 라그랑주 방법을 포함하는 비선형 BMPC 문제를 위한 다중 슈팅 반복 솔버에 이러한 트리 LQR 솔버를 통합했습니다.
3. 벤치마킹 및 오픈 소스: 제안된 솔버를 기존 iLQR 솔버들(TRAJAX, MPX) 및 고성능 CPU 기반 솔버(HPIPM)와 종합적으로 벤치마킹하였으며, 오픈 소스 구현체를 공개했습니다.

수치 결과
저자들은 무제약 트리 LQR 문제와 유니사이클(unicycle) 및 쿼드-펜듈럼(quad-pendulum)의 제약 궤적 계획이라는 두 가지 별개의 작업에 대해 솔버를 평가했습니다.

• Tree LQR 성능: GPU 기반 솔버의 성능은 문제 크기와 하드웨어에 크게 의외됩니다. 작은 문제 규모(예: $Z = 2$ 트리 경로)에서는 GPU 메모리 액세스 지연 및 오버헤드로 인해 STLQR은 5배 이상, SLQR은 20배 이상 느려 NVIDIA RTX 5060 Ti에서 CPU 기반 HPIPM 솔버보다 현저히 느립니다. 그러나 대규모 인스턴스의 경우 성능이 역전되어, SLQR은 RTX 5060 Ti에서 대규모 인스턴스($Z \ge 128$)에 대해 HPIPM보다 최대 2배 빠르게 동작할 수 있습니다. 마찬가지로, RTX 4090과 같은 고성능 GPU에서 STLQR은 중대형 트리 크기($Z \ge 16$)에 대해 HPIPM 대비 최대 1.9배의 속도 향상을 달관합니다.
• 제약 조건 처리: 궤적 계획 작업에서 제안된 솔버(ILQRJAX)는 최첨단 CPU 솔버인 IPOPT와 유사한 수렴 동작을 보이면서도 반복당 계산 시간은 현저히 단축했습니다(예: 유니사이클의 경우 평균 반복 시간을 3.80ms에서 1.87ms로 단축). 이 솔버는 모든 테스트 인스턴스를 성공적으로 처리한 반면, 다른 GPU 기반 솔버들(TRAJAX, MPX)은 정식화의 한계나 적응형 업데이트 체계의 부재로 인해 더 까다로운 인스턴스에서 수렴에 실패하는 등 어려움을 겪었습니다.

의의 및 주장
본 논문은 제안된 접근 방식이 GPU 상의 병렬 알고리즘을 통해 트리 구조를 완전히 활용함으로써 대규모 문제를 위한 실시간 BMPC로 가는 실행 가능한 경로를 제공한다고 주장합니다. 저자들은 트리 구조가 효과적으로 병렬화될 수 있는 대규모 인스턴스에서 제안된 방법이 고성능 CPU 기반 솔버보다 우수한 성능을 달성함을 강조합니다. 다만, 병렬 스캔 기반 솔버는 높은 GPU 자원 요구량을 가지며, 이는 자원이 포화될 경우 확장성을 제한할 수 있고, 작은 문제 규모에서는 여전히 CPU 기반 솔사가 더 나을 수 있음을 인정합니다. 본 연구는 계산 효율성과 제약 및 불확실성에 대한 엄격한 처리를 균형 있게 맞춤으로써 복잡한 실제 응용 분야를 위한 불확실성 인식 계획(uncertainty-aware planning)을 가능하게 하는 단계로 자리매김하고 있습니다. 향-후 과제로 자원 활용을 더욱 최적화하기 위해 CUDA C++로 구현하는 것과, FP32에 최적화된 하드웨어에서 수치적 안정성을 개선하기 위해 혼합 정밀도 산술을 탐색하는 것을 제시하였습니다.