CacheMPC는 보행 로봇의 모델 예측 제어(MPC)를 가속화하기 위해 인증된 캐싱 프레임워크를 도입합니다. 유사한 상태에서 이전에 계산된 해를 재사용하며, 각 질의마다 사후 인증을 통해 실행 가능성과 준최적성 경계를 모두 보장합니다.
MPC 가속화 접근법
명시적 MPC(explicit MPC)는 다중 파라메트릭 QP를 오프라인으로 풀어 최적 제어 법칙을 상태의 구분적 선형 함수(piecewise affine function)로 미리 계산합니다. 온라인 평가는 상태 공간의 폴리헤드랄 분할(polyhedral partition)에서 점 위치 찾기 문제로 축소됩니다. 저차원 시스템에는 효과적이지만, 문제 차원이 증가함에 따라 영역의 수가 기하급수적으로 늘어나 보행 로봇 제어에서 흔한 13-상태 MPC 문제에는 완전 열거 방식이 실용적이지 않습니다. 우리의 프레임워크는 명시적 MPC의 온라인 샘플 기반 변형으로 볼 수 있습니다. 각 캐시 항목은 명시적 법칙의 지역적 선형 조각으로, 제어기가 원래 풀었을 동일한 QP에서 느리게 채워지며, 사후 인증서가 보증할 때만 질의 시점에 수락됩니다.
함수 근사 방법은 상태에서 MPC 해로의 매핑을 지도 학습으로 학습합니다. MPCNET은 MPC 시연 데이터로 신경망을 훈련하고 온라인 추론에 사용합니다. 마찬가지로 반복 학습 제어(ILC) 접근법은 궤적 단계별로 색인된 제어 동작 라이브러리를 유지하여 최적화 대신 조회를 통해 더 빠른 실행을 달성합니다. 이러한 방법은 오프라인 훈련이나 별도의 최적화 단계가 필요하며, 변화하는 환경에 온라인으로 적응하기 어렵습니다.
TinyMPC는 ADMM 솔버 내에서 행렬 분해를 미리 계산하고 캐싱하여 실행 시간에 비용이 많이 드는 연산을 피함으로써 속도 향상을 이룹니다. 고정된 구조의 볼록 문제에는 효과적이지만, 유사한 상태 간의 전체 MPC 해 재사용이라는 더 넓은 문제를 다루지는 않습니다.
웜 스타팅(warm-starting)은 널리 사용되는 기술로, 이전 시간 단계의 해로 현재 문제의 솔버를 초기화합니다. 반복 횟수를 줄이는 데 효과적이지만, MPC 업데이트 사이에 상태가 크게 변할 때는 효과가 감소하며, 여전히 솔버를 완료까지 실행해야 합니다.
캐시 기반 및 조회 접근법
최적화 해를 캐싱하고 재사용하는 아이디어는 다양한 제어 맥락에서 탐구되었습니다. 한 매개변수 적응 프레임워크에서는 시스템 매개변수로 색인된 MPC 해를 저장하여 빠르게 검색합니다. 우리의 접근법은 LSH(Locality-Sensitive Hashing)를 사용하여 전체 운용 상태로 색인된 해를 캐싱하고, 운용 중 동적으로 캐시를 업데이트하며, 보행 로봇 특유의 접촉 스케줄 구조를 활용한다는 점에서 다릅니다. 우리가 아는 한, CacheMPC는 LSH 기반 캐싱과 접촉 스케줄 분할, 그리고 보행 MPC에 대한 질의별 최적성 인증서를 결합한 최초의 프레임워크입니다.
인증된 메모리 증강 MPC
검색된 제어는 현재 예측 문제의 최적성 조건에 대해 평가된 사후 인증서가 원시 실행 가능성과 예산 내 준최적성 경계를 모두 확인할 때만 수락됩니다. 이 인증서는 캐시 항목을 특성 공간에서의 휴리스틱 이웃에서 명시적 MPC 법칙의 검증된 지역 선형 조각으로 승격시킵니다. 최적 제어 맵은 활성 집합 경계에서 불연속성을 가진 구분적 선형 함수이므로, 특성 공간에서 가까운 이웃이 다른 임계 영역에 있을 수 있습니다. 질의별 인증서가 이를 배제합니다.
특성 벡터 및 LSH를 통한 후보 생성
각 캐시 항목은 운용적으로 관련된 상태를 압축한 특성 벡터로 색인됩니다(정확한 수학적 공식은 생략).
질의별 인증서
캐시에서 검색된 제어 후보(민감도 보정 가능)에 대해 인증서는 실행 가능성과 준최적성을 나타내는 두 값을 반환하며, 하나의 행렬-벡터 곱으로 계산됩니다.
예산 제한 컨트롤러 스케줄
컨트롤러는 모든 MPC 틱에서 결정론적 스케줄을 적용합니다. 틱 예산이 여러 이산 시간 창으로 분할된다고 가정합니다. 첫 번째 창 내에서는 QP를 풉니다. 솔버가 예산 내에 반환되면 최적 제어를 적용하고 캐시에 삽입합니다. 데드라인을 초과하면 마지막으로 인증된 실행 가능한 시퀀스를 시프트하여 적용합니다. 컨트롤러는 모든 틱에서 이 스케줄을 실행합니다. 일반 MPC에서는 단계 (3)의 대응이 없습니다. 데드라인을 초과한 솔버는 컨트롤러가 정의된 동작 없이 남게 합니다.
예산 제한 스트레스 테스트
단일 트롯 시행에서 의도적으로 빡빡한 데드라인 하에 스케줄을 테스트했습니다. 스케줄은 시행의 모든 틱에서 벽시계 예산을 준수했으며 넘어짐이 없었습니다. 이는 시간 압박 하의 행동을 보여주는 단일 시행의 서술적 증거이며, 통계적 비교는 아닙니다.
자주 묻는 질문
CacheMPC는 캐시된 해가 현재 상태에 유효함을 어떻게 보장하나요? 각 검색된 제어는 현재 MPC 문제의 최적성 조건에 대해 원시 실행 가능성과 예산 내 준최적성 경계를 모두 확인하는 사후 인증서로 검증됩니다.
MPC 솔버가 계산 예산을 초과하면 어떻게 되나요? 예산 제한 스케줄은 마지막으로 인증된 실행 가능한 시퀀스를 시프트하여 적용하므로, 솔버가 데드라인을 놓쳐도 컨트롤러는 항상 정의된 동작을 가집니다.
캐시는 상태 공간의 차원성에 따라 어떻게 확장되나요? CacheMPC는 Locality-Sensitive Hashing을 사용하여 고차원 특성 공간에서 해를 효율적으로 색인하고 검색하므로, 명시적 MPC를 제한하는 영역의 지수적 증가를 피합니다.
CacheMPC는 오프라인 훈련이나 사전 데이터 수집이 필요한가요? 아니요. 캐시는 운용 중에 컨트롤러가 원래 풀었을 동일한 QP에서 느리게 채워지며, 별도의 훈련이나 오프라인 최적화 단계가 필요하지 않습니다.