💻 computer science

TurboADMM: A Structure-Exploiting Parallel Solver for Multi-Agent Trajectory Optimization

이 논문은 밀집된 상호작용을 가진 다중 에이전트 궤적 최적화 문제의 확장성 한계를 극복하기 위해, ADMM 분해, 리카티 워밍스트, 그리고 qpOASES 기반의 파라메트릭 QP 핫스트를 통합하여 에이전트 수에 대해 거의 선형 복잡도를 달성하는 병렬 솔버 'TurboADMM'을 제안합니다.

원저자: Yucheng Chen

게시일 2026-02-19

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yucheng Chen

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 **여러 대의 로봇이나 자율주행차가 빽빽하게 모여 있을 때, 서로 충돌하지 않으면서도 가장 효율적으로 목적지까지 가는 길을 찾아주는 '초고속 지능'**을 개발한 이야기입니다.

기존의 방법들은 로봇이 2~3 대일 때는 잘 작동했지만, 로봇이 10 대, 20 대가 되면 계산량이 너무 많아져서 "계산 중입니다..."라고 멈춰버리는 문제가 있었습니다. 이 논문은 TurboADMM이라는 새로운 프로그램을 만들어 이 문제를 해결했습니다.

이 복잡한 기술을 누구나 이해할 수 있도록 비유를 들어 설명해 드리겠습니다.

1. 문제 상황: "혼잡한 교차로"와 "계산 마비"

상상해 보세요. 14 대의 자율주행차가 좁은 교차로에서 서로 마주보고 있습니다. 각 차는 "내가 어디로 가야 하지? 다른 차는 어디로 가나? 서로 부딪히지 않으려면 어떻게 해야 하지?"를 실시간으로 계산해야 합니다.

기존 방식 (OSQP, MOSEK 등): 모든 차를 하나의 거대한 팀으로 묶어서 한 번에 계산합니다. 마치 14 명이 모두 한 테이블에 앉아 서로의 의견을 모두 조율해야만 결정을 내리는 것과 같습니다. 사람이 적을 때는 괜찮지만, 사람이 14 명으로 늘어나면 대화 (계산) 시간이 기하급수적으로 늘어나서 실용성이 떨어집니다.
기존의 다른 시도 (HPIPM): 시간의 흐름을 잘 이용하는 똑똑한 방법이지만, 차들이 서로 너무 밀접하게 얽혀 있을 때는 오히려 계산이 꼬여서 "계산 불가"라고 포기해 버립니다.

2. TurboADMM 의 해결책: "3 단계 슈퍼 전략"

TurboADMM 은 이 문제를 해결하기 위해 세 가지 마법 같은 기술을 섞어서 사용합니다.

① "각자 일하기" (ADMM 분해)

가장 먼저, 모든 차를 개별적으로 일하게 만듭니다.

비유: 14 명이 한 테이블에 앉아 고민하는 대신, 14 명 모두 각자 책상으로 가서 자신의 길을 먼저 계산하게 합니다.
장점: 각자 계산하므로 컴퓨터가 여러 코어를 가진 경우, 14 명이 동시에 일할 수 있어 속도가 빨라집니다.
단점: 서로의 위치를 조정해야 하므로, "내 길이 너랑 겹치네? 다시 계산해"라는 조율 과정이 여러 번 반복되어야 합니다. 이 조율 과정이 너무 길어질 수 있습니다.

② "예측 능력" (Riccati Warmstart)

각자가 계산을 시작할 때, 아무것도 모른 채 (Cold Start) 시작하는 대신, 이미 경험과 논리로 미리 대략적인 답을 유추해서 시작합니다.

비유: 시험을 볼 때, 문제를 보고 "아, 이건 저번에 풀었던 문제랑 비슷하네, 답은 대략 이쪽일 거야"라고 미리 답안지를 대충 채워놓고 시작하는 것입니다.
효과: 처음부터 0 부터 시작하는 것보다 훨씬 빠르게 정답에 도달합니다. 특히 첫 번째 조율 단계에서 엄청난 시간을 아껴줍니다.

③ "기억력 활용" (Hotstart)

한 번 계산한 내용을 다음 계산에 그대로 활용합니다.

비유: 14 명이 서로 조율할 때, 1 번째 조율에서 "A 차는 오른쪽으로 가자"라고 합의했다면, 2 번째 조율에서는 "아, A 차는 오른쪽으로 가는 게 맞았지"라고 이전 결과를 기억하고 바로 다음 단계로 넘어갑니다.
효과: 매번 처음부터 다시 계산할 필요가 없어져서, 조율 과정이 반복될수록 속도가 기하급수적으로 빨라집니다.

3. 시너지 효과: "1+1+1 = 100"

이 세 가지 기술을 따로 쓰면 효과가 있지만, TurboADMM은 이들을 하나로 합쳤습니다.

결과: 14 대의 로봇이 복잡한 교차로를 통과할 때, 기존 프로그램 (OSQP, MOSEK) 은 2 초 이상 걸리거나 아예 실패했지만, TurboADMM 은 0.1 초 (96ms) 만에 해결했습니다.
속도 차이: 기존 방법보다 최대 23 배나 빠릅니다. 마치 걸어서 가는 대신 제트기를 탄 것과 같은 차이입니다.

4. 왜 중요한가요?

이 기술은 단순히 "빠르다"는 것을 넘어, 실시간 안전을 보장합니다.

실제 적용: 창고에서 수백 대의 로봇이 물건을 나르거나, 도시에서 자율주행차들이 서로 밀집해서 주행할 때, 이 기술이 없으면 로봇들이 서로 기다리느라 멈춰 서거나 (Deadlock), 충돌할 위험이 큽니다.
TurboADMM은 이 모든 계산을 일반 컴퓨터 (단일 서버) 에서도 실시간으로 처리할 수 있게 해주어, 로봇이 더 똑똑하고 빠르게 움직일 수 있게 합니다.

요약

TurboADMM은 "여러 대의 로봇이 서로 부딪히지 않게 길을 찾는 문제"를 해결하기 위해,

각자 일하게 하고 (분산),
미리 대략적인 답을 유추해서 시작하며 (예측),
이전 결과를 기억해서 반복 계산을 줄이는 (기억)
3 중 전략을 통해, 기존 기술보다 20 배 이상 빠른 속도로 안전한 경로를 찾아주는 혁신적인 소프트웨어입니다.

이제 로봇들은 더 이상 "계산 중"이라고 멈추지 않고, 마치 프로 스포츠 선수들처럼 서로를 의식하며 유려하게 움직일 수 있게 되었습니다.

TurboADMM: 다중 에이전트 궤적 최적화를 위한 구조 활용 병렬 솔버 기술 요약

본 논문은 TurboADMM이라는 새로운 단일 머신 (single-machine) QP(Quadratic Programming) 솔버를 제안합니다. 이는 밀집된 상호작용 네트워크를 가진 다중 에이전트 궤적 최적화 문제를 해결하기 위해 설계되었으며, 기존 솔버들의 한계를 극복하고 실시간 성능을 달성합니다.

1. 문제 정의 (Problem)

다중 에이전트 궤적 최적화 (예: 자율 주행 차량, 로봇 군집) 는 제어 주파수 내에서 대규모 결합된 QP 를 해결해야 합니다. 그러나 기존 접근법들은 다음과 같은 한계가 있습니다:

일반 목적 솔버 (OSQP, MOSEK): 문제를 단일 블록 (monolithic) 으로 처리하여 에이전트 수가 증가함에 따라 계산 비용이 급격히 증가합니다 (확장성 부족).
구조 활용 솔버 (HPIPM): 단일 에이전트 MPC 에서는 리카티 (Riccati) 재귀를 통해 시간적 구조를 활용하여 우수하지만, 에이전트 간의 밀집된 결합 제약 (collision avoidance) 이 존재할 경우 수렴에 실패하거나 성능이 급격히 저하됩니다.
기존 분산 방법: ADMM 기반 방법들은 병렬화가 가능하지만, 수렴을 위해 많은 반복 횟수가 필요하여 전체 계산 시간이 길어지는 경향이 있습니다.

2. 방법론 (Methodology)

TurboADMM 은 세 가지 상보적인 구성 요소를 체계적으로 통합하여 설계되었습니다. 이는 단일 머신 환경 (멀티 코어 CPU) 에서 OpenMP 를 통해 병렬 실행됩니다.

2.1. ADMM 분해 (ADMM Decomposition)

글로벌 문제를 에이전트별 하위 문제로 분해하여 병렬로 해결합니다.
밀집된 결합 제약 (모든 에이전트 쌍 간의 충돌 회피) 을 고려하더라도, 에이전트별 하위 문제는 블록 대각 행렬 (block-diagonal) 구조를 유지하며, 결합은 듀얼 변수 (dual variables) 를 통해 조정됩니다.

2.2. 리카티 웜스타트 (Riccati Warmstart)

핵심 아이디어: 각 ADMM 반복의 첫 번째 QP 풀이 시, 단순한 영 (zero) 초기화 대신 **리카티 재귀 (Riccati recursion)**를 사용하여 고품질의 프라임 - 듀얼 (primal-dual) 초기값을 제공합니다.
작동 원리: 제약 조건을 무시한 비제약 아핀 LQR 문제를 풀어 에이전트의 동역학 구조를 정확히 반영하는 궤적을 생성합니다. 이를 qpOASES 솔버의 초기값으로 사용하여, 솔버가 최적 해를 찾는 데 필요한 활성 집합 (active-set) 반복 횟수를 획기적으로 줄입니다.

2.3. 파라메트릭 QP 핫스타트 (Parametric QP Hotstart)

핵심 아이디어: 연속된 ADMM 반복들에서 생성되는 QP 인스턴스는 서로 매우 유사합니다.
작동 원리: qpOASES 의 핫스타트 메커니즘을 활용하여, 이전 ADMM 반복에서 계산된 KKT 시스템의 QR 분해 (factorization) 와 활성 집합 정보를 재사용합니다. 이는 반복이 진행될수록 QP 풀이 비용을 극도로 낮춥니다.

시너지 효과:

리카티 웜스타트: 첫 번째 ADMM 반복의 비효율적인 QP 풀이를 방지.
핫스타트: 후속 반복들의 QP 풀이 비용을 최소화.
ADMM 병렬화: 에이전트별 계산을 동시 실행.

3. 주요 기여 (Key Contributions)

시너지 솔버 아키텍처: ADMM 분해, 리카티 기반 보조 QP 초기화, 파라메트릭 QP 핫스타트를 통합한 고유한 아키텍처를 제안했습니다.
성능 비교: 기존 SOTA 솔버 (OSQP, MOSEK, HPIPM) 와의 비교를 통해 속도와 견고성 (robustness) 을 입증했습니다.
실증적 검증 및 오픈소스: 2~14 에이전트 환경에서 체계적인 확장성 분석을 수행하고, GitHub 에서 C++ 라이브러리를 오픈소스로 공개하여 다중 에이전트 MPC 애플리케이션에 바로 사용할 수 있도록 했습니다.

4. 실험 결과 (Results)

실험은 2~14 개의 에이전트가 20 단계 예측 구간 (horizon) 에서 충돌 회피를 수행하는 벤치마크를 기반으로 수행되었습니다.

속도 향상:
- OSQP 대비: 6.7 배 ~ 14.8 배 빠른 속도.
- MOSEK 대비: 13.1 배 ~ 23.1 배 빠른 속도.
- 확장성: 에이전트 수가 증가함에 따라 TurboADMM 은 $O(N^{1.2})$ 에 가까운 선형 확장성을 보인 반면, OSQP 와 MOSEK 는 $O(N^{2.5})$ 의 초선형 (super-linear) 확장성을 보여 에이전트 수가 많아질수록 성능 격차가 커졌습니다.
성능 비교 (14 에이전트 기준):
- TurboADMM: 96ms (실시간 제어 가능).
- OSQP: 1,421ms.
- MOSEK: 2,118ms.
- HPIPM: 4 에이전트 이상에서는 수렴에 실패 (Convergence Failure).
Ablation Study (구성 요소 분석):
- BaseADMM (웜스타트/핫스타트 없음): 14 에이전트 기준 14.3 초 소요.
- HotstartADMM (핫스타트만 적용): 121ms 로 단축.
- TurboADMM (전체 적용): 96ms 로 최종 최적화.
- 이는 리카티 웜스타트와 핫스타트가 서로 다른 단계에서 시너지 효과를 발휘함을 보여줍니다.
정확도:
- 소규모 문제 (2~4 에이전트) 에서 리카티 웜스타트 덕분에 OSQP/MOSEK 대비 약 10 배 낮은 궤적 추적 오차를 보였습니다.
- 대규모 문제에서도 MOSEK 와 유사한 정확도를 유지하면서 훨씬 빠른 속도를 달성했습니다.

5. 의의 및 결론 (Significance)

TurboADMM 은 단일 머신 환경에서 다중 에이전트 MPC 문제를 해결하는 새로운 표준을 제시합니다.

실시간성 달성: 표준 하드웨어 (멀티 코어 CPU) 에서 10~204Hz 의 제어 주파수를 달성하여, 도시 환경의 자율 주행이나 창고 로봇 군집 관리와 같은 실시간 응용 분야에 직접 적용 가능합니다.
밀집 결합 문제 해결: 에이전트 간의 밀집된 상호작용 (all-pairs coupling) 이 존재하는 상황에서도 HPIPM 이 실패하는 문제를 성공적으로 해결합니다.
실용성: 경량 C++ 라이브러리로 제공되어 연구 및 생산 환경 모두에서 활용 가능합니다.

결론적으로, TurboADMM 은 문제의 구조적 특성 (시간적 구조, 에이전트 분해, 반복 간 유사성) 을 통합적으로 활용함으로써 기존 솔버들의 확장성 한계를 극복하고, 다중 에이전트 궤적 최적화의 실시간 실현 가능성을 크게 높였습니다.